Алгоритмизация. Понятие алгоритма и алгоритмической системы. Свойства алгоритма. Проектирование алгоритмов. Блок-схема алгоритма. Основн

 

 

 

7.1.7.2 Модульное программирование

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.8 Сложность алгоритмов

 

 

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

7.1.8.1 Временная сложность

 

Физическое время выполнения алгоритма — это величина, равная произведению n и t, где n – число действий (элементарных шагов, команд); t — среднее время выполнения одного действия. Число шагов и определяется описанием алгоритма в данной алгоритмической модели и не зависит от физической реализации модели; t — величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ, поэтому объективной математической характеристикой трудоемкости алгоритма (его временной сложности) в данной модели является число действий.

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

 

7.1.8.2 Емкостная сложность

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.9 Решение задач с помощью алгоритмов

 

 

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

1. Общая формулировка задачи

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

2. Математическая формулировка задачи

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

3. Выбор математического метода решения

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

4. Составление алгоритма решения

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

5. Составление и отладка программы

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

6. Тестирование программы

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

7. Решение поставленной задачи и представление результатов

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ключевые понятия

 

 

Алгоритмизация – процесс систематического составления алгоритмов для решения поставленных прикладных задач.

 

Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.

 

Алгоритмическая система – общий способ задания алгоритмов.

 

Псевдокод – описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задачи, перед точной его записью на языке программирования.

 

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

 

Программа – описание структуры алгоритма на языке алгоритмического программирования.

 

Рекурсивный алгоритм – алгоритм, организованный таким  образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Библиографический список

 

Алгоритмы: введение в  разработку и анализ. : Пер. с англ. — М. :

Издательский дом "Вильяме", 2006. — 576 с. : ил. — Парал. тит. англ.

 

Гуц А.К. Математическая логика и теория алгоритмов: Учебное  пособие. – Омск: Издательство Наследие. Диалог – Сибирь, 2003. – 108 с.

 

Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М,

2000. - 232 с. - (Серия «Высшее образование»)

 

Соболь Б.В. [и др.] «Информатика»– Ростов-на-Дону: Феникс, 2007 – 449 с.

 

http://www.slovopedia.com/2/192/204796.html