Анализ и проектирование алгоритмов (теория алгоритмов)

Описание: Целью дисциплины является изучение понятия алгоритма математическими методами и овладение методами построения конкретных алгоритмов. В рамках данного курса изучаются общие свойства и закономерности алгоритмов и разнообразных формальных моделей их представления. Основное внимание уделяется алгоритмам распознавания регулярных языков конечными автоматами, машинами Тьюринга и Поста, ассоциативным вычислениям, рекурсивным функциям. Данный курс образует теоретический фундамент для криптографических методов защиты информации.

Количество кредитов: 5

Пререквизиты:

• Алгебра

Трудоемкость дисциплины:

Компонент: Компонент по выбору

Цикл: Базовые дисциплины

Цель

• Изучение понятия алгоритма математическими методами и овладение методами построения конкретных алгоритмов

Задача

• 1.Изучить различные уточнения понятия алгоритма; 2. Рассмотреть методы построения конкретных алгоритмов; 3. Составлять программу для машины Тьюринга для вычисления известных функций; 4. Доказывать вычислимую перечислимость основных подмножеств натуральных чисел:

Результат обучения: знание и понимание

• Умеет выводить формулы в различных формальных исчислениях и освоить методы доказательства непротиворечивости;

Результат обучения: применение знаний и пониманий

• Приобретение современных знаний в области математики к построению и исследованию алгоритмов;

Результат обучения: формирование суждений

• Умение формулировать основные понятия и высказывать суждения о построенных алгоритмов, выбранном методе теории алгоритмов и обосновать их

Результат обучения: коммуникативные способности

• Быть способным работать в команде, корректно отстаивать свою точку зрения, предлагать новые решения математическими методами прикладных задач

Результат обучения: навыки обучения или способности к учебе

• Владеть навыками приобретения новых математических знаний, необходимых для повседневной профессиональной деятельности и продолжения образования в докторантуре, стремиться к профессиональному и личностному росту

Основная литература

• 1. А.И. Мальцев Алгоритмы и рекурсивные функции. М.: Нау-ка, 2005. 2. С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2007г. 3. Х. Роджерс Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 2004. 4. К. Соар. Вычислимо перечислимые множества и степени. Казань. Изд. Казанск. у-та, 2003.