http://ktiml.mff.cuni.cz/~bartak/automa ... ture12.pdf
nemohl by mi někdo pls napsat:
1] jak si mám vysvětlit ty tečky na str. 4, slajd na pozici 1x1?
2] a kde se vzala ta tabulka na slajdu 2x1?
Myšlenka toho důkazu je ta, že PKP převedu na turingův stroj, o kterém víme, že se nemusí zastavit na nějakých slovech => problém je nerozhodnutelný. Ale jak vznikla ta tabulka a jaký vztah má u a v k w - to už mi jasné není
Díky za pomoc
PKP
-
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 31. 1. 2008 12:51
- Typ studia: Informatika Bc.
- Login do SIS: benat7am
Re: PKP
Ahoj!
Ted jsem na to PKP koukal a myslim, ze tem teckam rozumim. On si schvalne slova ui a vi upravil tak, ze mezi pismena tech slov nacpal tecky, a to dvojim zpusobem:
a) Bud dava tecky mezi vsechna pismena slova a i na zacatek nebo
b) dava tecky mezi vsechna pismena slova a i na konec
Nyni xi a yi jsou preteckovana pro indexy od 2 do n+1 a x(i+1) je preteckovane ui, obdobne pro y a v. Pro index n+2 tam ma pomocna slova x(n+2) a y(n+2). Kdyz budu hledat PKP pro tyhle dvojice slov, tak musi zacinat dvojici (x1,y1), protoze vsechny ostatni dvojice se lisi v tecce na zacatku. Takze kdyz mam nalezeno PKP, odstranim z vybranych dvojic tecky a mam definovany seznam dvojic (ui,vi), ze resi PKP a navic prvni dvojici je (u1,v1), tedy mam PKP s inicialnim resenim.
Aspon myslim .
Ten TS zatim nechapu.
Ted jsem na to PKP koukal a myslim, ze tem teckam rozumim. On si schvalne slova ui a vi upravil tak, ze mezi pismena tech slov nacpal tecky, a to dvojim zpusobem:
a) Bud dava tecky mezi vsechna pismena slova a i na zacatek nebo
b) dava tecky mezi vsechna pismena slova a i na konec
Nyni xi a yi jsou preteckovana pro indexy od 2 do n+1 a x(i+1) je preteckovane ui, obdobne pro y a v. Pro index n+2 tam ma pomocna slova x(n+2) a y(n+2). Kdyz budu hledat PKP pro tyhle dvojice slov, tak musi zacinat dvojici (x1,y1), protoze vsechny ostatni dvojice se lisi v tecce na zacatku. Takze kdyz mam nalezeno PKP, odstranim z vybranych dvojic tecky a mam definovany seznam dvojic (ui,vi), ze resi PKP a navic prvni dvojici je (u1,v1), tedy mam PKP s inicialnim resenim.
Aspon myslim .
Ten TS zatim nechapu.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 15
- Registrován: 19. 1. 2010 10:57
- Typ studia: Informatika Mgr.
Re: PKP
Tady je pěkne vysvetleno PKP http://www.cs.vsb.cz/kot/animace.php
Je tam i dost dalších věcí.
Ten odkaz už tady na fóru je, ale pokud někdo hledá PKP, tak ho lépe najde tady.
Je tam i dost dalších věcí.
Ten odkaz už tady na fóru je, ale pokud někdo hledá PKP, tak ho lépe najde tady.