Конспект урока "Алгоритм и его формальные исполнители"

Тема: Алгоритм и его формальное исполнение. Свойства алгоритма и его исполнители.

Цели урока:

• получить представление о алгоритме и его формальном исполнении, свойствах алгоритма и его исполнителях;

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

• развитие познавательных интересов, навыков работы на компьютере, самоконтроля, умения конспектировать.

Тип урока: изучение нового материала.

Оборудование: доска, компьютер, компьютерная презентация.

Ход урока:

1.Теоретическая часть.

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

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

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

Понятие алгоритма не есть для нас что-то новое и необычное. Встречаются они в нашей повседневной жизни почти на каждом шагу. Так, утром мама перед вашим уходом в школу дает вам такую инструкцию: «Когда придешь со школы, сразу пообедай и не забудь вымыть посуду. После этого подмети пол, купи в магазине молоко и хлеб. Сделав покупки, погуляй часок и начинай выполнять домашнее задание».

Эта инструкция состоит из последовательности отдельных указаний, которые определяют ваше поведение. Это и есть — алгоритм.

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

Для приготовления омлета с сыром можно руководствоваться следующей последовательностью действий:

50 г мякоти белого хлеба намочить в 3 столовых ложках молока и размять

разбить в эту смесь 3 яйца, и все это хорошо взбить лежкой;

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

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

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

Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783–850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком», знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов

Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

• среда;

• элементарные действия;

• система команд;

• отказы.

Сpеда (или обстановка) — это «место обитания» исполнителя.

Система команд. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды.

После вызова команды исполнитель совершает соответствующее элементарное действие.

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов «почему» и «зачем».

В информатике универсальным исполнителем алгоритмов является компьютер.

Примеры исполнителей.

1. Исполнитель «Робот».

Среда обитания клетчатое поле со стенами. Система команд :вверх, вниз, вправо, влево, закрасить. Элементарные действия закрашивает клетки на поле.

2. Исполнитель «Чертежник».

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

3. Исполнитель «Квадратор», «Утроитель», «Умножитель» и т.д.

Среда обитания экран монитора. Система команд :1.возвести в квадрат, 2.прибавить 1.() Элементарные действия -действия с числами.

Основные свойства алгоритмов следующие:

1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

2. Дискpетность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).

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

4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.

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

На практике наиболее распространены следующие формы представления алгоритмов:

• словесная (запись на естественном языке);

• графическая (изображения из графических символов);

• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

• программная (тексты на языках программирования).

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

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

Такое графическое представление называется схемой алгоритма или блок-схемой.

Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. «Основы информатики и вычислительной техники», 1991. Этот язык в дальнейшем мы будем называть просто «алгоритмический язык».

Основные служебные слова

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

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

надо цель выполнения алгоритма

нач описание промежуточных величин

| последовательность команд (тело алгоритма)

Кон

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

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

Преимущества языка программирования Паскаль перед другими системами:
-краткость языка (некоторые называют его «спартанским» языком программирования);
-легкость программирования на нем;
-мобильность написанных программ;
-возможность эффективной реализации и пригодность с точки зрения формальных методов отладки программ;

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

2. Практическая часть.

АиПО: компьютер с установленной ОС Линукс .

Цель работы: научится создавать алгоритмы исполнителей Робот, Черепашка, Чертежник, Квадратор, Утроитель и т.д.

Ход работы

Задание № 1. Учебник А.Г. Кушнеренко, " Основы информатики и ВТ" стр.28-31.

Исполнитель «Робот».

Робот -работает на клетчатом поле (между клетками могут быть расположены стены) и умещается целиком в одной клетке.

Задание № 2. Учебник А.Г. Кушнеренко, " Основы информатики и ВТ" стр.32-35.

Исполнитель " Чертежник".

Чертежник — предназначен для построения рисунков, чертежей, графиков и т.д. на бесконечном листе бумаги.

4 команды:

Поднять перо

Опустить перо

Сместится в точку ( арг вещ х, y)

Сместится на вектор ( арг вещ х, y)

Разбор примера буква М

Задание № 3.

1. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножьна  3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, умножает его на 3. Запишите порядок команд в программе получения из числа 1 числа 45, содержащей не более 5 команд, указывая лишь номера команд. (например, программа 21211 — это программа, содержащая следующие команды:
умножь на3
прибавь 1
умножь на 3
прибавь 1
прибавь 1, которые преобразуют число 3 в 32)

2. У исполнителя Калькулятор две команды, которым присвоены номера:
1. вычти 3
2. умножь на 4
Выполняя первую из них, Калькулятор уменьшает число на экране на 3, а выполняя вторую, увеличивает его на 4. Запишите порядок команд в программе получения из числа 2 числа 500, содержащей не более 5 команд, указывая лишь номера команд. (например, программа 21211 — это программа, содержащая следующие команды:
умножь на 4
вычти 3
умножь на 4
вычти 3
вычти 3, которые преобразуют число 5 в 62)

3. У исполнителя Калькулятор две команды, которым присвоены номера:
1. умножь на 2
2. прибавь 3
Выполняя первую из них, Калькулятор умножает число на экране на 2, а выполняя вторую, прибавляет к нему 3. Запишите порядок команд в программе получения из числа 0 числа 30, содержащей не более 5 команд, указывая лишь номера команд. (например, программа 21211 — это программа, содержащая следующие команды:
прибавь 3
умножь на 2
прибавь 3
умножь на 2
умножь на 2, которые преобразуют число 1 в 44)

Задание 3.

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

Угринович Н.Д. Информатика и ИТ. Учебник для 9класса.§4.1.1,Стр.105-108.Ответить на вопросы