1610906302-7baf3ecf4b7f342a1c4a47b28dd9d598 (Программа курса Морозов)

Программа курса «Введение в теорию алгоритмов» для I потока I курса ММФ НГУ2017/2018 учебный год, I семестр1. Введение Понятие о множествах, их основные свойства, операции над ними. Некоторыеосновные понятия в теории множеств (отношения, функции и т.п.). Алфавиты и языки,длина слова, конкатенация слов, степени с натуральным показателем, звездочка Клини.2.

Введение в теорию графов Определение (неориентированного) графа. Смежность,инцидентность. Степень вершины. Лемма о рукопожатии. Дополнительный граф. Матрицасмежности графа. Ориентированные графы. Ориентация дуги, полустепени захода иисхода. Подграфы, остовные и порожденные подграфы. Маршрут. Цепь, простая цепь.Свойства степеней матрицы смежности графа. Циклические маршруты. Циклы, простыециклы. Достижимость для неориентированных и ориентированных графов. Связанность икомпоненты связанности.

Сильная связанность для ориентированных графов. Важныеклассы графов: полный (максимальное количество ребер), дерево (связанный сминимальным количеством ребер; эквивалентные определения), двудольный.Характеризация Кёнига двудольных графов.3. Конечные автоматы Определение конечных автоматов. Их графическое изображение.Языки, распознаваемые конечными автоматами. Лемма о накачивании и примеры еёиспользования. Недетерминированные конечные автоматы, недетерминированныеавтоматы со скачками и их языки. Эквивалентность конечных автоматов,недетерминированных конечных автоматов и недетерминированных автоматов соскачками. Замкнутость конечно-автоматных языков относительно объединения,пересечения, дополнения, конкатенации и звездочки Клини. Регулярные языки.Определение.

Совпадение классов регулярных и конечно-автоматных языков.3. Теория алгоритмов Обсуждение свойств алгоритмических процессов. Определениечастично рекурсивных функций (ЧРФ). Операторы суперпозиции, примитивной рекурсиии минимизации. Примитивно рекурсивные и общерекурсивные функции. Логическиесвязки и их значение. Вычислимые (рекурсивные) отношения и некоторые их свойства.Кодирование конечных последовательностей. Минимашины (ММ). Совпадение классовфункций, вычислимых на ММ и класса частично рекурсивных функций. Тезис Чёрча.Теорема о параметризации (s-m-n-теорема).

Универсальные вычислимые функции.Машины Тьюринга: определение функций, вычислимых на Машинах Тьюринга,совпадение этого класса функций с классом ЧРФ.Общее понятие о нумерации. Понятие об алгоритмически разрешимых и неразрешимыхпроблемах. Неразрешимость проблемы остановки. Теорема Клини о неподвижной точке.Теорема Райса. Неразрешимость проблемы распознавания свойств функций по задающимих программам.

Вычислимо перечислимые множества. Теорема о графике. Теорема Поста.Список литературы[1] Лекторская веб-страница курса с текстами некоторых тем:http://www.math.nsc.ru/~asm256/TA[2] Ю.Л.Ершов, Е.А.Палютин, Математическая логика, М., Наука, 1987.[3] А.Н.Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986.[4] В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич, Лекции по теорииграфов, М.: Наука, 1990.Темы семинаровВведение Множества, отношения, функции, операции над языками. (2-3 семинара)Введение в теорию графов Примеры на основные понятия. Решение занимательныхзадач (1 семинар).Конечные автоматы Построение конкретных автоматов, распознающих некоторыепростые языки. Доказательство автоматности и неавтоматности некоторых языков.Построение эквивалентных детерминированных автоматов по недетерминированным.

(3-4семинара)Теория алгоритмов Построение минимашин для конкретных функций (1 семинар).Доказательство вычислимости (примитивной рекурсивности) для некоторых функций иотношений (2 семинара).Нумерации минимашин и доказательство вычислимости отношения T(a,x,y) (подробноразобрать на семинаре доказательство теоремы) (1-2 семинара)Построение машин Тьюринга для вычисления конкретных функций. (1 семинар)Комбинирование машин Тьюринга (композиция, условный оператор, циклы) (1 семинар).Планируется провести 2 контрольные работы.Программу составил профессор, доктор физико-математических наук А.С.Морозов..