Информация о курсе
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР). Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков. Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.

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

Предварительные знания
Для изучения курса желательно предварительное знакомство с материалами курса "Основы дискретной математики".

Предварительные курсы

• Основы дискретной математики

Дополнительные курсы

• Графы и их применение
• Графы и алгоритмы
• Структуры данных и модели вычислений