Файл: Алгоритм и его свойства. Запись алгоритмов. Виды алгоритмов.doc

Алгоритм и его свойства. Запись алгоритмов. Виды алгоритмов

Цель урока:

1. 
   Дать понятие алгоритму и его свойствам. Проверить знания прошлого урока.
   
2. 
   Воспитание умения слушать учителя.
   
3. 
   Развитие познавательного интереса.
   

План урока:

1. 
   Постановка цели урока.
   
2. 
   Проверка домашнего задания.
   
3. 
   Объяснение нового материала.
   
4. 
   Примеры алгоритмов.
   
5. 
   Домашняя работа.
   
6. 
   Подведение итогов урока.
   

Ход урока

• Проверка домашнего задания.

• Постановка цели урока.

• Объяснение нового материала.

В 1983 году отмечалось 1200-летие со дня рождения величайшего средневекового ученого Средней Азии Мухамеда ибн Мусы аль-Хорезми. С именем этого ученого связано понятие алгоритма. Итак, Алгоритм - это определённая последовательность действий, которые необходимо выполнить, чтобы получить результат. Алгоритм может представлять собой некоторую последовательность вычислений, а может - последовательность действий нематематического характера. Для любого алгоритма справедливы общие закономерности - свойства алгоритма.

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

1. 
   Дискретность.
   
2. 
   Понятность
   
3. 
   Детерминированность
   
4. 
   Массовость
   
5. 
   Результативность
   

Дискретность - это свойство алгоритма, когда алгоритм разбивается на конечное число элементарных действий (шагов).

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

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

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

Результативность – свойство, при котором любой алгоритм в процессе выполнения должен приводить к определённому результату. Отрицательный результат также является результатом.

СВОЙСТВА АЛГОРИТМОВ(подробнее)

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

---

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

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

2. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.

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

Запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных составителем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации

---

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

Отмеченное свойства алгоритмов называют определенностью или детерминированностью.

4. Обязательное требование к алгоритмам - результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует - тоже результат.

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

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

Основные блоки алгоритмов.



Все имеющиеся алгоритмы можно разделить на три вида:

• 
  линейные алгоритмы;
  
• 
  алгоритмы ветвления;
  
• 
  циклические алгоритмы.
  

В примере алгоритма “Телефонный разговор” имеются все три вида алгоритмов, хотя пример носит не математический характер. Если задача решается с помощью математического аппарата, то в зависимости от степени сложности задачи, чаще всего используется также три вида алгоритмов: линейные, ветвление и циклы. Для решения любых задач достаточно этих трех видов алгоритмов.

---

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

Домашнее задание.

1. 
   Вычислить площадь полной поверхности и объём цилиндра, если D-диаметр его основания. а H - высота. Составить алгоритм.
   
2. 
   В рассказе А.П.Чехова "Репетитор". Репетитор, гимназист 7 класса Егор Зиберов задаёт своему ученику Пете Удотову задачу - "Купец купил 138 аршин чёрного и синего сукна за 540 рублей .Сколько аршин купил он того и другого, если синее стоило 5 рублей за аршин, чёрное 3 рубля?". Составить алгоритм этой задачи.
   

Подведение итогов урока

---