В обзорный по тематике курс войдут яркие сюжеты из теории алгоритмов, комбинаторики, теории графов и алгебры, на которых будут продемонстрированы идеи и методы, часто применяющиеся в современных работах по теоретической информатике. Курс подходит для начинающих, но может быть интересен и тем, кто уже заглядывал в клуб.

План курса:

1. Теория алгоритмов
   • Вычислимые функции, разрешимые и перечислимые множества.
   • Универсальный алгоритм.
   • Перечислимое неразрешимое множество.
   • Теорема Клини о неподвижной точке.
   • Теорема Успенского-Райса.
   • Машины Тьюринга.
   • Предикатные формулы, неразрешимость исчисления предикатов.
   • Выразимость в арифметике. Арифметичность вычислимых функций.
   • m-сводимость. Арифметическая иерархия.
   • Теоремы Тарского и Геделя.
2. Вероятностный метод в комбинаторике
   • Основы теории вероятностей.
   • Основная идея вероятностного метода.
   • Линейность математического ожидания и ее применение.
   • Метод малых вариаций.
   • Локальная лемма Ловаса.
   • Оценки Чернова.
   • Метод второго момента.
3. Коды, исправляющие ошибки
   • Границы Хэмминга и Гилберта
   • Линейные коды. Код Хэмминга.
   • Код Рида-Соломона.
   • Каскадные коды.
   • Оценки Плоткина. Коды Адамара.
   • Коды БЧХ.