1610906302-7baf3ecf4b7f342a1c4a47b28dd9d598 (824384)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Программа курса «Введение в теорию алгоритмов» для 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 контрольные работы.Программу составил профессор, доктор физико-математических наук А.С.Морозов..

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)