Составил файл с программой курса. В нём расширенный список тем (скорее всего, пройдём меньше), а также подробные правила выставления оценки. Изучите их внимательно.

#дневниклекций
Сегодня была вторая лекция про NP-полноту. Обсуждали несколько конкретных задач, а также задачи поиска. Изучили вот что:
- Задачи, связанные с гамильтоновыми путями: HAMPATH (существует ли гамильтонов путь в орграфе из s в t), HAMCYCLE (существует ли гамильтонов цикл в орграфе), аналоги для неориентированных графов, задача коммивояжёра.
- Сведение HAMPATH к HAMCYCLE: неправильность очевидной конструкции и её исправление.
- Сведение 3SAT к HAMCYCLE: гаджеты-ромбы, гирлянда и вершины для скобок, обоснование корректности сведения
- Сведение HAMPATH к UHAMPATH: недостаточность снятие ориентации, конструкция с утроением вершин
- Сведение UHAMCYCLE к TSP
- Задача NAE-SAT о существовании набора, при котором в каждой скобке есть истинные и ложные литералы. Сведение 3SAT к NAE-SAT
- Сведение NAE-SAT к 3COL
- Задачи поиска: определение, сводимость по Левину
- Сводимость задач поиска к задачам распознавания на примере задачи о клике. Рекурсивная конструкция через самосводимость
- Кратко о задачах подсчёта и аппроксимации (подробнее в следующий раз)

#дневниклекций
Сегодня были 3 слабо связанные между собой темы: задачи подсчёта, задачи аппроксимации и пэддинг. Изучили следующее:
- Постановка задачи подсчёта: по входу x нужно найти число таких y, что V(x,y)=1. Класс #P для полиномиальных V. Понятие NP-трудности для задач подсчёта. Сводимость по Куку.
- (Очевидная) NP-трудность задачи подсчёта, соответствующей NP-полной задаче распознавания. Пример, когда задача распознавания полиномиальна, а задача подсчёта NP-трудна: число простых циклов в ориентированном графе. Построение сводимости: гаджет-"конфета", замена рёбер на него, подсчёт числа циклов в двух случаях, итоговая конструкция сводимости.
- Пара слов про задачу о перманенте.
- Постановка задач оптимизации и аппроксимации. Два варианта в каждом случае: поиск оптимума и точки оптимума. Пример, когда задача точной оптимизации NP-трудна, а аппроксимации - полиномиальна (Задача о вершинном покрытии). Вариации задачи коммивояжёра: общая (NP-трудная для любой точности), метрическая (полиномиально разрешимая с множителем 3/2, алгоритм Кристофидеса-Сердюкова), евклидова (полиномиально разрешимая с любой точностью, алгоритм Ароры).
- Классы задач оптимизации и аппроксимации: NPO, APX, PTAS, FPTAS.
- Понятие об NP-трудности задач аппроксимации. Формулировка теоремы для задачи MAX3SAT: существование приближённого алгоритма с множителем 7/8 и NP-трудность аппроксимации с множителем 7/8+ε (PCP-теорема).
- Метод пэддинга (изменения масштаба задачи). Общая идея и два приложения: если P=NP, то EXP=NEXP, а также NP≠E (вывод из E≠EXP).

Как я вчера сказал на лекции, через неделю, 15 октября, будет контрольная. В этом файле написано, в каких группах какие задачи будут и в какое время к/р (у части групп во время лекции, у части на 5-й паре). Чуть позже сделают табличку, можно будет поменять время при необходимости.

Я сделал табличку с оценками, но там пока неточные данные. Давайте постараемся всё исправить до завтрашней к/р. Присылайте мне в личку (@musatych) сведения о таких случаях:
- Вы сдаёте курс, но вас нет в табличке
- Вы знаете кого-то, кто есть в табличке, но курс не сдаёт
- Вы ходите на семинары в другую группу, а в табличке в старой (даже если писали о переводе, напишите ещё раз)
- Вам не подходит время, указанное для к/р на завтра (даже если писали об этом, напишите ещё раз)
- Вы пропустите завтрашнюю к/р по уважительной причине (напишите с указанием причины)
- Есть ещё какая-то ошибка
Ссылка на табличку: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing

Рассадка на первую часть к/р, в 12:20. Приходите!

А это рассадка на вторую часть к/р, в 15:30, 110 КПМ. Приходите! Upd. В рассадке была ошибка, файл заменён в 14:13.

Если вас интересует, почему так много сообщений в чате, то обсуждается очередная странная попытка доказать, что P не равно NP. Если есть дела важнее, можно смело всё пролистать.

Публикуем обновлённый файл со списком проектов и открываем запись на них. Подробные правила описаны в файле, но основное правило выбора темы - не заявляться более чем вдвоём на одну тему, а если всё же заявились, то вписывать уточнение, почему получаются разные подтемы. Это будет проверяться. Запись открыта в табличке: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing на листе Проекты, столбцы D и E должны редактироваться. В строках 143-258 проверяется число записавшихся, там же можно искать свободные темы.

#дневниклекций
На прошедших двух лекциях 8 и 22 октября изучали полиномиальную иерархию и начали полиномиальную память. Немного подробнее про то, что было:
- Задача о проверке значения кликового числа. Почему она NP-трудна, но скорее всего не в NP. Представление её как разности двух языков из NP. Преобразование в формулу с двумя кванторами. Класс DP.
- Другие примеры возникновения формулы с двумя или тремя кванторами: минимизация формулы, кликовая раскраска, в том числе наследственная, обобщённая рамсеевость, размерность Вапника-Червоненкиса
- Определение классов полиномиальной иерархии, вложения одних в другие.
- Если P=NP, то P=PH.
- Три условия коллапсирования полиномиальной иерархии, их эквивалентность.
- Существование полных задач на уровнях иерархии. Задачи Sigma_k-SAT и Pi_k-SAT, эквивалентность друг другу их полноты в соответствующих классах для каждого k. Доказательство полноты для случая, когда последний квантор - квантор существования. Эквивалентность существования полной задачи во всей иерархии и её коллапсирования.
- Альтернирующие машины и их связь с полиномиальной иерархией.
- Игровой взгляд на задачи из PH как множества выигрышных позиций в играх с фиксированным числом ходов.
- Измерение памяти, используемой машиной. Модель с неизменяемым входом и рабочей лентой. Классы DSPACE(s(n)) и NSPACE(s(n)).
- Соотношения временных и пространственных классов: L вложено в P, PSPACE вложено в EXP, NL вложено в P (доказательство через конфигурационный граф). Формулировка теоремы Сэвича, следствие: PSPACE=NPSPACE.

Сегодня докажем теорему Сэвича и поговорим о PSPACE-полных задачах. Если останется время, посмотрим на задачи из класса L.

Новости про отчётность по курсу:
- Первая к/р проверена, в ближайшие дни сделаю дорешку
- Вчера был крайний срок выбора проектов. В связи с этим:
* Если забыли выбрать, срочно выберите, я пока ещё не закрыл редактирование
* Есть несколько нарушенных ограничений на число одинаковых проектов: 69 в группе 321 выбран дважды, 33 и 90 на курсе - трижды. В каждой коллизии нужно либо кому-то уйти на другую тему, либо всем прописать разные подтемы. Договоритесь, пожалуйста, друг с другом.

Если у вас есть знакомые в Казани, можете позвать их на мою научно-популярную лекцию!

⚪️ Задача о равенстве классов P и NP в 2000 году была включена в список из 7 задач тысячелетия, за решение которых объявлена премия в миллион долларов.
⚪️ Формулируется она так: "Есть ли универсальный способ сокращения экспоненциального перебора возможных решений до какого-то полиномиального алгоритма?" Звучит страшно? Значит тебе к нам! Приходите на лекцию и вы узнаете:

-В чем же суть этой проблемы? И почему она важна для науки и всего общества?
-Историю изучения проблемы и обнаруженные препятствия к её решению.
-Почему мы верим, что P не равно NP, но не можем этого доказать? Оказывается, целые техники доказательств заведомо не могут дать результата! Хотя считается, что установлено «экспериментальное» доказательство проблемы, но математического нет даже близко!

⚫️ Даниил Мусатов - кандидат физико-математических наук, доцент кафедры дискретной математики МФТИ (г.Москва)

🗓 22 ноября 15:00
📍 Казань, ИТ-парк, ул.Петербургская, 52
🎫 Необходима регистрация
🛸 Научный лекторий Milmax Science

#milmax

Дорешка по первой контрольной. В файле индивидуальные варианты, есть задачи, которые вы решили меньше, чем на 8 баллов, а также 2 новые задачи. Даётся 5 баллов за решение, в сумме с набранным на к/р не больше 8. За новые задачи 10 баллов. Сдача письменно семинаристу (или устно по договорённости). Срок на решение - 2 недели, до 26 ноября.

В среду, 3 декабря, будет вторая контрольная. Это тренировочный вариант с задачами. Время то же, что и у первой к/р: у части групп вместо лекции, у другой части в 15:30. Табличка в файле. Если нужно перенести на другое время или вы пропускаете по уважительной причине, пишите в личку @musatych с указанием причины.

Рассадка на сегодня, 12:20, 113 ГК. Если пропускаете по уважительной причине, пишите в личку @musatych до начала контрольной.

Рассадка на контрольную 15:30, 110 КПМ

Вторая к/р почти проверена, по ней будет дорешка со сдачей до экзамена минус 2 дня. По третьей к/р предлагается выбор: написать завтра, 17 декабря, в 12:20 по 12 баллов за задачу или дома по 8 баллов за задачу. Темы к/р: схемные классы, NC-иерархия, вероятностные классы, дерандомизация (всего 4 задачи). Выбор можно сделать на специальном листе в таблице: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing Если хотите написать очно, но завтра не подходит, тоже отметьте, можно попробовать сделать в четверг или пятницу. Если никакого выбора не делаете, то задачи будут в домашке по 5 баллов.

Также я сделал лист про дату экзамена, в той же таблице: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing
Пока что там поставлены даты из общего расписания той группы, с которой вы ходите. Если нужно перенести, отметьте там с комментарием. Перенос по неуважительной причине не гарантируется. Если вы из магистратуры, то можете выбрать любую из двух дат.

Несколько людей попросили сделать к/р в пятницу, и я сегодня тоже уже не успеваю её провести. Давайте предварительно считать, что к/р в пятницу в то же время 12:30 - если не подходит, сообщите. На вкладке можно переголосовать, давайте зафиксируем итог завтра вечером (в 22:00).