# playlist (click the video's upper-left icon)
source: Лекториум 2013年7月24日
Подписывайтесь на канал: https://www.lektorium.tv/ZJA
Следите за новостями:
https://vk.com/openlektorium
https://www.facebook.com/openlektorium
Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества
формулировку и доказательство можно понять за ограниченное время, у нас имеющееся
результат достаточно фундаментальный для того, чтобы практическим программистам стоило про него знать
результат не общеизвестный (последнее можно будет скорректировать по ходу дела)
Примерный перечень возможных тем:
понятие универсальной функции (хранимой программы) и диагональная конструкция алгоритмически неразрешимых проблем (перечислимого неразрешимого множества)
конкретные модели и доказательство неразрешимости конкретных задач (подстановки в словах = проблема тождества слов в полугруппах)
теорема Клини о неподвижной точке и self-referential конструкции
понятие сводимости как средство доказательства неразрешимости и полиномиальной сводимости как средства сравнения сложности
case study: потоки в сетях, сведение к ним (двудольного) паросочетания, вероятностный и детерминированный полиномиальные алгоритмы
правила доказательства свойств программ: примеры
вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
пример результата из теории сложности: что значит и почему BPP содержится в
теория смыкается с практикой: регулярные выражения и конечные автоматы
алгебра и computer science: разделение секрета, коды Рида–Соломона
алгебра и computer science: IP=PSPACE
пример из теории кодирования: границы Гилберта и Шеннона
пример из теории информации: шенноновская энтропия как граница для средней длины префиксного (или даже однозначного) кода
колмогоровская сложность (пример результата: теорема о сложности пары)
PCP: эквивалентность проверки доказательства и gap reduction
доказательства с двумя пруверами: пример, когда квантовая механика позволяет перейти границу для классической
псевдослучайные генераторы: почему тестирование равносильно предсказанию
Страница курса на сайте Computer Science клуба.logic.pdmi.ras.ru/csclub/courses/hugedataalgorithms
No comments:
Post a Comment