Книга: Дехтярь М. И. «Введение в схемы, автоматы и алгоритмы»

Введение в схемы, автоматы и алгоритмы

Серия: "Основы информационных технологий"

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

Содержание:

Выходные данные...... 3 Лекция 1. Предварительные сведения...... 4 Лекция 2. Реализация булевых функций с помощью логических схем...... 22 Лекция 3. Упорядоченные бинарные диаграммы решений (УБДР)...... 35 Лекция 4. Конечные автоматы: преобразователи и распознаватели...... 48 Лекция 5. Регулярные языки и конечные автоматы...... 73 Лекция 6. Свойства замкнутости класса автоматных языков. Неавтоматные языки...... 85 Лекция 7. Алгоритмы: структурированные программы...... 101 Лекция 8. Алгоритмы: частично рекурсивные функции...... 110 Лекция 9. Алгоритмы: машины Тьюринга...... 128 Лекция 10. Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы...... 146 Список литературы...... 168

Издательство: "Национальный Открытый Университет «ИНТУИТ»" (2016)

ISBN: 9785947747140

См. также в других словарях:

  • Конечные автоматы — Конечный автомат  в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… …   Википедия

  • Конечный автомат — Конечный автомат  абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например,… …   Википедия

  • НКА — Конечный автомат  в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… …   Википедия

  • Эквивалентность детерминированных и недетерминированных конечных автоматов — Конечный автомат  в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… …   Википедия

  • ЛОГИЧЕСКИЕ СХЕМЫ АВТОМАТОВ — технич. устройства (или части технич. устройств), в к рых зависимость между входными и выходными сигналами выражается логич. функцией. Л. с. а. делятся на два основных класса – Л. с. а. без памяти (однотактные или комбинационные схемы), в к рых… …   Философская энциклопедия

  • КИБЕРНЕТИКА — (от греч. kybernetike [techne] – искусство управления) – наука о самоуправляющихся машинах, в частности о машинах с электронным управлением («электронный мозг»). Кибернетика получила самое широкое распространение в последней трети 20 в. и сейчас… …   Философская энциклопедия

Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»