Основы теории алгоритмов — различия между версиями
Root (обсуждение | вклад) (Новая страница: «Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович. == Программа к…») |
PodymovVV (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
| + | [[Категория:Спецкурсы кафедры МК (архив)]] | ||
| + | |||
Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]]. | Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]]. | ||
| Строка 23: | Строка 25: | ||
Теорема о неподвижной точке и ее следствия. | Теорема о неподвижной точке и ее следствия. | ||
| − | + | m-сводимость и ее свойства. Существование m-полного перечислимого множества. | |
Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация | Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация | ||
| Строка 42: | Строка 44: | ||
* Программа курса ([[Media:Osnov_p.pdf|pdf]]) | * Программа курса ([[Media:Osnov_p.pdf|pdf]]) | ||
| − | |||
| − | |||
Текущая версия на 13:08, 18 февраля 2019
Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.
Программа курса
Машины Тьюринга. Вычислимые функции. Тезис Черча.
Разрешимые и перечислимые множества, теоретико-множественные операции над ними. Эквивалентные определения перечислимых множеств. Связь между вычислимыми функциями и перечислимыми множествами.
Универсальные функции. Построение вычислимой универсальной функции. Всюду определенные продолжения вычислимых функций.
Существование рекурсивно перечислимого неразрешимого множества. Рекурсивно перечислимые рекурсивно неотделимые множества.
Иммунные и простые множества. Простое множество Поста.
Существование главной универсальной функции. Номера композиции функций в главной нумерации. Неразрешимость множества номеров нетривиального семейства функций в главной нумерации. Изоморфизм главных нумераций.
Теорема о неподвижной точке и ее следствия.
m-сводимость и ее свойства. Существование m-полного перечислимого множества.
Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация относительной вычислимости функций.
Операции суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции. Относительная примитивная рекурсивность. Операции ограниченного суммирования и мультиплицирования. Предикаты и представляющие функции. Операции ограниченной квантификации и минимизации. Возвратная рекурсия.
Литература
- Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999. 174 с.
- Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. 392 с.
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.
Ссылки
- Программа курса (pdf)
