Спецкурс "Математическая теория программирования" читается по четвергам в 16 ч. 20 м. (сбор у ауд. 14-08).
Первая лекция - 5 сентября.
В спецкурсе будут изложены основные математические вопросы теоретического и прикладного программирования, в частности - функционального и параллельного программирования. Особое внимание будет уделено проблемам формального доказательства свойств программ и построению cистем оптимизирующих преобразований программ.
Программа спецкурса:
1. Теория дискретных автоматов, автоматы в категориях, нечеткие автоматы, проблема минимизации.
2. Методы Флойда и Хоара доказательства частичной и тотальной корректности последовательных нерекурсивных программ.
3. Введение в функциональное программирование, языки Lisp, Hope, Miranda, Refal, ML, Haskell.
4. Введение в лямбда-исчисление, теорема Черча-Россера.
5. Энергичная и ленивая интерпретация функциональных программ.
6. Реализация функциональных программ на основе SECD-автомата.
7. Реализация функциональных программ на основе редукции графов.
8. Теория Манны неподвижной точки функциональных программ и методы верификации функциональных программ.
9. Алгебраические методы оптимизации функциональных программ.
10. Введение в модальную и динамическую логику. Полнота логики PDL.
11. Введение в анализ моделей (model checking).
12. Алгебраические модели параллельных программ.
13. Исчисление взаимодействующих систем Р.Милнера.
14. Бимоделирование и наблюдаемая конгруэнция. Методы формальной верификации параллельных программ.
Литература:
1. А.Филд, П.Харрисон: Функциональное программирование, Москва, Мир, 1993
2. N.Francez, Verification of programs, Addison-Wesley Publishers Ltd., 1992.
3. R.Milner, Communication and concurrency, Prentice-Hall, 1989.
4. Д.Ю.Жуков, Математические методы анализа программ, Часть 1, Переславль-Залесский, 2002.
Сразу после спецкурса в ауд. 14-13 в 18 ч. 05 м. будет работать семинар по теоретическому программированию.
Основные направления работы семинара:
1. теория автоматов
2. анализ и оптимизация последовательных программ
3. функциональное программирование
4. логическое программирование
5. модальная логика
6. параллельные и распределенные вычисления
7. объектно-оринетированное программирование
