Вычислимые числовые функции

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