Содержание
Применение уголовного закона по аналогии не допускается.
(УК РФ, Ст.3, ч.2)
АЛГОРИТМЫ РЕШЕНИЯ
ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
Приступая к решению любой задачи, человек планирует последовательность действий, выполнение которых приводит к достижению поставленной цели. Подобный план действий называют алгоритмом. В математике имеют дело с вычислительными алгоритмами.
Алгоритмом (вычислительным) называется строгое описание эффективной процедуры решения математической задачи.
Поясним смысл сказанного примером. Пусть заданы натуральные числа А и В. Требуется найти их наибольший общий делитель (НОД). Древнегреческий математик Евклид в III веке до н.э. составил остроумный алгоритм решения этой задачи. Приведем описание этого алгоритма в современной интерпретации.
Проверим работу этого алгоритма на примере. Пусть А=12 и В=18. Наши действия по реализации алгоритма сведем в табл.12.1. Как видим, процедура вычислений, порождаемая алгоритмом, представляет собою последовательность шагов. На каждом шаге выполняется тот или иной пункт алгоритма.
Перечислим основные требования, которым должны отвечать алгоритмы.
Конечность. Это требование состоит в том, что запущенный в работу алгоритм за конечное число шагов должен завершиться получением искомого результата.
Определенность. На любом шаге вычислений должно быть ясно, что делать дальше (переходить к следующему пункту, вернуться к тому или иному из предыдущих пунктов или закончить работу).
Допустимость. Каждому алгоритму ставится в соответствие множество числовых величин, допустимых для него в качестве исходных данных. Точно так определено и множество допустимых для этого алгоритма результатов вычислений.
В полной мере этим требованиям отвечает наглядное и, в то же время, строгое представление алгоритма в форме графа. На рис. 12.3 показан граф алгоритма Евклида
Список использованной литературы
—