Уважаемые посетители!
Данный сайт является архивным и больше не поддерживается.
Содержание дисциплины:Предмет является обязательным (федеральный компонент) в разделе дисциплин предметной подготовки. Включает в себя теоретический и практический материал по темам: Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости (частично рекурсивные функции, регистровые машины, машины Тьюринга). Тезис Чёрча. Конечные и бесконечные машины. Понятие программы. Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы. Компьютер фон Неймана. Диагональный метод. Пример невычислимой функции. Проблема останова. Примеры неразрешимых и неперечислимых множеств. Алгоритмическая сводимость проблем. Примеры алгоритмически неразрешимых проблем в математике и информатике. Эффективные операции над вычислимыми функциями. Теорема о неподвижной точке. Общее понятие исчисления. Грамматики. Языки, иерархия языков по Хомскому. Языки и машины. Основные меры сложности вычисления. Основы теории NР-полноты. Применение теории NР-полноты для анализа сложности проблем. Приложения теории алгоритмов в информатике.
Компетенции:Знать теоретические основы дисциплины в объёме, необходимом для решения типовых задач; уметь решать типовые задачи изучаемой дисциплины
Связь с другими дисциплинами:Все дисциплины математического цикла