Сложность вычислений ФПМИ

Комментарий к опросу: в прошлые годы были задачи подсчёта и сложность в среднем, интерактивные доказательства и PCP будут в курсе допглав (в любом случае подробнее, чем за пару лекций), задачи поиска - на алгоритмической теории игр в магистратуре нашей кафедры, про дерандомизацию я раньше только на спецкурсе рассказывал.

Тем от обязательной части программы осталось примерно на 1-2 лекции, а самих лекций осталось 4. Какие темы было бы более интересно изучить на последних двух лекциях 1 и 8 декабря? anonymous poll Псевдослучайные конструкции и дерандомизация – 9 👍👍👍👍👍👍👍 35% Подсчёт сложности в среднем – 6 👍👍👍👍👍 23% Трудность задач аппроксимации и вероятностно проверяемые доказательства. – 5 👍👍👍👍 19% Задачи подсчёта подробно (теорема Тоды с доказательством и иерархия подсчёта) – 3 👍👍 12% Интерактивные доказательства – 3 👍👍 12% Задачи поиска (PPAD и др. классы) ▫️ 0% 👥 26 people voted so far.

Тренировочный вариант контрольной. Если от какой-либо группы будет консолидированное желание заменить на L и NL, сообщите.

Задачи на обе темы в любом случае будут, просто какие-то в этой контрольной, а какие-то в следующей.

Какие задачи включить в контрольную? Про полиномиальную иерархию (классификация и полнота на каком-то уровне) – 18 👍👍👍👍👍👍👍 67% Про классы L и NL – 9 👍👍👍👍 33% 👥 27 people voted so far.

Сейчас здесь появятся листочки с задачами первых 4 семинаров.

Также на странице курса вывешена и будет обновляться книга конспектов - http://ru.discrete-mathematics.org/fall2017/3/complexity/compl-book.pdf Решения некоторых задач там приведены.

https://docs.google.com/spreadsheets/d/12-3WWCwysKpsEpiPkaGdwwnQg2rNoCWa98ZA6jAjiSc/edit?usp=sharing - форма для выбора темы. Форма открытая, пожалуйста, обойдитесь без вандализма. Внизу есть табличка с количеством выбравших каждый проект, контролируйте, чтобы число по каждому проекту не превышало двух.

Наконец вывешен список тем для проектов. Если не понравится выбор, придумайте свою.

Это обновлённая глава про вычислительные модели из будущей книги. Будут ещё добавлены исторический раздел и задачи. Там же есть решение задачи про палиндром.

Со следующего понедельника начинается спецкурс Б.З.Мороза "Диофантовы уравнения". Начало в 18:30, аудитория 419 ГК. Аннотация: Цель этого спецкурса — доказать теорему Ю.В. Матиясевича о диофантовости перечислимых множеств. Из этой теоремы. в частности, следует существование полинома от многих переменных с целыми рациональными коэффициентами, множество положительных значений которого есть множество простых чисел. Разумеется, такого полинома от одной переменной не существует (упражнение !). Теория диофантовых уравнеий — старая и вечно новая область чистой математики. Теорема Матиясевича показывает, что любая (точно поставленная) математическая задача в принципе сводится к поиску решений некоторого диофантова уравнения. Никаких специальных знаний от слушателей курса не предполагается.

Ссылка для присоединения к чату для желающих: https://t.me/joinchat/DZlFTUSE1txDQid4LeIkbA