А.П. Ершов и графы в программировании

Касьянов Виктор Николаевич

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

Академик Андрей Петрович Ершов, основатель сибирской школы информатики и программирования, говорил, что программирование — это новый вид универсальной деятельности, при которой человек должен вложить в ЭВМ все, что видит, слышит, знает, и научить ее всему, что делает сам. Важнейшим свойством информационной модели или управляющей системы является ее структура, или говоря математическим языком, совокупность бинарных отношений на наборах элементарных единиц данных и действий. Эти структуры данных и структуры действий являются единственными ипостасями программ и обрабатываемой ими информации, в которых они могут существовать в воображении программиста во чреве компьютера. Вот почему, утверждал Ершов, графы являются основной конструкцией для программиста. Он считал, что графы обладают огромной, неисчерпаемой изобразительной силой, соразмерной масштабу задачи программирования, и говорил, что программисту о графах нужно много знать, при этом с большим запасом по отношению к любой конкретной задаче.

Андрей Петрович был основоположником применения графов в программировании. Среди первых работ, существенно использующих теоретико–графовые методы в решении задач программирования, были классические работы А.П. Ершова по организации вычисления арифметических выражений (1958), оптимальному использованию оперативной памяти (1962) и перенесению теории схем Янова на язык графов (1968). Первой книгой, посвященной применению графов в программировании, была монография А.П. Ершова «Введение в теоретическое программирование (беседы о методе)» (1977). В ней Ершовым рассмотрены две классические задачи теоретического программирования, решения которых и развитые на этих решениях методы привели к созданию теоретического программирования как самостоятельной математической дисциплины. Это - задача экономии памяти в операторных схемах Лаврова и задача построения полной системы преобразований в схемах Янова.

Об авторе: Завлаб Лаборатории конструирования и оптимизации программ ИСИ СО РАН им. А.П.Ершова, kvn@iis.nsk.su
Материалы международной конференции SORUCOM 2006 (3—7 июля 2006 года)
Статья помещена в музей 18.07.2008 с разрешения автора