UL/FRI/VSP-RI/PJ/Vaje/2006-01-10

Naloge iz izpitov

Najbolj neprazno binarno drevo je predstavljeno z b(L,El,D)

(levo poddrevo, element, desno poddrevo; element = koren drevesa)

Prazno drevo se predstavi z nil. Sestavi program, ki bo preveril, če je dano drevo kopica.

(kopica = levo poravnano drevo ki ima v korenu manjši element od vseh elementov v levem in desnem poddrevesu)

b(b(b(nil,66,nil),65,b(nil,112,nil)),19,b(nil,25, b(nil, 30,nil))))

lahko pišemo tudi kot

b(
  b(
    b(
      nil,
      66,
      nil),
   65,
   b(
     nil,
     112,
     nil)
   ),
 19,
 b(
   nil,
   25,
   b(
     nil,
     30,
     nil)
    )
  )
)

Drevo ni levo poravnano, torej ni kopica.

b(b(b(nil,66,nil),65,b(nil,112,nil)),19,b(nil,25,nil)))

Drevo je kopica.

b(b(b(nil,66,nil),67,b(nil,112,nil)),19,b(nil,25,nil)))

Drevo ni kopica.

Program, ki preveri, ali je kopica ali ni.

heap(b(Levo,Element,Desno)):-
  number(Element), Z is Element-1,
  heap(b(Levo,Element,Desno),Z).
heap(b(Levo,Element,Desno),Koren):-
  Levo = nil,
  !,
  Desno = nil,
  Koren < Element; % velja, ce je levo poddrevo prazno.
  Koren < Element,
  heap(Levo,Element),
  heap(Desno,Element). % preverimo se levo in desno poddrevo.
heap(A,Min):-
  A = nil,
  !;
  number(A),
  A >= Min,
  !.

Dvoumnost gramatike

gramatika
S -> SS | a

aaa
leva izpeljava
S -> SS -> SSa -> aaa
desna izpeljava
S -> SS -> aSS -> aaa

ni dvoumna, ker v isti smeri lahko naredimo samo 1 izpeljavo

gramatika
S -> SS | a | aa

aaa
leva izpeljava
S -> SS -> Saa -> aaa
S -> SS -> aSS -> aaa

je dvoumna, ker lahko v isti smeri naredimo več izpeljav