Algoritmická riešiteľnosť
Z Psychostudia
Hlavná stránka / Umelá inteligencia / Vybrané kapitoly z umelej inteligencie
Úlohy pre ktoré existuje algoritmus sa nazývajú algoritmicky riešiteľné(efektívne)
Algoritmus je možné znázorniť vývojovým diagramom.
Pri výpočte sa algoritmom pohybuje tzv. riadenie, ktoré označuje, ktorý príkaz sa má práva vykonať.
Snímok = údaje + algoritmus + riadenie
Za predpokladu existencie počiatočnej podmienky X ktorú musia spĺňať vstupné údaje algoritmu a súčasnej existencie výstupnej podmienky Y, ktorú musia spĺňať výstupné údaje môžeme definovať:
- Konečnosť diagramu - ak pre všetky vstupné údaje spĺňajúce podmienku X je výpočet konečný.
- Podmienená správnosť diagramu - ak pre všetky vstupné údaje spĺňajúce podmienku X dostaneme, za súčasnej platnosti konečnosti výpočtu, výstupné údaje spĺňajúce podmienku Y.
- Úplná správnosť diagramu - ak pre všetky vstupné údaje spĺňajúc podmienku X výpočet skončí a výstupné údaje spĺňajú podmienku Y.
Turingova veta
Hovorí o neriešiťeľnosti problému skončenia.
Úloha, či daný vývojový diagram skončí pre dané údaje alebo nie, je algoritmicky neriešiteľná.
Dôkaz:
Voľne interpretované: Môžem zostrojiť algoritmus (problémový program - PP), ktorý bude volať program pre testovanie konečnosti programu (testovací program - TP). TP vráti PP 1 ak je PP konečný a 0 ak nie.
----1 ak u je kód turingovho stroja, ktorý sa pre vstupné slovo v zastaví
|
f(u,v)=|
|
----0 inak
Potom mi do PP stačí vložiť podmienku,že keď TP vráti 0 ukonči a keď 1 choď do nekonečného cyklu.
Problém dôkazu správnosti riešenia, je tiež vo všeobecnosti neriešiteľný.
Pre "rozumné" vývojové diagramy je možné použiť napr. Floydovu metódu.
Zdroje
- Csontó, J., Sabol, T.: Umelá Inteligencia. (skriptum) Technická Univerzita Košice, 1991;ISBN 80-7099-104-6
- P. Sinčák, G. Andrejková: Neurónové siete Inžiniersky prístup. TU Košice, Elfa-Press, 1996, ISBN 80-88786-38-X.
