Полный текст работы© 2007 А.П.Лукьянова
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
В настоящее время наблюдается некоторый разрыв между теоретическими основами информатики и практическим программированием. Одна из главных причин такого положения дел заключается, видимо, в том, что абстрактные модели, определяемые и исследуемые в теоретической информатике, имеют слишком высокий уровень абстракции и слишком далеки от современного практического программирования.
В работе сделана попытка определить такую модель вычислимости, которая была бы, с одной стороны, достаточно близка к практическому программированию для того, чтобы на ее основе делать практически значимые выводы, а, с другой - была бы достаточно формализована для того, чтобы к ней были применимы математические методы анализа.
Ограничившись императивным программированием, автор исследует возможности формализации различных его парадигм. Для конкретного рассмотрения предлагается три парадигмы: процедурное программирование, автоматное программирование, и объектно-ориентированное.
Исследуется вопрос, возможен ли переход из одной парадигмы в другую с сохранением сущностных характеристик, а если он возможен, то чего стоит такой переход с вычислительной точки зрения. Выделена определенная сущностная характеристика программы (ее поведение) и исследована возможность преобразования программ различных парадигм программирования с сохранением этой характеристики. Для всех предложенных преобразований приведены оценки их вычислительной и емкостной сложности и количественные оценки результата (размер полученной программы). Для каждого типа предложенных преобразований описано формальное доказательство сохранности выбранной характеристики.
Приведено сравнение метода и результатов работы с результатами и методами аналогичных исследований.