Skip to content

Description.md

Latest commit

 

History

History
116 lines (89 loc) · 8.3 KB

Description.md

File metadata and controls

116 lines (89 loc) · 8.3 KB
Raw

Автоматное программирование

Лекции набраны на typst; PDF собираются из исходников репозитория (см. «Описание»).

Необходимо знать

Для освоения материала курса студенту необходимы начальные знания:

  1. Дискретная математика: множества, отношения, отображения, булева алгебра;
  2. Основы теории графов: вершины, дуги, пути, достижимость;
  3. Программирование на ЯПВУ Си: указатели, структуры, массивы, раздельная компиляция;
  4. Архитектура ЭВМ: память, регистр, прерывание, такт.

Развёрнуто — § 1 лекции 1.

Цель курса

Научить проектировать управляющие программы как явные автоматные модели: строить автомат по словесной постановке задачи, превращать его в схему или в код, проверять полученную программу тестированием и верификацией. Курс построен тремя «этажами»: теория (что автомат может и чего не может), синтез (как получить автомат и его реализацию) и проверка (как убедиться, что реализация соответствует модели).

Описание

Курс читается по двенадцати лекциям; их исходники — в lectures/, реестр с номерами и названиями — в lectures/course.typ. Сборка PDF:

cmake -S . -B build && cmake --build build -j   # лекции и примеры

Вспомогательные материалы, не входящие в лекции:

  • Приложение «Система управления версиями Git» — команды, ветки, слияние, разрешение конфликтов и порядок сдачи работ. Собирается вместе с лекциями (lectures/src/a1-version-control) и лежит в комплекте курса рядом с ними.
  • Приложение «Требования к коду курса» — режим сборки (ISO C90, строгий режим компиляции), форматирование и проверки оформления, комментарии Doxygen, тесты и покрытие переходов, порядок самопроверки перед сдачей (lectures/src/a2-code-style).
  • practices/README.md — окружение сборки и состав практикума.

Порядок приема лабораторных работ

Работа сдаётся историей репозитория: ветка на работу, коммиты по ходу дела, pull request с описанием того, что сделано и чем проверено. Подробно — в приложении «Система управления версиями Git».

Что проверяется при приёме:

  1. Оформление кода: ./scripts/check-style.sh без нарушений;
  2. Сборка в Debug и в Release без единого предупреждения — строгий режим курса превращает предупреждение в ошибку;
  3. Тесты: ctest --test-dir build --output-on-failure проходит полностью;
  4. Автоматная модель: диаграмма и таблица переходов совпадают с кодом, а каждый переход таблицы пройден хотя бы одним прогоном;
  5. Описание работы в pull request'е: что сделано, чем проверено, какие отступления от требований допущены и почему.

Полный перечень требований с обоснованием — приложение «Требования к коду курса».

Лабораторные работы

Пять работ, по одной к своей лекции. Задание, варианты, порядок сдачи и критерии приёмки у каждой — отдельным документом; они собираются вместе с лекциями и лежат в комплекте курса.

№ Лекция Работа Что делается
1 3 Синтез автомата и его схемы автомат наращиванием состояний, карты Карно, канонические уравнения, схема, код с тестами
2 4 От регулярного выражения к минимальному автомату конструкция Томпсона, детерминизация подмножествами, минимизация разбиением
3 6 Распознаватель формата как конечный автомат прикладной формат таблицей переходов, тесты на границах, граница регулярности
4 10 Программа для машины Тьюринга таблица переходов, ручной прогон, реализация на интерпретаторе, оценка числа тактов
5 7 Прикладной автомат в трёх реализациях одна задача тремя способами, сверка трасс, модель установки, покрытие переходов

У каждой работы 22–30 вариантов, и каждый шаг задания имеет машинную проверку — прогон практики, тест или сверку с порождённым эталоном. Список вариантов — в самой работе; номер варианта соответствует номеру студента в журнале группы.

Задачи по машине Тьюринга, которые раньше лежали в этом файле, перенесены в приложение лекции 10 «Задачи на машину Тьюринга»: там их 22, у первых десяти есть разборы с готовыми программами-таблицами.

Курсовая работа

Тема — прикладная автоматная модель: установка изделия на конвейер, сварка, покраска, сортировка и упаковка, гибкая производственная система, управление роботом. Полный список тем — в КР_15.11.2019.txt; те же темы служат вариантами лабораторной работы 5, поэтому её удобно делать скелетом курсовой.

Образец ожидаемого объёма и оформления — сквозной проект курса practices/20-welding-line: автоматная модель задана таблицей переходов, реализация отделена от ввода-вывода, выдержки входят в модель, считается покрытие переходов и порождается модель для верификатора.

Готовые PDF

Комплект курса выкладывается релизами: архив содержит лекции, приложения и лабораторные работы под читаемыми именами. Собрать самому:

cd lectures && make        # PDF в lectures/out
cd lectures && make pack   # то же плюс архив комплекта