Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.
В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».
В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, среди которых одна из проблем тысячелетия — проблема «P=NP?».
За прошедшие пять встреч мы обсудили машины Тьюринга и проблему остановки, понятие сложности алгоритма с иллюстрациями на примерах, а также определения P, NP и суть упомянутой проблемы тысячелетия.
Подробный список пройденного, а также некоторые задачи для самостоятельного обдумывания расположены на страничке: http://mesyarik.ru/17/kocherga_algo...
На ближайшей встрече мы поговорим об NP-полных задачах — важнейшем понятии из теории сложности вычислений. Разберемся, как, имея решатель для некоторой конкретной задачи (а именно задачи о булевых формулах), можно с его помощью решить любую задачу из NP. После этого докажем (если успеем, конечно), что вместо задачи о булевых формулах на эту роль «универсальной задачи» подходит и многое другое — например, пресловутая задача о гамильтоновом цикле.
От слушателей ожидается владение математикой и программированием на уровне выпускника 11 класса профильной школы. Для доказательств заявленных утверждений нам вновь потребуется работать с машинами Тьюринга, поэтому нужно понимать их определение и смысл.
Ведущий — Илья Мещерин, студент 5 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.
Встречи проходят по вторникам в 20:00 в антикафе Кочерга.
Мероприятие вконтакте