дата__________ класс_________
УРОК 2
ПОНЯТИЕ
АЛГОРИТМА, СВОЙСТВА АЛГОРИТМОВ,
СПОСОБЫ
ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
Цели: 1. Обучать
основам программирования.
2. Развивать
логическое мышление.
3. Воспитывать интерес
к предмету.
Проверка домашнего задания
Ход урока
Понятие
алгоритма
Понятие алгоритма является одним
из основных понятий современной математики. Еще на самых ранних ступенях
развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать
различные вычислительные процессы чисто механического характера. С их помощью
искомые величины ряда задач вычислялись последовательно из исходных величин по
определенным правилам и инструкциям. Со временем все такие процессы в
математике получили название алгоритмов (алгорифмов).
Термин алгоритм происходит от имени средневекового
узбекского математика Аль-Хорезми, который еще в IX в. (825) дал правила
выполнения четырех арифметических действий в десятичной системе счисления.
Процесс выполнения арифметических действий был назван алгоризмом.
С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого
состоял в комбинировании четырех операций арифметического исчисления -
сложения, вычитания, умножения, деления.
К 1950 г. алгорисмус стал алгорифмом.
Смысл алгорифма чаще всего связывался с алгорифмами Евклида - процессами
нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей
меры двух отрезков и т.п.
Под алгоритмом понимали конечную
последовательность точно сформулированных правил, которые позволяют решать те
или иные классы задач. Такое определение алгоритма не является строго
математическим, так как в нем не содержится точной характеристики того, что
следует понимать под классом задач и под правилами их решения.
Первоначально для записи
алгоритмов пользовались средствами обычного языка (словесное представление
алгоритмов).
Уточним понятие словесного
представления алгоритма на примере нахождения произведения n натуральных чисел
- факториал числа и (с = n!), т.е. вычисления по формуле с = 1*2*3*4-... n.
Этот процесс может быть записан в
виде следующей системы последовательных указаний (пунктов):
1. Полагаем с равным единице и
переходим к следующему пункту.
2. Полагаем i равным единице и
переходим к следующему пункту.
3. Полагаем с = i* с и переходим к
следующему пункту.
4. Проверяем, равно ли i числу n.
Если i = n, то вычисления прекращаем. Если i < n, то увеличиваем i на
единицу и переходим к пункту 3.
Рассмотрим еще один пример
алгоритма - нахождение наименьшего числа М в последовательности из n чисел a1,
a2, ..., an (n0). Прежде чем записать словесный алгоритм данного примера,
детально рассмотрим сам процесс поиска наименьшего числа. Будем считать, что
процесс поиска осуществляется следующим образом. Первоначально в качестве числа
М принимается a1 т. е. полагаем М = a1, после чего М сравниваем с последующими
числами последовательности, начиная с a2. Если М < a2, то М сравнивается с
a3, если М < а3, то М сравнивается с a4, и так до тех пор, пока найдется
число ai < М. Тогда полагаем М = ai и продолжаем сравнение с М последующих
чисел из последовательности, начиная с ai+1, и так до тех пор, пока не будут
просмотрены все n чисел. В результате просмотра всех чисел М будет иметь
значение, равное наименьшему числу из последовательности (i- текущий номер
числа). Этот процесс может быть записан в виде следующей системы
последовательных указаний:
1. Полагаем i = 1 и переходим к
следующему пункту.
2. Полагаем М = ai, и переходим к
следующему пункту.
3. Сравниваем i с n; если i <
n, переходим к 4 пункту, если i = n,
процесс поиска останавливаем.
4. Увеличиваем i на 1 и переходим
к следующему пункту.
5. Сравниваем ai, с М. Если М ai,
то переходим к пункту 3, иначе
(M > ai) переходим к пункту 2.
В первом алгоритме в качестве
элементарных операций используются простейшие арифметические операции
умножения, которые могли бы быть разложены на еще более элементарные операции.
Мы такого разбиения не делаем в силу простоты и привычности арифметических
правил.
Алгоритмы,
в соответствии с которыми решение поставленных задач сводится к арифметическим
действиям, называются численными алгоритмами.
Алгоритмы,
в соответствии с которыми решение поставленных задач сводится к логическим
действиям, называются логическими алгоритмами. Примерами логических
алгоритмов могут служить алгоритмы поиска минимального числа, поиска пути на
графе, поиска пути в лабиринте и др.
Алгоритмом,
таким образом, называется система четких однозначных указаний, которая
определяет последовательность действий над некоторыми объектами и после
конечного числа шагов приводит к получению требуемого результата.
Свойства
алгоритмов
Каждое указание алгоритма
предписывает исполнителю выполнить одно конкретное законченное действие.
Исполнитель не может перейти к выполнению следующей операции, не закончив
полностью выполнения предыдущей. Предписания алгоритма надо выполнять последовательно
одно за другим, в соответствии с указанным порядком их записи. Выполнение всех
предписаний гарантирует правильное решение задачи.
Поочередное выполнение команд
алгоритма за конечное число шагов приводит к решению задачи, к достижению цели.
Разделение выполнения решения задачи на отдельные операции (выполняемые
исполнителем по определенным командам) - важное свойство алгоритмов, называемое дискретностью.
Анализ примеров различных
алгоритмов показывает, что запись алгоритма распадается на отдельные указания
исполнителю выполнить некоторое законченное действие. Каждое такое указание
называется командой.
Команды алгоритма выполняются одна за другой. После каждого шага исполнения
алгоритма точно известно, какая команда должна выполняться следующей. Алгоритм
представляет собой последовательность команд (также инструкций, директив),
определяющих действия исполнителя (субъекта или управляемого объекта).
Таким образом, выполняя алгоритм,
исполнитель может не вникать в смысл того, что он делает, и вместе с тем
получать нужный результат. В этом случае говорят, что исполнитель действует
формально, т.е. отвлекается от содержания поставленной задачи и только строго
выполняет некоторые правила, инструкции.
Это очень важная особенность алгоритмов.
Наличие алгоритма формализовало процесс, исключило рассуждения. Если обратиться
к другим примерам алгоритмов, то можно увидеть, что и они позволяют исполнителю
действовать формально. Таким образом, создание алгоритма дает возможность
решать задачу формально, механически исполняя команды алгоритма в указанной
последовательности.
Всякий алгоритм составляется в
расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы
алгоритм мог быть выполнен, нельзя включать в него команды, которые исполнитель
не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы
подробная инструкция ему не давалась. У каждого исполнителя имеется свой
перечень команд, которые он может исполнить. Совокупность команд, которые могут
быть выполнены исполнителем, называется системой
команд исполнителя. Каждая команда алгоритма должна определять однозначно
действие исполнителя. Такое свойство алгоритмов называется определенностью (или точностью)
алгоритма.
Алгоритм, составленный для
конкретного исполнителя, должен включать только те команды, которые входят в
его систему команд. Это свойство алгоритма называется понятностью. Алгоритм не должен
быть рассчитан на принятие каких-либо самостоятельных решений исполнителем, не
предусмотренных составленным алгоритмом.
Еще одно важное требование,
предъявляемое к алгоритмам, - результативность
(или конечность) алгоритма.
Оно означает, что исполнение алгоритма должно закончиться за конечное число
шагов.
Разработка алгоритмов - процесс
творческий, требующий умственных усилий и затрат времени. Поэтому
предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса
задач данного типа. Например, если составляется алгоритм решения кубического
уравнения ах3 + bх2 + сх + d - О, то он должен быть вариативен, т.е. обеспечивать
возможность решения для любых допустимых исходных значений коэффициентов а, b,
с, d. Про такой алгоритм говорят, что он удовлетворяет требованию массовости. Свойство массовости
не является необходимым свойством алгоритма. Оно скорее определяет качество
алгоритма; в то же время свойства дискретности, точности, понятности и
конечности являются необходимыми (иначе это не алгоритм).
Вопросы и домашнее
задания:
1.
Что
такое алгоритм?
2.
Какие
вы знаете свойства алгоритмов?
3.
Понятие
алгоритма.
