Računalništvo (FMF)/Vaje/2. kolokvij 2006-2007

Iz MaFiRaWiki


1. naloga

Poišči vsa optimalna iskalna dvojiška drevesa za simbole a < c < e < g < i. Frekvence pojavitev simbolov so p=\frac{1}{32}(4,2,4,2,4), frekvence ponesrečenih iskanj pa q=\frac{1}{16}(2,1,2,1,1,1).

2. naloga

Na kupu imamo n knjig, debelin d_1,d_2,\cdots,d_n. Knjige zlagamo na polico dolžine D. Pri tem bi želeli

  • P1 : na polico zložiti čimveč knjig.
  • P2 : minimizirati neuporabljen prostor na polici.
  1. Formuliraj oba problema, kot problema kombinatorične optimizacije.
  2. Reši problem P1 s požrešno metodo.
  3. Reši problem P2 z lokalno optimizacijo. Definiraj kriterijsko funkicijo in opiši okolico dane dopustne rešitve.
  4. Ali lahko prevedeš katerega od problemov P1 in P2 na kakšnega od znanih problemov?

3. naloga

Za dani niz S in vzorec V želimo ugotoviti, če se niz S ujema z vzorcem V. Vzorec je sestavljen iz običajnih znakov ter posebnih simbolov * in ?. S simbolom * se lahko ujema poljubno zaporedje nič ali več znakov, s simbolom ? pa poljuben posamičen znak. Tako se na primer niz abcde ujema z vzorci ab*e, *c*d*e, a?c*, ne pa z *??b*. Problem reši z metodo dinamičnega programiranja. Zapiši rekurzivno enačbo in opiši učinkovit način njenega reševanja. Pokaži delovanje tvojega postopka na zgornjem primeru.

4. naloga

V AVL drevo po vrsti vstavi elemente

20,5,77,55,33,10,44,25,50,21,100,60,40,37,

nato pa iz drevesa po vrsti izbriši števila

30,21,44,10,100,40,77.

Dokler ne izvedeš rotacije, lahko delaš na isti sliki, sicer nariši novo drevo!

Osebna orodja