Презентация "Основные понятия алгоритмизации"

Скачать материал

Подписи к слайдам:

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

Учитель информатики
МБОУ «Софринская СОШ № 2»
Муравьёва Л. В.

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

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

Крестьянин стоит на левом берегу реки с волком, козой и капустой. Ему нужно перевезти все это на правый берег. Но его лодка слишком мала: он может взять только одного пассажира – либо волка, либо капусту, либо козу. Как тут поступить?

Составим план:

1). Перевези козу
2). Переправься
3). Перевези волка
4). Перевези козу
5). Перевези капусту
6). Переправься
7). Перевези козу.

План решения задачи в информатике называют алгоритмом.

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

Примеры алгоритмов

Рецепт приготовления различных блюд.
Инструкция по использованию электроприбора.
Правило возведения числа в степень.
Решение квадратных уравнений.

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

Дискретность
Детерминированность
Понятность
Массовость
Результативность

Дискретность

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

Налить в чайник воду.
Зажечь спичку.
Открыть кран газовой горелки.
Поднести спичку к горелке.
Поставить чайник на плиту.
Ждать, пока вода закипит.
Выключить газ.

Детерминированность

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

Понятность

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

Массовость

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

Результативность

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

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

Выбор средств и методов для записи алгоритма зависит прежде всего от назначения самого алгоритма, а также от того, кто будет исполнять алгоритм.

Словесный способ
Графический способ (блок-схемы)
Описание алгоритмов с помощью программ

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

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

Алгоритм нахождения максимального из двух значений

1 . Определим форматы переменных X, Y, M, где X и Y – значения для сравнения, M – переменная для хранения максимального значения;
2. Получим два значения чисел X и Y для сравнения;
3. Сравним X и Y.
4. Если X меньше Y, значит большее число Y.
5. Поместим в переменную M значение Y.
6. Если X не меньше (больше) Y, значит большее число X.
7. Поместим в переменную M значение X.

Графический способ описания алгоритмов (блок-схемы)

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

Основные типы блоков

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

Алгоритм нахождения максимального из трёх значений Описание алгоритмов с помощью программ

Программа - алгоритм, записанный на языке программирования.
Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования (языке, понятном ЭВМ) .
Наиболее популярные языки:
Си
Паскаль
Delphi
Бэйсик

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

В зависимости от порядка выполнения команд алгоритмы бывают:

Линейные
Разветвляющиеся
Циклические

Линейные алгоритмы

Линейный алгоритм – алгоритм, в котором исполнитель все команды выполняет одну за другой в порядке их записи.
Примеры:

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

Примеры линейных алгоритмов

Как открыть дверь
1. Достать ключ.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ 2 раза против часовой стрелки.
4. Вынуть ключ.

Как проехать к другу
1. Выйти из дома.
2. Повернуть направо.
3. Пройти 2 квартала до автобусной остановки.
4. Сесть в автобус № 25, идущий
к центру города.
5. Проехать 3 остановки.
6. Выйти из автобуса.

Задача: вычислить площадь круга. Дано: R – радиус круга. Требуется: S – площадь круга. Связь: S=3,14*R2.

1. Прочесть значение R.
2. S:=3,14*R*R
3. Записать значение S.

начало

конец

ввод R

вывод S

S:=3.14*R*R

Разветвляющиеся алгоритмы

Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого происходит переход на один из двух возможных шагов.
Примеры:

Нахождение корней квадратного уравнения.
Нахождения min, max двух чисел.
Выбор просмотра программы телепередач.

Алгоритм нахождения максимального из двух чисел

1 . Прочесть значения переменных a, b
2. Сравним a и b.
3. Если a больше b, то поместим в переменную max значение a, иначе поместим в переменную max значение b.
4. Записать значение max.