Esame di Fondamenti di Informatica 3.      04.12.2000
=====================================================
Fare un esercizio di ogni gruppo. Verra' apprezzata la
chiarezza e la concisione.

01. Descrivere l'algoritmo di quicksort e
studiarne la complessita' nel caso peggiore e nel caso medio.
02. Descrivere l'algoritmo di heapsort e
studiarne la complessita' nel caso peggiore.
-------
11. Descrivere un algoritmo per la visita breadth-first
di un albero binario del tipo:
    bt = emptytree | leaf(n) | node(bt,n,bt)
    (n e' un numero naturale)
12. Descrivere un algoritmo di calcolo degli anagrammi di una parola
facendo uso del backtracking.
13. Descrivere un algoritmo per la costruzione di tutte le coppie di
nodi zio-nipote "con uguale numero" in un albero binario del tipo:
    bt = emptytree | leaf(n) | node(bt,n,bt)
-------
21. Data una matrice M (nxn), descrivere un algoritmo per
calcolare M*, cioe' la sua chiusura transitiva in tempo proporzionale
a quello della moltiplicazione di due matrici nxn.
22. Dimostrare il teorema di Kuroda.
-------
31. Parlare delle algebre booleane.
32. Parlare del Calcolo proposizionale.
33. Parlare di Programmazione Logica.
-------
41. Descrivere la gerarchia di Chomsky.
42. Descrivere l'algoritmo di parsing per un linguaggio context-free
col metodo di chop-expand (Burstall-Dijkstra).
43. Descrivere il CYK (Cocke-Younger-Kasami) parser per un linguaggio
context-free e studiarne la complessita' temporale
-------
51. Dimostrare l'equivalenza tra automi finiti e espressioni
regolari (Teorema di Kleene)
52. Dati i linguaggi S e R, dimostrare che S*.R e' il minimo
linguaggio X tale che X = S.X U R (Arden rule)
"." denota la concatenazione di linguaggi e "U" l'unione.
=====================================================