Компьютерные науки

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

Программа для начального погружения в дискретные структуры. Включает работу с упорядоченными бинарными диаграммами решений, детерминированными автоматами, логическими схемами и теорией алгоритмов.
Студентов 1143 Выпускников 14 Для профессионалов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Эта учебная программа посвящена фундаментальным понятиям информатики через дискретные структуры. В рамках обучения рассматриваются способы представления булевых функций с помощью логических схем и бинарных диаграмм решений. В разделе теории конечных автоматов изучаются преобразователи, распознаватели, регулярные языки и детерминизация. Изложение строится на последовательном разборе трех крупных блоков, включая введение в теорию алгоритмов и анализ машин Тьюринга. Изучение сопровождается проверочными заданиями.
Цели
  • Сформировать представление об основных дискретных структурах и формальных моделях вычислений.
  • Раскрыть основы теории конечных автоматов и регулярных языков.
  • Дать базовые знания по теории алгоритмов и алгоритмической разрешимости.
Чему я научусь?
  • Анализировать представления булевых функций с помощью логических схем.
  • Работать с конечными автоматами, регулярными выражениями и автоматными языками.
  • Применять концепции частично рекурсивных функций и машин Тьюринга к алгоритмическим задачам.

Авторы

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

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Предварительные сведения Класс
2 Реализация булевых функций с помощью логических схем Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические... Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические схемы и линейные программы. Примеры логических схем: сложение по модулю 2 и двоичный сумматор ещё
Реализация булевых функций с помощью логических схем тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
3 Упорядоченные бинарные диаграммы решений (УБДР) Бинарные деревья решений и их превращение в упорядоченные бинарные диаграммы решений (УБДР). Сокращенные УБДР и их... Бинарные деревья решений и их превращение в упорядоченные бинарные диаграммы решений (УБДР). Сокращенные УБДР и их построение по произвольным УБДР, алгоритм СОКРАЩЕНИЕ-УБДР. Построение сокращенных УБДР по формулам ещё
Упорядоченные бинарные диаграммы решений (УБДР) тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
4 Конечные автоматы: преобразователи и распознаватели Конечные автоматы-преобразователи. Пример: сложение двоичных чисел. Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство правильности автомата. Произведение автоматов. Замкнутость... Конечные автоматы-преобразователи. Пример: сложение двоичных чисел. Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство правильности автомата. Произведение автоматов. Замкнутость класса конечно-автоматных языков относительно теоретико-множественных операций ещё
Конечные автоматы: преобразователи и распознаватели тест для курса Введение в схемы, автоматы и алгоритмы 40 мин
5 Регулярные языки и конечные автоматы Операции конкатенации и итерации языков. Регулярные выражения и языки. Примеры регулярных выражений и языков. Построение конечного... Операции конкатенации и итерации языков. Регулярные выражения и языки. Примеры регулярных выражений и языков. Построение конечного автомата по регулярному выражению ещё
Регулярные языки и конечные автоматы тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
6 Свойства замкнутости класса автоматных языков. Неавтоматные языки Построение конечного автомата для гомоморфного образа автоматного языка и для обращения гомоморфизма. Теорема о разрастании для... Построение конечного автомата для гомоморфного образа автоматного языка и для обращения гомоморфизма. Теорема о разрастании для автоматных языков. Ее применение для доказательства неавтоматности языка.Примеры неавтоматных языков ещё
Свойства замкнутости класса автоматных языков. Неавтоматные языки тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
7 Алгоритмы: структурированные программы Алгоритмы и модели вычислений. Структурированные программы: синтаксис и семантика. Арифметические функции, вычислимые структурированными программами
Алгоритмы: структурированные программы тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
8 Алгоритмы: частично рекурсивные функции Операторы суперпозиции, примитивной рекурсии и минимизации. Классы частично рекурсивных и примитивно рекурсивных функций. Программная вычислимость частично... Операторы суперпозиции, примитивной рекурсии и минимизации. Классы частично рекурсивных и примитивно рекурсивных функций. Программная вычислимость частично рекурсивных функций. Рекурсивность табличных функций, функций, определенных с помощью суммирования и произведения, кусочно заданных функций, функций нумерации n-ок и функций, определенных совместной рекурсией ещё
Алгоритмы: частично рекурсивные функции тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
9 Алгоритмы: машины Тьюринга Определение машин Тьюринга и класса вычислимых ими функций. Примеры работы машин Тьюринга. Тьюрингово программирование: последовательная и... Определение машин Тьюринга и класса вычислимых ими функций. Примеры работы машин Тьюринга. Тьюрингово программирование: последовательная и параллельная композиция, ветвление (условный оператор), повторение (оператор цикла) ещё
Алгоритмы: машины Тьюринга тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
10 Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы Частично рекурсивные функции вычислимы на м.Т. М.Т. моделируют структурированные программы. Классы частично рекурсивных функций, функций, вычислимых... Частично рекурсивные функции вычислимы на м.Т. М.Т. моделируют структурированные программы. Классы частично рекурсивных функций, функций, вычислимых структурированными программами, и функций, вычислимых машинами Тьюринга, совпадают. Тезис Тьюринга-Черча. Алгоритмически разрешимые и неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова, тотальности, эквивалентности и оптимизации текста программ ещё
Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы тест для курса Введение в схемы, автоматы и алгоритмы 30 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^