Theory of Algorithms
Description: The purpose of the course is fundamental training in the field of mathematical logic, mastering the modern mathematical apparatus necessary for solving applied problems. Questions are considered: the theory of recursive functions; definability of calculations in formal calculus; Turing machines, Schoenfield machines, equivalence of different approaches to computability; familiarity with the basic concepts and results of the theory of complexity of calculations.
Amount of credits: 5
Пререквизиты:
- Analysis, number theory and approximation
Course Workload:
| Types of classes | hours |
|---|---|
| Lectures | 15 |
| Practical works | 30 |
| Laboratory works | |
| SAWTG (Student Autonomous Work under Teacher Guidance) | 75 |
| SAW (Student autonomous work) | 30 |
| Form of final control | Exam |
| Final assessment method |
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
- Владеть навыками приобретения новых математических знаний, необходимых для повседневной профессиональной деятельности и продолжения образования в докторантуре, стремиться к профессиональному и личностному росту
Key reading
- 1. А.И. Мальцев Алгоритмы и рекурсивные функции. М.: Нау-ка, 2005. 2. С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2007г. 3. Х. Роджерс Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 2004. 4. К. Соар. Вычислимо перечислимые множества и степени. Казань. Изд. Казанск. у-та, 2003.
