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

По­ня­тие "ал­го­ритм" от­но­си­т­ся к чис­лу наи­бо­лее фун­да­мен­та­ль­ных по­ня­тий ма­те­ма­ти­ки. Бо­лее то­го, са­мо от­кры­тие об­ще­го по­ня­тия "ал­го­ритм" в ка­че­ст­ве но­вой и от­де­ль­ной сущ­но­сти мож­но счи­тать важ­ным от­кры­ти­ем, ко­то­рое при­ве­ло к со­зда­нию са­мой те­ории ал­го­рит­мов. Это по­ня­тие сло­жи­лось по­сте­пен­но. В ка­че­ст­ве пе­ре­чис­ле­ния кон­крет­ных дат и имен, при­ве­дём здесь лишь сле­ду­ющую ци­та­ту [Успен­ский,Семёнов,1987,с.30]: "... ед­ва ли не са­мые ран­ние при­ме­ры ис­по­ль­зо­ва­ния та­ко­го по­ня­тия встре­ча­ют­ся в пер­вой чет­вер­ти XX ве­ка, в ра­бо­тах Бо­ре­ля (1912) и Вей­ля (1921)".

По­ня­тие "ал­го­ритм" (по­до­бно по­ня­тию "мно­же­ст­во") не вы­ра­жа­ют че­рез дру­гие ма­те­ма­ти­че­с­кие по­ня­тия, а по­то­му не да­ют ему опре­де­ле­ния. Мы го­во­рим об ин­ту­итив­ном по­ня­тии "ал­го­ритм", так же как об ин­ту­итив­ном по­ня­тии "мно­же­ст­во", лишь по­яс­няя его. По­ня­тие "ал­го­ритм" - од­но из ис­хо­дных по­ня­тий те­ории ал­го­рит­мов и при по­стро­ении те­ории счи­та­ет­ся уже из­ве­ст­ным с са­мо­го на­ча­ла.

Пер­во­на­ча­ль­но по­яс­нить по­ня­тие "ал­го­ритм" мож­но сло­вом "пред­пи­са­ние". Под­хо­дя­щи­ми для это­го слу­чая яв­ля­ет­ся так­же сло­ва "ре­цепт" и "про­грам­ма". Од­на­ко вся­кое ли пред­пи­са­ние (про­грам­ма, ре­цепт) мы склон­ны счи­тать ал­го­рит­мом? Как, на­при­мер быть с пред­пи­са­ни­ем ти­па "пой­ди ту­да, не знаю ку­да, при­не­си то, не знаю что"? Раз­ве это - ал­го­ритм? Тре­бу­ют­ся бо­лее под­роб­ные по­яс­не­ния для то­го, что­бы по­лу­чить бо­лее точ­ное пред­став­ле­ние о том, что та­кое ал­го­ритм. При­ве­дём ряд та­ких по­яс­не­ний, сде­лан­ных раз­лич­ны­ми ав­то­ра­ми. Рас­по­ло­жен­ные в по­ряд­ке воз­рас­та­ния их под­роб­но­сти, они под­чер­ки­ва­ют те или иные сто­ро­ны это­го по­ня­тия. Пред­ла­га­ем чи­та­те­лю срав­нить эти по­яс­не­ния.

(1) [Мар­ков,Нагорный,1996,с.109] Ал­го­рифм есть об­ще­по­нят­ное пред­пи­са­ние, одно­знач­но опре­де­ля­ющее ход не­ко­то­рых кон­стру­к­тив­ных про­цес­сов.

(2) [Ма­тю­ш­ков,Лихтарович,1988] Ал­го­рит­мом на­зы­ва­ет­ся пред­пи­са­ние, опре­де­ля­ющее по­ря­док вы­пол­не­ния опе­ра­ций над дан­ны­ми с це­лью по­лу­че­ния ис­ко­мо­го ре­зу­ль­та­та.

(3) [Успен­ский,1977,с.202] Ал­го­ритм, ал­го­рифм - это точ­ное пред­пи­са­ние, ко­то­рое за­да­ет вы­чис­ли­те­ль­ный про­цесс (на­зы­ва­емый в этом слу­чае ал­го­рит­ми­че­с­ким про­цес­сом), на­чи­на­ющий­ся с про­из­во­ль­но­го ис­хо­дно­го дан­но­го (из не­ко­то­рой со­во­куп­но­сти воз­мож­ных для дан­но­го ал­го­рит­ма ис­хо­дных дан­ных) и на­прав­лен­ный на по­лу­че­ние пол­нос­тью опре­де­ля­емо­го этим ис­хо­дным дан­ным ре­зу­ль­та­та.

(4) [Эб­бин­ха­уз,Якобс,Ман,Хермес,1972,с.9] Под ал­го­рит­мом для не­ко­то­ро­го клас­са за­дач ма­те­ма­тик по­ни­ма­ет не­ко­то­рое об­щее пра­ви­ло, с по­мо­щью ко­то­ро­го ре­ше­ние лю­бой ука­зан­ной про­бле­мы это­го клас­са мо­жет быть най­де­но чис­то ме­ха­ни­че­с­ки и "без вся­кой изоб­ре­та­те­ль­но­сти", ес­ли, ко­неч­но, это ре­ше­ние су­ще­ст­ву­ет.

(5) [Ки­та­ев,Шень,Вялый,1999,с.16] Ал­го­ритм - это одно­знач­но опре­де­лён­ная со­во­куп­ность ин­стру­к­ций по пре­об­ра­зо­ва­нию ис­хо­дных дан­ных в ре­зу­ль­тат, при­чём все ин­стру­к­ции эле­мен­тар­ны, т.е. при их вы­пол­не­нии "нам при­дёт­ся то­ль­ко ме­ха­ни­че­с­ки сле­до­вать пред­пи­са­ни­ям, как ес­ли бы мы бы­ли ро­бо­та­ми: от нас не по­тре­бу­ет­ся ни по­ни­ма­ния, ни ис­кус­ст­ва, ни изоб­ре­та­те­ль­но­сти" (к по­след­ним сло­вам в ка­вы­ч­ках ци­ти­ру­емые ав­то­ры при­во­дят ссыл­ку [Кли­ни,1973,с.270]).

(6) [Ба­бен­ко,1986,с.25-26] Ал­го­рит­мом в ал­фа­ви­те A на­зы­ва­ет­ся точ­ное об­ще­по­нят­ное пред­пи­са­ние P, опре­де­ля­ющее по­тен­ци­аль­но осу­ще­ст­ви­мый про­цесс по­сле­до­ва­те­ль­но­го пре­об­ра­зо­ва­ния слов в A. Пред­пи­са­ние P до­лжно удо­влет­во­рять сле­ду­ющим усло­ви­ям: (а) оно до­лжно быть ко­неч­ным и со­став­лен­ным так, что­бы его вы­пол­не­ние не тре­бо­ва­ло ни­ка­кой до­пол­ни­те­ль­ной ин­фор­ма­ции, по­ми­мо со­дер­жа­щей­ся в са­мом P и в ис­хо­дном сло­ве, к ко­то­ро­му ал­го­ритм при­ме­ня­ет­ся; (б)предписание P до­лжно быть та­ко­вым, что­бы его ис­пол­не­ние бы­ло одно­знач­ным во всех де­та­лях; (в) при ис­пол­не­нии пред­пи­са­ния P до­лжно вы­пол­ня­ть­ся ус­ло­вие вос­про­из­во­ди­мо­сти, т.е. при­ме­не­ние ал­го­рит­ма к од­но­му и то­му же вход­но­му сло­ву до­лжно при­во­дить каж­дый раз к од­но­му и то­му же ре­зу­ль­та­ту (ли­бо не при­во­дить ни к ка­ко­му ре­зу­ль­та­ту); (г)процесс при­ме­не­ния ал­го­рит­ма при ре­ше­нии за­да­чи мо­жет быть сколь угод­но длин­ным, но он до­лжен быть ко­неч­ным. Прак­ти­че­с­ки ал­го­ритм мо­жет ока­за­ть­ся при из­ве­ст­ных усло­ви­ях не­осу­ще­ст­ви­мым. Од­на­ко он до­лжен быть по­тен­ци­аль­но осу­ще­ст­ви­мым, т.е. до­лжен при­во­дить к ис­ко­мо­му ре­зу­ль­та­ту че­рез ко­неч­ное чис­ло ша­гов.

(7) [Ер­шов,Палютин,1987,с.241] Под ал­го­рит­мом, дей­ст­ву­ющим на не­ко­то­ром мно­же­ст­ве объ­е­к­тов X бу­дем по­ни­мать точ­ное пред­пи­са­ние, опре­де­ля­ющее по лю­бо­му объ­е­к­ту aÎX не­ко­то­рую впол­не опре­де­лён­ную по­сле­до­ва­те­ль­ность про­стей­ших дей­ст­вий, осу­ще­с­тв­ляя ко­то­рые, мы ли­бо ни­ког­да не за­кон­чим этот про­цесс (вы­чис­ле­ния), ли­бо этот про­цесс за­кан­чи­ва­ет­ся и мы по­лу­ча­ем объ­ект A(a), на­зы­ва­емый зна­че­ни­ем A на a, ли­бо про­цесс об­ры­ва­ет­ся без по­лу­че­ния зна­че­ния. Ес­ли про­цесс, опре­де­ля­емый ал­го­рит­мом A по эле­мен­ту a, не за­кан­чи­ва­ет­ся или об­ры­ва­ет­ся без по­лу­че­ния зна­че­ния, то го­во­рят, что A не при­ме­ним к a.

Ко­ли­че­ст­во про­стей­ших дей­ст­вий, не­об­хо­ди­мых для по­лу­че­ния зна­че­ния ал­го­рит­ма, мо­жет быть ве­сь­ма бо­ль­шим. Од­на­ко мы от­вле­ка­ем­ся (аб­стра­ги­ру­ем­ся) на дан­ном уров­не изу­че­ния от ре­аль­ных воз­мож­но­стей осу­ще­с­тв­ле­ния ал­го­рит­мов и бу­дем ис­хо­дить из пред­по­ло­же­ния, что при осу­ще­с­тв­ле­нии про­цес­са вы­чис­ле­ния, опре­де­лён­но­го ал­го­рит­мом, мы име­ем не­огра­ни­чен­ный за­пас вре­ме­ни и ма­те­ри­алов. Та­кое пред­по­ло­же­ние но­сит на­зва­ние при­нци­па по­тен­ци­аль­ной осу­ще­ст­ви­мо­сти.

(8) [Ве­ре­ща­гин,Шень,1999,с.9] Не­ско­ль­ко де­ся­ти­ле­тий на­зад по­ня­тие "ал­го­ритм" тре­бо­ва­ло спе­ци­аль­но­го разъ­яс­не­ния. Сей­час ("ком­пь­ю­тер­ная гра­мо­тность"?) та­кие объ­яс­не­ния всё рав­но ни­кто чи­тать не бу­дет, по­ско­ль­ку и так яс­но, что та­кое ал­го­ритм. Но всё же на­до со­блю­дать осто­ро­жность, что­бы не при­нять за ал­го­ритм то, что им не яв­ля­ет­ся.

Основные понятия теории алгоритмов - часть первая

09-04-2009

Алгоритмом часто называют конечную совокупность инструкций для решения некоторого класса задач. Это определение неформально, так как с его помощью нельзя однозначно ответить на вопросы, что такое совокупность инструкций и некоторый класс задач... подробнее Комментарии: 0 Кол. просмотров: общее - 3039 сегодня - 2

Основные понятия теории алгоритмов - часть вторая

09-04-2009

В современной математике алгоритмами принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах. Это определение, в свою очередь, использует два понятия – понятие абстрактного алфавита и слов в таком алфавите... подробнее Комментарии: 0 Кол. просмотров: общее - 2630 сегодня - 0

Основные понятия теории алгоритмов - часть третья

09-04-2009

К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В... подробнее Комментарии: 0 Кол. просмотров: общее - 2176 сегодня - 1

Основные понятия теории алгоритмов - часть четвертая

09-04-2009

Понятие алфавитного оператора является чрезвычайно общим. К нему фактически сводятся или могут быть сведены любые процессы преобразования информации, поскольку символам алфавита можно поставить в соответствие объекты произвольной природы... подробнее Комментарии: 0 Кол. просмотров: общее - 2391 сегодня - 0

Оценка сложности алгоритмов

09-04-2009

С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов... подробнее Комментарии: 0 Кол. просмотров: общее - 2289 сегодня - 2