Основы теории вычислимых функций: Информация
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 5 студентам
Уровень:
Профессионал
Длительность:
15:50:00
Студентов:
534
Выпускников:
42
Качество курса:
4.45 | 4.18
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Изложение рассчитано на учеников математических школ,
студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает себя много задач различной трудности.
Специальности: Программист, Математик
Предварительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 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 минуты
Рекурсивные функции
Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова.
Оглавление
-