| Казахстан, Алматы |
Инспектор
Вы можете этот курс.
Опубликован: 16.03.2007 | Уровень: профессионал | Доступ: платный
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Изложение рассчитано на учеников математических школ,
студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает себя много задач различной трудности.
Предварительные курсы |
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 139 минут | Вычислимость, разрешимость и перечислимость
Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям выполнения этих условий.
Оглавление | - |
Тест 124 минуты | - | |
Лекция 230 минут | Универсальные функции и неразрешимость
Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены условия перечислимости таких множеств, некоторые конструкции перечислимых неразрешимых множеств.
Оглавление | - |
Тест 224 минуты | - | |
Лекция 333 минуты | Нумерации и операции
Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных универсальных функции и множества.
Оглавление | - |
Тест 324 минуты | - | |
Лекция 458 минут | Свойства главных нумераций
Посвящена условиям (выяснению) "нигде не определенности" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема Роджерса об изоморфизме геделевых нумераций.
Оглавление | - |
Тест 424 минуты | - | |
Лекция 549 минут | Теорема о неподвижной точке
Посвящена одной из центральных проблем – существованию неподвижной точки (теорема Клини), а также некоторым приложениям этой теоремы, в частности, вопросу существования программы, печатающей свой код.
Оглавление | - |
Тест 524 минуты | - | |
Лекция 61 час 25 минут | m-сводимость и свойства перечислимых множеств
Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности, эффективной неперечислимости, m – полноте, изоморфизму.
Оглавление | - |
Тест 624 минуты | - | |
Лекция 71 час 41 минута | Вычисления с оракулом
Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции), релятивизации теории вычислимых функции, теореме Мучника-Фридберга о существовании несравнимых по Тьюрингу перечислимых множеств.
Оглавление | - |
Тест 724 минуты | - | |
Лекция 81 час 13 минут | Арифметическая иерархия
Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений, объединений, дополнений множеств из этих классов.
Оглавление | - |
Тест 824 минуты | - | |
Лекция 91 час 8 минут | Машины Тьюринга
Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах.
Оглавление | - |
Тест 924 минуты | - | |
Лекция 101 час 7 минут | Арифметичность вычислимых функций
Посвящена критериям вычислимости на машине Тьюринга, арифметичности множеств, теоремам Тарского и Геделя.
Оглавление | - |
Тест 1024 минуты | - | |
Лекция 111 час 23 минуты | Рекурсивные функции
Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова.
Оглавление | - |
Тест 1124 минуты | - | |
5 часов | - |
