Сетевой журнал "Интернет и образование"

Уроки из системы уроков по теме "Основы алгоритмизации и объектно-ориентированного программирования"

Вашему вниманию предлагается 4 последовательных урока (урок №1 конспект и презентация; урок №2-№4 - презентации) из системы уроков по теме "Основы алгоритмизации и объектно-ориентированного программирования". Преподавание по учебнику Н.Д.Угриновича "Информатика и ИКТ" Базовый курс. 9 класс.

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

Проходит апробация материала на 9-ых классах общеобразовательной школы.

Список использованных ресурсов:

1. Угринович Н.Д. Информатика и ИКТ. Базовый курс: учебник для 9 класса
2. Информатика в школе: Приложение к журналу «Информатика и образование» №1 – 2004. – М.: Образование и Информатика, 2004. – 152 с.: ил.
3. Андреева Е.В. Информатика. Основы алгоритмизации. Тетрадь с печатной основой. – Саратов: «Лицей», 1999. – 80с.
4. CD «Вычислительная математика и программирование 10-11 кл.» 1С:  Образование, 2004 г.
5. Н.В. Макарова «Информатика. Подготовка к ЕГЭ», издательство «Питер»

Презентация

Урок №1. Алгоритм и его свойства

" Мы редко до конца понимаем,
чего мы в действительности хотим"
Франсуа де Ларошфуко

Цели урока:
 Образовательная: Сформировать представление у учащихся о понятии алгоритма, выделить его свойства. Рассмотреть понятие исполнителя и системы команд исполнителя;
Развивающая: Формирование приемов логического мышления, развитие интереса к предмету;
Воспитательная: Воспитание  аккуратности, точности.

Обеспечение урока:

1. Угринович Н.Д. Информатика и ИКТ. Базовый курс: учебник для 9 класса
2. Информатика в школе: Приложение к журналу «Информатика и образование» №1 – 2004. – М.: Образование и Информатика, 2004. – 152 с.: ил.
3. Андреева Е.В. Информатика. Основы алгоритмизации. Тетрадь с печатной основой. – Саратов: «Лицей», 1999. – 80с.
4. Презентация «Основы алгоритмизации и объектно-ориентированного программирования» - Урок №1
5. CD «Вычислительная математика и программирование 10-11 кл.» 1С Образование

План урока:

1. Организационный момент.
2. Актуализация знаний. Мотивация изучения нового материала.
3. Изучение  нового материала.
4. Закрепление изученного материала.
5. Проверка знаний. Тест на CD.
6. Домашнее задание.
7. Подведение итогов урока.

Ход урока:
Изучение нового материала:

            Каждый человек в своей повседневной жизни, в учебе или на работе сталкивается с необходимостью решения огромного количества задач самой разной сложности. Некоторые из них настолько трудны, что требуют длительных размышлений для поиска решения (а иногда найти его так и не удается). Другие же напротив, столь просты и привычны, что решаются нами автоматически. Решение задачи «Поступить в институт» намного труднее и требует выполнения гораздо большего количества сложный действий, чем решение задачи «Купить мороженое». При этом выполнение даже самой простой задачи обычно осуществляется в несколько последовательных этапов, или шагов.  Если проанализировать ход выполнения этих задач, то окажется, что практически любое действие, которое надо при этом произвести, может быть четко сформулировано и записано.
            Назовите пример вам хорошо знакомых последовательных действий?
№1 Приготовление завтрака.
№2 Решение квадратного уравнения
№3  Определение рода существительного

Определение 1:  Алгоритм – это предписание исполнителю выполнить последовательность команд, приводящую от исходных данных к искомому результату.

           
            Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)

            Поговорим и о происхождении слова «алгоритм». Известно, что в раннем Средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster’s New World Dictionary», изданном в 1957 году., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр. Несмотря на то что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «альгирос» - больной и «арифмом» - число. Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Эфрона (1890 г.) В нем «алгорифм» (кстати, до революции использовалось и написание «алгори?м», через «фиту») производится от арабского слова «Аль-Горетм», т.е. корень.
            Но истину удалось установить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике аль – Хорезми, жившего в первой половине IX века. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами" – о счете с помощью десяти цифр и правилах арифметических действий с числами.  В латинской транскрипции его имя записывается как Abu’Abd Allah Muhammad ibn Musa al-Khwarismi и означает «Мухаммад, сын Мусы, отец Абдуллы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является город Хива.
            Возвращаясь к определению алгоритма, хочется задать вам вопрос: а все ли алгоритмы правильные? Любой ли алгоритм возможно выполнить?

Верно ли, что следующий алгоритм правильный?

1. Налить воду в чайник
2. Открыть кран газовой горелки
3. Поставить чайник на плиту
4. Ждать, пока вода не закипит
5. Поднести спичку к горелке
6. Зажечь спичку

1. Выключить газ

Обсуждение правильного решения. После чего, ребята диктуют правильное решение, и оно появляется на следующем слайде: 

Верно что:

1. Налить воду в чайник
2. Поставить чайник на плиту
3. Открыть кран газовой горелки
4. Зажечь спичку
5. Поднести спичку к горелке
6. Ждать, пока вода не закипит
7. Выключить газ

            Какими же свойствами должен обладать алгоритм, для того, чтобы мог быть правильно выполнен исполнителем?

Введем второе определение алгоритма

Определение 2: Алгоритм – это  конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Ответьте на вопрос: какие изменения вы заметили в новом определении? Ответ: более полное определение,  введение понятия происходит с опорой на основные изученные свойства алгоритма.

         Закрепление изученного материала: решение алгоритмических задач

               
Решение:
Решение удобно записать в виде таблицы, указывая текущее положение объектов при переправе: кто на каком берегу остался, кто переправляется.

Целесообразно, если возникли сложности при решении, обсудить с учащимися вопросы:

1. Может ли перевозчик поплыть на лодке один, оставив на берегу всех троих – волка, козу и капусту?
2. Может ли перевозчик поплыть на другой берег с одним из «пассажиров», а вернуться с другим?

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

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

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

Задача №2.
Выполните предложенные действия.

1. Задумайте целое число от 1 до 20.
2. Прибавьте к нему 2.
3. Результат умножьте на 2.
4. К полученному произведению прибавьте 3.
5. От суммы отнимите задуманное число.
6. К разности прибавьте 5.
7. От суммы отнимите задуманное число.
8. Сообщите ответ.

            Что у вас получилось? Объясните, в роли какого исполнителя – формального или неформального – вы выступали. Попробуйте поменять местами две любые команды. Получится ли у вас тот же результат?
Решение: Очень хочется надеяться, что вы были внимательны, и у вас получилось число 12. Если получилось другое число, то выми допущена ошибка в вычислениях, так как последовательность действий была такова:
Х
Х+2
(х+2)*2=2х+4
2х+4+3=2х+7
(2х+7)-х=х+7
(х+7)+5=х+12
(х+12)-х=12
12

Ответ: В данном случае вы выступали в качестве формального исполнителя, т.к. выполняли команды. Если поменять команды местами, то ответ будет уже другим. Если выполнять эти команды друг за другом, без вычислительных ошибок, то для разных чисел результат будет один и тот же.

Задача №3.
            Какому исполнителю под силу решить такую задачу: «Отгадай пословицу, обойдя поле ходом шахматного коня»?

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

Задача №4*. Задача более высокого уровня.
Имеется Исполнитель алгоритма, который может передвигаться по числовой оси. Система команд Исполнителя алгоритма:

1. «Вперед N»
2. «Назад M»

                        Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было.
Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
Решение: Найдем сколько было команд «Вперед», а сколько было «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение х+(х+12)=50, где х- количество команд «Вперед». Тогда общее количество команд»Вперед» - х=19, а количество команд «Назад»: 19+12=31.
Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед3», Исполнитель алгоритма оказался на отметке числовой оси 57 (19*3=57). После выполнения 31 раз команды «Назад2» (31*2=62) он оказался бы на отметке -5. (57-62=-5).
Все эти команды можно заменить на одну команду «Назад 5»

Задача №5**. Задача повышенного уровня.
Леонардо Пизанский, известный, как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который назван его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака»(1202 год).
                        Он выглядит так: 1,1,2,3,5,8,13,21,34,55,89,144…
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих.
            Составьте словесный алгоритм проверки принадлежности введенного числа n ряду Фибоначчи.
Решение:
1. Ввести число N.
2. Установить значение первых трех чисел Фибоначчи: 1,1,2.
3. Пока введенное число N больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
3. Если число Фибоначчи равно введенному N или было введено число N=1, значит, что было введено число Фибоначчи, в противном случае – введенное число не является числом Фибоначчи.
            Приведенный словесный алгоритм сожержит начальные установки, в пункте 3 цикл с условием, а пункт 4 – это вывод результата работы алгоритма.

Способы записи алгоритмов:

1. Словесный – на естественном языке;
2. На языке блок – схем;
3. На языке программирования.

         Блок-схема – это графическое изображение алгоритма в виде определенным образом связанных между собой нескольких типов блоков.
         Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ.
Сегодня на уроке мы познакомились с понятием алгоритма и его свойствами. Следующий урок мы продолжим знакомство с алгоритмикой и поучаствуем в составлении различных блок – схем.
Проверка знаний: Тест №1 «Алгоритм и его свойства» на CD
              1.Какие из предложенных документов являются алгоритмами?
а) Правило правописания приставок, оканчивающихся на з,с  
б) Программа телепередач
в) Кулинарный рецепт приготовления блюда
г) Инструкция по сборке проданного в разобранном виде шкафа

2. В каких случаях правильно заканчивается предложение: Алгоритм – это
а) конечная последовательность действий, приводящая к искомому результату при любых допустимых исходных данных
б) указание на выполнение действий
в) конечный набор понятных некоторому исполнителю команд, выполнение которых приводит к однозначному решению поставленной задачи
г) программа в машинных кодах

3. Разбиение  алгоритма на отдельные элементарные действия – это
а) Дискретность
б) Определенность
в) Массовость
г) Детерминированность

4. Какие из документов являются алгоритмами?
А) Каталог книг в библиотеке
Б) Порядок набора международного телефонного номера
В) Рецепт приготовления клея
Г) Настенный календарь на текущий год

Задание на дом: выучить определения, привести примеры алгоритмов из жизненной практики. П. 4.1.1, № 4.1 письменно в тетради
Подведение итогов. Выставление оценок с учетом процентного выполнения теста

____________________________________________________________________________

                Сизифов труд* - Сизиф, точнее Сисиф (др.-греч. ???????) — в древнегреческой мифологии [1] строитель и царь Коринфа, после смерти (в Аиде) приговорённый богами вкатывать на гору тяжёлый камень, который, едва достигнув вершины, каждый раз скатывался вниз.
Отсюда выражения «сизифов труд», «сизифов камень», означающие тяжёлую, бесконечную и безрезультатную жизнь и муки. «Википедия»
** отрывок из рассказа «Человек с пятью «не» или исповедь простодушного», Вадим Шефнер, «Лениздат» 1980

Дополнительные материалы:
Текст:

С точки зpения банальной эpyдиции каждый индивидyyм, кpитически мотивиpyющий абстpакцию, не может игноpиpовать кpитеpии yтопического сyбьективизма, концептyально интеpпpетиpyя общепpинятые дефанизиpyющие поляpизатоpы, поэтомy консенсyс, достигнyтый диалектической матеpиальной классификацией всеобщих мотиваций в паpадогматических связях пpедикатов, pешает пpоблемy yсовеpшенствования фоpмиpyющих геотpансплантационных квазипyзлистатов всех кинетически коpеллиpyющих аспектов. Исходя из этого, мы пpишли к выводy, что каждый пpоизвольно выбpанный пpедикативно абсоpбиpyющий обьект pациональной мистической индyкции можно дискpетно детеpминиpовать с аппликацией ситyационной паpадигмы коммyникативно-фyнкционального типа пpи наличии детектоpно-аpхаического дистpибyтивного обpаза в Гилбеpтовом конвеpгенционном пpостpанстве, однако пpи паpаллельном колабоpационном анализе спектpогpафичеких множеств, изомоpфно pелятивных к мyльтиполосным гипеpболическим паpаболоидам, интеpпpетиpyющим антpопоцентpический многочлен Hео-Лагpанжа, возникает позиционный сигнификатизм гентильной теоpии психоанализа, в pезyльтате чего надо пpинять во внимание следyющее: посколькy не только эзотеpический, но и экзистенциальный аппеpцепциониpованный энтpополог антецедентно пассивизиpованный высокоматеpиальной сyбстанцией, обладаетпpизматической идиосинхpацией, но так как валентностный фактоp отpицателен, то и, соответственно, антагонистический дискpедитизм дегpадиpyет в эксгибиционном напpавлении, посколькy, находясь в пpепyбеpтатном состоянии, пpактически каждый сyбьект, меланхолически осознавая эмбpиональнyю клаyстоpофобию, может экстpаполиpовать любой пpоцесс интегpации и диффеpенциации в обоих напpавлениях, отсюда следyет, что в pезyльтате синхpонизации, огpаниченной минимально допyстимой интеpполяцией обpаза, все методы конвеpгенционной концепции тpебyют пpактически тpадиционных тpансфоpмаций неоколониализма. Hеоколонии, pазмножающиеся почкованием, имеют вегетационный пеpиод от тpех до восьми фенотипических гомозигот, но все они являются лишь фyндаментальным базисом социогенетической надстpойки кpиогенно-кpеативного пpоцесса геpонтологизации. Увеличить этот базис можно с помощью гектаплазменного yскоpителя биоинеpтных коллоидных клеток контагиозной конкpетизации, однако введение конкpетизации влечет за собой пpименение методов теории множеств и дистрибутивного анализа, что обусловлено тем, что тpансцендентальная поликонденсация неpоноспоpы в пеpплексном хаосе может инбабyлиpовать комплексный моpфоз только тогда, когда конститyент доминанты квазитенденциально yнивеpсален, и пpоисходит довольно внезапно. Очевидно, что все вышесказанное пpоливает свет на теоpию предикативных ощущений сyбьекта, абсолютно нефункциональных в условиях абстрактного хаоса.

Об уроке на примере одной задачи

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

Казалось бы, что может быть проще…

Работу над этой задачей я веду планомерно в течение нескольких уроков, причем  один из них мы полностью посвящаем этой задаче. Урок так и называется – Урок одной задачи – поиск НОД двух чисел, а на нескольких уроках мы возвращаемся к этой задаче.

Далее (скачать текст в формате .pdf)