Главная  Терминология Хоора 

[ 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

терминология Хоора

В последние годы программирование для вычислительных машин стало не только средством, владение которым оказывается, решающим для успешной работы во многих прикладных областях, а. также и предметом научного изучения. Из ремесла программирование превратилось в академическую дисциплину. Первые крупные шаги в этом направлении были сделаны в работах Э. Дейкстры и К. Хоора. Заметки по структурному программированию Дейкстры *) определили новый взгляд на программирование как на предмет научного изучения и поле для интеллектуальной деятельности; этот подход получил название революции в программировании. Б статье Аксиоматическая основа программирования для вычислительных машин **) Хоор продемонстрировал, что программы поддаются точному анализу, основанному на математических рассуждениях. В этих работах убедительно показано, что можно избежать многих ошибок программирования, если программисты со знанием дела будут применять те методы и приемы, которые они ранее использовали интуитивно и часто неосознанно. Основное внимание в них уделено построению и анализу программ, или, более конкретно, структуре алгоритмов, представленных текстами программ. Причем совершенно ясно, что систематический и научный подход к построению программ важен в первую очередь в случае больших программ со сложными данными. Таким образом, методы программирования включают также и все варианты структурирования данных. Программы представляют собой в конечном счете конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. Важный вклад в упорядочение широкого, разнообразия терминов и концепций, отно-оящихся к структурам данных, был сделан Хоором в статье О структурной организации данных ***). Стало ясно, что решения о структурировании данных нельзя принимать без

*) В книге: О. Дал, Э. Дейкстра, К- Хоор, Структурное программи-Р.ованне: Пер. с аигл.-М.: Мир, 1975.

♦*) В Comm, ACM, 12. № 10 (1969). 576-583. ***) В книге Структурное программирование см. сноску выше.



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

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

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

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

*) См. пе] *) N. Wir

первую сноску на предыдущей странице.

Wirth, The Programming Language Pascal, Acta Informatlca, 1, No. 1 (1971), 35-63.



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

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

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

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




[ 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133