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

Общая информация
ЛекторА. Х. Шень
Семестросень 2010
Дата начала09.12.2010
Количество пар6
Язык курсарусский
Видеоhttp://video.yandex.ru/users/uralcsclub/collection/4/
Анонсы
Встреча ВКонтактеhttp://vkontakte.ru/event21818796
Аннотация

Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества

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

Примерный перечень возможных тем:

  • понятие универсальной функции (хранимой программы) и диагональная конструкция алгоритмически неразрешимых проблем (перечислимого неразрешимого множества)
  • конкретные модели и доказательство неразрешимости конкретных задач (подстановки в словах = проблема тождества слов в полугруппах)
  • теорема Клини о неподвижной точке и self-referential конструкции
  • понятие сводимости как средство доказательства неразрешимости и полиномиальной сводимости как средства сравнения сложности
  • case study: потоки в сетях, сведение к ним (двудольного) паросочетания, вероятностный и детерминированный полиномиальные алгоритмы
  • правила доказательства свойств программ: примеры
  • вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
  • пример результата из теории сложности: что значит и почему BPP содержится в $ \Sigma_2 $
  • теория смыкается с практикой: регулярные выражения и конечные автоматы
  • алгебра и computer science: разделение секрета, коды Рида–Соломона
  • алгебра и computer science: IP=PSPACE
  • пример из теории кодирования: границы Гилберта и Шеннона
  • пример из теории информации: шенноновская энтропия как граница для средней длины префиксного (или даже однозначного) кода
  • колмогоровская сложность (пример результата: теорема о сложности пары)
  • PCP: эквивалентность проверки доказательства и gap reduction
  • доказательства с двумя пруверами: пример, когда квантовая механика позволяет перейти границу для классической
  • псевдослучайные генераторы: почему тестирование равносильно предсказанию

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

Ваша оценка: Пусто Средняя: 5 (4 голосов)
Share |
Курс Александра Шеня
Курс Александра Шеня
Открытие Computer Science клуба в Казани
Открытие Computer Science клуба в Казани
Курс Александра Шеня
Сверху вниз: Александр Мироненко, Олег Расин, Сергей Кумков
Открытие Computer Science клуба в Казани
Открытие Computer Science клуба в Казани
Слева направо: Павел Мартюгин, Михаил Берлинков, Константин Лихоманов, Владимир Гусев
Открытие Computer Science клуба в Казани
Открытие Computer Science клуба в Казани
Открытие Computer Science клуба в Казани
Курс Александра Шеня - слушатели