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

Selected Topics in Computer Science
Saint-Petersburg / autumn 2018, посмотреть все семестры

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

Классификация задач по сложности алгоритмического решения. Разрешимые и полуразрешимые (перечислимые) множества.

Доказательства и перечислимость. Неразрешимость проблемы остановки.

Почему не все истины можно доказать (Гёдель). Сведение как метод доказательства неразрешимости.

Игра Конвея.

Полиномиально разрешимые задачи, хорошие и плохие вычислительные модели.

Схемная сложность. Полиномиальные задачи имеют полиномиальные схемы.

Неконструктивное доказательство существования сложных задач. Задачи из класса NP: примеры. Полиномиальные сведения задач: примеры. CIRCUIT-SAT к 3SAT. Полнота задачи 3SAT.

Двойственность: препятствие к существованию решения в виде конкретного объекта, на примере Форда-Фалкерсона.

Исчисление резолюций и его полнота.

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

Конечная игра с полной информацией: препятствие к выигрышной стратегии одного игрока - выигрышная стратегия второго.

Полиномиальные игры и их решение в классе PSPACE.

Пример полной полиномиальной игры.

Вероятностные алгоритмы. Что такое вероятностное пространство и где оно в этих алгоритмах.

Почему для абстрактной вычислимости вероятностные алгоритмы не помогают. Порядковая статистика и среднее линейное время.

Быстрая сортировка и среднее логарифмическое время.

Коммуникационная сложность и проверка равенства с логарифмической сложностью и с \(O(1)\) сложностью с публичными битами. Проверка полиномиальных тождеств в случайной точке. one-time pad и надёжность (неотличимость).

Amplification, \(BPP \subset P_{/poly}\).

Конечные автоматы и теорема Клини.

Коды: граница Хемминга и Варшамова-Гилберта.

Код Рида-Соломона. Беспрефиксные коды, лемма Крафта, энтропия.

Интерактивные доказательства: определение.

Неизоморфизм графов.

Zero-knowledge proofs.

Изоморфизм графов.

Псевдослучайные генераторы: определение.

Как из одного бита сделать несколько: hybrid argument.

Ценность сложных задач: разложение на простые как модель digital cash.

Колмогоровская сложность, отсутствие вычислимых нижних оценок, парадокс Ришара.

Date and time Class|Name Venue|short Materials
01 December
17:15–18:45
Лекция 1, lecture ПОМИ No
01 December
19:00–20:30
Лекция 2, lecture ПОМИ No
02 December
11:15–12:45
Лекция 3, lecture ПОМИ No
02 December
13:00–14:30
Лекция 4, lecture ПОМИ No
08 December
17:15–18:45
Лекция 5, lecture ПОМИ No
08 December
19:00–20:30
Лекция 6, lecture ПОМИ No
09 December
11:15–12:45
Лекция 7, lecture ПОМИ No
09 December
13:00–14:30
Лекция 8, lecture ПОМИ No
09 December
15:30–17:00
Лекция 9, lecture ПОМИ files
14 December 2018

Дедлайн по экзамену "Избранные темы Computer Science"

Добрый день!

Дедлайн отправки решений задач из экзамена (смотрите новость ниже) - 15 января 23:59.

Катя Артамонова CS центр

09 December 2018

Экзамен "Избранные темы Computer Science"

Задачи для получения оценки за экзамен по курсу Избранные темы Computer Science доступны по ссылке https://goo.gl/zhPF2V или в приложении к последней 9 лекции.