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

Избранные темы Computer Science
Санкт-Петербург / осень 2018, посмотреть все семестры

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

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

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

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

Игра Конвея.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Zero-knowledge proofs.

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

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

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

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

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

Дата и время Название Место Материалы
01 декабря
17:15–18:45
Лекция 1, лекция ПОМИ Нет
01 декабря
19:00–20:30
Лекция 2, лекция ПОМИ Нет
02 декабря
11:15–12:45
Лекция 3, лекция ПОМИ Нет
02 декабря
13:00–14:30
Лекция 4, лекция ПОМИ Нет
08 декабря
17:15–18:45
Лекция 5, лекция ПОМИ Нет
08 декабря
19:00–20:30
Лекция 6, лекция ПОМИ Нет
09 декабря
11:15–12:45
Лекция 7, лекция ПОМИ Нет
09 декабря
13:00–14:30
Лекция 8, лекция ПОМИ Нет
09 декабря
15:30–17:00
Лекция 9, лекция ПОМИ файлы
14 декабря 2018

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

Добрый день!

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

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

09 декабря 2018

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

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