UL/FRI/VSP-RI/OAPS2/Izpiti/2006-08-25

1. naloga

Dana je podatkovna struktura drevesa, kjer vsako vozlišče hrani kazalec najbolj levega sina, oceta in desnega brata, če le ta obstaja:

public class TreeLSRSnode extends TreeNode {
public TreeLSRSnode parent, leftSon, rightSibling;
 
}

Sestavi funkciji, ki računata:

a) Stevilo listov z n brati, kjer je n parameter.

b) Povprecno stevilo bratov, ki jih imajo listi.

Definiraj ustrezne parametre in oceni časovno zahtevnost obeh funkcij!

Rešitev a)

Rešitev b)

2. naloga

Dana je kontekstno neodvisna gramatika:

S --> XS | SY | SS | AB
X --> a | AS
Y --> b | SB | SY
A --> a
B --> b

Pri dani gramatiki simuliraj algoritem CYK na besedi abbbab in ugotovi, ce gramatika iz zacetnega simbola S generira dano besedo.

Rešitev

2. naloga

Ali bi algoritmi:

a) Za iskanje kriticne poti po principu dinamicnega programiranja

b) Kruskalov algoritem za iskanje minimalnega vpetega drevesa

c) Dijkstra za iskanje drevesa najkrajsih poti

delovali in ce je odgovor pritrdilen, kaksna bi bila casovna zahtevnost algoritma, ce je izpolnjen eden od spodnjih pogojev (3 krat 3 je 9 argumentiranih odgovorov):

• če graf vsebuje 5.000 vozlisc in 10.000.000 povezav;
• če graf vsebuje povezave z negativno dolzino
• če graf vsebuje dve vozlisci in eno povezavo.

Rešitev a)

Rešitev b)

Rešitev c)

4. naloga

Sestavi algoritem za stetje nenegativnih stevil iz danega polja realnih stevil, definiraj pogoje, ki jih mora izpolnjevati vhodno polje stevil (ki lahko vsebuje tudi negativna stevila) ter dokazi parcialno pravilnost svojega programa. Neobvezno (za dodatnih 10 točk): dokazi totalno pravilnost tega algoritma.

Rešitev