ПРОГРАММА

по курсу «Теория программирования» на 2013-2014 гг

составлена доцентом, к.ф.-м.н. Бульонковым М.А.

ЛЕКЦИИ

1. Понятие машины Тьюринга. Запись программ на МТ. Функционирования МТ:

конфигурация, протокол. Вычисляемая функция. Временная сложность. Ёмкостная сложность.

Вариации МТ. Понятие РАМ-машины. Вычисление на РАМ: состояние памяти,

конфигурация, операнды, команды. Функция, вычисляемая РАМ. Временная и ёмкостная сложность, равномерный и логарифмический весовой критерии. Понятие сложности в среднем.

2. Понятие порядка сложности, полиномиальная связанность, экспоненциальная функция.

Понятие моделирования, пошаговое моделирование. Моделирование РАМ на МТ, оценка сложности. Невозможность моделирование РАМ на МТ при равномерном весовом критерии.

Моделирование РАМ на МТ при логарифмическом весовом критерии, оценка сложности.

3. Теорема об ускорении. Понятие сигнализирующего оператора. Временная и ёмкостная сложность МТ как сигнализирующие. Теорема Цейтина, диагональный метод. Теорема Рабина.

4. Нижние оценки. Задачи, допускающие матричные формулировки. Неветвящиеся программы, как модель вычислений. Теоремы о нижней оценке для задачи умножения матрицы на вектор по строкам и по столбцам. Примеры использования.

5. Понятие конечного автомата. Графовое представление. Язык конечного автомата.

Понятие регулярного выражения и его языка. Понятие регулярного выражения. Теорема о регулярности конечно-автоматных языков. Лемма о разрастании, примеры использования.

6. Проблемы пустоты и эквивалентности конечных автоматов. Переборный и алгебраический способы доказательства эквивалентности, оценка сложности. Понятие минимального автомата и его построение методом грубейшего разбиения. Оценка сложности.

Доказательство эквивалентности методом сведения к задаче «Объединить-найти».

7. Поиск в информационном массиве. Линейный поиск, оценка сложности в худшем и среднем. Бинарный поиск и двоичные деревья поиска. Сбалансированные деревья. 2- деревья: оценка сложности, процедуры вставки и удаления. B-деревья, как обобщение 2- деревьев: оценка сложности. АВЛ-деревья: оценка сложности, процедуры вставки в АВЛ дерево. Метод расстановки: оценка сложности в худшем и среднем.

8. Задача сортировки. Классификация методов сортировки: по области применения, по используемым методам. Критерии оценки сложности. Примеры сортировки вставкой, выбором и обменом. Понятие дерева решений. Оценка сложности в худшем случае для сортировки, основанной на сравнениях. Сортировка слиянием: оценка временной и ёмкостной сложности в худшем случае. Оценка сложности в среднем для сортировки, основанной на сравнениях. Быстрая сортировка: оценка временной сложности в среднем.

9. Метод разметки. Понятие ориентированного мультиграфа, примеры. Понятие полурешётки свойств, свойства ограниченности и обрыва цепей. Понятие монотонных и дистрибутивных преобразователей свойств. Формулировка задачи глобального анализа.

Понятие точного решение ЗГА, Понятие недетерминированного процесса разметки. Понятие стационарной разметки, доказательство её существования. Понятие безопасной разметки.

Теоремы о безопасности и единственности стационарной разметки.

10. Теорема о точности стационарной разметки в дистрибутивном случае. Пример формулировки ЗГА для анализа циклов в графе. Методы минимизации количества применений правила разметки. Теорема о невозможности построения точного решения в монотонном случае.

11. Понятие стандартной схемы: базис, термы, операторы. Понятие аргументов и результатов, правильность стандартной схемы. Понятие интерпретации: значение терма, протокол, результат. Свободные интерпретации как пример интерпретации. Понятие функциональной эквивалентности стандартных схем. Понятие логико-термальной эквивалентности: логико-термальная история, детерминант. Теорема о корректности лтэквивалентности.

12. Понятие информационных связей и информационного графа. Нахождение информационного графа путём сведения к ЗГА. Компоненты связности информационного графа, их зацеплённость. Переименование переменных, минимизация количества переменных в стандартной схеме путём сведения к задаче раскраски графов.

13. Понятие инвариантного соотношения. Функциональные сети, как средство представления инвариантных соотношений. Множество утверждений функциональной сети, приведённые сети. Операция пересечения функциональных сетей. Функциональные сети как полурешётка свойств. Преобразователи функциональных сетей, их дистрибутивность.

Решение задачи нахождения инвариантных соотношений методом ЗГА.

14. Понятие фрагмента стандартной схемы. Фрагмент, как обобщение стандартной схемы.

Эквивалентность фрагментов, вхождения фрагментов. Понятие система преобразований.

Система лт. Теорема о корректности. Теорема о полноте: согласование стандартных схем, Лграфы, Оценка сложности.

15. Понятие смешанного вычисления программ: программы как данные, доступные и задержанные вычисления, основное уравнение СВ. Связь смешанных вычислений с S-m-n теоремой Клини. Условия выгодности СВ, Связь СВ и трансляции программ: понятие транслятора и интерпретатора. Проекции Футамуры. Понятие метаинтерпретатора и автоинтерпретатора, критерий оптимальности Джонса. Другие потенциальные применения СВ.

16. Пример функции xn. Интерпретационный подход к реализации СВ. Понятие генерирующего расширения, как объектного кода для семантики, заданной СВ, Трансформационный подход.

17. Проблема задержанного управления при СВ, Поливариантные СВ, Пример интерпретатора конечных автоматов. Методы улучшения специализируемости программ.

Построение транслятора конечных автоматов.

18. Понятие анализа периода связывания (BTA). Сведение задачи BTA к ЗГА, Решение BTA методом нахождения неподвижной точки. Решение BTA методом решения системы неравенств. Понятие поливариантного анализа периода связывания: преобразование программы в процессе анализа.

ЛИТЕРАТУРА

Издательский дом “Вильямс”, 2000.

2. Бульонков М.А. Смешанные вычисления. Учебное пособие. – Новосибирск: Изд-во НГУ, 1995.

3. Карпов Ю. Теория автоматов. Учебник для вузов. – СПб.: Издательский дом Питер, 2002.

4. Котов В.Е., Сабельфельд В.К. Теория схем программ. – М.: Наука, 1991.

5. Лавров С. Программирование. Математические основы, средства, теория. – СПб.: БХВПетербург, 2001.

6. Мотвани Р., Хопкрофт Дж., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е издание, – М.: Издательский дом “Вильямс”, 2002.

7. Сабельфельд В.К. Теория программирования. Учебное пособие. – Новосибирск: Изд-во НГУ, 1993.

8. Ахо А., Сети Р., Ульман Дж.Д. Компиляторы: принципы, технологии и инструменты. – М.: Издательский дом “Вильямс”, 2001.

9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.

10. Биркгоф Г. Теория решеток. – М.: Наука, 1984.

11. Ершов А.П. Введение в теоретическое программирование (беседы о методе). – М.:

12. Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. Учебное пособие. – Новосибирск: Изд-во НГУ, 1995.

13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 14. Котов В.Е. Введение в теорию схем программ. – М.: Наука, 1978.

15. Трахтенброт Б.А. Сложность алгоритмов и вычислений. – Новосибирск: Изд-во НГУ,