# 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
1. Clicking ▼&► to (un)fold the tree menu may facilitate locating what you want to find. 2. Videos embedded here do not necessarily represent my viewpoints or preferences. 3. This is just one of my several websites. Please click the category-tags below these two lines to go to each independent website.
No comments:
Post a Comment