Основы алгоритмизации

1.1. Понятия алгоритма

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

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

 

1.2. Свойства алгоритма

1. Наличие ввода исходных данных.

2. Наличие вывода результата выполнения.

3. Однозначность (компьютер "понимает" только однозначные инструкции).

4. Общность - алгоритм предназначен для решения некоторого класса задач.

5. Корректность - алгоритм должен давать правильное решение задачи.

6. Конечность - решение задачи должно быть получено за конечное число шагов.

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

 

1.3. Типы алгоритмов

I. Линейным алгоритмом (линейная последовательность операций) называется так потому, что выполняются только последовательные действия без условий и повторов. Линейная последовательность в данном примере состоит из блоков ввод/вывод данных.

II. Алгоритм ветвления (условный оператор) называется так потому, что после передачи ему управления выполнение алгоритма может пойти по одной из двух возможных ветвей. Какая именно ветвь будет выбрана, зависит от выполнения условия.

III. Цикл представляет собой многократно повторяющуюся последовательность операторов. Операторы повторяются конечное число раз до выполнения условия.

IV. Обход (безусловный переход по метке) еще одна структура, которая представляет собой передачу управления с пропуском нескольких шагов алгоритма.

 

1.4. Виды представления алгоритмов

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

II. Псевдокод –полуформальный язык с ограниченным словарем (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования.

III. Блок-схема – используется для разработки структуры программы (в англоязычной литературе используется термин flow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рис. 4.

IV. Программирование – запись алгоритмы на выбранном языке программирования программирования для решения различных задач на компьютере.

 

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

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

 

Ø постановка задачи;

Ø анализ, формализованное описание задачи, выбор математической модели;

Ø выбор или разработка алгоритма решения задачи;

Ø проектирование общей структуры программы;

Ø кодирование (запись алгоритма на языке программирования);

Ø отладка и верификация программы (исправление алгоритмических и синтаксических ошибок);

Ø получение результата, его интерпретация и, возможно, последующая модификация модели;

Ø публикация или передача заказчику результата работы;

Ø сопровождение программы.

 

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

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

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

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

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

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

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

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

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