Алгоритмы и их свойства (стр. 1 )

§ 1. Алгоритмы и их свойства

Людям в повседневной жизни приходится решать различные за­дачи. Это могут быть бытовые (приготовить обед), профессиональные (изго­товить деталь) и т. д. Все задачи можно разделить по определенным призна­кам на группы: математические, инженерные, экономические и т. д. Одни задачи решаются легко, другие сложнее. Решить задачу - это значит получить результат, отвечающий целям задачи. Для каждой задачи всегда должно быть известно, что считать исходными данными, а что результатом.

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

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

Понятие алгоритма относится к числу фундаментальных математических понятий. Термин "алгоритм" происходит от имени узбекского математика IX века Аль–Хорезми, который разработал правила выполнения четырех ариф­метических действий над числами в десятичной системе счисления. Сово­купность этих правил в Европе стали называть "алгоризм". Впоследствии слово переродилось в "алгоритм" и в 30-х годах XX века понятие алгоритма стало объектом математического изучения, а с появлением ЭВМ получило широкую известность.

Свойства алгоритма

1.  дискретность – каждый алгоритм – это последовательность четко разде­ленных друг от друга команд, образующих дискретную (прерывистую) струк­туру. Только выполнив одну команду можно перейти к другой;

2.  определенность (детерминированность) – каждая команда понятна ис­полнителю, однозначно им трактуема, не возникает разночтений в трактовке порядка выполнения команд;

3.  массовость – один и тот же алгоритм может быть использован для реше­ния целого класса однотипных задач;

4.  результативность – алгоритм всегда приводит за конечное число дейст­вий к правильному решению в случае точного его исполнения;

5.  однозначность - при одних и тех же условиях алгоритм должен приводить к од­ному результату.

Способы описания алгоритмов

Существует несколько способов записи алгоритмов, отличающихся друг от друга наглядностью, компактностью, степенью формализации. Спо­соб записи алгоритма – это язык определенных символов, правил и т. д. Естественный человеческий язык не является формализованным, и поэтому может содержать выражения, имеющие неоднозначный смысл. По­добные явления должны быть полностью исключены в языках, используемых для общения с исполнителями-автоматами. Приходится соблюдать ряд требований:

·  при формулировании предписаний можно требовать от исполнителя вы­полнения лишь тех операций, которые жестко определены для данного исполнителя;

·  можно использовать лишь принятые для языка исполнителя правила построения предписаний;

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

Формализация языка обедняет его выразительные способности по сравнению с естественным языком человека. Основными способами описания алгоритмов являются:

1.  словесный;

2.  табличный;

3.  графический;

4.  программа.

1. Словесный способ описания алгоритмов ориентирован, прежде всего, на исполнителя-человека и допускает различные варианты записи указаний (команд). Но при этом запись должна быть достаточно точна, чтобы человек-исполнитель мог понять суть команд и выполнить их. Один из недостатков этого способа – многословие. Но этот способ описания алго­ритмов обладает и большой универсальностью: словами можно выразить то, что нельзя записать с помощью формул. А это особенно ценно при рабо­те с алгоритмами не вычислительных процессов.

Примеры: инструкция сборки шкафа, велосипеда, порядок постройки дома, рецепт приготовления торта.

2. Табличный способ описания алгоритма удобен при массовых вычислениях по одной и той же формуле.

Пример: вычислить значение функции при разных значениях аргумента х.

x	2x	2x + 3	3x	3x – 5
5	10	13	15	10	1.3
-3	-6	-3	-9	-14	0.21428...
0	0	3	0	-5	-0.6

3. Графический способ описания предполагает запись алгоритма в виде блок-схемы.

Блок-схема – это способ представления алгоритма с помощью геометриче­ских фигур заданного набора, изображающих отдельные шаги алгоритма и соединенных между собой линиями (стрелками), указывающими порядок реализации алгоритма.

Для изображения блок–схемы любого алгоритма ограничимся сле­дующим набором геометрических фигур:

	или		начало (конец) алгоритма
	выполнение действий
	ввод (вывод) данных
	проверка условия
	подпрограмма
	начало цикла

Графический способ записи отличается наглядностью и очень полез­ен на начальной стадии разработки алгоритма.

4. Программа представляет собой способ записи алгоритма с помощью операторов (команд) языка программирования (Паскаль, Бейсик, Cи++, Фортран, Пролог, Ассемблер)

В таблице приведены примеры записей алгоритма вычисления суммы квадратов первых 100 натуральных чисел с помощью различных языков программирования:

Алгоритмический язык АЛГ сумма квадратов НАЧ ЦЕЛ s, i s: = 0 НЦ ДЛЯ i ОТ 1 ДО 100 s: = s + i * i КЦ ВЫВОД «Сумма квадратов= »,s КОН	Паскаль (Pascal) REM Вычисление суммы квадратов S = 0 FOR I=1 TO 100 S = S + I * I NEXT I PRINT «Сумма квадратов= »,S END
Бейсик (Basic) Program sum; var s, i: integer; Begin s: = 0; for i: = 1 to 100 do s: = s + i * i; writeln(‘сумма квадратов= ’,s); End.	Cи++ (С++) // summa. cpp # include <iostream. h> main () {for (int i = 1, s = 0; i<=100, i++) s+ = i * i; {cout<< «\ n Сумма квадратов= »<<s; } }

Структурный подход к составлению алгоритмов

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

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

1. Линейная структура обеспечивает выполнение команд или операторов последовательно друг за другом

2. Разветвляющаяся структура обеспечивает выполнение одной из последовательностей действий (P1 или P2) в зависимости от выполнения условия S:

альтернатива (полная конструкция) ЕСЛИ S ТО P1 ИНАЧЕ P2.

коррекция (неполная конструкция) ЕСЛИ S ТО P

3. Циклическая структура обеспечивает многократное повторение последовательности действий в зависимости от определенного условия (повторяй пока условие истинно) или определенное число раз (повторяй 15 раз).