[Zap] 14.1.2009

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.
Prince_of_Persia
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Typ studia: Informatika Mgr.
Bydliště: Jindřichův Hradec
Kontaktovat uživatele:

[Zap] 14.1.2009

Příspěvek od Prince_of_Persia »

Dneska jsme dostali tuto sadu prikladu:

1) Reseni dvou rekurentnich rovnic
a) T(n) = 2T(n/2) + n^3
b) T(n) = 2T(2n/3) + T(n/3) + n * sqrt(n)

2) priklad z 3. cviceni cislo 3 (podle toho dokumentu co ma p. Cepek na webu)
tj. ze DFS minimalizuje pocet inkonzistentnich hran.... - dokazat nebo vyvratit

3) Problem TAUT
a) Je TAUT ve tride co-NP?
b) Jaka je slozitost TAUT pokud je F CNF?
Uživatelský avatar
joshis
Matfyz(ák|ačka) level III
Příspěvky: 127
Registrován: 23. 11. 2006 01:47
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zap] 14.1.2008

Příspěvek od joshis »

Vi nekdo, kdy muzeme ocekavat vysledky (resp. my "ostatni", co nejdeme na predtermin)?

Jinak myslim, ze kombinace prikladu byla vice nez pratelska...
Prince_of_Persia
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Typ studia: Informatika Mgr.
Bydliště: Jindřichův Hradec
Kontaktovat uživatele:

Re: [Zap] 14.1.2009

Příspěvek od Prince_of_Persia »

Jestli jsem dobre slysel a pochopil, tak vysledky by meli byt do nedele v SISu,
protoze potom odleta kamsi do /dev/null.
Kdo do te doby nebude mit zapocetv SISu tak to pravdepodobne neudelal.

Opravte me pokud to pisu blbe prosim
Naposledy upravil(a) Prince_of_Persia dne 22. 1. 2009 10:31, celkem upraveno 1 x.
Uživatelský avatar
Void
Matfyz(ák|ačka) level II
Příspěvky: 54
Registrován: 17. 1. 2006 16:21
Typ studia: Informatika Mgr.

Re: [Zap] 14.1.2008

Příspěvek od Void »

Vypadá to tak, já dostal zápočet už 16. tj. v pátek. Btw, datum toho zápočtu je v předmětu o rok pozadu :)
Aurë Entuluva!!
Prince_of_Persia
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Typ studia: Informatika Mgr.
Bydliště: Jindřichův Hradec
Kontaktovat uživatele:

Re: [Zap] 14.1.2009

Příspěvek od Prince_of_Persia »

Void píše:Vypadá to tak, já dostal zápočet už 16. tj. v pátek.
Me se taky nekdy po poledni objevil zapocet v SISu
Btw, datum toho zápočtu je v předmětu o rok pozadu :)
Njn to se stava :D Casem dokonvegruju k tomu, abych zacal pouzivat novej letopocet :)
Naposledy upravil(a) Prince_of_Persia dne 22. 1. 2009 10:32, celkem upraveno 1 x.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: [Zap] 14.1.2009

Příspěvek od hippies »

fixed
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Odpovědět

Zpět na „TIN062 Složitost I“