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

МОУ «Торосовская основная общеобразовательная школа»

Алгоритм

Введение

• Сегодня вы изучите понятие алгоритма, узнаете о его свойствах, видах и способах описания. Для этого вам нужно: - внимательно прочитать весь изложенный материал; - записать и зарисовать в тетрадь все, что написано красным шрифтом; - выполнить все задания, выделенные светло-коричневым цветом.
• Не забудьте, что учитель обязательно проверит ваши записи и выставит за них оценку.
• Для того, чтобы перейти на следующую страницу или вернуться назад пользуйтесь кнопками
• Удачи вам!

Алгоритм

• Понятие алгоритма
• Свойства алгоритмов
• Способы описания алгоритмов
• Типы алгоритмов
• Правила построения блок-схем

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

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

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

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

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

• Рассмотрим этот вопрос на примере. Задача: вычислить площадь круга. Дано: R-радиус круга. Найти: S-площадь круга. Формула:
• Словесный (для всех типов алгоритмов). Такое описание состоит из словесного перечня шагов алгоритма. Каждый шаг имеет свой номер. Если в тексте алгоритма написано «перейти к шагу с номером №», то это означает, что выполнение алгоритма продолжится с шага №. Алгоритм: 1. Прочесть значение R. 2. Возвести R в квадрат. 3. Умножить результат шага 2 на 3,14. 4. Записать результат шага 3 как значение S.

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

• Табличный (для линейных алгоритмов). Алгоритм представляется в виде таблицы, где названия столбцов (строк) являются командами алгоритма. Количество столбцов - количество шагов алгоритма, их последовательность строго определена. Число шагов конечно. Алгоритм:

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

НАЧАЛО R S

КОНЕЦ

• Графический (для всех типов алгоритмов). Этот способ описания основан на замене команд алгоритма определенными геометрическими фигурами.
• На рисунке представлена блок-схема алгоритма решения нашей задачи.
• Далее приведен перечень наиболее часто употребляемых в блок-схемах алгоритмов геометрических фигур.

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

• Начало-конец. Блок, обозначающий начало или конец алгоритма.
• Ввод-вывод. Блок, обозначающий ввод данных или вывод результатов.
• Процесс. Арифметический блок, определяющий действия, которые необходимо выполнить.
• Принятие решения. Логический блок, проверяющий истинность или ложность некоторого условия.
• Соединитель. Указание связи между прерванными линиями потока информации,связывающими блоки алгоритма.
• Комментарий. Используется для пояснений.

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

• Блоки соединяются линиями потока информации (стрелками), которые определяют направление вычислений.
• Блок-схема алгоритма записывается строго сверху вниз. Если снизу не хватает места, то оставшуюся часть алгоритма можно перенести рядом или на другую страницу следующим образом:
• Составьте алгоритм решения задачи (три способа). Задача: вычислить значение суммы двух чисел. Дано: a,b. Найти: s.

1

начало

Действие 2

Ввод данных

Вывод результата

Действие 1

конец

1

Типы алгоритмов

• Известны три типа алгоритмов - линейный, разветвляющийся и циклический.
• Линейный алгоритм - алгоритм, состоящий из последовательности операций, которые выполняются только один раз в порядке их следования.

начало

...

Действие 1

Действие 2

Действие 3

...

конец

Типы алгоритмов

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

...

...

б)

а)

да

да

условие

условие

нет

нет

Действие

Действие 2

Действие 1

...

...

Типы алгоритмов

• Циклический алгоритм - алгоритм, содержащий некоторую последовательность операций, которая многократно выполняется.

...

...

а)

б)

да

действие

условие

нет

да

условие

действие

нет

Выход из цикла

Выход из цикла

Правила построения блок-схем

1. Каждая блок-схема должна иметь точку начала и окончания.

2. От точки начала блоки располагаются сверху-вниз и слева-направо.

3. Блоки связываются друг с другом с помощью линий потока, определяющих

последовательность обработки данных.

4. Линии потока, входящие в блок, указывают последовательность выполнения

операций данного блока.

Линии потока, выходящие из блокауказывают, каким блокам может передавать

направление данный блок.

5. Если блок показывает разветвление на схеме алгоритма, то из него должно

выходить не менее 2-х линий.

Правильно составленной считается такая блок схема, в которой, следуя из точки

начала можно пройти по направлению линий потока в точку окончания по каждой

из имеющихся в блок-схеме ветвей.

Вопросы для самоконтроля

• Как произошел термин «алгоритм»?
• Что называют алгоритмом?
• Какими свойствами должен обладать алгоритм?
• Какие способы описания алгоритмов вы знаете?
• Какие типы алгоритмов вы знаете?
• Какую блок-схему называют правильно составленной ?

Выход

Начало