zk 7.2.2007

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
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

zk 7.2.2007

Příspěvek od Dawe »

Takže písemka:
15.1. z minulých let

Na ústním bylo: myslím že BICON (nejsem si jist), kachlikovaní, Strassen, #P a vše okolo, haldy a amortizovaný složitosti.

Další snad nľkdo doplní později...

Měl jsem Kachlikování, napsal jsem to co sem měl v sešitě, občas se na něco zeptal, ale vesměs tomu asi snad ani člověk nemusí rozumět, jen skopírovat. Řek že to mám OK a ať ještě povím něco o Strassenovi, trochu jsem se do něj zamotal, ale s jeho malou pomocí jsem to dal do kupy...
Zatím tam byly dvě jedničky, jeden boj o 2-3 a dál nevím...
Přeju hodně štěstí a já jdu na yasloužený odpočinek 8)

PS: Děkuji Aničce za zápisky na webu, především tady (ale občas i jinde) pomohly.
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

Ja som mal amortizovanu zlozitost decrease-key u Fib. haldy, teda nic nove. Najprv som popisal merge a konsolidaciu, potom na upozornenie som doplnil tu pozadovanu cast s decrease-key + dokaz s vyskou stromu. Na nic dalsie sa nepytal, zapisal 1.
BICON medzi prvymi otazkami nebol, bol to planarny separator - nastastie ma tesne minul :twisted:
Prekvapilo ma, ze sa vlastne ani nepozrel na pisomku. Cviciaci (Kronus?) nam prvym styrom co sme odovzdali pisomku opravil a Cepkovi stacila informacia, ze to mame ok.
Pripajam sa k podakovaniu Anji, bez tych poznamok to neviem. 8)
bondoer
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 27. 11. 2006 21:39

Re: zk 7.2.2007

Příspěvek od bondoer »

Dawe píše:Takže písemka:
15.1. z minulých let
a nevies presne z ktoreho rou, lebo ja mam viac pismiek s datumom 15.1.....
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: zk 7.2.2007

Příspěvek od rastik »

bondoer píše:
Dawe píše:Takže písemka:
15.1. z minulých let
a nevies presne z ktoreho rou, lebo ja mam viac pismiek s datumom 15.1.....
Ta, co ma priklad s MMNM - 15.1.2001. Jedna z tych krajsich, povedal by som.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Jo cvičící byl Kronus. Asi s těma písemkama nebyl problém :-) Mě spíš dostalo, když mi řekl, že mám jít od 11. Sem čekal, že pujdu až odpoledne a něco se ještě naučím :-) Planární separátor jsem si docela přál, to kachlíkování ani moc ne, ale dopadlo :-)
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

Dawe píše:Mě spíš dostalo, když mi řekl, že mám jít od 11. Sem čekal, že pujdu až odpoledne a něco se ještě naučím :-)
Tak to si mal odovzdavat neskor, u Cepka sa chodi podla poradia odovzdania pisomky :)
bondoer
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 27. 11. 2006 21:39

Příspěvek od bondoer »

rastik píše:
Dawe píše:Mě spíš dostalo, když mi řekl, že mám jít od 11. Sem čekal, že pujdu až odpoledne a něco se ještě naučím :-)
Tak to si mal odovzdavat neskor, u Cepka sa chodi podla poradia odovzdania pisomky :)
ale da sa aj dohodnut ;) proste prides povies ze mozes aj poobede a on ta tam zapise.

jo este jedna otazocka, nekussal dnes ja kronus? :)
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

bondoer píše:jo este jedna otazocka, nekussal dnes ja kronus? :)
O 11h nie, mozno niekto bude vediet ci na terminoch od 13h.
Uživatelský avatar
Dolda
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 2. 2. 2006 14:22
Typ studia: Informatika Mgr.
Bydliště: Bohnice

Příspěvek od Dolda »

Neee, od jedny ani od dvou taky ne.... On snad nekdy zkousel?
Born 2 die in Enemy Territory
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

2Rastik - no já byl nakonec rád, že jsem to měl už za sebou. To že se chodí v pořadí jak se odevzdá vím, ale myslel jsem, že si třeba vezmou aspoň čas na opravení nebo tak :-)

2Dolda - Kronus skoušel ADS 2, bylo to celkem vpohodě. Tak to loni zkoušel Petr Kučera. Složitost si ale asi nechává Čepek pro sebe...
bondoer
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 27. 11. 2006 21:39

Příspěvek od bondoer »

Dolda píše:Neee, od jedny ani od dvou taky ne.... On snad nekdy zkousel?
no na termine predtym, vypomahal cepkovi ku konci, a co som pocul tak to bola unho fakt pohodova slozitost ;), tak preto sa pytam :), chcem pohodu a slozitost hlavne :)
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

bondoer píše:chcem pohodu a slozitost hlavne :)
Jeden zo skusanych dostal vcera otazku (neviem aku) a asi ju nevedel, tak Cepka poziadal o inu. Cepek povedal, ze sa to odrazi na jeho znamke, ale dal mu nejaku inu. Takze prinajhorsom pokial clovek dostane nieco, co by naozaj nevedel (napr. planarny separator u mna :D ), tak sa to da uhrat niecim inym.
bondoer
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 27. 11. 2006 21:39

Příspěvek od bondoer »

rastik píše:
bondoer píše:chcem pohodu a slozitost hlavne :)
Jeden zo skusanych dostal vcera otazku (neviem aku) a asi ju nevedel, tak Cepka poziadal o inu. Cepek povedal, ze sa to odrazi na jeho znamke, ale dal mu nejaku inu. Takze prinajhorsom pokial clovek dostane nieco, co by naozaj nevedel (napr. planarny separator u mna :D ), tak sa to da uhrat niecim inym.
hehe a nevies co vymenil za co? :) akoze co viem tak ked nevies tak zvykne davat tu druhu otazku, zvacsa definiciu. Ale takato moznost sa mi lubi, lebo napriklad ten planarny separator je riadna p.....
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

bondoer píše:
rastik píše:
bondoer píše:chcem pohodu a slozitost hlavne :)
Jeden zo skusanych dostal vcera otazku (neviem aku) a asi ju nevedel, tak Cepka poziadal o inu. Cepek povedal, ze sa to odrazi na jeho znamke, ale dal mu nejaku inu. Takze prinajhorsom pokial clovek dostane nieco, co by naozaj nevedel (napr. planarny separator u mna :D ), tak sa to da uhrat niecim inym.
hehe a nevies co vymenil za co? :) akoze co viem tak ked nevies tak zvykne davat tu druhu otazku, zvacsa definiciu. Ale takato moznost sa mi lubi, lebo napriklad ten planarny separator je riadna p.....
Dawe by vedel, sedel vedla neho. To druhe co dostal bolo tusim #P a nejake veci okolo. Co som pocul, tak sa v tom dost vrtal.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

No dostal kachlíkování, nechtěl ho, tak dostal #P a já schytal to kachlíkování :-) Podle mně je lepší, když víte aspoň půlku, tak tam tu půlku napsat, on pak dá druhou věc a je z toho jeden a půl. Když řeknete, že nevíte, je z toho 0... A taky když člověk ví aspoň půl, tak Čepek pomůže a třeba z toho i nakonec bude celá ta věc.
Odpovědět

Zpět na „TIN062 Složitost I“