Тема 7. Основы теории алгоритмов

П. 1. Сущность алгоритма. Основные свойства алгоритмов.

Понятие алгоритма относится к числу фундаментальных математических понятий и является объектом специального раздела математики – теории алгоритмов.

В настоящее время это одно из основных понятий информатики.

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

Суть состоит в том, что если алгоритм разработан, то его можно вручить для выполнения любому исполнителю (в том числе ЭВМ) незнакомому с решением задачи, и точно следуя правилам алгоритма, исполнитель получит её решение.

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

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

Свойства, которым должны удовлетворять алгоритмы:

1. Дискретность. Это свойство состоит в том, что описываемый процесс должен быть разбит на последовательность отдельных шагов.
2. Понятность. Используемые на практике записи алгоритмов составляются и ориентируются на определённого исполнителя.
3. Определённость (детерменированность) означает, что способ решения задачи определён однозначно в виде последовательности шагов. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно
4. Массовость – алгоритм решения задачи разрабатывается в общем виде так, что бы его можно было применять для класса задач различающихся только лишь исходными данными.
5. Результативность. При точном использовании всех предписаний должен прекратиться за конечное число шагов и при этом должен быть получен конечный результат.

П. 2. Форма записи алгоритмов.

На практике наиболее распространены следующие формы записи алгоритмов:

• Содержательная (текстуальная) форма это самая распространённая форма представления алгоритмов, адресуемых человеку. Форму словесной записи имеют многие «бытовые» алгоритмы. Эта форма может быть использована и для описания вычислительных алгоритмов.
  Пример. Пусть задано три числа А1, А2, А3. Требуется определить максимальное число Амакс из заданного набора.
  Текстуальная форма представления алгоритма может выглядеть следующим образом:
  1. Ввести числа
  2. Сравнить числа А1 и А2
  3. Если значения А1 больше А2, то Амакс = А1, иначе Амакс = А2
  4. Сравнить значения А3 и Амакс, если А3 больше Амакс, то Амакс = А3
  5. Вывести Амакс
• Изображение алгоритма в виде блок-схемы. Блок-схема это наглядное представление алгоритма, дополненное элементами словесной записи. Каждый элемент изображается графической фигурой или блоками, причём различным действиям соответствуют различные фигуры.