Альгарытм

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

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

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

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

Тэрмін

Сучаснае фармальнае азначэньне альгарытму было дадзена ў 1930—1950-х гадох ў працах Т’юрынга, Чэрча, Вінэра, Маркава.

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

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

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

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

Гісторыя

Баранэса Ада Лаўлэйс — першая ў сьвеце праграмоўца

Першы альгарытм, прызначаны для выкананьня на аўтаматычнай вылічальнай прыладзе (кампутары), апісала Ада Лаўлэйс у 1843 годзе. Альгарытм быў павінен вылічаць лікі Бэрнульлі й працаваць на аналітычнай машыне Бэбіджа. Гэты альгарытм лічыцца першай кампутарнай праграмай, а ягоная аўтарка, Ада Лаўлэйс — першым праграмоўцам^[1]. З 1930-х гадоў пачалося бурнае разьвіцьцё галіны дасьледаваньня альгарытмаў і станаўленьня інфарматыкі ў ейным сучасным выглядзе. У 1935 годзе Стывэн Клінаў распрацаваў першую фармулёўку тэорыі рэкурсіі, і паказаў эквівалентнасьць распрацаванай сыстэмы часткова рэкурсіўнай функцыі. У 1936 годзе незалежна былі апублікаваныя працы Элана Т’юрынга й Эміля Посту, у якіх прыведзены падобныя сыстэмы для вызначэньня панятку альгарытму. А ўжо ў 1937 годзе была даказана эквівалентнасьць розных азначэньняў.

Машына Т’юрынга прапаноўвала канструкцыю, прыдатную для аўтаматычнай інтэрпрэтацыі. Пабудаваная пад уплывам Элана Т’юрынга ў Вялікабрытаніі вылічальная сыстэма ACE (завершана ў 1950 годзе), і сыстэмы, пабудаваныя па архітэктуры фон Нэймана ў ЗША й у іншых краінах (у СССР — МЭСМ, распрацаваная ў 1950 годзе ў Інстытуце электратэхнікі АН УССР групай навукоўцаў пад кіраўніцтвам Сяргея Лебедзева), былі першымі ўнівэрсальнымі вылічальнымі прыладамі, якія цалкам задавальнялі патрабаваньні вылічэньня . На працягу 1935—1960 гадоў былі распрацаваны шматлікія ідэі і тэхналёгіі, якія ляглі ў аснову сучаснай інфарматыкі.

Фармальныя сродкі для прадстаўленьня альгарытмаў мелі ня толькі тэарэтычную значнасьць. Распрацоўка альгарытмічных моваў для праграмаваньня вылічальных прыладаў пачалася ў 1951 годзе з публікацыі нямецкага інжынэра Ганса Рутысгаўзэра. Спачатку важнай здавалася праблема натацыі, яе дасьледаваў Аляксей Ляпуноў, але паступова яна адышла на другі плян. Першая мова, Плянкалькюль (ням. Plankalkül) была распрацавана Конрадам Цузэ ў 1946 годзе, але з-за адсутнасьці кампілятараў выкананьне напісаных на гэтай мове праграмаў было немагчыма. Апісаньне мовы быў надрукавана ў 1972 годзе, а ў 2000 годзе быў створаны кампілятар для падмноства мовы. У сярэдзіне 1950-х была распрацавана мова праграмаваньня Фартран Джонам Бакусам з кампаніі IBM. У канцы 1950-х быў распрацаваны Алгол і Кабол, для навучальных мэтаў BASIC (1963) і Pascal (пачатак 1970-х). Для сыстэмнага праграмаваньня ў Bell Laboratories была распрацавана C.

λ-вылічэньне дало штуршок да стварэньня ў канцы 1950-х функцыянальнай мовы праграмаваньня Lisp. На аснове ідэяў Lisp было створана Scheme. Мова ML была распрацавана Робінам Мілнэрам ў канцы 1970-х. У канцы 1980-х была створана мова Haskell. Пад уплывам дасьледаваньняў у вобласьці штучнага інтэлекту была распрацавана парадыгма лягічнага праграмаваньня. У адрозьненьне ад імпэратыўнай і функцыянальнай парадыгмаў, лягічнае праграмаваньне не патрабуе ад распрацоўніка апісваць спосаб рашэньня пастаўленай задачы. Planner — першая мова лягічнага праграмаваньня, была распрацавана ў 1969 годзе. У пачатку 1970-х быў распрацаваны Prolog, які пасьля стаў распаўсюджанай мовай лягічнага праграмаваньня са стандартам ISO, зацьверджаным у 1995 годзе.

Уласьцівасьці альгарытму

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

Глядзіце таксама

Куін

Крыніцы

^ Fuegi, J. and Francis, J. «Lovelace & Babbage and the creation of the 1843 'notes'.» Annals of the History of Computing 25 #4

Вонкавыя спасылкі

Альгарытм на MathWorld. (анг.)
The Stanford GraphBase. (анг.)
Combinatorica. (анг.)
Algorithms Course Materials. (анг.)

[1] Fuegi, J. and Francis, J. «Lovelace & Babbage and the creation of the 1843 'notes'.» Annals of the History of Computing 25 #4

[1]