118
Îãëàâëåíèå
1. ÊÈÁÅÐÍÅÒÈÊÀ ÍÀÓÊÀ ÎÁ ÓÏÐÀÂËÅÍÈÈ ......................................... 3
1.1. Ñîçäàíèå êèáåðíåòèêè ................................................................ 3
1.2. Ïðåäìåò è ìåòîäû èññëåäîâàíèÿ êèáåðíåòèêè........................ 4
2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÀËÃÎÐÈÒÌÎÂ .................................................. 6
2.1. Îïðåäåëåíèå àëãîðèòìà ............................................................. 6
2.2. Ïðåäìåò òåîðèè àëãîðèòìîâ ...................................................... 7
2.3. Áëîê-ñõåìû àëãîðèòìîâ, êîìïîçèöèÿ àëãîðèòìîâ .................. 9
2.4. Àëãîðèòìè÷åñêèå ìîäåëè .......................................................... 10
3. ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀ ................................................................................ 13
3.1. Ñòðóêòóðà ìàøèíû ...................................................................... 13
3.2. Äåòåðìèíèðîâàííîñòü ìàøèíû Òüþðèíãà ................................ 15
3.3. Ðàáîòà ìàøèíû Òüþðèíãà .......................................................... 16
3.4. Êîíôèãóðàöèÿ ìàøèíû Òüþðèíãà .............................................. 20
3.5. Òüþðèíãîâî âû÷èñëåíèå ............................................................ 22
3.6. Òåçèñ Òüþðèíãà ............................................................................ 27
4. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÀÂÒÎÌÀÒÎÂ ...................................................... 29
4.1. Àëôàâèòíûå îïåðàòîðû è àâòîìàòû .......................................... 30
4.2. Àáñòðàêòíûå àâòîìàòû ............................................................... 32
4.3. Ñïîñîáû çàäàíèÿ àáñòðàêòíûõ àâòîìàòîâ ................................ 34
4.4. Àâòîìàòíûå îïåðàòîðû .............................................................. 37
5. ÀÁÑÒÐÀÊÒÍÛÉ ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÎÂ ................................................... 40
5.1. Ïîñòðîåíèå ôóíêöèé ïåðåõîäîâ è âûõîäîâ ïî àëôàâèòíîìó
îïåðàòîðó ..................................................................................... 40
5.2. Ïîñòàíîâêà çàäà÷è î ñèíòåçå àâòîìàòîâ................................... 44
5.3. Êëàññû ñîâìåñòèìîñòè àâòîìàòà .............................................. 48
5.4. Àâòîìàò ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé ............................ 50
5.5. Ïðèìåð ìèíèìèçàöèè àâòîìàòà Ìèëè ....................................... 52
5.6. Ïðèìåð ìèíèìèçàöèè àâòîìàòà Ìóðà ........................................ 58
6. ÑÒÐÓÊÒÓÐÍÛÉ ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÎÂ .................................................. 64
6.1. Êîìïîçèöèÿ àâòîìàòîâ ............................................................... 64
6.2. Êàíîíè÷åñêèé ìåòîä ñòðóêòóðíîãî ñèíòåçà àâòîìàòîâ ........... 66
7. ÝËÅÌÅÍÒÀÐÍÛÅ ÀÂÒÎÌÀÒÛ .................................................................. 74
7.1. Ýëåìåíòàðíûå àâòîìàòû ñ äâóìÿ âõîäíûìè ñèãíàëàìè .......... 76
7.2. Ýëåìåíòàðíûå àâòîìàòû ñ òðåìÿ âõîäíûìè ñèãíàëàìè .......... 79
7.3. Ýëåìåíòàðíûé àâòîìàò ñ ÷åòûðüìÿ âõîäíûìè ñèãíàëàìè ...... 84