Нормальные алгоритмы маркова

Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.

Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

Например, в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.

Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Последовательность слов Р, P₁, Р₂, ..., М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.

Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.

Пример

Алфавит Подстановки

{а, b, с, d, е} ас - сa, abac - abace

ad - da; eca - ae

bc - cb; eda - be

bd - db; edb - be

Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.

Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подстановки являются ориентированными: N → М (стрелка означает, что подстановку разрешается производить лишь слева направо). Для каждого ассоциативного исчисления существует задача: для любых двух слов определить, являются ли они эквивалентными или нет.

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

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

Пример

Алфавит: Система подстановок В:

А = {а, b, с} cb - cc

сса - аb

ab – bса

Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.

Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bсaсаbс получаем:

babaac → bbcaaac → остановка

bcacabc → bcacbcac → bcacccac → bсасаbс → бесконечные процесс (остановки нет), так как мы получили исходное слово.

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

Такой набор предписаний вместе с алфавитом А и набором подстановок В определяют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.

Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел (представленных наборами единиц).

Пример

Алфавит: Система подстановок В:

А = (+, 1) 1 + → + 1

+ 1 → 1

1 → 1

Слово Р: 11+11+111

Последовательная переработка слова Р с помощью нормального алгоритма Маркова проходит через следующие этапы:

Р = 11 + 11 + 111 Р₅ = + 1 + 111111

Р₁ = 1 + 111 + 111 Р₆ = ++ 1111111

Р₂ = + 1111 + 111 Р₇ = + 1111111

Р₃ = + 111 + 1111 Р₈ = 1111111

Р₄ = + 11 + 11111 Р₉ = 1111111

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А,

Разъясним последнее утверждение. В некоторых случаях не удается построить нормальный алгоритм, эквивалентный данному в алфавите А, если использовать в подстановках алгоритма только буквы этого алфавита. Однако, можно построить требуемый нормальный алгоритм, производя расширение алфавита А (добавляя к нему некоторое число новых букв). В этом случае говорят, что построенный алгоритм является алгоритмом над алфавитом А, хотя он будет применяться лишь к словам в исходном алфавите A.

Если алгоритм N задан в некотором расширении алфавита А, то говорят, что N есть нормальный алгоритм над алфавитом А.

Условимся называть тот или иной алгоритм нормализуемым, если можно построить эквивалентный ему нормальный алгоритм, и ненормализуемым в противном случае. Принцип нормализации теперь может быть высказан в видоизмененной форме: все алгоритмы нормализуемы.

| Данный принцип не может быть строго доказан, поскольку понятие произвольного алгоритма не является строго определенным и основывается на том, что все Известные в настоящее время алгоритмы являются нормализуемыми, а способы ромпозиции алгоритмов, позволяющие строить новые алгоритмы из уже известных, не выводят за пределы класса нормализуемых алгоритмов. Ниже перечислены способы композиции нормальных алгоритмов.

I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р)),

II. Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и В(р).

III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е - пустая строка.

IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.

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

РЕКУРСИВНЫЕ ФУНКЦИИ

Еще одним подходом к проблеме формализации понятия алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в математических исследованиях, посвященных алгоритмам, он имеет наибольшее распространение.

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

Введем несколько основных понятий. Пусть X, Y - два множества. Частичной функцией (или отображением) из Х в Y будем называть пару <D(f), f>, состоящую из подмножества D(f) Ì X (называемого областью определения f) и отображения f: D(f) ® Y. Если D(f) пусто, то f нигде не определена. Будем считать, что существует единственная нигде не определенная частичная функция.

Через N будем обозначать множество натуральных чисел. Через (N)ⁿ (при п ³ 1) будем обозначать n-кратное декартово произведение N на себя, т.е. множество упорядоченных n-ок (х₁ ..., x_n), х_i Ì N. Основным объектом дальнейших построений будут частичные функции из (N)^m в (N)ⁿ для различных т и п.

Частичная функция f из (N)^m в (N)ⁿ называется вычислимой, если можно указать такой алгоритм («программу»), который для входного набора х Ì (N)^m дает на выходе f(x), если х Ì D(f) и нуль, если х Ë D(f). В этом определении неформальное понятие алгоритма (программы) оказывается связанным (отождествленным) с понятием вычислимости функции. Вместо алгоритмов далее будут изучаться свойства вычислимых функций. Вместо вычислимых функций оказывается необходимым использовать более широкий класс функций (и более слабое определение) - полувычислимые функции. Частичная функция из (N)" в (N)" полувычислима, если можно указать такой алгоритм (программу), который для входного набора х с (N)" дает на выходе х е D(f), или алгоритм работает неопределенно долго, если х е D(f). Очевидно, что вычислимые функции полувычислимы, а всюду определенные полувычислимые функции вычислимы.

Частичная функция f называется невычислимой, если она не является ни вычислимой, ни полувычислимой.

Из вновь введенных понятий основным является полувычислимость, так как вычислимость сводится к нему. Существуют как невычислимые функции, так и функции, являющиеся полувычислимыми, но не вычислимые. Пример такой функции:

Можно показать, что существует такой многочлен с целыми коэффициентами P(t, x₁,...,x_n), что g(t) - невычислима. Однако, легко видеть, что g(t) - полувычислима.

Фундаментальным открытием теории вычислимости явился, так называемый, тезис Черча, который в слабейшей форме имеет следующий вид: можно явно указать а) семейство простейших полувычислимых функций; б) семейство элементарных операций, которые позволяют строить по одним полувычислимым функциям другие полувычислимые функции с тем свойством, что любая полувычислимая функция получается за конечное число шагов, каждый из которых состоит в применении одной из элементарных операций к ранее построенным или к простейшим функциям.

Простейшие функции:

suc: N ® N; suc(x) = x+1 - определение следующего за х числа;

l⁽ⁿ⁾: (N)ⁿ ® N; l⁽ⁿ⁾ (x₁,..., х_n) = 1, п ³ 0 - определение «размерности» области определения функции;

рr : (N)ⁿ® N; pr (x₁,..., х_n) = х_i, х ³ 1 - «проекция» области определения на одну из переменных.

Элементарные операции над частичными функциями:

а) композиция (или подстановка) ставит в соответствие паре функций f из (N)^m в (N)ⁿ и g из (N)ⁿ в (N)^p функцию h = g_of из (N)^m в (N)^p , которая определяется как

б) соединение ставит в соответствие частичным функциям f_i из (N)ⁿⁱ, i = 1, ..., k функцию (fi, ..., f_k) из (N)^m в (N)ⁿ¹ х... х (N)^nk, которая определяется как

в) рекурсия ставит в соответствие паре функций f из (N)ⁿ в N и g из (N)ⁿ⁺² в N функцию h из (N)ⁿ⁺² в N, которая определяется рекурсией по последнему аргументу

h(x₁,... , х_n, 1) = f (x₁,... ,x_п) (начальное условие),

h (x₁,... ,х_n, k+1) = g(x₁,... ,x_n, k, h(x₁,... ,х_n, k)) при k³ 1 (рекурсивный шаг).

Область определения D(h) описывается также рекурсивно:

г) операция т, которая ставит в соответствие частичной функции f из (N)ⁿ⁺¹ в N частичную функцию h из (N)ⁿ в N, которая определяется как

Операция т позволяет вводить в вычисления перебор объектов для отыскания нужного в бесконечном семействе.

Теперь, когда введены простейшие функции и элементарные операции, можно дать следующие основные определения:

а) последовательность частичных функций fi, . . . ,f_N называют частично рекурсивным (соответственно примитивно рекурсивным) описанием функции f_N = f, если fi - одна из простейших функций; f_i для всех i ³ 2 либо является простейшей функцией, либо получается применением одной из элементарных операций к некоторым из функций fi,..., f_i-1 (соответственно одной из элементарных операций, кроме т);

б) функция f называется частично рекурсивной (соответственно примитивно рекурсивной), если она допускает частично рекурсивное (соответственно примитивно рекурсивное) описание.

Теперь можно привести тезис Черча в обычной форме:

а) функция f полувычислима, если и только если она частично рекурсивна;

б) функция f вычислима, если и только если рекурсивны f и характеристическая функция X_D(f).

Характеристическая функция подмножества Х в Y(X Ì Y) есть такая функция, что

Тезис Черча может использоваться как определение алгоритмической неразрешимости.

Пусть имеется счетная последовательность «задач» P₁, P₂, ..., которые имеют ответ «да» или «нет». Такая последовательность носит название «массовой проблемы». Свяжем с ней функцию f из N в N:

Массовая проблема Р называется алгоритмически разрешимой, если функции f и X_D(f) частично рекурсивны. В противном случае Р называется алгоритмически неразрешимой.

Контрольные вопросы и задания

1. Для чего необходимо формализовать понятие алгоритма?

2. Что означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?

3. Для чего предназначены машины Поста и Тьюринга?

4. Как «устроена» машина Поста?

5. Перечислите и запишите команды машины Поста.

6. С помощью бумаги, карандаша и стиральной резинки «исполните» вместо машины Поста программы сложения чисел из текста.

7. Составьте (и проверьте) программу для машины Поста, создающую на ленте копию заданной последовательности меток справа от нее.

8. Пользуясь предыдущей программой, составьте программу умножения чисел для машины Поста.

9. Как «устроена» машина Тьюринга?

10. Каков принцип исполнения программы машиной Тьюринга?

11. Сравните машины Поста и Тьюринга. Укажите различия.

12. Выполните вместо машины Тьюринга примеры программ из текста.

13. Каким образом могут быть обобщена машина Тьюринга?

14. Что такое ассоциативное исчисление?

15. Постройте дедуктивную цепочку от слова «мука» к слову «торт», заменяя каждый раз по одной букве так, чтобы каждый раз получалось слово.

16. Дайте определение нормального алгоритма Маркова.

17. В чем состоит принцип нормализации алгоритмов?

18. Охарактеризуйте способы композиции нормальных алгоритмов.

19. Как алгоритм может быть связан с рекурсивной функцией?

20. Дайте определения частичной, полувычислимой и вычислимой функции.

21. В чем состоит тезис Черча в слабейшей и в обычной формах?

22. Перечислите простейшие функции.

23. Перечислите элементарные операции.

24. Чем отличается рекурсивная функция от примитивно-рекурсивной?

25. Дайте определение частично-рекурсивной функции.

26. Что называется массовой проблемой? Что означает алгоритмическая разрешимость массовой проблемы?

§ 8. ПРИНЦИПЫ РАЗРАБОТКИ АЛГОРИТМОВ
И ПРОГРАММ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ

ОПЕРАЦИОНАЛЬНЫЙ ПОДХОД

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

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

1) минимальные требования в отношении оперативной памяти компьютера -.программа должна была использовать наименьшее возможное число ячеек оперативной памяти компьютера;

2) минимальное время исполнения (минимальное число операций). При этом программы составлялись из команд, непосредственно или почти непосредственно исполнявшихся компьютером (точнее говоря, процессором):

• операции присваивания;

• простейших арифметических операций;

• операций сравнения чисел;

• операторов безусловного и условных переходов (изменяющих порядок вычисления команд в программе);

• операторов вызова подпрограмм (вспомогательных алгоритмов).

Такой подход в программировании (создании алгоритмов), ориентированный на непосредственно выполняемые компьютером операции, можно назвать операциональным.

Рассмотрим подробнее операции, которые выполняются компьютером и которые являются шагами программы при операциональном подходе.

Операция присваивания состоит в том, что некоторое значение фигурирующей в программе величины помещается в ячейку памяти компьютера. Эта ячейка может либо принадлежать оперативной памяти, либо находиться в арифметико-логическом устройстве, выполняющем основные операции (это устройство - часть процессора). После операции присваивания указанное значение сохраняется в ячейке памяти, куда оно было помещено, пока не будет заменено другим в результате другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается именем (идентификатором) соответствующей переменной. Примеры идентификаторов: а, х, у₁, у₂. Важно помнить, что переменные и, соответственно, их значения могут быть разных типов - числовые (целые или действительные), литерные или логические. Значения различных типов представляются (кодируются) в компьютере по-разному, поэтому они должны соответствовать типам переменных, которым они присваиваются. При разработке алгоритма следует всегда помнить и 'тщательно различать типы переменных.

Набор простейших арифметических операций «сложения» (+), «вычитания» (-), «умножения» (*) и «деления» (/) (причем во многих случаях следует тщательно отличать деление, выполняемое над целыми числами - в этом случае операция деления распадается на деление нацело и вычисление остатка от деления) позволяет записывать арифметические выражения с использованием числовых констант и идентификаторов переменных. Для определения порядка операций в выражениях чаще всего используют стандартное математическое соглашение о старшинстве операции, согласно которому старшими и выполняемыми в 1-ю очередь являются умножение и деление, а младшими - сложение и вычитание. Для изменения «естественного» порядка выполняемых операций служат скобки. Сравните, например, порядок операций в выражениях:

(а + 2) * х и а + 2 * х.

Что же касается порядка выполнения операций одного старшинства, то они, как правило, выполняются в порядке записи в выражении.

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

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

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

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

n = 0,1,2,...

Можно показать, что .

Будем обозначать через x₀ нулевое приближение (за него в данном случае можно принять любое положительное число), через e заданную точность вычислений и через c₀ какое-нибудь число, удовлетворяющее условию 0 < c₀ < , необходимое для оценки достигнутой точности с помощью неравенства

Алгоритм вычисления .

1) ввести числа а, e, x₀, c₀;

2) присвоить переменной х значение у,

3) присвоить переменной у значение а/х;

4) присвоить переменной у значение х + у,

5) присвоить переменной х значение у/2;

6) присвоить переменной у значение x²;

7) присвоить переменной у значение y-а;

8) присвоить переменной у значение у/c₀;

9) присвоить переменной d значение у/2;

10) сравнить d и e; если d > e, то перейти к команде 3, иначе перейти к следующей команде;

11) вывести числа х, а и e;

12) стоп.

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

Поясним эту программу. Команда 2 помещает значение начального приближения x₀ в ячейку памяти, в которой хранятся значения переменной х (на каждом этапе вычислений в этой ячейке хранится значение х, равное значению одного из членов рекуррентной последовательности x_n).

Команды 3-5 вычисляют по числу х число (х + а/х)/2. Результат помещается в ячейку памяти, в которой хранится значение переменной х, при этом старое значение «стирается» новым. Команды 6-9 вычисляют величину

,

с помощью которой оценивается сверху разность х - . Важное значение имеет команда 10. По ней не производятся вычисления, а сравниваются между собой вычисленное значение 5 и заданная точность e. Если d > e, то управляющее устройство вернет вычислительный процесс к команде 3 и заставит повторить процесс.

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

Данный алгоритм весьма экономичен: в качестве рабочих он использует всего две ячейки памяти (для переменных х и у), его команды так продуманы, что никакие операции не выполняются с избыточным повторением.

В данном примере не были использованы какие-либо специальные обозначения команд, чтобы сделать их независимыми от языка конкретных ЭВМ (такие языки называют Ассемблерами), чтобы стал ясен общий характер операционального подхода к разработке алгоритмов. Однако, ориентированность этого подхода на возможности и особенности ЭВМ с появлением большого числа компьютеров 3-го и особенно 4-го поколений не позволяла перейти к массовому промышленному программированию и стала сдерживать развитие вычислительной техники. Отметим основные недостатки алгоритмов, к которым приводил операциональный подход:

• злоупотребление командой условного и безусловного переходов зачастую приводило к очень запутанной структуре программы, напоминавшей по образному сравнению «блюдо спагетти»;

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

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

СТРУКТУРНЫЙ ПОДХОД

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

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

Следование - самая важная из структур. Она означает, что действия могут быть выполнены друг за другом, рис. 1.19:

Рис. 1.19. Структура «следование»

Эти прямоугольники могут представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных.

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

Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

Рис. 1.20. Структура «ветвление»

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

Рис. 1.21. Структура «неполное ветвление»

Цикл (или повторение) предусматривает повторное выполнение некоторого Набора команд программы. Если бы циклы не существовали, вряд ли занятие программированием было бы оправданным: циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд. Разновидности цикла изображены на рис. 1.22 и рис. 1.23.

Цикл начинается с проверки логического выражения. Если оно истинно, то выполняется «a», затем все повторяется снова, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, выполнение операций «а» прекращается и управление передается по программе дальше.

Рис. 1.22. Структура цикла «пока»

Рис. 1.23. Структура цикла «до»

Рис. 1.24. Нахождение суммы трех чисел

Рис. 1.25. Нахождение наибольшего из трех чисел

Эти структуры можно комбинировать одну с другой - как путем организации их следований, так и путем создания суперпозиций (вложений одной структуры в другую) - сколь угодно разнообразно для выражения логики алгоритма решения любой задачи. Используя описанные структуры, можно полностью исключить использование каких-либо еще операторов условного и безусловного перехода, что является важным признаком структурного программирования. Направление выполнения команд часто изображают сверху вниз. На рис. 1.24 - 1.26 приведены простейшие примеры структурной реализации алгоритмов работы с величинами.

Рис. 1.26. Нахождение суммы 100 чисел

Умение образовывать из базовых структур их суперпозиции в соответствии с условиями конкретной задачи - одно из важнейших в программировании. Допустим, надо ввести в память компьютера 100 чисел и по дороге отсуммировать те из них, которые положительны. Ясно, что ввод - операция циклическая, а внутри этого цикла находится развилка, в которой проверяется знак числа и производится суммирование. Схематически соответствующая суперпозиция изображена на рис. 1.27.

Так как выражение, управляющее циклом, проверяется в самом начале, то в случае, если условие сразу окажется ложным, операторы циклической части «a» могут вообще не выполняться. Операторы циклической части «а» должны изменять переменную (или переменные), влияющие на значение логического выражения, иначе программа «зациклится» - будет выполняться бесконечно. Рассмотренная циклическая конструкция называется также цикл «пока», или «цикл с предусловием».

Существует и иная конструкция цикла, которая предусматривает проверку условия, по которому, наоборот, выполнение команд циклической части прекращается, после команд циклической части (см. рис. 1.23).

Рис 1.27 Алгоритм типа развилка, вложенная в цикл,
для нахождения суммы положительных чисел из 100 возможных

Схематические изображения нескольких суперпозиций базовых алгоритмических структур представлены ниже на рис. 1.28-1.31.

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

1) возможность создания программы несколькими программистами;

2) простота проектирования и последующих модификаций программы;

3) упрощение отладки программы - поиска и устранения в ней ошибок;

4) возможность использования готовых библиотек наиболее употребительных модулей.

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

Рис. 1.28. Алгоритм типа «цикл, вложенный в неполную развилку»	Рис. 1.29. Алгоритм типа «цикл в цикле»

Рис. 1.30. Алгоритм типа «развилка в развилке»	Рис. 1.31. Иллюстрация трехкратного вложения одной базовой структуры в другую

На следующем этапе эти задачи, в свою очередь, разбиваются на более мелкие подчиненные подзадачи и так далее, до уровня отн<