Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — различия между версиями
StasFomin (обсуждение | вклад) (→Темы) |
StasFomin (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Ведется [https://spreadsheets.google.com/pub?hl=en&hl=en&key=0Ao6tsK_6FZEldG5EUUotWTRSbXRVRXUzY0JxTDA1dVE&single=true&gid=7&output=html список посещений]. | Ведется [https://spreadsheets.google.com/pub?hl=en&hl=en&key=0Ao6tsK_6FZEldG5EUUotWTRSbXRVRXUzY0JxTDA1dVE&single=true&gid=7&output=html список посещений]. | ||
| + | |||
| + | |||
| + | <html><center> | ||
| + | </p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://spreadsheets.google.com/pub?hl=en&hl=en&key=0Ao6tsK_6FZEldG5EUUotWTRSbXRVRXUzY0JxTDA1dVE&single=true&gid=7&output=html" id="1695919049" frameborder="0" height="800" width="100%"></iframe></div></div></div> | ||
| + | </center></html> | ||
| + | |||
Версия 04:39, 11 апреля 2013
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
- Лекторы
- д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин
Место чтения курса в 2011 году - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.
Время: по четвергам, 11:45.
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.
Ведется список посещений.
Содержание
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.
Темы
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Полиномиальный в среднем алгоритм для SAT
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- Дискретный логарифм
- Почему дл обратим в среднем так же фигово, как в худшем.
- Начала криптографии (односторонние функции)
- Протокол диффи-хелмана
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
Примечания и ссылки
- Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.