Алгарытм

Сучаснае фармальнае азначэнне алгарытму было дадзена ў 30-50-х гадах ХХ стагоддзя ў працах Цьюрынга, Поста^[ru], Чорча (тэзіс Чорча — Цьюрынга), Н. Вінера, А. Маркава^[ru].

Само слова алгарытм паходзіць ад імя персідскага вучонага Абу Абдулах Мухамеда ібн Муса аль-Харэзмі (алгарытм — аль-Харэзмі). Каля 825 года ён напісаў сачыненне, у якім упершыню даў апісанне прыдуманай у Індыі пазіцыйнай дзесятковай сістэмы лічэння. На жаль, персідскі арыгінал кнігі не захаваўся. Аль-Харэзмі сфармуляваў правілы вылічэння ў новай сістэме і, верагодна, упершыню выкарыстаў лічбу 0 для абазначэння прапушчанай пазіцыі ў запісе ліку (яе індыйскую назву арабы пераклалі як as-sifr альбо проста sifr, адсюль такія словы, як «цыфра» і «шыфр»). Прыблізна ў гэты ж час індыйскія лічбы пачалі ўжываць і іншыя арабскія навукоўцы. У першай палове XII стагоддзя кніга аль-Харэзмі ў лацінскім перакладзе трапіла ў Еўропу. Перакладчык, імя якога да нас не дайшло, даў ёй назву Algoritmi de numero Indorum («Алгарытмы пра лічэнне індыйскае»). Па-арабску ж кніга называлася Кітаб аль-джэбр валь-мукабала («Кніга пра складанне і адыманне»). З арыгінальнай назвы кнігі паходзіць слова Алгебра (алгебра — аль-джэбр — складанне).

Такім чынам, мы бачым, што лацінізаванае імя сярэднеазіяцкага вучонага было вынесена ў загаловак кнігі, і сёння ні ў каго няма сумненняў, што слова «алгарытм» трапіла ў еўрапейскія мовы менавіта дзякуючы гэтаму сачыненню. Аднак пытанне пра яго сэнс доўгі час выклікала зацятыя спрэчкі. На працягу многіх стагоддзяў паходжанню слова даваліся самыя розныя тлумачэнні.

Адны выводзілі algorism з грэчаскіх algiros (хворы) і arithmos (лік). З-за такога тлумачэння не вельмі зразумела, чаму лікі менавіта «хворыя». Ці лінгвістам хворымі здаваліся людзі, якія маюць няшчасце займацца вылічэннямі? Сваё тлумачэнне прапанаваў і энцыклапедычны слоўнік Бракгаўза і Эфрона. У ім алгарыфм (дарэчы, да рэвалюцыі ў Расійская імперыі выкарыстоўвалася напісанне алг��риθм, праз фіту) выводзіцца «ад арабскага слова Аль-Гарэтм, што значыць корань». Зразумела, гэтыя тлумачэнні наўрад ці можна лічыць пераканаўчымі.

Згаданы вышэй пераклад сачынення аль-Харэзмі стаў першай ластаўкай, і на працягу некалькіх наступных стагоддзяў з'явілася мноства іншых прац, прысвечаных усё таму ж пытанню — навучанню мастацтву лічэння з дапамогай лічбаў. І ўсе яны ў назве мелі слова algoritmi ці algorismi.

Пра аль-Харэзмі пазнейшыя аўтары нічога не ведалі, але паколькі першы пераклад кнігі пачынаецца словамі: «Dixit algorizmi: …» («Аль-Харэзмі казаў: …»), усё яшчэ звязвалі гэтае слова з імем канкрэтнага чалавека. Вельмі распаўсюджанай была версія пра грэчаскае паходжанне кнігі. У англа-нарманскім рукапісе XIII стагоддзя, напісаным у вершах, чытаем:

"Алгарызм быў прыдуманы ў Грэцыі.

Гэта частка арыфметыцы. Прыдуманы ён быў майстрам па імi Алгарызм, які даў яму сваё імя. І паколькі яго звалі Алгарызм,

Ён назваў сваю кнігу «Алгарызм»

Каля 1250 года англійскі астраном і матэматык Іаханус Сакрабоска напісаў працу па арыфметыцы Algorismus vulgaris, што на стагоддзі стала асноўным падручнікам па вылічэннях у дзесятковай пазіцыйнай сістэме злічэння ў многіх еўрапейскіх універсітэтах. Ва ўводзінах Сакрабоска назваў аўтарам навукі пра лічэнне мудраца па імi Алгус (Algus). А ў папулярнай сярэдневяковай паэме «Раман пра Ружу» (1275—1280) Жана дэ Мена «грэчаскі філосаф Алгус» ставіцца ў адзін рад з Платонам, Арыстоцелем, Эўклідам і Пталамеем! Сустракаўся таксама варыянт напісання імя Аргус (Argus). І хоць, паводле старажытнагрэчаскай міфалогіі, карабель «Арго» быў пабудаваны Ясонам, менавіта гэтаму Арго прыпісвалася будаўніцтва карабля.

«Майстар Алгус» (ці Аргус) стаў у сярэдневяковай літаратуры ўвасабленнем мастацтва лічэння. І ва ўжо згаданым «Рамане пра ружу», і ў вядомай італьянскай паэме «Кветка», напісанай Дурантэ, ёсць фрагменты, у якіх гаворыцца, што нават «mestre Argus» не здолее падлічыць, колькі разоў сварацца і мірацца закаханыя. Англійскі паэт Джэфры Чосер у паэме «Кніга герцагіні» (1369 г.) піша, што нават «знаны лічыльнік Аргус» (noble countour Argu) не зможа палічыць пачвар, якія з'явіліся ў жахлівых відзежах герою.

Зрэшты, грэчаская версія была не адзінай. Міфічны Алгор (Algor) называўся то каралём Кастыліі (Rex quodam Castelliae), то індыйскім каралём, то арабскім мудрацом (philosophus Algus nomine Arabicus).

Аднак з часам такія тлумачэнні ўсё менш цікавілі матэматыкаў, і слова algorism (ці algorismus), якое нязменна прысутнічала ў назвах матэматычных сачыненняў, набыло значэнне спосабу выканання арыфметычных дзеянняў з дапамогай арабскіх лічбаў, гэта значыць на паперы, без выкарыстання абака. Менавіта ў такім значэнні яно ўвайшло ў многія еўрапейскія мовы. Напрыклад, з пазнакай «састарэлае» яно прысутнічае ў прадстаўнічым слоўніку англійскай мовы Webster's New World Dictionary, выдадзеным у 1957 годзе.

Алгарытм — гэта мастацтва лічэння з дапамогай лічбаў, але спачатку слова «лічба» адносілася толькі да нуля. Знакаміты французскі трувер Гацье дэ Куансі (Gautier de Coincy, 1177—1236) у адным з вершаў выкарыстоўваў слова algorismus-cipher (якія азначалі лічбу 0) як метафару для характарыстыкі абсалютна нікчэмнага чалавека. Відавочна, разуменне такога вобразу патрабавала адпаведнай падрыхтоўкі слухачоў, а гэта азначае, што новая сістэма лічэння ўжо была ім досыць добра вядомая.

Многія стагоддзі абак быў фактычна адзіным сродкам для практычных вылічэнняў, ім карысталіся і купцы, і мянялы, і навукоўцы. Добрыя якасці вылічэнняў на дошцы тлумачыў у сваіх сачыненнях такі выдатны мысліцель, як Герберт Аўрылакскі (938—1003), які стаў у 999 годзе Папам Рымскім пад імем Сільвестра II. Новае з вялікай цяжкасцю прабівала сабе дарогу, і ў гісторыю матэматыкі ўвайшло зацятае супрацьстаянне лагераў алгарысмікаў і абацыстаў (часам званых гербекістамі), якія прапагандавалі выкарыстанне для вылічэнняў абака замест арабскіх лічбаў. Цікава, што вядомы французскі матэматык Нікаля Шюке (Nicolas Chuquet, 1445—1488) у рэестр падаткаплацельшчыкаў горада Ліёна быў упісаны як алгарысмік (algoriste). Але прайшло не адно стагоддзе, перш чым новы спосаб лічэння канчаткова зацвердзіўся, столькі часу спатрэбілася, каб выпрацаваць агульнапрызнаныя азначэнні, удасканаліць і прыстасаваць да запісу на паперы метады вылічэнняў. У Заходняй Еўропе настаўнікаў арыфметыкі ажно да XVII стагоддзя працягвалі зваць «магістрамі абака», як, напрыклад, матэматыка Нікола Тарталью (1500—1557).

Паступова значэнне слова пашыралася. Навукоўцы пачыналі ўжываць яго не толькі да выключна вылічальных, але і да іншых матэматычных працэдур. Напрыклад, каля 1360 года французскі філосаф Мікалай Арэм (Nicolaus Oresme, 1323/25-1382) напісаў матэматычны трактат Algorismus proportionum («Вылічэнне прапорцый»), у якім упершыню выкарыстоўваў ступені з дробнымі паказчыкамі і фактычна ўшчыльную падышоў да ідэі лагарыфмаў. Калі ж на змену абаку прыйшло так званае лічэнне на лініях, шматлікія дапаможнікі па ім сталі называць Algorithmus linealis.

Можна звярнуць увагу на тое, што першапачатковая форма algorismi праз нейкі час страціла апошнюю літару, і слова набыло зручнейшы для еўрапейскага вымаўлення выгляд algorism. Пазней і яно, у сваю чаргу, зазанала скажэнне, хутчэй за ўсё, звязанае са словам arithmetic.

Алгарытмы станавіліся прадметам усё больш пільнай увагі вучоных, і паступова гэта паняцце заняло адно з цэнтральных месцаў у сучаснай матэматыцы. Што ж тычыцца людзей, ад матэматыкі далёкіх, то да пачатку саракавых гадоў гэта слова яны маглі пачуць хіба што ў час вучобы ў школе, у спалучэнні «алгарытм Еўкліда». Нягледзячы на гэта, алгарытм усё яшчэ ўспрымаўся як тэрмін выключна спецыяльны.

Адначасова з развіццём паняцця алгарытму паступова адбывалася і яго экспансія з чыстай матэматыкі ў іншыя сферы. І пачатак ёй паклала з'яўленне камп’ютараў, дзякуючы якому слова «алгарытм» увайшло ў 1985 годзе ва ўсе школьныя падручнікі інфарматыкі і набыло новае жыццё. Наогул можна сказаць, што яго сённяшняя вядомасць напрамую звязана са ступенню распаўсюджання камп’ютараў.

Адзінага «сапраўднага» азначэння паняцця «алгарытм» няма. «Алгарытм — гэта пэўны набор правіл, які вызначае паслядоўнасць аперацый для вырашэння канкрэтнага мноства задач і валодае пяццю важнымі рысамі: канечнасць, вызначанасць, увод, вывад, эфектыўнасць». (Д. Э. Кнут)

«Алгарытм — гэта ўсякая сістэма вылічэнняў, што выконваюцца па строга вызначаных правілах, якая пасля якой-небудзь колькасці крокаў заведама прыводзіць да вырашэння пастаўленай задачы». (А. Калмагораў)

«Алгарытм — гэта дакладнае прадпісанне, якое вызначае вылічальны працэс, які ідзе ад зыходных дадзеных, якія могуць вар'іравацца, да шуканага выніку». (А. Маркаў)

«Алгарытм — дакладнае прадпісанне аб выкананні ў вызначаным парадку нейкай сістэмы аперацый, якія вядуць да рашэння ўсіх задач дадзенага тыпу». (Філасофскі слоўнік / Пад рэд. М. М. Разенталя)

«Алгарытм — строга дэтэрмінаваная паслядоўнасць дзеянняў, якая апісвае працэс пераўтварэння аб'екта з пачатковага стану ў канчатковы, запісаны з дапамогай зразумелых выканаўцу каманд». (М. Д. Угрыновіч, падручнік «Інфарматыка і інфарм. Тэхналогіі»)

Розныя азначэнні алгарытму ў яўнай або няяўнай форме ўтрымліваюць наступны шэраг агульных патрабаванняў:

• Дыскрэтнасць — алгарытм павінен прадстаўляць працэс рашэння задачы як паслядоўнае выкананне нейкіх простых крокаў. Пры гэтым для выканання кожнага кроку алгарытму патрабуецца канечны адрэзак часу, гэта значыць пераўтварэнне зыходных дадзеных у вынік ажыццяўляецца ў часе дыскрэтна.
• Дэтэрмінаванасць (вызначанасць). У кожны момант часу наступны крок працы адназначна вызначаецца станам сістэмы. Такім чынам, алгарытм выдае адзін і той жа вынік (адказ) для адных і тых жа зыходных дадзеных. У сучаснай трактоўцы ў розных рэалізацый аднаго і таго ж алгарытму павінен быць ізаморфны граф. З іншага боку, існуюць імавернасныя алгарытмы, у якіх наступны крок работы залежыць ад бягучага стану сістэмы і генераванага выпадковага ліку. Аднак пры ўключэнні метаду генерацыі выпадковых лікаў у спіс «зыходных дадзеных», імавернасны алгарытм становіцца падвідам звычайнага.
• Зразумеласць — алгарытм для выканаўца павінен уключаць толькі тыя каманды, якія яму (выканаўцу) даступныя, якія ўваходзяць у яго сістэму каманд.
• Завяршальнасць (канечнасць) — пры карэктна зададзеных зыходных дадзеных алгарытм павінен завяршаць працу і выдаваць вынік за канечную колькасць крокаў. З іншага боку, імавернасны алгарытм можа і ніколі не выдаць вынік, але імавернасць гэтага роўная 0.
• Масавасць (універсальнасць). Алгарытм павінен выкарыстоўвацца і ў дачыненні да розных набораў зыходных дадзеных.
• Выніковасць — завяршэнне алгарытму пэўнымі вынікамі.
• Алгарытм змяшчае памылкі, калі прыводзіць да атрымання няправільных вынікаў або не дае вынікаў зусім.
• Алгарытм не змяшчае памылак, калі ён дае правільныя вынікі для любых дапушчальных зыходных дадзеных.

Асаблівую ролю выконваюць прыкладныя алгарытмы, прызначаныя для рашэння пэўных прыкладных задач. Алгарытм лічыцца правільным, калі ён адпавядае патрабаванням задачы (напрыклад, дае фізічна праўдападобны вынік). Алгарытм (праграма) змяшчае памылкі, калі для некаторых зыходных дадзеных ён дае няправільныя вынікі, збоі, адмовы ці не дае ніякіх вынікаў наогул. Апошні тэзіс выкарыстоўваецца ў алімпіядах па алгарытмічным праграмаванні, каб ацаніць складзеныя ўдзельнікамі праграмы.

Важную ролю граюць рэкурсіўныя алгарытмы (алгарытмы, якія выклікаюць самі сябе да таго часу, пакуль не будзе дасягнута нейкая ўмова вяртання). Пачынаючы з канца XX — пачатку XXI стагоддзя актыўна распрацоўваюцца паралельныя алгарытмы, прызначаныя для вылічальных машын, здольных выконваць некалькі аперацый адначасова.

Алгарытм — гэта дакладна вызначаная інструкцыя, паслядоўна ўжываючы якую да зыходных дадзеных, можна атрымаць рашэнне задачы. Для кожнага алгарытму ёсць нейкае мноства аб’ектаў, дапушчальных у якасці зыходных дадзеных. Напрыклад, у алгарытме дзялення рэчаісных лікаў дзялімае можа быць любым, а дзельнік не можа быць роўны нулю.

Алгарытм служыць, як правіла, для рашэння не адной канкрэтнай задачы, а нейкага класа задач. Так, алгарытм складання выкарыстоўваецца ў дачыненні да любой пары натуральных лікаў. У гэтым выяўляецца яго ўласцівасць масавасці, гэта значыць магчымасці выкарыстоўваць многаразова адзін і той жа алгарытм для любой задачы аднаго класу.

Для распрацоўкі алгарытмаў і праграм выкарыстоўваецца алгарытмізацыя — працэс сістэматычнага складання алгарытмаў для вырашэння пастаўленых прыкладных задач. Алгарытмізацыя лічыцца абавязковым этапам у працэсе распрацоўкі праграм і рашэнні задач на ЭВМ. Менавіта для прыкладных алгарытмаў і праграм прынцыпова важныя дэтэрмінаванасць, выніковасць і масавасць, а таксама правільнасць вынікаў рашэння пастаўленых задач.

Алгарытм — гэта зразумелае і дакладнае прадпісанне, выканаць паслядоўнасць дзеянняў, накіраваных на дасягненне мэт.

Алгарытм можа быць запісаны словамі і паказаны схематычна. Звычайна спачатку (на ўзроўні ідэі) алгарытм апісваецца словамі, але па меры набліжэння да рэалізацыі ён набывае ўсё больш фармальныя абрысы і фармулёўку на мове, зразумелай выканаўцу (напрыклад, машынны код). Напрыклад, для апісання алгарытму выкарыстоўваюцца блок-схемы. Іншым варыянтам апісання, незалежным ад мовы праграмавання, з'яўляецца псеўдакод.

Хоць у азначэнні алгарытму патрэбна толькі канечнасць колькасці крокаў, неабходных для дасягнення выніку, на практыцы выкананне нават хаця б мільярда крокаў занадта павольнае. Таксама звычайна ёсць іншыя абмежаванні (на памер праграмы, на дапушчальныя дзеянні). У сувязі з гэтым уводзяць такія паняцці як складанасць алгарытма (часавая, па памеры праграмы, вылічальная і інш.)

Для кожнага запісу можа існаваць мноства алгарытмаў, што прыводзяць да мэты. Павелічэнне эфектыўнасці алгарытмаў складае адну з задач сучаснай інфарматыкі. У 50-х гг. XX стагоддзя з’явілася нават яе асобная галіна — хуткія алгарытмы. У прыватнасці, у знаёмай усім з дзяцінства задачы аб памнажэнні дзесятковых лікаў выявіўся шэраг алгарытмаў, якія дазваляюць істотна (у асімптатычным сэнсе) паскорыць знаходжанне здабытку.

Яскравым прыкладам з’яўляецца алгарытм Чудноўскага для вылічэння ліку π.

Разам з распаўсюджаннем інфармацыйных тэхналогій павялічылася рызыка праграмных збояў. Адным з спосабаў пазбегнуць памылак у алгарытмах і іх рэалізацыях з'яўляецца давядзенне карэктнасці сістэм матэматычнымі сродкамі.

Выкарыстанне матэматычнага апарата для аналізу алгарытмаў і іх рэалізацый называюць фармальнымі метадамі. Фармальныя метады прадугледжваюць прымяненне фармальных спецыфікацый і, як правіла, набору інструментаў для сінтаксічнага аналізу і доказы уласцівасцей спецыфікацый. Абстрагаванне ад дэталей рэалізацыі дазваляе ўсталяваць уласцівасці сістэмы незалежна ад яе рэалізацыі. Акрамя таго, дакладнасць і адназначнасць матэматычных сцвярджэнняў дазваляе пазбегнуць шматзначнасці і недакладнасці натуральных моў^[1].

Па гіпотэзе Рычарда Мэйса «пазбяганне памылак лепш ліквідацыі памылак»^[2]. Паводле гіпотэзы Гоара «доказ праграм вырашае праблему карэктнасці, дакументацыі і сумяшчальнасці»^[3]. Доказ карэктнасці праграм дазваляе выяўляць ўласцівасці ў адносінах да ўсяго дыяпазону ўваходных дадзеных. Для доказу карэктнасці праграм, паняцце карэктнасці было пашырана на два тыпы:

• Частковая карэктнасць — праграма дае карэктны вынік для тых выпадкаў, калі яна завяршаецца.
• Поўная карэктнасць — праграма завяршае працу і выдае карэктны вынік для ўсіх элементаў з дыяпазону ўваходных дадзеных.

Пры доказе карэктнасці параўноўваюць тэкст праграмы са спецыфікацыяй жаданых суадносін уваходных-выходных дадзеных. Для доказаў тыпу Гоара гэтая спецыфікацыя выглядае сцвярджэнняў, якія называюць прад- і постумовы. У сукупнасці з самай праграмай, іх яшчэ называюць тройкамі Гоара. Гэтыя сцвярджэнні запісваюць

P{Q}R

дзе P — гэта перадумова, што павінна выконвацца перад запускам праграмы Q, а R — постумовы, правільныя пасля завяршэння працы праграмы.

Фармальныя метады былі паспяхова ужытыя да шырокага кола задач, у прыватнасці: распрацоўка электронных схем, штучнага інтэлекту, сістэм, адчувальных да надзейнасці, бяспекі, аўтаматычных сістэм на чыгунцы, верыфікацыі мікрапрацэсараў, спецыфікацыі стандартаў і спецыфікацыі і верыфікацыі праграм^[4].

Распаўсюджаным крытэрыем ацэнкі алгарытмаў з'яўляецца час работы і парадак росту працягласці работы ў залежнасці ад аб'ёму ўваходных дадзеных.

Кожнай канкрэтнай задачы супастаўляюць некаторы лік, які называюць яе памерам. Напрыклад, памерам задачы вылічэнні здабытку матрыц можа быць максімальны памер матрыц-множнікаў, для задач на графах памерам можа быць колькасць рэбраў графа.

Час, які затрачвае алгарытм, як функцыя ад памеру задачы n, называюць часавай складанасцю гэтага алгарытму T(n). Асімптотыку паводзін гэтай функцыі пры павелічэнні памеру задачы называюць асімптатычнай часавай складанасцю, а для яе абазначэння выкарыстоўваюць натацыю Ландау (вялікае O).

Менавіта асімптатычная складанасць вызначае памер задач, якія алгарытм здольны апрацаваць. Напрыклад, калі алгарытм апрацоўвае ўваходныя дадзеныя памерам n за час cn², дзе c — некаторая пастаянная, то кажуць, што часавая складанасць такога алгарытму O(n²).

Часта, пры распрацоўцы алгарытму спрабуюць паменшыць асімптатычную часавую складанасць для горшых выпадкаў. На практыцы ж, бываюць выпадкі, калі дастатковы алгарытм, які «звычайна» працуе хутка.

Груба кажучы, аналіз сярэдняй асімптатычнай часовай складанасці можна падзяліць на два тыпы: аналітычны і статыстычны. Аналітычны метад дае больш дакладныя вынікі, але больш складаны ў выкарыстанні на практыцы. Затое статыстычны метад дазваляе хутчэй ажыццяўляць аналіз складаных задач^[5].

У наступнай табліцы прыведзены распаўсюджаныя асімптатычныя складанасці з каментарыямі^[6].

• Дыскрэтнасць — каманды ці дзеянні выкладзены ў пэўнай паслядоўнасці. Выканаўшы адно дзеянне, адбываецца пераход да наступнага;
• Дэтэрмінаванасць — выканаўшы пэўную каманду, становіцца ясна, што рабіць далей;
• Элементарнасць каманд — каманды з'яўляюцца нескладанымі, проста і коратка апісваюцца і проста выконваюцца (патрабуецца мінімум ітэрацый);
• Масавасць — алгарытм можна выкарыстоўваць для вырашэння пэўнай групы задач.

• Тэорыя алгарытмаў
• Схема Горнера
• Машына Цьюрынга
• Алгарытм Чудноўскага

• Алгоритм // Математическая энциклопедия / И. М. Виноградов (гл. ред.). — М.: Советская энциклопедия, 1977. — Т. 1. — 576 с. — 150 000 экз. Стл. 202—206.