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.
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

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

Příspěvek od Petr-H »

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

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

Příspěvek od JardaK »

Bohuzel soubor nelze otevrit, neslo by to nahrat jeste jednou nekam? Diky moc
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

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

Příspěvek od Petr-H »

Opraveno, díky za upozornění.
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: Přepis přednášky pro ak. rok 2008/2009

Příspěvek od Prince_of_Persia »

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
Typ studia: Informatika Mgr.
Bydliště: Jindřichův Hradec
Kontaktovat uživatele:

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

Příspěvek od Prince_of_Persia »

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
Typ studia: Informatika Mgr.
Bydliště: Jindřichův Hradec
Kontaktovat uživatele:

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

Příspěvek od Prince_of_Persia »

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' )
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

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

Příspěvek od Petr-H »

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í!
johnny
Donátor
Donátor
Příspěvky: 95
Registrován: 13. 12. 2005 00:31
Typ studia: Informatika Mgr.
Bydliště: Trója

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

Příspěvek od johnny »

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
Uživatelský avatar
Petr-H
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 30. 1. 2006 14:18
Typ studia: Informatika Mgr.
Bydliště: VŠK 17. listopadu
Kontaktovat uživatele:

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

Příspěvek od Petr-H »

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
Che
Donátor
Donátor
Příspěvky: 166
Registrován: 2. 6. 2005 12:29
Typ studia: Informatika Mgr.
Bydliště: EU
Kontaktovat uživatele:

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

Příspěvek od Che »

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
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

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

Příspěvek od Lukas Mach »

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?
Návštěvník

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

Příspěvek od Návštěvník »

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?
Odpovědět

Zpět na „TIN062 Složitost I“