DTS resici rozhodovaci problem P

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.

DTS resici rozhodovaci problem P

Příspěvekod Almer » 12. 8. 2010 13:54

V definici mam napsano, ze DTS s programem M ma jazyk L(M), coz je seznam vstupnich ktere DTS s programem M prijima ( tedy pouze prijem nikoliv odmitnuti ). A pak dale, ze DTS s programem M resi rozhodovaci problem P , pokud se M vzdy zastavi a navic ze L(M) je L(P)y.

Neni resenim i neprijeti? tedy L(M) je L(P)y u L(P)n? nebo je zla definice toho L(M)? Nejak se mi nezda, ze se bere jenom odpoved ano, protoze ne by mela byt taky platna odpoved ( jakoze zastaveni v koncovem stavu je defacto uznani ze problem x je instane P a prijeti nebo odmitnuti je odpoved ANO / NE ).
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Almer
Site Admin
 
Příspěvky: 686
Registrován: 12. 10. 2004 09:58
Bydliště: Mala Strana - 203
Typ studia: Informatika Ph.D.
Login do SIS: lasap4am

Re: DTS resici rozhodovaci problem P

Příspěvekod Myshaak » 13. 8. 2010 10:20

Almer píše:V definici mam napsano, ze DTS s programem M ma jazyk L(M), coz je seznam vstupnich ktere DTS s programem M prijima ( tedy pouze prijem nikoliv odmitnuti ). A pak dale, ze DTS s programem M resi rozhodovaci problem P , pokud se M vzdy zastavi a navic ze L(M) je L(P)y.

Neni resenim i neprijeti? tedy L(M) je L(P)y u L(P)n? nebo je zla definice toho L(M)? Nejak se mi nezda, ze se bere jenom odpoved ano, protoze ne by mela byt taky platna odpoved ( jakoze zastaveni v koncovem stavu je defacto uznani ze problem x je instane P a prijeti nebo odmitnuti je odpoved ANO / NE ).

Nemam u sebe poznamky a nechce se mi u toho dlouho premyslet, ale matne si vzpominam, ze byl u toho nejaky zadrhel kvuli "odmitnuti nekonecnym vypoctem" (ne jen "koncovym stavem"). Pak by to asi nefungovalo... :) (doufam, ze nerikam blbost, ale zkus se nad tim zamyslet)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.

Re: DTS resici rozhodovaci problem P

Příspěvekod Almer » 13. 8. 2010 12:46

DTS se vzdy zastavi. Bud v koncovem stavu qy nebo qn cimz prijme nebo ne.

Nemusi se zastavit NTS, ktery neprijima bud koncovym staven qn nebo nezastavenim.
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Almer
Site Admin
 
Příspěvky: 686
Registrován: 12. 10. 2004 09:58
Bydliště: Mala Strana - 203
Typ studia: Informatika Ph.D.
Login do SIS: lasap4am

Re: DTS resici rozhodovaci problem P

Příspěvekod stviper » 15. 8. 2010 16:19

Almer píše:DTS se vzdy zastavi. Bud v koncovem stavu qy nebo qn cimz prijme nebo ne.

Nemusi se zastavit NTS, ktery neprijima bud koncovym staven qn nebo nezastavenim.


DTS sa nemusi vzdy zastavit, co ak ti zadefinujem prechodovu funkciu tak, ze sa ti DTS zacykli? Potom nikdy nedostanes odpoved ANO/ NE. Teda nevies o tom rozhodnut.
Uživatelský avatar
stviper
Matfyz(ák|ačka) level I
 
Příspěvky: 14
Registrován: 23. 1. 2005 18:12
Bydliště: Troja

Re: DTS resici rozhodovaci problem P

Příspěvekod cunav5am » 15. 8. 2010 16:26

Ano, DTS se samozřejmě nemusí zastavit a potom je to to samé, jako by odpověděl NE. Někdy se proto taky odmítací stavy neřeší a stroj se prostě nechá cyklit. Problém je ale v tom, jak poznat, že stroj cyklí (halting problem).

Lépe řečeno, L(M) je množina slov na kterých se M zastaví v přijímacím stavu po konečně mnoha krocích (někdy se přidávají požadavky na počet kroků v závislosti na délce vstupu, jako pro P, apod.)
cunav5am
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 4. 6. 2007 08:37
Typ studia: Informatika Mgr.
Login do SIS: cunav5am

Re: DTS resici rozhodovaci problem P

Příspěvekod Almer » 15. 8. 2010 19:01

Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Almer
Site Admin
 
Příspěvky: 686
Registrován: 12. 10. 2004 09:58
Bydliště: Mala Strana - 203
Typ studia: Informatika Ph.D.
Login do SIS: lasap4am

Re: DTS resici rozhodovaci problem P

Příspěvekod cunav5am » 15. 8. 2010 19:10

Ne, DTS se opravdu nemusí zastavit. Halting problem je otázka zda se daný DTS zastaví na daném vstupu.
Totiž, co do výpočetní síly (vyčíslitelnosti) jsou DTS a NTS ekvivalentní, protože lze výpočet NTS simulovat na DTS (průchodem výpočetního stromu do šířky). Samozřejmě, rozdíl je v "délce výpočtu".
cunav5am
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 4. 6. 2007 08:37
Typ studia: Informatika Mgr.
Login do SIS: cunav5am

Re: DTS resici rozhodovaci problem P

Příspěvekod beaver » 15. 8. 2010 23:23

Almer píše:Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?


Ty michas jablka a hrusky. Turinguv stroj (a je celkem jedno jaky, protoze pokud neni linearne omezeny, tak jsou vsechny varianty stejne silne) je jen jinym modelem pro rekurzivne spocetne jazyky. Das stroji (funkci, necemu, ...) slovo a cekas, co ti na to odpovi. Bud rekne "ANO" a pak vis, ze slovo do jazyka patri, nebo bude divergovat.

Jestli je stroj deterministicky nebo ne je z hlediska halting problemu fuk. Zajimave je to jen kdyz uvazujeme casove slozitosti.

Mas v tom pekny hokej. Doporucuju zopakovat si Automaty a gramatiky a pak si precist Johanciny pohadky o vycislitelnosti. http://atrey.karlin.mff.cuni.cz/~johanka/vyuka/pohadky_vycislitelnost.html
Cožpak většina z nás svým způsobem nehledá svou kravičku?
T. Pratchett, z knihy "Kdepak je má kravička"
Uživatelský avatar
beaver
Matfyz(ák|ačka) level III
 
Příspěvky: 186
Registrován: 2. 2. 2007 09:33
Bydliště: Praha
Typ studia: Nestuduji ale učím na MFF

Re: DTS resici rozhodovaci problem P

Příspěvekod Myshaak » 16. 8. 2010 22:17

Almer píše:Ja myslel, ze DTS se musi zastavit vzdy. Prave proto je deterministicky. Ikdyz je pravda, ze TS prijima bud vypoctem a nebo stavem ( tedy bud stavem ANO/NE ) nebo skoncenim.

Pokud si to ale vezmeme jinak , tak DTS defacto prijima rekurzivni ( efektivne vycislitelne ) funkce. Zatim NTS prijima rekurzivne spocetne ( castecne rekurzivni ) funkce. Do druhe skupiny patri i halting problem, tedy nemichate jablka a hrusky?

Jak uz bylo receno (a jak uz je Ti doufam jasne), DTS se obecne rozhodne zastavit nemusi ( while(true){;} ). Nicmene v definici DTS resi problem P je pozadavek, ze DTS se na kazdem vstupu zastavi.
Mozna ale tusim, kde mohlo dojit trochu k nejasnostem - ono je vic (ekvivalentnich) definic TS, aspon pokud si to dobre pamatuju. Jedna, kde je proste mnozina koncovych stavu, kam kdyz se stroj dostane, tak skonci ("prijme", rekne ANO...), jinak treba nekde zacykli. Druha (ktera se spis pouzivala prave ve Slozitosti), kde jsou dva zvlastni stavy qy (jeden jediny, ne mnozina) pro prijimuti (ale POZOR, prijimuti ne v "automato-gramatickem" smyslu "rozeznal jsem, ze slovo patri do daneho jazyka", ale prijimuti ve smyslu "odpoved na zadani je ANO") a qn pro odmitnuti. I tento stroj se muze nekde zacyklit.
Je potreba si tento rozdil uvedomit - zatimco v Autogramech byl TS na testovani, zda je slovo z daneho jazyka, tady je na rozhodovani, jestli zadani spada do "kategorie ANO" nebo "kategorie NE". Je to sice ekvivalentni, ale musi se clovek nad tim zamyslet, na jaky jazyk bude kde testovat. :)

Definice rika, ze DTS M resi problem P <=> M vzdy zastavi a L(M) = L(P)y. Jo mimochodem byl tam takovy maly predpoklad, ze rozhodnout, zda x e P jde polynomialne (=preprocessing, ktery rekne, jesti x je zadani problemu, nebo jen nesmyslny retezec). Otazkou tedy neni, zda na vstupu x skonci TS v nejakem koncovem stavu (jako v "Autogramech"), ale v kterem z nich.
Kdybys za L(M) vzal ne vstupy, ktere skonci v qy, ale vstupy, ktere skonci bud v qy nebo v qy, tak bys s tim nemohl postavit definici pro stroj resici problem P. (Myslim ze treba stroj, ktery nehlede na vstup, osetreny preprocessingem, skoci hned do libovolneho z tech dvou koncovych stavu by pak "resil" libovolny problem [ pze v takovem pripade opravdu L(M) = L(P) = L(P)y U L(P)n ], coz nedava smysl ;) )
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron