Замечание о методах, алгоритмах и программах

В ЧЕМ РАЗНИЦА МЕЖДУ МЕТОДОМ И АЛГОРИТМОМ?

Метод - это совокупность действий, а алгоритм - конкретная последо­вательность действий.

1. Алгоритм более подробен, чем метод. Иллюстрация алгоритма - блок-схема, а иллюстрация метода - устройство, компоненты которого рабо­тают одновременно.

2. Один и тот же метод могут реализовывать несколько алгоритмов. И чем сложнее метод, тем больше возможно реализаций в виде алгоритмов.

3. По описанию алгоритма можно понять метод, но описание метода даст более полное представление об идеях, реализованных в алгоритме.

4. В методе ошибок быть не может. Но с другой стороны, ошибочным мо­жет быть выбор метода. На тех же данных может всегда давать лучший результат другой метод, преимущество которого может казаться не оче­видным на первый взгляд. Ошибочным может быть и выбор алгоритма.

5. Разные алгоритмы, реализующие один и тот же метод, могут давать со­вершенно разные результаты! Покажем это на примере.

ПРИМЕР, ПОКАЗЫВАЮЩИЙ НЕЭКВИВАЛЕНТНОСТЬ АЛГОРИТМОВ МЕТОДА

Метод содержит процедуру Z, поворачивающую двумерное изображение на заданный угол А и добавляющую яркость точкам изображения на вели­чину В, зависящую от расстояния до заданной точки С: В=В(х-хо, у-уо) "Выделенная" точка С может лежать как внутри, так и снаружи границ изо­бражения, это дела не меняет. При повороте она получает новые координа­ты: х₀, у\.

Очевидно, что возможны два алгоритма: ■ сначала развернуть на заданный угол, затем добавить яркость; » сначала добавить яркость, затем развернуть.

Результаты работы этих двух алгоритмов могут незначительно отличать­ся из-за округления результатов вычисления расстояний: D=((x-xo)^{2 +}(у-Уо)²)^1/2, a D^,=((x^,-x^>o)²+(y'-y'o)²)^1/2> и в общем случае эти расстояния до и после поворота D и D' не равны.

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

тики - 16 знаков или 1024, все равно D и D' придется округлять после кака^ го-то знака, отбрасывая остальные знаки. Увеличение точности приведет лишь к уменьшению вероятности того, что после округления D и D' будут неравны.

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

Например, критерий имеет вид T_new<3-T₀i_d', где T₀|_d - суммарная яркость изображения до процедуры Z, a T_new- после нее. И если в первом алгоритме Ты/Tnew = 0.3333 , а во втором 0.3334, то после проверки критерия выпол­нятся разные ветви алгоритма. Результат неэквивалентности алгоритмов будет хорошо заметен.

Даже если никакого критерия нет, ошибка может накапливаться посте­пенно, на каждом шаге некоторого цикла.

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

Реализация алгоритма - программа

Программа - это реализация, "воплощение" алгоритма на одном из языков программирования. Таким образом, общая схема написания программы сжатия (кодека, т. е. компрессора и декомпрессора), равно как и любой про­граммы вообще, следующая:

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

2) выбор метода;

3) создание алгоритма;

4) написание программы;

5) тестирование, оптимизация и настройка.

В этой книге описаны именно методы, но для их иллюстрации приводятся конкретные алгоритмы для одного процессора, иллюстрируемые текстами на языке программирования Си.