Алгарытм

З пляцоўкі Вікіпедыя.
Перайсці да: рух, знайсці

Алгары́тм, ад імя вучонага аль-Харэзмі (фарсі. خوارزمی [al-Khwārazmī]) -дакладны набор інструкцый, якія апісваюць парадак дзеянняў выканаўца для дасягнення выніку рашэння задачы за канчатковы/пэўны час. У старой трактоўцы замест слова «парадак» выкарыстоўвалася слова «паслядоўнасць», але па меры развіцця паралельнасці ў працы камп'ютараў слова «паслядоўнасць» сталі замяняць больш агульным словам «парадак». Гэта звязана з тым, што праца нейкіх інструкцый алгарытму можа залежыць ад іншых інструкцый або вынікаў іх працы. Такім чынам, некаторыя інструкцыі павінны выконвацца строга пасля завяршэння працы інструкцый, ад якіх яны залежаць. Незалежныя інструкцыі ці інструкцыі, якія сталі незалежнымі з-за завяршэння працы інструкцый, ад якіх яны залежаць, могуць выконвацца ў адвольным парадку, паралельна або адначасова, калі гэта дазваляюць працэсар і аперацыйная сістэма.

Раней часта пісалі «алгарыфм», цяпер такое напісанне выкарыстоўваецца рэдка, але, тым не менш, мае месца (напрыклад, Нармальны алгарыфм Маркава).

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

Гісторыя тэрміну[правіць | правіць зыходнік]

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

Старонка з «Алгебры» Мухамад Аль-Харэзміперсідскага матэматыка, ад імя якога паходзіць слова Алгарытм

Само слова алгарытм паходзіць ад імя персідскага вучонага Абу Абдулах Мухамеда ібн Муса аль-Харэзмі (алгарытм — аль-Харэзмі). Каля 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).

Баранэса Ада Лавлэйс, якую лічуць першым праграмiстам

Аднак з часам такія тлумачэнні ўсё менш цікавілі матэматыкаў, і слова 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 стагоддзя з'явілася нават яе асобная галіна - хуткія алгарытмы. У прыватнасці, у знаёмай усім з дзяцінства задачы аб памнажэнні дзесятковых лікаў выявіўся шэраг алгарытмаў, якія дазваляюць істотна (у асімптатычным сэнсе) паскорыць знаходжанне здабытку.

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

Уласцівасці алгарытма[правіць | правіць зыходнік]

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

Гл. таксама[правіць | правіць зыходнік]