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

1) процесс составления программы, плана действий; 2) дисциплина, изучающая методы и приемы составления программ. С определенной долей условности П. как дисциплина делится на программирование теоретическое, изучающее математич. абстракции программ и способов их построения, системное программирование, имеющее дело с разработкой математического обеспечения ЭВМ, т. е. программных комплексов массового и длительного применения, и прикладное программирование, обслуживающее конкретные применения ЭВМ во всем их разнообразии.

Составление программы является творч. задачей, т. к. поиски способа достижения даже четко сформулированной цели в общем случае требуют выработки или привлечения нового знания. В нек-рых частных случаях возможно нахождение более систематической и формальной процедуры П. Так, если задание на П. уже сформулировано в виде алгоритма, то П. сводится к переводу с языка записи алгоритма, или алгоритмического языка, к языку, непосредственно воспринимаемому исполнителем. В нек-рых математич. моделях задача перевода, решается исчерпывающе. Напр., если задача сформулирована в виде теоремы существования

где Р( х, у) - нек-рая формула узкого исчисления предикатов, то из доказательства теоремы в конструктивной логике эффективно извлекается рекурсивное описание функции j(х), для к-рой (теорема Клини Нельсона). Поиски систематич. процедур перевода записей алгоритма в программы и извлечения программы из условия задачи и дополнительной информации составляют предмет автоматизации программирования и ее частного случая трансляции программ.

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

Нек-рое представление о способе перехода от спецификации задачи к программе дает следующий пример П. задачи возведения хв натуральную степень п.

Исходное знание: x¹=x, х ^п+т=х ^n. х ^т, х ^пт=( х ^п) ^т. Обнаруживая, что эти соотношения позволяют свести решение задачи х ⁿ к более простой (т. е. с меньшим n), пытаются придать исходному знанию простейшую форму (творч. шаг):

х ⁰=1, xⁿ⁺¹= x^n.x, x²ⁿ=(xⁿ)².

Содержательный анализ показывает, что третье соотношение эффективнее, нежели второе, но зато применимо не всегда. Второе соотношение переписывается в виде случая, дополнительного к третьему (творч. шаг):

х ⁰=1, х ^2п+1= х ^2n. х, х ²ⁿ=( х ^п)².

Используя обратимость функций 2n и n+1 и логич. несовместимость соотношений, получают рекурсивное соотношение методом разбора случаев (формальный шаг):

Остается переписать это правило на каком-либо алгоритмич. языке, напр. алгол-60 (формальный шаг):

real power(x, n); real x,integer n;

power:=if n=0 then 1 else

if even(n).then power(else x power(x, n-1). Определение процедуры проверки четности even(n).становится отдельной, более частной задачей П.

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

Лит.:[1] Любимский Э. 3., Мартынюк В. В., Трифонов Н. П., Программирование, М., 1980; [2] Дейкстра Э. В., Дисциплина программирования, пер. с англ., М., 1978; [3] Мейер Б., Бодуэн К., Методы программирования, пер. с франц., т. 1-2, М., 1982. А. П. Ершов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985