Математические основы Computer Science

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2009
Дата начала20.09.2009
Количество пар11
Язык курсарусский
Видеоhttp://video.yandex.ru/users/pdmicsclub/collection/4/
Аннотация

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

Задачи:

Задачи по теории алгоритмов: pdf

Задачи по вероятностному методу: pdf

План курса:

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

Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(17.08.2010 - 17:20)

Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа. http://video.yandex.ru/users/pdmicsclub/view/12/?cauthor=pdmicsclub&cid=4
2. Лекции 2-3
(17.08.2010 - 17:20)

Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике. Кодирование конечных последовательностей. http://video.yandex.ru/users/pdmicsclub/view/13/?cauthor=pdmicsclub&cid=4
3. Лекция 4
(17.08.2010 - 17:20)

Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя. http://video.yandex.ru/users/pdmicsclub/view/7/?cauthor=pdmicsclub&cid=4
4. Лекция 5
(17.08.2010 - 17:20)

Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо. http://video.yandex.ru/users/pdmicsclub/view/42/
5. Лекция 6
(17.08.2010 - 17:20)

Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–SAT. http://video.yandex.ru/users/pdmicsclub/view/52/
6. Лекция 7
(17.08.2010 - 17:30)

Локальная лемма Ловаса. Оценки Чернова.
7. Лекция 8
(17.08.2010 - 17:30)

Метод второго момента. Порог для 4–клики. Сепараторы.
8. Лекция 9
(17.08.2010 - 17:30)

Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды.
9. Лекции 10-11
(17.08.2010 - 17:30)

Теорема Форни. Оценки Плоткина. Код Адамара. Код Рида–Маллера. Код БЧХ.
Ваша оценка: Пусто Средняя: 2.3 (3 голосов)
Share |
Лекция Дмитрия Ицыксона