Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
- Лекторы
- д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин
Место чтения курса в 2011 году - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.
Время: по четвергам, 11:45.
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.
Ведется список посещений.
Содержание
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.
Задачи
Все статьи в этой категории — задачи, которые можно пытаться решать.
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:
- Category:Решенные задачи — кстати, полезно смотреть чужие решения.
Cтатьи-решения задач помечать вставляя строку
[[Category:На проверку]]
и подписываться на изменения («watch this page»).
Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.
Т.е. очередь решений на проверку → Category:На проверку, проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
Эти задачи заводим в Category:Предложенные студентами задачи
Темы
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Полиномиальный в среднем алгоритм для SAT
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- Дискретный логарифм
- Почему ДЛ обратим в среднем так же плохо, как в худшем.
- Начала криптографии (односторонние функции)
- Протокол диффи-хелмана
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
Примечания и ссылки
- Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.
[ Хронологический вид ]Комментарии
Здесь можно писать вопросы к курсу
Войдите, чтобы комментировать.