1626435673-e8f375334f11338eff1a03e146128817 (Программа курса Бульонков)

ПРОГРАММАпо курсу «Теория программирования» на 2013-2014 ггсоставлена доцентом, к.ф.-м.н. Бульонковым М.А.ЛЕКЦИИ1. Понятие машины Тьюринга. Запись программ на МТ. Функционирования МТ:конфигурация, протокол. Вычисляемая функция. Временная сложность. Ёмкостная сложность.Вариации МТ. Понятие РАМ-машины. Вычисление на РАМ: состояние памяти,конфигурация, операнды, команды. Функция, вычисляемая РАМ. Временная и ёмкостнаясложность, равномерный и логарифмический весовой критерии.

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

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

Понятие регулярного выражения. Теорема орегулярности конечно-автоматных языков. Лемма о разрастании, примеры использования.6. Проблемы пустоты и эквивалентности конечных автоматов. Переборный иалгебраический способы доказательства эквивалентности, оценка сложности. Понятиеминимального автомата и его построение методом грубейшего разбиения. Оценка сложности.Доказательство эквивалентности методом сведения к задаче «Объединить-найти».7. Поиск в информационном массиве. Линейный поиск, оценка сложности в худшем исреднем. Бинарный поиск и двоичные деревья поиска. Сбалансированные деревья.

2-3деревья: оценка сложности, процедуры вставки и удаления. B-деревья, как обобщение 2-3деревьев: оценка сложности. АВЛ-деревья: оценка сложности, процедуры вставки в АВЛдерево. Метод расстановки: оценка сложности в худшем и среднем.8. Задача сортировки. Классификация методов сортировки: по области применения, поиспользуемым методам.

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

Оценка сложности в среднем для сортировки, основанной насравнениях. Быстрая сортировка: оценка временной сложности в среднем.9. Метод разметки. Понятие ориентированного мультиграфа, примеры. Понятиеполурешётки свойств, свойства ограниченности и обрыва цепей. Понятие монотонных идистрибутивных преобразователей свойств. Формулировка задачи глобального анализа.Понятие точного решение ЗГА, Понятие недетерминированного процесса разметки. Понятиестационарной разметки, доказательство её существования. Понятие безопасной разметки.Теоремы о безопасности и единственности стационарной разметки.10.

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

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

Понятие инвариантного соотношения. Функциональные сети, как средствопредставления инвариантных соотношений. Множество утверждений функциональной сети,приведённые сети. Операция пересечения функциональных сетей. Функциональные сети какполурешётка свойств. Преобразователи функциональных сетей, их дистрибутивность.Решение задачи нахождения инвариантных соотношений методом ЗГА.14. Понятие фрагмента стандартной схемы. Фрагмент, как обобщение стандартной схемы.Эквивалентность фрагментов, вхождения фрагментов.

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

Понятиегенерирующего расширения, как объектного кода для семантики, заданной СВ,Трансформационный подход.17. Проблема задержанного управления при СВ, Поливариантные СВ, Примеринтерпретатора конечных автоматов. Методы улучшения специализируемости программ.Построение транслятора конечных автоматов.18. Понятие анализа периода связывания (BTA). Сведение задачи BTA к ЗГА, РешениеBTA методом нахождения неподвижной точки. Решение BTA методом решения системынеравенств. Понятие поливариантного анализа периода связывания: преобразованиепрограммы в процессе анализа.ЛИТЕРАТУРА1.

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.:Издательский дом “Вильямс”, 2000.2. Бульонков М.А. Смешанные вычисления. Учебное пособие. – Новосибирск: Изд-воНГУ, 1995.3. Карпов Ю. Теория автоматов. Учебник для вузов. – СПб.: Издательский дом Питер,2002.4. Котов В.Е., Сабельфельд В.К. Теория схем программ. – М.: Наука, 1991.5. Лавров С. Программирование. Математические основы, средства, теория.

– СПб.: БХВПетербург, 2001.6. Мотвани Р., Хопкрофт Дж., Ульман Дж. Введение в теорию автоматов, языков ивычислений, 2-е издание, – М.: Издательский дом “Вильямс”, 2002.7. Сабельфельд В.К. Теория программирования. Учебное пособие. – Новосибирск: Изд-воНГУ, 1993.8. Ахо А., Сети Р., Ульман Дж.Д. Компиляторы: принципы, технологии и инструменты. –М.: Издательский дом “Вильямс”, 2001.9.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.10. Биркгоф Г. Теория решеток. – М.: Наука, 1984.11. Ершов А.П. Введение в теоретическое программирование (беседы о методе). – М.:Наука, 1977.12. Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложностивычислений. Учебное пособие. – Новосибирск: Изд-во НГУ, 1995.13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО,1999.14.

Котов В.Е. Введение в теорию схем программ. – М.: Наука, 1978.15. Трахтенброт Б.А. Сложность алгоритмов и вычислений. – Новосибирск: Изд-во НГУ,1967..