Алгоритмы и алгоритмизация

[Akrom Obidov]

Вот статья из Инета, автор С. Немнюгин.

Полезно для новичков, профиссионалам тоже прочитать не помешает!

Этапы разработки программы. Алгоритмы

Этапы разработки программы

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

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

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

[Akrom Obidov]

Алгоритмы и алгоритмизация

Процессор электронно-вычислительной машины, это чудо техники, умеет, тем не менее, выполнять лишь простейшие команды. Каким же образом компьютер решает сложнейшие задачи обработки информации? Для решения этих задач программист должен составить подробное описание последовательности действий, которые необходимо выполнить центральному процессору компьютера. Составление такого пошагового описания процесса решения задачи называется алгоритмизацией, а алгоритмом называется конечный набор правил, расположенных в определенном логическом порядке, позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач. В разных ситуациях в роли исполнителя может выступать электронное или какое-либо иное устройство или человек (например, военнослужащий, охраняющий склад боеприпасов и действующий согласно алгоритмам, записанным в устав караульной службы).
Само слово "алгоритм" возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми "Algoritmi de numero Indorum", что можно перевести как "Трактат Аль-Хорезми об арифметическом искусстве индусов". Составление алгоритмов и вопросы их существования являются предметом серьезных математических исследований. Здесь мы познакомимся только с основными понятиями и фактами, касающимися алгоритмизации.

Алгоритм должен удовлетворять определенным требованиям. Принято выделять следующие семь:

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

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

2, 3, +

Проследим выполнение этой программы. Первая операция -- считывание в стек значения 2. Затем в стек считывается второе значение (3). Первое значение при этом сдвигается во вторую ячейку памяти. Третий шаг выполнения программы -- вычисление суммы двух считанных значений (они называются операндами). Результат этой операции -- значение 5 -- записывается в первую ячейку стека.
Мы рассмотрели пример простейшей программы. Она является записью алгоритма решения некоторого класса задач -- задач вычисления суммы двух чисел. Обозначим эти числа a и b. Тогда алгоритм можно записать следующим образом:

• Считать число a.
• Считать число b.
• Выполнить суммирование c := a + b.
• Вывести число c.
  

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

a := a + 1

воспринимается программистом совершенно естественно, а уравнение

a = a + 1

математик сочтет неверным. В первом случае имеется в виду вычисление суммы содержимого ячейки a и числовой константы 1 и занесение полученного результата в ту же ячейку a. Второй случай равносилен неверному тождеству 0 = 1.
Составим алгоритм решения следующей задачи. Пусть заданы два значения, x и y. Необходимо сравнить эти значения и напечатать имя большей переменной. Для решения этой задачи достаточно сравнить оба значения и в зависимости от результата сравнения вывести на печать символ "x" или символ "y":

• Ввести значение x.
• Ввести значение y.
• Если x < y, то напечатать "y", иначе напечатать "x".
  

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

z0 = 1,
zn = zn-1x x.

Запись алгоритма вычисления произвольной целочисленной степени числа приводится ниже:

• Ввести значения x и n.
• Переменной z присвоить начальное значение 1.
• Вспомогательной переменной i присвоить начальное значение 0.
• Переменной z присвоить результат выполнения операции zx x.
• Переменной i присвоить значение i + 1.
• Если i < n, то перейти к шагу 4, иначе остановить работу программы.
  

Этот алгоритм содержит ввод данных (шаг 1), блок вычислений (шаги 2, 3), ветвление (шаг 6), а также еще одну алгоритмическую структуру -- цикл (шаги 4, 5 и 6). Цикл представляет собой многократно повторяющуюся последовательность операторов и играет в программировании важнейшую роль. Кроме уже перечисленных структур иногда выделяют еще одну -- обход, который представляет собой передачу управления с пропуском нескольких шагов алгоритма.
Для записи алгоритмов мы пользовались естественным языком. Иногда используют полуформальный язык с ограниченным словарем (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования.
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flowchart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рис. 1.1

Рис. 1.1. Обозначения, используемые в блок-схемах алгоритмов

Составим алгоритм вычисления квадратного корня из произвольного положительного вещественного числа x методом Герона и запишем его на естественном языке, а также в виде блок-схемы. Напомню (см. Учебник, урок 1), что метод основан на многократном применении формулы

zn+1=½*(zn+x/zn)
при
z0 = 1.

Числовая последовательность z n в пределе при n сходится к искомому значению. Мы, разумеется, не сможем устремить нашу последовательность к бесконечности, поэтому примем самое простое (но не самое верное!) решение -- выполним только 5 итераций метода, считая, что при этом будет достигнута достаточно хорошая точность. Обычно десяти итераций метода Герона более чем достаточно для достижения хорошей точности расчета. На рис. 1.2 приводятся оба варианта записи алгоритма.

Числовая последовательность z n в пределе при n сходится к искомому значению. Мы, разумеется, не сможем устремить нашу последовательность к бесконечности, поэтому примем самое простое (но не самое верное!) решение -- выполним только 5 итераций метода, считая, что при этом будет достигнута достаточно хорошая точность. Обычно десяти итераций метода Герона более чем достаточно для достижения хорошей точности расчета. На рис. 1.2 приводятся оба варианта записи алгоритма.

Рис. 1.2. Алгоритм вычисления квадратного корня методом Герона: слева -- блок-схема, справа -- запись алгоритма на естественном языке

Ну а теперь займемся самым любимым занятием школьников всех времен и народов -- решением квадратного уравнения:

ax2 + bx + c = 0.

Будем полагать, что коэффициенты этого уравнения a, b и c представляют собой вещественные числа. Простейший случай предполагает, что все коэффициенты отличны от нуля. В зависимости от знака дискриминанта квадратного уравнения

D = b2 - 4ac

возможны три случая:

• Если D > 0, то имеются два различных вещественных корня, которые можно вычислить по следующим формулам:
• Если D = 0, то имеется единственный корень (точнее, двукратный корень): x=-b/2a.
• Если D < 0, то вещественных корней нет.
  

Блок-схема алгоритма приведена на рис. 1.3.

Рис. 1.3. Блок-схема упрощенного алгоритма решения квадратного уравнения

Следует заметить, что приведенный алгоритм предназначен для решения узкого класса задач -- квадратных уравнений с "хорошими" коэффициентами. Если допустить, что коэффициенты могут принимать произвольные вещественные значения, есть опасность, что при определенных значениях коэффициентов (например, a = 0) возникнет аварийная ситуация (деление на ноль). Качественный алгоритм и качественная программа должны быть устойчивыми, то есть при любых входных параметрах завершение работы программы должно быть нормальным, хотя, возможно, и сопровождаться предупреждающим сообщением о некорректности входных данных. Свойством устойчивости обладает алгоритм решения квадратного уравнения, приведенный на рис. 1.4.
Разработанный программистом алгоритм должен давать правильный ответ. Проверка алгоритма может оказаться непростым делом. В простых случаях такая проверка может быть выполнена с помощью заполнения трассировочной таблицы. Каждый столбец такой таблицы соответствует определенной переменной, а каждая строка -- одному шагу алгоритма. Для заполнения таблицы необходимо шаг за шагом проследить выполнение алгоритма, записывая в таблицу текущие значения выбранных для трассировки переменных. Такой метод позволяет выявить логические ошибки, допущенные при составлении или записи алгоритма, и определить, верен ли окончательный ответ. Составим в качестве примера трассировочную таблицу для алгоритма Герона вычисления квадратного корня из числа 2 (табл. 1.1). Как видно из таблицы, уже после третьей итерации приближенное значение квадратного корня отличается от точного 1,414213 лишь в шестом знаке после запятой.

Рис. 1.4. Блок-схема полного алгоритма решения квадратного уравнения

Таблица 1.1. Трассировочная таблица алгоритма Герона

[Akrom Obidov]

to be continued....

[Snaky]

мне кажется что эти посты надо переместить в другой раздел, например "проектирование"
потому что к паскалю они относятся лишь косвенно

[Akrom Obidov]

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

[Fayzulla Agzamov]

Очень актуальная тема наверно вот этот стандарт как раз и подойдет для всего этого
Информационные тех...
Процессы жизненного цикла Программных средств
ISO /IEC 12207 : 1995, IDT

[Fayzulla Agzamov]

Данный стандарт действует на территории Узбекистана также

[Timur Bazikalov]

По ссылке можно скачать сам стандарт:

http://cert.obninsk.ru/dump/alldoc/i...6/g31220.shtml

Или в приложении к посту ...

А главное, всё это можно делать на паскале!