Programma del corso
Corso di Laurea in Informatica Umanistica
Anno Accademico 2009-10
6 crediti
| Docente | Linda Pagli
|
||||
| Orario |
|
||||
| Ricevimento |
|
Modalità d'esame
- L'esame consiste in una prova scritta e eventulamente in una prova orale.
- Durante la prova scritta è vietato consultare libri o appunti.
Bibliografia
Risulta quanto mai difficile parlare formalmente di Algoritmi senza disporre di una sufficiente "base matematica". Pertanto in questo corso di Algoritmica per InformaticaUmanistica cercheremo di lasciare da parte gli aspetti formali di "analisi degli algoritmi" e ci concentreremo sui principi e sulle tecniche di progettazione, accennando alla loro complessità. Date queste premesse, non stato possibile identificare un libro di testo che trattasse di Algoritmica in modo preciso ma "non formale". Qui di seguito si "suggerisce" un libro di testo che riporta (quasi) tutti gli pseudo-codici degli algoritmi che discuteremo in classe. Il libro però è molto tecnico e quindi poco appropriato per la laurea in InformaticaUmanistica. Lo seguiremo per ciò che concerne la formalizzazione degli pseudo-codici degli algoritmi; gli studenti potranno d'altra parte utilizzare un qualunque altro libro per ciò che riguarda la discussione delle proprietà e della complessità di questi algoritmi. Materiale aggiuntivo relativo alle singole lezioni, verrà segnalato nel registro delle lezioni.
P.Crescenzi, G.Gambosi, R.Grossi.
Strutture di dati e algoritmi.
Pearson-Addison Wesley 2006.
Testi prove scritte
Anno Accademico 2008-2009
Anno Accademico 2009-2010
- Pre-Appello: testo
- Appello1: testo e soluzione
- Compitino: testo e soluzione
- Appello 1: testo
- Appello 2: testo
- Appello 3: testo
- Appello 4: testo
Risultati compiti scritti
- Compitino: Risultati del Compito del 17/12/2009
- Primo Appello: Risultati del Compito del 7/1/2010
- Secondo Appello: Risultati del Compito del 1/2/2010
- Terzo Appello: Risultati del Compito del 7/6/2010
- Quarto Appello: Risultati del Compito del 29/6/2010
Registro delle lezioni
N Data Argomenti Riferimenti 1 23/09 Introduzione al corso. Introduzione al concetto di algoritmo.
Algoritmo di moltiplicazione egizia.2 25/09 Il problema delle 12 monete.
Il problema delle dodici monete 3 30/09 Il modello RAM e la complessità computazionale. Par. 1.4 del testo 4 02/10 Ricerca sequenziale e ricerca binaria. Algoritmi, analisi e limite inferiore. Par. 2.4 del testo 5 07/10 Algoritmi ricorsivi. Calcolo del fattoriale.Le torri di Hanoi. Par. 1.2 del testo
Algoritmi ricorsivi.6 09/10 Principio di induzione. Tecnica del Divide et Impera. Ricerca binaria ricorsiva. Equazioni di ricorrenza Par. 2.5 del testo
7 14/10 Divide et impera; equazioni di ricorrenza principali e loro soluzioni. Ordinamento per selezione. Par. 2.2.1 del testo
8 16/10 Ordinamento per selezione: QuickSort, analisi caso pessimo, caso ottimo. Confronto con selection Sort Par. 2.5.4 del testo, analisi del caso medio esclusa.
9 21/10 Algoritmo ottimo di ordinamento per confronti: Merge-Sort. Analisi e limite inferiore per il problema. Par. 2.5.3 del testo,
Limiti inferiori10 23/10 Esercitazione: Unione, intersezione e differenza di insiemi. Algoritmi che utilizzano o meno l'ordinamento preventivo. Confronto tra le diverse soluzioni. 11 28/10 Ordinamento in tempo lineare. Algoritmo, discussione sulla complessità. 12 30/10 Esercitazione: problemi di ricerca e ordinamento. Esercizi e soluzioni 13 04/11 Array bidimensionali. Numeri di Fibonacci, definizione e calcolo. Algoritmi di varia complessità Introduzione alla Programmazione Dinamica. Par. 2.7 del testo.
I numeri di Fibonacci14 06/11 l problema dell'edit distance. Algoritmo di programmazione dinamica, con spazio quadratico e con spazio ottimo. La programmazione dinamica 15 11/11 Edit Distance: ricostruzione dell'allineamento. Cenni ai problemi NP-completi. Par. 1.2.2, 1.3 del testo
I problemi NP-completi16 13/11 Esercitazione: problemi riassuntivi. Esercizi e soluzioni 17 18/11 Esercitazione: problemi riassuntivi. Esercizi e soluzioni 18 20/11 Esercitazione: problemi riassuntivi. Esercizi e soluzioni 19 02/12 Cenni ai problemi che non posseggono un algoritmo di risoluzione. Numerabilità e indecidibilità L'indecidibilità 20 04/12 Esercitazione: problemi riassuntivi 21 17/12 Esercitazione scritta Esercizi e soluzioni