Основы теории алгоритмов — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Новая страница: «Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович. == Программа к…»)
 
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК (архив)]]
 +
 
Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]].
 
Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]].
  
Строка 23: Строка 25:
 
Теорема о неподвижной точке и ее следствия.  
 
Теорема о неподвижной точке и ее следствия.  
  
<math>m</math>-сводимость и ее свойства. Существование <math>m</math>-полного перечислимого множества.
+
m-сводимость и ее свойства. Существование m-полного перечислимого множества.
  
 
Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация
 
Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация
Строка 42: Строка 44:
  
 
* Программа курса ([[Media:Osnov_p.pdf|pdf]])
 
* Программа курса ([[Media:Osnov_p.pdf|pdf]])
 
[[Категория:Спецкурсы кафедры МК]]
 

Текущая версия на 13:08, 18 февраля 2019


Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.

Программа курса

Машины Тьюринга. Вычислимые функции. Тезис Черча.

Разрешимые и перечислимые множества, теоретико-множественные операции над ними. Эквивалентные определения перечислимых множеств. Связь между вычислимыми функциями и перечислимыми множествами.

Универсальные функции. Построение вычислимой универсальной функции. Всюду определенные продолжения вычислимых функций.

Существование рекурсивно перечислимого неразрешимого множества. Рекурсивно перечислимые рекурсивно неотделимые множества.

Иммунные и простые множества. Простое множество Поста.

Существование главной универсальной функции. Номера композиции функций в главной нумерации. Неразрешимость множества номеров нетривиального семейства функций в главной нумерации. Изоморфизм главных нумераций.

Теорема о неподвижной точке и ее следствия.

m-сводимость и ее свойства. Существование m-полного перечислимого множества.

Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация относительной вычислимости функций.

Операции суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции. Относительная примитивная рекурсивность. Операции ограниченного суммирования и мультиплицирования. Предикаты и представляющие функции. Операции ограниченной квантификации и минимизации. Возвратная рекурсия.

Литература

  1. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999. 174 с.
  2. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. 392 с.
  3. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.

Ссылки

  • Программа курса (pdf)