Алгоритм как модель деятельности

Алгоритм как модель деятельности

10 класс

Учитель информатики:Гериханов Шахман Хамзатович

26.02.20

• Почему алгоритм можно назвать моделью и что он моделирует?
• Алгоритм – это понятное и точное предписание конкретному исполнителю совершить конечную последователь-ность действий, приводящую к поставленной цели.
• Цель достигается через деятельность некоторого исполнителя.

Что такое алгоритмическая модель?

26.02.20

Этапы деятельности:

• Определение цели;
• Планирование работы исполнителя;
• Работа исполнителя;
• Получение результата.

Где же здесь место алгоритму?

Алгоритм – это детальный план работы исполнителя , это описание последовательности действий, которые должен совершить исполнитель.

26.02.20

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

Построение

плана-

алгоритма

Работа

исполнителя

Определение

цели

Получение

результата

Модель

работы

исполнителя

26.02.20

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

Проще построить алгоритм для программно управляемого автомата, чем для человека. Для автомата СКИ – это строго определённый набор команд на формализованном языке описания алгоритмов. Такие языки называются языками программирования , а алгоритм – программой .

СКИ человека невозможно полностью описать.

Система команд исполнителя

26.02.20

Задача:

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

например от 1 до 100.

Второй должен угадать число за наименьшее количество вопросов.

Пример алгоритмической модели.

26.02.20

Алгоритм для исполнителя-человека.

Алгоритм Угадывание числа

Дано: диапазон чисел от А до В

Надо: угадать число Х, задуманное игроком, используя алгоритм половинного деления

Начало

1.Задать вопрос: Х меньше среднего значения между А и В?

2.Если ответ «да», то принять за значение В целую часть среднего значения.

3.Если ответ «нет», то принять за значение А ближайшее целое число, большее, чем среднее.

4.Если значения А и В равны, то их общее значение и есть искомое число Х.

5. Если значения А и В не равны, то вернуться к исполнению пункта 1.

Конец

26.02.20

Алгоритм для исполнителя-компьютера.

Блок-схема

нет

да нет

начало

Ввод А,В,Х

А ≠В

Х ≤(А+В)/2

А=ЦЕЛ((А+В)/2)+1

В=ЦЕЛ((А+В)/2)

Вывод А

26.02.20

Конец

Алгоритм для исполнителя-компьютера. Алгоритмический язык

Алг Половинное деление

Цел А, В, Х

Начало

Ввод А, В, Х

Пока А ≠В, повторять

Нц

Если Х≤(А+В)/2

То В:=ЦЕЛ((А+В)/2)

Иначе А:=ЦЕЛ((А+В)/2)+1

Кц

Вывод А

Конец

26.02.20

Структура построенного алгоритма – цикл с вложенным ветвлением.

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

Если алгоритм построен структурно, то легко перейти от описания алгоритма к программе.

Структурное программирование

26.02.20

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

Выберем интервал угадываемых чисел от 1 до 8. Пусть игрок задумал число 3.

Трассировка алгоритма - модель работы процессора.

26.02.20

№

шага

№

шага

Команда

алгоритма

Команда

алгоритма

Переменные

Переменные

1

1

Выполняемые

действия

Выполняемые

действия

Ввод А, В, Х

2

2

Х А В

Х А В

Ввод А, В, Х

3 1 8

А ≠ В

3 1 8

3

3

А ≠ В

4

Х ≤ (А+В)/2

4

Х ≤ (А+В)/2

1 ≠ 8, да

В:=ЦЕЛ((А+В)/2)

5

5

В:=ЦЕЛ((А+В)/2)

1 ≠ 8, да

6

3 1 4

А ≠ В

А ≠ В

3 ≤ 4,5, да

3 ≤ 4,5, да

6

В:= 4

Х ≤ (А+В)/2

Х ≤ (А+В)/2

В:= 4

1 ≠ 4, да

1 ≠ 4, да

3 ≤ 2,5, нет

3 ≤ 2,5

26.02.20

7

А:=ЦЕЛ((А+В)/2+1)

8

3

А ≠ В

9

Х ≤ (А+В)/2

3

10

В:=ЦЕЛ((А+В)/2)

4

11

А ≠ В

3

12

А:=3

Вывод А

3

3 ≠ 4,да

3

3 ≤3,5,да

В:=3

3 ≠ 3,нет

Ответ: 3

26.02.20

• Программа выполняется по шагам (первый

столбец таблицы).

• В столбце «Команда алгоритма» отображается содержимое регистра команд процессора , куда помещается очередная команда.
• В столбце «Переменные» отображается содержимое ячеек памяти , отведённых под переменные величины.
• В графе «Выполняемое действие» отражаются действия , выполняемые арифметико-логическим устройством процессора.

Трассировка алгоритма - модель работы процессора.

26.02.20

• Таким образом, алгоритм в совокупности с трассировочной таблицей полностью моделируют процесс обработки информации, происходящий в компьютере.

Вывод:

26.02.20

Система основных понятий

Алгоритм - модель деятельности

Объект моделирования –

целенаправленная деятельность исполнителя.

Исполнитель-человек

Исполнитель-автомат(в том числе компьютер)

Неформализованная СКИ

Формализованная СКИ

Формы представления алгоритмов

Блок-схема

Учебный алгоритмический язык

Трассировка алгоритма- пошаговое исполнение алгоритма с тестовым вариантом исходных данных.

Язык программирования

«Ручная трассировка»-заполнение трассировочной таблицы.

Трассировочная таблица- модель работы процессора при исполнении алгоритма.

26.02.20