Прикладні логіки та елементи квантових обчислень

Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмне забезпечення систем

Викладач: доцент Шкільняк Оксана Степанівна (лекції)

Викладається: в 3-му семестрі магістратури.
Загальний обсяг: 90 год, з яких:
  • Лекції – 28 год.
  • Самостійна робота – 60 год.

Мета та завдання дисципліни

Мета та завдання дисципліни – поглиблене вивчення математичної логіки, головним чином некласичних логік, та основних понять і принципів квантових обчислень.

Предмет дисципліни

Предмет навчальної дисципліни Прикладні логіки та елементи квантових обчислень включає в себе розгляд теорій першого порядку та нетрадиційних логік – неокласичних, багатозначних, інтуїціоністських та модальних, їх семантичних моделей та формально-аксіоматичних систем, а також основних понять і принципів квантових обчислень.

В результаті вивчення навчальної дисципліни студент повинен
отримати:
  • поняття про прикладні некласичні логіки – неокласичні, багатозначні, інтуїціоністські та модальні, їх семантичні моделі та формально-аксіоматичні системи;
та має дістати уявлення:
  • про фізичні основи квантових обчислень, їх особливості, основні моделі, операції, сфери застосування і проблеми реалізації;
  • найвідоміші квантові алгоритми і відмінності в їх ефективності порівняно з класичними.

Вимоги до знань та вмінь

Для вивчення курсу Прикладні логіки та елементи квантових обчислень студент повинен прослухати наступні курси:
  • дискретна математика,
  • алгебра та геометрія,
  • загальна алгебра,
  • теорія алгоритмів та математична логіка

Програма курсу

Змістовий модуль 1: Аксіоматичні системи логік першого порядку та нетрадиційні логіки.

Тема 1: Теорії першого порядку, їх несуперечливість, повнота і розв'язність.
  • Аксіоматичні системи класичних логік 1-го порядку Гільбертівського типу (теорії 1-го порядку) та їх моделі.
  • Теорема істинності.
  • Приклади теорій 1-го порядку.
  • Формальна арифметика.
  • Теорема тавтології.
  • Теореми дедукції, редукції.
  • Синтаксичні теореми еквівалентності, рівності.
  • Несуперечливість та максимальність (повнота) теорій 1-го порядку.
  • Теорема Лінденбаума.
  • Перелічність, розв'язність теорій 1-го порядку.
  • Теорема про розв'язність.
Тема 2: Теорема Гьоделя про повноту. Теорема компактності. Категоричність. Теореми Гьоделя про неповноту.
  • Поняття теорії Генкіна.
  • Теорема Гьоделя про повноту.
  • Теорема Льовенгейма-Скулема про спуск.
  • Теорема компактності.
  • Теорема Льовенгейма-Скулема про підйом.
  • Категоричність теорій 1-го порядку.
  • Категоричність і повнота теорій 1-го порядку.
  • Теорема Лося-Воота.
  • Теореми Гьоделя про неповноту, їх значення.
Тема 3: Логіки вищих порядків. Багатозначні логіки.
  • Логіки вищих порядків.
  • Теза Гільберта.
  • Нетрадиційні логіки.
  • Багатозначні логіки.
  • Багатозначні логіки Поста.
  • 3-значні логіки Лукасєвича та Кліні, їх властивості.
  • 4-значна логіка Белнапа, її властивості.
Тема 4: Інтуїціоністська логіка.
  • Інтуїціоністська логіка.
  • Семантика можливих світів (реляційна семантика) інтуїціоністської логіки.
  • Інтуїціоністські числення Гільбертівського та Генценівського типу.
Тема 5: Алетичні модальні логіки.
  • Модальні логіки.
  • Системи T, B, S4, S5.
  • Реляційна семантика алетичної модальної логіки.
Тема 6: Темпоральні логіки.
  • Темпоральні логіки, синтаксис мови та реляційна семантика.
  • Застосування темпоральних логік.
Тема 7: Епістемічні логіки.
  • Епістемічні логіки, логіка знання.
  • Синтаксис мови, реляційна семантика та застосування.
Тема 8: Деонтичні логіки.
  • Деонтична логіка – логіка норм.
  • Синтаксис мови, реляційна семантика, різновиди.
  • Питання адекватності формалізації деонтичної логіки.
Тема 9: Аксіоматичні системи неокласичних логік першого порядку.
  • Чисті неокласичні числення, їх властивості, коректність і повнота.
Тема 10: Композиційно-номінативні модальні логіки.
  • Композиційно-номінативні модальні системи.
  • Композиційно-номінативні модальні логіки.
  • Транзиційні та темпоральні КНМЛ.
  • Аксіоматичні системи КНМЛ.
Модульна контрольна робота 1

Змістовий модуль 2: Елементи квантових обчислень.

Тема 11: Вступ до квантових обчислень. Основи теорії інформації і квантової механіки.
  • Історія квантових обчислень.
  • Основні постулати квантової механіки.
  • Кубіт як елементарна одиниця квантової інформації, його представлення і суперпозиція станів.
  • Квантові регістри і квантова заплутаність.
  • Квантовий паралелізм.
Тема 12: Схема квантового обчислення. Операції над кубітами.
  • Моделі квантових обчислень.
  • Логічні та квантові вентилі (гейти).
  • Оборотні обчислення.
  • Одно- та багатокубітові вентилі.
  • Універсальні квантові вентилі.
Тема 13: Квантові алгоритми та їх складність.
  • Співпадіння класів задач, що можуть бути розв'язаними на квантовому і класичному комп'ютері.
  • Основні класи квантової складності.
  • Опис квантових алгоритмів.
  • Підходи до класифікації квантових алгоритмів.
  • Алгоритми Дойча-Джози, Гровера, Шора.
Тема 14: Квантова криптографія. Фізична реалізація квантового комп'ютера.
  • Застосування квантових обчислень в криптографії.
  • Протоколи квантового розподілу ключа.
  • Проблеми фізичної реалізації квантового комп'ютера.
Модульна контрольна робота 2

Рекомендована література

Основна:

  1. Клини С. Математическая логика. – М.: Наука, 1973.
  2. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів. – ВПЦ Київський університет. – К., 2003.
  3. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976.
  4. Непейвода Н.Н. Прикладная логика. – Новосибирск: НГУ, 2000.
  5. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008.
  6. Шкільняк С.С. Математична логіка: приклади і задачі. – ВПЦ Київський університет. – К., 2007.
  7. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М.: Мир. – 2006.
  8. Вакарчук І.О. Квантова механіка. – 4-е видання, доповнене. — Л.: ЛНУ ім. Івана Франка, 2012.
  9. Прескилл Дж. Квантовая информация и квантовые вычисления. В 2-х томах. – Ижевск: РХД, 2011.

Додаткова:

  1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін. Основи дискретної математики. – К., 2002.
  2. Клини С. Введение в метаматематику. – М.: ИЛ, 1957.
  3. Смирнов В.А. Семантика модальных и интенсиональных логик. – M.: Прогресс, 1981. – 494 с.
  4. Справочная книга по математической логике / Под ред. Дж. Барвайса: В 4 т. – М., 1982-1983.
  5. Такеути Г. Теория доказательств. – М.: Мир, 1978.
  6. Фейс Р. Модальная логика. – M.: Мир, 1974.
  7. Шенфилд Дж. Математическая логика. – М.: Наука, 1975.
  8. Belnap N., Steel T. The logic of questions and answers. – New Haven and London: Yale Univ. Press, 1976.
  9. Ішмуратов А.Т. Вступ до філософської логіки. – К., 1997.
  10. Смирнова Е.А. Логика и философия. – М.: РОССПЕН, 1996.
  11. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М., 1983.
  12. Квантовые вычисления: за и против / Под ред. В.А. Садовничего: Квантовый компьютер и квантовые вычисления. – Ижевск : РХД, 1999. – Т. 1.
  13. Квантовый компьютер и квантовые вычисления / Под ред. В.А. Садовничего. – Ижевск : РХД, 1999. – Т. 2.
  14. Watrous J. Quantum Computational Complexity. In Encyclopedia of Complexity and Systems Science, Springer, 2009.