Компьютерные науки
Математика и логика

Основы теории вычислимых функций

Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Студентов 578 Выпускников 45 Для всех
Бесплатно
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
72 час.
Длительность
60 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Изложение рассчитано на учеников математических школ, студентов математиков и всех интересующихся основами теории алгоритмов. Книга включает в себя много задач различной трудности.

Авторы

Верещагин Николай Константинович
Верещагин Николай Константинович
Доктор физико-математических наук, профессор кафедры "Математической логики и теории алгоритмов" механико-математического факультета Московского Государственного Университета им. М.В. Ломоносова.
Шень Александр Ханиевич
Шень Александр Ханиевич
Кандидат физико-математических наук, старший научный сотрудник Института проблем передачи информации РАН.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Вычислимость, разрешимость и перечислимость Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям... Посвящена основным понятиям теории вычислимых функции и перечислимых множеств: вычислимость, разрешимость, перечислимость, а также некоторым критериям выполнения этих условий. ещё
Вычислимость, разрешимость и перечислимость тест для курса Основы теории вычислимых функций 40 мин
2 Универсальные функции и неразрешимость Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены... Посвящена основным теоремам существования (не существования) вычислимых функций двух переменных, перечислимости множеств пар натуральных чисел, рассмотрены условия перечислимости таких множеств, некоторые конструкции перечислимых неразрешимых множеств. ещё
Универсальные функции и неразрешимость тест для курса Основы теории вычислимых функций 40 мин
3 Нумерации и операции Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных... Посвящена основным понятиям и теоремам относительно нумерации, существования алгоритма нахождения номеров объектов в нумерациях, использованию главных универсальных функции и множества. ещё
Нумерации и операции тест для курса Основы теории вычислимых функций 40 мин
4 Свойства главных нумераций "Посвящена условиям (выяснению) ""нигде не определенности"" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема... "Посвящена условиям (выяснению) ""нигде не определенности"" функции, приводится теорема Успенского-Райса и ее усиления, а также теорема Роджерса об изоморфизме геделевых нумераций." ещё
Свойства главных нумераций тест для курса Основы теории вычислимых функций 40 мин
5 Теорема о неподвижной точке Посвящена одной из центральных проблем – существованию неподвижной точки (теорема Клини), а также некоторым приложениям этой... Посвящена одной из центральных проблем – существованию неподвижной точки (теорема Клини), а также некоторым приложениям этой теоремы, в частности, вопросу существования программы, печатающей свой код. ещё
Теорема о неподвижной точке тест для курса Основы теории вычислимых функций 40 мин
6 m-сводимость и свойства перечислимых множеств Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности,... Посвящена проблема m-сводимости перечислимых множеств (существованию m – сводящей функции), а также их свойствам, в частности, эффективной неперечислимости, m – полноте, изоморфизму. ещё
m-сводимость и свойства перечислимых множеств тест для курса Основы теории вычислимых функций 40 мин
7 Вычисления с оракулом Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции),... Посвящена проблеме сводимости по Тьюрингу (Т – сводимости) и относительной вычислимости (вычислимости относительно всюду определенной функции), релятивизации теории вычислимых функции, теореме Мучника-Фридберга о существовании несравнимых по Тьюрингу перечислимых множеств. ещё
Вычисления с оракулом тест для курса Основы теории вычислимых функций 40 мин
8 Арифметическая иерархия Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений,... Посвящена критериям принадлежности свойств классам свойств, определяющихся последовательностями дескрипторов – кванторов существования и общности, свойствам пересечений, объединений, дополнений множеств из этих классов. ещё
Арифметическая иерархия тест для курса Основы теории вычислимых функций 40 мин
9 Машины Тьюринга Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины... Посвящена простой классической вычислительной модели (описанию) алгоритма (алгоритмизируемого процесса) – машине А.Тьюринга, проблеме остановки такой машины (завершаемости такого процесса) и связям этой проблемы с классической алгоритмической проблемой равенства слов в свободных полугруппах. ещё
Машины Тьюринга тест для курса Основы теории вычислимых функций 40 мин
10 Арифметичность вычислимых функций Посвящена критериям вычислимости на машине Тьюринга, арифметичности множеств, теоремам Тарского и Геделя.
Арифметичность вычислимых функций тест для курса Основы теории вычислимых функций 40 мин
11 Рекурсивные функции Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а... Посвящена рекурсивным операциям, функциям и множествам, приведены примеры, рассмотрены различные виды рекурсии (примитивная, совместная, возвратная), а также частично рекурсивные функции и нормальные алгоритмы Маркова. ещё
Рекурсивные функции тест для курса Основы теории вычислимых функций 40 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

Бесплатно
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^