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