УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Автоматное решение задачи Д. Кнута о лифте

(C) 2003 г. Л.А.Наумов, А.А.Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Отсюда можно скачать полный текст документации в формате pdf (520 Kb)
Отсюда можно скачать демонстрационную программу Lift (23 Kb)
Отсюда можно скачать исходные тексты демонстрационной программы Lift (38 Kb)
Отсюда можно скачать исходные тесты ядра программы, перенесённого на микроконтроллер (10 Kb)

Аннотация

Уже около сорока лет, одним из примеров, на котором Д. Кнут обучает «Искусству программирования», является задача управления лифтом. Он на основании невнятного технического задания, используя только словесное описание алгоритмов, на многих страницах книги приводит в окончательной форме программу на языке низкого уровня, откомментированную не более внятно, чем было сформулировано задание.

В предисловии к третьему изданию «Искусства программирования» приводятся слова Б. Гейтса: «За последние двадцать лет мир изменился». Настоящая работа призвана показать справедливость этого высказывания на примере задачи управления лифтом.

В этой книге Д. Кнут, кроме математических основ программирования, пытается обучать также и искусству прикладного программирования. С этой целью он создает виртуальную машину MIX, для программирования которой он разработал язык ассемблера. Одним из самых «больших» и подробно рассмотренных примеров, демонстрирующих «искусство программирования по Кнуту», является разработка программного обеспечения для системы управления лифтом.

Из этого примера следует, что искусством программирования Д. Кнут обладает, так как настоящее искусство не предполагает обоснования процесса создания произведения. Возникает ситуация, не удовлетворявшая Э. Дейкстру, который говорил, «что программы часто приводятся в форме готовых изделий, почти без упоминания тех рассуждений, которые проводились в процессе разработки и служили обоснованием для окончательного вида завершенной программы».

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