Определение и свойства алгоритма

Школа № 65

Класс 9 «в» дата_________

Тема:

Определение и свойства алгоритма

Цели:

1) образовательные

o  Повторить пройденный материал по темам: «Управление и кибернетика», «Управление с обратной связью»;

o  Изучить новую тему: «Определение и свойства алгоритма»;

o  Помочь учащимся усвоить понятие алгоритма, свойства алгоритмов;

o  Обучить составлению алгоритмов для управления исполнителем.

2) воспитательные

o  Воспитание информационной культуры учащихся, внимательности, дисциплинированности;

3) развивающие

o  Развитие внимания, памяти и алгоритмического мышления;

o  Развитие познавательного интереса.

Тип занятия

комбинированный

Методы обучения

1)  Лекция

2)  Объяснительно - иллюстративный

3)  Фронтальный опрос

Оборудование урока: проектор для показа презентации, классная доска, учебник Семакин и ИКТ. Базовый курс: Учебник для 9 класса.

План проведения занятия:

1.  Проверка домашнего задания (примеры управления с обратной связью и без); (7 мин.)

2.  Объяснение новой темы:«Определение и свойства алгоритма»(31 мин.)

2.1)  Рассказать про происхождение понятия «алгоритм»;

2.2) Ознакомить учащихся с различными определениями термина «алгоритм»;

2.3) Объяснить учащимся, что такое алгоритмический язык;

2.4) Объяснить свойства алгоритма: дискретность, понятность, точность (детерминированность), конечность, результативность, массовость;

3. Подвести итоги урока; (5 мин.)

4. Дать домашнее задание. (2 мин.)

Ход занятия

1.  Проверка домашнего задания (примеры управления с обратной связью и без);

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

2.  Объяснение новой темы: «Определение и свойства алгоритма»

2.1) Рассказать про происхождение понятия «алгоритм»

В 1987 году отмечалось 1200-летие со дня рождения ученого из Средней Азии Мухаммеда аль-Хорезми, который был из государства Хорезм (сейчас территория Узбекистана). Он написал ряд трактатов по арифметике и алгебре, которые произвели в те времена огромное впечатление на математиков.

Само слово «Алгоритм» происходит от имени Мухаммеда аль-Хорезми, который называл этим словом арифметические операции (+;-;*; :) с многозначными числами. Сейчас эти «алгоритмы» изучают в начальной школе, но тогда это было величайшим достижением.

Современное понятие алгоритма было дано в 30-50-х гг. 20 века в работах Тьюринга, Поста, Н. Винера.

Что же такое алгоритм?

2.2) Ознакомить учащихся с различными определениями термина «алгоритм»

Точного определения алгоритма нет. Приведем несколько определений алгоритма.

Школьное определение

Алгоритм - это:

1)  последовательность команд управления каким-либо объектом (Семакин);

2)  строго детерминированная (разбитая, расчлененная) последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд (Угринович).

Определение из словаря:

Алгоритм - это:

1)  план того, что должно быть сделано, выполнено;

2)  это последовательность действий, направленных на получение определённого результата за конечное число шагов;

3)  закодированная информация, вводимая в компьютер для управления его деятельностью.

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

Вы наверно не задумывались, сколько знаете алгоритмов. Приведем еще несколько примеров алгоритма:

o  в предмете русского языка – это различные правила правописания;

o  в математике – это, например, решение квадратного уравнения;

o  в обычной жизни: путь от дома до школы.

Учащиеся приводят еще несколько своих примеров алгоритма.

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

  А что такое программа? Отличается ли программа от алгоритма?

  Программа – это алгоритм, записанный на языке исполнителя.

Иначе можно сказать так: алгоритм и программа не отличаются по содержанию, но могут отличаться по форме. Для алгоритма строго не определяется форма его представления. Но программа должна быть записана на языке исполнителя.

2.3) Объяснить свойства алгоритма: дискретность, понятность, точность (детерминированность), конечность, результативность, массовость.

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

Конечность – исполнение алгоритма должно завершиться за конечное число шагов.

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

Точность (детерминированность) – каждая команда алгоритма должна определять однозначное действие исполнителя.

Результативность – каждый шаг алгоритм (как и весь алгоритм в целом) должен приводить к определенному результату.

Массовость – алгоритм применим к определенному классу задач.

Приведем пример алгоритма и на нем рассмотрим свойства алгоритма.

Алг Алгоритм открывания двери

нач

1.  Достать ключ.

2.  Вставить ключ в замочную скважину.

3.  Повернуть ключ 2 раза против часовой стрелки.

4.  Вынуть ключ.

кон

У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Такой перечень называется системой команд исполнителя (СКИ).

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

Если вы можете выполнить все шаги алгоритма «Открывание двери» (см. выше), то в Вашу СКИ входит каждая из этих команд.

Например, повару нельзя доверить работу бухгалтера, потому что у повара одна СКИ (варить супы, делать фирменные блюда), а у бухгалтера другая (делать бухгалтерские расчеты).

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

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

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

Только имея полный набор данных можно решить задачу.

Задача:

Исполнитель умеет:

1.  умножать число на 2

2.  увеличивать число на единицу

Составьте для этого исполнителя алгоритм на школьном АЯ для получения числа 100 из единицы.

Как достичь искомого результата за 8 и 15 шагов?

Задача:

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

2.4) Объяснить учащимся, что такое алгоритмический язык

Алгоритм записывается на алгоритмическом языке (АЯ). Для нас с Вами – это школьный алгоритмический язык.

Программа записывается на языке программирования.

Приведем несколько примеров языков программирования:

o  Turbo Pascal;

o  C++;

o  Java;

o  BASIC;

o  Perl;

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

Математическая модель этого алгоритма будет выглядеть так:

Алг Квадратные корни

нач

1.  Если , то вычислить значение выражения (дискриминант уравнения).

2.  Обозначить результат буквой d.

3.  Вычислить значение выражения (–b+ )/2a и обозначить результат x1.

4.  Вычислить значение выражения (–b– )/2a и обозначить результат x2.

5.  Сообщить числа x1 и x2.

кон

Из примера видно, что при записи алгоритма на АЯ в начале пишется заголовок, который начинается со служебного слова алг. Затем указывается название алгоритма.

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

Задачи:

n  Петя и Коля играют в следующую игру: Петя задумывает правило преобразования текстовой информации. Задача Коли – отгадать это правило. Попробуйте отгадать, какое правило задумал Петя и напишите алгоритм преобразования на школьном алгоритмическом языке:

1)  А → Б; мама → нбнб;  ЭВМ → ЮГН; язык → аиьл;

2)  А → А;   мама → амам; ЭВМ   → ВМЭ; язык → зыкя;

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

1)  1 →   0;  5 → 4;  0 → -1;  1990 → 1989;

2)  1 → 1;  7 → 1;  10 → 2;  187 → 3;  1990 → 4;

3. Подвести итоги урока

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

4. Дать домашнее задание

Внимательно прочитать § 27, дорешать задачи, которые не успели решить в классе.

Подготовиться к самостоятельной работе по теории и практике.

Учитель

Методист