Глава 3.Основы алгоритмизации и программирования

3.1.Понятие алгоритма и его свойства

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

Довольно часто рассматриваются и нечисленные алгоритмы, где объектами операций являются не числа. В роли данных могут выступать последовательности символов - тексты, формулы и т.д.; в роли операций - не операции сложения, умножения и подобные им, а операции приписывания одной последовательности к другой, операции замены по некоторой таблице одних символов на другие и т.д. Примером алгоритма, основывающегося на подобных операциях, являются алгоритмы преобразования текста в код Морзе.

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

Поиски различных алгоритмов входили в круг важных задач во все время существования науки. В качестве примера рассмотрим алгоритм Евклида (III век до н.э.), решающий все задачи следующего типа: для двух натуральных чисел Х и Y найти их наибольший общий делитель (НОД). Суть задачи заключается в последовательности деления чисел. Заменив деление повторным вычитанием, получим одну из формулировок этого алгоритма:

1. Присвоить переменным X и Y исходные значения.

2. Если X > Y, то перейти к п. 4, иначе к п. 3.

3. Если X < Y, то перейти к п. 5, иначе к п. 6.

4. Заменить пару (X,Y) парой (X-Y,Y) и вернуться к п. 2.

5. Заменить пару (X,Y) парой (X,Y-X) и вернуться к п. 2.

6. Здесь Х=Y. Считать НОД равным Х или Y.

7. Конец работы.

Составим таблицу, показывающую, как с течением времени после выполнения очередного шага меняются значения X и Y. В качестве исходного данного возьмем пару чисел (100,80).

Работа алгоритма Евклида может быть изображена в виде таблицы (табл.3.1).

Алгоритм Евклида Табл. 3.1.

Момент времени	Шаг Алгоритма	X	Y	? (X>Y)	? (X<Y)
1 2 3 4 5 6 7 8 9 10 11 12 13 14	1 2 4 2 3 5 2 3 5 2 3 5 2 3	100 100 20 20 20 20 20 20 20 20 20 20 20 20	80 80 80 80 80 60 60 60 40 40 40 20 20 20	ДА НЕТ НЕТ НЕТ НЕТ	ДА ДА ДА НЕТ
15	6	НОД=20
16	КОНЕЦ РАБОТЫ

В настоящее время интерес к алгоритмам особенно велик благодаря упомянутой возможности использования компьютеров в технике, экономике, научных исследованиях и т.д. Дело здесь в том, что компьютер во время работы выполняет заданную программу, а программа является некоторым алгоритмом, записанным в специальных обозначениях. Соответствующую систему обозначений называют языком программирования. Точнее, язык программирования - это совокупность средств и правил представления алгоритма в виде, приемлемом для компьютера. Число используемых языков программирования сейчас достаточно велико. Среди наиболее распространенных следует в первую очередь назвать такие языки, как Фортран, Алгол, Бейсик, Лисп, Паскаль, Модула, Си, Ада.

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

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

Алгоритм - это сформулированное на некотором языке правило, указывающее на действия, последовательное выполнение которых приводит от исходных данных к искомому результату. Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ. Однако любой алгоритм, в отличие от рецепта или способа, обязательно обладает следующими свойствами..

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

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

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

Массовость, или универсальность, означает возможность его решать серию однотипных задач при различных начальных условиях.

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