[ Программа курса
ДИСКРЕТНАЯ МАТЕМАТИКА И ТЕОРИЯ АЛГОРИТМОВ
1-й курс, 1-й поток ММФ НГУ,
1-й семестр 2014-2015 уч. года
лектор – к.ф.-м.н. Н.Т.Когабаев
ГЛАВА I. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ.
§1. Некоторые аксиомы теории множеств.
Некоторые аксиомы теории множеств Цермело-Френкеля. Основные операции над множествами. Упорядоченные кортежи. Декартово произведение. Отношения и функции на множествах.
§2. Алфавиты и формальные языки.
Понятия алфавита и слова. Подслова, префиксы и суффиксы. Операции над словами. Понятие формального языка. Операции объединения, пересечения, дополнения, конкатенации и звездочки Клини над языками.
ГЛАВА II. КОНЕЧНЫЕ АВТОМАТЫ И ФОРМАЛЬНЫЕ ГРАММАТИКИ.
§3. Детерминированные конечные автоматы.Определение детерминированных конечных автоматов. Их графическое изображение. Пути в автомате.
Языки, распознаваемые детерминированными конечными автоматами.
§4. Недетерминированные конечные автоматы.
Определение недетерминированных конечных автоматов. Языки, распознаваемые недетерминированными конечными автоматами. Теорема о детерминизации недетерминированных конечных автоматов.
§5. Свойства автоматных языков.
Лемма о вахтере. Замкнутость автоматных языков относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини. Автоматность конечных языков. Лемма о накачивании. Существование неавтоматных языков.
§6. Регулярные языки.
Регулярные выражения. Определение регулярных языков. Теорема о совпадении класса регулярных и класса автоматных языков.
§7. Определение формальных грамматик.
Определение и примеры формальных грамматик. Определение языка, порождаемого грамматикой. Основные типы грамматик.
§8. Свойства формальных грамматик.
Теорема о соотношении класса языков, порождаемых регулярными грамматиками, и класса автоматных языков. Разрешимость языков, порождаемых неукорачивающими грамматиками. Разрешимость контекстно-свободных языков, автоматных языков и языков, порождаемых регулярными грамматиками.
ГЛАВА III. ФОРМАЛИЗАЦИИ ПОНЯТИЯ ВЫЧИСЛИМОЙ ФУНКЦИИ.
§9. Машины Шёнфилда.Описание машины Шёнфилда. Понятие макроса. Примеры макросов. Теорема об элиминации макросов.
Определение функций, вычислимых на машинах Шёнфилда.
§10. Частично рекурсивные функции.
Операторы суперпозиции, примитивной рекурсии и минимизации. Определения примитивно рекурсивных, частично рекурсивных и рекурсивных функций. Теорема о вычислимости ч.р.ф. на машинах Шёнфилда.
§11. Рекурсивность некоторых функций и отношений.
Примитивная рекурсивность нульместных функций и функций x + y, x · y, xy, xy, |x y|, sg(x), sg(x).
Суммы и произведения с переменным верхним индексом суммирования (произведения). Ограниченная минимизация. Рекурсивные и примитивно рекурсивные отношения. Замкнутость (примитивно) рекурсивных отношений относительно конъюнкции, дизъюнкции, импликации, отрицания и ограниченных кванторов существования и всеобщности. Примитивная рекурсивность отношений =, =,,, на натуральных числах. Кусочное задание (примитивно) рекурсивных функций. Примитивная рекурсивность функций [x/y], p(x), ex(i, x) и отношений Div(x, y), Prime(x).
§12. Кодирование машин Шёнфилда.
Кодирование конечных последовательностей, команд и программ. Примитивная рекурсивность предикатов Seq(x), Com(x), Prog(x). Лемма о совместной рекурсии. Лемма о примитивной рекурсивности функций ct(e, x, n) и rg(e, x, n). Код вычисления на машине Шёнфилда и T -предикат Клини.
§13. Машины Шёнфилда vs Частично рекурсивные функции.
Теорема о частичной рекурсивности функций, вычислимых на машинах Шенфилда. Теорема Клини о нормальной форме. Теорема об универсальной ч.р.ф. Определение клиниевской нумерации частично вычислимых функций. Существование невычислимых функций. Теорема о параметризации. s-m-n-теорема.
§14. Машины Тьюринга.
Описание машины Тьюринга. Формальное определение машины Тьюринга. Машинные слова и отношения перерабатываемости одних машинных слов в другие. Определение функции, вычислимой по Тьюрингу.
Теорема о совпадении класса ч.р.ф. и класса вычислимых по Тьюрингу функций (схема доказательства).
ГЛАВА IV. ТЕОРИЯ ВЫЧИСЛИМОСТИ.
§15. Теорема о неподвижной точке.Теорема о неподвижной точке. Теорема Райса. Невычислимость множества всех клиниевских номеров фиксированной частично вычислимой функции.
§16. Вычислимо перечислимые множества.
Определение вычислимо перечислимых множеств. Теорема об эквивалентных определениях вычислимо перечислимых множеств. Неразрешимость проблемы остановки. Существование вычислимо перечислимого множества, не являющегося вычислимым. Замкнутость вычислимо перечислимых множеств относительно объединения, пересечения. Теорема Поста. Незамкнутость вычислимо перечислимых множеств относительно дополнения. Теорема о графике.
§17. Универсальные функции.
Отсутствие р.ф. (п.р.ф.), универсальной для семейства всех k-местных р.ф. (п.р.ф). Вычислимая функция, универсальная для семейства всех полиномов от одной переменной.
ГЛАВА V. ВВЕДЕНИЕ В КОМБИНАТОРИКУ И ТЕОРИЮ ГРАФОВ.
§18. Введение в комбинаторику.Правила суммы и произведения. Число (всевозможных, инъективных, строго возрастающих) отображений множества {1, 2,..., k} в множество {1, 2,..., n}. Число подмножеств n-элементного множества. Число перестановок n-элементного множества. Число размещений Ak. Число сочетаний Cn. Свойства биномиk n альных коэффициентов.
§19. Введение в теорию графов.
Понятия ориентированного и неориентированного графов. Смежность и инцидентность. Изоморфизм графов. Маршруты, цепи, циклы, пути и контуры в графах. Связные графы. Обходы неориентированных связных графов. Алгоритмы поиска в глубину и ширину.
ТЕМЫ СЕМИНАРСКИХ ЗАНЯТИЙ:
1. Теоретико-множественные операции. Алфавиты, слова и языки. Конкатенация, звездочка Клини.2. Детерминированные конечные автоматы.
3. Недетерминированные конечные автоматы. Теорема о детерминизации.
4. Формальные грамматики. Регулярные грамматики. КС-грамматики.
5. Регулярные языки. Лемма о накачивании. Примеры нерегулярных языков.
6. Контрольная работа.
7. Машины Шёнфилда. Функции, вычислимые по Шёнфилду.
8. Примитивно рекурсивные функции.
9. Ограниченная минимизация. Частично рекурсивные функции.
10. Базовые машины Тьюринга. Правый и левый сдвиги, перенос нуля, транспозиция, удвоение.
11. Композиция машин Тьюринга. Циклический сдвиг, копирование. Вычислимые по Тьюрингу функции.
12. Универсальные функции, s-m-n-теорема, теорема о неподвижной точке.
13. Вычислимые и невычислимые множества. Теорема Райса.
14. Вычислимо перечислимые множества. Теорема Поста. Теорема о графике.
15. Элементы комбинаторики. Базовые понятия теории графов.
Список основной литературы:
(1) Н. Т. Когабаев, Лекции по теории алгоритмов, Новосибирск, НГУ, 2009. (электронный вариант доступен на сайте ММФ mmf.nsu.ru в разделе Ресурсы/Учебные материалы) Список дополнительной литературы:
(2) Ю. Л. Ершов, Теория нумераций, Москва, Наука, 1977.
(3) Ю. Л. Ершов, Е. А. Палютин, Математическая логика, Санкт-Петербург, Лань, 2004.
(4) Т. Йех, Теория множеств и метод форсинга, Москва, Мир, 1973.
(5) В. Н. Касьянов, Лекции по теории формальных языков, автоматов и сложности вычислений, Новосибирск, НГУ, 1995.
(6) А. И. Мальцев, Алгоритмы и рекурсивные функции, Москва, Наука, 1986.
(7) Э. Мендельсон, Введение в математическую логику, Москва, Наука, 1971.
(8) А. С. Морозов, Машины Шёнфилда, Методические указания, Новосибирск, НГУ, 1996.
(9) Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Москва, Мир, 1972.
(10) Р. И. Соар, Вычислимо перечислимые множества и степени, Казань, Казанское мат. общество, 2000.
(11) B. Khoussainov, A. Nerode, Automata Theory and Its Applications, Boston, Birkhauser, 2001.
(12) H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, New Jersey, Plentice Hall, 1998.
(13) J. R. Shoeneld, Recursion Theory, Lecture Notes in Logic, Berlin, Springer-Verlag, 1993.
«