Zkouška 22. května, 15:00

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Uživatelský avatar
lukax
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 12. 1. 2009 11:32
Typ studia: Informatika Bc.

Zkouška 22. května, 15:00

Příspěvek od lukax »

A1. Kruskalův algoritmus, jeho složitost a důkaz správnosti.

A2. Násobení dlouhých čísel v podkvadratickém čase.

B1. Vymyslet datovou strukturu, která by uměla operace Insert, Delete a Vyber k-tý nejmenší prvek a dokázat, že ji nejde vymyslet rychlejší.

B2. Máme čtvercovou síť N×N, kde jsou volná políčka, zdi, klíče K1..k a odpovídající zamčené dveře D1..k a my a máme v ní najít cestu ven.

C1. Polosouvislý je takový graf, kde pro každé u, v ∈ V existuje cesta z u do v nebo z v do u. Jak něco takového rychle poznat?

Bylo to moc fajn a spousta lidí si odnesla jedničky. :-)
cman
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 3. 11. 2008 10:36
Typ studia: Informatika Bc.

Re: Zkouška 22. května, 15:00

Příspěvek od cman »

Byl by někdo ochotný sem napsat správné odpovědi, čímž by pomohl ostatním a zvýšil užitnou hodnotu tohoto fóra?
mp

Re: Zkouška 22. května, 15:00

Příspěvek od mp »

Ve stručnosti nějak takto:
A1. Algoritmus na hledání minimální kostry (tzv. hladový). Kdo by nevěděl, přečtěte si zápisky z letošních přednášek na stránkách MJ. (Nejsou ještě všechny hodiny, ale tahle tam tuším je.) Doporučuji neodbýt důkaz správnosti, často to vypadá naprosto jasné - ale musí se to dobře zdůvodnit. (Zde např. s výhodou použít Lemma o řezech.) Složitost záleží na datové struktuře: uchovávání v obyč. poli vyjde na \O(m\log m + n^2), zakořeněné stromy komponent souvislosti na \O(m\log m + m\log n + n\log n).
A2. Násobení dlouhých čísel --> viz zápisky. (Metoda rozděl a panuj - rozpůlení, využít, že můžeme násobit jen 3krát místo 4krát --> časová složitost \O(n^{\log_2 3}), důkaz např. z Kuchařkové věty (Master Theorem).)
B1. Např. BVS (binární vyhledávací strom) + v každém vrcholu si pamatovat #vrcholů v levém a pravém podstromě. K-tý nejmenší prvek se pak najde na jeden průchod od kořene k hledanému prvku (udržuji si interval, ve kterém se nachází prvky v mém podstromě a ve vrcholu vždy jasně vidím, kudy se vydat). Insert, Delete i K-tý nejmenší prvek tedy trvají \Theta(hloubka stromu). Pokud tedy bude strom vyvážený, tak je to \Theta(log n), kde n je #vrcholů. Nutno si ještě rozmyslet, jak bude vypadat vyvažování (především rotace) a že neovlivní časovou složitost. Jinak důkaz, že to nejde rychleji není složitý - stačí využít toho, že jsme si dokázali, že v porovnávacím modelu (kdy smíme jen porovnávat a prohazovat) lze třídit nejrychleji (tedy \Omega) n\log n. Kdyby byly tyto operace rychlejší, tak umíme třídit pomocí nich rychleji než n\log n.
B2. Obecná myšlenka je taková, že prohledáváme do šířky graf: vrcholům odpovídají stavy - souřadnice človíčka - a mezi dvěma vrcholy vede hrana, když se z jednoho dá dostat na druhý (tzn.je sousední, není mimo pole, není zeď, když dveře, tak jsou otevřené atd.) Tento graf si v podstatě vůbec nemusíme pamatovat - stačí nám přechodová funkce, která nám vždy vrátí dosažitelné sousední pozice. Jediný problém je tedy s klíči. Není dobré řešení si ke stavům pamatovat ještě množinu nalezených klíčů, neboť klíčů může být hodně a takových stavů by pak bylo exponenciálně mnoho --> zhorší se časová i paměťová složitost. Jinak jeden klíč může pasovat do více dveří (všechny se stejným indexem), ale nemůže více klíčů pasovat do jedněch dveří. Řešení: na začátku si celé pole projít a zaznamenat si (do nějakého pole) souřadnice dveří, které otevírá daný klíč a naopak. Pak při nalezení dveří se vždy kouknout, zda klíč už máme --> pak mohu vstoupit. Když najdeme klíč, tak je nutné se ještě podívat, ke kterým dveřím vede --> a tyto pozice znovu hodit do fronty (už jsme je totiž označili za navštívené a nikdy bychom přes ně více neprošli), aby byly prozkoumány. Prohledávání končí klasicky, když se dojde na cílové políčko. Ještě dodám, že nebylo účelem najít nejkratší cestu, ale libovolnou - a především říci, zda je cíl dosažitelný.
C1. Pomalu a blbě: Pustit DFS/BFS postupně na všechny vrcholy a zaznačit si, zda vždy obarvil všechny ostatní. Když ne, např. z u do v, tak se ještě kouknout, zda neobarvil z v do u. Pokud existuje takováto oboustranně neobarvená dvojice, pak není graf polosouvislý.
Rychleji a lépe: Graf je polosouvislý <==> existuje jednoznačné topologické uspořádání na grafu komponent souvislosti. Tzn. využít algoritmus na rozdělení do komponent souvislosti (\O(m + n)) a pak určit, zda na něm existuje jednoznačné TU, např. algoritmem na TU, který postupně odtrhává zdroje a snižuje stupně sousedním vrcholům, to je také \O(m + n) --> polosouvislost určíme s lineání časovou složitostí.

Zkouška byla docela příjemná. MJ je klasicky v pohodě. =) Většinu chtěl dosti pečlivě - i v praktických příkladech. Takže je potřeba se klasicky trošku obrnit proti čekání (znáte to, když pokaždé vymyslíte něco lepšího, ale dozvíte se, že to ještě není ono a ať si to ještě rozmyslíte... ;) ) - ale to je na všech polopísemných-poloústních zkouškách.... A je fajn, že člověka nikdo nestresuje. Hodně štěstí všem, kdo ještě nebyli!
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“