Основы теории вычислимых функций: Информация
Авторы: Николай Верещагин, Александр Шень
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 5 студентам
Уровень:
Профессионал
Длительность:
15:50:00
Студентов:
520
Выпускников:
37
Качество курса:
4.45 | 4.18
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Изложение рассчитано на учеников математических школ,
студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает себя много задач различной трудности.
Специальности: Программист, Математик
Теги: beta, алгоритмы, всюду определенные функции, вычисления, вычислимость, вычислительная модель, графика, дополнение множества, одноместная функция, полугруппа, примитивная рекурсия, примитивно рекурсивная функция, процедуры, разрешимые множества, теория, универсальное множество, частично рекурсивная функция, элементы, эффективность
Предварительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
39 минут
Вычислимость, разрешимость и перечислимость
Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям выполнения этих условий.
Оглавление
-
Лекция 2
30 минут
Универсальные функции и неразрешимость
Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены условия перечислимости таких множеств, некоторые конструкции перечислимых неразрешимых множеств.
Оглавление
-
Лекция 3
33 минуты
Нумерации и операции
Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных универсальных функции и множества.
Оглавление
-
Лекция 4
58 минут
Свойства главных нумераций
Посвящена условиям (выяснению) "нигде не определенности" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема Роджерса об изоморфизме геделевых нумераций.
Оглавление
-
Лекция 5
49 минут
Теорема о неподвижной точке
Посвящена одной из центральных проблем – существованию неподвижной точки (теорема Клини), а также некоторым приложениям этой теоремы, в частности, вопросу существования программы, печатающей свой код.
Оглавление
-
Лекция 6
1 час 25 минут
m-сводимость и свойства перечислимых множеств
Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности, эффективной неперечислимости, m – полноте, изоморфизму.
Оглавление
-
Лекция 7
1 час 41 минута
Вычисления с оракулом
Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции), релятивизации теории вычислимых функции, теореме Мучника-Фридберга о существовании несравнимых по Тьюрингу перечислимых множеств.
Оглавление
-
Лекция 8
1 час 13 минут
Арифметическая иерархия
Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений, объединений, дополнений множеств из этих классов.
Оглавление
-
Лекция 9
1 час 8 минут
Машины Тьюринга
Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах.
Оглавление
-
Лекция 10
1 час 7 минут
Арифметичность вычислимых функций
Посвящена критериям вычислимости на машине Тьюринга, арифметичности множеств, теоремам Тарского и Геделя.
Оглавление
-
Лекция 11
1 час 23 минуты
Рекурсивные функции
Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова.
Оглавление
-