Уважаемые посетители!
Данный сайт является архивным и больше не поддерживается.
Содержание дисциплины:Предмет является обязательным в разделе дисциплин предметной подготовки. Включает в себя теоретический и практический материал по темам: Введение. Алгоритмы в математике. Основные черты алгоритмов. Необходимость уточнения понятия алгоритма. Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции, разрешимого множества. Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции. Операторы подстановки, примитивной рекурсии, минимизации. Рекурсивные предикаты. Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции. Машины Тьюринга. Понятие машины Тьюринга Операции с машинами. Тезис Черча-Тьюринга. Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Рекурсивно-перечислимые множества. Нумерация. Универсальная функция. Теорема Клини. Неразрешимые алгоритмические проблемы. Алгоритмическая сводимость.
Компетенции:Знать теоретические основы дисциплины в объёме, необходимом для решения типовых задач; уметь решать типовые задачи изучаемой дисциплины.
Связь с другими дисциплинами:Все дисциплины математического цикла.\r\n