Дехтярь М.И. - Введение в схемы, автоматы и алгоритмы (2-е издание)

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

Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков.

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

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

Содержание:

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

Название: Введение в схемы, автоматы и алгоритмы
Автор: Дехтярь М.И.
Издательство: М.: НОУ "Интуит"
Год издания: 2016
Качество: Хорошее
Страниц: 169
Формат: PDF
Язык: Русский
Размер: 15.2 Mb