Koutecký - 18.6.2020 - skupina B

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

Koutecký - 18.6.2020 - skupina B

Příspěvek od ERRORCEK »

Z prednášiek:
  • 1. Borůvkův algoritmus + dokázať pomocné tvrdenia (myslím, že na rezové lemma sa stačí odkázať, samotné lemma netreba dokazovať :?: )
  • 2. Dolný odhad zložitosti pre triedenia (nie je potrebný až ten precízny z průvodce, úplne stačí napísať myšlienky dôkazov)
Z cvičení:
  • 1. Majme dva roboty v bludisku. Vieme ich ovládať príkazmi Sever, Juh, Východ, Západ. Oba vykonávajú rovnaký príkaz naraz. Keď robot dostane príkaz, ktorý nemôže vykonať (narazil by do steny), tak ho ignoruje. Ako nájdeme postupnosť príkazov, ktorými oboch roboty vyvedieme z bludiska? Akonáhle je robot vonku z bludiska, zastaví sa a príkazy už ignoruje.
  • 2. (príliš ťažká) Konvexní mnohouholník vieme triangulovať t.j. vieme rozdeliť na trojuholníky neprekrývajúcimi sa uhlopriečkami. Navrhnite algoritmus, ktorým nájdeme takú trianguláciu, kde súčet dĺžok použitých uhlopriečok je minimálny možný (Minimum-weight triangulation problem)
  • 2. (alternatívna) Nájdite maximálny počet všetkých nezávislých vrcholov v strome. Platí teda pre ne \forall u, v \in M: uv \notin E(T). Stačí počet, nemusíme ich vedieť vypísať


V 1. úlohe stačí pustiť BFS-ko na stavový graf, ktorý postupne budujeme. V grafe ukladáme pozície oboch robotov, štart je teda ich počiatočná pozícia a cieľ, keď oba roboty sú vonku. Popísať zložitosť, tá je O(n^4) pre bludisko n \times n. Z každej pozície vieme ísť štyrmi smermi a pozícií robota je n \times n, čiže možných stavov je 4 * (n \times n)^2, čiže O(n^4)
V druhej úlohe idea je, že LISS(x) nám vráti počet nezávislých vrcholov v strome s koreňom x.

Kód: Vybrat vše

LISS(x) =  MAX{(1 + súčet LISS všetkých potomkov X), (súčet LISS všetkých synov X)}
Vieme to spraviť rekurzívne, no to je príšerne pomalé (zbytočne opakovane rátame niektoré vrcholy), čiže to spravíme dynamickým programovaním, tak, že vrcholy budú niesť informáciu liss od seba nižšie a vyriešime to zdola nahor. Hodnota sa bude počítať, len ak už nie je spočítaná (!=0) a nadobudne hodnotu súčtu LISS synov alebo 1+súčet LISS vnukov, resp. 1 ak je vrchol listom
Odpovědět

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