ALGORITMI E STRUTTURE DATI
Algoritmi: correttezza e complessita' di calcolo. Due casi esemplari: l'algoritmo di Euclide e il problema del sacco (knapsack). La filosofia avida (greedy). La notazione asintotica di Landau (O grande). Il teorema maestro (o principale, master theorem).
Algoritmi di ordinamento: insertion sort, merge sort, heap sort, quicksort. La filosofia del divide et impera. Algoritmi di ordinamento lineari: counting sort, bucket sort.
Strutture dati elementari: array, liste, pile, code, alberi.
Grafi e loro rappresentazioni. Visita in ampiezza BFS e visita in profondita' DFS. Ordinamento topologico per grafi aciclici orientati DAG. L'algoritmo di Dijkstra.
La filosofia della programmazione dinamica. La distanza di Levenstejn (edit distance).
***********************
Il seguito riguarda solo il corso da 9 cfu.

Generazione di bit pseudo-casuali tramite registri a scorrimento (cenni). NP-completezza e algoritmi approssimati (cenni). Controlli di primalita' e algoritmi probabilistici (cenni). Problemi di matching di stringhe: l'algoritmo ingenuo, l'algoritmo di Karp-Rabin, matching mediante automi finiti.
TESTI di RIFERIMEMTO:
1. Th.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Cl. Stein: Introduzione agli algoritmi e strutture dati; Mc Graw Hill
2. C. Demetrescu, I. Finocchi, G.F. Italiano: Algoritmi e strutture dati; Mc Graw Hill
3. A. Bertossi, A. Montresor:  Algoritmi e strutture di dati; Citta' Studi
4. P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi: Strutture di dati e algoritmi; Pearson

Academic year 2015-16

COMPLESSITA' COMPUTAZIONALE (vedi sotto !!!!!)

COMPLEXITY THEORY: P and NP problems, deterministic and non-deterministic computation. Some basic NP-complete decision problems, NP-hard problems. How to get along with NP-completeness (partial, approximate and probabilistic algorithms).

Textbook: M.R. Garey, D.S. Johnson: Computers and Intractability. Freeman, New York

SOFT COMPUTING: Artificial intelligence: philosophy of soft computing. Management of uncertainty and ignorance. Imprecise probabilities, possibility theory, evidence theory. Dempster rule for pooling opinions. Management of vagueness, fuzzy logic and multyi-valued logics. Fuzzy arithmetic. Fuzzy control.

Textbook: A. Sgarro, Livre flou, to be found at www.dmi.units.it/~sgarro/html

!!!!!! COMPUTABILITA' E COMPLESSITA' e COMPLEMENTI DI INFORMATICA e simili sono MUTUATI a carico di COMPLESSITA' COMPUTAZIONALE e COMPUTABILITA' E LINGUAGGI, vedi sotto, da parte di MATEMATICA in un ordine da concordare ad personam (contattatemi !)

COMPUTABILITA' E LINGUAGGI

Primo modulo: a cura del prof. Fr. Fabris (teoria della computabilità)

Secondo modulo a cura mia: contenuti descritti sotto Automi e linguaggi formali

    AUTOMI e LINGUAGGI FORMALI: Automi finiti e lingue regolari. Computazione deterministica e non deterministica. Espressioni regolari di Kleene. Grammatiche acontestuali (context-free). Proprieta' di stabilita' e lemmi di espansione (pumping). Forme normali di Chomsky. Ambiguita'. Automi a pila (pushdown). Grammatiche contestuali (context-sensitive). Grammatiche generali e macchine di Turing decisionali.
TESTI di RIFERIMENTO: 1. M. Sipser: Introduction to the Theory of Computation; PWS Publishing. - 2. G. Ausiello, F. D'Amore, G. Gambosi: Linguaggi, modelli, complessita'; Franco Angeli - 3. J.H. Hopcroft, R. Motwani, J.D. Ullman:  Introduction to Automata Theory, Languages, and Computation; Addison Wesley.
    SOFT COMPUTING: Intelligenza artificiale: la filosofia del soft computing e del calcolo verbale. Gestione dell'incertezza e dell'ignoranza: Richiami sulle probabilita' bayesiane. Probabilita' imprecise; teoria delle possibilita', teoria dell'attestabilita' (evidence theory). Aggiornamento e sintesi (pooling) delle conoscenze: la regola di Bayes e la regola di Dempster-Shafer. Gestione della vaghezza: logica sfocata (logica sfumata, fuzzy logic) e logiche multivalenti. Insiemi sfocati e aritmetica sfocata. Controllo sfocato.
TESTO di RIFERIMENTO: A. Sgarro, Livre flou, reperibile all'indirizzo www.dmi.units.it/~sgarro/html