Версия 04:49, 11 апреля 2013

Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.

Лекторы

д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин

Место чтения курса в 2011 году - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.

Время: по четвергам, 11:45.

Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.

Ведется список посещений.

Тренировка

Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.

Темы

На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.

• Формально об алгоритмах. Вычислительные модели
• Временная и пространственная сложность алгоритмов
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
• Жадный алгоритм в задачах о покрытии
• Жадный алгоритм покрытия для почти всех исходных данных
• Полиномиальный в среднем алгоритм для SAT
• Вероятностная проверка тождеств
• MAX-SAT: вероятностное округление
• MAX-SAT: дерандомизация

• Дискретный логарифм
  • Почему дл обратим в среднем так же фигово, как в худшем.
• Начала криптографии (односторонние функции)
  • Протокол диффи-хелмана

Книга

Специальная верстка для чтения с ноутбуков и КПК:

• альбомная ориентация
• крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

Примечания и ссылки

• Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.