Programma del corso
Corso di Laurea in Informatica Umanistica
Anno Accademico 2012-13
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, G. Rossi.
Strutture di dati e algoritmi.
Pearson 2012, seconda edizione.
Riferimento: CGGR
Questo libro si propone di spiegare l'algoritmica in modo informale e leggero: fornisce letture introduttive agli argomenti trattati a lezione. Vi si espongono con semplicità le nozioni su cui è basata la costruzione di algoritmi e si mostra come, inaspettatamente, le stesse nozioni si incontrino nella letteratura e nella storia, nell'antropologia e nelle fiabe, guidando il lettore non esperto attraverso un territorio altrimenti ostico.
Anno Accademico 2008-2009
F.Luccio, L.Pagli.
Algoritmi, divinità e gente comune.
Edizioni ETS 1999.
Anno Accademico 2009-2010
Anno Accademico 2010-2011
Anno Accademico 2011-2012
Risultati compiti scritti
Anno Accademico 2012-2013
Anno Accademico 2013-2014
Introduzione al corso.
Definizioni di problema e algoritmo.
Algoritmo di moltiplicazione egizia.
Analisi di un problema semiserio.
Il problema delle dodici monete
Seminario introduttivo alla complessità degli algoritmi tenuto dal prof. Romani
Libro CGGR: Introduzione.
Modello RAM e complessità computazionale
Principali costrutti di programmazione
Prologo Libro CGGR.
Notazioni O grande, Omega e Theta definizione e uso.
Algoritmi di Ricerca sequenziale e loro complessita&grave.
Prologo;
e pp.67-69 Libro CGGR.Introduzione
Algoritmi di ordinamento InsertionSort e SelectionSort, analisi, limite inferiore per il problema.
Introduzione Libro CGGR. Capitolo1
Problema della ricerca. Limite inferiore. Algortimo di Ricerca Binaria non ricorsivo. Introduzione alla ricorsione.
pp.14-15 Libro CGGR.par 3.3
Algortimo di Ricerca Binaria ricorsivo. Tecnica del Divide et Impera. Algoritmo del torneo. Equazioni di ricorrenza.
Libro CGGR.par.3.1, 3.2 e 3.3
Esercitazione: esercizi su modifica di algoritmi noti e su Divide et Impera.
Algoritmo di Merge. MergeSort: definizione, simulazione e analisi.
Libro CGGR.par.3.1
Esercitazione: algoritmi diversi per il problema dell'intersezione di due insiemi con analisi di complessità. Eliminazione di occorrenze ripetute con o senza compattazione.
Ordinamento di elementi che valgono solo 0 o solo 1. Quicksort e partition: definizione, analisi simulazione.
QuickSort.
Esercitazione. Esercizi di applicazione della tecnica Divide et Impera e di valutazione della complessità
Esercizi
Ordinamento in tempo lineare: il CountingSort. Numeri di Fibonacci: definizione e algoritmi di generazione.
Ordinamento lineare
I numeri di Fibonacci
La Programmazione Dinamica. Il problema dell'Edit Distance.
Programmazione dinamica
Apparizioni approssimate di una stringa X breve in una stringa Y lunga come estensione dell'Edit Distance.Codice per l'Edit Distance.
Array bidimensionali, algoritmi di percorrenza.
esercitazione: Esercizi su ordinamento lineare e programmazione dinamica.
Problemi polinomiali e esponenziali. Le torri di Hanoi, algoritmo ricorsivo, crescita esponenziale. Problemi nella classe NP: il problema del sottografo completo.
Eulero e il problema del ciclo euleriano. Il problema del ciclo hamiltoniano. Grafi: definizioni e rappresentazione con matrici di adiacenza. Numero massimo e minimo di archi.
pag. 123-126 Libro LP.
Grafi: Rappresentazione con matrici di adiacenza. Visite DFS e BFS. Procedura ricorsiva DFS. Esempi.
grafi
Alberi liberi, alberi con radice, esempi e terminologia. Rappresentazione con parentesi e visite in ordine anticipato e differito. Alberi binari e alberi binari di ricerca. Visita in ordine simmetrico.
Libro CGGR.pag. 114-116
alberi
Esercitazione: esercizi di ripasso presi da vecchi compiti