1626435674-2aa2204d71b92fca39a62b0a540076af (Аннотация курса)

Теория программированияБульонков Михаил Алексеевич, Филаткина Наталья НиколаевнаEt.nsu.ru, дата размещения 7.11.2014АннотацияДисциплина «Теория программирования» является частью математического цикла ООПпо направлению подготовки «010200 – Математика и компьютерные науки» и «010400 –Прикладная математика и информатика». Дисциплина реализуется на Механикоматематическом факультете Новосибирского государственного университета кафедройПрограммирования ММФ НГУ.Содержание дисциплины охватывает круг вопросов, связанных с анализом сложностиалгоритмов для разных видов вычислительных моделей, анализом свойств моделейпрограмм, а также с проблематикой смешанных вычислений.Преподавание дисциплины предусматривает следующие формы организации учебногопроцесса: лекции, практические занятия, контрольная работа, реферат, самостоятельнаяработа студента.Курс изучается в первом семестре, итоговая аттестация - экзамен.1.

Цели и задачи учебной дисциплиныЦелью курса является освоение студентами базовых понятий теоретическогопрограммирования, которые, в свою очередь, необходимы для понимания современныхметодологий и технологий разработки программного обеспечения. Первая часть курса, вотличие от курса «Теория алгоритмов», где рассматриваются вопросы существованияалгоритмов, посвящена элементам теории сложности, как средства для оценкисущественных характеристик модельных вычислительных систем. Знакомство сразличными моделями вычислений, их сравнительный анализ на основе моделированиядаёт студентам представление о программной реализации вычислительной модели и ихсложности.

Методы оценка сложности демонстрируются на широко используемыхалгоритмах поиска и сортировки, а также задаче умножения матрицы на вектор. Даетсявведение в машинно-независимую теорию сложности, которая позволяет оценить границыприменимости понятий, связанных со сложностью алгоритмов.Вторая часть курса также посвящена методам анализа программных моделей.Использование достаточно высокого уровня абстракции предоставляет единый механизмдля определения разнообразных свойств программ и, в общем случае, динамическихсистем переходов, что позволяет распространить эти методы анализа на широкий классзадач.

Студент получает представление о таких фундаментальных свойствах программыкак поток управления, информационные зависимости, инварианты и т.п. Полезность этихпонятий содержательно проявляется при определении систем преобразования программ,которая в свою очередь используются конструктивном доказательстве разрешимостилогико-термальной эквивалентности.Заключительная часть курса посвящена смешанным вычислениям программ, которые, содной стороны, являются инструментом повышения эффективности программ и хорошимпримером использования описанных ранее в курсе методов, с другой, – связующимзвеном между основными подходами к реализации языков программирования:интерпретацией и трансляцией, а с третьей – связь с фундаментальными фактами,рассматривающимися в теории вычислимости.1.1 Понятие машины Тьюринга. Запись 3программ на МТ.Функционирования МТ:конфигурация, протокол.Вычисляемая функция.

Временнаясложность. Ёмкостная сложность.Вариации МТ. Понятие РАМмашины. Вычисление на РАМ:состояние памяти, конфигурация,операнды, команды. Функция,вычисляемая РАМ. Временная иёмкостная сложность, равномерныйи логарифмический весовойкритерии. Понятие сложности всреднем.1.2 Понятие порядка сложности,3полиномиальная связанность,экспоненциальная функция.Понятие моделирования, пошаговоемоделирование. МоделированиеРАМ на МТ, оценка сложности.Невозможность моделированиеРАМ на МТ при равномерномвесовом критерии.

МоделированиеРАМ на МТ при логарифмическомвесовом критерии, оценкасложности.Виды учебнойработы, включаясамостоятельную Формы текущегоконтроляработу студентов иуспеваемоститрудоемкость (в(по неделямчасах)семестра)ЛекцияПрактич.занятияСамост.работаКонтр.работаЭкзаменРаздел дисциплиныНеделя семестра№п/пСеместр2. Содержание учебной дисциплиныОбщая трудоемкость дисциплины составляет 4 зачетных единиц, 144 часа.12222222Формапромежуточнойаттестации(по семестрам)1.3 Теорема об ускорении.

Понятиесигнализирующего оператора.Временная и ёмкостная сложностьМТ как сигнализирующие.Машинно-независимая теориясложности. Теорема Цейтина,диагональный метод. ТеоремаРабина.1.4 Нижние оценки. Задачи,допускающие матричныеформулировки. Неветвящиесяпрограммы, как модель вычислений.Теоремы о нижней оценке длязадачи умножения матрицы навектор по строкам и по столбцам.Примеры использования.1.5 Понятие конечного автомата.Графовое представление. Языкконечного автомата. Понятиерегулярного выражения и его языка.Понятие регулярного выражения.Теорема о регулярности конечноавтоматных языков. Лемма оразрастании, примерыиспользования (существованиенерегулярных языков).1.6 Проблемы пустоты иэквивалентности конечныхавтоматов. Переборный иалгебраический способыдоказательства эквивалентности,оценка сложности.

Понятиеминимального автомата и егопостроение методом грубейшегоразбиения. Оценка сложности.Доказательство эквивалентностиметодом сведения к задаче«Объединить-найти».1.7 Поиск в информационном массиве.Битовые шкалы: константноевключение и поиск. Линейныйпоиск, оценка сложности в худшеми среднем. Бинарный поиск идвоичные деревья поиска.Сбалансированные деревья. 2-3деревья: оценка сложности,процедуры вставки и удаления. Bдеревья, как обобщение 2-3деревьев: оценка сложности. АВЛдеревья: оценка сложности,процедуры вставки в АВЛ дерево.Хэш-функции. Метод расстановки:3322234222352223622237222оценка сложности в худшем исреднем.1.8 Задача сортировки.

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

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

Оценка сложностиалгоритмов ЗГА.1.10 Теорема о точности стационарнойразметки в дистрибутивном случае.Пример формулировки ЗГА дляанализа циклов в графе. Методыминимизации количестваприменений правила разметки.Теорема о невозможностипостроения точного решения вмонотонном случае (путем сведениязадачи анализа к построениюсистемы Поста).2.1 Понятие стандартной схемы: базис,термы, операторы. Понятиеаргументов и результатов,правильность стандартной схемы.3822239222310231122222контрольная3.13.23.34.1Понятие интерпретации: значениетерма, протокол, результат.Свободные интерпретации какпример интерпретации.

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

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

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