Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (→Книга) |
||
Строка 60: | Строка 60: | ||
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе. | Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе. | ||
− | [[File:book-advanced-algorithms.pdf| | + | [[File:book-advanced-algorithms.pdf|512px|page=1-3]] |
== Примечания и ссылки == | == Примечания и ссылки == |
Версия 07:27, 18 апреля 2013
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
- Лекторы
- д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин
Место чтения курса в 2011 году - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.
Время: по четвергам, 11:45.
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.
Ведется список посещений.
Содержание
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.
Темы
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Полиномиальный в среднем алгоритм для SAT
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- Дискретный логарифм
- Почему ДЛ обратим в среднем так же плохо, как в худшем.
- Начала криптографии (односторонние функции)
- Протокол диффи-хелмана
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
Примечания и ссылки
- Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.