Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2008 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/44264 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология / Г.Е. Цейтлин // Кибернетика и системный анализ. — 2008. — № 5. — С. 151-157. — Бібліогр.: 26 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44264 |
|---|---|
| record_format |
dspace |
| spelling |
Цейтлин, Г.Е. 2013-05-27T14:48:47Z 2013-05-27T14:48:47Z 2008 Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология / Г.Е. Цейтлин // Кибернетика и системный анализ. — 2008. — № 5. — С. 151-157. — Бібліогр.: 26 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44264 519.3 ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| spellingShingle |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология Цейтлин, Г.Е. Программно-технические комплексы |
| title_short |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| title_full |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| title_fullStr |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| title_full_unstemmed |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| title_sort |
алгебро-алгоритмические аспекты полноты: абстракции, биология и экология |
| author |
Цейтлин, Г.Е. |
| author_facet |
Цейтлин, Г.Е. |
| topic |
Программно-технические комплексы |
| topic_facet |
Программно-технические комплексы |
| publishDate |
2008 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44264 |
| citation_txt |
Алгебро-алгоритмические аспекты полноты: абстракции, биология и экология / Г.Е. Цейтлин // Кибернетика и системный анализ. — 2008. — № 5. — С. 151-157. — Бібліогр.: 26 назв. — рос. |
| work_keys_str_mv |
AT ceitlinge algebroalgoritmičeskieaspektypolnotyabstrakciibiologiâiékologiâ |
| first_indexed |
2025-11-25T22:31:26Z |
| last_indexed |
2025-11-25T22:31:26Z |
| _version_ |
1850565046368731136 |
| fulltext |
ÓÄÊ 519.3
Ã.Å. ÖÅÉÒËÈÍ
ÀËÃÅÁÐÎ-ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÀÑÏÅÊÒÛ ÏÎËÍÎÒÛ:
ÀÁÑÒÐÀÊÖÈÈ, ÁÈÎËÎÃÈß È ÝÊÎËÎÃÈß
Êëþ÷åâûå ñëîâà: àëãåáðà àëãîðèòìèêè, îïåðàöèÿ ñóïåðïîçèöèè, êàíîíè÷åñêèå
ôîðìû, ôóíêöèîíàëüíàÿ è àêñèîìàòè÷åñêàÿ ïîëíîòà, ïîäàëãåáðû (çàìêíóòûå
êëàññû), ãðàììàòèêè ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ.
1. ÑÎÑÒÎßÍÈÅ ÈÑÑËÅÄÎÂÀÍÈÉ
Àêñèîìàòè÷åñêàÿ ïîëíîòà îòíîñèòñÿ ê ÷èñëó ôóíäàìåíòàëüíûõ ïðîáëåì àëãåá-
ðû è ëîãèêè. Åå çíà÷èìîñòü îïðåäåëÿåòñÿ èçâåñòíûìè òåîðåìàìè øäåëÿ [1].
Âàæíîñòü ýòèõ òåîðåì òðóäíî ïåðåîöåíèòü îñîáåííî â ýðó êîìïüþòåðíûõ âû-
÷èñëåíèé.  ýòîé ñâÿçè íåîáõîäèìî óïîìÿíóòü, íàïðèìåð, ðàáîòó [2], ãäå ìî-
äåëèðóåòñÿ äîêàçàòåëüñòâî òåîðåìû øäåëÿ î íåïîëíîòå ôîðìàëüíîé
àðèôìåòèêè ñ ïðîãðàììèñòñêèõ ïîçèöèé.
Íàñòîÿùàÿ ñòàòüÿ ïîñâÿùåíà ðàññìîòðåíèþ ïðîáëåìàòèêè àêñèîìàòè÷åñêîé
ïîëíîòû â àñïåêòå ïðåäïðèíÿòûõ íà Çàïàäå óñèëèé ïî àëãåáðàèçàöèè ñîâðåìåí-
íîãî ïðîãðàììèðîâàíèÿ [3, 4]. Ñëåäóåò îòìåòèòü, ÷òî â Óêðàèíå àëãåáðàèçàöèÿ
àëãîðèòìîâ è ïðîãðàìì ñòàëà àêòóàëüíîé, íà÷èíàÿ ñ ôóíäàìåíòàëüíûõ ðàáîò
Â.Ì. Ãëóøêîâà [5, 6] è Ë.À. Êàëóæíèíà [7].
Íà ðèñ. 1 ïîêàçàíà ñâÿçü àëãåáðû àëãîðèòìèêè
� AA > ñ àëãåáðàè÷åñêîé àëãîðèòìèêîé (AA): àëãåáðû è
ÿçûêà ïðîãðàììèðîâàíèÿ (ßÏ) ÀÄÀ [3]. Ñîïîñòàâè-
òåëüíûé àíàëèç àëãåáðàè÷åñêîé àëãîðèòìèêè (ÀÀ) ñ
àëãåáðîé àëãîðèòìèêè � AA > áûë ïðîâåäåí íà
ÓêðÏðîã-2004 [8]. Îòìåòèì, ÷òî ñðàâíåíèþ � AA >
ñ ìeíòàëüíûì ïðîãðàììèðîâàíèåì (IP) ïîñâÿùåíû
ðàáîòû [9, 10].
Äëÿ IP õàðàêòåðíà òðèàäà: àáñòðàêöèè, áèîëîãèÿ è
ýêîëîãèÿ çíàíèé (ðèñ. 2). Ïîä àáñòðàêöèÿìè â IP ïîíè-
ìàþòñÿ ôîðìóëû â ðàçëè÷íûõ àëãåáðàõ (èíûìè ñëîâà-
ìè, àíàëèòè÷åñêàÿ ôîðìà ïðåäñòàâëåíèÿ çíàíèé îá àëãîðèòìàõ).  � AA > íàðÿäó
ñ àíàëèòè÷åñêîé (â çàâèñèìîñòè îò ìåòîäîâ ïðîåêòèðîâàíèÿ) ðàññìàòðèâàþòñÿ äâå
äðóãèå ýêâèâàëåíòíûå ôîðìû — òåê-
ñòîâàÿ è ãðàôîâàÿ. Íàïðèìåð, ñ ñèñòå-
ìîé àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ)
[5], ïîëó÷èâøåé íàçâàíèå àëãåáðû
Ãëóøêîâà (ÀÃ), ñâÿçàíî òåêñòîâîå
ïðîåêòèðîâàíèå àëãîðèòìîâ â ÿçûêå
ÑÀÀ-ñõåì [11] è âèçóàëèçàöèÿ àëãî-
ðèòìîâ â òåðìèíàõ ýêâèâàëåíòíûõ
ãðàô-ñõåì [7] (áîëåå äåòàëüíî
ñì. [12]). Ñëåäóåò îòìåòèòü, ÷òî â
� AA > ôóíêöèîíàëüíàÿ ýêâèâàëåí-
òíîñòü ðàññìîòðåííûõ ôîðì ïðåäñòàâëåíèÿ àëãîðèòìîâ îáåñïå÷èâàåòñÿ
íàëè÷èåì ñîîòâåòñòâóþùèõ èíñòðóìåíòàëüíûõ ñðåäñòâ [9, 25].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 151
Ðèñ. 1. Êîíöåïöèÿ àëãåáðà-
è÷åñêîé àëãîðèòìèêè
Ðèñ. 2. Ñîïîñòàâëåíèå àëãåáðû àëãîðèòìèêè è
ìåíòàëüíîãî ïðîãðàììèðîâàíèÿ
© Ã.Å. Öåéòëèí, 2008
Ê ÷èñëó «âå÷íûõ» ïðîáëåì ïðîãðàììèðîâàíèÿ îòíîñèòñÿ îáîñíîâàíèå ïðà-
âèëüíîñòè ñêîíñòðóèðîâàííûõ àëãîðèòìîâ è ïðîãðàìì. Ýôôåêòèâíûì ñðåäñòâîì
îáîñíîâàíèÿ ïðàâèëüíîñòè ñëóæèò ïðåîáðàçîâàíèå (òðàíñôîðìàöèÿ) àëãîðèòìîâ,
à òàêæå ïðåäëîæåííûå â � AA > ôîðìàëèçîâàííûå ìåòàïðàâèëà: ñâåðòêà (óêðóï-
íåíèå), ðàçâåðòêà (äåòàëèçàöèÿ), ïåðåèíòåðïðåòàöèÿ (ñâåðòêà–ðàçâåðòêà) è
òðàíñôîðìàöèÿ ñõåì àëãîðèòìîâ.
Ê ýêîëîãèè ïðîãðàììèðîâàíèÿ îòíîñÿòñÿ èíñòðóìåíòàëüíûå ñðåäñòâà, àâòî-
ìàòèçèðóþùèå ïðèìåíåíèå ïåðå÷èñëåííûõ ìåòàïðàâèë [9, 10, 25]. Äëÿ àëãåáðû
â öåëîì è äëÿ � AA > â ÷àñòíîñòè îñîáûé èíòåðåñ ïðåäñòàâëÿåò ìåòàïðàâèëî
òðàíñôîðìàöèè â ïëàíå ïîñòðîåíèÿ àëãîðèòìîâ, óäîâëåòâîðÿþùèõ íåîáõîäè-
ìûì êðèòåðèÿì êà÷åñòâà [13, 14]. Âàæíûì äëÿ ïðîöåññà àêñèîìàòèçàöèè ëþáîé
àëãåáðû ÿâëÿåòñÿ ïîñòðîåíèå åå «çàêîíîâ»:
— ñâîéñòâ ýëåìåíòîâ, âõîäÿùèõ â îñíîâó è/èëè îñíîâû (åñëè àëãåáðà ìíî-
ãîîñíîâíàÿ);
— ñâîéñòâ îïåðàöèé, âõîäÿùèõ â ñèãíàòóðó ðàññìàòðèâàåìîé àëãåáðû.
Ïðè ýòîì õàðàêòåðíûå äëÿ ëîãèêè êîíñòðóêöèè (êâàíòîðû), èõ ñâîéñòâà, ëîãè-
÷åñêèå ïðàâèëà âûâîäà ðàñøèðÿþòñÿ çà ñ÷åò àëãîðèòìè÷åñêîé êîìïîíåíòû:
ìåòàïðàâèëà âûâîäà, ñòðóêòóðû äàííûõ è ïàìÿòè è ò.ä. Â ðåçóëüòàòå ñîçäàåò-
ñÿ àïïàðàò ëåìì è òåîðåì äëÿ îáåñïå÷åíèÿ âîçìîæíîñòè åãî ïðèëîæåíèé
â ðàçëè÷íûõ àêòóàëüíûõ ïðåäìåòíûõ îáëàñòÿõ.
Òàêèì îáðàçîì, èññëåäîâàíèå àêñèîìàòè÷åñêîé ïîëíîòû íåêîòîðîé àëãåáðû
îñóùåñòâèìî ñ ó÷åòîì âîçìîæíûõ àíàëîãèé ïî îòíîøåíèþ ê ôóíêöèîíàëüíîé
ïîëíîòå è îãðàíè÷åíèé, âûòåêàþùèõ èç óïîìÿíóòîé òåîðåìû øäåëÿ î íåïîëíî-
òå ôîðìàëüíîé àðèôìåòèêè.
Ñòðóêòóðó ñòàòüè ñîñòàâëÿþò ñëåäóþùèå ðàçäåëû. Â ðàçä. 2 ðàññìîòðåíà àë-
ãåáðà ëîãèêè, èëè êëîí Ïîñòà (ÊÏ). Ðàçä. 3 ïîñâÿùåí ëîãè÷åñêèì è àëãîðèòìè-
÷åñêèì êëîíàì, à òàêæå êëîíàì ôîðìàëüíûõ ÿçûêîâ.  ðàçä. 4 ðàññìîòðåí àëãåá-
ðî-ãðàììàòè÷åñêèé ôîðìàëèçì ãðàììàòèê ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ (îáîá-
ùàþùèé ÿçûê ÑÀÀ-ñõåì). Â ðàçä. 5 èíòåðïðåòèðóåòñÿ áèîëîãèÿ è ýêîëîãèÿ
ïðîãðàììèðîâàíèÿ.
2. ÀËÃÅÁÐÀ ËÎÃÈÊÈ È ÁÓËÅÂÛ ÔÓÍÊÖÈÈ
Îñíîâíîé îïåðàöèåé òåîðèè êëîíîâ [23], êëàññè÷åñêèì ïðèìåðîì êîòîðîé
ñëóæèò àëãåáðà ëîãèêè L( )2 , ÿâëÿåòñÿ ñóïåðïîçèöèÿ ôóíêöèé (îïåðàöèé) ðàñ-
ñìàòðèâàåìîé àëãåáðû. Äëÿ ñëó÷àÿ L( )2 òàêèìè îïåðàöèÿìè ñëóæàò áóëåâû
ôóíêöèè (ÁÔ). Èõ ñóïåðïîçèöèÿ ñóòü ïîäñòàíîâêà îäíîé ÁÔ âìåñòî
ïåðåìåííîé â äðóãóþ.
 ðàìêàõ L( )2 èçâåñòíû çíàìåíèòàÿ òåîðåìà Ïîñòà î ôóíêöèîíàëüíîé ïîëíî-
òå [6, 9, 10, 12, 13] è áàçèðóþùèéñÿ íà íåé ìåõàíèçì ïîñòðîåíèÿ ðàçëè÷íûõ àë-
ãåáð ÁÔ. Â îñíîâó èññëåäîâàíèé Ïîñòà ïîëîæåíî ïîñòðîåíèå ðåøåòêè ïîäàëãåáð
(çàìêíóòûõ êëàññîâ) L( )2 . Ìîùíîñòü ñîâîêóïíîñòè ïîäàëãåáð àëãåáðû L( )2 ñ÷åò-
íà, íî êîëè÷åñòâî ðàçëè÷íûõ òèïîâ ïîäàëãåáð êîíå÷íî.
Ïîñðåäñòâîì òåîðåìû Ïîñòà ìîãóò áûòü ïîñòðîåíû ðàçëè÷íûå àëãåáðû ÁÔ:
àëãåáðà Áóëÿ, àëãåáðà Æåãàëêèíà è äð. Äëÿ êàæäîé èç ýòèõ è ïîäîáíûõ àëãåáð,
ïðåäñòàâëÿþùèõ èíòåðåñ äëÿ ðàçëè÷íûõ ïðèëîæåíèé, íåîáõîäèìî ïîñòðîèòü åå
àêñèîìàòèêó. Íàïðèìåð, õîðîøî èçâåñòíà àêñèîìàòèêà àëãåáðû Áóëÿ, îáîáùåíèåì
êîòîðîé ñëóæèò ñèñòåìà àêñèîì áóëåâûõ àëãåáð, èìåþùàÿ ðÿä âàæíûõ ïðèëîæå-
íèé â ïðîãðàììèðîâàíèè, â ÷àñòíîñòè â ñâÿçè ñ ðàçðàáîòêîé áàç äàííûõ è çíàíèé.
Ê êëàññó áóëåâûõ àëãåáð îòíîñèòñÿ òàêæå îáùåèçâåñòíàÿ àëãåáðà ìíîæåñòâ [12].
Îñîáåííîñòü àêñèîìàòèçèðîâàííîé àëãåáðû ñîñòîèò â òîì, ÷òî åå àíàëèòè-
÷åñêèå ïðåäñòàâëåíèÿ (ôîðìóëû) ìîãóò áûòü ñâåäåíû ê êàíîíè÷åñêîìó âèäó.
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
Òàê, â àëãåáðå Áóëÿ ëþáàÿ ôîðìóëà ñâîäèìà ê ÑÄÍÔ èëè ÑÊÍÔ. Ñëåäñòâèåì
ýòîãî ôàêòà ñëóæèò ðàçðåøèìîñòü ïðîáëåìû òîæäåñòâ â ýòîé àëãåáðå. Èìåííî
äëÿ òîãî, ÷òîáû óáåäèòüñÿ â ñïðàâåäëèâîñòè òîæäåñòâà f g� ( f è g — áóëåâû
ôóíêöèè), íåîáõîäèìî åãî ëåâóþ è ïðàâóþ ÷àñòè ñâåñòè, íàïðèìåð, ê ÑÄÍÔ.
Îòñþäà ñëåäóåò è ñïîñîá ïðîâåðêè íà ïîëíîòó àêñèîìàòèêè A íåêîòîðîé àëãåá-
ðû ÁÔ: íåîáõîäèìî óáåäèòüñÿ, ÷òî âñå àêñèîìû, âõîäÿùèå â A, íå ïðèíàäëåæàò
íè îäíîé èç ìàêñèìàëüíûõ ïîäàëãåáð òåîðåìû Ïîñòà.
3. ÏÎËÓÃÐÓÏÏÎÂÛÅ ÊËÎÍÛ È ÏÐÈËÎÆÅÍÈß
(ÏÀÐÀÄÈÃÌÀ ÊËÎÍÀ ÃËÓØÊÎÂÀ)
Ðàññìîòðèì ïîëóãðóïïîâûå êëîíû, èõ îòëè÷èå è ñâÿçü ñ ÊÏ. Êàê è â [22],
ëèíãâèñòè÷åñêàÿ äåäóêòèâíàÿ òåîðèÿ T L/ ñ àëôàâèòîì L a a ak� 1 2, , . . . , ñî-
ñòîèò èç áóêâ ai , ãäå i k�1 2, , . . . , ; T L/ 1 — ýëåìåíòàðíàÿ ñëîâàðíàÿ òåîðèÿ ñ îä-
íîáóêâåííûì àëôàâèòîì L a1 � . Çäåñü ìû íàçîâåì ñëîâàðíîé ïîëóãðóïïîâîé àë-
ãåáðîé ýëåìåíòàðíóþ òåîðèþ T L/ 1 ñ îïåðàöèåé óìíîæåíèÿ (êîíêàòåíàöèè) ñëîâ
s s s s1 2 1 2* � . Íàïðèìåð, åñëè s aa1 � è s aaa2 � , òî s s aaaaa1 2* � .
Íà îñíîâå ýëåìåíòàðíîé ïîëóãðóïïîâîé àëãåáðû ñ îïåðàöèåé * ïîñòðîèì
ýëåìåíòàðíûé ïîëóãðóïïîâîé êëîí C T L T L( / ) / ;1 1� � SUPER >. Ðàññìîòðèì
ìíîæåñòâî ñëîâ M P S P/ /� , äëèíû êîòîðûõ ñóòü ïðîñòûå ÷èñëà. Ïóñòü A —
ýëåìåíòàðíàÿ ïîëóãðóïïîâàÿ àëãåáðà ñ îïåðàöèåé * è
C T L T L( / ) / ;1 1�� SUPER > — ýëåìåíòàðíûé ïîëóãðóïïîâîé êëîí. Îòìåòèì,
÷òî ìíîæåñòâî âñåõ ïîäìíîæåñòâ ñ÷åòíîãî ìíîæåñòâà èìååò ìîùíîñòü
êîíòèíóóìà. Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 1. Ìíîæåñòâî M P/ ÿâëÿåòñÿ ñèñòåìîé îáðàçóþùèõ (ÑÎ) êëîíà
C T L( / )1 .
Ïðåäñòàâèòåëüíîé íàçîâåì ýëåìåíòàðíóþ ïîëóãðóïïîâóþ àëãåáðó A (ñ îïå-
ðàöèåé *), ïî êîòîðîé ñòðîèòñÿ êëîí C A/ .
Ñëåäñòâèå. Êëîí C A A/ ;�� SUPER > ÿâëÿåòñÿ êëîíîì êîíòèíóàëüíîãî
òèïà, ãäå A — ïðåäñòàâèòåëüíàÿ àëãåáðà.
Ïðèâåäåì ïîñòðîåííûå â [5] ïàðû (ðèñ. 3): ïðåäñòàâèòåëüíàÿ àëãåáðà è ñîîò-
âåòñòâóþùèé åé àëãîðèòìè÷åñêèé êëîí. Êàæäîé ïàðå ñîîòâåòñòâóåò îïðåäåëåí-
íûé ìåòîä è òåõíîëîãèÿ ïðîãðàììèðîâàíèÿ.
Ñòðóêòóðíîå ïðîãðàììèðîâàíèå: àëãåáðà Äåéêñòðû (ÀÄ) — êëîí Äåéêñòðû
(ÊÄ); ñèñòåìû àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ) Ãëóøêîâà — êëîí Ãëóøêîâà (ÊÃ).
Íåñòðóêòóðíîå ïðîãðàììèðîâàíèå: àëãåáðà ßíîâà (Àß) — êëîí ßíîâà (Êß).
Âèçóàëüíîå ïðîãðàììèðîâàíèå: àëãåáðà ãðàô-ñõåì Êàëóæíèíà (ÀÊ) — êëîí
Êàëóæíèíà (ÊëÊ) (îáîáùåííûå ÀÊ (ÎÀÊ) — ÊëÊ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 153
Ðèñ. 3. Êëàññèôèêàöèÿ êëîíîâ
Ïðîêîììåíòèðóåì ïðèâåäåííûå ïàðû. Êàæäàÿ ïðåäñòàâèòåëüíàÿ àëãåáðà ÿâ-
ëÿåòñÿ äâóõîñíîâíîé. Ëîãè÷åñêàÿ îñíîâà ñîñòîèò èç áóëåâûõ îïåðàöèé è îïåðàöèè
ïðîãíîçèðîâàíèÿ (íàëè÷èå ïàìÿòè) â ñëó÷àå ÑÀÀ [6]. Òàêèì îáðàçîì, ÊÄ, ÊëÊ è
Êß â êà÷åñòâå ëîãè÷åñêîé êîìïîíåíòû èìåþò ÊÏ. Ïðîáëåìà ôóíêöèîíàëüíîé ïî-
ëíîòû äëÿ ïåðå÷èñëåííûõ êëîíîâ ðåøåíà â [6] ñ ó÷åòîì íàëè÷èÿ îïåðàöèè ïðîãíî-
çèðîâàíèÿ â ÊÃ, ÷òî è îáúÿñíÿåò èçîáðàçèòåëüíóþ ìîùíîñòü ÑÀÀ è ÊÃ â ñðàâíå-
íèè ñ äðóãèìè êëîíàìè. Îòìåòèì âîçìîæíîñòü ïåðåõîäà ê k-çíà÷íûì ëîãèêàì â
ÑÀÀ, ÷òî âàæíî äëÿ ìíîãîçíà÷íûõ ñðåäñòâ ïðåäñòàâëåíèÿ çíàíèé (íåîïðåäåëåí-
íîñòü, òàáëèöû ðåøåíèé è ïð.). Â [5] ðàññìîòðåí òàêæå ïîëóãðóïïîâîé êëîí Êëè-
íè, îòíîñÿùèéñÿ ê êëîíàì ôîðìàëüíûõ ÿçûêîâ è ãðàììàòèê.
4. ÇÀÌÊÍÓÒÎÑÒÜ ÓÑËÎÂÈÉ. ÑÒÀÍÄÀÐÒÍÛÅ ÏÀÐÀËËÅËÜÍÛÅ ÏÎËÈÍÎÌÛ
 [14] ïîñòðîåíà àêñèîìàòèêà äëÿ ÑÀÀ, áàçèðóþùèõñÿ íà ïîíÿòèè çàìêíóòûõ
óñëîâèé (àäåêâàòíîé ïðåäëîæåííîé À.À. Ëåòè÷åâñêèì êîíöåïöèè ìîíîòîííîãî
îïåðàòîðà [15]). Ñóòü ïîíÿòèÿ çàìêíóòîãî óñëîâèÿ ñîñòîèò â òîì, ÷òî, ñòàâ èñ-
òèííûì, îíî ñîõðàíÿåòñÿ âïëîòü äî îêîí÷àíèÿ âû÷èñëèòåëüíîãî ïðîöåññà (íå-
çàâèñèìî îò ñîñòîÿíèÿ îáðàáàòûâàåìûõ äàííûõ) ââèäó ïðèìåíåíèÿ îïåðàòî-
ðîâ, âîçìîæíî, âëèÿþùèõ íà òàêîå ñîñòîÿíèå. Â ýòîì ñìûñëå çàìêíóòûå
óñëîâèÿ ôèêñèðóþò íåêîòîðûå âåõè, õàðàêòåðèçóþùèå ïðîöåññ âû÷èñëåíèé.
Íàïðèìåð, åñëè ðå÷ü èäåò î ñåìåéñòâå çàäà÷ â ñìåñè íåêîòîðîé îïåðàöèîí-
íîé ñèñòåìû, òî ôàêò ðåøåíèÿ îäíîé èç ýòèõ çàäà÷ ìîæíî ñ÷èòàòü îêîí÷àòåëü-
íûì íåçàâèñèìî îò ñîñòîÿíèÿ äðóãèõ çàäà÷ â ðàññìàòðèâàåìîé ñìåñè. Çàìêíó-
òîñòü âåñüìà âàæíà äëÿ îðãàíèçàöèè âçàèìîäåéñòâèÿ ïàðàëëåëüíûõ âåòâåé ïðè
àñèíõðîííîé (ðàñïðåäåëåííîé) îáðàáîòêå äàííûõ. Ñ ýòîé öåëüþ â àïïàðàò ÑÀÀ
áûëè ââåäåíû:
— ñèíõðîíèçàòîðû, îáåñïå÷èâàþùèå îæèäàíèå âûïîëíåíèÿ çàìêíóòûõ
óñëîâèé ïî ïàðàëëåëüíûì âåòâÿì;
— êîíòðîëüíûå òî÷êè (ÊÒ), â êîòîðûõ îñóùåñòâëÿþòñÿ ïðîâåðêè çíà÷åíèé
óêàçàííûõ óñëîâèé;
— ôèëüòðû �(u ), â òåðìèíàõ êîòîðûõ îïèñàíû ñâîéñòâà ðÿäà îïåðàöèé,
âõîäÿùèõ â ñèãíàòóðû àëãîðèòìè÷åñêèõ àëãåáð.
Ïðåäëîæåííàÿ àêñèîìàòèêà ÿâëÿåòñÿ ïîëíîé. Òàêèì îáðàçîì, ñïðîåêòèðî-
âàííûé ïàðàëëåëüíûé àëãîðèòì â ðåçóëüòàòå ïðåîáðàçîâàíèé, áàçèðóþùèõñÿ íà
ðàçðàáîòàííîé àêñèîìàòèêå, ñâîäèì ê êàíîíè÷åñêîé ôîðìå — ñòàíäàðòíîìó
ïàðàëëåëüíîìó ïîëèíîìó (ÑÏÏ).
Òàêèì îáðàçîì, åñëè èìååòñÿ ãèïîòåçà â âèäå ðàâåíñòâà f g� , òî, ïðåîáðàçî-
âàâ ëåâóþ è ïðàâóþ ÷àñòè äàííîãî ðàâåíñòâà ê ÑÏÏ (â ñëó÷àå ñîâïàäåíèÿ — ñ
òî÷íîñòüþ äî ïåðåñòàíîâêè ïàðàëëåëüíûõ âåòâåé), ïîëó÷èì äîêàçàòåëüñòâî
ñïðàâåäëèâîñòè óêàçàííîé ãèïîòåçû.
Åñòåñòâåííûì îáîáùåíèåì ïîíÿòèÿ çàìêíóòîãî óñëîâèÿ ñëóæèò êâàçèçàì-
êíóòîñòü, ñóòü êîòîðîé ñîñòîèò â äîïóùåíèè âîçìîæíîñòè ñáðàñûâàíèÿ çíà÷åíèÿ
èñòèíû íà ëîæü ïðè ïîâòîðíîì âû÷èñëåíèè î÷åðåäíîãî âèòêà öèêëà. Êàê èçâåñ-
òíî, îñíîâíîé îáúåì âû÷èñëåíèé ñîñðåäîòî÷åí ïðè âûïîëíåíèè öèêëîâ — îòñþ-
äà è ñëîæíîñòü èõ ðàñïàðàëëåëèâàíèÿ. Ñ ïîíÿòèåì êâàçèçàìêíóòîñòè ñâÿçàíà èå-
ðàðõèÿ âëîæåííûõ öèêëîâ, êîãäà ïðè âû÷èñëåíèè òåëà îñíîâíîãî öèêëà åãî
óñëîâèå, ñòàâ îäíàæäû èñòèííûì, óæå íå ìåíÿåò ýòîãî çíà÷åíèÿ äî î÷åðåäíîãî
âèòêà îñíîâíîãî öèêëà.
Ýòî îòíîñèòñÿ è ê öèêëàì, âëîæåííûì â îñíîâíîé öèêë. Ïðè ýòîì íåêîòî-
ðûå öèêëè÷åñêèå óñëîâèÿ ñâÿçàíû èìïëèêàöèÿìè, îïðåäåëÿþùèìè èåðàðõèþ
óïðàâëåíèÿ âû÷èñëåíèé îñíîâíîãî öèêëà [19].
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
5. ÃÐÀÌÌÀÒÈÊÈ ÑÒÐÓÊÒÓÐÍÎÃÎ ÏÐÎÅÊÒÈÐÎÂÀÍÈß.
ÌÀÊÐÎÊÎÍÒÅÉÍÅÐÛ
 ðàìêàõ � AA > ïðåäëîæåíû áàçèðóþùèåñÿ íà àïïàðàòå Àà ôîðìàëèçîâàííûå
ñðåäñòâà ïðîåêòèðîâàíèÿ è ñèíòåçà àëãîðèòìîâ è ïðîãðàìì.
Ïîñòðîåííûé ôîðìàëèçì ñîïðÿæåí ñ ïðèìåíåíèåì ïîäñòàíîâîê âèäà
ÑÈÄ :: = ñïåöèôèêàöèÿ, (1)
ãäå ÑÈÄ — èìÿ ñåìàíòè÷åñêîãî èäåíòèôèêàòîðà (îïåðàòîðà èëè ïðåäèêàòà),
ïîäëåæàùåãî ñïåöèôèêàöèè â Àà — ïðàâîé ÷àñòè ïîäñòàíîâêè (1).
1. Ïàðàëëåëüíûå âû÷èñëåíèÿ. Ìàòðè÷íàÿ ìóëüòèîáðàáîòêà. Ðàññìîòðèì
ìåòîä ñèíòåçà àëãîðèòìîâ è ïðîãðàìì â � AA >, áàçèðóþùèéñÿ íà ñî÷åòàíèè àïïà-
ðàòà � AA > ñ ìåõàíèçìàìè óïðàâëåíèÿ âûâîäîì, êîòîðûå õàðàêòåðíû äëÿ òåîðèè
ôîðìàëüíûõ ãðàììàòèê [18]. Ïðåäëàãàåìûå ñèñòåìû áûëè íàçâàíû ãðàììàòèêàìè
ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ (ÃÑÏ). Ïðîöåññ ïðîåêòèðîâàíèÿ â ÃÑÏ áàçèðóåòñÿ íà
ïðèìåíåíèè ïîäñòàíîâîê âèäà (1) ñ öåëüþ äåòàëèçàöèè èëè óêðóïíåíèÿ ñõåì â ðàì-
êàõ íèñõîäÿùåé, âîñõîäÿùåé èëè êîìáèíèðîâàííîé ñòðàòåãèè ïðîåêòèðîâàíèÿ.
Ïîä ÃÑÏ ïîíèìàåòñÿ èíòåãðèðîâàííûé àëãåáðî-ãðàììàòè÷åñêèé àïïàðàò, ñî-
÷åòàþùèé îïðåäåëåííóþ àëãåáðó àëãîðèòìîâ è ñîîòâåòñòâóþùèé êëàññ ãðàììà-
òèê. Íàñòðîéêà íà íåîáõîäèìóþ ïðåäìåòíóþ îáëàñòü îñóùåñòâëÿåòñÿ ïîñðåäñòâîì
êîíòåéíåðîâ — ñåìàíòè÷åñêèõ èäåíòèôèêàòîðîâ, îïðåäåëÿþùèõ ýëåìåíòàðíûå
ïðåäèêàòû è îïåðàòîðû, íà áàçå êîòîðûõ îñóùåñòâëÿåòñÿ ñèíòåç ïðîãðàìì.
Ñëåäóåò îòìåòèòü, ÷òî ïðè íåîáõîäèìîñòè ìîãóò áûòü èñïîëüçîâàíû è ìàêðî-
êîíòåéíåðû, êîòîðûå, â ñâîþ î÷åðåäü, ìîãóò áûòü äîñòàòî÷íî êðóïíûìè àëãîðèò-
ìàìè, âõîäÿùèìè â ñîñòàâ ïðîåêòèðóåìîãî àëãîðèòìè÷åñêîãî êîìïëåêñà. Íàïðè-
ìåð, â êà÷åñòâå ìàêðîêîíòåéíåðà ìîæåò áûòü èñïîëüçîâàí òàêîé àäàïòèâíûé àëãî-
ðèòì Äåéêñòðû, êàê ×ÅËÍÎÊ (èëè ïðÿìûå âñòàâêè â òåðìèíîëîãèè Êíóòà [20]).
ÃÑÏ ñîäåðæèò ñèñòåìó îáîáùåííûõ ïðîäóêöèé, êàæäàÿ èç êîòîðûõ ñóòü êî-
íå÷íàÿ ñîâîêóïíîñòü ïîäñòàíîâîê, èìåþùèõ, êàê ïðàâèëî, ëåâóþ è ïðàâóþ ÷àñ-
òè. Ïîäñòàíîâêè â îáîáùåííûõ ïðîäóêöèÿõ ìîãóò âûïîëíÿòüñÿ ïîñëåäîâàòåëüíî
èëè ïàðàëëåëüíî.  ñâîþ î÷åðåäü, ñàìè îáîáùåííûå ïðîäóêöèè ìîãóò òàêæå
ïðèìåíÿòüñÿ â óêàçàííûõ ðåæèìàõ ê óæå ïîëó÷åííûì ñòðîêàì âûâîäà. ÃÑÏ
ïðåäñòàâèìû â ìàòðè÷íîé ôîðìå, ãäå ñòðîêè — îáîáùåííûå ïðîäóêöèè, ñòîë-
áöû — ïîäñòàíîâêè.  ÷àñòíîñòè, ìàòðèöàìè ïðåäñòàâèìû òðàäèöèîííûå
ôîðìàëüíûå ÿçûêè è ãðàììàòèêè, íàïðèìåð â êëàññèôèêàöèè Õîìñêîãî [18].
 [21] ïîñòðîåíû ìàòðè÷íûå ÃÑÏ, ïîðîæäàþùèå êëàññû àñèíõðîííûõ ñõåì
àëãîðèòìîâ ñèìâîëüíîé ìóëüòèîáðàáîòêè: ñîðòèðîâêè, ïîèñê, ÿçûêîâîå ïðîöåñ-
ñèðîâàíèå [10, 12]. Ïîðîæäåíèå ôîðìàëüíûõ ÿçûêîâ ïîñðåäñòâîì ãðàììàòè÷åñ-
êèõ ìîäåëåé ñîïðÿæåíî ñ ïîñòðîåíèåì ïîëóãðóïïîâûõ êëîíîâ (áîëåå ïîäðîáíî
ñì. [13, 23]).
2. Ìåòàïðàâèëà âûâîäà ñõåì àëãîðèòìîâ. Ïðîåêòèðîâàíèå àëãîðèòìîâ â
ÃÑÏ ñâÿçàíî ñ ïðèìåíåíèåì ìåòàïðàâèë êîíñòðóèðîâàíèÿ ñõåì àëãîðèòìîâ
(ñâåðòêè, ðàçâåðòêè, ïåðåèíòåðïðåòàöèè, òðàíñôîðìàöèè è äð. [10, 12]). Ñ ïî-
ìîùüþ ìåòàïðàâèë îñóùåñòâëÿåòñÿ ïåðåõîä îò îäíèõ àëãîðèòìîâ ê äðóãèì, à
òàêæå ïîðîæäåíèå íîâûõ àëãîðèòìè÷åñêèõ çíàíèé â ðàññìàòðèâàåìîé
ïðåäìåòíîé îáëàñòè.
Äëÿ àëãåáðàè÷åñêîãî ïîäõîäà áîëüøîå çíà÷åíèå èìååò ïðèìåíåíèå ìåòàïðà-
âèëà òðàíñôîðìàöèè — ïðåîáðàçîâàíèÿ ñõåì ïóòåì ïðèìåíåíèÿ ñîîòíîøåíèé. Â
êàæäîì ñîîòíîøåíèè ëåâàÿ è ïðàâàÿ ÷àñòè îòðàæàþò ñâîéñòâà îïåðàöèé, âõîäÿ-
ùèõ â ñèãíàòóðó ðàññìàòðèâàåìîé àëãåáðû. Îòìåòèì âàæíîñòü òåîðèè êëîíîâ,
êëàññèôèêàöèÿ êîòîðûõ áûëà ïðîâåäåíà â [23] ñ èñïîëüçîâàíèåì ïîíÿòèÿ
ïðåäñòàâëÿþùåé àëãåáðû, âîñõîäÿùåé ê èçâåñòíîé ñòàòüå À. Óñïåíñêîãî [22].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 155
6. ÝÊÎËÎÃÈß ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß (ÈÍÑÒÐÓÌÅÍÒÀËÜÍÛÅ ÑÐÅÄÑÒÂÀ)
 [10, 23] ðàçðàáîòàí èíòåãðèðîâàííûé èíñòðóìåíòàðèé ïðîåêòèðîâàíèÿ è
ñèíòåçà (ÈÏÑ) àëãîðèòìîâ è ïðîãðàìì. Äàííûé èíñòðóìåíòàðèé âîñõîäèò ê
ñèíòåçàòîðó ÌÓËÜÒÈÏÐÎÖÅÑÑÈÑÒ [6, 11, 12] — îäíîé èç ïåðâûõ óêðàèí-
ñêèõ CASE-ñèñòåì, îðèåíòèðîâàííîé íà ãåíåðàöèþ ïðîãðàìì. Ñèñòåìà òàêæå
ìîæåò áûòü îòíåñåíà ê ïðîòîòèïó ìåíòàëüíîãî ïðîãðàììèðîâàíèÿ. Â åå îñíî-
âó ïîëîæåí ìåòîä ìíîãîóðîâíåâîãî ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ ïðîãðàìì
ïî èõ îïèñàíèÿì â ÿçûêå ÑÀÀ/1.
Âàæíî îòìåòèòü, ÷òî àëãåáðàè÷åñêèå ñðåäñòâà ïðîåêòèðîâàíèÿ àëãîðèòìîâ è
ñòðóêòóð äàííûõ ñîîòâåòñòâóþò ïðèíÿòîìó â îáúåêòíî-îðèåíòèðîâàííûõ ñðåäàõ
ìåòîäó êîíñòðóèðîâàíèÿ îáúåêòîâ â òåðìèíàõ øàáëîíîâ. Ïðè ýòîì ïîóðîâíåâîå
ïðèñâîåíèå ëîãè÷åñêèì è îïåðàòîðíûì ïåðåìåííûì èõ èíòåðïðåòàöèé ñóòü
çàïîëíåíèå ïîëåé øàáëîíîâ â ðàìêàõ îáúåêòíûõ ñðåä.
Ñëåäóåò òàêæå îòìåòèòü âîçìîæíîñòü èñïîëüçîâàíèÿ àëãåáðàè÷åñêèõ ïðåîá-
ðàçîâàíèé ñõåì íà îñíîâå ñâîéñòâ àëãåáðàè÷åñêèõ îïåðàöèé, âõîäÿùèõ â ôîðìó-
ëû, ïðåäñòàâëÿþùèå ïðîåêòèðóåìûå îáúåêòû.
Òàêèì îáðàçîì, ê ÷èñëó âàæíûõ îòêðûòûõ ïðîáëåì <ÀÀ> îòíîñÿòñÿ ñëåäóþùèå.
1. Ïîñòðîåíèå ïîâåðõíîñòè êëîíîâ êîíòèíóàëüíîãî òèïà è èññëåäîâàíèå ïî-
ãðàíè÷íîé çîíû, îãðàíè÷èâàþùåé äàííóþ ïîâåðõíîñòü.
2. Ñîçäàíèå ýôôåêòèâíûõ àëãåáðî-ãðàììàòè÷åñêèõ ñèñòåì, îðèåíòèðîâàííûõ
íà ñòðóêòóðíîå ïðîåêòèðîâàíèå è äðóãèå ìåòîäû îïèñàíèÿ àëãîðèòìîâ è ïðîãðàìì,
âêëþ÷àÿ ìóëüòèîáðàáîòêó â ñîâðåìåííûõ âû÷èñëèòåëüíûõ ñðåäàõ.
3. Ñîçäàíèå äëÿ àêòóàëüíûõ ïðåäìåòíûõ îáëàñòåé ñîîòâåòñòâóþùèõ áàç çíà-
íèé è ýôôåêòèâíûõ àëãîðèòìîâ ïîèñêà â óêàçàííûõ áàçàõ.
4. Ðàçâèòèå àðõèòåêòóðû èíñòðóìåíòàðèÿ ïðîåêòèðîâàíèÿ è ñèíòåçà àëãî-
ðèòìîâ è ïðîãðàìì ñ ó÷åòîì ñïåöèôèêè ñîçäàâàåìûõ àêòóàëüíûõ ïðåäìåòíûõ
îáëàñòåé.
5. Àäàïòàöèÿ ðàçâèâàåìûõ òåîðåòè÷åñêèõ è ïðèêëàäíûõ ñðåäñòâ äëÿ âàæíîé
ãóìàíèòàðíîé ñôåðû ê ãðóïïàì ëèö ñ ðàçëè÷íûìè ôèçè÷åñêèìè îãðàíè÷åíèÿìè,
âêëþ÷àÿ è íàèáîëåå óÿçâèìûå èõ êàòåãîðèè (â ÷àñòíîñòè, ñ ïðîáëåìàìè çðåíèÿ).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Í î â è ê î â Ï . Ñ . Ýëåìåíòû ìàòåìàòè÷åñêîé ëîãèêè. — Ì.: Íàóêà, 1973. — 400 ñ.
2. Ã ë ó ø ê î â Â . Ì . Òåîðåìà î íåïîëíîòå ôîðìàëüíûõ òåîðèé ñ ïîçèöèé ïðîãðàììèñòà //
Êèáåðíåòèêà. — 1979. — ¹ 2. — Ñ. 1–5.
3. Í î ä å í Ï . , Ê è ò ò å Ê . Àëãåáðàè÷åñêàÿ àëãîðèòìèêà. — Ì.: Ìèð, 1999. — 720 ñ.
4. × à ð í å ö ê è Ê . , À é ç å í å ê å ð Ó . Ïîðîæäàþùåå ïðîãðàììèðîâàíèå: ìåòîäû,
èíñòðóìåíòû, ïðèìåíåíèå. Äëÿ ïðîôåññèîíàëîâ. — ÑÏá.: Ïèòåð, 2005. — 731 ñ.
5. Ã ë ó ø ê î â Â . Ì . Òåîðèÿ àâòîìàòîâ è ôîðìàëüíûå ïðåîáðàçîâàíèÿ ìèêðîïðîãðàìì //
Êèáåðíåòèêà. — 1965. — ¹ 5. — C. 1–10.
6. Ã ë ó ø ê î â Â . Ì . , Ö å é ò ë è í Ã . Å . , Þ ù å í ê î Å . Ë . Àëãåáðà. ßçûêè.
Ïðîãðàììèðîâàíèå. — Ê.: Íàóê. äóìêà. — 1-å èçä., 1974. — 327 ñ.; 2-å èçä., ïåðåðàá., 1978. —
318 ñ.; 3-å èçä., ïåðåðàá. è äîï., 1989. — 376 ñ.
7. Ê à ë ó æ í è í Ë . À . Îá àëãîðèòìèçàöèè ìàòåìàòè÷åñêèõ çàäà÷ // Ïðîáë. êèáåðíåòèêè. —
1959. — Âûï. 2 — Ñ. 51–69.
8. Ö å é ò ë è í à . Å . , Ì î õ í è ö à À . Ñ . ×òî òàêîå àëãåáðàè÷åñêàÿ àëãîðèòìèêà? // Ïðîáë.
ïðîãðàììèðîâàíèÿ. Ñïåöâûïóñê ïî ìàòåðèàëàì 4-é Ìåæäóíàð. íàó÷.-ïðàêò. êîíô. ïî
ïðîãðàììèðîâàíèþ ÓêðÏÐÎÃ’2004. — Ê.: ÈÏÑ ÍÀÍ Óêðàèíû, 2004. — ¹ 2–3. — Ñ. 52–57.
9. Ä î ð î ø å í ê î À . Å . , Ç à õ à ð è ÿ Ë . Ì . , Ö å é ò ë è í à . Å . Àëãåáðàè÷åñêîå
ïðîåêòèðîâàíèå ïðîãðàìì: àëãîðèòìû, îáúåêòû, èíñòðóìåíòû // Ïðîáëåìû
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5
ïðîãðàììèðîâàíèÿ. — 2007. — ¹ 2. — Ñ. 5–14.
10. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í Ã . Å . , ß ö å í ê î Å . À .
Àëãåáðîàëãîðèòìè÷åñêèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Ê.:
Àêàäåìïåðèîäèêà, 2007. — 634 ñ.
11. Ã ð è ö à é Â . Ï . , Ö å é ò ë è í Ã . Å . Íåêîòîðûå âîïðîñû àâòîìàòèçàöèè ñòðóêòóðíîãî
ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ // Êèáåðíåòèêà. — 1979. — ¹ 1. — Ñ. 106–111.
12. Ö å é ò ë è í Ã . Å . Ââåäåíèå â àëãîðèòìèêó — Ê.: Ñôåðà, 1999. — 720 ñ.
13. S z e n d r e i A . Clones in universal algebra, seminaire de mathematiques superieures. Vol. 99. —
Montreal: Les Presses de l’Universite de Montreal, 1986.
14. Ö å é ò ë è í Ã . Å . Ïðîáëåìà òîæäåñòâåííûõ ïðåîáðàçîâàíèé ñõåì ñòðóêòóðèðîâàííûõ
ïðîãðàìì ñ çàìêíóòûìè ëîãè÷åñêèìè óñëîâèÿìè. ×. 1–3 // Êèáåðíåòèêà. — 1978. — ¹ 3. —
Ñ. 50–57; ¹ 4. — Ñ. 10–18; 1979. — ¹ 5. — Ñ. 44–51.
15. Ë å ò è ÷ å â ñ ê è é À . À . Îá óñêîðåíèè èòåðàöèé ìîíîòîííûõ îïåðàòîðîâ // Êèáåðíåòèêà. —
1976. — ¹ 4. — Ñ. 1–7.
16. Ö å é ò ë è í Ã . Å . Ôîðìàëüíàÿ òðàíñôîðìàöèÿ ñòðóêòóðèðîâàííûõ àëãîðèòìîâ ñîðòèðîâêè //
Ïðîãðàììèðîâàíèå. — 1985. — ¹ 2. — Ñ. 79–91.
17. Ö å é ò ë è í Ã . Å . Ïðîåêòèðîâàíèå àëãîðèòìîâ ïàðàëëåëüíîé ñîðòèðîâêè // Òàì æå. — 1989.
— ¹ 6. — Ñ. 4–19.
18. C h o m s k y N . Formal properties of grammars // In «Handbook of Mathematical Psychology». —
1963. — 2. — New York: Wiley. — P. 323–418.
19. Ö å é ò ë è í Ã . Å . Òðàíñôîðìàöèîííàÿ ñâîäèìîñòü è ñèíòåç àëãîðèòìîâ è ïðîãðàìì
ñèìâîëüíîé îáðàáîòêè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 165–174.
20. Ê í ó ò Ä . Èñêóññòâî ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ, ò.3. — Ì.: Ìèð, 1978. — 843 ñ.
21. Ö å é ò ë è í Ã . Å . Àëãîðèòìû ñèìâîëüíîé îáðàáîòêè: îáúåêòíàÿ îðèåíòàöèÿ,
òðàíñôîðìàöèÿ, ñèíòåç // Ñìåøàííûå âû÷èñëåíèÿ è ïðåîáðàçîâàíèå ïðîãðàìì. —
Íîâîñèáèðñê: ÂÖ ÑÎ ÀÍ ÑÑÑÐ, 1991. — Ñ. 182–199.
22. U s p e n s k y A . G��odel’s incompleteness theorem / Theoretical Computer Science. — 1994.—
130, N 2. — Ð. 239–319.
23. Ö å é ò ë è í Ã . Å . Àëãåáðà Ãëóøêîâà è òåîðèÿ êëîíîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç.
— 2003. — ¹ 4 — Ñ. 48–58.
24. D o r o s h e n k o A . , T s e y t l i n G . , Y a t s e n k o O . , Z a c h a r i y a L . Intentional aspects
of algebra of algorithmics. — Proceedings of International Workshop «Concurrency, Specification
and Programming» (CS&P’2007), 27–29 September 2007, Lagow (Poland). — 2007.
25. ß ö å í ê î Å . À . , Ì î õ í è ö à À . Ñ . Èíñòðóìåíòàëüíûå ñðåäñòâà êîíñòðóèðîâàíèÿ
ñèíòàêñè÷åñêè ïðàâèëüíûõ ïàðàëëåëüíûõ àëãîðèòìîâ è ïðîãðàìì // Ïðîáë.
ïðîãðàììèðîâàíèÿ. Ñïåöâûïóñê ïî ìàòåðèàëàì 4-é Ìåæäóíàð. íàó÷.-ïðàêò. êîíô. ïî
ïðîãðàììèðîâàíèþ ÓêðÏÐÎÃ’2004. — 2004. — ¹ 2–3. — Ñ. 444–450.
26. Ê à ï è ò î í î â à Þ . Â . , Ë å ò è ÷ å â ñ ê è é À . À . Ïàðàäèãìû è èäåè àêàäåìèêà
Â.Ì. Ãëóøêîâà. — Ê.: Íàóê. äóìêà, 2003. — 330 ñ.
Ïîñòóïèëà 14.01.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 5 157
|