Восходящее и нисходящее программирование

Фактически, мы определили бесконечное число языков блок-схем, различающихся наборами конкретных базовых операторов и предикатов.

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

Восходящее программирование – от средств к цели. Отталкиваясь от данного языка определений строить все более крупные блоки, то есть подниматься вверх по уровням языков программ.

Нисходящее программирование – от цели к средствам. В этом случае начиная от цели (спецификации задачи на каком-то языке высокого уровня) мы спускаемся вниз по уровням языков ко все более мелким деталям конечной программы.

Сначала, восходящее программирование кажется более естественным. Начинающие программисты обычно пишут операторы программы в порядке вычисления их компьютером.

Но восходящее программирование – скорее тактика, пригодная лишь для небольших задач. Главная стратегия при решении сложных задач – нисходящее проектирование. Фактически, нисходящее программирование не зависит от конкретного языка программирования.

Простой пример.

Сначала определи (итерацией) главную (последнюю в смысле вычисления) функцию S b_i, выделяя задачу вычисления b_i =P a_ij в качестве отдельной подзадачи.

Итак, идея нисходящего программирования:

Начинай со спецификации – изложи то, что нужно хоть на каком-нибудь (достаточно) точном языке.

Далее, придумывай все более ограниченные языки спецификаций с тем, чтобы решение задачи, поставленной на языке L₂, сформулированное в терминах языка L_i+1 было достаточно простым, надежным, контролируемым.

Программа обычно считается сложной, если содержит более 2-х, 3-х циклов. Однако надежно отслеживать можно только один цикл.

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

Пример с чуть менее очевидной спецификацией.

Дана последовательность положительных чисел a₁, …, a_n; a_i>0, a_n=0.

Ступенькой назовем произвольную возрастающую подпоследовательность a_i, …, a_i+k. Найти длину наибольшей ступени.

Спецификация. Max(l_k), где l_k - (подзадача вычисления) длины очередной ступеньки. Путаница здесь возникает из-за того, что функции привычнее обозначать существительными. Но длин много, наибольшая – одна (однозначность функции).

Дата добавления: 2014-01-07