Алгоритмы решения

• Название: Алгоритмы решения
• Дата: 21.10.2018
• Размер: 87.92 Kb.
• Имя файла: Itogovy_test.docx
• Тип: Документы; #54099

Применение уголовного закона по аналогии недопускается.

(УК РФ, Ст.3, ч.2)

АЛГОРИТМЫ РЕШЕНИЯ

ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ

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

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

Поясним смысл сказанного примером. Пусть заданы натуральные числа A и B. Требуется найти их наибольший общий делитель (НОД). Древнегреческий математик Евклид в III веке до н.э. составил остроумный алгоритм решения этой задачи. Приведем описание этого алгоритма в современной интерпритации:

1. 
   Положить X равным A, а Y равным B.
   
2. 
   Если X больше Y, то перейти к п.4.
   
3. 
   Если X меньше Y, то перейти к п.5.
   
4. 
   Положить НОД равным X и перейти к п.6.
   
5. 
   Положить X равным XY и перейти к п.1.
   
6. 
   Положить Y равным YX и перейти к п.1.
   
7. 
   Закончить вычисления (СТОП).
   

Проверим работу этого алгоритма на примере. Пусть A12 и B18. Наши действия по реализации алгоритма сведем в табл.12.1. Как видим,

Таблица 12.1

Шаг	Пункт алгоритма	Результатдействия
0	0	X12, Y18.
1	1	XY? – Нет.
2	2	XY? – Да.
3	5	YYX6.
4	1	XY? – Да.
5	4	XXY6.
6	1	XY? – Нет.
7	2	XY? – Нет.
8	3	НОД6.
9	6	СТОП.

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

Перечислим основные требования, которым должны отвечать алгоритмы.

• 
  Конечность. Это требование состоит в том, что запущенный в работу алгоритм за конечное число шагов должен завершиться получением искомого результата.
  
• 
  Определенность. На любом шаге вычислений должно быть ясно, что делать дальше (переходить к следующему пункту, вернуться к тому или иному из предыдущих пунктов или закончить работу).
  
• 
  Допустимость. Каждому алгоритму ставится в соответствие множество числовых величин, допустимых для него в качестве исходных данных. Точно так определено и множество допустимых для этого алгоритма результатов вычислений.
  

В полной мере этим требованиям отвечает наглядное и, в то же время, строгое представление алгоритма в форме графа на рис. 12.3 показан граф алгоритма Евклида. Сравнив рис12.3с вербальным описанием этого алгоритма, легко убедиться в том, что они практически идентичны.

На том или ином шаге вычислений выполняют действия двух типов. Первый тип действий – содержательная обработка информации: задание исходных данных, вычисление значения переменной, (например, Y=YX), фиксация результатов вычислений и т.п. Второй тип действий – анализ результатов, полученных на предыдущих шагах, и выбор дальнейшего пути развития вычислительного процесса (скажем, проверка условия XY и переход по результату проверки на тот или иной пункт алгоритма). В соответствии с этим, для графического представления алгоритмов используем два символа:

• 
  прямоугольник, внутри которого записывается действие первого типа, выполняемое на данном шаге вычислений,
  

0

X=A

Y=B

1

XY

1

0

1

2

5

XY

0

Y=YX

X=XY ⁴

3

НОД=X

6

СТОП

шестиугольник, внутри которого записывается проверяемое условие. Эти символы называют вершинамиграфа:

прямоугольник – операторной вершиной, а шестиугольник – условной вершиной.

Вершины графа соединяют дугами (стрелками) в соответствии с логикой развития вычислительного процесса.

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

Рис.12.3

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

Среди операторных вершин две – особые: начальная и конечная. Начальная вершина не имеет входов, конечная вершина не имеет выхода. На рис. 12.3. начальная вершина – прямоугольник с записями X=A; Y=B, а конечная – прямоугольник с записью СТОП.

Корректно разработанный граф (тот, который отвечает требованиям конечности и определенности) отличается тем, что:

• 
  он должен иметь одну и только одну начальную вершину, одну и только одну конечную вершину,
  
• 
  из любой вершины графа должен быть путь в конечную вершину.
  

Для того чтобы в поясняющем тексте можно было сослаться на ту или иную вершину графа, ее снабжают меткой. Обычно в качестве метки используют число, записываемое в разрыв контура вершины. На рис. 12.3 вершины графа отмечены символами, которые отвечают пунктам словесного алгоритма Евклида.