Přepis přednášky pro ak. rok 2008/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.

Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Petr-H » 22. 1. 2009 02:50

Vystavil jsem na svůj web přepis letošní přednášky. Jedná se o zatím nerevidovanou verzi, pokud narazíte na chyby, ať už gramatické či formální, budu rád pokud mi dáte vědět abych tyto mohl odstranit.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Bydliště: VŠK 17. listopadu
Typ studia: Informatika Mgr.
Login do SIS: hosep5am

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod JardaK » 30. 1. 2009 11:31

Bohuzel soubor nelze otevrit, neslo by to nahrat jeste jednou nekam? Diky moc
JardaK
 

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Petr-H » 31. 1. 2009 18:54

Opraveno, díky za upozornění.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Bydliště: VŠK 17. listopadu
Typ studia: Informatika Mgr.
Login do SIS: hosep5am

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Prince_of_Persia » 3. 2. 2009 12:15

Ja jsem mozna objevil chybu u Strassenova algoritmu (2.2.2)

Jak tam mas ty vypocty M1 az M7 tak se mi nejak nezda vypocet M4

Podle me tam ma byt (A11 + A12) x B22

EDIT: ve slajdech se moje podezreni potvrdilo
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: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Prince_of_Persia » 3. 2. 2009 21:37

Nasel jsem dalsi nesrovnalost: konkretne v algoritmu VISIT-CON (str. 16)

Nevim jestli se nepletu, kdyztak me kamenujte

ten kus kodu jak je tam

Kód: Vybrat vše
if NOT parent(i) then
    art(i) <- true
endif


by mel IMHO vypadat takto

Kód: Vybrat vše
if NOT root(i) then
    art(i) <- true
endif


stejny problem je myslim o par radek nize

Kód: Vybrat vše
if parent(i) then
    parent(i) <- false
endif


nahradit timto

Kód: Vybrat vše
if root(i) then
    root(i) <- false
endif
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: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Prince_of_Persia » 3. 2. 2009 21:44

Jo a jeste mozna chybka u kachliku (spis drobnost, ale kdyz uz jsem si toho zazracne vsiml)

kachlik (b) by mel vypadat takto

horni = q,s (OK)
leva = \lambda (OK)
prava = \lambda (OK)
dolni = q', s' (v tom pdfku je jen q, s' )
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: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Petr-H » 4. 2. 2009 00:22

Máš ve všem pravdu. Co se týče chybky u Strassenova algoritmu, tento kus textu jsem kopíroval ze svých poznámek z Algoritmů a datových struktur a i tam to bylo samozřejmě špatně. Chyby u algoritmu pro testování 2-souvislosti jsem si už všiml a čekal jsem až se posbírá více takových abych je všechny opravil. Kachlík je taktéž špatně. Vyjma těchto jsem narazil ještě na několik dalších chyb a překlepů, především v poslední kapitole kterou jsem v době zveřejnění zápisků jako jedinou ještě nečetl. Všechny tyto chyby jsem opravil a vystavil novou verzi poznámek na web. Mockrát díky za upozornění!
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Bydliště: VŠK 17. listopadu
Typ studia: Informatika Mgr.
Login do SIS: hosep5am

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod johnny » 4. 2. 2009 18:20

Díky moc za materiály, jsou super.
Za odměnu posílám 2 překlepy co jsem objevil :)
1.1 - asymptoticky ostre vetsi / mensi: definice spatne, ma byt velky kvantifikator u n
str. 35, pocetni ulohy, znaceni: prehozeny symboly pro abecedy problemu/certifikatu
johnny
Donátor
Donátor
 
Příspěvky: 95
Registrován: 13. 12. 2005 00:31
Bydliště: Trója
Typ studia: Informatika Mgr.

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Petr-H » 7. 2. 2009 04:13

Díky za upozornění. Opravil jsem tyto a několik dalších chyb a nedostatků a společně se zdrojovým souborem vše vystavil na web.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Bydliště: VŠK 17. listopadu
Typ studia: Informatika Mgr.
Login do SIS: hosep5am

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Che » 11. 2. 2009 16:51

Může mi někdo prosím vysvětlit, jaký je význam posledního kachlíku (g)? Předem díky za odpověď :)
shoot that shit
Uživatelský avatar
Che
Donátor
Donátor
 
Příspěvky: 166
Registrován: 2. 6. 2005 11:29
Bydliště: EU
Typ studia: Informatika Mgr.
Login do SIS: przyc4am

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Lukas Mach » 7. 3. 2009 17:22

Che píše:Může mi někdo prosím vysvětlit, jaký je význam posledního kachlíku (g)? Předem díky za odpověď :)

Aby kdyz ten turingac dokonci praci prilis rychle (a podle nej tak stihneme vykachlikovat jen cast radku), tak abysme mohli dokoncit kachlikovani trivialne (jakoby cekanim v tom koncovem stavu).
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
 
Příspěvky: 261
Registrován: 28. 3. 2006 16:08
Bydliště: Praha a Kladno

Re: Přepis přednášky pro ak. rok 2008/2009

Příspěvekod Návštěvník » 4. 5. 2009 16:55

2.0.4 Operator minimalizacie
2. riadok: tvrdis tam, ze h minimalizacia funkcie f v poslednej premennej a na konci je podmienena rovnost na y.
Nemala by tam byt 0?
Návštěvník
 


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