Analysis and design of algorithms (theory of algorithms)

Description: The purpose of the discipline is to study the concept of an algorithm by mathematical methods and master the methods for constructing specific algorithms. In this course, the General properties and regularities of algorithms and various formal models of their representation are studied. The main attention is paid to algorithms of recognition of regular languages by finite automata, Turing and Post machines, associative calculations, recursive functions. This course forms the theoretical basis for cryptographic methods of information security.

Amount of credits: 5

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

• Algebra

Course Workload:

Component: Component by selection

Cycle: Base disciplines

Goal

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

Objective

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

Learning outcome: knowledge and understanding

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

Learning outcome: applying knowledge and understanding

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

Learning outcome: formation of judgments

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

Learning outcome: communicative abilities

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

Learning outcome: learning skills or learning abilities

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

Key reading

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