Алгоритмы. Свойства алгоритмов. 9 класс. Базовый уровень.
Конспект
С самого детства вы сталкиваетесь с алгоритмами, не осознавая этого. Алгоритмы появляются в ситуациях, которые можно описать в виде последовательности действий.
Внимание на экран. Демонстрация видеофрагмента.
Например, с утра вас призывает радио «На зарядку становись!» Вам предлагается выполнить одно из упражнений в следующей последовательности:
Вы решили зайти к другу, а у него в подъезде установлен домофон. Вы выполняете действия, следуя инструкции, вывешенной на входной двери:
1. Наберите номер квартиры.
2. Нажмите кнопку «Вызов».
3. Услышав прерывистый сигнал, ждите ответа.
4. Услышав ответ, говорите.
5. Услышав звуковой сигнал — входите.
В первом примере вашими действиями управляет спортивный инструктор по радио. Во втором случае вы сами в соответствии с инструкцией управляете техническим устройством (домофоном), с помощью которого осуществляется голосовая связь и дистанционное открытие двери. В обоих случаях вы совершаете заданную последовательность действий для достижения определенной цели. А если вместо вас будет кто-то другой, сможет ли он выполнить то, что делали вы?
Конечно, сможет, ведь эти инструкции адресованы любому человеку.
Из этого можно сделать важный вывод:
«Строго следуя плану, любой человек, не знакомый ранее с описанной в плане последовательностью действий, получит ожидаемый результат».
Подробное описание действий, необходимых для получения ожидаемого результата, получило название алгоритма.
С этим понятием вы сталкиваетесь постоянно.
Объявление цели урока:
Тема сегодняшнего урока «Технология решения задач с помощью компьютера. Алгоритм. Свойства алгоритма”.
Цель – сформировать четкие представления о технологии решения задач с помощью компьютера, понятии – алгоритм, свойствах алгоритма, алгоритмическом способе деятельности человека.
Слайд 6
Принцип работы вычислительных машин был высказан еще в 1834 году Чарльзом Бэббиджем. Только после истечение ста лет были реализованы эти принципы, только не в механических, а в электронных вычислительных системах. Теперь на этих же принципах продолжают работать современные компьютеры. Компьютером управляет программа, заранее разработанная человеком. Об этом мы говорили, когда рассматривали архитектуру компьютера. Теперь конкретизируем процесс создания программ, тем более, что данный процесс позволяет выстраивать схему решения любой жизненной задачи.
Этапы решения задачи с использованием компьютера:
1. Постановка задачи;
2. Определение условий;
3. Построение модели задачи;
4. Описание алгоритма решения задачи;
5. Выбор оптимальных компьютерных средств для решения;
6. Описание алгоритма с помощью выбранных программных средств;
7. Тестирование решения задачи.
8. При необходимости, коррекция решения задачи.
Для нас описанные этапы решения задачи не являются новым и фактически при работе с любым программным средством мы проходим эти этапы решения задач. Мы должны научиться конкретизировать данный процесс, с использованием понятий информатики, что позволит нам усвоить одно из основных направлений курса школьной информатики.
Прежде чем мы с помощью компьютера конкретизируем каждый этап решения задачи, познакомимся с новыми понятиями.
Алгоритмрешения задачи - это конечная последовательность четко сформулированных правил решения определенного класса задач. Любой результат деятельности человека - это последовательно выполненная совокупность действий. Вопрос лишь в том, насколько оптимально подобное решение задачи.
Получается, что, продумывая ход решения задачи, можно найти оптимальную последовательность действий. Это означает, что нужно не просто решить задачу, а решить ее с минимальными затратами.
Что такое исполнитель алгоритма?
Исполнитель алгоритма- это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя характеризуют: среда; элементарные действия; система команд; отказы.
Среда (или обстановка) — это «место обитания» исполнителя. Например, для исполнителя Робота из школьного учебника [I] среда — это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды, а их расположение и положение самого Робота задают конкретное состояние среды.
Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнено заданное действие).
Любой алгоритм должен быть построен с соблюдением определенных правил, согласованных с его свойствами.
Основные свойства алгоритма:
1. дискретность,
2. точность,
3. понятность,
4. результативность,
5. массовость.
Дискретностьозначает разбиение алгоритма на последовательность отдельных законченных действий. Точность или детерминированность- строго определенная последовательность шагов. В одном случае задаются номера строк, но даже при отсутствии нумерации предполагается строгая последовательность выполняемых действий.
Однозначное понимание исполнителем каждого шага алгоритма задает свойство понятности. При этом алгоритм должен выполняться за конечное число шагов (результативность) и может быть применен для решения целого класса однотипных задач (массовость). Прежде чем писать алгоритм нужно выяснить, возможно ли решение данной группы задач с помощью строго заданного алгоритма, в противном случае подобные алгоритмы относят к неразрешимым алгоритмам.
Для представления алгоритмов используют несколько способов:
• словесный;
• графический;
• с помощью алгоритмического языка.
Самый простой способ - словесный. При данном способе в каждой строке перечисляется определенная команда, последовательное выполнение команд приводит исполнителя к нужному результату.
Посмотрим на примере алгоритма «Заварка чая»:
1. вскипятить воду;
2. окатить заварочный чайник кипятком;
3. засыпать заварку в чайник;
4. залить кипятком;
5. закрыть крышкой;
6. накрыть полотенцем.
При графическом описании алгоритма используются геометрические фигуры для обозначения каких-либо команд, называемых блоками. Каждый блок соответствует конечному этапу процесса. Внутри каждого блока дается описание тех операций, которые необходимо выполнить.
Рассмотрим каждый блок:
Блок начала и конца
Функциональный блок
Блок ввода-вывода данных
Блок условия
Схемы строятся в соответствии с заданной задачей, в которой с помощью стрелок отслеживается направление движения по алгоритму. В качестве основных базовых структур используются объединенные схемы: линейные, ветвление, цикл.
Рассмотрим сказанное на примере решения физической задачи.
Задача: определить расстояние, пройденное человеком, если известно время движения, а так же известно, что движение было равномерным.
Условия задачи: заданы скорость движения и время. Нужно найти путь.
Создание модели задачи: для решения необходимо использовать математическую модель, выраженную в виде формулы равномерного движения:
s =v*t
Для описания алгоритма решения задачи используем блок-схему:
Для решения данной задачи можно использовать электронную таблицу, которая позволит найти зависимость пройденного пути от скорости пешехода, и также представить данные в наглядном виде.
1.
Итог:
• Этапы решения задач включают последовательно: постановку задачи; определение условий; построение модели задачи; описание алгоритма решения задачи; выбор оптимальных компьютерных средств для решения; описание алгоритма с помощью выбранных программных средств; тестирование решения задачи.
• Построение модели предполагает приведение задачи к виду, удобному для обработки техническим устройством (компьютером).
• Присоздании алгоритмов необходимо придерживаться основных требований, базирующихся на свойствах алгоритма.
прочитать §12.1, 12.2, ответить на вопросы, выучить новые определения;
дополнительное –
решить задачи индивидуального домашнего задания (какие и сколько определяют сами обучающиеся) (Приложение № 1)
подготовить доклад о жизни и деятельности ученого Абдулле (или Абу Джафаре) Мухаммеде бен Муса аль-Хорезми;
Домашнее задание (для тех, кому интересно)
Тема: Определение и свойства алгоритма
1. Запишите исполнителей для приведённых ниже видов работ:
Уборка мусора во дворе –
Перевозка пассажиров в поезде –
Выдача заработной платы –
Приём экзаменов в школе –
Сдача экзамена в университете –
Набор текста на компьютере –
Приготовление еды в ресторане -
2. Определите полный наборданных для решения следующих задач обработки информации:
а) вычисление стоимости покупок в магазине
б) вычисление суммы сдачи от данных Вами продавцу денег
в) определение времени показа по телевизору интересующего Вас фильма
г) вычисление площади треугольника
д) определение времени падения кирпича с крыши дома
е) определение месячной платы за расход электроэнергии
ж) перевод русского текста на итальянский язык
з) перевод итальянского текста на русский язык
3. Есть исполнитель «Перевозчик», который перевозит через реку волка, козу и капусту. Напишите алгоритм перевоза через реку волка, козы и капусты, если СКИ «Перевозчика» содержит 5 команд: ВЗЯТЬ КОЗУ, ВЗЯТЬ ВОЛКА, ВЗЯТЬ КАПУСТУ, ВЫСАДИТЬ, ПЕРЕПЛЫТЬ. В лодку может поместиться только один предмет или животное. Нельзя оставлять на берегу одних волка с козой и козу с капустой.
4. Напишите алгоритм приготовления какого-либо блюда (алгоритм должен иметь линейную структуру).
5. Есть исполнитель «Арифмометр», который понимает следующие команды:
- взять число N (занести в память число N),
- умножить (перемножаются занесённые в память последние два числа),
- сложить (складываются занесённые в память последние два числа),
- вычесть (вычисляется разность занесенных в память последних двух чисел),
- результат (вывести результат)
Например, в результате выполнения алгоритма:
- взять число 5,
- взять число 10,
- взять число 2,
- вычесть,
- умножить,
- результат
получим ответ 40, так как 5*(10-2)=40.
Какой результат будет получен при выполнении приведённого ниже алгоритма?
- взять число 4,
- взять число 8,
- взять число 2,
- вычесть,
- взять число 10,
- умножить,
- взять число 56,
- вычесть,
- вычесть,
- результат.
Дайте объяснение своему ответу (приведите формулу для вычисления).
6. Почему приведённые ниже алгоритмы для исполнителя «Арифмометр» не могут бытьвыполнены (какие свойства алгоритма нарушены)?
