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

Обзорный курс по теоретической информатике
Санкт-Петербург / осень 2013, посмотреть все семестры

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

Курс призван познакомить слушателей с некоторыми классическими результатами и идеями теоретической информатики (Theoretical Computer Science), которые будут полезны как исследователям, так и программистам, желающим расширить свой кругозор. В частности:

  • Мы узнаем, что теоретическая информатика предлагает свои трактовку понятия доказательства: если в математике доказательство обязано быть текстом, то информатика рассматривает случаи, когда доказательство — это интерактивный процесс, иногда для проверки доказательства его не обязательно полностью прочитывать, а иногда можно доказывать, не сообщая никакой дополнительной информации, кроме верности доказываемого утверждения.

  • Выясним, как случайные числа помогают при построении алгоритмов и сведений между задачами.

  • Покажем, что коды, исправляющие ошибки, используемые для передачи информации по зашумленным каналам, могут быть использованы в криптографии.

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

  • Познакомимся с классическими параллельными алгоритмами.

  • Узнаем классическое и алгоритмическое понятие количества информации.

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

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

Дата и время Занятие Место Материалы
12 сентября
18:30–19:50
О понятии "доказательства" в информатике, Лекция ПОМИ РАН Нет
12 сентября
20:00–21:50
Практическое занятие № 1, Семинар ПОМИ РАН файлы
19 сентября
18:30–19:50
Короткие доказательства, класс NP, Лекция ПОМИ РАН Нет
19 сентября
20:00–21:20
Практическое занятие № 2, Семинар ПОМИ РАН файлы
26 сентября
18:30–19:50
Решение оптимизационных задач: вероятностное округление, Лекция ПОМИ РАН Нет
26 сентября
20:00–21:20
Практическое занятие № 3, Семинар ПОМИ РАН файлы
03 октября
18:30–19:50
Линейное программирование, Лекция ПОМИ РАН Нет
03 октября
20:00–21:30
Практическое занятие № 4, Семинар ПОМИ РАН файлы
10 октября
18:30–19:50
Двойственность задач линейного программирования, матричные игры, Лекция ПОМИ РАН Нет
10 октября
20:00–21:20
Практическое занятие №5, Семинар ПОМИ РАН файлы
17 октября
18:30–19:50
PCP-теорема и трудность приближения. Конечные автоматы, Лекция ПОМИ РАН Нет
17 октября
20:00–21:20
Практическое занятие №6, Семинар ПОМИ РАН файлы
24 октября
18:30–19:50
Вычисления с маленькой памятью, Лекция ПОМИ РАН Нет
24 октября
20:00–21:20
Практика 7, Семинар ПОМИ РАН файлы
31 октября
18:30–19:50
Вычисления с маленькой памятью и параллельные вычисления, Лекция ПОМИ РАН Нет
31 октября
20:00–21:20
Практика 8, Семинар ПОМИ РАН файлы
07 ноября
18:30–19:50
Параллельные вычисления. Коды, исправляющие ошибки, Лекция ПОМИ РАН Нет
07 ноября
20:00–21:20
Практика 9, Семинар ПОМИ РАН файлы
14 ноября
18:30–19:50
Коды Адамара и Рида-Соломона. Коммуникационная сложность, Лекция ПОМИ РАН Нет
14 ноября
20:00–21:20
Практика 10, Семинар ПОМИ РАН файлы
21 ноября
18:30–19:50
Маленькие k-независимые множества. Энтропия, Лекция ПОМИ РАН Нет
21 ноября
20:00–21:20
Практика 11, Семинар ПОМИ РАН файлы
28 ноября
18:30–19:50
Колмогоровская сложность, Лекция ПОМИ РАН Нет
28 ноября
20:00–21:20
Практика 12, Семинар ПОМИ РАН файлы
05 декабря
18:30–19:50
Конструктивный вариант локальной леммы Ловаса. Условная колмогоровская сложность, Лекция ПОМИ РАН Нет
05 декабря
20:00–21:20
Практика. Зачет, Семинар ПОМИ РАН файлы