Основы алгоритмизации

Задачи главы

• 1. Изучить понятие алгоритма.
• 2. Изучить свойства алгоритма.
• 3. Рассмотреть типы алгоритмических моделей.
• 4. Освоить способы описания алгоритмов.
• 5. Получить представление о методах разработки алгоритмов.

После изучения главы 1 бакалавр должен: знать

• • современные возможности реализации алгоритмов;
• • принципы построения алгоритмов; уметь
• • составлять блок-схемы алгоритмов;
• • составлять программы на алгоритмическом языке высокого уровня;
• • работать в интегрированной среде изучаемых языков программирования;

владеть

• практическими навыками разработки и реализации алгоритмов обработки различных данных.

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

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

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

• 1) присвоить переменным X и У значения, НОД которых ищется;
• 2) если X > У, то перейти на шаг 5;
• 3) если X < У, то перейти на шаг 6;
• 4) здесь X = У. ВыдатьX в качестве результата. Конец работы;
• 5) заменить пару (X, У) парой (X - У, У) и вернуться на шаг 2;
• 6) заменить пару (X, У) парой (X, Y-Х) и вернуться на шаг 2.

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

Вычисления протекают во времени и в пространстве. Каждый шаг алгоритма выполняется за какое-то конечное время. Для размещения данных необходимо пространство — память. Рассмотрим основные свойства алгоритма.

Авторы: Трофимов Валерий, Павловская Татьяна