Лектор: Дмитрий Михайлович Ицыксон
Язык курса: русский
Задачи:
Задачи по теории алгоритмов: pdf
Задачи по вероятностному методу: pdf
Слайды лекций:
| Число | Название | Слайды | tube | mp4 | Содержание лекции |
|---|---|---|---|---|---|
| 20.09.2009 | Лекция 1 | 1 | 1 | Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа |
|
| 27.09.2009 | Лекции 2 и 3 | 2 3 |
2 3 |
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике. Кодирование конечных последовательностей. | |
| 04.10.2009 | Лекция 4 | 4 | 4 | Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя. | |
| 01.11.2009 | Лекция 5 | 5 | 5 | Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо. | |
| 08.11.2009 | Лекция 6 | 6 | 6 | Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–SAT. | |
| 15.11.2009 | Лекция 7 | 7 | 7 | Локальная лемма Ловаса. Оценки Чернова. | |
| 06.12.2009 | Лекция 8 | 8 | 8 | Метод второго момента. Порог для 4–клики. Сепараторы. | |
| 06.12.2009 | Лекция 9 | 9 | 9 | Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды. | |
| 06.12.2009 | Лекции 10 и 11 | 10, 11 | 10, 11 | Теорема Форни. Оценки Плоткина. Код Адамара. Код Рида–Маллера. Код БЧХ. |
Краткое описание курса:
В обзорный по тематике курс войдут яркие сюжеты из теории алгоритмов, комбинаторики, теории графов и алгебры, на которых будут продемонстрированы идеи и методы, часто применяющиеся в современных работах по теоретической информатике. Курс подходит для начинающих, но может быть интересен и тем, кто уже заглядывал в клуб.
План курса:
- Теория алгоритмов
- Вычислимые функции, разрешимые и перечислимые множества.
- Универсальный алгоритм.
- Перечислимое неразрешимое множество.
- Теорема Клини о неподвижной точке.
- Теорема Успенского–Райса.
- Машины Тьюринга.
- Предикатные формулы, неразрешимость исчисления предикатов.
- Выразимость в арифметике. Арифметичность вычислимых функций.
- m–сводимость. Арифметическая иерархия.
- Теоремы Тарского и Геделя.
- Вероятностный метод в комбинаторике
- Основы теории вероятностей.
- Основная идея вероятностного метода.
- Линейность математического ожидания и ее применение.
- Метод малых вариаций.
- Локальная лемма Ловаса.
- Оценки Чернова.
- Метод второго момента.
- Коды, исправляющие ошибки
- Границы Хэмминга и Гилберта
- Линейные коды. Код Хэмминга.
- Код Рида–Соломона.
- Каскадные коды.
- Оценки Плоткина. Коды Адамара.
- Коды БЧХ.