Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 28. 07. 2013 23:23
- ondrej.hav
- Příspěvky: 162
- Reputace: 4
Třída problémů P
Ahoj, tak jsem se dostal do situace, kdy nevím jak dál.
Mám definici. 
A přijde mi, že by tam mělo být "libovolné slovo délky n zpracuje v čase f(n). Vždyť pokud by stačilo aby bylo časem omezeno pouze rozhodnutí o slovech jazyka J, která podle definice budou všechna přijata mi to nedává záruku odpovědi v čase f(n) pro slova, která M nebude akceptovat.
Tedy pokud bych měl jazyk: J = všechny souvislé grafy... Tak přijímací počítač M, který přijímá J mi musí pro libovolný graf rozhodnout, zdali je graf souvislý nebo ne v čase f(n). V tomhle případě tedy v polynomiálním čase.
Je to tak, nebo něco chápu špatně? Moc se mi nechce věřit, že by ve skriptech byla chyba.
Offline
- (téma jako vyřešené označil(a) ondrej.hav)
#2 28. 07. 2013 23:48 — Editoval JohnPeca18 (29. 07. 2013 00:00)
- JohnPeca18
- Příspěvky: 651
- Škola: MFF UK
- Pozice: Absolvent 2014
- Reputace: 81
Re: Třída problémů P
Podľa mňa máš pravdu a v skriptech je chyba.
My sme sa to učili cez Turingove stroje. Vy tam namiesto Turingoveho stroja mate príjmací počítač. Nepoznám teda definici příjmacieho počítača ale to čo hovoríš dáva logiku. Počítač musí spracovať v čase f(n) slová délky n i ty, ktere nepatri do jazyka L.
Popravde ta definice se mi vubec nelibi, nelibi se mi kvuli tomu, že používa nejaký počítač, a nepoužíva Turinguv stroj. A taky se mi nelíbi, že nevím jestli se jedná deterministicku alebo nedeterministickú časovú zložitost. To je prece dost velky rozdil.
Edit: Ak sa jedna o to ako sa dostat k tride problemu P. Potom sa jedna o deterministicku zlozitost a o to viac som presvedceny, ze to čo hovoríš je pravda. Keď tak, pokiaľ máš k dispozící skripta on-line, bolo by možné dosledovať z ostatných definic jak to vlastne je myšleno.
Offline
#3 29. 07. 2013 00:05
- ondrej.hav
- Příspěvky: 162
- Reputace: 4
Re: Třída problémů P
↑ JohnPeca18:
Díky moc za odpověď. Já jsem o tom taky v podstatě přesvědčený.
Skripta jsou na http://www.cam.zcu.cz/~ryjacek/students/ps/TGD1.pdf
Omlouvám se za neúplnou specifikaci, jedná se o deterministickou složitost. Právě z těch ostatních definic se mi zdá, že to je tak, jak říkám.
Ve skriptech problém začíná na straně 54.
Offline
#4 29. 07. 2013 00:13
- JohnPeca18
- Příspěvky: 651
- Škola: MFF UK
- Pozice: Absolvent 2014
- Reputace: 81
Re: Třída problémů P
Podival jsem se na to. Ten prijmaci počítač je RAM, což mi dáva už víc smysl. A stále si myslim, že máš pravdu a v skriptech mají nepřesnost.
Offline