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

Задачи главы

  • 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.

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >