13.01.2005, 9:30, F2, 2 hodiny na pisanie
1. (14b) Dynamicke programovanie - vysvetlite metodu a pouzite na priklade KSP 213 (O sucte). Aka je zlozitost vasho riesenia? (Ma byt menej ako O(n^2))
2. (14b) Rozdeluj a panuj - vysvetlite metodu a pouzite na priklade KSP 535 (O sachovnici).
3. (12b) A je matica cien hran grafu G(V,E). A(i,j)=0 <=> hrana (i,j) neexistuje, A(i,j)>0 => vzd miest i,j je A(i,j). Je dane pole B[1..6] indexov do V 6 kandidatskych miest. Treba z nich vybrat 4, z ktorych sa budu zasobovat vsetky mesta. (Pre kazde mesto vyrazi z najblizsieho skladu ine auto, ktore sa vecer vrati.) Napiste co najefektivnejsi algoritmus, ktory urci tie mesta, ktorych vyber minimalizuje celkovy pocet km najazdenych vsetkymi autami pocas dna. Dokazte korektnost vasho algoritmu. Aka je zlozitost? Nestaci hadat - odovodnite.
4. (10b) Zadefinujte (vysvetlite) ulohu o max. toku. Vysvetlite, co je rezervna polocesta. Vysvetlite zakladny algoritmus na jej riesenie, ktory vyuziva rezervne polocesty. Aka je zlozitost tohto algoritmu?