Математическая энциклопедия - программирование теоретическое

математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т. сформировалось преимущественно на основе двух моделей вычислений: последовательных программ с памятью, или операторных программ, и рекурсивных программ. Обе модели строятся над нек-рой абстрактной алгебраич. системой <D, Ф, П>, образованной предметной областью D, конечным набором (сигнатурой) функциональных Ф={j1, . . ., j т} и предикатных П= {p1 ,. . ., pn} символов с заданным для каждого символа числом его аргументов (арностью).

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

Схема программы с памятью, называемая также алголоподобной, или операторной, схемой, задается в виде конечного ориентированного графа переходов, имеющего обычно одну входную и одну выходную вершины, вершины с одной (преобразователи) и двумя (распознаватели) исходящими дугами. С помощью символов сигнатуры и счетного множества символов переменных и констант обычным образом строится множество функциональных и предикатных термов. Каждому распознавателю сопоставляется нек-рый предикатный терм, а преобразователю оператор присваивания, имеющий вид y:=t, где у - символ переменной, а t функциональный терм. Конечная совокупность всех переменных в схеме образует ее память. Интерпретация в дополнение к конкретизации базовых операций предписывает каждой переменной область ее изменения, а каждой константе ее значение. Для программ с памятью наиболее обычна т.