Теория автоматов

Бакалавриат 2025/2026

Статус: Курс обязательный (Компьютерные технологии, системы и сети)

Кто читает: Департамент информатики

Где читается: Школа информатики, физики и технологий

Когда читается: 2-й курс, 1, 2 модуль

Охват аудитории: для своего кампуса

Преподаватели: Вересова Алина Максимовна, Овчинников Андрей Анатольевич

Язык: русский

Кредиты: 5

Контактные часы: 60

Дополнительные материалы в LMS Задать вопрос

Аннотация

Содержание дисциплины охватывает круг вопросов, связанных с формальными моделями, составляющими основной аппарат информатики: булева алгебра, конечные автоматы, формальные языки, машины Тьюринга, классическая и темпоральная логика и др.

Цель освоения дисциплины

изучение основных методов проектирования цифровых дискретных автоматов, обеспечивающих контроль и управление как узлами вычислительных машин, так и других устройств и комплексов специального назначения, систематизированное представление о формальных моделях грамматик и их прикладных аспектах, использование синтаксически управляемых определений и автоматных моделей при разработке программного обеспечения.

Планируемые результаты обучения

формулировать математические методы описания автоматов; современные методы проектирования цифровых устройств; современное состояние, тенденции развития и области применения дискретных автоматов
использовать программные инструментальные средства для проектирования автоматов
проектировать цифровые автоматы различного назначения
выполнять описания формальных языков и их отдельных конструкций в виде формальных моделей грамматик
выполнять простейшие операции преобразования контекстно-свободных грамматик и построения на их основе детерминированных распознавателей контекстно-свободных языков

Содержание учебной дисциплины

Раздел 1. Модели цифровых автоматов
Раздел 2. Регулярные выражения. Регулярные языки

Элементы контроля

In-class assignment
Контрольную работу студенты выполняют в рамках практических занятий. На выполнение контрольной работы студенту отводится 2 академических часа.
Homework
Домашнее задание студенты выполняют индивидуально в рамках самостоятельной работы без подключения преподавателя, с последующей проверкой результатов преподавателем или учебным ассистентом (асинхронный элемент контроля). Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленный в письменном отчет, содержащий схему, описание и примеры спроектированного автомата.
Экзамен
Экзамен проводится в письменной форме в виде теста из 10 заданий разного типа во время контактной работы в соответствии с расписанием в присутствии преподавателя (синхронный элемент контроля). Продолжительность – 2 часа.

Промежуточная аттестация

2025/2026 2nd module
0.3 * Homework + 0.4 * In-class assignment + 0.3 * Экзамен

Список литературы

Авторы

Любавина Светлана Вячеславовна
Овчинников Андрей Анатольевич

Программа дисциплины