Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 47

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 41 42 43 44 45 46 < 47 > 48 49 50 51 52 53 .. 316 >> Следующая

130
3.
Структурные переходы являются паллиативом. Они возникли из-за необходимости выразить мысль, что успех либо неудача глобального процесса может выявиться внутри одной из решаемых подзадач, и дальнейшая работа и над текуей задачей, и над всей последовательность вло еннх подзадач становится просто бессмысленной. этом случае ну ны да е не переходы, а операторы заверения. о они в распространенных языках действу т лиь на один уровень иерархии вверх, а даже теоретически этого недостаточно.15 Еще один вопрос — о совместимости структурного программирования с рекурсиями. пыт показвает, что процедура, в которой есть ее рекурсивный вызов внутри цикла, практически почти всегда неправильна, теоретически е она входит за рамки примитивной рекурсии (см. курс логики и теории алгоритмов) и, как следствие, становится практически невычислимой. Чтобы здесь не попасть впросак, соблюдайте простое правило.
Внимание!
Не используйте рекурсивный вызов процедуры внутри цикла !Рекурсия и циклы должны быть «территориальноразделены»!
Хотя данное правило пригодно в подавляющем большинстве случаев, но тем не менее иногда бывают исключения. Рассмотрим, например, схему поиска вглубь на дереве.
Программа 3.3.2
int search (ELEMENT x) ELEMENT y; int result; { if (good(x)) { return id(x)}
elsefor(int i=0; i<100; i++)
{y=get_successor(x,i); result=search(y);
if (result>0) return result;
}
return 0;
}
Здесь рекурсии вместе с циклом зада т обход дерева возмо ностей и гибельного размно ения рекурсивных взовов не происходит.
15 В связи с этим стоит помянуть добрыс словом отечественные разработки в области алгоритмических языков, в частности, язык ЯРМО [25], в котором необходимость многоуровневых средств завершения конструкций была осознана еще в начале 70-х гг.
3.3.
131
ля стиля мыления при структурном программировании характерно стремление к локальности и иерархическое разбиение задачи на подзадачи — так называемое нисходящее программирование. Нисходящее программирование часто рассматривали (и рассматрива т) как обий способ декомпозиции действий. ричины тому следуие:
• так проще, поскольку можно ограничиваться операционной моделью вычислений;
• раннее программирование — это поиск способов вычислений, т. е. наработка типовых алгоритмов, приемов и методов (рекурсия, динамическое программирование, поиск в глубину и др.);
• нисходяее построение структур данных стало появляться (оформляться явно) только тогда, когда сформировалась идея абстракции даннх;
• давление теории сложности. Задача программистской оптимизации ча-
е всего формулируется так: требуется найти минимальное по времени вчислений реение в заданных ограничениях по памяти (а иногда и без них).
оследнее сомнительно, т. к. наиболее суественными критическими участками программ очень часто явля тся алгоритм доступа к даннм, но до появления концепции абстракции данных понять это было трудно.
Невозможность при нисходящем структурном программировании увидеть то дественность процедур, работаих на разнх ветвях декомпозиции, а тем более унифицировать несколько формально различных процедур на раз-нх ветвях в одну обу , показвает необходимость дополнения подхода средствами, позволяющими "поднять" уровень понятий. Первым выражением стремления разумно обобщить понятия можно считать привлечение к разработке структурных программ подхода, получившего название восходя-его программирования. К примеру, когда строят библиотеку, занима тся обобением, а не делением какой-то задачи. Части, выделяемые в виде библиотечных средств, вбира тся исходя из их применимости в различных контекстах. Таким образом, это построение снизу вверх!
Создание глобального контекста, каковм и является восходяее построение, требует такого стиля, который ему соответствует. апример, здесь моет применяться программирование от состояний. Если разделение стилей по модулям, пакетам и другим единицам декомпозиции проведено строго, то можно избежать эклектического их смешения.
132
3.
Реальный проект — это смесь нисходящего и восходящего подходов:
• сначала сверху вниз для выяснения крупных "строительных блоков" (при любой технологии: от данных или от действий);
• затем попытка движения снизу вверх, чтобы спроецировать понятия, оформивиеся ранее, на абстрактные структур , допускаие адекватну реализаци ;
• далее проверка соответствия, углубление нисходяей декомпозиции и обобение понятий, выделенных восходяими приемами.
§ 3.4. СЕНТЕНЦИАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Теорией, вдохновившей создателей сентенциального программирования, явля тся такие формализации понятия алгоритма, как алгоритм аркова и олмогорова, и логические исчисления с крупноблочными правилами ввода (например, метод резолюций).
Схема сентенциального программирования получила две различные реализации, появившиеся практически одновременно (Рефал, Россия, В. Ф. Тур-чин, 1968, Prolog, Р. Ковальски, М. ван Эмден, Великобритания, А. Колмероэ, Канада, 1971-1974 гг.) и активно используемые до настоящего времени. О бе они концептуально интересны, и поэтому мы их рассматриваем в соответ-ствуей главе.
Предыдущая << 1 .. 41 42 43 44 45 46 < 47 > 48 49 50 51 52 53 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100