City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Introduction to Theoretical Computer Science
Saint Petersburg / autumn 2013, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

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

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

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

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

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

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