 |
Алгоритм «Заточи сломанные карандаши»
|
|
|
|
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ
ГБОУ СПО ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ № 39
МЕТОДИЧЕСКАЯ РАЗРАБОТКА
Темы 6: «Алгоритмы и способы их описания»
дисциплины «Информатика и ИКТ»
для групп первого курса СПО
технический профиль
Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но и одним из главных понятий современной науки. Более того, сегодня с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации.
В.А. Успенский
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин.
Термин «алгоритм» происходит от имени узбекского ученого IX века Абу Абдуллы Муххамеда бен Мусы аль–Хорезми («аль-Хорезми» означает «хорезмиец», человек из города Хорезми). В настоящее время Хорезми – город Хива в Хорезмской области Узбекистана). Узбекский ученый в своем труде «Арифметический трактат», переведенном в XI веке с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Позже в Европе эти приемы назвали алгоритмами от “ Algorithmic ” – латинского написания имени аль - Хорезми.
Многие годы понятие «алгоритм» использовались математиками для описания правил решения математических задач.
В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Однако не следует считать алгоритм чисто математическим понятием. Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи различной сложности: как быстрее добраться в школу, колледж или на работу в условиях нехватки времени; в каком порядке выполнить дела, намеченные на текущий день и т. д. Для описания этих задач используется тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний.
|
|
|
В подавляющем большинстве случаев успех любой деятельности человека зависит от степени продуманности действий и их последовательности, возможных вариантов. Именно с целью успешного решения какого-либо определенного класса задач люди вырабатывают системы таких предписаний для использования различными людьми.
Для решения любой задачи надо знать, что дано и что следует получить, т. е. у задачи есть исходные данные (некие объекты) и искомые результаты. Для получения результатов необходимо знать способ решения задачи, т. е. располагать алгоритмом (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнять, чтобы решить задачу (получить искомые результаты).
Алгоритм – это конечная последовательность однозначных предписаний, исполнение которых позволяет с помощью конечного числа шагов получить решение задачи, однозначно определяемое исходными данными.
Приведенное выше определение не является определением в математическом смысле слова, т. е. это не формальное определение. А довольно подробное описание понятия алгоритма, раскрывающее его сущность.
Каждый алгоритм создается конкретным автором (человеком или группой людей) в результате обобщения прошлого опыта или технологических разработок и рассчитан на конкретного исполнителя.
По своему назначению алгоритмы могут быть как «бытовыми», так и вычислительными.
НАПРИМЕР:
Носителями алгоритмов являются фоторецептурные справочники, инструкции по использованию бытовой аппаратуры, медицинские рекомендации и описание гимнастических упражнений.
|
|
|
Алгоритмы «бытовой сферы» (иногда их называют интуитивными) всегда предполагают, определенный уровень предварительной подготовки исполнителя и потому излагаются операции, способ выполнения, которых (тоже алгоритм) избирается самим исполнителем. Даже в простейших ситуациях Вы, не задумываясь, оцениваете уровень исполнителя.
Автор кулинарного рецепта предполагает, что хозяйка умеет включать и выключать газовую или электрическую плиту, регулировать нагрев.
В инструкции по применению водоэмульсионной краски не описывается техника вскрытия банки т. д.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять.
Не только в быту, но и в технике, и даже в математике многие алгоритмы формулируются приблизительно, т. к. рассчитаны на конкретного исполнителя. Отметим, что для каждого исполнителя набор допустимых действий всегда ограничен – не может существовать исполнителя, для которого любое действие является допустимым.
Для использования алгоритма в информатике требуется более точное определение алгоритма, чем приведенное выше.
! Компьютер – автоматический исполнитель алгоритма.
Ключевыми словами, раскрывающими смысл этого понятия, являются: исполнитель, команда, система команд исполнителя.
Алгоритм представляет собой последовательность команд (инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта).
! Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей, знаний и умений, другими словами, каждый исполнитель имеет свой перечень команд, которые он может исполнить. Такой перечень команд называется системой команд исполнителя алгоритмов.
Средства, используемые для записи алгоритмов, в значительной степени определяются тем, для какого исполнителя предназначается алгоритм.
Если алгоритм предназначен для исполнителя человека, то запись может быть не полностью формализована, на первое место здесь выдвигаются понятность и наглядность, поэтому для записи таких алгоритмов может использоваться естественный или графический язык, лишь бы запись отражала все основные особенности алгоритма. Для записи алгоритмов предназначенных для исполнителей автоматов, необходима формализация, поэтому в таких случаях применяют формальные специальные языки.
|
|
|
! Способы записи алгоритмов:
1. словесная (текстовая) форма записи;
2. графическая форма записи - схемы алгоритмов;
3. программная - запись алгоритма на алгоритмическом языке;
Псевдокоды.
1. Словесная запись алгоритма содержит тщательно отобранный набор фраз, без повторений и неоднозначностей Команды алгоритма нумеруются, чтобы иметь возможность на них ссылаться. В командах помимо слов могут использоваться символы и формулы. Форма записи команд не формализованная. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противное.Словесная запись алгоритма ориентирована на исполнителя – человека.
Важно лишь, чтобы каждая команда была понятна исполнителю, точно определяла все его действия и могла быть им выполнена.
Приведем в качестве примера словесной формы записи алгоритма алгоритм «бытовой сферы».
Пример:
Алгоритм «Посади дерево»
1) Возьми лопату и саженец.
2) Выкопай ямку.
3) Возьми саженец.
4) Посади саженец в ямку.
5) Засыпь ямку землей.
6) Возьми лейку с водой и полей саженец.
7) Поставь лопату и лейку на место.
2. Схемы алгоритмов – это графическое представление метода решения задачи.
Схемы представляют алгоритм в наглядной форме. Команды алгоритма помещаются внутрь блоков, соединенных стрелками, показывающими очередность выполнения команд алгоритма. Приняты определенные стандарты графических изображений:
 |
Рис. 1
Для записи внутри блоков используется естественный язык с элементами математической символики. В блоке «Проверка условия» в результате проверки условия возникают два возможных пути продолжения алгоритма. Эти пути отражаются стрелками с соответствующими надписями “Да” и “Нет”.
Рассмотрим алгоритм “бытовой сферы”, записанный двумя способами: словесной записью и с помощью схемы алгоритма.
|
|
|
Пример:
Алгоритм «Заточи сломанные карандаши»
1. Собери все сломанные карандаши.
2. Возьми точилку.
3. Возьми один сломанный карандаш.
4. Заточи его.
5. Если есть еще сломанные карандаши, перейди к пункту 3.
Блок-схема алгоритма
 |
Рис. 2
Схемы алгоритмов обладают большей наглядностью, чем словесная запись алгоритма. Однако, эта наглядность быстро теряется при изображении очень большого алгоритма, т. к. в этом случае схема получается плохо обозрима.
- Псевдокод – это язык записи структурированных алгоритмов, состоит из смеси языка высокого уровня и фраз родного языка исполнителя. Стандартов на псевдокод нет, существует он как средство разработки программ. По сравнению со словесным алгоритмом псевдокод ближе программным конструкциям. Основное достоинство псевдокода – он позволяет пользователю легко разобраться в самом длинном и сложном алгоритме, поэтому чаще всего псевдокод используется для документирования программ.
Исполнители алгоритмов.
Задача составления алгоритма не имеет смысла, если неизвестны или не учитываются возможности его исполнителя, ведь выполнимость алгоритма зависит от того, какие действия может совершить исполнитель. Это означает, что алгоритм пишется для конкретного исполнителя.
Исполнителем алгоритма может быть человек или автомат. Например, банкомат, исправный автомат по продаже напитков работает согласно разработанному специально для него алгоритму, компьютер. Алгоритмом описывается работа любого механического устройства.
В ряду всевозможных автоматов компьютер является частным (хотя и наиболее впечатляющим) примером исполнителя, чье поведение реализуется на основе алгоритма. Более того, создание компьютеров оказало воздействие на развитие теории алгоритмов – одной из областей математики.
От компьютера, как от любого другого исполнителя, требуется четкое выполнение команд алгоритма. А от нас, как от разработчиков алгоритмов работы компьютера, требуется знание и соблюдение правил их составления. Эти правила заключаются в том, что алгоритм должен обладать пятью свойствами (удовлетворять пяти требованиям). Эти требования нашли отражение в приведенном выше определении алгоритма.
|
|
|
