Инспектор
Вы можете этот курс.
Введение в схемы, автоматы и алгоритмы
: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР).
Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков.
Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ.
Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Цель: Ознакомить студентов с базовыми понятиями и методами решения типовых задач в таких разделах дискретной математики и теоретической информатики как представление булевых функций с помощью схем и диаграмм, теория конечных автоматов и теория алгоритмов, выработать у них навыки алгоритмического мышления, характерного для этих дисциплин.
Необходимые знания: Для изучения курса желательно предварительное знакомство с материалами курса "Основы дискретной математики".
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 11 час 27 минут | Предварительные сведения
Класс mathcal{P}_n булевых функций от n переменных. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой и 2-х
переменных. Булевы (логические) формулы и их
эквивалентность. Основные эквивалентности ( законы логики ).
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ).
Графы. Деревья.
Оглавление | - |
Лекция 240 минут | Реализация булевых функций с помощью логических схем
Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические схемы и линейные программы. Примеры логических схем: сложение по модулю 2 и двоичный сумматор
Оглавление | - |
Тест 118 минут | - | |
Лекция 347 минут | Упорядоченные бинарные диаграммы решений (УБДР)
Бинарные деревья решений и их превращение в упорядоченные бинарные
диаграммы решений (УБДР). Сокращенные УБДР и их построение по произвольным
УБДР, алгоритм СОКРАЩЕНИЕ-УБДР. Построение сокращенных УБДР по формулам
Оглавление | - |
Тест 218 минут | - | |
Лекция 41 час 49 минут | Конечные автоматы: преобразователи и распознаватели
Конечные автоматы-преобразователи. Пример: сложение двоичных чисел.
Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство
правильности автомата. Произведение автоматов. Замкнутость класса конечно-автоматных языков
относительно теоретико-множественных операций
Оглавление | - |
Тест 324 минуты | - | |
Лекция 549 минут | Регулярные языки и конечные автоматы
Операции конкатенации и итерации языков. Регулярные выражения и языки. Примеры регулярных выражений и языков. Построение конечного автомата по регулярному выражению
Оглавление | - |
Тест 418 минут | - | |
Лекция 61 час 18 минут | Свойства замкнутости класса автоматных языков. Неавтоматные языки
Построение конечного автомата для гомоморфного образа автоматного языка и для обращения гомоморфизма.
Теорема о разрастании для автоматных языков.
Ее применение для доказательства неавтоматности языка.Примеры неавтоматных языков
Оглавление | - |
Тест 518 минут | - | |
Лекция 742 минуты | Алгоритмы: структурированные программы
Алгоритмы и модели вычислений. Структурированные программы: синтаксис и семантика.
Арифметические функции, вычислимые структурированными программами
Оглавление | - |
Тест 618 минут | - | |
Лекция 81 час 5 минут | Алгоритмы: частично рекурсивные функции
Операторы суперпозиции, примитивной рекурсии и минимизации. Классы частично
рекурсивных и примитивно рекурсивных функций. Программная вычислимость
частично рекурсивных функций. Рекурсивность табличных функций, функций, определенных с помощью суммирования и произведения, кусочно заданных функций, функций нумерации n-ок и
функций, определенных совместной рекурсией
Оглавление | - |
Тест 718 минут | - | |
Лекция 91 час 22 минуты | Алгоритмы: машины Тьюринга
Определение машин Тьюринга и класса вычислимых ими функций. Примеры работы машин Тьюринга.
Тьюрингово программирование: последовательная и параллельная композиция, ветвление
(условный оператор), повторение (оператор цикла)
Оглавление | - |
Тест 818 минут | - | |
Лекция 101 час 31 минута | Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы
Частично рекурсивные функции вычислимы на м.Т. М.Т. моделируют структурированные программы.
Классы частично рекурсивных функций,
функций, вычислимых структурированными программами, и функций, вычислимых
машинами Тьюринга, совпадают. Тезис Тьюринга-Черча. Алгоритмически разрешимые и неразрешимые
проблемы. Неразрешимость проблем самоприменимости, останова, тотальности, эквивалентности
и оптимизации текста программ
Оглавление | - |
Тест 918 минут | - | |
5 часов | - |