Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Профессионал
Длительность:
15:50:00
Студентов:
453
Выпускников:
35
Качество курса:
4.45 | 4.18
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Изложение рассчитано на учеников математических школ, студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает себя много задач различной трудности.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
39 минут
Вычислимость, разрешимость и перечислимость
Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям выполнения этих условий.
-
Тест 1
24 минуты
-
Лекция 2
30 минут
Универсальные функции и неразрешимость
Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены условия перечислимости таких множеств, некоторые конструкции перечислимых неразрешимых множеств.
-
Тест 2
24 минуты
-
Лекция 3
33 минуты
Нумерации и операции
Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных универсальных функции и множества.
-
Тест 3
24 минуты
-
Лекция 4
58 минут
Свойства главных нумераций
Посвящена условиям (выяснению) "нигде не определенности" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема Роджерса об изоморфизме геделевых нумераций.
-
Тест 4
24 минуты
-
Лекция 6
1 час 25 минут
m-сводимость и свойства перечислимых множеств
Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности, эффективной неперечислимости, m – полноте, изоморфизму.
-
Тест 6
24 минуты
-
Лекция 7
1 час 41 минута
Вычисления с оракулом
Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции), релятивизации теории вычислимых функции, теореме Мучника-Фридберга о существовании несравнимых по Тьюрингу перечислимых множеств.
-
Тест 7
24 минуты
-
Лекция 8
1 час 13 минут
Арифметическая иерархия
Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений, объединений, дополнений множеств из этих классов.
-
Тест 8
24 минуты
-
Лекция 9
1 час 8 минут
Машины Тьюринга
Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах.
-
Тест 9
24 минуты
-
Лекция 11
1 час 23 минуты
Рекурсивные функции
Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова.
-
Тест 11
24 минуты
-
1 час 40 минут
-
Павел Счетчиков
Павел Счетчиков
Россия, Казань
Сергей Комель
Сергей Комель
Россия