В. Разработка алгоритма

Б. Разработка математической модели и составление алгоритма.

А. Постановка и формулировка задачи.

Необходимо в самом начале четко поставить задачу, то есть:

- определить цели решения и наименование задачи;

- изучить закономерности исследуемого процесса;

- обосновать и выбрать показатели эффективности;

- определить исходные данные с указанием размерности и пределов изменения;

- определить выходные данные (результаты счета);

- оговорить промежуточные результаты;

- ввести ограничения и допущения, принимаемые в задаче.

В результате этого этапа мы имеем словесное формулирование задачи с указанием исходных данных, ожидаемых промежуточных и конечных результатов, их точности и достоверности.

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

"Математическая модель - приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики" (академик А.Н.Тихонов).

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

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

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

В IX в. великий узбекский математик Мохаммед аль-Хорезми разработал правила выполнения четырех арифметических действий над числами в десятичной системе счисления. Множество этих правил назвали алгоритмом (algorithmi - от латинского написания аль-Хорезми (из Хорезма)), а затем словом "алгоритм" стали обозначать совокупность правил подобного вида, а не только правил выполнения арифметических действий.

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

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

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

Алгоритм характеризуется следующими свойствами:

- дискретностью, т.е. способностью преобразования исходных данных за прерывистые отдельные законченные шаги;

- массовостью, т.е. применимостью алгоритма ко всем задачам рассматриваемого типа при любых исходных данных. Как установлено в теории алгоритмов, существуют и такие классы задач, для решения которых нет и не может быть установлен универсальный прием - алгоритм решения (хотя при отдельных ограничениях на данные решения может быть найден). Примером такой алгоритмически неразрешимой задачи является теорема Ферма: xⁿ + yⁿ = zⁿ при n>4. Возможно перевести некоторые алгоритмически неразрешимые задачи в алгоритмически разрешимые. Например, задачи перевода вещественных чисел из десятичной системы в двоичную, путем введения ограничения по точности;

- определенностью, т.е. строгим однозначным определением смысла и порядка выполнения его отдельных шагов;

- результативностью, т.е. выполнимостью его за конечное число шагов;

- формальностью, т.е. возможностью правильного восприятия и выполнения его любым пользователем;

- сложностью, т.е. минимальным количеством информации, необходимым для его описания. Сложность алгоритма определяется: полиномиально, в степенном виде, логарифмически;

- трудоемкостью, т.е. сложностью вычислений, определяемой объемом вычислений и количеством работы вычислительной системы в целом;

- детерминированностью, т.е. однозначностью результата при заданных исходных данных;

- понятностью, когда каждая команда алгоритма входит в систему команд исполнителя (СКИ) и обеспечивает его выполнение.

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

Будем называть два алгоритма эквивалентными, если:

1) множество допустимых исходных данных одного из них является множеством допустимых исходных данных и для другого; из применимости одного алгоритма к каким-либо исходным данным следует применимость и другого алгоритма к этим исходным данным;

2) применение этих алгоритмов к одним и тем исходным данным дает одинаковые результаты.

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

1) Описания используемых в алгоритме переменных

2) Ввода. Присваиваются некоторым переменным значения исходных данных, подготовленных на внешних носителях.

3) Вывода. На внешний носитель передаются значения вычисленных переменных.

4) Присваивания (вычислительный). Присваивают переменным значения, полученные в результате вычисления выражений

y=y+2

Значение переменной y формируется из старого ее значения и прибавления константы равной 2. После выполнения операции в поле памяти переменной y будет записано новое значение, старое при этом будет уничтожено.

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

6) Стандартный. Обращение к стандартному, т.е. заранее разработанному программному обеспечению; например, встроенной функции, подпрограмм и т.д.

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

При графической форме алгоритм представляется в виде схемы в соответствии с ГОСТ 19.003-80.

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

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

Результат этапа: алгоритм решения задачи, записанный одним из известных способов - алгоритмический язык, схема алгоритма или последовательность предикатов (наибольшее распространение получил способ графических схем алгоритмов).

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

Г. Разработка программы на алгоритмическом языке.

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

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

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

1. При разработке программа делится на небольшие модули, имеющие низкую степень связи друг с другом.

2. Написание программы выполняется в соответствии с правилами структурного программирования.

3. Программа пишется так, чтобы ее текст не требовал серьезной доработки и перестройки при тестировании и отладке.

4. При сомнении в правильности использования и выполнения того или иного оператора (компонента ОС) следует проверить свои подозрения с помощью специально подобранных тестовых данных и программ.

Дата добавления: 2014-12-27