Нерешенная задача это вызов
Опять единица
Если взять пятерку, помножить на три, приплюсовать единицу, а потом поделить на два, выходит восемь, да? спрашивает меня математик Егорычев.
Кажется, да, неуверенно мямлю я и спешу оправдаться: у меня, дескать, нет склонности к точным наукам. Поэтому вы, Георгий Петрович, если можно, попроще…
А это не сложно! Поверьте!
И я вдруг начинаю верить. Настолько «вкусно» и с такими сияющими глазами он рассказывает о цифрах, так легко и стремительно выводит их строгие ряды на тетрадном листе в клеточку, так ими очарован, что не поверить и не поддаться очарованию невозможно!
Идем дальше! Восемь число четное, а четные числа в данном случае на три не умножаются они просто делятся пополам до тех пор, пока не получатся нечетные. Считаем! Восемь пополам четыре. Четыре пополам два. Два пополам один. Нечетную единицу множим на три получаем три, три плюс один четыре, четыре поделить на два два, два на два опять единица! Понимаете?! Есть предположение, что какое натуральное число ни возьми, если рассчитывать его по формуле «(3х + 1) : 2» для нечетных и по формуле «х : 2» для четных, в результате всегда останется единица! Это называется «проблема Коллатца» по имени немца Лотара Коллатца, который активно пытался решить данную проблему.
В чем же, собственно, проблема?
В том, что ни Коллатц, ни другие ученые так и не нашли решения и не доказали, верно ли предположение о единице. Хотя до определенных величин порядка 10-ти в 28-й степени задача просчитана, и конечная единица подтверждается. Однако алгоритма, доказывающего ее непременное подтверждение, пока нет, а возможно, нет в принципе. Я сам уже лет десять ломаю голову над этой загадкой, а в существовании разгадки совсем не уверен. Я, выражаясь фигурально, и очень прошу вас эту мою формулировку сохранить сижу в самом сыром и темном месте нашего организма, и не факт, что когда-то появится просвет.
Георгий Петрович, извините за глупый вопрос, но смысл Вам там сидеть? Какая от всей этой высокой математики низменная практическая польза?
Конечно, можно ответить: никакой. А можно ответить: громадная! Математические расчеты применяются в программировании, в оборонке… Кстати, во времена «холодной войны» в КГБ ходили слухи, что проблему Коллатца придумало ЦРУ и подкинуло советским компьютерщикам, чтобы те все свои силы тратили на ее решение и не занимались ничем другим, а в ЦРУ, наоборот, думали, что это «привет» из КГБ.
Если же рассуждать глобально, то любая нерешенная задача это вызов. Почему 400 лет миру не давала покоя теорема Ферма? Потому что доказать ее означало не просто доказать теорему, но и доказать торжество человеческого разума!
Громкое имя
Не знаю, как цифры, но слова от частого употребления стираются и тускнеют. Выражение «ученый с мировым именем» как раз такое, тусклое и скучное. А ученый с мировым именем, доктор физико-математических наук, профессор кафедры «МОДУС» Института фундаментальной подготовки СФУ Георгий Петрович Егорычев яркий и непосредственный! Внешне он немного похож на Эйнштейна…
6 мая Егорычеву исполнилось 70 лет. День рождения он празднует в Канаде в университете Уилфида Лурье города Ватерлоо проходит конференция, организованная специально в честь юбиляра. Участвуют математики из США, Голландии, Австрии, Словении и Тайваня многие из них учились по книгам красноярского коллеги и все без исключения признают его безусловный авторитет.
А для него самого первым авторитетом стал свердловский школьный учитель Николай Иванович Слободчиков.
Егорычев у Слободчикова поначалу числился в малопримечательных хорошистах, но однажды, точно по наитию, решил уравнение, с которым другие не справились, почти правильно решил, только один нолик в конце не написал по рассеянности. Учитель поставил четверку с огромным плюсом и пригласил ученика в математический кружок. Вот так он и увлекся математикой в общем-то, случайно, хотя каждая случайность это непознанная и математически не доказуемая закономерность… «В том кружке я впервые почувствовал себя человеком!» вспоминает Георгий Петрович. А еще вспоминает, как плакала мама, Антонина Романовна, когда узнала, что сын поступил на матфак Уральского университета: «Я, причитала, хотела, чтобы ты стал инженером, а ты…» А он окончил аспирантуру, несколько лет преподавал в Уральском политехе, а потом друзья сманили в Красноярск. Первым, с кем ему предстояло встретиться, был академик Киренский, но Егорычев на встречу опоздал приехал в ноябре 1969-го, в день похорон Леонида Васильевича.
Сам он явно скромничает: «В Красноярске, говорит, математиков моего уровня человек тридцать, не меньше. Здесь вообще люди уникальные потомки мятежных ссыльных и тех рисковых романтиков, которые ехали за туманом и за запахом тайги, поэтому неординарность у красноярцев в крови, и талантливых тут очень много…». Талантливых, может, и много, но немногие за свою жизнь успели сделать столько, сколько сделал Георгий Петрович. В Красноярске Егорычев организовал несколько кафедр, в том числе кафедру прикладной математики в тогдашнем КГУ и кафедру «МОДУС» (математическое обеспечение дискретных устройств и систем) в Политехническом институте. Кроме того и этим он особенно гордится был организатором и руководителем Высшей Математической Школы для инженеров. Работал в Институте физики и Вычислительном центре Сибирского отделения Академии наук. Написал около сотни научных статей и две монографии (включая дважды переизданную на Западе книгу «Интегральное представление и вычисление комбинаторных сумм»).
В 1982 году Егорычев стал лауреатом премии им. Д.Р. Фулкерсона. Эта премия, присуждаемая Обществом математического программирования и Американским математическим обществом, считается самой престижной в области дискретной (компьютерной) математики. Из всех российских математиков лишь четверо являются ее обладателями!
Георгий Петрович получил премию Фулкерсона за доказательство гипотезы Ван дер Вардена. И хотя он отзывается о своем успехе с присущей ему скромностью и несколько вскользь: «Ну а что тут такого? Гипотезы для того и существуют, чтобы их доказывать. Это своего рода экзамен для ученых…» тем не менее, доказательство гипотезы Ван дер Вардена стало настоящим событием в научном мире!
Мы не Канада, нам ученых не надо?
Вот, держите! Георгий Петрович достает из кармана и протягивает мне симпатичную ракушку. Я ее нашел на берегу озера Гурон в свой прошлый приезд в Канаду. Обычно привожу таких сувенирчиков целый мешок и, как Дед Мороз, хожу, раздариваю.
Спасибо! А в Канаде Вы, значит, завсегдатай?
Ну, не то чтобы, но за последние годы пять раз ездил в качестве приглашенного профессора. А в советское время, конечно, был невыездным: беспартийный, женат во второй раз да еще с характеристикой «не уважает начальство» кто такого выпустит? Поэтому о своей мировой известности даже не догадывался! Помню, когда меня впервые в Канаде с распростертыми объятиями встретили, я изумился! Подумал: «Может, они считали, что я давно умер, и поверить не могут, что я живой?!» Вообще внимание со стороны иностранцев, безусловно, радует. Огорчает, что в России внимания не уделяют.
Нет пророка в своем отечестве?
Да какой я пророк! И я не о себе говорю об общей ситуации. На Западе профессора уважаемые, состоятельные люди. У нас, вроде, тоже уважаемые, но лишь на словах, а с материальным эквивалентом уважения как-то туговато зарплаты скромные, и такой востребованности, нужности своей, здесь не ощущаешь.
Почему так?
Возможно, потому, что в России хоть и провозглашен курс на инновационную экономику знаний, но на деле экономика остается сырьевой…
У нас в квартире газ! А также нефть и прочие ископаемые.
Вот именно. И к чему нам какие-то высоколобые ученые, если мы всей страной работаем исключительно на добывающую и перерабатывающую промышленность?
Так выглядит Университет Ватерлоо в Канаде
В таком случае, не хотелось ли Вам переехать на Запад, в ту же Канаду?
Нет, никогда! Хотя предлагали… В Канаде, разумеется, сытнее, спокойнее в Ватерлоо за последние пять лет произошло одно-единственное убийство! И экология там лучше. Но… Там женщины некрасивые! А если серьезно, главное, что меня сдерживает, некоторая зависимость западных ученых, необходимость выполнять, прежде всего, пожелания заказчика. В России больше свободы: никто тебя не поддерживает, не замечает, но зато никто и не мешает особо, не диктует условия.
Поэтому я прекрасно понимаю тех наших специалистов, которые не уезжают за границу навсегда, а ездят туда, так сказать, «на заработки». К примеру, известный математик Хованский по полгода работает на Западе за деньги, по полгода в России практически бесплатно… Я, кстати, тоже подвижничеством занимаюсь привожу из Канады тяжеленные чемоданы книг, учебников, методических материалов. Меня в тамошней университетской библиотеке даже лишили права ксерокопирования я у них всю бумагу извел! А в нынешнюю свою поездку хочу попросить иностранных профессоров приехать с лекциями в СФУ. Думаю, по случаю моего дня рождения они мне не откажут!
Твори добро!
Георгий Петрович рассказывал еще много интересного. Сравнительно о России и Канаде. Познавательно о цифрах. Вполне компетентно о медицине, в которой, как оказалось, разбирается не хуже профессионального врача. С трепетным восхищением и нежностью о жене Зиночке, Зинаиде Валентиновне… В конце разговора он сказал: «Вы знаете, начинать всегда нужно с себя с самого взыскательного отношения к своим поступкам, с собственной личной порядочности, с добра, которое ты делаешь для окружающих.
Тогда, наверное, и окружающие станут добрее. Это как льдинка, которая все вокруг себя обмораживает…». По-моему, не очень удачное сравнение. Льдинка она ведь холодная. А от знакомства с математиком Егорычевым легко и тепло.
P=NP? Важнейшая нерешенная задача теоретической информатики / Хабр
nil
Занимательные задачки
Эта задача была сформулирована в 1971 году и до сих пор остается нерешенной. За доказательство утверждения P=NP или за доказательство его опровержения Математическим институтом Клэя назначена премия в 1 миллион долларов США. Если все-таки окажется, что P=NP, то это даст возможность быстро и эффективно решать множество трудноразрешимых на данный момент задач.
Так в чем же все-таки суть проблемы?
Понятия классов сложности P и NP изучаются теорией сложности вычислений.
К классу P (Polynomial time) относятся простые задачи, которые можно решить за полиномиальное время по отношению к длине ввода. Примером такой задачи может служить сортировка массива. В зависимости от выбранного алгоритма сортировки, для массива длиной n, количество выполненных операций будет от O(n*log(n)) до O(n2). Таким образом, простота алгоритмов, принадлежащих к классу P заключается в том, что при увеличении длины ввода, время выполнения увеличивается незначительно.
К классу NP (Non-deterministic Polynomial time) относятся задачи для которых проверку решения можно осуществить за полиномиальное время. Заметьте, что речь идет лишь о проверке уже найденного решения. Сложность задач этого класса заключается в том, что непосредственно нахождение решения требует значительно большего, чем полиномиальное, времени. Рассмотрим в качестве примера задачу о сумме подмножеств. Она формулируется следующим образом: «в данном множестве целых чисел, имеется ли хотя бы одно непустое подмножество сумма элементов которого равняется нулю?» Например пусть нам дано множество {5, -2, 17, 10, -4, -8}.
Для него ответ на поставленный вопрос «да«, поскольку искомое подмножество существует: -2+10-8=0. Легко убедиться, что проверка решения осуществляется быстро (нужно лишь просуммировать элементы найденного подмножества). Но на поиск решения необходимо затратить экспоненциальное время, поскольку необходимо проверить все возможные подмножества. Количество возможных комбинаций составляет 2n для ввода длиной n. Это делает решение поставленной задачи непрактичным для больших значений n.
Итак, возвращаемся непосредственно к проблеме P=NP. Положительный ответ будет означать, что возможно выполнение NP алгоритмов за полиномиальное время. Если это будет доказано, к примеру, для приведенной выше задачи о сумме подмножеств, то тоже самое будет справедливо и для многих других сложных задач. Дело в том, что существует особый класс NP алгоритмов, называемый NP-complete для которого доказано, что любая задача принадлежащая к нему может быть легко сведена к любой другой задаче этого класса.
Вот список некоторых известных NP-complete задач:
- Задача коммивояжёра
- Задача о сумме подмножеств
- Задача выполнимости булевой формулы
- Задача о раскраске графа
- Задача о рюкзаке
В заключение можно сказать, что хотя вопрос о равенстве классов P и NP до сих пор не решен, многие специалисты склонны считать, что они не равны. В поддержку этого мнения приводится довод, что уже на протяжении более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач. Но окончательно точку в споре поставит лишь строгое математическое доказательство.
Теги:
- теоретическая информатика
- теория алгоритмов
- классы сложности
- проблемы тысячелетия
Хабы:
- Занимательные задачки
Всего голосов 96: ↑84 и ↓12 +72
Просмотры13K
Комментарии 376
@nil
Пользователь
Комментарии Комментарии 376
10 самых увлекательных нерешенных проблем в мире
Эбби Норман | Проверено Саванной Кокс
Опубликовано 7 июня 2015 г.
Обновлено 13 июня 2019 г.
Эти нерешенные вопросы продолжают волновать умы практиков во всех дисциплинах современной науки и гуманитарных наук.
Помимо вездесущей логической задачи «Если дерево упадет в лесу», бесчисленные загадки продолжают будоражить умы практиков во всех дисциплинах современной науки и гуманитарных наук.
Вопросы типа «Есть ли универсальное определение «слова»?», «Цвет в нашем сознании или он существует физически, присущ объектам окружающего нас мира?» и «Какова вероятность того, что завтра взойдет солнце?» продолжают будоражить даже самые проницательные умы. Взятые из медицины, физики, биологии, философии и математики, вот некоторые из самых увлекательных вопросов без ответа в мире — у вас есть ответ на любой из них?
Интересные нерешенные проблемы: почему клетки совершают самоубийство?
Источник: Giphy
Биохимическое явление, известное как апоптоз, иногда называют «запрограммированной гибелью клеток» или «клеточным самоубийством».
По причинам, которые науке еще предстоит полностью понять, клетки, по-видимому, обладают способностью «отмирать» строго регулируемым, ожидаемым образом, который полностью отличается от некроза (гибели клеток, вызванной болезнью или травмой). Где-то от 50 до 80 миллиардов клеток умирает в результате запрограммированной клеточной смерти в среднем человеческом теле каждый день, но механизм этого и даже намерения не совсем понятны.
С одной стороны, слишком большая запрограммированная гибель клеток приводит к атрофии мышц и связана с заболеваниями, вызывающими крайнюю, но в остальном необъяснимую мышечную слабость, тогда как слишком слабый апоптоз позволяет клеткам пролиферировать, что может привести к раку. Общая концепция апоптоза была впервые описана немецким ученым Карлом Фогтом в 1842 году. В ее понимании был достигнут значительный прогресс, но более глубокие загадки этого процесса все еще существуют.
Вычислительная теория разума
Источник: Giphy
Некоторые ученые сравнивают деятельность разума с тем, как компьютер обрабатывает информацию.
Таким образом, вычислительная теория разума была разработана в середине 1960-х годов, когда человек и машина впервые начали всерьез бороться за существование друг друга. Проще говоря, представьте, что ваш мозг — это компьютер, а ваш разум — это операционная система, которой он управляет.
В контексте информатики можно провести захватывающую аналогию: теоретически программы производят выходные данные исключительно на основе набора входных данных (внешние стимулы, зрение, звук и т. д.) и памяти (что здесь означает как физическое жесткий диск и нашу психологическую память). Программы выполняются с помощью алгоритмов, которые имеют конечное число шагов, повторяющихся в соответствии с получением различных входных данных. Подобно мозгу, компьютер должен отображать то, что он физически не может вычислить, — и это один из основных аргументов в пользу данной конкретной теории.
Однако вычислительная теория отличается от репрезентативной теории разума тем, что она допускает, что не все состояния являются репрезентативными (например, депрессия) и, следовательно, не будут реагировать на лечение, основанное на вычислениях.
Проблема скорее философская, чем какая-либо другая: вычислительная теория разума работает хорошо, за исключением случаев, когда речь идет о том, как «перепрограммировать» депрессивный мозг. Мы не можем перезагрузиться к заводским настройкам.
Эбби Норман — писательница из Новой Англии, в настоящее время пишет мемуары для Nation Books. Ее работы были представлены на The Rumpus, The Independent, Cosmopolitan, Medium, Seventeen, Romper, Bustle и Quartz.
Подпишитесь на информационный бюллетень ATIНерешенные проблемы в операционной
Кембриджский университет > Математика > Статистическая лаборатория > Ричард Вебер > Нерешенные проблемы
Эта страница содержит список открытых проблем, которые я обнаружил
интригующий. Это не большие проблемы (например, равно ли P NP или нет), но все они просты.
заявить и понять, и их решение бросило вызов усилиям
хороших исследователей на протяжении ряда лет.
Этот набор задач отражает мои собственные интересы и не претендует на полноту. Большинство этих проблем находится в область стохастического динамического программирования и оптимизации. хотелось бы увидеть решение любая из этих проблем
Я заметил, что эта страница получает довольно много интернет-трафика, поэтому я попытаюсь обновить ее в ближайшее время и добавить некоторые другие проблемы. Я также реализовал место в конце этой страницы, где люди, просматривающие ее, могут оставлять комментарии ..
Был достигнут значительный прогресс в решении первых двух из этих проблем, который не описан здесь полностью, но который можно найти на других моих веб-страницах. Я делаю несколько кратких комментариев ниже (пишу 23 октября 2011 г.). Если у кого-то есть какие-либо новости о любой из этих проблем, или хотел бы предложить проблему. Пожалуйста, свяжитесь со мной.
Связанная с этим интересная страница — «Мифы и контрпримеры в математическом программировании» Харви Гринберга.
Проблема бомбардировщика
(см. описание) Эта проблема возникла в 1960-х годах и долгие годы оставалась нерешенной. В приведенной ниже статье я показал, что гипотеза B ложна, если обычные предположения лишь слегка смягчены. См.
Р. Р. Вебер, Азбука проблемы бомбардировщика и ее родственники, 2011.
Интересно, что Такаси Камихигаси теперь показал, что гипотеза B ложна. См.
T. Kamihigashi, 41 Контрпримеры к свойству (B) задачи бомбардировщика с дискретным временем, 2016.
Он сделал это с помощью исчерпывающего поиска по 9k, q = 0,829, и атаки происходят с вероятностью r = 0,830, он находит, что за 6 шагов оптимальное количество ракет для запуска равно 16, когда количество оставшихся ракет равно 88, и 17, когда количество оставшихся ракет меньше. номер 87.
Задача рандеву
(см. описание) Есть много нерешенных проблем рандеву. Однако теперь проблема с полным графом K3 решена. Видеть
Р. Р. Вебер, Оптимальная стратегия поиска рандеву на К3, 2006.
Остается много интересных открытых вопросов. Например, рассмотрим игру, в которую играют на полном графе из N вершин. Никому никогда не удавалось показать, что значение рандеву (минимальное ожидаемое время рандеву) увеличивается в N.
Особенно интересна задача симметричного поиска рандеву на прямой. Игроки начинают на расстоянии 2 единиц друг от друга, не зная, находится ли другой игрок впереди или позади на 2 единицы. На каждом шаге каждый игрок перемещается вперед или назад на 1 единицу. Первоначально игрокам может быть сказано, что они смотрят в одном направлении, или им может быть сказано, что направления их взглядов являются случайными. Что касается минимизации ожидаемого времени встречи, кажется, не имеет значения, какое начальное условие задано. Объясните это!
Поиск движущейся цели
(см. аннотацию) Давным-давно я решил версию этой задачи с непрерывным временем.
Р. Р. Вебер. Оптимальный поиск случайно движущегося объекта.
Дж. Заявл. Проб. 23:708-717, 1986.
Но дискретная версия этой проблемы до сих пор не решена. Были частные решения, но не было решения для всех возможных значений параметров модели.
Неупреждающий выпуск стохастических заданий на однородные машины
См. реферат а также Р. Р. Вебер. О гипотезе о распределении заданий по разным скоростям процессоров. IEEE транс. Авто. Control 38, 166-169, 1993.
Я делаю предположение, что оптимальная политика обладает тем свойством, что всякий раз, когда она назначает задание доступному процессору, она назначает самый быстрый доступный процессор. Кроме того, существуют пороги, по одному для каждого состояния процессоров и уменьшающиеся в состоянии (рассматриваемые как логический вектор, в котором занятые и незанятые процессоры обозначены 1 и 0 соответственно), так что оптимальная политика заключается в назначении задание доступному процессору тогда и только тогда, когда количество заданий в буфере превышает соответствующий порог для текущего состояния процессоров.
Неважность вставленного времени простоя в невытесняющее стохастическое планирование для минимизации времени потока на параллельных машины
Предположим, у вас есть n заданий, которые должны быть обработаны на m идентичных машинах, работающих параллельно (m
{v_1–1}, и поэтому априорное среднее значение u_i/(u_i+v_i). Такое плечо возникает, если мы начнем с плеча, для которого предполагается, что p равномерно распределено на [0,1], а затем выберем его u_i+v_i–2 раза и отметим u_i–1 успехов и v_i–1 неудач.
Предположим, что группа 1 предлагает наибольшую непосредственную вероятность успеха при следующей выборке, т. е. u_1/(u_1+v_1) >=u_2/(u_2+v_2). Предположим, что в плече 1 выборка также меньше, так что u_1+v_1<=u_2+v_2. Цель состоит в том, чтобы провести еще N испытаний среди этих двух рук таким образом, чтобы максимизировать ожидаемое общее количество полученных успехов. Гипотеза Берри состоит в том, что в этих обстоятельствах следующее испытание должно быть оптимальным для руки 1. Интуитивно это очень правдоподобно, поскольку рука 1 не только предлагает большее немедленное вознаграждение, но и дает больше полезной информации, которую можно получить, взяв пробу из руки 1 (поскольку, таким образом, далеко он был выбран меньше).
Гипотеза, очевидно, верна, если N=1.
Вероятно, это может быть доказано для малых N. Это верно (из-за результатов индекса Гиттинса), когда временной горизонт бесконечен, а вознаграждение геометрически дисконтировано. Но статус гипотезы для конечного N и отсутствия дисконтирования остается нерешенным.
Д. А. Берри (1972) Двурукий бандит Бернулли. Энн. Мат. Статист . 43 871-897.
Некоторые связанные работы и комментарии к этой гипотезе появляются в
Ю. Ю. (2011) Предварительный порядок и монотонность в бандитах Дирихле, http://arxiv.org/abs/1101.4903
Гипотеза Ракла для игр с накоплением
Эта открытая проблема описана С. Альперном, Р. Фоккинком и К. Кикутой. Гипотеза Ракла для игр с накоплением, SIAM Journal on Control and Optimization, 48 (8). стр. 5073-5083. ISSN 0363-0129. В аннотации к этой статье говорится:
«В игре на накопление Прячущийся тайно распределяет свое общее богатство h между n местами, в то время как Искатель выбирает r мест и конфискует размещенный там материал.