Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Математические основы Computer Science
Осень 2009, посмотреть все семестры

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

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

План курса:

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