Теория автоматов и алгоритмов

Цели и задачи дисциплины

Цель: Формирование знаний и умений по теории алгоритмов и автоматов для дальнейшего использования в других областях математического знания, дисциплин естественно-научного цикла и программирования; формирование математической культуры; фундаментальная подготовка по основам профессиональных знаний; формирование навыков самостоятельного получения знаний и умение применять их на практике. Задачи: изучить вычислительные модели для реализации и исследования новых (или известных) алгоритмов, применяемых в информационных системах; математические способы доказательства корректности программ, модели эффективности алгоритмов; научиться разрабатывать алгоритмические и программные решения для системного и прикладного программного обеспечения; определять эффективность алгоритмов; овладеть приемами построения и отладки автоматных программ, методами разработки эффективных алгоритмов.

Краткое содержание дисциплины

Изучение курса даст основу профессионального программирования и даст понимание в построении вычислительных устройств. В рамках изучения курса рассматриваются: неформальное понятие алгоритма; понятия, связанные с алгоритмом; свойства алгоритма; абстракция потенциальной осуществимости; алгоритмически неразрешённая задача; определение, принцип работы, применение и конструирование машины Тьюринга; правильная вычислимость функций на машине Тьюринга; композиция машин Тьюринга; тезис Тьюринга; машины Поста; марковские подстановки; НАМ и их применение к словам; нормально вычислимые функции; принцип нормализации Маркова; эквивалентность различных теорий алгоритмов; анализ эффективности; виды эффективности; единицы измерения времени выполнения алгоритма; основные множества для сравнения порядка роста двух функций; основные классы временной эффективности алгоритмов; анализ эффективности рекурсивных и не рекурсивных алгоритмов; числа Фибоначчи и алгоритмы их вычисления; эмпирический анализ алгоритмов; визуализация как еще один путь изучения алгоритмов; основные понятия теории автоматов; конечный автомат: определение и разновидности; простейшие примеры конечных автоматов и их характеристики; автомат распознает слово; определение детерминированного конечного автомата; графическое представление, регулярный язык и минимизация ДКА; программная реализация конечных автоматов; теорема о регулярности языка; регулярность дополнения, объединения и пересечения регулярных языков; произведение ДКА; множество нерегулярных языков; недетерминированный конечный автомат и его отличие от ДКА; графическое представление, слова и языки, преимущества НКА.

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать:

ОПК-1 Способен консультировать и использовать фундаментальные знания в области математического анализа, комплексного и функционального анализа алгебры, аналитической геометрии, дифференциальной геометрии и топологии, дифференциальных уравнений, дискретной математики и математической логики, теории вероятностей, математической статистики и случайных процессов, численных методов, теоретической механики в профессиональной деятельности
ОПК-4 Способен находить, анализировать, реализовывать программно и использовать на практике математические алгоритмы, в том числе с применением современных вычислительных систем