Математические семинары. Сложность алгоритма

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?». 

На первых двух встречах мы подробно обсудили формальное определение алгоритма как машины Тьюринга, дали определение вычислимых функций и разрешимых множеств, доказали неразрешимость знаменитой проблемы остановки и на основе этого построили некоторые примеры функций, не являющихся вычислимыми. К следующему разу было предложено самостоятельно доказать следующее утверждение: не существует алгоритма, по двум числам n и m определяющего, верно ли, что n-я и m-я машины Тьюринга на всех входах ведут себя одинаково (то есть либо обе зависают, либо дают одинаковые ответы). Тем, кто пропустил первые встречи, можно прочитать о машинах Тьюринга и проблеме остановки во второй главе книги Роджера Пенроуза «Новый ум короля».

На третьей встрече, по заявкам слушателей, начнем говорить о том, как оценивается сложность алгоритма. Дадим определение сложности и на примерах рассмотрим, что такое алгоритмы со сложностью O(n), O(n^2), O(n log n) и тому подобное. Дадим определение класса P, а если повезет со временем, то и класса NP (тех самых, о которых идет речь в той знаменитой проблеме).

От слушателей ожидается владение математикой и программированием на уровне выпускника 11-го класса профильной школы. Третья лекция не будет по содержанию зависеть от второй — достаточно лишь понимать определения машины Тьюринга и вычислимой функции. Полезно будет повторить начальные сведения из мат.анализа (свойства показательной и логарифмической функций, основные методы вычисления пределов функций).

Ведущий — Илья Мещерин, студент 5 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.