Разработка алгоритма. 
Основы программирования

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

Пример 1.6.

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

• 1) составление первоначального плана перевозок выполняется с использованием метода «северо-западного угла» или метода наименьших стоимостей;
• 2) для определения, является ли общая стоимость перевозок наименьшей, применяют метод потенциалов;
• 3) для улучшения плана перевозок применяется метод перераспределения поставок. ?

Важно!

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

Проверка правильности алгоритма.

Данный этап является наиболее трудоемким. Теоретическое доказательство правильности алгоритма в большинстве случаев требует привлечения серьезного математического аппарата и обычно крайне громоздко. Теоретическое доказательство может выполняться без программной реализации.

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

Пример 1.7.

Пусть имеется программа, реализующая вычисление произведения двух матриц Л и В. Серия тестов может выглядеть следующим образом:

• 1) вход: матрицы А и В, причем количество столбцов А совпадает с количеством строк В. Результат — произведение С = ЛВ
• 2) вход: матрицы А и В, причем количество столбцов А не совпадает с количеством строк В. Результат — выдача предупреждения о некорректности входных данных;
• 3) вход: матрицы А и В, причем имеются ошибки при вводе матриц (например, какой-либо элемент матрицы не является числом). Результат — выдача предупреждения о некорректности входных данных;
• 4) вход: матрицы А и В, где

(частный случай, когда матрицы являются векторами). Результат — т

произведение С = X аД;

i-1.

• 5) вход: матрицы А и В, где А= A_ixi = аиВ = B_ixl = b (частный случай, когда матрицы являются скалярами). Результат — произведение С — АВ — ab
• 6) вход: матрицы А и В, где одна из матриц единичная. Результат — матрица А (если В — единичная) или В (если А — единичная);
• 7) вход: матрицы А и В, где одна из матриц нулевая. Результат — нулевая матрица. ?

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

Программирование. Данный этан связан с использованием специальных средств реализации алгоритма:

• 1. Системы программирования. Представляют собой комплекс инструментов для создания программ. Основой системы программирования служит некоторый язык программирования. Среди наиболее популярных систем стоит выделить Visual Studio и Eclipse. Каждая из них поддерживает несколько языков программирования и предоставляет разработчику ряд дополнительных инструментов.
• 2. Специализированные пакеты прикладных программ. В качестве примера можно привести универсальную среду MATLAB. Изначально она предназначалась для работы с данными, представленными в виде матриц, но благодаря огромному количеству расширений (toolbox-ов) и встроенному языку программирования она превратилась в очень мощное средство с возможностью реализации алгоритмов на графах, нечетких множествах, структурированных типах данных.
• 3. Неспециализированные пакеты прикладных программ. Например, офисный пакет фирмы Microsoft использует встроенный язык программирования VBA (Visual Basic for Applications), при использовании которого можно модифицировать работу некоторых функций программ либо реализовать собственные. Для несложных алгоритмов иногда достаточно уже имеющегося функционала.

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