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