Информатика

Тема: Алгоритм и исполнители

Урок: Что такое алгоритм

1. Тема урока.

На этом уроке мы узнаем, что такое алгоритм, а также рассмотрим сложности при составлении алгоритмов и пример составления и выполнения алгоритма.

2. Что такое алгоритм?

На этом уроке мы начинаем изучать одно из важнейших понятий в информатике – алгоритм. Алгоритм – это последовательность действий.

С алгоритмами мы сталкиваемся практически каждый день. Иногда даже сами того не осознавая. Например, когда просим кого-то купить продукты в магазине. Мы объясняем, какие нужны продукты, сколько их, какие требования к ним мы предъявляем. К примеру: купить две буханки чёрного хлеба, причём свежего.

Мы указываем чёткий алгоритм: необходимо зайти в магазин, узнать, есть ли чёрный хлеб. Затем узнать, свежий ли этот хлеб. А уже после этого (в случае двух положительных ответов) купить две буханки.

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

Сегодня мы более подробно поговорим об алгоритмах.

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

Например, процесс покупки хлеба можно представить так:

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

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

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

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

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

Впоследствии, когда мы познакомимся с языками программирования, то узнаем, что алгоритм с ошибкой в некотором смысле «лучше», чем алгоритм, который работает, но неправильно. Ведь, если ошибка есть, и компьютер нам об этом сообщит, то мы сможем её найти и исправить. А если ошибка, как в приведенном нами примере, проявляется только в редких случаях? В этом случае мы можем запускать программу сотни раз, и она покажет правильный результат, а в самый ответственный 101-ый раз неожиданно не сработает.

Легко ли составить алгоритм?

Преобразование информации кажется нам делом очень простым. Однако, на самом деле это далеко не так.

Особенно это касается составления алгоритма для правильного преобразования информации.

Простейшим примером такого алгоритма является инструкция пользователя к любому предмету. Если она составлена некачественно, то пользователь рискует либо поломать предмет из-за неправильной эксплуатации, либо не научиться с ним работать.

Многие скажут, что составить инструкцию для готового прибора очень легко. Однако будут неправы. Почему? Всё очень просто: большинству людей гораздо проще сделать что-то самим, чем объяснить остальным, как это делается.

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

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

Задание. Составить алгоритм приготовления кофе для робота (Рис. 1).

Рис. 1. Чашка кофе (Источник)

Думаю, многие из вас мысленно составили следующую модель алгоритма:

1. Взять чашку.
2. Положить в неё кофе.
3. Насыпать сахар.
4. Залить кипятком.
5. Помешать ложкой.
6. Разбавить кипячёной водой.

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

Далее – положить кофе можно ложкой, можно руками. Кроме того, не сказано: сколько кофе необходимо положить, то есть робот может бросить маленькую щепотку, а может засыпать полную чашку.

Аналогичная ситуация с сахаром и кипятком. В общем, вырисовывается целый ряд проблем.

Именно с такими проблемами и сталкиваются «специалисты» при составлении инструкций для «неспециалистов».

Попытаемся составить более полный алгоритм (хотя и его можно совершенствовать практически до бесконечности):

1. Взять в серванте прозрачную чашку с надписью «Моя»!
2. Поставить чашку на кухонный стол дном вниз.
3. Достать из шкафа, который расположен слева от серванта, контейнеры с надписью «Кофе» и «Сахар» и поставить их на стол рядом с чашкой.
4. Взять в серванте чайную ложку.
5. Насыпать в чашку одну полную чайную ложку вещества из контейнера с надписью «Кофе», а затем одну чайную ложку вещества из контейнера с надписью «Сахар».
6. Взять только что закипевший чайник и налить из него кипятка в чашку так, чтобы она была заполнена примерно на 2/3.
7. Чайной ложкой равномерно и не спеша помешать кофе в чашке в течение минуты.
8. Вынуть чайную ложку из чашки и положить в раковину.
9. Взять с кухонного стола графин с кипячёной водой и налить из него воду в чашку так, чтобы она была заполнена приблизительно на 90%.

Безусловно, этот алгоритм не является совершенным и предполагает знание роботом многих вещей, однако даже он показывает, насколько трудно описать те вещи, которые каждый из нас умеет делать с раннего детства. Возможно, именно поэтому создание полноценного искусственного интеллекта имеет весьма отдалённые перспективы. Это связано, в первую очередь, с тем, что нужно научить компьютер «думать» и «анализировать», как человек, потому что полностью «вложить» в него все человеческие знания практически невозможно. А ещё сложнее научиться ими распоряжаться.

Алгоритм Эвклида

Наибольший общий делитель двух чисел – как вы уже знаете – это наибольшее целое число, на которое делятся оба исходных числа.

Алгоритм Эвклида (Рис. 2) помогает находить наибольший общий делитель (НОД) двух чисел.

Рис. 2. Эвклид (Источник)

Алгоритм Эвклида имеет следующий вид:

1. Сравнить числа а и б. При сравнении возможны два случая: а=б, аб. Если а=б, то за НОД принять любое из них. Вычисление прекратить. Если аб, перейти к указанию 2.
2. Если а<б, перейти к указанию 3, если а>б, перейти к указанию 4.
3. Поменять местами а и б. Перейти к указанию 4.
4. Вычесть из а б. Перейти к указанию 5.
5. Если разность равна 0, то за НОД принять число б. Вычисление прекратить. Если разность отлична от нуля, перейти к указанию 6.
6. За новое вычитаемое взять полученную разность, а за новое уменьшаемое взять старое число б. Перейти к указанию 1.

Рассмотрим нахождение НОД (24; 54) с помощью этого алгоритма

• 1) 2454; 2) 24<54; 3) 54>24; 4) 54-24=30; 5) 300; 6) (24;30)
• 1) 24; 2) 24<30; 3) 30>24; 4) 30-24=6; 5) 60; 6) (24;6)
• 1) 24; 2) 24>6; 3) 24-6=18; 4) 180; 5) (6;18)
• 1)   18; 2) 6<18; 3) 18>6; 4) 18-6=12; 5) 120; 6) (6;12)
• 1)   ; 2) 6<12; 3) 12>6; 4)12-6=6; 5) 60; 6) (6;6)
• 1)                 .

Ответ: НОД(24;54)=6.

Подумайте: обязателен ли в этом алгоритме пункт под номером 5.

3. Пример алгоритма.

С алгоритмами вы уже не раз сталкивались на уроках математики. Например, при решении различных примеров на вычисление. Более того, сложение, вычитание, умножение и деление чисел в столбик – это также результат выполнения алгоритма.

Рассмотрим такой пример (Рис. 3):

Вычислить: .

• ;
• ;
• ;
• ;
• .

Рис. 3. (Источник)

Можно ли изменить порядок действий в этом случае?

На самом деле, нет, так как действия при решении примеров выполняются в строго определённом порядке.

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

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

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

О происхождении слова «алгоритм»

Правила выполнения арифметических действий над целыми числами и простыми дробями в десятичной системе счисления впервые были сформулированы выдающимся средневековым ученым по имени Мухаммед ибн Муса ал-Хорезми (в переводе с арабского это означает «Мухаммед, сын Мусы из Хорезма»), сокращенно Ал-Хорезми (Рис. 4).

Рис. 4. Мухаммед ибн Муса ал-Хорезми (Источник)

Ал-Хорезми жил и творил в IX веке. Арабский оригинал его арифметического труда утерян, но имеется латинский перевод ХІІ века, по которому Западная Европа ознакомилась с десятичной позиционной системой счисления и правилами выполнения в ней арифметических действий.

Ал-Хорезми стремился к тому, чтобы сформулированные им правила были понятны для всех грамотных людей. Достичь этого в веке, когда еще не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и т. п.), было очень трудно. Но Ал-Хорезми удалось выработать в своих трудах такой стиль четкого, строгого словесного предписания, который не давал читателю никакой возможности уклониться от предписанного или пропустить какие-нибудь действия.

В латинском переводе книги Ал-Хорезми правила начинались словами «Алгоризми сказал». С течением времени люди забыли, что «Алгоризми» – это автор правил, и стали сами эти правила называть алгоритмами. Постепенно «Алгоризми сказал» преобразовалось в «алгоритм гласит».

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

 

На этом уроке мы рассмотрели определение алгоритма и простейшие примеры различных алгоритмов.

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

 

Список литературы

1. Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012
2. Босова Л.Л. Информатика: Рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.
3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5-6 классах: Методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Фестиваль педагогических идей "1 сентября" (Источник).
2. Nsportal.ru (Источник).
3. Методическая копилка учителя информатики (Источник).

 

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

1. §3.1 (Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса);
2. Стр. 68 задание 2, 4 (Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса);
3. Стр. 68 задание 5, 6 (Босова Л.Л. Информатика и ИКТ: Учебник для 6 класса).