Новая классификация алгоритмов
Предложена собственная классификация алгоритмов на основании обзора наиболее известных фундаментальных и современных работ. В отличие от известных классификаций введены понятия алгоритмов высших порядков и контекстнозависимых алгоритмов. Запропоновано власну класифікацію алгоритмів за результатами о...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101342 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Новая классификация алгоритмов / Г.А. Кравцов, И.А. Притулюк // Электронное моделирование. — 2016. — Т. 38, № 2. — С. 11-25. — Бібліогр.: 19 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859673864895725568 |
|---|---|
| author | Кравцов, Г.А. Притулюк, И.А. |
| author_facet | Кравцов, Г.А. Притулюк, И.А. |
| citation_txt | Новая классификация алгоритмов / Г.А. Кравцов, И.А. Притулюк // Электронное моделирование. — 2016. — Т. 38, № 2. — С. 11-25. — Бібліогр.: 19 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Предложена собственная классификация алгоритмов на основании обзора наиболее известных фундаментальных и современных работ. В отличие от известных классификаций введены понятия алгоритмов высших порядков и контекстнозависимых алгоритмов.
Запропоновано власну класифікацію алгоритмів за результатами огляду найбільш відомих фундаментальних та сучасних робіт. На відміну від відомих класифікацій введено поняття алгоритмів вищих порядків та контекстнозалежних алгоритмів.
The author’s classification of algorithms based on the review of famous fundamental and modern works is presented. The author’s classification is different from already known ones due to the involved terms of high order algorithms and context-related algorithms.
|
| first_indexed | 2025-11-30T14:37:40Z |
| format | Article |
| fulltext |
ÓÄÊ 510.5
Ã.À. Êðàâöîâ, êàíä. òåõí. íàóê, È.À. Ïðèòóëþê, àñïèðàíòêà
Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû
(Óêðàèíà, 03164, Êèåâ, óë. Ãåíåðàëà Íàóìîâà, 15,
òåë. (044) 4249165, e-mail: hryhoriy.kravtsov@gmail.com; i.prytulyuk@gmail.com)
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
Ïðåäëîæåíà ñîáñòâåííàÿ êëàññèôèêàöèÿ àëãîðèòìîâ íà îñíîâàíèè îáçîðà íàèáîëåå èç-
âåñòíûõ ôóíäàìåíòàëüíûõ è ñîâðåìåííûõ ðàáîò.  îòëè÷èå îò èçâåñòíûõ êëàññèôèêàöèé
ââåäåíû ïîíÿòèÿ àëãîðèòìîâ âûñøèõ ïîðÿäêîâ è êîíòåêñòíîçàâèñèìûõ àëãîðèòìîâ.
Çàïðîïîíîâàíî âëàñíó êëàñèô³êàö³þ àëãîðèòì³â çà ðåçóëüòàòàìè îãëÿäó íàéá³ëüø â³äî-
ìèõ ôóíäàìåíòàëüíèõ òà ñó÷àñíèõ ðîá³ò. Íà â³äì³íó â³ä â³äîìèõ êëàñèô³êàö³é ââåäåíî
ïîíÿòòÿ àëãîðèòì³â âèùèõ ïîðÿäê³â òà êîíòåêñòíîçàëåæíèõ àëãîðèòì³â.
Ê ë þ ÷ å â û å ñ ë î â à: êëàññèôèêàöèÿ, ñâîéñòâà, äèñêðåòíîñòü, äåòåðìèíèðîâàííîñòü,
ñëó÷àéíîñòü, êîíòåêñòíàÿ çàâèñèìîñòü.
Èçó÷åíèå òåîðåòè÷åñêèõ îñíîâ ôóíêöèîíàëüíûõ ÿçûêîâ ïðîãðàììèðîâà-
íèÿ ïðèâîäèò ê ïîíèìàíèþ òîãî ôàêòà, ÷òî ñóùåñòâóåò íåñîãëàñîâàííîñòü
â òåîðèè àëãîðèòìîâ, à èìåííî ìåæäó àëãîðèòìàìè âû÷èñëèìûõ ôóíêöèé
è ïîíÿòèåì ôóíêöèè â ôóíêöèîíàëüíûõ ÿçûêàõ.
 ðàáîòå [1] îäíîçíà÷íî îïðåäåëåíî, ÷òî «êëàññ àëãîðèòìîâ, âû÷èñëè-
ìûõ íà ìàøèíàõ, â òî÷íîñòè ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóð-
ñèâíûõ ôóíêöèé», èç ÷åãî â ïîñëåäóþùåì ñäåëàí âûâîä î ïðåäñòàâëåíèè
àëãîðèòìîâ ÷àñòè÷íî ðåêóðñèâíûìè ôóíêöèÿìè. Ôóíêöèîíàëüíûå ÿçûêè
ñîãëàñíî ñâîåé ïàðàäèãìå ïðîãðàììèðîâàíèÿ îïåðèðóþò âû÷èñëèìûìè íà
ìàøèíàõ Ïîñòà è Òüþðèíãà ôóíêöèÿìè, êëàññ êîòîðûõ â òåðìèíàõ ðàáîòû [1]
«â òî÷íîñòè ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé»,
êîòîðûé ñîâïàäåò ñ êëàññîì àëãîðèòìîâ, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà
è Ïîñòà. Ê ñîæàëåíèþ, â [1] íå ïîÿñíÿåòñÿ, ÷òî çíà÷èò «êëàññ, êîòîðûé â òî÷-
íîñòè ñîâïàäàåò ñ äðóãèì êëàññîì», íî áóäåì ïîëàãàòü, ÷òî â ñîîòâåòñòâèè ñ
òåîðèåé êëàññîâ, ïîñòðîåííîé íà àêñèîìàõ Ãåäåëÿ—Áåðíàéñà, òàêîå âûñêà-
çûâàíèå ñîîòâåòñòâóåò ïîíÿòèþ ðàâåíñòâà.
Øèðîêî èçâåñòíûå â òåîðèè ôóíêöèîíàëüíûõ ÿçûêîâ ôóíêöèè âûñ-
øèõ ïîðÿäêîâ íå èìåþò àíàëîãîâ â ñóùåñòâóþùåé òåîðèè àëãîðèòìîâ è íå
âûäåëåíû â îòäåëüíûé êëàññ ïðè èõ êëàññèôèêàöèè. Ýòî ñòàëî ïîâîäîì ê
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 11
� Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê, 2016
ïðîâåäåíèþ èññëåäîâàíèÿ ñ öåëüþ ñîïîñòàâëåíèÿ äâóõ òåîðèé è óñòðà-
íåíèÿ íåñîãëàñîâàííîñòè.
Ïðîâåäåííîå èññëåäîâàíèå îñíîâàíî íà äåòàëüíîì èçó÷åíèè ïîëó÷èâ-
øèõ íàèáîëüøóþ èçâåñòíîñòü è èìåþùèõ ïðàêòè÷åñêóþ öåííîñòü ðàáîò.
Äëÿ ïðåäñòàâëåíèÿ öåëîñòíîé êàðòèíû áóäåì ñëåäîâàòü ýòèì ðàáîòàì,
öèòèðóÿ èíîãäà çíà÷èòåëüíûå îòðûâêè îðèãèíàëüíûõ ðàáîò.
Ïîíÿòèå àëãîðèòìà. Àëãîðèòìàì è èõ ñâîéñòâàì ïîñâÿùåíî áîëü-
øîå ÷èñëî ôóíäàìåíòàëüíûõ ðàáîò, ñðåäè êîòîðûõ îñíîâíîé ìîæíî ñ÷è-
òàòü ðàáîòó [2], â êîòîðîé Ä.Ý. Êíóò ïèøåò, ÷òî ñàìî ñëîâî «àëãîðèòì» (al-
gorithm) (óñòàðåâøåå «àëãîðèôì») ïðåäñòàâëÿåò áîëüøîé èíòåðåñ. «Íà ïåð-
âûé âçãëÿä ìîæåò ïîêàçàòüñÿ, ÷òî êòî-òî ñîáèðàëñÿ íàïèñàòü ñëîâî «ëîãà-
ðèôì», íî ñëó÷àéíî ïåðåñòàâèë ïåðâûå ÷åòûðå áóêâû.  ñëîâàðå Webster’s
New World Dictionary, âûøåäøåì â 1957 ã. ýòîãî ñëîâà åùå íå áûëî. Òàì
íàõîäèì òîëüêî óñòàðåâøóþ ôîðìó «algorism» — ñòàðèííîå ñëîâî, êîòî-
ðîå îçíà÷àåò «âûïîëíåíèå àðèôìåòè÷åñêèõ äåéñòâèé â ïîìîùüþ àðàáñêèõ
öèôð».  ñðåäíèå âåêà àáàêèñòû ñ÷èòàëè íà àáàêàõ (ñ÷åòíûõ äîñêàõ), à
àëãîðèòìèêè èñïîëüçîâàëè algorism. Â ýïîõó âîçðîæäåíèÿ ýòî ñëîâî îêà-
çàëîñü çàáûòûì. Îäíè ëèíãâèñòû òîãî âðåìåíè ïûòàëèñü îáúÿñíèòü åãî
çíà÷åíèå ñî÷åòàíèåì ñëîâ «algiros» (áîëüíîé) è «arithmos» (÷èñëî), äðóãèå
íå ñîãëàøàëèñü ñ òàêèì òîëêîâàíèåì è óòâåðæäàëè, ÷òî ýòî ñëîâî ïðîèñ-
õîäèò îò «King Algor Of Castile».
Íàêîíåö, èñòîðèêàìè ìàòåìàòèêè áûëî óñòàíîâëåíî èñòèííîå ïðîèñ-
õîæäåíèå ñëîâà «algorism»: îíî ïðîèñõîäèò îò èìåíè àâòîðà çíàìåíèòîãî
ïåðñèäñêîãî ó÷åáíèêà ïî ìàòåìàòèêå Àáó Àáä Àëëàõ Ìóõàììåä èáí Ìóñà
àëü-Õîðåçìè, ÷òî îçíà÷àåò áóêâàëüíî «Îòåö Àáäóëû, Ìóõõàìåä, ñûí Ìóñ-
ñû, óðîæåíåö Õîðåçìà». Àëü-Õîðåçìè íàïèñàë çíàìåíèòóþ «Êíèãó î âîñ-
ñòàíîâëåíèè è ïðîòèâîïîñòàâëåíèè», êîòîðàÿ îïðåäåëèëà åùå îäíî ñëîâî:
«àëãåáðà».
Ïîñòåïåííî ôîðìà è çíà÷åíèå ñëîâà «algorism» èñêàçèëèñü. Êàê îáúÿñ-
íÿåòñÿ â ñëîâàðå Oxford English Dictionary, ýòî ñëîâî «ïðåòåðïåëî ìíî-
æåñòâî ïñåâäîýòèìîëîãè÷åñêèõ èñêàæåíèé, âêëþ÷àÿ ïîñëåäíèé âàðèàíò
«algorithm», ãäå ïðîèçîøëà ïóòàíèöà ñ êîðíåì ñëîâà ãðå÷åñêîãî ïðîèñ-
õîæäåíèÿ «arithmetic». Ýòîò ïåðåõîä îò «algorism» ê «algorithm» êàæåòñÿ
âïîëíå çàêîíîìåðíûì ââèäó òîãî, ÷òî ïðîèñõîæäåíèå ðàññìàòðèâàåìîãî
ñëîâà áûëî ïîëíîñòüþ çàáûòî.  ñòàðèííîì íåìåöêîì ìàòåìàòè÷åñêîì ñëî-
âàðå Vollst��àndiges mathematisches Lexicon (Leipzig, 1747) äàíî ñëåäóþùåå
îïðåäåëåíèå ñëîâà algorithmus: «Ýòîò òåðìèí âêëþ÷àåò â ñåáÿ ïîíÿòèå î
÷åòûðåõ òèïàõ àðèôìåòè÷åñêèõ îïåðàöèé, à èìåííî: î ñëîæåíèè, óìíîæåíèè,
âû÷èòàíèè è äåëåíèè». Ëàòèíñêîå âûðàæåíèå algorithmus infinitesimalis â òî
âðåìÿ èñïîëüçîâàëîñü äëÿ îïðåäåëåíèÿ «ñïîñîáîâ âûïîëíåíèÿ äåéñòâèé ñ
áåñêîíå÷íî ìàëûìè âåëè÷èíàìè, îòêðûòûìè Ëåéáíèöåì (Leibniz)» [2].
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
12 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
Ä.Ý. Êíóò [2] óòâåðæäàåò, ÷òî «ñîâðåìåííîå çíà÷åíèå ñëîâà «àëãî-
ðèòì» âî ìíîãîì àíàëîãè÷íî òàêèì ïîíÿòèÿì, êàê ðåöåïò, ïðîöåññ, ìåòîä,
ñïîñîá, ïðîöåäóðà, ïðîãðàììà. Íî âñå-òàêè ñëîâî «algorithm» èìååò äîïîë-
íèòåëüíûé ñìûñëîâîé îòòåíîê. Àëãîðèòì — ýòî íå ïðîñòî ïîñëåäîâàòåëü-
íîñòü âûïîëíåíèÿ îïåðàöèé äëÿ ðåøåíèÿ çàäà÷è îïðåäåëåííîãî òèïà».
Ò. Êîðìåí [3] íåôîðìàëüíî îïðåäåëÿåò àëãîðèòì, êàê «ëþáóþ êîð-
ðåêòíî îïðåäåëåííóþ âû÷èñëèòåëüíóþ ïðîöåäóðó, íà âõîä (input) êîòî-
ðîé ïîäàåòñÿ íåêàÿ âåëè÷èíà èëè íàáîð âåëè÷èí, è ðåçóëüòàòîì âûïîë-
íåíèÿ êîòîðîé ÿâëÿåòñÿ âûõîäíàÿ âåëè÷èíà (output) èëè íàáîð çíà÷åíèé.
Òàêèì îáðàçîì, àëãîðèòì ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîñòü âû÷èñ-
ëèòåëüíûõ øàãîâ, ïðåîáðàçóþùèõ âõîäíûå âåëè÷èíû â âûõîäíûå.
Àëãîðèòì òàêæå ìîæíî ðàññìàòðèâàòü êàê èíñòðóìåíò, ïðåäíàçíà-
÷åííûé äëÿ ðåøåíèÿ êîððåêòíî ïîñòàâëåííîé âû÷èñëèòåëüíîé çàäà÷è
(computational problem).  ïîñòàíîâêå çàäà÷è â îáùèõ ÷åðòàõ çàäàþòñÿ
îòíîøåíèÿ ìåæäó âõîäîì è âûõîäîì. Â àëãîðèòìå îïèñûâàåòñÿ êîíê-
ðåòíàÿ âû÷èñëèòåëüíàÿ ïðîöåäóðà, ñ ïîìîùüþ êîòîðîé óäàåòñÿ äîáèòüñÿ
óêàçàííûõ îòíîøåíèé. Ãîâîðÿò, ÷òî àëãîðèòì êîððåêòåí (correct), åñëè äëÿ
êàæäîãî ââîäà ðåçóëüòàòîì åãî ðàáîòû ÿâëÿåòñÿ êîððåêòíûé âûõîä. Ìû
ãîâîðèì, ÷òî êîððåêòíûé àëãîðèòì ðåøàåò äàííóþ âû÷èñëèòåëüíóþ çà-
äà÷ó. Åñëè àëãîðèòì íåêîððåêòíûé, òî äëÿ íåêîòîðûõ ââîäîâ îí ìîæåò
âîîáùå íå çàâåðøèòü ñâîþ ðàáîòó èëè âûäàòü îòâåò, îòëè÷íûé îò îæè-
äàåìîãî. Ïðàâäà, íåêîððåêòíûå àëãîðèòìû èíîãäà ìîãóò îêàçàòüñÿ ïîëåç-
íûìè, åñëè â íèõ åñòü âîçìîæíîñòü êîíòðîëèðîâàòü ÷àñòîòó âîçíèêíîâå-
íèÿ îøèáîê».
Ñëåäóåò çàìåòèòü, ÷òî ÷òî ïðîâåðêà êîððåêòíîñòè àëãîðèòìà ìîæåò
áûòü âåñüìà òðóäîåìêîé çàäà÷åé. Íàïðèìåð, êàê ïðîâåðèòü êîððåêòíîñòü
àëãîðèòìà íà âñåì ìíîæåñòâå äåéñòâèòåëüíûõ ÷èñåë èëè êîððåêòíîñòü
ôàêòîðèçàöèè ïðîèçâîëüíîãî ÷èñëà N?
Ç.Â. Àëôåðîâà [4] ïîä àëãîðèòìîì ïîíèìàåò «êîíå÷íóþ ñîâîêóïíîñòü
òî÷íî ñôîðìóëèðîâàííûõ ïðàâèë ðåøåíèÿ íåêîòîðîãî êëàññà çàäà÷. Àëãî-
ðèòìû, â ñîîòâåòñòâèè ñ êîòîðûìè ðåøåíèå ïîñòàâëåííûõ çàäà÷ ñâîäèòñÿ
ê àðèôìåòè÷åñêèì äåéñòâèÿì, íàçûâàþòñÿ ÷èñëåííûìè àëãîðèòìàìè, à
àëãîðèòìû, â ñîîòâåòñòâèè ñ êîòîðûìè ðåøåíèå ïîñòàâëåííîé çàäà÷è
ñâîäèòñÿ ê ëîãè÷åñêèì äåéñòâèÿì, íàçûâàþòñÿ ëîãè÷åñêèìè àëãîðèòìà-
ìè». Â [4] óòâåðæäàåòñÿ, ÷òî «àëãîðèòìàìè â ñîâðåìåííîé ìàòåìàòèêå
ïðèíÿòî íàçûâàòü êîíñòðóêòèâíî çàäàâàåìûå ñîîòâåòñòâèÿ ìåæäó ñëî-
âàìè â àáñòðàêòíûõ àëôàâèòàõ, ãäå àáñòðàêòíûì àëôàâèòîì íàçûâàåòñÿ
ëþáàÿ êîíå÷íàÿ ñîâîêóïíîñòü îáúåêòîâ, íàçûâàåìûõ áóêâàìè èëè ñèìâî-
ëàìè äàííîãî àëôàâèòà. Ïðè ýòîì ïðèðîäà ýòèõ îáúåêòîâ ñîâåðøåííî íå
èíòåðåñóåò. Ñèìâîëàìè àáñòðàêòíûõ àëôàâèòîâ ìîæíî ñ÷èòàòü, íàïðè-
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 13
ìåð, áóêâû àëôàâèòà êàêîãî-ëèáî ÿçûêà, öèôðû, ëþáûå çíà÷êè, ðèñóíêè è
äàæå ñëîâà êîíêðåòíîãî ÿçûêà. Âàæíî ëèøü, ÷òîáû ðàññìàòðèâàåìûé àë-
ôàâèò áûë êîíå÷íûì.
Ìîæíî íàçâàòü àëôàâèò êîíå÷íûì ìíîæåñòâîì ðàçëè÷íûõ ñèìâîëîâ.
Ñëîâî «àáñòðàêòíûé» äëÿ êðàòêîñòè áóäåì îïóñêàòü. Êàê ëþáîå ìíîæåñò-
âî àëôàâèò çàäàåòñÿ ïåðå÷èñëåíèåì åãî ýëåìåíòîâ, ò.å. ñèìâîëîâ. Ïîä
ñëîâîì èëè ñòðîêîé àëôàâèòà ïîíèìàþò ëþáóþ êîíå÷íóþ óïîðÿäî÷åí-
íóþ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ. Íàðÿäó ñî ñëîâàìè ïîëîæèòåëüíîé
äëèíû, ñîñòîÿùèìè íå ìåíåå ÷åì èç îäíîãî ñèìâîëà, â íåêîòîðûõ ñëó÷àÿõ
öåëåñîîáðàçíî ðàññìàòðèâàòü òàêæå ïóñòûå ñëîâà, íå ñîäåðæàùèå íè îä-
íîãî ñèìâîëà. Î÷åâèäíî, ÷òî òàêîå îïðåäåëåíèå ñëîâà îòëè÷àåòñÿ îò ïðè-
íÿòîãî â îáû÷íîì èëè åñòåñòâåííîì ÿçûêå. Ïðè èçó÷åíèè àëãîðèòìîâ
ñëîâàìè â óêàçàííîì âûøå ñìûñëå ñëåäóåò ñ÷èòàòü ëþáûå ñî÷åòàíèÿ è
ïîñëåäîâàòåëüíîñòè ñèìâîëîâ, â òîì ÷èñëå è áåññìûñëåííûå.
Àëôàâèòíûì îïåðàòîðîì èëè àëôàâèòíûì îòîáðàæåíèåì íàçûâàåòñÿ
âñÿêîå ñîîòâåòñòâèå, ïðè êîòîðîì ñëîâàì íåêîòîðîãî àëôàâèòà ñîïîñòàâ-
ëÿþòñÿ ñëîâà â òîì æå ñàìîì èëè äðóãîì ôèêñèðîâàííîì àëôàâèòå. Ïðè
ýòîì ïåðâûé àëôàâèò íàçûâàåòñÿ âõîäíûì, âòîðîé — âûõîäíûì àëôà-
âèòîì äàííîãî îïåðàòîðà.  ñëó÷àå ñîâïàäåíèÿ âõîäíîãî è âûõîäíîãî àë-
ôàâèòîâ ãîâîðÿò, ÷òî àëôàâèòíûé îïåðàòîð çàäàí â ñîîòâåòñòâóþùåì àë-
ôàâèòå. Èíûìè ñëîâàìè, àëôàâèòíûé îïåðàòîð — ôóíêöèÿ, çàäàþùàÿ
ñîîòâåòñòâèå ìåæäó ñëîâàìè âõîäíîãî àëôàâèòà è ñëîâàìè ýòîãî æå èëè
äðóãîãî àëôàâèòà.
Ðàçëè÷àþò îäíîçíà÷íûå è ìíîãîçíà÷íûå àëôàâèòíûå îïåðàòîðû. Ïîä
îäíîçíà÷íûì àëôàâèòíûì îïåðàòîðîì ïîíèìàåòñÿ òàêîé àëôàâèòíûé îïå-
ðàòîð, êîòîðûé êàæäîìó âõîäíîìó ñëîâó ñòàâèò â ñîîòâåòñòâèå íå áîëåå
îäíîãî âûõîäíîãî ñëîâà. Ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ, îäíîçíà÷íûé
àëôàâèòíûé îïåðàòîð ÿâëÿåòñÿ ñþðúåêòèâíûì îòîáðàæåíèåì».
Ñëåäóÿ óòâåðæäåíèÿì Ç.Â. Àëôåðîâîé [4], óêàæåì, ÷òî àëôàâèòíûé
îïåðàòîð, íå ñîïîñòàâëÿþùèé íåêîòîðîìó âõîäíîìó ñëîâó íèêàêîãî âû-
õîäíîãî ñëîâà, íå îïðåäåëåí íà ýòîì ñëîâå. Òàêèå îïåðàòîðû øèðîêî
èñïîëüçóþòñÿ â ôóíêöèîíàëüíûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ â îïåðàöèÿõ
«ñîïîñòàâëåíèÿ ñ îáðàçöîì» (pattern matching) [5] è â ÷àñòè÷íî îïðåäåëåí-
íûõ ôóíêöèÿõ (partial function) [5, 6].
Ñîâîêóïíîñòü âñåõ ñëîâ, íà êîòîðûõ àëôàâèòíûé îïåðàòîð îïðåäåëåí,
íàçûâàåòñÿ åãî îáëàñòüþ îïðåäåëåíèÿ èëè äîìåíîì [6]. Ñîâîêóïíîñòü
âñåõ ñëîâ, êîòîðûå ìîãóò áûòü ðåçóëüòàòîì âûïîëíåíèÿ àëôàâèòíîãî
îïåðàòîðà, íàçûâàåòñÿ îáëàñòüþ çíà÷åíèé èëè êîäîìåíîì [6].
«Ñ êàæäûì àëôàâèòíûì îïåðàòîðîì ñâÿçûâàåòñÿ èíòóèòèâíîå ïðåä-
ñòàâëåíèå î åãî ñëîæíîñòè. Íàèáîëåå ïðîñòûìè ÿâëÿþòñÿ àëôàâèòíûå
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
14 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
îïåðàòîðû, îñóùåñòâëÿþùèå ïîñèìâîëüíûå îòîáðàæåíèÿ. Ïîñèìâîëüíîå
îòîáðàæåíèå ñîñòîèò â òîì, ÷òî êàæäûé ñèìâîë âõîäíîãî ñëîâà çàìåíÿåòñÿ
íåêîòîðûì ñèìâîëîì âûõîäíîãî àëôàâèòà. Áîëüøîå çíà÷åíèå èìåþò òàê
íàçûâàåìûå êîäèðóþùèå îòîáðàæåíèÿ. Ïîä êîäèðóþùèì îòîáðàæåíèåì
ïîíèìàåòñÿ ñîîòâåòñòâèå, ñîïîñòàâëÿþùåå êàæäîìó ñèìâîëó âõîäíîãî
àëôàâèòà íåêîòîðóþ êîíå÷íóþ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ â âûõîäíîì
àëôàâèòå, íàçûâàåìóþ êîäîì. Êîäèðîâàíèå ïîçâîëÿåò ñâîäèòü èçó÷åíèå
ïðîèçâîëüíûõ àëôàâèòíûõ îòîáðàæåíèé ê àëôàâèòíûì îòîáðàæåíèÿì â
íåêîòîðîì ñòàíäàðòíîì àëôàâèòå. Íàèáîëåå ÷àñòî â êà÷åñòâå òàêîãî ñòàí-
äàðòíîãî àëôàâèòà âûáèðàåòñÿ òàê íàçûâàåìûé äâîè÷íûé àëôàâèò, ñîñ-
òîÿùèé èç äâóõ ñèìâîëîâ, êîòîðûå îáû÷íî îòîæäåñòâëÿþòñÿ ñ öèôðàìè 0
è 1». Òàê îáúÿñíÿåòñÿ ïðèðîäà êîäèðîâàíèÿ â ðàáîòå [4].
Ñ ïîíÿòèåì ñîïðÿæåííîãî àëôàâèòíîãî îïåðàòîðà, à òàêæå ñ ïðèðîäîé
âçàèìîñâÿçè ñîïðÿæåííûõ àëôàâèòíûõ îïåðàòîðîâ ìîæíî áîëåå äåòàëüíî
îçíàêîìèòüñÿ â ðàáîòå [4]. Ñëåäóåò çàìåòèòü, ÷òî ïðåäëîæåííûé Ç.Â. Àë-
ôåðîâîé àëôàâèòíûé îïåðàòîð åñòü íå ÷òî èíîå êàê óòî÷íåííàÿ àáñòðàê-
öèÿ ôóíêòîðà, à ñîïðÿæåííûé àëôàâèòíûé îïåðàòîð — óòî÷íåííàÿ àáñò-
ðàêöèÿ ñîïðÿæåííîãî ôóíêòîðà â òåîðèè êàòåãîðèé [7, 8].
Ñîãëàcíî [4] àëôàâèòíûå îïåðàòîðû, çàäàâàåìûå ñ ïîìîùüþ êîíå÷íîé
ñèñòåìû ïðàâèë, ïðèíÿòî íàçûâàòü àëãîðèòìàìè. Îòñþäà ëåãêî ïîíÿòü,
÷òî «âñÿêèé àëôàâèòíûé îïåðàòîð, êîòîðûé ìîæíî ôàêòè÷åñêè çàäàòü,
ÿâëÿåòñÿ íåïðåìåííî àëôàâèòîì. Îäíàêî ñëåäóåò èìåòü â âèäó îäíî ðàç-
ëè÷èå, ñóùåñòâóþùåå ìåæäó ïîíÿòèÿìè àëôàâèòíîãî îïåðàòîðà è àëãî-
ðèòìà. Â ïîíÿòèè àëôàâèòíîãî îïåðàòîðà ñóùåñòâåííî ëèøü ñàìî ñîîò-
âåòñòâèå, óñòàíàâëèâàåìîå ìåæäó âõîäíûìè è âûõîäíûìè ñëîâàìè, à íå
ñïîñîá, êîòîðûì ýòî ñîîòâåòñòâèå óñòàíàâëèâàåòñÿ. Â ïîíÿòèè àëãîðèòìà,
íàîáîðîò, îñíîâíûì ÿâëÿåòñÿ ñïîñîá çàäàíèÿ ñîîòâåòñòâèÿ, óñòàíàâëèâàå-
ìîãî àëãîðèòìîì». Òàêèì îáðàçîì, àëãîðèòì — ýòî àëôàâèòíûé îïåðàòîð
âìåñòå ñ ïðàâèëàìè, îïðåäåëÿþùèìè åãî äåéñòâèÿ.
 ðàáîòå [9] äàíî îïðåäåëåíèå àëãîðèòìîâ, êàê «íåêîòîðûõ èíñòðó-
ìåíòîâ îïåðèðîâàíèÿ ñòðóêòóðàìè äàííûõ, ãäå ñòðóêòóðîé äàííûõ íàçû-
âàåòñÿ ñïîñîá îðãàíèçàöèè äàííûõ â ïàìÿòè êîìïüþòåðà (èëè íà äèñêå).
Ïðèìåðàìè ñòðóêòóð äàííûõ ÿâëÿþòñÿ ìàññèâû, ñâÿçàííûå ñïèñêè, ñòåêè,
äâîè÷íûå äåðåâüÿ, õåø-òàáëèöû è ò.ï. Î÷åâèäíî, ÷òî òàêîå îïðåäåëåíèå
ìàëîèíôîðìàòèâíîå».
À.È. Ìàëüöåâ [1] êîíñòàòèðóåò èíòóèòèâíîñòü ïîíÿòèÿ àëãîðèòìà,
êîòîðîå «õîòÿ è íåñòðîãîå, íî íàñòîëüêî ÿñíîå, ÷òî ïðàêòè÷åñêè íå áûëî
ñåðüåçíûõ ñëó÷àåâ, êîãäà ìàòåìàòèêè ðàçîøëèñü áû âî ìíåíèÿõ îòíîñè-
òåëüíî òîãî, ÿâëÿåòñÿ ëè àëãîðèòìîì òîò èëè èíîé êîíêðåòíî çàäàííûé
ïðîöåññ». Îäíàêî, «...ïîëîæåíèå ñóùåñòâåííî èçìåíèëîñü â ÕÕ âåêå, âûä-
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 15
âèíóâøåì íà ïåðâûé ïëàí òàêèå àëãîðèòìè÷åñêèå ïðîáëåìû, ñóùåñòâî-
âàíèå ïîëîæèòåëüíîãî ðåøåíèÿ êîòîðûõ áûëî ñîìíèòåëüíûì. Äåéñòâè-
òåëüíî, îäíî äåëî — äîêàçàòü ñóùåñòâîâàíèå àëãîðèòìà, äðóãîå — äîêà-
çàòü îòñóòñòâèå àëãîðèòìà. Ïåðâîå ìîæíî ñäåëàòü ïóòåì ôàêòè÷åñêîãî
îïèñàíèÿ ïðîöåññà, ðåøàþùåãî çàäà÷ó; â ýòîì ñëó÷àå äîñòàòî÷íî è èíòóè-
òèâíîãî ïîíÿòèÿ àëãîðèòìà, ÷òîáû óäîñòîâåðèòüñÿ â òîì, ÷òî îïèñàííûé
ïðîöåññ è åñòü àëãîðèòì. Äîêàçàòü íåñóùåñòâîâàíèå àëãîðèòìà òàêèì
ïóòåì íåâîçìîæíî. Äëÿ ýòîãî íóæíî òî÷íî çíàòü, ÷òî òàêîå àëãîðèòì.
 20-õ ãîäàõ ÕÕ âåêà çàäà÷à òî÷íîãî îïðåäåëåíèÿ ïîíÿòèÿ àëãîðèòìà
ñòàëà îäíîé èç öåíòðàëüíûõ ìàòåìàòè÷åñêèõ ïðîáëåì. Ðåøåíèå åå áûëî
ïîëó÷åíî â ñåðåäèíå 30-õ ãîäîâ òîãî æå âåêà â ðàáîòàõ Ãèëüáåðòà, Ãåäåëÿ,
×åð÷à, Êëèíè, Ïîñòà è Òüþðèíãà â äâóõ ôîðìàòàõ. Ïåðâîå ðåøåíèå áûëî
îñíîâàíî íà ïîíÿòèè ðåêóðñèâíîé ôóíêöèè, âòîðîå — íà îïèñàíèè òî÷íî
î÷åð÷åííîãî êëàññà ïðîöåññîâ».
Ñîãëàñíî [1] «÷èñëîâûå ôóíêöèè, çíà÷åíèÿ êîòîðûõ ìîæíî âû÷èñëÿòü
ïîñðåäñòâîì íåêîòîðîãî (åäèíîãî äëÿ äàííîé ôóíêöèè) àëãîðèòìà, íàçû-
âàþòñÿ âû÷èñëèìûìè ôóíêöèÿìè. Èìåííî îïðåäåëåíèå À.È. Ìàëüöåâà
äàåò âîçìîæíîñòü ïîñòðîèòü ïàðàëëåëü ìåæäó ôóíêöèÿìè â ôóíêöèîíàëü-
íûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ è òåîðåòè÷åñêèìè àñïåêòàìè àëãîðèòìîâ â
ìàòåìàòèêå, èáî ñîâîêóïíîñòü âû÷èñëèìûõ ôóíêöèé äëÿ ñàìûõ ðàçíûõ
ïîíèìàíèé ïðîöåññîâ, óäîâëåòâîðÿþùàÿ óñëîâèÿì, îïðåäåëåííûì Ìàëü-
öåâûì äëÿ àëãîðèòìà, îêàçàëàñü ëåãêî îïèñûâàåìîé â òåðìèíàõ ìàòåìàòè-
êè. Ýòà òî÷íî îïèñàííàÿ ñîâîêóïíîñòü ÷èñëîâûõ ôóíêöèé, ñîâïàäàþùàÿ ñ
ñîâîêóïíîñòüþ âñåõ âû÷èñëèìûõ ôóíêöèé ïðè ñàìîì øèðîêîì äî ñèõ ïîð
èçâåñòíîì ïîíèìàíèè àëãîðèòìà, íîñèò íàçâàíèå ñîâîêóïíîñòè ðåêóð-
ñèâíûõ ôóíêöèé».
 ðàáîòå [1] ñêàçàíî: «Ãèëüáåðò è Áåðíàéñ [10] ðàññìàòðèâàëè ðåêóð-
ñèâíûå îïðåäåëåíèÿ, îòòàëêèâàÿñü îò àêñèîì àðèôìåòèêè Ïåàíî è âûñò-
ðàèâàÿ ñâîå âèäåíèå ðåêóðñèâíîé àðèôìåòèêè. Îïèðàÿñü íà èäåè Ãèëüáåðòà
è Áåðíàéñà, Ãåäåëü [11] âïåðâûå îïèñàë êëàññ âñåõ ðåêóðñèâíûõ ôóíêöèé
êàê êëàññ âñåõ ÷èñëîâûõ ôóíêöèé, îïðåäåëèìûõ â íåêîòîðîé ôîðìàëüíîé
ñèñòåìå. Èñõîäÿ èç äðóãèõ ñîîáðàæåíèé, ×åð÷ [12] ïðèøåë ê òîìó æå
êëàññó ÷èñëîâûõ ôóíêöèé, ÷òî è Ãåäåëü. Àíàëèç èäåé, ïðèâåäøèõ ê ýòîìó
êëàññó ôóíêöèé, ïîçâîëèë Àëîíçî ×åð÷ó ïåðâûì îïóáëèêîâàòü ãèïîòåçó î
òîì, ÷òî êëàññ ðåêóðñèâíûõ ôóíêöèé òîæäåñòâåíåí êëàññó âñþäó îïðåäå-
ëåííûõ âû÷èñëèìûõ ôóíêöèé. Ýòà ãèïîòåçà èçâåñòíà êàê òåçèñ ×åð÷à. Òàê
êàê ïîíÿòèå âû÷èñëèìîé ôóíêöèè òî÷íî íå îïðåäåëåíî, òî òåçèñ ×åð÷à äî-
êàçàòü íåëüçÿ.
Ó÷èòûâàÿ, ÷òî íå âñå ïðîöåññû âû÷èñëåíèé êîíå÷íû, Ñòèâ Êîëë Êëè-
íè ââåë ïîíÿòèå ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè [13] è âûñêàçàë ãèïîòåçó,
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
16 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
÷òî âñå ÷àñòè÷íûå (ò.å. íå îáÿçàòåëüíî îïðåäåëåííûå äëÿ âñåõ çíà÷åíèé
àðãóìåíòîâ) ôóíêöèè, âû÷èñëèìûå ïîñðåäñòâîì àëãîðèòìîâ, ÿâëÿþòñÿ
÷àñòè÷íî ðåêóðñèâíûìè».
 ðàáîòå [1] íå ðàçëè÷àþòñÿ ãèïîòåçû À. ×åð÷à è Ñ. Êëèíè. Ãèïîòåçà
Ñ. Êëèíè, êîòîðàÿ ÿâëÿåòñÿ áîëåå îáùåé, ÷åì ãèïîòåçà À. ×åð÷à, òàê æå
íåäîêàçóåìà, êàê è ãèïîòåçà À. ×åð÷à. «Òåçèñ ×åð÷à îêàçàëñÿ äîñòàòî÷-
íûì, ÷òîáû ïðèäàòü íåîáõîäèìóþ òî÷íîñòü ôîðìóëèðîâêàì àëãîðèòìè÷åñ-
êèõ ïðîáëåì è â ðÿäå ñëó÷àåâ ñäåëàòü âîçìîæíûì äîêàçàòåëüñòâî èõ íåðàç-
ðåøèìîñòè» [1]. À.È. Ìàëüöåâ êîíñòàòèðóåò, ÷òî «òî÷íîå îïèñàíèå êëàññà
÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé âìåñòå ñ òåçèñîì ×åð÷à — Êëèíè äàåò îäíî
èç âîçìîæíûõ ðåøåíèé çàäà÷è îá óòî÷íåíèè ïîíÿòèÿ àëãîðèòìà».
Ý.Ë. Ïîñò [14] è À. Òüþðèíã [15] «íåçàâèñèìî äðóã îò äðóãà è ïî÷òè
îäíîâðåìåííî ñ ðàáîòàìè ×åð÷à è Êëèíè óòî÷íèëè íåïîñðåäñòâåííî ñàìî
ïîíÿòèå àëãîðèòìà è óæå ïîòîì, ïðè åãî ïîìîùè òî÷íî îïðåäåëèëè êëàññ
âû÷èñëèìûõ ôóíêöèé. Îñíîâíàÿ ìûñëü Ïîñòà è Òüþðèíãà çàêëþ÷àëàñü â
òîì, ÷òî àëãîðèòìè÷åñêèå ïðîöåññû — ýòî ïðîöåññû, êîòîðûå ìîæåò ñî-
âåðøàòü ïîäõîäÿùå óñòðîåííàÿ «ìàøèíà». Â ñîîòâåòñòâèè ñ ýòîé ìûñëüþ
èìè áûëè îïèñàíû â òî÷íûõ ìàòåìàòè÷åñêèõ òåðìèíàõ óçêèå êëàññû ìàøèí,
ïîçâîëÿþùèõ îñóùåñòâèòü èëè èìèòèðîâàòü î÷åíü ñëîæíûå àëãîðèòìè÷åñ-
êèå ïðîöåññû, êîòîðûå êîãäà-ëèáî îïèñûâàëèñü ìàòåìàòèêàìè» [1].
Ñâîéñòâà àëãîðèòìà. Ñîãëàñíî [2] àëãîðèòì îáëàäàåò òàêèìè ïÿòüþ
ñâîéñòâàìè: êîíå÷íîñòü, îïðåäåëåííîñòü, òî÷êà âõîäà (ââîä), òî÷êà âû-
õîäà (âûâîä) è ýôôåêòèâíîñòü.
Êîíå÷íîñòü àëãîðèòìà îçíà÷àåò, ÷òî àëãîðèòì âñåãäà äîëæåí çàêàí-
÷èâàòüñÿ ïîñëå âûïîëíåíèÿ êîíå÷íîãî ÷èñëà øàãîâ. ×èñëî øàãîâ àëãî-
ðèòìà ìîæåò áûòü äîñòàòî÷íî áîëüøèì, íî öåëåñîîáðàçíûì. Ñîãëàñíî [4]
ñâîéñòâî àëãîðèòìà, îáåñïå÷èâàþùåå ïîëó÷åíèå ðåçóëüòàòà ÷åðåç êîíå÷-
íîå ÷èñëî øàãîâ, íàçûâàåòñÿ ðåçóëüòàòèâíîñòüþ àëãîðèòìà. Îäíàêî àâòîð
[2], äàâ îïðåäåëåíèå ñâîéñòâà êîíå÷íîñòè àëãîðèòìà, íå ñêàçàë íè ñëîâà î
áåñêîíå÷íûõ àëãîðèòìàõ. Ïîä áåñêîíå÷íûì àëãîðèòìîì áóäåì ïîíèìàòü
òàêîé àëãîðèòì, ðåàëèçàöèÿ êîòîðîãî â âèäå ïðîãðàììû ïðè çàïóñêå íà
êîìïüþòåðå ìîæåò áûòü îñòàíîâëåíà òîëüêî ïîñðåäñòâîì âûêëþ÷åíèÿ (ïå-
ðåçàãðóçêè) êîìïüþòåðà.
Ñëåäóåò çàìåòèòü, ÷òî «ïðîöåäóðà, îáëàäàþùàÿ âñåìè õàðàêòåðèñòè-
êàìè (ñâîéñòâàìè) àëãîðèòìà, çà èñêëþ÷åíèåì, âîçìîæíî, êîíå÷íîñòè,
íàçûâàåòñÿ ìåòîäîì âû÷èñëåíèé. Ìåòîä âû÷èñëåíèÿ, âûðàæåííûé íà ÿçû-
êå ïðîãðàììèðîâàíèÿ, íàçûâàåòñÿ ïðîãðàììîé» [2].
Îïðåäåëåííîñòü [2] «òðåáóåò, ÷òîáû êàæäûé øàã àëãîðèòìà áûë òî÷-
íî îïðåäåëåí. Äåéñòâèÿ, êîòîðûå íóæíî âûïîëíèòü, äîëæíû áûòü ñòðîãî
è íåäâóñìûñëåííî îïðåäåëåíû äëÿ êàæäîãî âîçìîæíîãî ñëó÷àÿ. Ïðè îïè-
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 17
ñàíèè àëãîðèòìîâ åñòåñòâåííûìè ÿçûêàìè ñóùåñòâóåò âîçìîæíîñòü íå-
òî÷íîãî ïîíèìàíèÿ ìûñëè àâòîðà. ×òîáû ïðåîäîëåòü ýòî çàòðóäíåíèå, äëÿ
îïèñàíèÿ àëãîðèòìîâ áûëè ðàçðàáîòàíû ôîðìàëüíî îïðåäåëåííûå ÿçûêè —
ÿçûêè ïðîãðàììèðîâàíèÿ èëè ìàøèííûå ÿçûêè, â êîòîðûõ êàæäûé îïåðà-
òîð èìååò ñòðîãî îïðåäåëåííîå çíà÷åíèå.
Êàæäûé àëãîðèòì èìååò òî÷êó âõîäà èëè ââîäà.  òî÷êå âõîäà îïðå-
äåëÿþòñÿ âõîäíûå äàííûå àëãîðèòìà, êîòîðûå ìîãóò è îòñóòñòâîâàòü.
Âõîäíûå äàííûå ìîãóò áûòü ñòàòè÷åñêèìè, à ìîãóò áûòü äèíàìè÷åñêèìè,
êîòîðûå áåðóòñÿ èç îïðåäåëåííîãî íàáîðà îáúåêòîâ. Âõîäíûå äàííûå
ìîæíî ïîäåëèòü íà äâå ãðóïïû: îïðåäåëÿþùèå àëãîðèòì è êîíòåêñòíûå.
Îïðåäåëÿþùèå àëãîðèòì äàííûå ïðåäñòàâëÿþò ñîáîé íåîáõîäèìûé è
äîñòàòî÷íûé íàáîð íà÷àëüíûõ äàííûõ äëÿ ðåøåíèÿ íåêîòîðîé çàäà÷è,
îïèñûâàåìîé àëãîðèòìîì â åå òåîðåòè÷åñêîé ïîñòàíîâêå. Êîíòåêñòíûå
äàííûå — äàííûå, îïðåäåëÿþùèå óñëîâèÿ ïðîâåäåíèÿ âû÷èñëåíèé».
Íàïðèìåð, íåîáõîäèìî îòñîðòèðîâàòü ïîñëåäîâàòåëüíîñòü ÷èñåë â
îäèí ïîòîê èëè íåñêîëüêî ïîòîêîâ âû÷èñëåíèé. Ñóòü çàäà÷è îò ýòîãî íå
ìåíÿåòñÿ: íåîáõîäèìî îòñîðòèðîâàòü ïîñëåäîâàòåëüíîñòü. Èñõîäíàÿ ïîñ-
ëåäîâàòåëüíîñòü — ýòî îïðåäåëÿþùèå àëãîðèòì èñõîäíûå äàííûå, à ïàðà-
ìåòð «â ñêîëüêî ïîòîêîâ ñîðòèðîâàòü» — ýòî êîíòåêñòíûå èñõîäíûå äàí-
íûå. Ïîñêîëüêó àëãîðèòì åñòü ôóíêöèÿ, êîíòåêñòíî-çàâèñèìûå àëãîðèò-
ìû ïîðîæäàþò êëàññ ôóíêöèé â ôóíêöèîíàëüíûõ ÿçûêàõ ïðîãðàììèðî-
âàíèÿ, íàïðèìåð Scala, íàçûâàåìûé çàìûêàíèåì (closure) [5].
Êàæäûé àëãîðèòì èìååò âûâîä, ñîñòîÿùèé èç îäíîãî èëè íåñêîëüêèõ
âûõîäíûõ äàííûõ (ðåçóëüòàòîâ ðàáîòû àëãîðèòìà). Ðåçóëüòàòû ðàáîòû
àëãîðèòìà òåñíî ñâÿçàíû ñ âõîäíûìè äàííûìè.
Àëãîðèòì îáû÷íî ñ÷èòàåòñÿ ýôôåêòèâíûì, åñëè âñå åãî îïåðàòîðû
äîñòàòî÷íî ïðîñòû äëÿ òîãî, ÷òîáû èõ ìîæíî áûëî òî÷íî âûïîëíèòü â
òå÷åíèå êîíå÷íîãî ïðîìåæóòêà âðåìåíè ñ ïîìîùüþ êàðàíäàøà è áóìàãè.
Ïîíÿòèå ýôôåêòèâíîñòè àëãîðèòìà ñâÿçàíî ñ ïîÿâëåíèåì íàó÷íîãî íàï-
ðàâëåíèÿ — àíàëèç àëãîðèòìîâ [1, 3]. Ïîíÿòèå ýôôåêòèâíîñòü àëãîðèòìà
ïðèìåíèìî òîëüêî ê àëãîðèòìàì ÷èñòûõ âû÷èñëåíèé. Âûïîëíåíèå êàæ-
äîãî èç îïåðàòîðîâ àëãîðèòìà íå îçíà÷àåò, ÷òî ñ åãî ïîìîùüþ ìîæíî
ïîëó÷èòü ðåçóëüòàò çà ïðèåìëåìîå âðåìÿ äëÿ ïðîèçâîëüíîé çàäà÷è èç
êëàññà ðåøàåìûõ èì.  ïåðâóþ î÷åðåäü, ýòî çàäà÷è èç êëàññà NP-ñëîæíûõ
èëè ýêñïîíåíöèàëüíîé ñëîæíîñòè. Äàííîå çàìå÷àíèå òðåáóåò îòäåëüíîãî
èññëåäîâàíèÿ.
Ê ñâîéñòâàì àëãîðèòìà îòíîñÿò äåòåðìèíèðîâàííîñòü, ìàññîâîñòü,
ýêâèâàëåíòíîñòü, îáëàñòü ïðèìåíèìîñòè [2, 4]. Ç.Â. Àëôåðîâà îïðåäåëÿåò:
«Äâà àëôàâèòíûõ îïåðàòîðà ñ÷èòàþòñÿ ðàâíûìè, åñëè îíè èìåþò îäíó è
òó æå îáëàñòü îïðåäåëåíèÿ è ñîïîñòàâëÿþò ëþáîìó íàïåðåä çàäàííîìó
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
18 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
âõîäíîìó ñëîâó èç ýòîé îáëàñòè îäèíàêîâûå âûõîäíûå ñëîâà» [4]. Ä. Êíóò
óòâåðæäàåò, ÷òî «äâà àëãîðèòìà ñ÷èòàþòñÿ ðàâíûìè, åñëè ðàâíû ñîîò-
âåòñòâóþùèå èì àëôàâèòíûå îïåðàòîðû è ñîâïàäàåò ñèñòåìà ïðàâèë, çà-
äàþùèõ äåéñòâèå ýòèõ àëãîðèòìîâ íà âûõîäíûå ñëîâà» [2].
Ñîãëàñíî Ç.Â. Àëôåðîâîé: «Ýêâèâàëåíòíîñòü àëãîðèòìîâ îïðåäåëÿåò-
ñÿ ÷åðåç ñîâïàäåíèå àëôàâèòíûõ îïåðàòîðîâ àëãîðèòìîâ, íî íå ñîâïàäåíèå
ñïîñîáîâ èõ çàäàíèÿ (ñèñòåìû ïðàâèë). Îáû÷íî â òåîðèè àëãîðèòìîâ ðàñ-
ñìàòðèâàþò ëèøü òàêèå àëãîðèòìû, êîòîðûì ñîîòâåòñòâóþò îäíîçíà÷íûå
àëôàâèòíûå îïåðàòîðû. Âñÿêèé àëãîðèòì òàêîãî ðîäà ëþáîìó âõîäíîìó
ñëîâó îòíîñèò òîëüêî îäíî âûõîäíîå ñëîâî. Òàêèå àëãîðèòìû è àëôà-
âèòíûå îïåðàòîðû íàçûâàþò äåòåðìèíèðîâàííûìè.
Ìàññîâîñòü àëãîðèòìà — ñâîéñòâî àëãîðèòìà áûòü ïðèìåíèìûì äëÿ
ìíîæåñòâà ñòðîê. Åñëè àëãîðèòì ïðèìåíèì äëÿ ìíîæåñòâà ñòðîê, òî îí
îáëàäàåò ñâîéñòâîì ìàññîâîñòè.
Èç ñâîéñòâà ðåçóëüòàòèâíîñòè (êîíå÷íîñòè) âûòåêàåò ïîíÿòèå îáëàñòè
ïðèìåíèìîñòè àëãîðèòìà.
Îáëàñòü ïðèìåíèìîñòè àëãîðèòìà — ìíîæåñòâî ñòðîê, äëÿ êîòîðûõ
àëãîðèòì êîíå÷åí èëè ðåçóëüòàòèâåí.
Òåïåðü ýêâèâàëåíòíîñòü àëãîðèòìîâ ìîæåò áûòü îïðåäåëåíà ñëåäóþùèì
îáðàçîì: äâà àëãîðèòìà ýêâèâàëåíòíû, åñëè ñîâïàäàþò èõ îáëàñòè ïðèìåíè-
ìîñòè è ðåçóëüòàòû ïåðåðàáîòêè ëþáîãî ñëîâà èç ýòîé îáëàñòè.
Ðàçëè÷àþò åùå ñëó÷àéíûå è ñàìîèçìåíÿþùèåñÿ àëãîðèòìû. Àëãî-
ðèòì íàçûâàåòñÿ ñëó÷àéíûì, åñëè â ñèñòåìå ïðàâèë, îïèñûâàþùèõ àëãî-
ðèòì, ïðåäóñìàòðèâàåòñÿ âîçìîæíîñòü ñëó÷àéíîãî âûáîðà òåõ èëè èíûõ
ñëîâ èëè òåõ èëè èíûõ ïðàâèë. Èì ñîîòâåòñòâóþò ìíîãîçíà÷íûå àëôà-
âèòíûå îïåðàòîðû». Ñóáúåêòèâíî ïîíÿòèå ïðèìåíèìîñòè òðåáóåò óòî÷íå-
íèÿ, à ïîíÿòèå ðåçóëüòàòèâíîñòè âîîáùå íå îïðåäåëåíî.
«Àëãîðèòì íàçûâàåòñÿ ñàìîèçìåíÿþùèìñÿ, åñëè îí íå òîëüêî ïåðåðà-
áàòûâàåò âõîäíûå ñëîâà, íî è ñàì èçìåíÿåòñÿ â ïðîöåññå òàêîé ïåðåðà-
áîòêè. Ðåçóëüòàò äåéñòâèÿ ñàìîèçìåíÿþùåãîñÿ àëãîðèòìà íà òî èëè èíîå
ñëîâî çàâèñèò íå òîëüêî îò ýòîãî ñëîâà, íî è îò èñòîðèè ïðåäûäóùåé
ðàáîòû àëãîðèòìà» [4].
Èçó÷åíèå òåîðèè ôóíêöèîíàëüíûõ ÿçûêîâ [6, 12] è èõ ïðàêòè÷åñêîãî
ïðèìåíåíèÿ ïðèâîäèò ê íåîáõîäèìîñòè ôîðìóëèðîâàíèÿ ïîíÿòèÿ àëãî-
ðèòìà ÷èñòûõ âû÷èñëåíèé èëè ÷èñòîãî àëãîðèòìà.
×èñòûé àëãîðèòì — àëãîðèòì ðåøåíèÿ êîíêðåòíîé çàäà÷è, â êî-
òîðîì íå ñóùåñòâóåò íè îäíîãî øàãà, êîòîðûé ìîæåò áûòü óäàëåí áåç
íàðóøåíèÿ îòîáðàæåíèÿ èñõîäíûõ äàííûõ â âûõîäíûå. Ïîÿñíèì îïðå-
äåëåíèå. Íàïðèìåð, åñòü àëãîðèòì, êîòîðûé âû÷èñëÿåò íåêîòîðîå çíà÷å-
íèå â öèêëå è ïóáëèêóåò ïðîìåæóòî÷íûå ðåçóëüòàòû. Øàãè ïóáëèêàöèè
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 19
ïðîìåæóòî÷íûõ äàííûõ ìîãóò áûòü óäàëåíû èç àëãîðèòìà áåç óùåðáà äëÿ
êîíå÷íîãî ðåçóëüòàòà âû÷èñëåíèé. ×èñòûå àëãîðèòìû â ôóíêöèîíàëüíûõ
ÿçûêàõ ïðîãðàììèðîâàíèÿ (íàïðèìåð, Scala) ïðåäñòàâëÿþò â âèäå ÷èñòûõ
ôóíêöèé (pure function) [5]. Øàãè àëãîðèòìîâ, êîòîðûå ìîãóò áûòü óäàëå-
íû áåç óùåðáà äëÿ âû÷èñëåíèé, ïðèíÿòî íàçûâàòü ñòîðîííèé ýôôåêò (side
effect)[16].
 òåîðèè àëãîðèòìîâ áîëüøîå âíèìàíèå óäåëÿåòñÿ îáùèì ñïîñîáàì
çàäàíèÿ àëãîðèòìîâ, äëÿ êîòîðûõ õàðàêòåðíû ñâîéñòâà óíèâåðñàëüíîñòè,
ò.å. òàêèì ñïîñîáàì, êîòîðûå ïîçâîëÿþò çàäàòü àëãîðèòì, ýêâèâàëåíòíûé
ëþáîìó íàïåðåä çàäàííîìó àëãîðèòìó. Âñÿêèé îáùèé ñïîñîá çàäàíèÿ
àëãîðèòìîâ ïðèíÿòî íàçûâàòü àëãîðèòìè÷åñêîé ñèñòåìîé. Ïðè îïèñàíèè
àëãîðèòìè÷åñêèõ ñèñòåì èñïîëüçóþòñÿ ñïåöèàëüíûå ôîðìàëèçîâàííûå
ñðåäñòâà, â òîì ÷èñëå ôîðìàëüíàÿ ñåìàíòèêà.
Îñíîâíûå ôîðìàëèçìû ïðèêëàäíîé òåîðèè àëãîðèòìîâ ìîæíî ðàçäå-
ëèòü íà äâà íàïðàâëåíèÿ, óñëîâíî íàçûâàåìûå «àëãåáðàè÷åñêèì» è «ãåî-
ìåòðè÷åñêèì» [1]. Àëãåáðàè÷åñêàÿ òåîðèÿ ñòðîèòñÿ â êîíêðåòíîé ñèìâî-
ëèêå, ïðè êîòîðîé àëãîðèòìû ðàññìàòðèâàþòñÿ â âèäå ëèíåéíûõ òåêñòîâ.
 ãåîìåòðè÷åñêîé òåîðèè àëãîðèòìû ñòðîÿòñÿ â âèäå ìíîæåñòâ, ìåæäó êî-
òîðûìè ââîäÿòñÿ ñâÿçè, íîñÿùèå õàðàêòåð îòîáðàæåíèé èëè áèíàðíûõ
îòíîøåíèé. Ïðè ýòîì çíà÷èòåëüíîå ìåñòî çàíèìàåò ãåîìåòðè÷åñêàÿ èí-
òåðïðåòàöèÿ îáúåêòîâ â âèäå ãðàôîâ, âåðøèíû êîòîðûõ çàäàþò ýëåìåíòû
ìíîæåñòâà, à ðåáðà — îòíîøåíèÿ ìåæäó íèìè.
Ê ïåðâîìó íàïðàâëåíèþ îòíîñÿòñÿ ðåêóðñèâíûå ôóíêöèè, ìàøèíû
Òþðèíãà, îïåðàòîðíûå ñèñòåìû Âàí-Õàî, À.À. Ëÿïóíîâà, ëîãè÷åñêèå ñõå-
ìû àëãîðèòìîâ Þ.È. ßíîâà è äð.
Êî âòîðîìó íàïðàâëåíèþ îòíîñÿòñÿ ïðåäñòàâëåíèÿ íîðìàëüíûõ àëãî-
ðèòìîâ À.À. Ìàðêîâà [17] (ïðèìåíèìûõ ê ñëîâàì â ðàçëè÷íûõ àëôàâèòàõ),
ãðàô-ñõåì, áëîê-ñõåìíûé ìåòîä àëãîðèòìèçàöèè è äð.
Íàèáîëåå óäîáíûìè ïðè êîëëåêòèâíîé ðàáîòå ÿâëÿþòñÿ àëãåáðàè÷åñ-
êèå ïðåäñòàâëåíèÿ. Ïîýòîìó òåîðèÿ êàòåãîðèé [8] èãðàåò âàæíóþ ðîëü.
Êîìïîçèöèÿ êàê îñíîâíîé ìåõàíèçì èçó÷åíèÿ êàòåãîðèé ïîçâîëÿåò ïðåä-
ñòàâëÿòü ÷èñòûå àëãîðèòìû â âèäå ìàòåìàòè÷åñêèõ êàòåãîðèé.
Àëãîðèòì âûñøåãî ïîðÿäêà — ýòî àëãîðèòì, ïðèíèìàþùèé â êà÷åñòâå
âõîäíîãî ïàðàìåòðà äðóãîé àëãîðèòì. Àíàëîãàìè òàêèõ àëãîðèòìîâ â
ôóíêöèîíàëüíûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ, íàïðèìåð Scala, ÿâëÿþòñÿ
ôóíêöèè âûñøèõ ïîðÿäêîâ (higher-ordered function, HOF)[15, 16]. Ñëåäóåò
çàìåòèòü, ÷òî àëãîðèòìîì ïåðâîãî ïîðÿäêà ÿâëÿåòñÿ àëãîðèòì, íå ïðèíè-
ìàþùèé â êà÷åñòâå ïàðàìåòðà äðóãîé àëãîðèòì.
 ðàáîòå [18] äàíî èíòóèòèâíîå îïðåäåëåíèå àëãîðèòìà è ñäåëàí
àêöåíò íà òîì, ÷òî àëãîðèòìû ñëåäóåò âñåãäà ðàññìàòðèâàòü â ñîâîêóï-
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
20 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
íîñòè ñî ñòðóêòóðàìè äàííûõ. «Àëãîðèòì ìîæíî îïðåäåëèòü, îïèñàâ ïðî-
öåäóðó ðåøåíèÿ çàäà÷è íà åñòåñòâåííîì ÿçûêå èëè â âèäå êîìïüþòåðíîé
ïðîãðàììû, êîòîðàÿ ðåàëèçóåò ïðîöåäóðó», «òåðìèí àëãîðèòì ïðèìåíÿòñÿ
â âû÷èñëèòåëüíîé òåõíèêå äëÿ îïèñàíèÿ êîíå÷íîãî, äåòåðìèíèðîâàííîãî
è ýôôåêòèâíîãî ìåòîäà ðåøåíèÿ çàäà÷è, êîòîðûé ãîäèòñÿ äëÿ ðåàëèçàöèè
â âèäå êîìïüþòåðíîé ïðîãðàììû». Èç ýòèõ èíòóèòèâíûõ îïðåäåëåíèé
ìîæíî ñäåëàòü âûâîä î òîì, ÷òî Ð. Ñåäæâèê è Ê. Óýéí [18] âûäåëÿþò ñëå-
äóþùèå ñâîéñòâà àëãîðèòìà: êîíå÷íîñòü, äåòåðìèíèðîâàííîñòü, ýôôåê-
òèâíîñòü è ìàññîâîñòü.
Ñâîþ ñèñòåìó ñâîéñòâ àëãîðèòìîâ ôîðìèðóåò À.È.Ìàëüöåâ [1]: «Àë-
ãîðèòì — ýòî ïðîöåññ ïîñëåäîâàòåëüíîãî ïîñòðîåíèÿ âåëè÷èí, èäóùèé â
äèñêðåòíîì âðåìåíè òàêèì îáðàçîì, ÷òî â íà÷àëüíûé ìîìåíò çàäàåòñÿ
èñõîäíàÿ êîíå÷íàÿ ñèñòåìà âåëè÷èí, à â êàæäûé ñëåäóþùèé ìîìåíò ñèñ-
òåìà âåëè÷èí ïîëó÷àåòñÿ ïî îïðåäåëåííîìó çàêîíó (ïðîãðàììå) èç ñèñòå-
ìû âåëè÷èí, èìåâøèõñÿ â ïðåäûäóùèé ìîìåíò âðåìåíè (äèñêðåòíîñòü
àëãîðèòìà). Ïðè ýòîì ñèñòåìà âåëè÷èí, ïîëó÷àåìûõ â êàêîé-òî (íå íà-
÷àëüíûé) ìîìåíò âðåìåíè, îäíîçíà÷íî îïðåäåëÿåòñÿ ñèñòåìîé âåëè÷èí,
ïîëó÷åííûõ â ïðåäûäóùèå ìîìåíòû âðåìåíè (äåòåðìèíèðîâàííîñòü àëãî-
ðèòìà)».
Çàêîí ïîëó÷åíèÿ ïîñëåäóþùåé ñèñòåìû âåëè÷èí èç ïðåäøåñòâóþùåé
äîëæåí áûòü ïðîñòûì è ëîêàëüíûì, ÷òî îïðåäåëÿåò åùå îäíî ñâîéñòâî
àëãîðèòìà ïî Ìàëüöåâó — ýëåìåíòàðíîñòü øàãîâ àëãîðèòìà. Îäíàêî
àâòîð [1] íå ïîÿñíÿåò, ÷òî îí ïîäðàçóìåâàåò, ãîâîðÿ î «ïðîñòîì è ëîêàëü-
íîì», îñòàâëÿÿ ýòî íà ñóä ÷èòàòåëÿ.
Ñëåäóþùåå óòâåðæäåíèå õàðàêòåðèçóåò íàïðàâëåííîñòü àëãîðèòìà:
«Åñëè ñïîñîá ïîëó÷åíèÿ ïîñëåäóþùåé âåëè÷èíû èç êàêîé-íèáóäü çàäàí-
íîé âåëè÷èíû íå äàåò ðåçóëüòàòà, òî äîëæíî áûòü óêàçàííî, ÷òî íàäî ñ÷è-
òàòü ðåçóëüòàòîì àëãîðèòìà» [1].
Àëãîðèòìû âûñøèõ ïîðÿäêîâ. Àâòîðû ðàáîòû [18] ïðèäåðæèâàþò-
ñÿ ìíåíèÿ, ÷òî «ñòðóêòóðû äàííûõ ñóùåñòâóþò êàê ïîáî÷íûå èëè êî-
íå÷íûå ïðîäóêòû àëãîðèòìîâ, è èõ èçó÷åíèå íåîáõîäèìî äëÿ ïîíèìàíèÿ
àëãîðèòìîâ». Îíè òàêæå ãîâîðÿò î òîì, ÷òî ñëåäóåò âûäåëèòü â îòäåëüíûé
êëàññ àëãîðèòìû ïåðâîãî ïîðÿäêà è àëãîðèòìû âûñøèõ ïîðÿäêîâ. Ýòî
âûòåêàåò èç ñëåäóþùåãî: «Ïðîñòûå àëãîðèòìû ìîãóò ïîòðåáîâàòü ñëîæ-
íûå ñòðóêòóðû äàííûõ, è íàîáîðîò, ñëîæíûå àëãîðèòìû ìîãóò èñïîëü-
çîâàòü ïðîñòûå ñòðóêòóðû äàííûõ» [18]. Î÷åíü âàæíî ïîíèìàòü, ÷òî åñëè
íåêîòîðûé àëãîðèòì òðåáóåò âñåãäà îäíó è òó æå ñòðóêòóðó äàííûõ, òî òà-
êîé àëãîðèòì íå ÿâëÿåòñÿ àëãîðèòìîì âûñøåãî ïîðÿäêà.  òàêîì ñëó÷àå
ñëåäóåò ãîâîðèòü î êîìïîçèöèè àëãîðèòìîâ èëè êîìïîçèöèè ìîðôèçìîâ
èëè ôóíêòîðîâ, åñëè ðå÷ü èäåò îá àëãîðèòìàõ âû÷èñëèìûõ ôóíêöèé èëè
÷èñòûõ àëãîðèòìàõ [8].
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 21
Ïðè ðàññìîòðåíèè âîïðîñà î âû-
äåëåíèè ïîðÿäêà àëãîðèòìîâ êàê îò-
äåëüíîãî êëàññèôèêàöèîííîãî ïðèçíà-
êà íàèáîëåå ÷àñòî âîçíèêàåò âîïðîñ:
ÿâëÿþòñÿ ëè àëãîðèòìû âûñøèõ ïîðÿä-
êîâ ñóïåðïîçèöèåé àëãîðèòìîâ?
Ñîãëàñíî [19] «íåôîðìàëüíîå ïî-
øàãîâîå îïðåäåëåíèå àëãîðèòìà ïîêà-
çûâàåò ÷åòûðå ñïîñîáà ñîåäèíåíèÿ àë-
ãîðèòìîâ:
1. Ïîñëåäîâàòåëüíîå ñîåäèíåíèå,
èëè ñóïåðïîçèöèÿ, êîãäà çà âûïîëíå-
íèåì øàãîâ ïåðâîãî àëãîðèòìà ñëå-
äóåò âûïîëíåíèå øàãîâ âòîðîãî àëãî-
ðèòìà è âõîäíîé èíôîðìàöèåé äëÿ
âòîðîãî àëãîðèòìà ñëóæèò âûõîäíàÿ èíôîðìàöèÿ ïåðâîãî àëãîðèòìà.
2. Êîìïîçèöèÿ, êîãäà äâà àëãîðèòìà ïàðàëëåëüíî è íåçàâèñèìî âûïîë-
íÿþò ðàáîòó íàä âõîäíîé èíôîðìàöèåé è ðåçóëüòàòîì èõ ðàáîòû ÿâëÿåòñÿ
âûõîäíàÿ èíôîðìàöèÿ îáîèõ àëãîðèòìîâ.
3. Âåòâëåíèå, êîãäà â çàâèñèìîñòè îò âûïîëíåíèÿ óñëîâèÿ äëÿ âõîä-
íîé èíôîðìàöèè, ïðîâåðÿåìîãî ïåðâûì àëãîðèòìîì, âûïîëíÿåòñÿ èëè íå
âûïîëíÿåòñÿ âòîðîé àëãîðèòì.
4. Öèêë, êîãäà ïðè ïðîâåðêå ïåðâûì àëãîðèòìîì âûïîëíåíèÿ óñëîâèÿ
äëÿ âõîäíîé èíôîðìàöèè ñîåäèíåíèÿ àëãîðèòìîâ èëè âûõîäíîé èíôîð-
ìàöèè ïðåäûäóùåãî âûïîëíåíèÿ âòîðîãî àëãîðèòìà ýòîò âòîðîé àëãîðèòì
ñíîâà âûïîëíÿåòñÿ â öèêëå èëè ïðîèñõîäèò âûõîä èç öèêëà ñ âûõîäíîé
èíôîðìàöèåé âòîðîãî àëãîðèòìà».
Ðàññìîòðèì íà ïðèìåðå çàÿâëåííûå â ðàáîòå [19] ñïîñîáû ñîåäèíåíèÿ.
Íà ðèñóíêå ïðåäñòàâëåí àëãîðèòì, ïðèíèìàþùèé íà âõîä ïàðàìåòðû
x, y è f z( ), ãäå f z( ) — àëãîðèòì îò ïàðàìåòðà z; ?z — íåêîòîðîå óñëîâèå
áèíàðíîãî âåòâëåíèÿ; ïðÿìîóãîëüíèêàìè ñ äâîéíûìè ëèíèÿìè îáîçíà-
÷åíû ïðåäîïðåäåëåííûå øàãè àëãîðèòìà. Ïðÿìîóãîëüíèêîì, âûïîëíÿþ-
ùèì ïðåîáðàçîâàíèå f z( ), îáîçíà÷åíà ðåêîíôèãóðèðóåìàÿ ÷àñòü àëãîðèò-
ìà. Î÷åâèäíî, ÷òî â äàííîì ïðèìåðå f z( ) íàõîäèòñÿ â ñóïåðïîçèöèè ïî
îòíîøåíèþ ê z, à m — â ñóïåðïîçèöèè ïî îòíîøåíèþ ê f z( ). Îäíàêî
íåâîçìîæíî ïîêàçàòü, ÷òî èçîáðàæåííûé àëãîðèòì íàõîäèòñÿ â ñóïåðïî-
çèöèè ïî îòíîøåíèþ ê f z( ), òàê æå êàê è íå ÿâëÿåòñÿ êîìïîçèöèåé, âåòâ-
ëåíèåì èëè öèêëîì.
Íîâàÿ êëàññèôèêàöèÿ. Èçëîæåííîå ïîçâîëÿåò ïðåäñòàâèòü ñâîéñòâà
àëãîðèòìà â âèäå òàáëèöû, â êîòîðîé íà ïåðåñå÷åíèè ñòðîê è ñòîëáöîâ çíàêîì
«+» îòìå÷åíî ñâîéñòâî, èçó÷àåìîå îïðåäåëåííûì àâòîðîì. Êàê âèäíî èç òàá-
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
22 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
m
m
p f z( )
�z
z
x y f z, , ( )
Ïðèìåð àëãîðèòìà âûñøåãî ïîðÿäêà
ëèöû, ëþáîé àëãîðèòì, îáëàäàþùèé ñâîéñòâàìè äèñêðåòíîñòè, ýëåìåíòàð-
íîñòè øàãîâ, ýôôåêòèâíîñòè, íàïðàâëåííîñòè, ìàññîâîñòè è ýêâèâàëåíò-
íîñòè, ìîæåò áûòü äîïîëíèòåëüíî îïðåäåëåí êàê äåòåðìèíèðîâàííûé ëèáî
ñòîõàñòè÷åñêèé; ñàìîèçìåíÿåìûé ëèáî íåñàìîèçìåíÿåìûé; ïåðâîãî ëèáî
âûñøåãî ïîðÿäêà; êîíòåêñòíîçàâèñèìûé ëèáî êîíòåêñòíîñâîáîäíûé.
×åòûðå îïðåäåëåííûõ êðèòåðèÿ äåëåíèÿ àëãîðèòìîâ íà êëàññû ôîð-
ìèðóþò íîâóþ êëàññèôèêàöèþ àëãîðèòìîâ.
Âûâîäû
Ïðåäëîæåííàÿ êëàññèôèêàöèÿ àëãîðèòìîâ, îñíîâàííàÿ íà àíàëèçå íàèáî-
ëåå èçâåñòíûõ ôóíäàìåíòàëüíûõ è ñîâðåìåííûõ ðàáîò, ïîçâîëÿåò ââåñòè
ïîíÿòèå àëãîðèòìîâ âûñøèõ ïîðÿäêîâ è êîíòåêñòíîçàâèñèìûõ àëãîðèò-
ìîâ, ïðîâîäÿ ÷åòêóþ ïàðàëëåëü ìåæäó àëãîðèòìàìè è èõ ïðåäñòàâëåíèåì
â ôóíêöèîíàëüíûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ, âîññòàíàâëèâàÿ ñîãëàñî-
âàííîñòü äâóõ òåîðèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ìàëüöåâ À.È. Àëãîðèòìû è ðåêóðñèâíûå ôóíêöèè. — Ì.: «Íàóêà», 1986. — 367 ñ.
2. Êíóò Ä.Ý. Èñêóññòâî ïðîãðàììèðîâàíèÿ. Ò. 1. Îñíîâíûå àëãîðèòìû / Ïåð.ñ àãë.: ó÷.
ïîñ., 3-å èçä., ïîä îáùåé ðåä. äîêò. ôèç.-ìàò. íàóê, ïðîô. Þ.Â. Êîçà÷åíêî. — Ì. : Èçä.
äîì «Âèëüÿìñ», 2000. — 720 ñ.
3. Êîðìåí Ò.Õ., Ëåéçåðñîí ×.È., Ðèâåñò Ð.Ë., Øòàéí Ê. Àëãîðèòìû: ïîñòðîåíèå è àíà-
ëèç. 2-e èçä. — Ì.: «Âèëüÿìñ», 2005. — 1290 ñ.
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 23
Ñâîéñòâî àëãîðèòìà
À.È. Ìàëü-
öåâ [1]
Ò.Õ. Êîðìåí
[3]
Ç.Â. Àëôå-
ðîâà [4]
Ä.Ý. Êíóò
[2]
Ð. Ñåäæâèê
[18]
Äèñêðåòíîñòü +
Äåòåðìèíèðîâàííîñòü + + +
Ýëåìåíòàðíîñòü øàãîâ +
Ñàìîèçìåíÿåìîñòü +
×èñòîòà +
Ïîðÿäîê Ðàíåå íå îïðåäåëÿëîñü
Ýôôåêòèâíîñòü + + +
Ìàññîâîñòü + +
Êîíå÷íîñòü + + +
Ýêâèâàëåíòíîñòü +
Íàïðàâëåííîñòü +
Ïðèìåíèìîñòü +
Êîððåêòíîñòü +
Êîíòåêñòíàÿ çàâèñèìîñòü Ðàíåå íå îïðåäåëÿëîñü
4. Àëôåðîâà Ç.Â. Òåîðèÿ àëãîðèòìîâ. — Ì. : Ñòàòèñòèêà, 1973. — 164 ñ.
5. Subramaniam V. Programming Scala. Tackle Multicore Complexity on Java Virtual Ma-
chine. The Progmatic Programmers. — Pragmatic Bookshelf. — Raleigh, North Carolina,
Dallas, Texas, 2008. — 218 p.
6. Ïèðñ Á. Òèïû â ÿçûêàõ ïðîãðàììèðîâàíèÿ / Ïåð. ñ àíãë. —Ì.: «Ëÿìáäà ïðåññ» &
«Äîáðîñâåò», 2012. — 655 ñ.
7. Foundational Theories of Classical and Constructive Mathematics. Åd. Giovanni Somma-
ruga. — Springer: The Western Ontario Series in Philosophy of Science, 2011. — 316 p.
8. Ìàêëåéí Ñ. Êàòåãîðèè äëÿ ðàáîòàþùåãî ìàòåìàòèêà.—Ì.: ÔÈÇÌÀÒËÈÒ, 2004.— 352 ñ.
9. Ëàôîðå Ð. Ñòðóêòóðû äàííûõ è àëãîðèòìû â Java // Êëàññèêà Computer Science. —
Ì. : Èçä-âî «Ïèòåð», 2013. — 704 ñ.
10. Ãèëüáåðò Ä., Áåðíàéñ Ï. Îñíîâàíèÿ ìàòåìàòèêè. Ëîãè÷åñêèå èñ÷èëåíèÿ è ôîðìàëè-
çàöèÿ àðèôìåòèêè. — Ì. : «Íàóêà», 1982. — 550 ñ.
11. G��îdel K. ��Uber formal unentscheidbare S��atze der Principia Mathematica und verwandter
Systeme I //Monatshefte f��ur mathematik und physik. — 1931. — Ò. 38, ¹ 1. — Ñ. 173—198.
12. Áàðåíäðåãò Õ.Ï. Ëàìáäà-èñ÷èñëåíèå. Åãî ñèíòàêñèñ è ñåìàíòèêà. — Ì. : Ìèð,
1985. — 606 ñ.
13. Kleene S.C. General recursive functions of natural numberse // Mathematische Annalen.—
1936. — 112. — P. 727—742.
14. Óñïåíñêèé Â.À. Ìàøèíà Ïîñòà. — Ì.: Íàóêà, 1979. — C. 89—95.
15. Turing A. On computable numbers, with an application to the Entscheidungs problem //
Proc. of the London Mathematical Society. Series 2. — 1936-7. — 42. — P. 230—265. —
Last access: August of 2015. — Mode of access: http://www.cs.virginia.edu/~robins/Tu-
ring_Paper_ 1936.pdf .
16. Õîðñòìàí Ê. Scala äëÿ íåòåðïåëèâûõ /Ïåð. ñ àíãë. — M.: Èçä-âî «ÄÌÊ», 2013. — 407 ñ.
17. Ìàðêîâ À.À. Òåîðèÿ àëãîðèôìîâ // Òð. Ìàòåìàòè÷. èí-òà èì. Â.À. Ñòåêëîâà. Ò. 42. —
Ì.: ÌAÈÊ «Íàóêà/Èíòåðïåðèîäèêà», 1954. — 376 ñ.
18. Ñåäæâèê Ð., Óýéí Ê. Àëãîðèòìû íà Java, 4-å èçä. — Ì. : «È.Ä. Âèëüÿìñ», 2013. — 848 ñ.
19. Ðóáëåâ Â.Ñ. Îñíîâû òåîðèè àëãîðèìîâ.— ßðîñëàâëü: ßðîñëàâñêèé ãîñ. óí-ò èì. Ï.Ã. Äå-
ìèäîâà, 2005. — 143 ñ.
H.À. Kravtsov, I.A. Prytulyuk
A NEW ALGORITHM CLASSIFICATION
The author’s classification of algorithms based on the review of famous fundamental and modern
works is presented. The author’s classification is different from already known ones due to the in-
volved terms of high order algorithms and context-related algorithms.
K e y w o r d s: classification, properties, discreteness, determinism, probability, context dependency.
REFERENCES
1. Maltsev, A. (1986), Algoritmy i rekursivnyie funktsii [Algorithms and recursive functions],
Nauka, Moscow, Russia.
2. Knut, D. (1968), Iskustvo programmirovaniya. Tom1. Osnovnyie algoritmy [The Art of
Computer Programming. Vol. 1. Fundamental Algorithms], Manual, Third Edition, trans-
lated from English by Prof. Kozachenko, Yu.V., Williams, Moscow, Russia.
3. Cormen, T.H., Leizerson, Ch.I., Rivest, R.L. and Shtain, K. (1990), Algoritmy: postroyeniye
i analiz [Algorithms: structure and analysis], Williams, Moscow, Russia.
Ã.À. Êðàâöîâ, È.À. Ïðèòóëþê
24 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 2
4. Alferova, Z.V. (1973), Teoriya algoritmov [Algorithm theory], Statistika, Moscow, Russia.
5. Subramaniam, V. (2008), Programming Scala. Tackle multicore complexity on Java virtual
machine. The pragmatic programmers, Pragmatic bookshelf, Raleigh, North Carolina, Dal-
las, Texas, USA.
6. Pirs, B. (2012), Tipy v yazykakh programmirovaniya [Types in programming languages],
Lambda Press and Dobrosvet, Moscow, Russia.
7. Foundational theories of classical and constructive mathematics (2011), Åd. by Giovanni
Sommaruga, Springer: The Western Ontario Series in Philosophy of Science, Canada.
8. Makleyn, S. (1998), Kategorii dlya rabotayushchego matematika [Categories for the work-
ing mathematician], Translated from English, Fizmatlit, Moscow, Russia.
9. Lafore, R. (2002), Struktury dannykh i algoritmy v Java [Data structures and algorithms in
Java], Piter, Moscow, Russia.
10. Gilbert, D. and Bernays, P. (1982), Osnovaniya matematiki. Logicheskie ischileniya i forma-
lizatsiya arifmetiki [Mathematics bases. Logical calculus and arithmetic formalization],
Nauka, Moscow, Russia.
11. G��îdel, K. (1931), ��Uber formal unentscheidbare S��atze der Principia Mathematica und ver-
wandter Systeme I, Monatshefte f��ur mathematik und physic, Vol. 38, no. 1, pp. 173-198.
12. Barendregt, H.P. (1985), Lambda-ischislenie. Yego sintaksis i semantika [The Lambda cal-
culus. Its syntax and semantics], Translated from English, Mir, Moscow, Russia.
13. Kleene, S.C. (1936), General recursive functions of natural numbers, Mathematische Anna-
len, Vol. 112, pp. 727-742.
14. Uspenskiy, V. (1979), Mashina Posta [Post–Turing machine], Nauka, Moscow, Russia.
15. Turing, A. (1936), On computable numbers, with an application to the Entscheidungs prob-
lem, Proc. of the London Mathematical Society, Series 2, Vol. 42, pp. 230-265, available at:
http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf ( accessed August 2015).
16. Khorstman, Ñ. (2012), Skala dlya neterpelivykh [Scala for the impatient], translated from
English, DMK, Moscow, Russia.
17. Markov, A. (1954), “Algorithm theory”, Trudyi matematich. in-ta im. V. A. Steklova, Vol. 42,
MAIK «Nauka/Interperiodika», Moscow, Russia.
18. Sedzhvik, R. and Ueyn, K. (2011), Algoritmy na Java [Algorithms in Java], Williams, Mos-
cow, Russia.
19. Rublev, V. (2005), Osnovyi teorii algorimov [Fundamentals of algorithm theory], P.G. De-
midov Yaroslavl State University, Yaroslavl, Russia.
Ïîñòóïèëà 23.02.16
ÊÐÀÂÖÎÂ Ãðèãîðèé Àëåêñååâè÷, êàíä. òåõí. íàóê, äîêòîðàíò Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â
ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû.  2000 ã. îêîí÷èë Ñåâàñòîïîëüñêèé âîåííî-ìîðñêîé
èí-ò èì. Ï.Ñ. Íàõèìîâà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — êèáåðáåçîïàñíîñòü ñìàðò-ãðèä, êðèïòî-
ãðàôèÿ, ïðîãðàììèðîâàíèå, ðàçðàáîòêà ðàñïðåäåëåííûõ ãåòåðîãåííûõ âû÷èñëèòåëüíûõ ñèñòåì.
ÏÐÈÒÓËÞÊ Èðèíà Àôàíàñüåâíà, àñïèðàíòêà Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå
èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû.  2011 ã. îêîí÷èëà Îòêðûòûé ìåæäóíàðîäíûé óíèâåðñèòåò
ðàçâèòèÿ ÷åëîâåêà «Óêðàèíà». Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìîäåëèðîâàíèå ôèíàíñîâûõ
ñèñòåì, òåîðèÿ èãð.
Íîâàÿ êëàññèôèêàöèÿ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 2 25
|
| id | nasplib_isofts_kiev_ua-123456789-101342 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-30T14:37:40Z |
| publishDate | 2016 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Кравцов, Г.А. Притулюк, И.А. 2016-06-02T17:12:55Z 2016-06-02T17:12:55Z 2016 Новая классификация алгоритмов / Г.А. Кравцов, И.А. Притулюк // Электронное моделирование. — 2016. — Т. 38, № 2. — С. 11-25. — Бібліогр.: 19 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101342 510.5 Предложена собственная классификация алгоритмов на основании обзора наиболее известных фундаментальных и современных работ. В отличие от известных классификаций введены понятия алгоритмов высших порядков и контекстнозависимых алгоритмов. Запропоновано власну класифікацію алгоритмів за результатами огляду найбільш відомих фундаментальних та сучасних робіт. На відміну від відомих класифікацій введено поняття алгоритмів вищих порядків та контекстнозалежних алгоритмів. The author’s classification of algorithms based on the review of famous fundamental and modern works is presented. The author’s classification is different from already known ones due to the involved terms of high order algorithms and context-related algorithms. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Новая классификация алгоритмов A new algorithm classification Article published earlier |
| spellingShingle | Новая классификация алгоритмов Кравцов, Г.А. Притулюк, И.А. Математическое моделирование и вычислительные методы |
| title | Новая классификация алгоритмов |
| title_alt | A new algorithm classification |
| title_full | Новая классификация алгоритмов |
| title_fullStr | Новая классификация алгоритмов |
| title_full_unstemmed | Новая классификация алгоритмов |
| title_short | Новая классификация алгоритмов |
| title_sort | новая классификация алгоритмов |
| topic | Математическое моделирование и вычислительные методы |
| topic_facet | Математическое моделирование и вычислительные методы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101342 |
| work_keys_str_mv | AT kravcovga novaâklassifikaciâalgoritmov AT pritulûkia novaâklassifikaciâalgoritmov AT kravcovga anewalgorithmclassification AT pritulûkia anewalgorithmclassification |