В жизни нам часто приходится встречаться с различными ситуациями, в которых мы совершаем одни и те же определенные действия. Для того, чтобы вовремя проснуться, нам нужно не забыть включить будильник. Для того, чтобы утолить свой голод, нам необходимо выполнить одни и те же действия по приготовлению вкусной пищи. Для того, чтобы выполнить знакомую нам работу, мы тоже часто делаем одно и то же.
Такое поведение можно называть по-разному, смотря в каком контексте оно рассматривается. Если рассмотреть с позиции эффективности деятельности, то эти действия можно назвать привычками или навыками. Если рассматривать с точки зрения отображения процесса, то описание последовательности действий, строгое исполнение которых приводит к решению поставленных задач за определенное количество шагов, называют алгоритмом действий.
Как создаются алгоритмы действий?
Мы постоянно сталкиваемся с этим в обычной жизни. Какие действия мы совершаем, чтобы пополнить счет своего мобильного телефона? Каждый из нас — разные. Так как способов пополнения счета несколько, следовательно мы все по-разному это делаем. Результат, правда всегда один получается — появление средств на телефоне.
Или еще пример: чтобы скопировать картинку или текст, нажимаем правой кнопкой мыши на картинку, затем выбираем «Копировать», помещаем в нужное место, нажимаем правой кнопкой » Вставить», и результат достигнут.
Все это — определенная последовательность действий, в результате которых различными средствами решается поставленная задача. Но пока это только наши знания, которые перерастают в навыки и умения, а если этот процесс описать, то мы сможем наглядно увидеть алгоритм наших действий, и передать его другим людям. На словах не все и не всегда понятно бывает.
Опишите последовательность действий — это запоминается
Создать алгоритм действий можно, описав или изобразив его последовательность. Знают ли все, что надо сделать, чтобы посадить дерево? Возможно, основные шаги понятны всем, но вот когда деревце поливать, перед посадкой или после, помнит не каждый. Созданный алгоритм позволит все действия выполнить в правильной последовательности.
Чтобы описать последовательность действий посложнее, придется постараться и подробно их все записать. Пример можно взять с всевозможных правил и инструкций — там очень четко прописываются по шагам действия, которые нам надо сделать. Но бывают ситуации, в которых за определенным действие следует не один шаг, а несколько, в зависимости от предыдущего результата. В таком случае, предположительные действия тоже записывают, чтобы человек мог легко сориентироваться в разных ситуациях, и знал, что нужно предпринять.
Алгоритм действий в графике — это блок-схема
Если изобразить алгоритмы действий в графическом варианте, с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения действия, то мы получим блок-схему. Блок-схема намного превосходит правила, инструкции, и записанные по порядку алгоритмы действий, по своей наглядности и читаемости.
Представьте, что вам нужно чему-то научить другого человека. Вы отлично знаете все действия в определенной последовательности. Ваша задача — показать, как это нужно делать и передать свои знания так, чтобы другой человек их запомнил и знал так же, как и вы. Устная передача знаний допускает импровизации и некоторый произвол. Самым лучшим способом будет блок-схема, в которой объясняется последовательность и возможные варианты действий. В качестве примера — веселое руководство по изучению блог-схем:
Лучшим условием для получения результата будет повторяемость действий. Это однозначно влияет на скорость достижения результата в будущем. Чем чаще вам придется повторять одни и те же действия, тем быстрее вы научитесь выполнять последовательность действий, а значит в каждый последующий раз, вам потребуется меньше времени на выполнение.
Блок-схемы применяются в продажах
В продажах такое обучение с помощью разработки алгоритмов и изображения их в виде блок-схем имеет большое распространение. Чаще всего их используют в телефонных сценариях разговоров в call-центрах и для «холодных» звонков. Корпоративная культура набирает обороты, поэтому многие компании уже не позволяют сотрудникам нести «отсебятину», даже талантливую, а предлагают действовать им по заранее разработанному сценарию, представляя «лицо фирмы» на различных этапах. Эффект появляется буквально после нескольких дней действий «по бумажке». Со временем, многое из описанных алгоритмов запоминается сотрудником, и в дальнейшем он свободно может общаться, не опасаясь того, в какую сторону может уйти разговор.
Алгоритмы действий и блог-схемы разрабатываются не только в продажах. Большое распространение они имеют в обучении и практике врачей, программистов, «компьютерщиков», у многих технических специальностей.
Стоит попробовать научиться действовать по подобным блок-схемам. Ведь впервые встречаясь с непонятным поначалу обилием действий и задач, думаешь о том, как тебе не хватает разработанной блок-схемы. После долгих мучений не выдерживаешь, и начинаешь разрабатывать и создавать самостоятельно. Эффективные люди не любят простоев в делах. А блок-схемы значительно упрощают жизнь и позволяют разобраться в решении сложных задач.
Сервисы для разработки блок-схем
В интернете есть сервисы, которые могут помочь вам создавать такие блок-схемы. Один из них — Сacoo . С его помощью вам легко удастся превращать ваши алгоритмы в различные диаграммы, блок-схемы и графики. Вы увидите, что это очень приятное и радостное занятие — преобразовывать то, что вам известно, в науку для других людей.
— хорошее настроение вам обеспечено. На первоначальном этапе можно воспользоваться возможностями бесплатной учетной записи, а в будущем за доступ нужно будет платить. Естественно, что бесплатный доступ имеет ограничения по сравнению с платными. Но для изучения и первых шагов, функционала вполне достаточно.
Разработав алгоритмы действий и преобразовав их в блок-схемы с помощью Cacoo, вы сможете надолго создать хорошее настроение не только себе, но и другим людям, постигающим азы.
Создавайте игровые блок-схемы для своих детей
Подводя итог вышесказанному отмечу, что теперь вы сможете использовать алгоритмы действий и блок-схемы в различных жизненных ситуациях. Даже ваши дети с огромным удовольствием станут выполнять не самые интересные обязанности, следуя понятным подсказкам. Если будут идеи, где и как можно применять алгоритм действий , поделитесь в комментариях, уважаемые читатели. Очень хотелось бы узнать про ваши алгоритмы.
Моя блок-схема
Вот какая блок-схема у меня получилась в первый раз. Для того, чтобы увеличить изображение, нажмите на него. После перехода на Cacoo, под записью «просмотр фигуры», нажимайте на картинку. Она откроется в большом окне. Удачи!
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Первоначально под словом алгоритм понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Само же слово алгоритм появилось в Средние века, когда европейцы познакомились со способами выполнения арифметических действий, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми. Слово алгоритм - европеизированное произношение слов аль-Хорезми .
В своем нынешнем смысле слово алгоритм часто ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя (НОД) двух чисел.
Приведем современное описание алгоритма Евклида с использованием блок-схемы (см. “Способы записи алгоритмов ”):
Стрелка “”, используемая при описании данного алгоритма, обозначает операцию замещения или присваивания (см. “Операторы языка программирования ”). Разумеется, в книге Евклида “Начала” этот алгоритм сформулирован не совсем так (а записан совсем не так). В данном случае мы продемонстрировали современную формулировку этого алгоритма и одну из распространенных наглядных форм записи алгоритмов.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (см. “Исполнители алгоритмов ”). Алгоритм описывается в командах исполнителя , который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя , а множество команд, которые исполнитель может выполнять, - систему команд исполнителя (СКИ).
Таким образом, алгоритм можно рассматривать как последовательность команд управления работой исполнителя (предписание исполнителю на выполнение последовательности действий).
Свойства алгоритма
Значение слова алгоритм очень схоже со значением слов рецепт , инструкция . Однако любой алгоритм в отличие от рецепта или способа обязательно обладает следующими свойствами.
1. Выполнение алгоритма разбивается на последовательность законченных действий-шагов. Только выполнив одно действие (команду), можно приступать к исполнению следующего. Это свойство алгоритма называется дискретностью . Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма (команда).
2. Понятность - алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т.е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на выполнение “не размышляющего” исполнителя . Алгоритм составляется из команд, входящих в СКИ.
Рассмотрим известный пример “бытового” алгоритма - алгоритм перехода улицы: “Посмотри налево. Если машин нет, дойди до середины улицы. Если есть, подожди, пока они проедут, и т.д.”. Представьте себе ситуацию: машина слева есть, но она не едет - у нее меняют колесо. Если вы думаете, что исполнитель алгоритма должен ждать, то вы поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.
3. Детерминированность (определенность и однозначность ). Каждая команда алгоритма определяет однозначное действие исполнителя, и должно быть однозначно определено, какая команда выполняется следующей. То есть если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат.
4. Результативность - исполнение алгоритма должно закончиться за конечное число шагов, и при этом должен быть получен результат решения задачи. В качестве одного из возможных результатов может быть и установление того факта, что задача решений не имеет.
Свойство результативности содержит в себе свойство конечности - завершение работы алгоритма за конечное число шагов.
5. Массовость - алгоритм пригоден для решения любой задачи из некоторого класса задач, т.е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма.
Свойство массовости определяет скорее качество алгоритма, а не относится к обязательным свойствам (как дискретность, понятность и пр.). Существуют алгоритмы, область применимости которых ограничивается единственным набором входных данных или даже отсутствием таковых (например, получение фиксированного числа верных цифр числа p ). Правильнее говорить о том, что алгоритм должен быть применим к любым данным из своей области определения, и слово массовость не всегда подходит для описания такого свойства.
Понятие алгоритма
Обобщив вышесказанное, сформулируем следующее понятие алгоритма.
Алгоритм - понятное и точное предписание исполнителю на выполнение конечной последовательности действий, приводящей от исходных данных к искомому результату.
Приведенное определение не является определением в математическом смысле слова, т.е. это не формальное определение (формальное определение алгоритма см. в статье “Теория алгоритмов ”).
Отметим, что для каждого исполнителя набор допустимых действий (СКИ) всегда ограничен - не может существовать исполнителя, для которого любое действие является допустимым. Перефразированное рассуждение И.Канта обосновывает сформулированное утверждение следующим образом: “Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднять. Но это противоречит допустимости действия «Поднять любой камень»”.
Интересно, что существуют задачи, которые человек, вообще говоря, умеет решать, не зная при этом алгоритм ее решения. Например, перед человеком лежат фотографии кошек и собак. Задача состоит в том, чтобы определить, кошка или собака изображена на конкретной фотографии. Человек решает эту задачу, но написать алгоритм решения этой задачи пока чрезвычайно сложно.
С другой стороны, существуют задачи, для которых вообще невозможно построить процедуру решения. Причем данный факт можно строго доказать. Об этом вы можете прочитать в статье “”.
Данная тема традиционно изучается в базовом курсе информатики основной школы. Содержание статьи “Алгоритм” может рассматриваться в качестве базового минимума информации по этой теме для учеников 8–9-х классов. В пропедевтическом курсе информатики (5–7-е классы) более актуальным является составление конкретных алгоритмов с использованием различных форм их записи, в том числе и для учебных исполнителей (см. “Исполнители алгоритмов ”).
Каждый из нас ежедневно решает задачи различной сложности: как быстрее добраться в школу или на работу в условиях нехватки времени; в каком порядке выполнять дела, намеченные на текущий день, и т.д. Некоторые задачи настолько сложны, что требуют длительных размышлений для нахождения решения (иногда решение так и не удается найти), другие задачи мы решаем автоматически, так как выполняем их ежедневно на протяжении многих лет (почистить утром зубы; позвонить другу по телефону). В большинстве случаев решение каждой задачи можно подразделить на простые этапы.
Пример. Задача “Звонок другу по телефону” подразделяется на следующие этапы (шаги):
1. Поднять телефонную трубку.
2. Если услышал гудок, то набрать номер друга, иначе конец решения задачи с отрицательным результатом (телефон неисправен).
3. Определить тип гудков: “вызов” или “занято”. Если “вызов”, перейти к шагу 4, если “занято”, перейти к шагу 6.
4. Дождаться 6 вызывающих гудков (конкретное число гудков в алгоритме для разных людей может быть различным).
5. Если за это время абонент не поднял трубку, то конец решения задачи с отрицательным результатом (абонент не отвечает). Иначе начать разговор (задача решена успешно).
6. Положить телефонную трубку; конец решения задачи с отрицательным результатом (абонент занят).
Последовательность шагов, приведенная в примере 1, является алгоритмом решения задачи “Звонок другу по телефону”. Исполнитель этого алгоритма - человек. Объекты алгоритма - телефон и телефонные сигналы.
При разборе алгоритма “Звонок другу по телефону” следует обратить внимание на п. 4 (“дождаться 6 вызывающих гудков”): без указания конкретного числа гудков нарушается сразу несколько свойств алгоритма (дискретность, определенность и результативность). Естественно, вместо числа 6 в алгоритме может стоять любое другое разумное число.
Для решения любой задачи надо знать, что дано и что следует получить, т.е. у задачи есть исходные данные (некие объекты) и искомые результаты. Для получения результатов необходимо знать способ решения задачи, то есть располагать алгоритмом , в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу (получить искомые результаты). Далее следует разобрать свойства алгоритма на примере решения какой-либо бытовой проблемы. Составление алгоритмов для решения бытовых проблем только на первый взгляд кажется простым, мы очень многие действия делаем автоматически, и их формализация требует от учащихся учета многих деталей и факторов.
При изложении теоретического материала необходимо обратить внимание на то, почему приведенное определение алгоритма не является строгим математическим определением , а является только описанием понятия алгоритм , раскрывающим его сущность. Оно не является формальным потому, что в нем используются такие не уточняемые понятия, как “система правил”, “исходные данные”, и т.д.
В рамках изучения этой темы желательно также обсудить вопрос, является ли способ переправки Волка, Козы и Капусты через реку алгоритмом (эта задача рассматривается во многих учебниках информатики как пример задачи на построение алгоритмов)? Иногда ученики сначала склоняются к мнению, что решение упомянутой задачи алгоритмом не является, т.к. не обладает свойством массовости. Но способ решения частной задачи - это тоже алгоритм (см. замечания о массовости в тексте статьи).
Стоит отметить, что областью применимости данного конкретного алгоритма являются все наборы объектов, которые характеризуются теми же взаимоотношениями, что и Волк, Коза и Капуста. Например, Удав, Кролик и Морковка.
Иногда вызывает споры и свойство конечности алгоритма. В качестве контрпримеров приводятся алгоритмы работы операционной системы и атомной электростанции. Не углубляясь в спор, заметим, что здесь делается попытка представить алгоритм, в котором в качестве исходного объекта рассматривается компьютер, обладающий непрерывными свойствами (бесконечная бесперебойная работа вне зависимости от действий пользователя и проблем с “железом”). Алгоритмы же работают по определению только с дискретными объектами (см. статью “Теория алгоритмов ”). Кроме того, свойство конечности существенно при доказательстве ряда фундаментальных утверждений в теории алгоритмов (см., например, “Алгоритмически неразрешимые проблемы ”), поэтому опускать его даже в рамках базового курса информатики не следует.
Важным при изучении данной темы является и понятие исполнителя . Причем оказывается, что гораздо проще построить алгоритм для программно-управляемого автомата (в том числе компьютера), чем для человека. Подробнее об этом рассказано в статье “Исполнители алгоритмов ”. Для управления автоматом или компьютером можно придумать формальный язык описания алгоритмов. Такие языки называются “Языки программирования ”, а сам алгоритм, записанный на таком языке, - программой.
При изучении данной темы полезным оказывается построение алгоритмов, известных ученикам из курса математики, но записываемых в математике менее формально. Например, алгоритм решения квадратного уравнения (в информатике более полезно решать обобщенно-квадратное уравнение, в котором коэффициент при x 2 может быть равен 0), алгоритм решения задач на построение (здесь особое внимание следует уделять детерминированности алгоритма) и т.п.
В курсе информатики средней школы к понятию алгоритма можно вернуться в контексте изучения темы “Моделирование ”. Ведь алгоритм можно рассматривать как информационную модель деятельности исполнителя.
В профильном курсе информатики углубление данной темы происходит в результате знакомства с основами “Теории алгоритмов ”, в рамках которой в первую очередь дается уже формальное определение алгоритма.
Слово "Алгоритм" происходит от algorithmi - латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело - реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его его допустимыми действиями . Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Для алгоритмов, встречающихся в математике, средой того или иного исполнителя могут быть числа разной природы - натуральные, действительные и т.п., буквы, буквенные выражения, уравнения, тождества и т.п.
Данное выше
определение
алгоритма
нельзя считать
строгим - не
вполне ясно,
что такое "точное
предписание"
или "последовательность
действий,
обеспечивающая
получение
требуемого
результата".
Поэтому обычно
формулируют
несколько общих
свойств алгоритмов,
позволяющих
отличать алгоритмы
от других
инструкций.
Такими свойствами являются:
Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
На основании этих свойств иногда дается определение алгоритма, например: “Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся детерменированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов.” Такая трактовка понятия “алгоритм” является неполной и неточной. Во-первых, неверно связывать алгоритм с решением какой-либо задачи. Алгоритм вообще может не решать никакой задачи. Во-вторых, понятие “массовость” относится не к алгоритмам как к таковым, а к математическим методам в целом. Решение поставленных практикой задач математическими методами основано на абстрагировании – мы выделяем ряд существенных признаков, характерных для некоторого круга явлений, и строим на основании этих признаков математическую модель, отбрасывая несущественные признаки каждого конкретного явления. В этом смысле любая математическая модель обладает свойством массовости. Если в рамках построенной модели мы решаем задачу и решение представляем в виде алгоритма, то решение будет “массовым” благодаря природе математических методов, а не благодаря “массовости” алгоритма.
Разъясняя понятие алгоритма, часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть дверь ключом, перейти улицу и т. д.. : рецепты приготовления какого-либо лекарства или кулинарные рецепты являются алгоритмами. Но для того, чтобы приготовить лекарство по рецепту, необходимо знать фармакологию, а для приготовления блюда по кулинарному рецепту нужно уметь варить. Между тем исполнение алгоритма – это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, то у нас просто не было бы такой специальности – повар.
Правила выполнения арифметических операций или геометрических построений представляют собой алгоритмы. При этом остается без ответа вопрос, чем же отличается понятие алгоритма от таких понятий, как “метод”, “способ”, “правило”. Можно даже встретить утверждение, что слова “алгоритм”, “способ”, “правило” выражают одно и то же (т.е. являются синонимами), хотя такое утверждение, очевидно, противоречит “свойствам алгоритма”.
Само выражение “свойства алгоритма” некорректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.
Первое правило – при построении алгоритма прежде всего необходимо задать мно-жество объектов, с которыми будет работать алгоритм. Формализованное (закодирован-ное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей рабо-ты выдает данные, которые называются выходными. Таким образом, алгоритм пре-образует входные данные в выходные.
Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит на-звание переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. счита-ется, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил. В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Итак, алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм каждому определенному набору входных данных ставит в соответствие некоторый набор выходных данных, т. е. вычисляет (реализует) функцию. При рассмотрении конкретных вопросов в теории алгоритмов всегда имеется в виду какая-то конкретная модель алгоритма.
Любая работа на компьютере – это есть обработка информации. Работу компьютера можно схематически изобразить следующим образом:
“Информация” слева и “информация” справа – это разные информации. Компьютер воспринимает информацию извне и в качестве результата своей работы выдает новую информацию. Информация, с которой работает компьютер, носит название “данные”.
Компьютер преобразует информацию по определенным правилам. Эти правила (операции, команды) заранее занесены в память компьютера. В совокупности эти правила преобразования информации называются алгоритмом. Данные, которые поступают в компьютер, называются входными данными. Результат работы компьютера – выходные данные. Таким образом, алгоритм преобразует входные данные в выходные:
Теперь можно поставить вопрос: а может ли человек обрабатывать информацию? Конечно, может. В качестве примера можно привести обычный школьный урок: учитель задает вопрос (входные данные), ученик отвечает (выходные данные). Самый простой пример: учитель дает задание – умножить 6 на 3 и результат написать на доске. Здесь числа 6 и 3 – входные данные, операция умножения – алгоритм, результат умножения – выходные данные:
Вывод: решение математических задач – частный случай преобразования информации. Компьютер (по-английски означает вычислитель, на русском языке – ЭВМ, электронная вычислительная машина) был создан как раз для выполнения математических расчетов.
Рассмотрим следующую задачу.
Длина класса 7 метров, ширина – 5 метров, высота – 3 метра. В классе 25 учеников. Сколько кв. м площади и сколько куб. м воздуха приходится на одного ученика?
Решение задачи:
1. Вычислить площадь класса:
2. Вычислить объем класса:
3. Вычислить, сколько квадратных метров площади приходится на одного ученика:
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика:
105: 25 = 4,2
Ответ:
на одного ученика
приходится
1,4 кв. метров
площади и 4,2 куб.
метров воздуха.
Если теперь убрать вычисления и оставить только “действия”, то получим алгоритм – перечень операций, которые необходимо выполнить, чтобы решить данную задачу.
Получается, что при решении любой математической задачи мы составляем алгоритм решения. Но прежде мы сами и выполняли этот алгоритм, то есть доводили решение до ответа. Теперь же мы будем только писать, что нужно сделать, но вычисления проводит не будем. Вычислять будет компьютер. Наш алгоритм будет представлять собой набор указаний (команд) компьютеру.
Когда мы вычисляем какую-либо величину, мы записываем результат на бумаге. Компьютер записывает результат своей работы в память в виде переменной. Поэтому каждая команда алгоритма должна включать указание, в какую переменную записывается результат. Алгоритм решения нашей задачи будет выглядеть так:
1. Вычислить площадь класса и записать в переменную S.
2. Вычислить объем класса и записать в переменную V.
3. Вычислить, сколько квадратных метров площади приходится на одного ученика и записать в переменную S1.
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика и записать в переменную V1.
5. Вывести на экран значения переменных S1 и V1.
Теперь остается только перевести команды алгоритма с русского языка на язык, понятный компьютеру, и получится программа. Программирование – это есть перевод алгоритма с “человеческого” языка на “компьютерный” язык.
Трактовка работы алгоритма как преобразования входных данных в выходные естественным образом подводит нас к рассмотрению понятия “постановка задачи”. Для того, чтобы составить алгоритм решения задачи, необходимо из условия выделить те величины, которые будут входными данными и четко сформулировать, какие именно величины требуется найти. Другими словами, условие задачи требуется сформулировать в виде “Дано... Требуется” – это и есть постановка задачи.
Алгоритм применительно к вычислительной машине – точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа.
Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
Механические алгоритмы , или иначе детерминированные, жесткие (например алгоритм работы машины, двигателя и т.п.);
Гибкие алгоритмы , например стохастические, т.е. вероятностные и эвристические.
Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.
Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоцияциях и прошлом опыте решения схожих задач.
Линейный алгоритм – набор команд (указаний), выполняемых последовательно во времени друг за другом.
Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
Циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов.
Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.
На рисунке продемонстрированы в условных обозначениях схемы основных конструкций алгоритмов:
а). линейного алгоритма;
б,в,г). разветвляющихся алгоритмов (б-ответвление, в-раздвоение, г-переключение);
д,е,ж). циклических алгоритмов (д,ж-проверка в начале цикла, е-проверка в конце цикла).
Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.
На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
Структурная (блок-, граф-) схема алгоритма – графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.
Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.
Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой схему – набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации “. Здесь форма представления алгоритма смешивается с самим алгоритмом.
Принцип программирования “сверху вниз” требует, чтобы блок-схема поэтапно конкретизировалась и каждый блок “расписывался” до элементарных операций. Но такой подход можно осуществить при решении несложных задач. При решении сколько-нибудь серьезной задачи блок-схема “расползется” до такой степени, что ее невозможно будет охватить одним взглядом.
Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна служить для упрощения изображения алгоритма, а не для усложнения.
При решении задач на компьютере необходимо не столько умение составлять алгоритмы, сколько знание методов решения задач (как и вообще в математике) . Поэтому изучать нужно не программирование как таковое (и не алгоритмизацию), а методы решения математических задач на компьютере. Задачи следует классифицировать не по типам данных, как это обычно делается (задачи на массивы, на символьные переменные и т. д.), а по разделу “Требуется”.
В информатике процесс решения задачи распределяется между двумя субъектами: программистом и компьютером. Программист составляет алгоритм (программу), компьютер его исполняет. В традиционной математике такого разделения нет, задачу решает один человек, который составляет алгоритм решения задачи и сам выполняет его. Сущность алгоритмизации не в том, что решение задачи представляется в виде набора элементарных операций, а в том, что процесс решения задачи разбивается на два этапа: творческий (программирование) и не творческий (выполнение программы). И выполняют эти этапы разные субъекты – программист и исполнитель
В учебниках по информатике обычно пишут, что исполнителем алгоритма может быть и человек. На самом деле алгоритмы для людей никто не составляет (не будем забывать, что не всякий набор дискретных операций является алгоритмом). Человек в принципе не может действовать по алгоритму. Выполнение алгоритма – это автоматическое, бездумное выполнение операций. Человек всегда действует осмысленно. Для того, чтобы человек мог выполнять какой-то набор операций, ему нужно объяснить, как это делается. Любую работу человек сможет выполнять только тогда, когда он понимает, как она выполняется.
Вот в этом – “ объяснение и понимание” – и кроется различие между понятиями “алгоритм” и “способ”, “метод”, “правило”. Правила выполнения арифметических операций – это именно правила (или способы), а не алгоритмы. Конечно, эти правила можно изложить в виде алгоритмов, но толку от этого не будет. Для того, чтобы человек смог считать по правилам арифметики, его нужно научить. А если есть процесс обучения, значит, мы имеем дело не с алгоритмом, а с методом.
При составлении алгоритма программист никому ничего не объясняет, а исполнитель не пытается ничего понять. Алгоритм размещается в памяти компьютера, который извлекает команды по одной и исполняет их. Человек действует по другому. Чтобы решить задачу, человеку требуется держать в памяти метод решения задачи в целом, а воплощает этот метод каждый по-своему.
Очень ярко эта особенность человеческой психологии – неалгоритмичность мышления – проявилась в методичесом пособии А. Г. Гейна и В. Ф. Шолоховича. В пособии излагаются решения задач из известного учебника. Решения задач должны быть представлены в виде алгоритмов. Однако авторы пособия понимают, что если просто написать алгоритм решения задачи, то разобраться в самом решении будет трудно. Поэтому они сначала приводят “нечеткое изложение алгоритма” (т. е. объясняют решение задачи), а затем пишут сам алгоритм.
Л И Т Е Р А Т У Р А
1. Нестеренко А. В. ЭВМ и профессия программиста.
М., Просвещение, 1990.
2. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию.
М., Наука, 1990.
3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера.
М., Энергоатомиздат, 1988.
4. Гейн А.Г. и др.. Основы информатики и вычислительной техники.
М., Просвещение, 1994.
5. Информатика. Еженедельное приложение к газете “Первое сентября”. 1998, № 1.
6. Радченко Н. П. Ответы на вопросы выпускных экзаменов. – Инфоматика и
образование, 1997, №4.
7. Касаткин В.Н. Информация, алгоритмы, ЭВМ. М., Просвещение, 1991.
8. Каныгин Ю. М., Зотов Б. И. Что такое информатика?
М., Детская литература, 1989.
9. Гейн А. Г., Шолохович В.Ф. Преподавание курса “Основы информатики и вычислительной техники” в средней школе. Руководство для учителя.
Екатеринбург, 1992.
10. Извозчиков В.А. Информатика в понятиях и терминах.
11. Газета «Информатика», №35, 1997г.
12. Л.З. Шауцуков Основы информатики в вопросах и ответах.
Автор: Богашова Татьяна, Донец Сергей (КПИ,ФАКС) г.Киев, 1999г.
Оценка:отл.
Сдавался: ПТУ №34
E-Mail:[email protected]
система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 89 вв. Аль-Хорезми (Хорезм историческая область на территории современного Узбекистана). Из математических работ Аль-Хорезми до нас дошли только две алгебраическая (от названия этой книги родилось слово алгебра) и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Например, в авторитетном словаре английского языка Webster"s New World Dictionary , изданном в 1957, слово алгоритм снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.
Слово «алгоритм» вновь стало употребительным с появлением электронных вычислительных машин для обозначения совокупности действий, составляющих некоторый процесс. Здесь подразумевается не только процесс решения некоторой математической задачи, но и кулинарный рецепт и инструкция по использованию стиральной машины, и многие другие последовательные правила, не имеющие отношения к математике, все эти правила являются алгоритмами. Слово «алгоритм» в наши дни известно каждому, оно настолько уверенно шагнуло в разговорную речь, что сейчас нередко на страницах газет, в выступлениях политиков встречаются выражения «алгоритм поведения», «алгоритм успеха» и т.д.
Тьюринг А. Может ли машина мыслить
? М., Мир, 1960
Успенский В. Машина Поста.
Наука, 1988
Кормен Т., Лейзерсон, Ривес Р. Алгоритмы. Построение и анализ
. М., МЦНМО, 1999
Найти "АЛГОРИТМ " на
Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм - это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм - это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм - точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм - строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
«Алгоритм - это последовательность действий, направленных на получение определённого результата за конечное число шагов».
«Алгоритм - однозначно, доступно и кратко (условные понятия - названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».
«Алгоритм - это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».
«Алгоритм - это некоторый конечный набор рассчитанных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».
«Алгоритм - это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».
«Алгоритм - это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач».
«Алгоритм - это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».
Свойства алгоритма
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
- Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
- Детерминированность - определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
- Понятность - алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
- Конечность - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
- Массовость - алгоритм должен быть применим к разным наборам исходных данных.
- Результативность - завершение алгоритма определёнными результатами.
- Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
- Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных
Виды алгоритмов
Основные виды алгоритмов:
1)Прикладные алгоритмы - предназначены для решения определённых прикладных задач.
Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат. Алгоритм (программа) содержит ошибки, если для некоторых исходных данных он даёт неправильные результаты, сбои, отказы или не даёт никаких результатов вообще.
2)Рекурсивные алгоритмы - алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения.
3)Начиная с конца XX - начала XXI века активно разрабатываются параллельные алгоритмы - предназначены для вычислительных машин, способных выполнять несколько операций одновременно.
Способы описания алгоритмов
Алгоритм может быть записан словами и изображён схематически. Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код). Например, для описания алгоритма применяются блок-схемы. Другим вариантом описания, не зависимым от языка программирования, является псевдокод.
Литература
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс», 2006. - С. 1296.
- Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. - 3-е изд. - М.: «Вильямс», 2006. - С. 720.
- Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. - М.: «Вильямс», 2007. - С. 480.
