Zkouška - Mareš 8. 2. 2018

Pokračování přednášky TIN060 Algoritmy a datové struktury I
MC RIDE

Zkouška - Mareš 8. 2. 2018

Příspěvek od MC RIDE »

1) Algoritmus na průsečík přímek.

2) Máme bipartitní graf a chceme nalézt perfektní dvojíté párování, tedy že každý vrchol má stupeň právě dva.

Graf převedeme na tok, dále rozdělíme každý vrchol partity V do hrany tak, že vytvoříme nové vrcholy V1 a V2. Hrany, které vedly z V napojíme na V2. Hrany, které vedly do V napojíme na V1. Kapacitu hran Z-V1, V1-V2, V2-S nastavíme na 2, kapacity hran mezi partitami na 1. Nalezneme maximální tok, třeba Ford-Fulkersonem. Poté jen ověříme, jestli je maximální tok skutečně perfektní párování, například tak, že velikost toku je rovna 2*N, kde N je počet vrcholů v menší partitě.

3) Máme seno, skládající se z znaků A a B. Máme Fibonacciho slova, definovaná takto: F0 = A, F1 = B, Fn = Fn-1 + Fn-2. Tedy F2 = AB, F3 = BAB. Jaké je nejdelší Fibonacciho slovo, vyskytující se v seně?

Použijeme Aho-Corasick algoritmus a šikovně zkonstruujeme stavový automat jehly. Na začátku bude jehlu tvořit nulový kořen, který bude mít dva syny A a B. Pořídíme si funkci S, která nám pro každý vrchol řekne, jestli se jedná o konec Fibonacciho slova nějaké velikosti. Tedy S(A) = 0, S(B) = 1, kde A B jsou syny nulového kořene. Následně budeme sestavovat automat jehly tak dlouho, až jeden z podstromů kořene bude delší nebo roven délce sena. Střídavě vezmeme levý podstrom kořene a zkopírujeme ho na konec pravého a naopak (Tím vlastně skládáme jednotlivá slova posloupnosti dohromady). Po každém zkopírování vytvořím zpětnou hranu, která povede od konce podstromu, do kterého jsme kopírovali vrcholy, na konec podstromu, odkud jsme vrcholy kopírovali. Pro konec vrcholu pak už jen upravím funkci S tak, aby ho vyhodnotila jako konec slova příslušné velikosti. Na tento stavový automat pustím seno s tím, že si udržuji maximum funkce S pro všechny navštívené vrcholy jehly, což je výsledek.

Úspěšnost nevím, odcházel jsem jako první - ačkoliv měl Mareš drobné výtky, moc se v tom nešťoural a prohlásil, že na jedničku to ještě stačí. Jinak Mareš byl při zkoušce velmi příjemný, rozhodně jedna z nejpříjemnějších zkoušek.
Odpovědět

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