Автор: Михаил Дехтярь | Тверской государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
14:18:00
Студентов:
1250
Выпускников:
40
Качество курса:
5.00 | 5.00
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР). Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков. Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Специальности: Программист, Математик
ISBN: 978-5-94774-714-0
 

План занятий

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