City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Mathematical Foundations of Computer Science
Saint Petersburg / autumn 2009, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

План курса:

  1. Теория алгоритмов
    • Вычислимые функции, разрешимые и перечислимые множества.
    • Универсальный алгоритм.
    • Перечислимое неразрешимое множество.
    • Теорема Клини о неподвижной точке.
    • Теорема Успенского-Райса.
    • Машины Тьюринга.
    • Предикатные формулы, неразрешимость исчисления предикатов.
    • Выразимость в арифметике. Арифметичность вычислимых функций.
    • m-сводимость. Арифметическая иерархия.
    • Теоремы Тарского и Геделя.
  2. Вероятностный метод в комбинаторике
    • Основы теории вероятностей.
    • Основная идея вероятностного метода.
    • Линейность математического ожидания и ее применение.
    • Метод малых вариаций.
    • Локальная лемма Ловаса.
    • Оценки Чернова.
    • Метод второго момента.
  3. Коды, исправляющие ошибки
    • Границы Хэмминга и Гилберта
    • Линейные коды. Код Хэмминга.
    • Код Рида-Соломона.
    • Каскадные коды.
    • Оценки Плоткина. Коды Адамара.
    • Коды БЧХ.
Date and time Class|Name Venue|short Materials
20 September
17:20–18:50
Лекция 1, Lecture ПОМИ РАН slides
27 September
17:20–18:50
Лекции 2-3, Lecture ПОМИ РАН slides
04 October
17:20–18:50
Лекция 4, Lecture ПОМИ РАН slides
01 November
17:20–18:50
Лекция 5, Lecture ПОМИ РАН slides
08 November
17:20–18:50
Лекция 6, Lecture ПОМИ РАН slides
15 November
17:30–19:00
Лекция 7, Lecture ПОМИ РАН slides
06 December
17:30–19:00
Лекция 8, Lecture ПОМИ РАН slides
06 December
17:30–19:00
Лекция 9, Lecture ПОМИ РАН slides
13 December
17:30–19:00
Лекции 10-11, Lecture ПОМИ РАН slides