Zadanie záverečného testu - cca
Created: 2010-05-11 - 17:14
1. Popíšte vlastnosti problému, na ktorý je možné aplikovať dynamické programovanie (teda, kedy je mozne pouzit dynamiku... optimalna podstruktura, prelinajuce sa podproblemy a pod.) (4b)
2. Klasicka uloha - najdlhsia spolocna podpostupnost... Popisat ideu a ukazat na konkretnom priklade. (6b)
3. a) Povedat ci je pravda - toto co bolo na cviceni - teda ak je graf G(V,E) s ohodnotenymi hranami, tak ak v nom existuje minimalna hrana (x,y), ktora spaja dve mnoziny vrcholov S a V-S, tak patri do minimalnej kostry... (velmi zjednodusene - checknite cvicenia pre podrobne zadanie)
b) Je pravda? Ak mame minimalnu kostru T ohodnoteneho neorientovaneho grafu G, tak potom cesta od vrchola x po y v T je zaroven najkratsiou cestou x,y v G. Toto nie je pravda, da sa na to najst jednoduchy kontrapriklad (preciarknuty stvorec s hranami s hodnotou 1) (8b)
4. Mame orientovany graf reprezentovany zoznamom susednosti (ja som to pochopil tak, ze kazdy vrchol ma sused). Popiste zlozitost funkcii Indegree(v) a Outdegree(v) pre kazdy vrchol v z V. (Indegree je stupen vrchola pre prichadzajuce hrany, outdegree opacne) (6b)
5. Binomicka halda... popisat ako spajame 2 haldy (8b)
6. Algoritmus na dynamiku, ktory bol prezlecenym alg. na zistenie n-teho clena fibonacciho postupnosti. Toto bude asi ine no... Trebalo tam ukazat, ze dany problem sa da riesit dynamikou (podla kriterii z ulohy 1) a navrhnut algoritmus... plus priestorova a casova zlozitost... (8b)
(bodove ohodnotenie uloh je len orientacne... podla toho co si pamätam)