Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы описания алгоритмов. Исполнитель алгоритма. Основные алгоритмические структуры. Выполнение алгоритма

Вид материала

Документы

Содержание Ход урока Свойства алгоритмов Определенность (однозначность) Первый способ— Третий способ— Пятый способ IV. Закрепление изученного материала V. Подведение итогов урока Аль-хорезми (783-s50)

Подобный материал:

• Основы алгоритмизации, 754.96kb.
• Программа курса «компьютерные науки» Специальность нм, 1 курс, 1 и 2 семестры (2008-2009, 88.62kb.
• Вопросы к промежуточному экзамену. Информационно-технологический профиль. 10 класс, 16.12kb.
• «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
• Реферат по теме Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок, 102.16kb.
• 1 Алгоритмизация и программирование Алгоритмы, виды алгоритмов, описания алгоритмов., 172.44kb.
• Урок Тема: Понятие алгоритма. Исполнитель алгоритма, 204.38kb.
• Задача обучения алгоритмизации заключается в том, чтобы научить составлять записи алгоритмов,, 78.61kb.
• Список ресурсов интернет «Место алгоритмов в повседневной жизни» определения алгоритма,, 26.36kb.
• Методические рекомендации к занятиям темы 7 «Алгоритмы обработки информации», 163.76kb.

Д. С. Осипенко


Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы описания алгоритмов. Исполнитель алгоритма. Основные алгоритмические структуры. Выполнение алгоритма


Цели:

обучающая: ознакомить с общим понятием алгоритмов; привести примеры; ознакомить учащихся с правилами написания алгоритмов; научить создавать алгоритмы с использованием базовых структур и правильно их записывать; научить распознавать базовые структуры в предложенных алгоритмах;

развивающая: развивать логическое мышление, умственную активность учащихся, целеустремленность, память;

воспитательная: воспитывать умение самостоятельно принимать решения.

Тип урока: комбинированный.


Ход урока

I. Организационный этап

1. Объявление темы и целей урока, его роли в теме, курсе информатики в целом и в профессиональной ориентации.
   
2. Постановка целей и раскрытие методов ее достижения на уроке.
   

II. Актуализация темы урока

1. Почему нужно записывать алгоритмы?
   
2. Что такое языки и для чего они существуют?
   
3. Нужны ли какие-то общие правила при записывании алгоритмов? Почему?
   

III. Изучение нового материала

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

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

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

Теперь мы можем сформулировать, что же такое алгоритм.


Определение. Алгоритм, алгорифм (латинизиров. Algorithmi, от имени среднеазиатского ученого математика IX в. Мухаммеда ибн Мусы аль-Хорезми) называет понятное и точное распоряжение выполнить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи. В этом определении используется понятие «исполнитель».

Что это означает? Под исполнителем алгоритма мы понимаем любое существо, способное выполнить алгоритм. Все зависит от того, какой цели мы стараемся достичь. Например, рытье ямы (исполнитель — человек или экскаватор), покупка некоторых товаров (один из членов семьи), решение математической задачи (ученик или компьютер) и т. п. Понятие алгоритма в информатике является фундаментальным, т. е. таким, которое не определяется через другие еще более простые понятия (для сравнения: в физике — понятие пространства и времени, в математике — точка).

Понятие алгоритма принадлежит к фундаментальным понятиям математики. В качестве примера из математики можно привести известную теорему Пифагора: «Квадрат гипотенузы равняется сумме квадратов катетов». Руководствуясь только формулировкой этой теоремы, вы можете получить нужный результат, т. е. гипотенузу.


Свойства алгоритмов


Алгоритмы обладают следующими характерными свойствами:

1. Понятность

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

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

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

3. Определенность (однозначность)
   

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

Например. Вас послали за каким-либо товаром в магазин, да еще и предупредили: «Без хлеба (сахара и т.п.) не возвращайся»,— а что делать, если товара нет в наличии? Так вот, точность — это свойство алгоритма, которое заключается в том, что алгоритм должен быть однозначно истолкован и на каждом этапе исполнитель должен знать, что ему делать дальше.

4. Дискретность
   

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

4. Массовость

Очень важно, чтобы составленный алгоритм обеспечивал решение не одной отдельной задачи, а мог бы выполнять решение широкого класса задач такого типа. Например, алгоритм покупки какого-нибудь товара будет всегда одинаковым, независимо от покупаемого товара. Или, алгоритм стирки не зависит от белья, которое надо выстирать и т.п. Итак, под массовостью алгоритма имеется в виду возможность его применения для выполнения большого количества однотипных задач.

5. Результативность

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

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


Способы описания алгоритма

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

Второй способ— подача в виде таблиц, формул, схем, рисунков и т.п. Например, в детском саду вас знакомили с правилами поведения на дороге. И лучше всего дети, очевидно, воспринимают алгоритм, представленный в виде схематических рисунков. Глядя на них, ребенок, а потом и взрослый человек, вырабатывает ту линию поведения, которая ему предлагается. Аналогично можно привести примеры алгоритмов, записанных в виде условных обозначений на купленном товаре относительно его использования (заваривание чая, стирка белья и т.п.). В математике наличие формул позволяет решить задачу даже «без слов».

Третий способ— запись с помощью блок-схемы.

Этот метод был предложен в информатике для наглядности представления алгоритма с помощью набора специальных блоков.


Основные блоки:





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

Эти языки имеют четко определенный синтаксис и уже максимально приближены к машинному языку (языку программирования). Однако созданы они с учебной целью, поэтому имеют понятный для человека вид. Подобных псевдокодов сейчас огромное количество, начиная с таких графических сред, как «Алгоритмика», «Роботландия», «Лого-миры», «Ракушка» и т.п., и заканчивая текстовыми «национальными» реализациями алгоритмических языков, подобных языку Паскаля. Такие псевдокоды имеют программную реализацию и широко применяются на этапе обучения основам программирования.

Пятый способ максимально приближен к компьютеру — это языки программирования.

Дело в том, что чаще всего на практике исполнителем созданного человеком алгоритма является машина, поэтому алгоритм должен составляться на языке, понятном для компьютера, т. е. на языке программирования.


Существуют четыре базовые структуры алгоритмов:

• линейные;
  
• разветвленные;
  
• циклические;
  
• смешанные.
  

IV. Закрепление изученного материала

Повторение с учениками основных моментов новой темы.

Выполним несколько заданий

1. Вспомните алгоритм деления отрезка пополам. Что является аргументами этого алгоритма? Конечно, концы отрезка, а результатом — точка отрезка, которая является его серединой. Есть ли тут промежуточные величины? Да, это засечки в разных полуплоскостях, границей которых является прямая, содержащая данный отрезок; прямая, проходящая через точки-засечки. Проанализируйте, все ли свойства соблюдаются для этого алгоритма?

2. Сформулируйте задачу о перевозке волка, козы и капусты. Запишите алгоритм с графической иллюстрацией (схематичными рисунками) решение этой задачи. Является ли этот алгоритм массовым? Дискретным? Конечным?
   
3. В начальной школе, после того как вы выучили таблицу умножения, ваша первая учительница показывала фокус отгадывания задуманное числа, при этом вы задумывали число и выполняли, допустим, следующие действия:
   

1. умножить задуманное число на 5;
   
2. к произведению прибавить 8;
   
3. полученную сумму умножить на 2;
   
4. сообщить результат.
   

А уже по указанному результату учительница безошибочно отгадывала задуманное число. Как же это ей удавалось? Cоставьте алгоритм угадывания задуманного числа. Проанализируйте этот алгоритм по свойствам.

4. Рассмотрим задачу. Генерал отправил на рынок денщика продать пару сапог, за которые назначил цену в 15 руб. денщик на рынке встретил двоих одноногих солдат-инвалидов, которым продал сапог по 7,5 руб. за каждый. Генерал, узнав о том, что покупатели — инвалиды, дал денщику 5 руб. и велел вернуть им по 2,5 руб. каждому. Денщик по дороге на рынок решил, что генерал не обеднеет и прикарманил 3 руб., а найдя солдат, вернул им по 1 руб.

А теперь посчитаем. Каждый из инвалидов заплатил за свой сапог по 7,5 — 1 = 6,5 (руб.), что в сумме составляет 13 руб. 3 руб. денщик взял себе. 13 + 3 = 16 (руб.) стоили сапоги. Откуда взялся лишний рубль?

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


V. Подведение итогов урока

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


VI. Домашнее задание

Конспект. Подготовить доклад на тему «Система команд исполнителя».


Дополнительная информация


АЛЬ-ХОРЕЗМИ (783-S50)


Полное имя — Абу Абдаллах (или Абу Джафар) Мухаммад ибн Муса ал Хорезми в переводе с арабского означает — отец Абдаллаха [или отец Джафара] Мухаммад, сын Мусы из Хорезма, один из крупнейших ученых (математик, астроном, историк, географ) Средневековья. Биографические сведения о нем почти не сохранились, известно лишь, что он родился в конце VIII в. (предположительно в Хиве), а умер во второй половине IX в. Приведенные годы жизни — условны. В некоторых источниках его называют «аль-маджуси», т.е. маг, из этого делается вывод, что его предки были магами, жрецами зороастрийской религии, широко распространенной в те времена в Средней Азии.


Имя аль-Хорезми мы упоминаем в связи с понятием «алгоритма». Считается, что слово «алгоритм» происходит от имени великого среднеазиатского учёного Мухаммеда аль-Хорезми. Около 825 года аль-Хорезми написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы исчисления. К сожалению, арабский оригинал его книги не сохранился, так что её оригинальное название нам неизвестно. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру О для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как цифра и шифр). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе стала известна в Европе. Переводчик, имя которого до нас не дошло, дал ей название «Algoritmi de numero Indorurra («Индийское искусство счёта, сочинение аль-Хорезми»).


Таким образом, мы видим, что латинизированное имя аль-Хорезми было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.


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


За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н.Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья». А это означает, что слово живёт, обогащаясь всё новыми значениями и смысловыми оттенками.


Журнал «Всё для учителя. Информатика»

Пилотный выпуск, 2010