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

 

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

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

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 164 165 166 167 168 169 < 170 > 171 172 173 174 175 176 .. 316 >> Следующая

Из обсуждения нетрадиционных процедур видно, что в их механизмах проявляется необходимость параллельного и совместного исполнения, предписываемого либо пооряемого соответствуими моделями вычислений.
Задания для самопроверки
1. странить неэффективность рекурсивного алгоритма для числе ибо-наччи 8.7.2 путем преобразования программы, направленного на запоминание вычисляемых значений.
2. странить неэффективность рекурсивного алгоритма для числе ибо-наччи 8.7.2 путем перехода к итеративной программе.
3. Устранить неэффективность рекурсивного алгоритма для числе Фибоначчи 8.7.2 путем использования теоретических результатов, дающих другое определение чисел Фибоначчи.
4. Сравнить четре реения задачи про числа ибоначчи.
Глава 9
Структуры данных
В данной главе анализируется, как организу тся структуры перерабатываемых программой данных.
Первой причиной появления структур данных является то, что систематизация и структурирование для сло ной информации всегда идут рука об руку. оскольку управление и данне взаимосвязаны, иерархически структурируя управление, мы долн соответственно структурировать и данные.
ругая причина связана с тем, что реальне объект представля тся агрегатами взаимосвязанных характеристик. Например, хранить координаты точки пространства как три отдельне переменные — провоцировать оибки в программе. Следовательно, в языке необходимо обеспечивать возмо ность агрегирования (соединения) данных. для вчислителя ну но обеспечить, чтобы в конце концов и аргументы, и результат вычислений сводились на уровень атомарных объектов. Поэтому агрегаты необходимо уметь разъединять на составные части.
Третья причина в том, что при составлении программ требуется задавать регулярные действия для подобно описваемх и подобно интерпретируемых объектов, и хранить промеуточные результаты вычислений, при этом далеко не всегда можно обойтись атомарными единицами данных.
В последуих параграфах обсу да тся вопрос задания, использования и хранения структурированных даннх, а так е средства, предлагаемые для этого язками программирования.
§ 9.1. ОБЩИЕ КОНЦЕПЦИИ СТРУКТУРИРОВАНИЯ ДАННЫХ 9.1.1. Структура программы и структуры данных
482
9.1. СТРУКТУРИРОВАНИЕ ДАННЫХ
483
Система данных, перерабатываемых программой, базируется на простых и неделимых понятиях — первичных элементах системы. Выбор базы первичных элементов зависит от точки зрения на программу, в частности, от того, что считается суественнм и чем мо но временно пренебречь. б-стракция рассмотрения в значительной степени определяет и взгляд на дан-не. В то е время, различные уровни абстрактности даннх требу т различных языковых средств, иногда своего языка описания обработки. Это касается и средств оперирования, и структур данных. Реальная моделируемая программой изнь содерит не целые, веественные и ине числа или массивы, а вполне конкретные объекты, представляемые в программе числами, структурами, массивами и т. п. Выбор представления суностей предопределяет реализацию конкретных операций, и чаще всего успех либо неудачу программного проекта.
оэтому, если задача с самого начала ставится корректно, правильно говорить о выборе языка программирования, соответствуего реаемой задаче. о часто выбор языка навязан вненими обстоятельствами. В лбом случае программист дол ен осознавать:
• на какие средства описания он вправе рассчитывать и чего не может требовать в данной ситуации;
• какие абстракции являются идеально подходящими для решаемой задачи, и как это идеальное моделируется в реальном языке.
твет на эти вопросы суественно зависит от квалификации самого программиста. Первая часть этого положения — вопрос специального образования программиста, вторая — обей теоретической подготовки.
бычный язык программирования предлагает ирокий ассортимент воз-мо ностей организации даннх. Следовательно, перед программистом стоит задача выбора не только абстрактного, но и конкретного представления данных. Видимость, что здесь больше свободы, чем при составлении алгоритмов, обманчива. алицо взаимосвязи и взаимовлияние. иксация структур данных определяет, будет ли хороо работать тот или иной алгоритм. С другой сторон , идеально подходяие для алгоритма объекты — не только образ конкретнх объектов, но и прообраз программной структуры данных, которая не может быть выбрана произвольно. Традиционные критерии эффективности по времени вчислений и занимаемой памяти ныне явля т-ся отн дь не самыми ванми. а выбор и алгоритмов, и структур данных суественно влия т ответ на следуие вопросы:
484
ГЛАВА 9. СТРУКТУРЫ ДАННЫХ
• насколько понятен сделаннй вбор,
• каков уровень адекватности получаегося реения,
• велика ли трудоемкость распространения реения на другие ситуации и его модификации при изменений условий задачи,
• каковы границы возможного для таких модификаций?
это далеко не полный перечень аспектов задачи выбора структуры данных и соответствуих ей алгоритмов.
Единственный универсальный рецепт, который здесь можно дать, это повышение уровня абстрактности рассмотрения задачи с последующей трансформацией выбранного в конкретные структуры. оэтому вано систематическое изучение возмо ностей наиболее употребляемых структур данных.
Предыдущая << 1 .. 164 165 166 167 168 169 < 170 > 171 172 173 174 175 176 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100