Вероятностные и квантовые алгоритмы — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Программа курса)
м
 
(не показаны 23 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
[[Категория:Лекционные курсы кафедры МК]]
+
[[Категория:Лекционные курсы кафедры МК (архив)]]
  
 
Лектор - профессор [[Алексеев Валерий Борисович]].
 
Лектор - профессор [[Алексеев Валерий Борисович]].
  
−
Курс читается для группы 618/1 в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.
+
Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.
−
 
+
−
[[Категория:Лекционные_курсы_кафедры_МК]]
+
  
 
==Объявления==
 
==Объявления==
  
−
[[Media:ВКА_2017.docx|Вопросы к экзамену на январь 2018 года]]
+
[[Media:Вопросы_ВКА_2023.pdf|Вопросы к экзамену в январе 2024 года]]
  
 
==Программа курса==
 
==Программа курса==
Строка 19: Строка 17:
 
*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.
 
*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.
  
−
*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.
+
*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.  
  
−
*Лекция 5. Вероятностные методы в перечислительных задачах. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.
+
*Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.
  
−
*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.
+
*Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.  
  
−
*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.
+
*Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.
  
−
*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.  
+
*Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.
  
−
*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.  
+
*Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.
  
−
*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.
+
*Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.  
  
−
*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.
+
*Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.  
  
−
*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.
+
*Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.
  
−
*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.
+
*Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.
  
−
*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств). Тензорное произведение линейных операторов, теорема о его дистрибутивности при действии на разложимый вектор.  
+
*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).  
  
−
*Лекция 15. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.  
+
*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.  
  
−
*Лекция 16. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.  
+
*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.  
  
−
*Лекция 17. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность.
+
*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.
 +
 
 +
*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.
  
 
'''Литература'''
 
'''Литература'''
  
−
# Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений  (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.  
+
1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений  (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288.  
 
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf
 
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf
 +
 
или
 
или
−
# Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.
 
  
−
# А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.
+
2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.
−
 
+
−
==Программа семинарских занятий==
+
−
 
+
−
*Занятие 1. Подсчет числа комбинаторных объектов. Правила суммы и произведения.
+
−
 
+
−
[1] Гл. VIII  1.1(1, 2), 1.2(1-2), 1.4(1-3), 1.6, 1.8(1-3), 1.9(1, 2), 1.10(1, 2), 1.11(1-3).
+
−
 
+
−
На дом:  [1] Гл. VIII  1.1(3), 1.5(1-2), 1.7, 1.8(4-7), 1.9(3), 1.10(3), 1.12(1-3).
+
−
 
+
−
*Занятие 2. Свойства биномиальных коэффициентов и их сумм.
+
−
 
+
−
[1] Гл. VIII  1.13(1-4), 1.14(1, 3, 5, 7), 1.18(1, 3, 5, 7, 9, 12), 1.21(1, 3), 1.22(1, 3), 1.25(1, 2).
+
−
 
+
−
На дом:  [1] Гл. VIII  1.13(5-8), 1.14(2, 4, 6), 1.18(2, 4, 6, 8, 10), 1.21(2, 4), 1.22(2, 4), 1.25(3, 4).
+
−
 
+
−
*Занятие 3. Принцип включений-исключений.
+
−
 
+
−
[1] Гл. VIII  2.1(2-3), 2.4(1-2), 2.5(1, 3), 2.6(1, 3, 5), 2.2, 2.7(1, 3), 2.8.
+
−
 
+
−
На дом:  [1] Гл. VIII  2.5(2), 2.6(2, 4, 6), 2.7(2, 4), 2.9.
+
−
 
+
−
*Занятие 4. Рекуррентные уравнения.
+
−
 
+
−
[1] Гл. VIII 3.2(1, 3, 5), 3.3(1, 3, 5), 3.5(1-3), 3.6(2), 3.7(5).
+
−
+
−
На дом:  [1] Гл. VIII 3.2(2, 4, 6), 3.3(2, 4), 3.5(4-5), 3.6(3). 
+
−
 
+
−
*Занятие 5. Понятие схемы в некотором базисе. Метод синтеза по ДНФ.
+
−
 
+
−
[1] Гл. X  1.4(р. 10.2 а)-в)), 1.1(1-2, 5), 1.18(1-3), 1.2(1-2), 1.5(1-2), 1.7(1-2, 5), 1.8.
+
−
 
+
−
На дом:  [1] Гл. X  1.1(3-4, 6-7), 1.18(4-6), 1.2(3-4), 1.5(3-4), 1.7(3-4, 6).
+
−
 
+
−
*Занятие 6. Синтез некоторых систем функций алгебры логики.
+
−
 
+
−
[1] Гл. X  1.9(1-2), 1.10, 1.11(1-2), 1.12(1, 3), 1.13(1), 1.10, 2.8 (1-3, СФЭ с уменьшением сложности).
+
−
 
+
−
На дом:  [1] Гл. X  1.9(3), 1.11(3), 1.12(2), 1.13(2), 1.17, 2.8 (4-6, СФЭ с уменьшением сложности).
+
−
 
+
−
*Занятие 7. Контрольная работа по темам "Комбинаторика" и "СФЭ" (2 ч).
+
−
 
+
−
*Занятие 8. Конечные автоматы без выхода (КА) и автоматные множества. Диаграмма переходов.
+
−
 
+
−
[2] 1(1-3, 7), 2(1, 3), 9.
+
−
 
+
−
На дом: [2] 1(4-6, 8), 2(2, 4), 10.
+
−
 
+
−
*Занятие 9. Недетерминированные конечные автоматы без выхода (НКА). Детерминизация НКА.
+
−
 
+
−
[2] 3(1, 3), 4(1, 3), 7(1), 8(1).
+
−
 
+
−
На дом: [2] 3(2, 4), 4(2, 4), 7(2), 8(2).
+
−
 
+
−
*Занятие 10. Регулярные выражения и регулярные множества. Упрощения КА.
+
−
 
+
−
[2] 5(1, 2), 6(1, 3, 5, 7).
+
−
 
+
−
На дом: [2] 5(3, 4), 6(2, 4, 6, 8).
+
−
 
+
−
*Занятие 11. Конечные автоматы с выходом (КАВ). Диаграмма Мура и канонические уравнения.
+
−
 
+
−
[1] Гл. IV 1.1(1-4), 1.2(1-2), 2.1(1, 3, 15, 24, 27).
+
−
 
+
−
На дом:  [1] Гл. IV 1.1(8-12), 1.2(3-4), 2.1(4, 8, 16, 25, 28).
+
−
 
+
−
*Занятие 12. Реализация КАВ СФЭз. Упрощения КАВ.
+
−
 
+
−
[1] Гл. IV 2.13(1, 4, 7), 2.14(1, 3), 2.4(1-3).
+
−
+
−
На дом: [1] Гл. IV 2.13(2, 3, 10), 2.14(2, 4), 2.4(4-6). 
+
−
 
+
−
*Занятие 13. Контрольная работа по темам «КА» и «КАВ» (2 ч).
+
−
 
+
−
'''Литература'''
+
  
−
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
+
3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.
−
# [[Media:finaut.pdf|Задачи для семинарских занятий по теме "Конечные автоматы без выхода"]]
+
−
# [[Media:odm-selezn.pdf|Селезнева С.Н. Основы дискретной математики]]. М.: МАКС Пресс, 2010.
+

Текущая версия на 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.

Источник — «https://mk.cs.msu.ru/index.php?title=Вероятностные_и_квантовые_алгоритмы&oldid=11398»