Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Математические основы Computer Science
Санкт-Петербург / осень 2009, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

План курса:

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