Понятие алгоритма
Слово "Алгоритм"происходитот algorithmi - латинскогонаписания имениаль-Хорезми,под которымв средневековойЕвропе зналивеличайшегоматематикаиз Хорезма(город в современномУзбекистане)Мухаммеда бенМусу, жившегов 783-850 гг. В своейкниге "Об индийскомсчете" онсформулировалправила записинатуральныхчисел с помощьюарабских цифри правила действийнад ними столбиком.В дальнейшемалгоритмомстали называтьточное предписание,определяющеепоследовательностьдействий,обеспечивающуюполучениетребуемогорезультатаиз исходныхданных. Алгоритмможет бытьпредназначендля выполненияего человекомили автоматическимустройством.Создание алгоритма,пусть дажесамого простого,- процесс творческий.Он доступенисключительноживым существам,а долгое времясчиталось, чтотолько человеку.Другое дело- реализацияуже имеющегосяалгоритма. Ееможно поручитьсубъекту илиобъекту, которыйне обязан вникатьв существодела, а возможно,и не способенего понять.Такой субъектили объектпринято называтьформальнымисполнителем.Примеромформальногоисполнителяможет служитьстиральнаямашина-автомат,которая неукоснительноисполняетпредписанныеей действия,даже если вызабыли положитьв нее порошок.Человек тожеможет выступатьв роли формальногоисполнителя,но в первуюочередь формальнымиисполнителямиявляются различныеавтоматическиеустройства,и компьютерв том числе.Каждый алгоритмсоздается врасчете навполне конкретногоисполнителя.Те действия,которые можетсовершатьисполнитель,называютсяего его допустимымидействиями.Совокупностьдопустимыхдействий образуетсистему командисполнителя.Алгоритм долженсодержатьтолько те действия,которые допустимыдля данногоисполнителя.
Объекты, надкоторыми исполнительможет совершатьдействия, образуюттак называемуюсреду исполнителя.Для алгоритмов,встречающихсяв математике,средой тогоили иного исполнителямогут бытьчисла разнойприроды - натуральные,действительныеи т.п., буквы,буквенныевыражения,уравнения,тождества ит.п.
Данное вышеопределениеалгоритманельзя считатьстрогим - невполне ясно,что такое "точноепредписание"или "последовательностьдействий,обеспечивающаяполучениетребуемогорезультата".Поэтому обычноформулируютнесколько общихсвойств алгоритмов,позволяющихотличать алгоритмыот другихинструкций.
Такими свойствамиявляются:
Дискретность(прерывность,раздельность)- алгоритм долженпредставлятьпроцесс решениязадачи какпоследовательноевыполнениепростых (илиранее определенных)шагов. Каждоедействие,предусмотренноеалгоритмом,исполняетсятолько послетого, как закончилосьисполнениепредыдущего.
Определенность- каждое правилоалгоритмадолжно бытьчетким, однозначными не оставлятьместа для произвола.Благодаряэтому свойствувыполнениеалгоритманосит механическийхарактер и нетребует никакихдополнительныхуказаний илисведений орешаемой задаче.
Результативность(конечность)- алгоритм долженприводить крешению задачиза конечноечисло шагов.
Массовость- алгоритм решениязадачи разрабатываетсяв общем виде,то есть, он долженбыть применимдля некоторогокласса задач,различающихсятолько исходнымиданными. Приэтом исходныеданные могутвыбиратьсяиз некоторойобласти, котораяназываетсяобластьюприменимостиалгоритма.
На основанииэтих свойствиногда даетсяопределениеалгоритма,например: “Алгоритм– это последовательностьматематических,логическихили вместевзятых операций,отличающихсядетерменированностью,массовостью,направленностьюи приводящаяк решению всехзадач данногокласса за конечноечисло шагов.”Такая трактовкапонятия “алгоритм”является неполнойи неточной.Во-первых, неверносвязыватьалгоритм срешением какой-либозадачи. Алгоритмвообще можетне решать никакойзадачи. Во-вторых,понятие “массовость”относится нек алгоритмамкак к таковым,а к математическимметодам в целом.Решение поставленныхпрактикой задачматематическимиметодами основанона абстрагировании– мы выделяемряд существенныхпризнаков,характерныхдля некоторогокруга явлений,и строим наосновании этихпризнаковматематическуюмодель, отбрасываянесущественныепризнаки каждогоконкретногоявления. В этомсмысле любаяматематическаямодель обладаетсвойствоммассовости.Если в рамкахпостроенноймодели мы решаемзадачу и решениепредставляемв виде алгоритма,то решениебудет “массовым”благодаряприроде математическихметодов, а неблагодаря“массовости”алгоритма.
Разъясняяпонятие алгоритма,часто приводятпримеры “бытовыхалгоритмов”:вскипятитьводу, открытьдверь ключом,перейти улицуи т. д.. : рецептыприготовлениякакого-либолекарства иликулинарныерецепты являютсяалгоритмами.Но для того,чтобы приготовитьлекарство порецепту, необходимознать фармакологию,а для приготовленияблюда по кулинарномурецепту нужноуметь варить.Между тем исполнениеалгоритма –это бездумное,автоматическоевыполнениепредписаний,которое в принципене требуетникаких знаний.Если бы кулинарныерецепты представлялисобой алгоритмы,то у нас простоне было бы такойспециальности– повар.
Правилавыполненияарифметическихопераций илигеометрическихпостроенийпредставляютсобой алгоритмы.При этом остаетсябез ответавопрос, чем жеотличаетсяпонятие алгоритмаот таких понятий,как “метод”,“способ”, “правило”.Можно дажевстретитьутверждение,что слова “алгоритм”,“способ”, “правило”выражают однои то же ( т.е. являютсясинонимами), хотя такоеутверждение,очевидно,противоречит“свойствамалгоритма”.
Само выражение“свойстваалгоритма”некорректно.Свойствамиобладают объективносуществующиереальности.Можно говорить,например, освойствахкакого-либовещества. Алгоритм– искусственнаяконструкция,которую мысооружаем длядостижениясвоих целей.Чтобы алгоритмвыполнил своепредназначение,его необходимостроить поопределеннымправилам. Поэтомунужно говоритьне о свойствахалгоритма, ао правилахпостроенияалгоритма, илио требованиях,предъявляемыхк алгоритму.
Первое правило– при построенииалгоритмапрежде всегонеобходимозадать мно-жествообъектов, скоторыми будетработать алгоритм.Формализованное( закодирован-ное) представлениеэтих объектовносит названиеданных. Алгоритмприступаетк работе с некоторымнабором данных,которые называютсявходными, и врезультатесвоей рабо-тывыдает данные,которые называютсявыходными.Таким образом,алгоритм пре-образуетвходные данныев выходные.
Это правилопозволяет сразуотделить алгоритмыот “методов”и “способов”.Пока мы не имеемформализованныхвходных данных,мы не можемпостроитьалгоритм.
Второе правило– для работыалгоритматребуетсяпамять. В памятиразмещаютсявходные данные,с которымиалгоритм начинаетработать,промежуточныеданные и выходныеданные, которыеявляются результатомработы алгоритма.Память являетсядискретной,т.е. состоящейиз отдельныхячеек. Поименованнаяячейка памятиносит на-званиепеременной.В теории алгоритмовразмеры памятине ограничиваются,т. е. счита-ется,что мы можемпредоставитьалгоритму любойнеобходимыйдля работыобъем памяти.
В школьной“теории алгоритмов”эти два правилане рассматриваются.В то же времяпрактическаяработа с алгоритмами( программирование) начинаетсяименно с реализацииэтих правил.В языках программированияраспределениепамяти осуществляетсядекларативнымиоператорами( операторамиописания переменных). В языке Бейсикне все переменныеописываются,обычно описываютсятолько массивы.Но все равнопри запускепрограммытрансляторязыка анализируетвсе идентификаторыв тексте программыи отводит памятьпод соответствующиепеременные.
Третье правило– дискретность.Алгоритм строитсяиз отдельныхшагов (действий,операций, команд).Множествошагов, из которыхсоставленалгоритм, конечно.
Четвертоеправило –детерменированность.После каждогошага необходимоуказывать,какой шаг выполняетсяследующим, либодавать командуостановки.
Пятое правило– сходимость( результативность). Алгоритм должензавершатьработу послеконечного числашагов. При этомнеобходимоуказать, чтосчитать результатомработы алгоритма.
Итак,алгоритм –неопределяемоепонятие теорииалгоритмов.Алгоритм каждомуопределенномунабору входныхданных ставитв соответствиенекоторый наборвыходных данных,т. е. вычисляет( реализует )функцию. Прирассмотренииконкретныхвопросов втеории алгоритмоввсегда имеетсяв виду какая-токонкретнаямодель алгоритма.
Любая работана компьютере– это есть обработкаинформации.Работу компьютераможно схематическиизобразитьследующимобразом:
“Информация”слева и “информация”справа – эторазные информации.Компьютервоспринимаетинформациюизвне и в качестверезультатасвоей работывыдает новуюинформацию.Информация,с которой работаеткомпьютер,носит название“данные”.
Компьютерпреобразуетинформациюпо определеннымправилам. Этиправила (операции,команды ) заранеезанесены впамять компьютера.В совокупностиэти правилапреобразованияинформацииназываютсяалгоритмом.Данные, которыепоступают вкомпьютер,называютсявходными данными.Результатработы компьютера– выходныеданные. Такимобразом, алгоритмпреобразуетвходные данныев выходные:
Теперь можнопоставитьвопрос: а можетли человекобрабатыватьинформацию? Конечно, может.В качествепримера можнопривести обычныйшкольный урок:учитель задаетвопрос ( входныеданные ), ученикотвечает ( выходныеданные ). Самыйпростой пример:учитель даетзадание – умножить6 на 3 и результатнаписать надоске. Здесьчисла 6 и 3 – входныеданные, операцияумножения –алгоритм, результатумножения –выходные данные:
Вывод : решениематематическихзадач – частныйслучай преобразованияинформации.Компьютер (по-английскиозначает вычислитель,на русскомязыке – ЭВМ,электроннаявычислительнаямашина ) былсоздан как раздля выполненияматематическихрасчетов.
Рассмотримследующуюзадачу.
Длина класса7 метров, ширина– 5 метров, высота– 3 метра. В классе25 учеников. Сколькокв. м площадии сколько куб.м воздуха приходитсяна одного ученика?
Решениезадачи:
1. Вычислитьплощадь класса:
7 х 5 = 35
2. Вычислитьобъем класса:
35 х 3 = 105
3. Вычислить,сколько квадратныхметров площадиприходитсяна одного ученика:
35 : 25 = 1,4
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 :vladimir@mail.kar.net
