Обязательный кафедральный курс для студентов 3 курса (314 группа), читается в 6 семестре.
Лекции – 34 часа, семинары 34 часа.
Экзамен в 6 семестре.
За курс отвечает кафедра нелинейных динамических систем и процессов управления.
Автор программы: проф. Шоломов Л.А.
Лектор 2013/14 уч.года: проф. Шоломов Л.А.

Аннотация

В курсе излагаются фундаментальные математические результаты, составляющие теоретическую основу информатики. Они входят в состав ряда научных дисциплин, в числе которых теория алгоритмов, математическая логика, теория формальных систем и языков, математическая теория сложности, теория информации. Материал курса изложен систематически и с единых позиций. Некоторые темы, относящиеся к данному предмету, изучались в обязательном курсе «Дискретная математика» и потому опущены.

В первую часть курса (5 семестр) входит рассмотрение формальных моделей алгоритмов и вычислений (на базе машины Тьюринга), изучение частично-рекурсивных функций и доказательство их эквивалентности вычислимым функциям, построение универсальных машин и универсальных частично-рекурсивных функций, изучение связанных с ними нумераций и доказательство ряда общих теорем теории алгоритмов, анализ свойств разрешимых и перечислимых множеств, освоение техники доказательства алгоритмической неразрешимости, рассмотрение формальных систем общего вида и их частных случаев – грамматик и логических исчислений, изучение контекстно-свободных грамматик, исследование свойств исчисления высказываний.

Во вторую часть курса (6 семестр) входит рассмотрение логического языка первого порядка, изучение исчисления предикатов и вопросов аксиоматизируемости теорий, доказательство неаксиоматизируемости арифметики, изучение характеристик сложности вычислений, рассмотрение классов сложности P и NP, доказательство NP-полноты ряда дискретных задач, изложение машинно-независимой теории сложности вычислений, изучение сложности конечных объектов по Колмогорову, введение на этой основе и анализ понятия алгоритмической информации, изложение элементов статистической теории информации Шеннона, доказательство результатов о сжатии данных и о скорости передачи при наличии помех.

 

Содержание курса

Лекции, 5 семестр

1. Машины Тьюринга и частично-рекурсивные функции

Машины Тьюринга. Модель машины. Реализация на ней частичных словарных и числовых функций. Приемы тьюрингова программирования: суперпозиция, композиция, ветвление машин, реализация цикла. Тезис Черча-Тьюринга.

Частично рекурсивные функции. Эффективная нумерация слов, сведение словарных функций к числовым. Операции суперпозиции, рекурсии и минимизации. Частично рекурсивные и рекурсивные функции. Доказательство рекурсивности основных арифметических функций. Нумерация пар и n-ок чисел. Схема совместной рекурсии.

Эквивалентность частичной рекурсивности и вычислимости по Тьюрингу. Реализация на машинах Тьюринга операций суперпозиции, рекурсии и минимизации, вычисление частично рекурсивных функций. Метод арифметизации. Арифметизация машин Тьюринга и доказательство частичной рекурсивности числовых функций, вычислимых по Тьюрингу.

 

2. Универсальные машины и функции, общие теоремы

теории алгоритмов

Универсальная машина Тьюринга. Шифры машин и конфигураций. Понятие универсальной машины Тьюринга, конструкция универсальной машины. Нумерация машин Тьюринга, ее эффективность.

Нумерации и универсальные функции. Нумерации частично рекурсивных функций. Универсальные функции. Вычислимые нумерации. Вычислимость нумерации, ассоциированной с машинами Тьюринга. Невозможность вычислимой нумерации рекурсивных функций. Наличие частично рекурсивных функций, не доопределимых до рекурсивных. Сводимость нумераций. Главные (геделевы) нумерации. Геделевость нумерации, ассоциированной с машинами Тьюринга. Содержательное обсуждение роли главных нумераций в получении машинно-независимых результатов.

Общие теоремы теории алгоритмов. Итерационная теорема. Теорема Клини о неподвижной точке. Теорема Райса. Ее содержательная интерпретация в терминах программ.

 

3. Разрешимые и перечислимые множества

Разрешимые и перечислимые множества. Характеристическая и частичная характеристическая функция множеств. Разрешимость и перечислимость в терминах этих функций. Замкнутость класса разрешимых (перечислимых) множеств относительно произвольных (соответственно, монотонных) теоретико-множественных операций. Перечислимость разрешимого множества. Пример перечислимого неразрешимого множества. Теорема Поста. Связь вычислимости функций с перечислимостью графиков. Перечислимость области определения и области значений вычислимой функции.

 

4. Алгоритмически неразрешимые проблемы

Индивидуальные и массовые задачи. Сводимость задач. Метод сводимости. Алгоритмическая неразрешимость проблемы самоприменимости. Диагональный метод. Неразрешимость для машин Тьюринга проблемы останова и проблемы переводимости. Моделирование машин Тьюринга системой подстановок. Неразрешимость проблемы выводимости в системах подстановок и проблемы равенства в полугруппах. Комбинаторная проблема Поста, ее неразрешимость (без доказательства).

 

5. Формальные системы и языки

Абстрактный язык. Алфавит, слова, язык. Операции над языками: теоретико-множественные, конкатенация, степень, итерация, подстановка. Некоторые свойства этих операций.

Формальные системы. Задание формальных систем. Аксиомы и правила вывода. Вывод в формальной системе, порождаемый язык. Некоторые примеры. Перечислимость языка формальной системы. Сопоставление формальных систем и алгоритмов. Система подстановок как формальная система. Порождаемость системами подстановок любых перечислимых словарных множеств.

 

6. Грамматики

(Порождающие) грамматики. Основной и вспомогательный словари, правила грамматики, вывод, полный вывод, порождаемый язык. Порождаемость произвольных перечислимых словарных множеств. Некоторые преобразования выводов и грамматик. Иерархия Хомского.

Контекстно-свободные (КС) грамматики. Преобразования КС-грамматик: сведение к неукорачивающим, приведение, устранение цепных правил. Пример языка, не представимого КС-грамматиками. Операции над языками и грамматиками. Замкнутость класса КС-языков относительно операций объединения, конкатенации, итерации и подстановки, незамкнутость относительно пересечения и дополнения. Дерево вывода. Эквивалентные выводы. Свойство однозначности. Алгоритмические проблемы для КС-грамматик. Разрешимость КС-языков. Решение проблемы конечности КС-языков. Неразрешимость проблемы однозначности.

 

7. Исчисление высказываний

Логические исчисления. Формулы, аксиомы и правила вывода. Вывод из системы гипотез, доказательство. Свойства отношения выводимости.

Исчисление высказываний. Формулы. Аксиомы, правило заключения. Примеры выводов. Теорема дедукции. Общезначимость выводимых формул. Непротиворечивость исчисления. Полнота исчисления высказываний. Полнота в узком смысле. Разрешимость. Независимость аксиом.

Лекции, 6 семестр

8. Исчисление предикатов

Язык первого порядка. Термы и формулы. Свободные и связанные переменные. Интерпретации. Значения формул. Модели. Эквивалентные преобразования формул. Приведение к предваренной форме.

Исчисление предикатов. Аксиомы и правила вывода. Корректность исчисления предикатов. Непротиворечивость. Теорема Геделя о полноте исчисления предикатов (формулировка). Отсутствие полноты в узком смысле. Теорема Черча о неразрешимости исчисления предикатов.

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

 

9. Сложность вычислений, классы P и NP

Характеристики сложности вычислений (сигнализирующие). Временная и емкостная сигнализирующие машин Тьюринга. Классы задач P и NP. Полиномиальная сводимость. NP-полные задачи. Теорема Кука о NP-полноте задачи выполнимости. NP-полнота задач 3-выполнимости, монотонной 3-выполнимости, задач о клике, вершинном покрытии, покрытии. Проблема устранимости перебора.

 

10. Машинно-независимая теория сложности

Свойства сигнализирующих (на примере временной и емкостной). Аксиомы Блюма, общее понятие сигнализирующей. Теоремы Цейтина и Рабина. Теорема Блюма об убыстрении вычислений. Аксиомы Блюма и диагональный метод.

11. Сложность конечных объектов, алгоритмическая информация

Сложность конечных объектов по Колмогорову. Сложность по заданной частично рекурсивной функции. Теорема оптимальности. Сложность по Колмогорову. Миноранты и мажоранты сложности. Теорема об отсутствии вычислимых минорант. Невычислимость сложности по Колмогорову. Мажоранты сложности для слов заданной длины и из заданного частотного класса. Теорема об отсутствии "хороших" мажорант. Сложность слов при ограничении на время вычислений. Относительная сложность по Колмогорову.

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

12. Статистическая теория информации

Мера информации. Энтропия случайного опыта и ее свойства. Произведение случайных опытов. Условная энтропия и ее свойства. Мера информации случайных опытов и ее свойства.

Сжатие данных. Алфавитное и блоковое кодирование. Характеристики кодирования. Теорема Шеннона о сжатии данных. Универсальное кодирование.

Передача информации при наличии помех. Помехоустойчивое кодирование. Кодовое расстояние и корректирующая способность кода. Линейные систематические коды. Декодирование в ближайший кодовый набор. Характеристики системы передачи информации: вероятность ошибки, скорость передачи, пропускная способность канала. Пропускная способность двоичного симметричного канала. Теорема Шеннона о скорости передачи при наличии помех. Достижимость максимальной скорости при использовании линейных кодов.

 

 

Литература

Основная литература

1. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Лань, 2004.

2. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука, 1980.

3. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986.

5. Гэри М., Джонсон М. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.

6. Колмогоров А.Н. Алгоритм, информация, сложность. – М.: Знание, 1991.

7. Галлагер Р. Теория информации и надежная связь. – М.: Советское радио, 1974

 

Дополнительная литература

1. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2006.

2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.

3. Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982. – (Популярные лекции по математике).

4. Алексеев В.Б. Введение в теорию сложности алгоритмов. – М.: Изд. отдел ф-та ВМиК МГУ, 2002.

5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 1999.

6. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987. – (Библиотечка программиста).

7. Гладкий А.В. Формальные грамматики и языки. – М.: Наука, 1973.

8. Трахтенброт Б.А. Сложность алгоритмов и вычислений: Спецкурс для студентов НГУ. – Новосибирск: Изд. НГУ, 1967.