Вид занятия: УУНЗ (лекция).
План:
-
Понятие алгоритма.
-
Свойства алгоритма.
-
Формы записи алгоритмов
-
Блок-схема.
- Основные элементы блок-схемы.
- Правила выполнения схем алгоритмов.
1. Понятие алгоритма.
Одним из фундаментальных понятий в информатике является понятие алгоритм. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которго европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первые алгоритмы в математике.
В наше время понятие алгоритма трактуется шире.
Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
С алгоритмами мы имеем дело постоянно. И рецепты приготовления блюд, и нотные записи музыкальных произведений, и описание того, как вычислить корни квадратного уравнения по его коэффициентам, – всё это алгоритмы.
Пример 1. Алгоритм «Заварка чая»:
- Вскипятить воду в чайнике.
- Положить в пустую чайную чашку пакетик чая.
- Залить чашку горячей водой.
- Подождать 1 минуту.
- Вытащить пакетик.
- Положить в чашку 2 чайных ложки сахара.
- Размешать сахар.
Пример 2. Алгоритм «Приготовь яичницу»:
- Достать яйцо и масло.
- Включить плиту.
- Поставить сковороду на плиту.
- Растопить на сковородке масло.
- Взять нож.
- Разбить ножом яйцо над сковородкой.
- Выбросить скорлупу в мусорное ведро.
- Жарить яичницу 5 минут.
- Выключить плиту.
Но не следует считать, что любая задача поддаётся алгоритмизации. Задачи, для которых невозможно составить общий алгоритм решения, получили название алгоритмически неразрешимыми.
Создателей алгоритмов называют программистами, а тех, кто по алгоритмам выполняет действия, – исполнителями. В широком смысле программистами можно считать и композиторов, и авторов кулинарных рецептов. Соответственно музыканты, играющие по нотам, и хозяйки, которые готовят по рецептам, – исполнители.
Исполнитель алгоритма – это объект или субъект, для управления которым составлен алгоритм.
В качестве исполнителей могут быть как живые существа, так и технические устройства. В частности, автоматическим исполнителем алгоритмов по обработке информации является компьютер.
Пример 3. Исполнители алгоритмов:
- Компьютер
- Солдат
- Автомобиль
- Дрессированный лев
Но между человеком и автоматическим устройством есть существенная разница. Если для человека имеют значение не только указания, которые даны в алгоритме, но и большой фактор заложен в степени эмоциональности изложения, то для компьютера или другого устройства имеет значение – понимает он данную команду или нет. Выполнив необходимые действия, алгоритмическое устройство прекращает работу.
Поэтому исполнителя, выполняющего команды определённого алгоритма без анализа действий и ситуаций, называют формальным исполнителем.
Исполнителя алгоритма характеризует среда его «обитания» и система команд исполнителя (СКИ).
Среда исполнителя – обстановка, в которой функционирует исполнитель.
Система команд исполнителя (СКИ) – это вся совокупность команд, которую может выполнить исполнитель.
СКИ считается полной, если содержит весь минимально-необходимый набор команд, позволяющий построить любой алгоритм в том классе задач, на который ориентирован исполнитель.
Пример 4. Некоторые команды из СКИ исполнителя «DVD-плеер»:
- начать воспроизведение
- пауза
- остановить воспроизведение
- увеличить громкость
- уменьшить громкость
- ускоренное воспроизведение назад
- ускоренное воспроизведение вперёд
- покадровое воспроизведение
- выбор языка
2. Свойства алгоритмов.
Любой алгоритм должен удовлетворять основным свойствам::
- Конечность (результативность)
- Дискретность
- Понятность
- Точность (определённость)
- Корректность
- Массовость
Конечность алгоритма означает, что за конечное число шагов должен быть получен результат. Поэтому иногда это свойство называют результативностью.
Пример 5. Пусть имеется последовательность команд:
- Взять книгу
- Открыть первую страницу
-
Пока не конец книги выполнить следующие действия:
- Прочитать текст
- Перелистнуть книгу на следующую страницу
- Прочитать текст
- Открыть первую страницу
Легко догадаться, что данная последовательность команд будет выполняться бесконечно и поэтому алгоритмом не является.
Чтобы данный алгоритм стал конечным, надо исключить из него пункты c и d.
Дискретность означает, что алгоритм должен быть разбит на последовательность отдельно выполняемых шагов.
Пример 6. Пусть необходимо решить следующий пример: (80+10)-5*(3+5)=
Запишем алгоритм решение примера, разбив его на шаги:
- Вычислить 80+10
- Вычислить 3+5
- Умножить 5 на результат предыдущего действия
- Вычесть из результата 1-го действия результат 3-го действия
В результате выполнения алгоритма получим 50.
Понятность алгоритма означает, что алгоритм должен содержать только те команды, которые входят в СКИ.
Если в данном алгоритме начать, например, выполнять четвёртое действие, не дожидаясь окончания выполнения третьего, то результат не может быть получен.
Понятность алгоритма означает, что алгоритм должен содержать только те команды, которые входят в СКИ.
Пример 7. Рассмотрим алгоритм:
- Пойти на кухню
- Вскипятить чайник
- Насыпать в чашку 1 чайную ложку кофе
- Положить в чашку 3 чайных ложки сахара
- Налить полную чашку кипячёной воды
Очевидно, что он легко может быть выполнен 10-летней девочкой, которая понимает все команды, входящие в данный алгоритм. Однако, для 10-месячного малыша данный алгоритм будет непонятен.
Точность (определённость) алгоритма означает, что любая его команда должна определять однозначное действие исполнителя. Иными словами, алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем.
Пример 8. Рассмотрим следующий алгоритм, описывающий, как добраться до стадиона:
- Идти прямо
- Повернуть
- Идти прямо
- Сесть на автобус
- Доехать до остановки «Стадион»
Данный алгоритм не уточняет, какое расстояние нужно пройти прямо, в какую сторону повернуть, на какой автобус сесть, поэтому разные исполнители будут выполнять его по-разному и цель вряд ли будет достигнута.
Массовость – лгоритм должен быть пригоден для решения не только одной конкретной задачи, а так же для реализации целого класса родственных задач.
Корректность – свойство алгоритма, заключающееся в способности алгоритма давать правильные результаты при различных исходных данных.
3. Формы записи алгоритма.
Не зная нотной грамоты, не сыграть по нотам; не разбираясь в названиях продуктов и кухонной посуды, не приготовить блюда. Поэтому алгоритмы всегда записываются так, чтобы исполнители их понимали и могли их выполнить. Это значит что есть правила записи алгоритмов, и эти правила должен знать как программист, так и исполнитель.
Для записи алгоритмов используют несколько способов:
- словесный
- графический
- программный
Самый простой способ – словесный – это способ записи алгоритма на естественном языке, но с тщательно отработанным набором слов и фраз, не допускающих повторений, синонимов, двусмысленности, лишних слов. Допускается использование математических символов.
Пример 9. Алгоритмы, записанные словесным способом: поваренная книга, инструкция к телевизору.
При графическом способе описания алгоритма осуществляется с помощью блок-схем.
Программный способ – это запись алгоритма на языке программирования (в виде компьютерной программы).
Пример 10. Алгоритм, записанный на языке программирования TURBO PASCAL.
4. Блок-схема .
Блок-схема – это графический способ представления алгоритма, каждое действие при этом осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками.
а) Основные элементы блок-схемы.
В таблице приведены наиболее часто употребляемые блоки:
Таблица 1. Основные элементы блок-схем
б) Правила выполнения схем алгоритмов.
Правила выполнения схем алгоритмов регламентирует ГОСТ 19.002-80 (единая система программной документации):
- Блоки на схемах соединяются линиями потоков информации.
- Основное направление потока информации идёт сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и справа на лево – стрелка обязательна.
- Количество входящих линий для блока не ограничено.
- Выходящая линия должна быть одна (исключение составляет логический блок).
Написать письмо
