Вероятностные и квантовые алгоритмы — различия между версиями
(→Объявления) |
PodymovVV (обсуждение | вклад) м |
||
(не показаны 3 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | [[Категория:Лекционные курсы кафедры МК]] | + | [[Категория:Лекционные курсы кафедры МК (архив)]] |
Лектор - профессор [[Алексеев Валерий Борисович]]. | Лектор - профессор [[Алексеев Валерий Борисович]]. | ||
Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен. | Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен. | ||
− | |||
− | |||
==Объявления== | ==Объявления== | ||
− | [[Media: | + | [[Media:Вопросы_ВКА_2023.pdf|Вопросы к экзамену в январе 2024 года]] |
==Программа курса== | ==Программа курса== |
Текущая версия на 23:09, 7 октября 2024
Лектор - профессор Алексеев Валерий Борисович.
Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.
Объявления
Вопросы к экзамену в январе 2024 года
Программа курса
- Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».
- Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».
- Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.
- Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.
- Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.
- Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.
- Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.
- Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.
- Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.
- Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.
- Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.
- Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.
- Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.
- Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).
- Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.
- Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.
- Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.
- Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.
Литература
1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288. discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf
или
2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.
3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.