Vaje 3. 3. (Dinamično programiranje 3)
Na teh vajah se boste v skupinah lotili dveh problemov z dinamičnim programiranjem.
Vse skupine bojo imele za nalogo:
- opisati idejo (z vašimi besedami),
- zapisati Bellmanovo enačbo,
- Implementirati zahtevane funkcije.
- Analiza časovne zahtevnosti
- Prikaz izvajanja na testnih primerih (Lahko tudi simulirate izvajanje na različnih velikostih in nato vizualizirate rezultate z npr matplotlib
Na zadnji uri vaj boste kolegom predstavili, do kje ste prišli. Za poročilo (na kratko!) opišite idejo algoritma in Bellmanovo enačbo, ter pripnite končno implementacijo ter rezultate izvajanja na testnih primerih. Poleg tega razmislite tudi, kako jasna je bila predstavitev druge skupine (napišite 1-2 stvari, ki sta bili dobri, ter 1-2 stvari, ki bi jih lahko izboljšali).
Izbira intervalov (z utežmi)
Podan imate seznam intervalov z utežmi: (z_i, k_i, d_i) (začetek, konec in dobiček), ki predstavljajo naloge, ki jih lahko opravite (in kolikšno nagrado dobite, če jih opravite). Vaša naloga je, da ugotovite, katere naloge se vam najbolj izplača opraviti, pri čemer lahko hkrati delate na samo eni nalogi (intervali se ne smejo prekrivati).
- https://en.wikipedia.org/wiki/Activity_selection_problem
- https://en.wikipedia.org/wiki/Interval_scheduling
- https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf
- https://www.geeksforgeeks.org/weighted-job-scheduling/
Levenshteinova razdalja
Levenshteinova razdalja med dvema nizoma je definirana kot najmanjše število sprememb, potrebnih da pretvorimo en niz v drugega, pri čemer so dovoljene spremembe: vstavljanje, brisanje, ali zamenjava enega samega znaka. Sestavi funkcijo, ki za dana dva niza izračuna Levenshteinovo razdaljo med njima. Primer: Levenshteinova razdalja med nizoma "ornitologija" in "otorinolaringolog" je 12.
- http://rosettacode.org/wiki/Levenshtein_distance
- http://en.wikipedia.org/wiki/Levenshtein_distance
- http://wiki.fmf.uni-lj.si/wiki/Levenshteinova_razdalja
- http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html (lepa animacija)
Vsota podmnožic
Imamo seznam celih števil A ter celo število s. Zanima nas, ali obstaja podmnožica množice A, tako da je vsota njenih elementov enaka s. Sestavite funkcijo, ki odgovori na to vprašanje. Kaj pa če nas zanima število takih podmnožic?
Kaj pa, če poleg A in s poznamo še pozitivno število k. Sedaj nas zanima, ali obstajajo podmnožice A_1, ..., A_k, kjer so med seboj disjunktne njihova unija pa je množica A. Poleg tega mora biti vsota vsake podmnožice A_i enaka s. Sestavite funkcijo, ki odgovori na to vprašanje.
- https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
- https://ucilnica.fmf.uni-lj.si/pluginfile.php/58726/mod_resource/content/0/Algorithms-JeffE-dec2018.pdf
- https://en.wikipedia.org/wiki/Subset_sum_problem