[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.

[Zap] 14.1.2009

Příspěvekod Prince_of_Persia » 14. 1. 2009 16:48

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

Re: [Zap] 14.1.2008

Příspěvekod joshis » 14. 1. 2009 22:39

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

Jinak myslim, ze kombinace prikladu byla vice nez pratelska...
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.

Re: [Zap] 14.1.2009

Příspěvekod Prince_of_Persia » 15. 1. 2009 12:59

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 Prince_of_Persia dne 22. 1. 2009 10:31, celkově upraveno 1
Prince_of_Persia
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Bydliště: Jindřichův Hradec
Typ studia: Informatika Mgr.
Login do SIS: prinf5am

Re: [Zap] 14.1.2008

Příspěvekod Void » 19. 1. 2009 11:59

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!!
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.2009

Příspěvekod Prince_of_Persia » 19. 1. 2009 20:27

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 Prince_of_Persia dne 22. 1. 2009 10:32, celkově upraveno 1
Prince_of_Persia
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Bydliště: Jindřichův Hradec
Typ studia: Informatika Mgr.
Login do SIS: prinf5am

Re: [Zap] 14.1.2009

Příspěvekod hippies » 21. 1. 2009 18:24

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ů..
Uživatelský avatar
hippies
Admin(ka) level I
 
Příspěvky: 990
Registrován: 29. 9. 2004 11:46
Bydliště: Mladá Boleslav
Typ studia: Informatika Mgr.
Login do SIS: procj4am


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