Теория алгоритмов
Название спецкурса на английском языке
Theory of algorithms
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Машины Тьюринга. Основные понятия. Тезис Тьюринга. Вычислимые (по Тьюрингу) функции. Примеры машин Тьюринга.
Проблема самоприменимости. Проблема применимости.
Универсальные машины Тьюринга.
Классы вычислимых и рекурсивных функций. Операции суперпозиции,
примитивной рекурсии, минимизации. Тезис Чёрча. Примеры.
Некоторые теоремы теории рекурсивных функций. Функция Аккермана.
Теорема о совпадении класса вычислимых по Тьюрингу функций и класса
частично рекурсивных функций (Кв=Кчр).
Нормальные алгоритмы Маркова. Теорема о совпадении класса нормально
вычислимых функций с классами Кв, Кчр.
Разрешимость и перечислимость множеств. Теорема Райса.
О теореме Гёделя о неполноте.
Проблема самоприменимости. Проблема применимости.
Универсальные машины Тьюринга.
Классы вычислимых и рекурсивных функций. Операции суперпозиции,
примитивной рекурсии, минимизации. Тезис Чёрча. Примеры.
Некоторые теоремы теории рекурсивных функций. Функция Аккермана.
Теорема о совпадении класса вычислимых по Тьюрингу функций и класса
частично рекурсивных функций (Кв=Кчр).
Нормальные алгоритмы Маркова. Теорема о совпадении класса нормально
вычислимых функций с классами Кв, Кчр.
Разрешимость и перечислимость множеств. Теорема Райса.
О теореме Гёделя о неполноте.
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции.
Мендельсон Э. Введение в математическую логику.
Яблонский С.В. Введение в дискретную математику.
Гаврила Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики.
Мендельсон Э. Введение в математическую логику.
Яблонский С.В. Введение в дискретную математику.
Гаврила Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики.
День недели
среда
Время
16:45-18:20
Аудитория
409
Дата первого занятия
Аудитория первого занятия
409