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

Профессор нашей кафедры Алексей Савватеев борется за приз зрительских симпатий премии "Просветитель". Его можно поддержать вот по этой ссылке: https://m.vk.com/wall-74404187_672899

Обновлённый тренировочный вариант в связи с переносом контрольной - будет задача про PSPACE, а про диагонализацию какая-то одна

Централизованная контрольная будет 14 ноября вместо лекции. Если какие-то группы это по какой-то причине не устраивает, то можно договориться отдельно. Поскольку контрольная сдвинулась, в ней также будет задача про PSPACE-полноту (пройдём сегодня). А про диагонализацию и оракулы будет только одна задача.

Также напоминаю, что сегодня нужно зафиксировать тему проекта, если вы собираетесь его делать. Дальше в любой момент редактирование файла со списком проектов может быть отключено, и после этого взять проект (а значит, и получить "отлично" за курс) будет нельзя.

Тренировочный вариант контрольной, про дату сейчас будет опрос в чате

В среду будет очень интересный доклад, приходите!

Предварительная дата первой контрольной: через 2 семинара, т.е. 26/30 октября.

http://www.nada.kth.se/~viggo/problemlist/ - ещё один список NP-полных задач, где можно искать темы для проектов, если из предложенного списка ничего не приглянулось.

Сегодня на межкафедральном семинаре (18:30, 115 КПМ) будет интересный доклад Николая Мощевитина
"Диофантовы приближения и квадратичные формы" Аннотация:
Я расскажу о классических и совсем новых результатах о равномерных приближениях точек на квадратичных поверхностях рациональными точкам. В частности, я попробую объяснить, почему законы приближения на сфере в Rn такие же, как на вещественной прямой R.

Список проектов и правила

https://docs.google.com/spreadsheets/d/1n1GvkogrZPe10Va0HzlvT70LblAReEUnIt7NJK-z9bU/edit?usp=sharing - в эту таблицу можно будет записывать номера выбранных проектов. Если есть своя тема, впишите номер 0 и комментарий. Внизу табличка со списком, какой проект сколько раз выбран. Если больше двух, то строка загорается красным - тогда нужно кому-то выбрать другой, либо всем явно указать разные спецификации. Не занимайтесь вандализмом, портя чужие строки! Конфликты решайти коммуникацией, а лучше придумыванием своих тем. Сам файл со списком выложу в 18:00.

Вчерашняя презентация с межкафедрального семинара. Все картинки взяты из compl-book.pdf (в основном глава 10)

Текущая версия книги про сложность вычислений.

Завтра, 12.09, в 18:30 в 115 КПМ будет межкафедральный семинар. Сначала будет доклад Ильи Шкредова про аддитивную комбинаторику, потом я расскажу про вычислительную сложность задач поиска и их связь с математической экономикой.

На всякий случай повторяю ссылку на чат по спецкурсу о псевдослучайности и дерандомизации: https://t.me/joinchat/DZlFTRI3Dvope1VxBqmUng
Занятия будут проходить по четвергам в 16:15 в ШАДе (м. Парк Культуры). Если есть желающие ходить 3-курсники, которым расписание неудобно, сообщите об этом.

Для присоединившихся: ссылка на чат для обсуждения оперативных вопросов https://t.me/joinchat/DZlFTUSE1txDQid4LeIkbA

Также на второй неделе начнётся спецкурс по псевдослучайности и дерандомизации. Для него тоже есть отдельный чат: https://t.me/joinchat/DZlFTRI3Dvope1VxBqmUng

В новом семестре этот канал будет использоваться для рассылки новостей по предметам у третьего курса. По криптографии у четвёртого курса создан отдельный чат: https://t.me/joinchat/DZlFTQ8qiK7Ymz7GXLiaKw

Напоминание информации из чата: контрольная по дополнительным главам будет сегодня в 10:30, аудитория Гарвард.

Наконец готово домашнее задание по курсу дополнительных глав. Подробные правила в шапке файла, прочтите внимательно.