Algoritmi, Programmi e Modelli di Calcolo: Algoritmi e Problemi - Programma - Le risorse di calcolo, l’irrisolubilità, l’intrattabilità - Il concetto di complessità applicata agli algoritmi - Definizione e proprietà delle notazioni O, Θ, Ω - Complessità applicata ai problemi - Algoritmi ottimali - Funzioni limitate polinomialmente, a crescita moderatamente esponenziale, a crescita esponenziale - Complessità degli algoritmi espressi in pseudo-codice - Regole per il calcolo di O
Liste, Pile e Code: Lista non ordinata - Lista ordinata - Pila - Coda
Algoritmi Ricorsivi e l’approccio Divide et Impera: Introduzione - Linguaggi che consentono la ricorsione - Un esempio: visita di un albero binario - Introduzione al Divide et Impera - Il Merge Sort - Il concetto di bilanciamento - Teorema Principale per analizzare gli algoritmi basati sull’approccio Divide et Impera
Le heaps: Le code con priorità - Le heaps: ricerca del minimo, inserimento, cancellazione del minimo, costruzione - Heapsort
Tecniche Hash: Caratteristiche ed esempi di funzioni hash note - Gli schemi ad indirizzamento aperto: tecniche di scansione, implementazione e complessità - Tecniche a concatenamento: introduzione ed analisi della complessità – Il BucketSort
Grafi: Grafi orientati - Grafi non orientati -Visite dei grafi - Visita in ampiezza - Visita in profondità - Rappresentazione di grafi - Rappresentazione mediante lista - Rappresentazione mediante matrice
Alberi: Alberi liberi - Alberi orientati - Alberi binari - Vista di un albero binario - Rappresentazione degli alberi binari - Alberi binari di ricerca
Minimo Albero Ricoprente: Formulazione del problema - La soluzione greedy – L'Algoritmo di Prim - L’algoritmo di Kruskal
Programmazione Dinamica: Moltiplicazione in serie di matrici - Algoritmo per calcolare i cammini minimi tra tutte le coppie di vertici di un grafo pesato orientato - Algoritmo per calcolare la chiusura transitiva di un grafo orientato

Algoritmi e strutture dati
Docente: Acciaro Vincenzo
SSD: INF/01
Corso di Laurea: CLEII (9)
Dipartimento di afferenza: Dipartimento di Ingegneria e Geologia
Numero di telefono: 085-4537704
E-mail: v.acciaro@unich.it
Giorni ed orario di ricevimento studenti: su appuntamento
Semestre: II
Obiettivi: Definire formalmente la nozione di algoritmo e di modello di calcolo. Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Progettare algoritmi corretti ed efficienti attraverso l'esame di diversi paradigmi.
Programma del corso (articolato in moduli):
Algoritmi, Programmi e Modelli di Calcolo: Algoritmi e Problemi - Programma - Le risorse di calcolo, l’irrisolubilità, l’intrattabilità - Il concetto di complessità applicata agli algoritmi - Definizione e proprietà delle notazioni O, Θ, Ω - Complessità applicata ai problemi - Algoritmi ottimali - Funzioni limitate polinomialmente, a crescita moderatamente esponenziale, a crescita esponenziale - Complessità degli algoritmi espressi in pseudo-codice - Regole per il calcolo di O
Liste, Pile e Code: Lista non ordinata - Lista ordinata - Pila - Coda
Algoritmi Ricorsivi e l’approccio Divide et Impera: Introduzione - Linguaggi che consentono la ricorsione - Un esempio: visita di un albero binario - Introduzione al Divide et Impera - Il Merge Sort - Il concetto di bilanciamento - Teorema Principale per analizzare gli algoritmi basati sull’approccio Divide et Impera
Le heaps: Le code con priorità - Le heaps: ricerca del minimo, inserimento, cancellazione del minimo, costruzione - Heapsort
Tecniche Hash: Caratteristiche ed esempi di funzioni hash note - Gli schemi ad indirizzamento aperto: tecniche di scansione, implementazione e complessità - Tecniche a concatenamento: introduzione ed analisi della complessità – Il BucketSort
Grafi: Grafi orientati - Grafi non orientati -Visite dei grafi - Visita in ampiezza - Visita in profondità - Rappresentazione di grafi - Rappresentazione mediante lista - Rappresentazione mediante matrice
Alberi: Alberi liberi - Alberi orientati - Alberi binari - Vista di un albero binario - Rappresentazione degli alberi binari - Alberi binari di ricerca
Minimo Albero Ricoprente: Formulazione del problema - La soluzione greedy – L'Algoritmo di Prim - L’algoritmo di Kruskal
Programmazione Dinamica: Moltiplicazione in serie di matrici - Algoritmo per calcolare i cammini minimi tra tutte le coppie di vertici di un grafo pesato orientato - Algoritmo per calcolare la chiusura transitiva di un grafo orientato
Libri di testo consigliati: dispense del docente
Modalità di verifica dell’apprendimento: prova scritta ed esame orale