Введение в схемы, автоматы и алгоритмы: Информация
Автор: Михаил Дехтярь | Тверской государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 36 студентам
Уровень:
Специалист
Длительность:
14:18:00
Студентов:
1719
Выпускников:
261
Качество курса:
5.00 | 5.00
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР).
Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков.
Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ.
Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Специальности: Программист, Математик
ISBN: 978-5-94774-714-0
Теги: PQ, автоматы, алгоритмы, арифметическая функция, вычисления, вычислимость, диаграмма автомата, законы, компоненты, курсы, полустепень исхода, примитивная рекурсия, примитивно рекурсивная функция, рабочая переменная, распознаватель, регулярные выражения, сложность, структурированная программа, УБДР, элементы
Предварительные курсы
Дополнительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 27 минут
Предварительные сведения
Класс \mathcal{P}_n булевых функций от n переменных. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой и 2-х
переменных. Булевы (логические) формулы и их
эквивалентность. Основные эквивалентности ( законы логики ).
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ).
Графы. Деревья.
Оглавление
-
Лекция 2
40 минут
Реализация булевых функций с помощью логических схем
Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические схемы и линейные программы. Примеры логических схем: сложение по модулю 2 и двоичный сумматор
Оглавление
-
Лекция 3
47 минут
Упорядоченные бинарные диаграммы решений (УБДР)
Бинарные деревья решений и их превращение в упорядоченные бинарные
диаграммы решений (УБДР). Сокращенные УБДР и их построение по произвольным
УБДР, алгоритм СОКРАЩЕНИЕ-УБДР. Построение сокращенных УБДР по формулам
Оглавление
-
Лекция 4
1 час 49 минут
Конечные автоматы: преобразователи и распознаватели
Конечные автоматы-преобразователи. Пример: сложение двоичных чисел.
Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство
правильности автомата. Произведение автоматов. Замкнутость класса конечно-автоматных языков
относительно теоретико-множественных операций
Оглавление
-
Лекция 5
49 минут
Регулярные языки и конечные автоматы
Операции конкатенации и итерации языков. Регулярные выражения и языки. Примеры регулярных выражений и языков. Построение конечного автомата по регулярному выражению
Оглавление
-
Лекция 6
1 час 18 минут
Свойства замкнутости класса автоматных языков. Неавтоматные языки
Построение конечного автомата для гомоморфного образа автоматного языка и для обращения гомоморфизма.
Теорема о разрастании для автоматных языков.
Ее применение для доказательства неавтоматности языка.Примеры неавтоматных языков
Оглавление
-
Лекция 7
42 минуты
Алгоритмы: структурированные программы
Алгоритмы и модели вычислений. Структурированные программы: синтаксис и семантика.
Арифметические функции, вычислимые структурированными программами
Оглавление
-
Лекция 8
1 час 5 минут
Алгоритмы: частично рекурсивные функции
Операторы суперпозиции, примитивной рекурсии и минимизации. Классы частично
рекурсивных и примитивно рекурсивных функций. Программная вычислимость
частично рекурсивных функций. Рекурсивность табличных функций, функций, определенных с помощью суммирования и произведения, кусочно заданных функций, функций нумерации n-ок и
функций, определенных совместной рекурсией
Оглавление
-
Лекция 9
1 час 22 минуты
Алгоритмы: машины Тьюринга
Определение машин Тьюринга и класса вычислимых ими функций. Примеры работы машин Тьюринга.
Тьюрингово программирование: последовательная и параллельная композиция, ветвление
(условный оператор), повторение (оператор цикла)
Оглавление
-
Лекция 10
1 час 31 минута
Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы
Частично рекурсивные функции вычислимы на м.Т. М.Т. моделируют структурированные программы.
Классы частично рекурсивных функций,
функций, вычислимых структурированными программами, и функций, вычислимых
машинами Тьюринга, совпадают. Тезис Тьюринга-Черча. Алгоритмически разрешимые и неразрешимые
проблемы. Неразрешимость проблем самоприменимости, останова, тотальности, эквивалентности
и оптимизации текста программ
Оглавление
-