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

1.

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

2.

«Алгоритм» является базовым основополагающим
понятием
информатики,
а
алгоритмизация
и
программирование
–
основным
разделом
курса
информатики (ядром курса). Единого определения понятия
алгоритма нет. Первоначально под алгоритмом понимали
способ выполнения арифметических действий над
десятичными числами. В дальнейшем алгоритмом стали
называть точное предписание, определяющее порядок
действий,
обеспечивающий
получение
требуемого
результата из исходных данных за конечное число шагов.

3.

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

4.

Основными свойствами алгоритма являются:
1. Результативность. Алгоритм имеет некоторое число входных величин
– аргументов, задаваемых до начала работы. Цель выполнения алгоритма
– получение результата (результатов), имеющего вполне определенное
отношение к исходным данным. Можно сказать, что алгоритм указывает
последовательность действий по преобразованию исходных данных в
результаты.
2. Массовость. Для алгоритма можно брать различные наборы
данных, т.е. использовать один и тот же алгоритм для решения
целого класса однотипных задач. Вместе с тем существуют
алгоритмы, которые применимы только к единственному набору
исходных данных.

5.

3. Понятность. Чтобы алгоритм можно было выполнить, он должен
быть понятен исполнителю. Понятность алгоритма означает знание
исполнителя алгоритма о том, что надо делать для его исполнения.
4. Дискретность. Алгоритм представлен в виде конечной
последовательности шагов.
5. Конечность. Выполнение алгоритма заканчивается после
выполнения конечного числа шагов. При выполнении
алгоритма некоторые его шаги могут выполняться
многократно.

6.

6. Определенность. Каждый шаг алгоритма должен
быть четко и недвусмысленно определен и не должен
допускать произвольной трактовки исполнителем.
7. Эффективность. Алгоритм должен быть
эффективен – значит, действия исполнителя на
каждом шаге исполнения алгоритма должны быть
достаточно простыми, чтобы их можно было
выполнить точно и за конечное время.

7.

Любой алгоритм существует не сам по себе, а предназначен для
определённого исполнителя (человека, робота, компьютера, языка
программирования и т.д.). Свойством, характеризующим любого
исполнителя, является то, что он умеет выполнять некоторые команды.
Совокупность команд, которые данный исполнитель умеет выполнять,
называется системой команд исполнителя. Алгоритм описывается в
командах исполнителя, который будет его реализовывать. Объекты, над
которыми исполнитель может совершать действия, образуют так
называемую среду исполнителя. Исходные данные и результаты любого
алгоритма всегда принадлежат среде того исполнителя, для которого
предназначен алгоритм.

8.

Способы описания алгоритмов
В настоящее время используются следующие способы описания алгоритмов:
- словесно-формульное описание алгоритма (Достоинства этого способа:
общедоступность, возможность описывать алгоритм с любой степенью
детализации. Недостаток этого способа – многословность, низкая наглядность,
громоздкость, возможна неоднозначность толкования).
Пример. Рассмотрим классический алгоритм Евклида для нахождения наибольшего общего
делителя двух натуральных чисел:
1. Если числа равны, то взять первое число в качестве ответа и закончить выполнение алгоритма,
иначе перейти к п.2.
2. Определить большее из двух чисел.
3. Заменить большее число на разность большего и меньшего чисел.
4. Перейти к п. 1.

9.

- Псевдокод (Псевдокод представляет собой систему обозначений и правил, предназначенную для
единообразной записи алгоритмов. Он занимает промежуточное место между естественным и
формальным языком)
Пример нахождения числа гласных букв в тексте:
алгоритм числогласных;
начало
записать в счетчик 0;
установить указатель на первый символ текста;
пока символ не есть $
повторять
начало
если символ есть гласная буква русского алфавита
то счетчик увеличить на 1
все;
перевести указатель на следующий символ текста
конец;
взять число, находящееся в счетчике, в качестве ответа
стоп
конец

10.

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

11.

Транслятор выполняет следующие основные функции:
1. Производит синтаксический анализ исходного текста программы,
т.е. выделяет все основные компоненты, из которых состоит
программа. В процессе этого анализа выявляются всевозможные
ошибки в исходном тексте. Такие ошибки называются
синтаксическими (связанными с неправильной записью программы на
исходном языке программирования, например, с использованием
недопустимых операторов или недопустимых последовательностей
символов, отсутствием необходимых описаний объектов языка и т.д.);
2. Производит генерацию машинной команды – непосредственную
трансляцию исходной программы на машинный язык.

12.

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

13.

14.

15.

16.

Структуры алгоритмов
1. Простые команды. Элементарной структурной единицей любого алгоритма
является простая команда, обозначающая один элементарный шаг обработки или
отображения информации (Например, команда x:=1 означает, что переменной х
присваивается значение 1, а команда y:=y+1 - что переменной y присваивается
значение, которое на 1 больше прежнего ее значения.)
2. Составные команды. Из простых команд и проверки условий образуются
составные команды, имеющие более сложную структуру.
Команда следования. Эта команда образуется из последовательности команд,
следующих одна за другой.
начало
<действие>;
<действие>; ………
...;
<действие> ………
конец

17.

Команда ветвления. С помощью этой команды, которую еще называют
развилкой осуществляется выбор одного из двух возможных действий
в зависимости от условия.
ДА
ДА
НЕТ
условие
условие
Действие1
НЕТ
Действие2
Действие1

18.

Команда повторения (цикл). Большинство алгоритмов содержат серии многократно
повторяемых команд.
НЕТ
Тело цикла
условие
ДА
ДА
условие
Тело цикла
НЕТ
3. Комбинации базовых команд.
4. Вспомогательные (подчиненные) алгоритмы. (Часто при построении
алгоритма оказывается возможным использовать уже разработанные ранее алгоритмы. )

19.

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

20.

Типы алгоритмов
1) Линейный алгоритм:
2) Разветвляющийся алгоритм:
3) Циклический алгоритм:

21.

Общими правилами при проектировании схем являются
следующие правила:
1. Каждая схема должна начинаться и заканчиваться символами,
обозначающими начало и окончание алгоритма. В алгоритме должен
быть только один символ начала и один символ окончания.
2. В начале алгоритма должны быть символы ввода значений входных
данных.
3. После ввода значений входных данных могут следовать символы
обработки и символы условия.
4. В конце алгоритма должны располагаться символы вывода значений
выходных данных.

22.

Пример.
Вычислить: С =