Zkouška Mareš 10.2.

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Zkouška Mareš 10.2.

Příspěvek od Ellrohir »

1. Dinicův algoritmus - formulace, ukázat korektnost, rozebrat časovou složitost + jak je to pro jednotkové kapacity hran
2. Definovat: problém, převoditelnost a třídy P, NP a NP-úplnost; dokázat Cookovu větu (s tím, že na přednášce nedokázané lemma se dalo považovat za platné)
3. Komparátorová síť na zatřídění prvku do už setříděné rostoucí posloupnosti (cílem byla logaritmická hloubka sítě)
4. Najít nejčastěji se vyskytující podřetězec délky k v zadaném textu délky n (cílem měla být konstatní složitost k délce textu)
bonus - spočítat 2^2^2^...^2 mod 13 (dva na dva na druhou atd., to celé n-krát)
Naposledy upravil(a) Ellrohir dne 10. 2. 2010 17:13, celkem upraveno 1 x.
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška Mareš 10.2.

Příspěvek od Ellrohir »

na začátku - to jest těsně po desáté - říkal Mareš, že by rád končil ve 4 a všichni se smáli...já pak odcházel asi v půl čtvrté a furt tam ještě asi 4 lidi zbývali

Dinice jsem jakžtakž dohromady dal, akorát v odhadu složitosti jsem otočil čeho je m a čeho n u hledání blokujícího toku, v důkazu korektnosti se (alespoň ten Marešův kolega student) moc nešťoural, myslím, že ho snad ani nečetl...to s jednotkovými kapacitami mi položil jako bonus otázku během řeči (ale slyšel jsem to i u jiných) a já to nevěděl hned z hlavy, ale po chvíli dorozmyslel (klesne složitost na O(mn), protože každý blokující tok neostraní minimálně 1 hranu, ale všechny hrany z cesty)

NP-úplnost jsem při učení "taktně přeskočil" a samozřejmě to bylo vidět, takže tam jsem neměl prakticky nic

Komparátorou síť jsem postavil zřejmě správně...podobá se to quick sortu - porovnat první a n/2-hý a na další hladině totéž pro dva poloviční intervaly (je potřeba buď chtít vstup 2^n a nebo říct, že jedna "půlka" bude n/2-horní celá část a druhá n/2-dolní celá část, na tohle mě Mareš trochu nachytal)...to potřebuje skutečně logaritmicky hladin a správnost se dokáže indukcí podle počtu vstupů

Ve čtyřce se rozhodně použije Rabin-Karp a jeho hashování...vždycky tu nahashovanou hodnotu porovnám s nějakým "seznamem už nalezených hodnot" a upravím počet výskytů nebo přidám novou hodnotu...potíž je, že když jako reprezentaci zvolím pole indexované hashi, taky budu potřebovat n^2 času na inicializaci...proto jsem zvolil reprezentaci binárním vyhledávacím stromem, což znamená složitost O(n log n) za hledání ve stromu...Mareš během "dávání nápověd" říkal, že bychom to "měli umět lineárně k délce vstupu, pokud předpokládáme, že máme perfektní hashovací funkci", ale takováhle složitost mi stačila, nic lepšího po mě nechtěli...akorát pak druhý zkoušející chtěl, aby se pak pro nalezený "nejčastější výskyt podle hashe" umělo rychle ověřit, že nedošlo ke kolizi (což byl teda podle mě trochu spor s tím, co nás nechal předpokládat sám MJ) a to jsem nějak nedal - postup co jsem "vyposlechl" byl nějak pustit znova Rabin-Karpa na hledání toho hashe, co jsme dostali a při nalezení vždycky porovnat, jestli to jsou stejné řetězce...a aby to nebylo moc složité v případě překrývajících se výskytů (například hledání "aaaa" v samých áčkách), tak se měl nějak využít automat na KMP a jeho zpětné hrany, ale to sem už nepochopil

bonus jsem trošku zkoušel, ale nic kloudného nevymyslel, tudíž ani nepředváděl

kažpodáně Mareš po zhodnocení toho, co jsem měl a neměl konstatoval, že je to mezi 2-3 a dal mi bonus - aproximační algoritmus obchodního cestujícho, který jsem tu včera na fóru někomu vysvětloval (aspoň to nebylo zbytečné, i kdyby ne pro toho dotyčného), takže pohoda dvojka i bez NP-úplnosti :) zkoušející jsou opravdu velmi hodní :)
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“