Рекомендации к уроку: Дидактические основания урока
| Вид материала | Урок |
- Оглавление, 1363.94kb.
- Требования к современному уроку, 212.43kb.
- Методические рекомендации к уроку, 88.01kb.
- Основные компоненты современного урока, 104.47kb.
- Методика преподавания темы «Многочлены» в профильной школе Методические рекомендации, 72.18kb.
- Уроку следует помнить: Тема урока, 31.42kb.
- Конспект урока по слесарному делу Тема: Крепёжные резьбовые детали, 24.52kb.
- Урока: Гусельникова Лидия Ивановна Тема урока : Поэтический мир А. А. Фета. 10 класс, 95.29kb.
- Методические рекомендации по подготовке и поведению краевого праздничного урока, 801.35kb.
- Этап планирование урока 2 этап подготовка к уроку 3 этап проведение урока, 37.8kb.
Тема: «Свойства алгоритма».
(1 час)
"
Мы редко до конца понимаем, чего мы в действительности хотим."Франсуа де Ларошфуко
"Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер."
Дональд Э. Кнут
Рекомендации по изучению раздела:
Традиционной темой для любой версии школьного курса информатики является алгоритмизация. Существуют различные подходы к преподаванию данной темы. Алгоритмизация связывается с программированием на каком-либо языке. В базовом курсе И.Семакина применен иной подход к теме алгоритмизации. Его можно назвать кибернетическим подходом. Алгоритм рассматривается как информационный компонент системы управления. Такой подход дает возможность ввести в содержание базового курса новую содержательную линию – линию управления. Это многоплановая линия, которая позволяет затронуть следующие вопросы:
- Элементы теоретической кибернетики: кибернетическая модель управления с обратной связью;
- Элементы прикладной кибернетики: структура компьютерных систем автоматического управления; назначение АСУ;
- Основы теории алгоритмов.
Основные цели раздела:
Познакомить учащихся с основами кибернетики, с кибернетической моделью процессов управления. Дать представление о применении компьютера для автоматизации процессов управления. Ввести понятие алгоритма управления, определить свойства алгоритма. Познакомить со способами описания алгоритмов; обучить составлению алгоритмов для управления исполнителем.
Рекомендации к уроку:
Дидактические основания урока:
- методы обучения: объяснительно-иллюстративный;
- тип урока: комбинированный;
- формы учебной работы учащихся: фронтальная работа, работа в парах, работа в группах.
Для проведения объяснительно-иллюстративной лекции эффективно использовать возможности диска «1С: Вычислительная математики и программирование, 10-11 класс», раздел «Алгоритмика». Также диск содержит тесты по каждой теме.
Компьютерная лекция предполагает различные формы работы учителя и ученика:
- слайд-лекция (для работы учителя с классом)
- слайд-лекции + текст лекции (для индивидуальной работы ученика на компьютере по теме урока)
- слайд-лекция + конспект (для расширенной индивидуальной работы ученика на компьютере по теме урока)
- текст лекции, текст конспекта без слайдов.
В ходе урока учащиеся делают записи в конспектах, которые в разработке отмечены восклицательным знаком и выделены зеленым цветом.
Теоретическая часть урока построена на основе текста лекций и текста конспектов диска «1С: Вычислительная математики и программирование, 10-11 класс», раздел «Алгоритмика».
Цели урока:
- помочь учащимся усвоить понятие алгоритма, свойства алгоритмов, виды алгоритмов.
- воспитание информационной культуры учащихся, внимательности, аккуратности, дисциплинированности, усидчивости.
- развитие алгоритмического мышления, познавательных интересов, навыков работы на компьютере.
Оборудование:
доска, компьютер, мультимедийная установка
Учебно-методический комплект:
- «Базовый курс», И.Семакин, М: Лаборатория Базовых Знаний, 2001 г., §38
- «Преподавание базового курса информатики в средней школе», И.Семакин, Т.Шеина, М: Лаборатория Базовых Знаний, 2000 г., часть 2, раздел «Информация и управление»
Программное обеспечение:
Диск «1С: Вычислительная математика и программирование, 10-11 класс»
План урока:
- Орг. момент
- Актуализация знаний
- Теоретическая часть
- Рефлексивный тест
- Дополнительные упражнения
- Домашнее задание
- Вопросы учеников
- Итог урока
Ход урока:
I. Орг. момент.
Приветствие, проверка присутствующих. Объяснение хода урока.
II. Актуализация знаний.
Для решения большинства задач существует множество готовых программ. Но для того чтобы лучше понимать все происходящее с компьютером и уверенно принимать правильные решения, рядовому пользователю необходимо обладать определенной компьютерной грамотностью.
Следует отметить, что большинство редакторов (например, Microsoft Office Word, Excel) имеют встроенные средства программирования, освоив которые можно значительно расширить свои возможности.
III. Теоретическая часть.
Запустить диск, установить режим «Только слайды»
Слайд №1 «Введение»
Один из важнейших этапов решения задач на ЭВМ – составление алгоритма. О том, что такое алгоритмы, какими общими свойствами они обладают и как исполняются, мы и поговорим на этом уроке.
Слайд №2 «Происхождение термина «алгоритм»
В 1983 году отмечалось 1200-летие со дня рождения одного из величайших ученых Средней Азии и средневекового Востока Мухамада ибн Мусы аль-Хорезми.
Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами". Из нее европейцы научились индийскому счету с помощью десяти цифр и узнали правила арифметических действий над ними. Она произвели в те времена столь огромное впечатление на математиков, что само имя ученого аль-Хорезми, указывающее на его происхождение из среднеазиатского государства Хорезм (области в нынешнем Узбекистане), в их устах превратилось в понятие algorithmi, первоначально обозначавшее десятичную систему исчисления и правила арифметических действий в этой системе. Отсюда и возник современный научный термин "алгоритм". Сейчас под алгоритмом понимают точное предписание, определяющее путь к достижению поставленной цели.
(Можно заменить лекцию слайда №2 на сообщение учащихся, подготовленные в виде домашнего задания по теме «Возникновение термина «алгоритм»)
(конспект!) современный научный термин «алгоритм» произошел от имени величайшего ученого Мухамада ибн Муссы аль-Хорезми, первым предложившего приемы выполнения арифметических операций с многозначными числами.
Слайд №3 «Свойства алгоритма «дискретность», «упорядоченность»
Примеры алгоритмов
Чтобы научить кого-либо открывать дверь, придется четко указать и сами действия, и порядок их выполнения. Приведем пример.
Алгоритм открывания двери
Достать ключ.
Вставить ключ в замочную скважину.
Повернуть ключ 2 раза против часовой стрелки.
Вынуть ключ.
А теперь представьте себе, что вас пригласили в гости. Вы знаете адрес, но хотите выяснить, как лучше проехать. Вот возможное объяснение:
Алгоритм "Как ехать в гости"
Выйти из дома.
Повернуть направо.
Пройти два квартала до автобусной остановки.
Сесть в автобус № 25, идущий к центру города.
Проехать три остановки.
Выйти из автобуса.
Найдите общее в этих алгоритмах? (ответы учащихся)
Общее в этих алгоритмах – строгий порядок действий. Давайте переставим в первом алгоритме второе и третье действия:
Достать ключ.
Повернуть ключ 2 раза против часовой стрелки.
Вставить ключ в замочную скважину.
Вынуть ключ.
Вы, конечно, сможете выполнить и этот алгоритм.(ответы учащихся) Но дверь вряд ли откроется. А что произойдет, если поменять местами четвертое и пятое действия во втором алгоритме? (ответы учащихся) Он станет невыполнимым! Итак, мы убедились, что для алгоритма важен не только набор действий, но и то, как они организованы, то есть в каком порядке эти действия выполняются. Эти свойства алгоритмов, соответственно, называются дискретностью и упорядоченностью.
Приведите примеры своих алгоритмов из пяти действий, в которых прослеживаются свойства дискретности и упорядоченности. Обоснуйте свои примеры.
(конспект!) Свойства алгоритма: дискретность, упорядоченность
Слайд №4 «Понятие алгоритма»
Понятие алгоритма в информатике является фундаментальным. Таким же, какими являются понятия точки, прямой и плоскости в геометрии, пространства и времени в физике, вещества в химии и т.д. Поэтому мы не станем стремиться к тому, чтобы дать всеобъемлющее определение алгоритма, а будем уточнять смысл этого понятия в последующем.
Мы можем теперь сказать, что алгоритм – это организованная последовательность действий. Данную формулировку, конечно, нельзя считать определением алгоритма. Например, мы не объяснили, что означают слова организованная и действия. Скажем сразу: абсолютно строгого определения алгоритма не существует. Алгоритм – это одно из тех основных понятий (категорий) математики, которые не обладают формальным определением в терминах более простых понятий, а абстрагируются непосредственно из опыта.
Слайд №5 «Найти ошибку в алгоритме»
На слайде еще одно задание. Выполните его, используя для записи ответа любой текстовый редактор или бумагу и карандаш.
Задание
Некий злоумышленник в качестве алгоритма получения кипятка предложил такую последовательность действий:
- Налить в чайник воду.
- Открыть кран газовой горелки.
- Поставить чайник на плиту.
- Ждать, пока вода закипит.
- Поднести спичку к горелке.
- Зажечь спичку.
- Выключить газ.
Измените алгоритм таким образом, чтобы предотвратить несчастный случай. Используйте для записи ответа любой текстовый редактор или бумагу и карандаш.
Слайд №6 «Правильный ответ»
- Сравните свой ответ с правильным.
- Правильный алгоритм:
- Налить в чайник воду.
- Зажечь спичку.
- Открыть кран газовой горелки.
- Поднести спичку к горелке.
- Поставить чайник на плиту.
- Ждать, пока вода закипит.
- Выключить газ.
Слайд №8 «Что такое исполнитель?»
Рассмотренные нами алгоритмы составлены для исполнения человеком. Но человек далеко не единственный возможный исполнитель алгоритмов. Все живые существа и даже отдельные клетки исполняют различные алгоритмы. Способны на это и созданные человеком устройства – роботы-манипуляторы и станки с программным управлением. Но прежде чем составлять алгоритм решения задачи, нужно узнать, какие действия предполагаемый исполнитель способен выполнить.
Что такое исполнитель
Упрощенно исполнителя можно представить себе как некоторое устройство управления, соединенное с набором манипуляторов. Устройство управления понимает алгоритмы и организует их выполнение, командуя соответствующими манипуляторами. А манипуляторы производят действия, выполняя команды управляющего устройства.
Скажем, если человека рассматривать, как исполнителя алгоритмов, то мозг – его управляющее устройство, а манипуляторы – руки, ноги, рот и т.д. У роботов, станков с программным управлением и ЭВМ управляющее устройство – процессор; что же касается набора манипуляторов, то он зависит от того, для решения каких задач предназначен данный исполнитель.
Ясно, что как бы ни были разнообразны возможности конкретного исполнителя, они всегда ограничены. В противном случае для решения любой задачи годился бы один-единственный алгоритм:
Получить исходные данные.
Найти решение.
Сообщить ответ.
Поэтому, прежде чем составлять алгоритм решения задачи, нужно узнать, какие действия предполагаемый исполнитель может выполнить. Все возможные действия исполнителя называются допустимыми действиями исполнителя и составляют его систему команд. При составлении алгоритмов можно использовать только их.
(!) конспект:
- Исполнитель – некий объект или субъект, для управления которым составлен алгоритм
- Система команд исполнителя (СКИ) – это вся совокупность команд, которые исполнитель умеет выполнять (понимает). Алгоритм можно строить только из команд, входящих в СКИ исполнителя (свойства понятности)
Слайд №9
Пусть требуется решить уравнение вида ax2 + bx + c = 0. Ученик десятого класса, который хорошо знает, как решать квадратные уравнения, не нуждается в объяснениях. Для него алгоритм решения будет состоять из двух действий:
- Решить уравнение.
- Сообщить результат.
Для ученика восьмого класса, который еще не знает формулу вычисления корней квадратного уравнения, придется написать более длинную инструкцию:
- Вычислить значение выражения b2 – 4ac (дискриминант уравнения).
- Извлечь из полученного числа квадратный корень и обозначить результат буквой р.
- Вычислить значение выражения (–b+р)/2a и обозначить результат x1.
- Вычислить значение выражения (–b–р)/2a и обозначить результат x2.
- Сообщить числа x1 и x2.
Для пятиклассника, который не умеет извлекать квадратный корень, тоже можно составить алгоритм решения нашего уравнения. Этот алгоритм будет очень длинным и сложным. Как видите, чем меньше запас умений школьника, тем подробнее будет составленный для него алгоритм.
Слайд №10 «Определение алгоритма»
Теперь мы можем уточнить понятие алгоритма: это организованная последовательность действий, допустимых для некоторого исполнителя.
Алгоритм – это организованная последовательность действий, допустимых для некоторого исполнителя. От исполнителя требуется лишь четкое выполнение каждого действия, входящего в алгоритм. Мы не обязаны объяснять ему, для каких целей предназначен алгоритм.
(конспект!) Алгоритм – это организованная последовательность действий, допустимых для некоторого исполнителя
Слайд №11 «Информационный процесс редактирования текста»
Рассмотрим информационный процесс редактирования текста. При работе с текстом возможны различные операции: удаление, копирование, перемещение или замена его фрагментов. Что необходимо для того, чтобы преобразовать текст?
Для преобразования текста, во-первых, требуется исполнитель – кто-то (или что-то), кем (или чем) эти преобразования выполняются. Во-вторых, процесс преобразования текста надо разбить на отдельные операции, которые должны быть записаны в виде отдельных команд исполнителю. При этом исполнитель должен быть в состоянии выполнить эти команды. Каждый исполнитель обладает определенным набором команд, которые он может выполнять. Значит, процесс должен быть разбит на операции, понятные исполнителю. Совокупность понятных исполнителю команд называется системой команд исполнителя. В-третьих, должно быть определено начальное состояние текста и его требуемое конечное состояние (цель преобразования). Процесс, удовлетворяющий этим требованиям, и есть искомый алгоритм. Наличие начального состояния (или исходных данных) и цели выполнения (конечного состояния, результата) – еще одно важнейшее свойство алгоритма
- Первое. Требуется исполнитель.
- Второе. Процесс должен быть разбит на этапы, понятные исполнителю.
- Третье. Должно быть определено начальное состояние текста и его требуемое конечное состояние.
(конспект!) свойства алгоритма – конечность, результативность
Слайд №12 «Мини-тест»
Очередной тест. Выберите с помощью мыши правильный вариант ответа и прочтите комментарий.
Какой из названных документов является алгоритмом?
- Расписание движения самолетов
- Список файлов на диске?
- Порядок оказания первой медицинской помощи?
Слайд №13 «Свойства алгоритма – детерминированность, массовость»
Теория алгоритмов имеет большое практическое значение. Алгоритмический тип деятельности важен не только как одна из эффективных форм труда человека. Через алгоритмизацию, через расчленение сложных действий на всё более простые, на действия, выполнение которых доступно машинам, пролегает путь к автоматизации различных процессов.
Далее под алгоритмом будет пониматься конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Такое свойство алгоритма, как однозначность результата при заданных исходных данных, называется определенностью (детерминированностью).
Заметим, что большинство алгоритмов могут выполняться при достаточно разнообразных наборах исходных данных, то есть использоваться для решения не какой-либо одной задачи, а целого класса подобных задач. Это свойство алгоритма называется массовостью.
С алгоритмами человек встречается на каждом шагу.
Пример 1. Дан угол. Необходимо провести биссектрису. (Есть способ, как, пользуясь линейкой и циркулем, можно решить эту задачу.)
Пример 2. Даны два целых числа. Необходимо найти их разность. (Имеется правило, в котором ясно изложен весь порядок действий с цифрами данных чисел.)
В приведенных примерах речь идет о том, как сложную работу представить в виде последовательности простых действий. Вычитание многоразрядных чисел сводится к действиям с цифрами. При делении угла пополам выполняются несложные построения линейкой и циркулем.
Однако высказанные соображения следует дополнить. Ведь правила вычитания формулируются для любых многоразрядных чисел, а не для каких-то конкретных двух. Инструкция проведения биссектрисы тоже такова, что, пользуясь ею, можно разделить пополам любой угол. То есть каждому алгоритму присуща массовость – пригодность для решения не какой-либо одной, а целого класса задач.
Далее под алгоритмом будет пониматься конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Такое свойство алгоритма, как однозначность результата при заданных исходных данных, называется определенностью (детерминированностью).
(конспект!) свойство алгоритма – детерминированность, массовость
Слайд №14 «Алгоритмический способ деятельности»
Алгоритмический способ деятельности человека состоит в том, что он либо сам разрабатывает алгоритм, либо получает его в готовом виде и затем исполняет, строго следуя всем указаниям, образующим данный алгоритм.
Создание алгоритма для решения задач какого-либо типа, его представление исполнителю в удобной для него форме – это творческий акт. Образно говоря, историю математики можно было бы назвать историей создания алгоритмов и их внедрения. Сегодня мы наблюдаем, как растет стремление продвигать алгоритмический способ в различных областях трудовой деятельности; мы видим, как ширится класс задач, которые удается алгоритмизировать.
Слайд №15 «Свойство алгоритма – понятность. Подведение итогов»
Кроме того, исполнитель переходит к выполнению следующей команды, только выполнив предыдущую.
Как вы думаете, каким еще должен быть алгоритм?
(ответ: понятным)
На этом занятии мы познакомились с такими важнейшими понятиями, как алгоритм, исполнитель, система команд исполнителя, узнали основные свойства алгоритма.
- дискретность – расчлененность алгоритма на отдельные элементарные действия;
- упорядоченность – строгий порядок выполнения действий;
- массовость – пригодность для решения не какой-либо одной, а целого класса задач;
- детерминированность (определенность) – однозначность результата при заданных исходных данных.
- понятность – алгоритм должен быть понятен исполнитель и исполнитель должен быть в состоянии выполнить его команды.
- результативность – процесс решения задачи должен прекратиться за конечное число шагов и при этом должен быть получен ответ задачи.
От исполнителя не требуется понимание сущности алгоритма, он должен лишь точно выполнять команды, не нарушая их последовательности.
А что такое программа? Отличается ли программа от алгоритма?
(конспект!) Программа – это алгоритм, записанный на языке исполнителя
Иначе можно сказать так: алгоритм и программа не отличаются по содержанию, но могут отличаться по форме. Для алгоритма строго не определяется форма его представления. Но программа должна быть записана на языке исполнителя.
IV. Рефлексивный тест «Свойства алгоритма»
Состоит из четырех вопросов, с возможностью повторного ответа. Результаты ответов на вопросы выводится в виде следующей таблицы:
| |||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||
V. Домашнее задание:
1. Знание основных определений по теме урока.
2. Выполнение заданий из раздела «Дополнительные задания к уроку»
VI. Дополнительные задания к уроку:
Дополнительный материал используется для развития алгоритмического и логического мышления учащихся. Возможны различные формы работы: индивидуальная, парная, групповая.
Игра Баше. (В игре участвуют двое).
Имеется 15 предметов. Соперники ходят по очереди, за каждый ход любой из играющих может взять 1, 2 или 3 предмета. Проигрывает тот, кто вынужден взять последний предмет.
Алгоритм для выигрыша 1 игрока имеет следующий вид:
1. Взять 2 предмета.
2. Второй и последующий ходы делать так, чтобы количество предметов, взятых вместе с соперником за очередной ход, в сумме составляло 4.
Данный алгоритм приводит к выигрышу для 7, 11, 15, 19,… предметов. Человек, пользующийся данным алгоритмом, всегда будет выигрывать в данной игре. Ему совершенно необязательно знать, почему надо поступать именно так, а не иначе. Для успешной игры ему требуется только строго следовать алгоритму.
По приведенному алгоритму восстановите формулу для вычисления значения y:
a)
Умножить x на x, обозначить результат R1.
Умножить R1 на a, обозначить результат R2
Сложить R2 с b, обозначить результат R3.
Разделить R3 на c, считать результат значением y.
b)
Сложить x с 1, обозначить результат с A1.
Разделить 1 на A1, обозначить результат A2.
Сложить A2 с 1, обозначить результат A3.
Вычесть из A2 единицу, обозначит результат A4.
Разделить А4 на А3, обозначить результат А5.
Вычесть из А5 единицу, считать результат значением у.
Какую задачу решает исполнитель, выполняя следующие команды:
Начертить отрезок АВ, длина которого равна 6 см.
Поставить ножку циркуля в точку А.
Установить раствор циркуля равным длине отрезка АВ.
Провести окружность
Поставить ножку циркуля в точку В
Провести окружность
Через точки пересечения окружностей провести прямую.
Отметить точку пересечения этой прямой с отрезком АВ
Опишите точный план действий, приводящий к решению следующих задач:
- Волк, коза и капуста. На берегу реки стоит крестьянин с лодкой, а рядом с ним – волк, коза и капуста. Крестьянин должен переправится сам, и перевезти волка, козу и капусту на другой берег. Однако, в лодку, кроме крестьянина, помещается либо волк, либо коза, либо только капуста. Оставлять же волка с козой или козу с капустой без присмотра нельзя – волк может съесть козу, а коза – капусту. Как должен вести себя крестьянин?
- Два встречных поезда, в каждом из которых паровоз и 21 вагон, встретились на дороге с одним тупиком. Тупик вмещает 11 вагонов или 10 вагонов и паровоз. Как разъехаться поездам (т.е. как должны маневрировать машинисты, чтобы каждый поезд продолжил движение в своем направлении)?
- Ханойская башня. На подставке укреплены три стержня, на левый стержень нанизано несколько колец уменьшающегося размера – внизу самое большое кольцо, на нем поменьше, сверху еще меньше и т.п. Надо, перемещая по одному кольцу со стержня на стержень, переместить все кольца на правый стержень, но при этом ни в какой момент времени большее кольцо на меньшее класть нельзя. Опишите, как надо перекладывать кольца, если в начальный момент на левом стержне:
1
2
3
4
64 кольца.
По преданию перекладыванием 64 колец занимаются монахи в одном из буддистских монастырей. Согласно легенде, в момент, когда они кончат перекладывать кольца, наступит конец света. Прикиньте приблизительно, когда это произойдет, если считать, что монахи перекладывают примерно 1 кольцо в секунду.
Ответ: 264-1 или »585 тыс. лет.
- Фирма «Электронные приборы» выпустила автоматизированную ванну «Банный комплекс – 10», управляемую с помощью 10 кнопок «долить 1 л», «долить 2 л», …, «долить 5 л», «слить 1 л», «слить 2 л»,…,«слить 5 л», при нажатии, на которые доливается или сливается указанное количество воды. Однако, в результате ошибки фирмы все кнопки, кроме «долить 5 л» и «слить 3 л», не работают. Как долить в ванну 3 л воды? Сколько воды при этом пропадает впустую из-за брака фирмы?
- Два солдата подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата либо двух мальчиков, а солдата и мальчика уже не вмещает?
- Игра Баше. Петя и Коля играют в следующую игру: на стол кладется 15 спичек. Ребята по очереди берут их со стола, причем за один ход разрешается взять 1, 2 или 3 спички. Выигрывает тот, кто возьмет последнюю спичку. Первым ходит Петя. Как он должен играть, чтобы выиграть?
- Есть двое песочных часов: на 3 минуты и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
- Автоматическое устройство имеет 2 кнопки и экран. При включении на экране загорается число 0. При нажатии на одну кнопку число на экране удваивается (вместо х появляется 2х). При нажатии на другую кнопку число увеличивается на 1 (вместо х появляется х+1). Как надо нажимать на кнопки, чтобы на экране появилось:
число 5;
число 99;
число 99, если разрешается нажимать на кнопки не более 10 раз?
- Придумайте способ нахождения самой легкой и самой тяжелой из 100 монет различной массы, если можно сделать не более 150 взвешиваний на чашечных весах без гирь.
- Имеется:
3;
4;
5;
6
монет, среди которых одна фальшивая (легче других). Придумайте способ нахождения фальшивой монеты за минимальное число взвешиваний на чашечных весах без гирь.
Упражнения на отгадывание алгоритма преобразования информации.
- В приведенных следующих примерах каждый следующий элемент получен по некоторому строгому правилу. Угадайте это правило:
a) а, б, в, г, д, е, … ;
b) 1, 2, 3, 4, 5, 6, 7, … ;
c) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, … ;
d) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … ;
e) 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, … ;
f) победа, обеда, беда, еда, … ;
g) о, д, т, ч, п, ш, с, в, д, д,…;
h) 1, 11, 21, 1211, 111221, 312211, 13112221, … .
- Петя и Коля играют в следующую игру: Петя задумывает правило преобразования текстовой информации. Коля может задавать Пете любые тексты и узнавать результаты преобразования. Задача Коли – отгадать это правило. Ниже приведены вопросы Коли и ответы Пети в нескольких таких играх. Попробуйте отгадать, какое правило задумал Петя в каждой игре:
i) А ® Б; мама ® нбнб; ЭВМ ® ЮГН; язык ® аиьл;
j) А ® 1; мама ® 4; ЭВМ ® 3; язык ® 4;
k) А ® 0+1; мама ® 2+2; ЭВМ ® 2+1; язык ® 2+2;
l) А ® А; мама ® амам; ЭВМ ®ВМЭ; язык ® зыкя;
- Петя задумывает правило преобразования целых чисел. Ниже приведены вопросы Коли и ответы Пети в нескольких таких играх. Попробуйте отгадать, какое правило задумал Петя в каждой игре:
m) 1 ® 0; 5 ® 4; 0 ® -1; 1990 ® 1989;
n) 1 ® 0; 2 ® 0; 10 ® 9; 3 ® 3; 20 ® 18; 1990 ® 1989;
o) 1 ® 1; 7 ® 1; 10 ® 2; 187 ® 3; 1990 ® 4;
p) 1 ® 0; 8 ® 2; 16 ® 1; 1990 ® 3; 1989 ® 4; 100 ® 2; 108 ® 3; 6 ® 1;
7 ® 0; 23 ® 0; 50 ® 1.
- Опишите правило преобразования текста, которое фразы вида «Тебя зовут Вася?» превращает во фразы вида «Это тебя зовут Вася!». Примените это преобразование к нескольким другим фразам.
- Даны: лист миллиметровки, иголка, лупа с десятикратным увеличением. Придумайте способ записать на листе миллиметровки как можно больше информации. Запишите алгоритм.
- Даны: лист тонкого картона и тупое шило. Придумайте способ записать на листе информацию так, чтобы ее можно было считать в темноте, «на ощупь».
- Коля сидит дома, делает уроки и не подходит к телефону. Петя набирает Колин номер, ждет некоторое время и кладет трубку. Затем снова набирает Колин номер и т.д. Придумайте способ передачи информации с помощью таких звонков.
Интернет-ресурсы для учителя и ученика:
ссылка скрыта,
Алгодром, Алгоритмика и программирование
Тема «Оценка эффективности алгоритма»
(1 час)
Для углубленного изучения.
Образовательная программа 138 часов (2 часа в неделю)
"Поразительно, скольким программистам приходится слишком дорогим способом выяснять, что их программа не может обработать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью карандаша и бумаги."
С. Гудман (S. Goodman), С. Хидетниеми (S. Hedetniemi)
"Лучше меньше, да лучше."
В.И. Ульянов (Ленин)
Интернет-ресурс для проведения уроков по углубленной программе:
ссылка скрыта,
Российская Интернет-школа информатики и программирования
Упражнение
Как известно из замечательной книги Л.Лагина, однажды со Стариком Хоттабычем приключился неприятный инцидент: он съел много эскимо, отчего сильно простыл. Предположим, для упрощения, что за 5 минут выполняется 1 шаг алгоритма: съедается очередная порция (в действительности, старик справился со всем запасом мороженого за пять минут). Подсчитайте (процесс – вычислительный!), сколько вам понадобится алгоритмических шагов для достижения того же результата (Хоттабычу «хватило» 43 порций). Если найдется хотя бы пара читателей, повторивших или превзошедших славное достижение Хоттабыча, то автор готов признать за указанным алгоритмом свойство массовости.
На прошлом уроке мы говорили о необходимости анализировать конструируемый алгоритм. Такой анализ должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса.
Первая часть вполне ясна: речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе. Естественно, к ним относятся входные наборы, промежуточная и выходная информация. Возможно, не все перечисленные наборы требуют одновременного хранения, – что ж, значит, удается сэкономить. В ряде случаев, впрочем, оценка емкостной сложности становится менее очевидной: так обстоит дело при использовании динамических структур.
Проведем анализ временной трудоемкости.
Итак, поставлена некоторая задача, и для ее решения спроектирован алгоритм. Он описывает вычислительный процесс, который завершается за конечное число действий-шагов. Мы уже говорили, что реальное время выполнения каждого отдельного шага зависит от конкретного вычислительного устройства. Иначе говоря, неотъемлемым участником вычислительного процесса, – не алгоритма! – является исполнитель. А вот, имея ввиду предполагаемого исполнителя, лучше заранее оценить его вычислительные способности.
Можно сказать, что алгоритм должен быть понятен исполнителю. Это означает, что любое предписание алгоритма должно входить в тот фиксированный набор инструкций, которые исполнитель умеет реализовывать. Скажем, ваш карманный калькулятор рассчитан на выполнение нескольких арифметических операций, а более мощный, программируемый калькулятор, уже готов выполнять несложные программы. Соответственно, наборы встроенных, элементарных, инструкций у этих устройств различаются. Притом, любая команда, которую готов выполнить второй калькулятор, все равно состоит из некоторого числа арифметических и логических операций. Другое дело, что нам не приходится их вызывать по отдельности. Таким образом, либо алгоритм явно предписывает выполнять арифметико-логические операции, – и такой уровень программирования рассчитан непосредственно на работу процессора, – либо используются "укрупненные" инструкции, и для их обработки применяется специальный язык.
Так, общение клиента с банкоматом предусматривает участие двух исполнителей алгоритма – человека и банкомата, причем первый из них обращается ко второму посредством кнопочного интерфейса. Опытный владелец пластиковой карты знаком с процедурой, тем не менее, второй участник процесса не учитывает компетентность клиента, и потому на табло высвечиваются поочередно все необходимые инструкции. Как видим, разработчики системы, обеспечивающей этот диалог, довели пошаговую детализацию алгоритма до определенного уровня "компетентности", разбив укрупненные шаги – "снятия наличности" или "получения справки о счете" – на шаги более мелкие.
Как мы выяснили, исполнитель нашего алгоритма должен "уметь" выполнить любую инструкцию из числа тех, которые он воспринимает как элементарные, а никакие другие он и не выполнит. Собственно, одно из различий между процессорами компьютеров состоит в несовпадении их "личных" наборов инструкций.
Но было бы нелепо ориентироваться на столь "интеллектуально ограниченного" исполнителя, каким является обыкновенный процессор. Напротив, "способности" нашего подразумеваемого исполнителя должны постепенно развиваться. Потому, по мере удаления от начальных страниц, степень детализации будет уменьшаться, и алгоритмы будут описываться в укрупненных шагах. Так, опытный повар вполне готов исполнить предписание "приготовить ростбиф", – помните, мы с ним выше сталкивались? – как элементарную инструкцию.
Предположим, алгоритм для решения некоторой задачи нам удалось построить. Раз так, что мешает предположить существование и другого алгоритма, и еще следующего? Но если удается сконструировать целый ряд различных алгоритмов решения одной и той же задачи, то кажется разумным – выбрать "наилучший". Что под этим следует понимать?
Как правило, речь идет о таком варианте решения, который, в сравнении с конкурентами, нуждается в наименее продолжительном по времени вычислительном процессе. Разумеется, давать такую оценку правомерно, лишь имея ввиду одного и того же потенциального исполнителя.
Далее: скорость реализации выбираемого алгоритма может существенно зависеть от содержания набора входных данных. Скажем, быстрый "в среднем" механизм способен давать сбои в отдельных "плохих" случаях. И, если задача должна наверняка решаться за определенное время работы процессора, то в этом случае, вероятно, мы предпочтем алгоритм более медленный в среднем, зато надежный в худших ситуациях.
За примерами вновь обратимся к некомпьютерной сфере. Чтобы выпить чашку кофе, надо, во всяком случае, подогреть воду. Достаточно удобна и эффективна в этом случае кофеварка или мощный электрочайник. Если к вам в дом, – а это весьма вероятно, – подведено электричество, то способ решения задачи, привлекающий один из указанных приборов, стоит предпочесть в большинстве случаев. Однако неполадки в распределительном электрощите, сколь бы редко они ни возникали, лишат вас ожидаемого удовольствия (как и автора, который ссылается здесь на собственный печальный опыт, когда одновременно с кофеваркой перестает работать и компьютер). Так что газовые плиты пока не стоит отменять.
Впрочем, остается и самый надежный, хотя и наиболее трудоемкий метод: вскипятить воду на открытом огне, разложив небольшой костер. Чтобы читатель не забывал анализировать и емкостную сложность алгоритма, заметим, что последний пример сочетает свойства наихудшей эффективности как по времени, так и по требованиям к ресурсам, учитывая безвозвратный расход горючего и низкий коэффициент полезного действия при изменении агрегатного состояния. Однако даже такой алгоритм имеет право на существование!
Итак, давая оценку быстродействия алгоритма, следует рассмотреть поведение вычислительного процесса в среднем и, отдельно, в экстремальных для него условиях, то есть – в худшем случае.
Моделирование "худших" случаев всегда связано с содержанием самого алгоритма. Можно предложить лишь малое число рецептов выделения и рассмотрения подобных ситуаций. Один из них состоит в проверке поведения алгоритма на входных данных, принимающих граничные значения из разрешенного диапазона. Другой рецепт: тестировать алгоритм на максимально больших по объему входных наборах, что важно для анализа как временной, так и емкостной эффективности.
Умение предвидеть "нехорошие" ситуации, – а они нередко возникают при выполнении готовой программы, – как раз и отличает квалифицированного алгоритмиста от обыкновенного кодировщика. В связи с расширением сферы производства программного обеспечения сформировалась даже самостоятельная специализация – "тестеры программ".
Упражнения
- На тарелке один на другой в произвольном порядке положены 15 блинов разных размеров. В любом месте стопки можно засунуть лопатку и перевернуть верхнюю часть стопки. Составить алгоритм упорядочения блинов в порядке увеличения их размеров.
- Ваш приятель живет в 100- этажном доме, где на каждом этаже разное число квартир. Он позвал Вас в гости, номер квартиры сказал, а этаж назвать забыл. Составить алгоритмы поиска номера нужного этажа. Какой из них самый эффективный?
- Великан-людоед поймал 7 братьев – малышей, но, будучи в добром настроении, пообещал отпустить самого легкого из них, если они найдут способ поиска его за 6 взвешиваний на весах с коромыслом и двумя чашками. Поможете малышам?
- Великан обещал отпустить всех братьев, если они составят 6 способов поиска самого легкого из 7 братьев, шесть раз сравнивая их попарно на весах (можно сравнивать братьев, объединяя их в группы по двое, по трое).
- Даны 5 попарно различных целых чисел a, b, c, d, e. Упорядочить их по возрастанию, используя для этого не более семи сравнений.