Vi sara' la possibilita' o di accettare il voto del compitino o di
sostenere un breve orale (in data da concordare, ma comunque prima che
riprendano le lezioni)
Il voto del compitino puo' essere conservato anche negli appelli
successivi (sia in sostituzione della prima parte dello scritto, sia
per saltare l'orale sulla prima parte del corso).
Riprendere ed integrare il corso di ASD I anno. In particolare:
illustrare idee generali per sviluppare ed analizzare algoritmi,
algoritmi su grafi, strutture date avanzate, nozioni e risultati
fondamentali di calcolabilita' e complessita' computazionale.
L'esame si suddivide in una prova scritta ed una orale. La prova
scritta consiste di due parti valutate indipendentemente (relative
rispettivamnte alla prima e seconda parte del corso). Per ciascuna
parte sara' dato un tempo prefissato (in genere 2 ore). Durante lo
scritto e' possibile consultare dispense e libri. E' possibile
conservare il voto dello scritto (o anche di una delle 2 parti) negli
appelli successivi, basta non ritentarlo (o non cosegnare quella
parte). La data degli orali viene concordata direttamente con i
docenti.
euristiche: ricerca esaustiva, pruning, branch-and-bound [AHU87, CH 10.3-5]
alcuni ADT e loro implementazioni
(Catania):
dizionario [AHU87, CH 4.5-8]
coda di priorita' [AHU87, CH 4.10-11]
binary search trees [AHU87, CH 5.1-2],
accenni a 2-3 e AVL trees [AHU87 5.4],
B-trees [AHU87 11.4]
grafi e algoritmi su grafi [AHU87, CH 6, 7.1-3]
rappresentazioni
visite DFS e BFS
test di aciclicita'
topological sorting
cammini minimi (vedi anche chiusura transitiva [NOTE])
algoritmi di ordinamento [AHU87, CH 8.3-4]
(Catania):
heapsort,
quicksort
dal divide-et-impera alla programmazione dinamica [NOTE]
numeri di fibonacci
coefficenti binomiali
problema dello zaino
PARTE CALCOLABILITA' e COMPLESSITA'
modelli di calcolo:
TM, RAM, funzioni calcolabili, complessita' tempo e spazio, relazione
tra i due modelli di calcolo, Tesi di Church e Tesi di Church estesa.
calcolabilita':
funzioni calcolabili, problemi/sottoinsiemi decidibili e
semidecidibili, riducibilita' tra problemi, codifica delle TM, TM
universale, esempi di problemi non (semi)decidibili, proprieta' di
chiusura dei sottoinsiemi (semi)decidibili.
complessita':
classi di complessita', relazioni tra classi di complessita' ed
O-notazione, classi naturali di complessita' (P, NP), teorema di Cook,
esempi di problemi NP-completi.
panoramica su altri argomenti di complessita':
accenni ad altri modelli di calcolo (per algoritmi probabilistici e
paralleli), e relative classi di complessita'.
Laurea e Diploma in
Informatica
