Programma del corso
  Bibliografia
  Modalità di esame
  Testi prove scritte
  Risultati compiti
  Registro delle lezioni

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.

  Errata corrige

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.

  F.Luccio, L.Pagli.
  Algoritmi, divinità e gente comune.
  Edizioni ETS 1999.

 

 

 

 

 

 

---

Testi prove scritte

---

Anno Accademico 2008-2009

• Pre-Appello: testo
• Appello1:   testo e soluzione

Anno Accademico 2009-2010

• Compitino:   testo e soluzione

---

 

 

 

 

 

 

---

Risultati compiti scritti

---

• Compitino: Risultati del Compito del 17/12/2010
• Primo Appello: Risultati dello scritto del 14/1/2011
• Secondo Appello: Risultati dello scritto del 4/2/2011 testo e soluzione
• Terzo Appello: Risultati dello scritto del 6/6/2011
• Quinto Appello: Risultati dello scritto del 7/7/2011
• Sesto Appello: Risultati dello scritto del 9/9/2011
• Appello dell'11/1/2012: Risultati dello scritto dell'11/1/2012

 

 

 

 

 

 

---

Registro delle lezioni

---

N	Data	Argomenti	Riferimenti
1	04/10	Introduzione al corso. Il concetto di algoritmo. Algoritmo di moltiplicazione egizia. Il problema delle 12 monete.	Il problema delle dodici monete
2	07/10	Il modello di computazione RAM. Complessità dei costrutti fondamentali IF, FOR, WHILE. Il problema della ricerca. Algoritmi di ricerca sequenziale.	Par. 1.4 del testo n.1
3	11/10	Il problema della ricerca. La ricerca binaria. Analisi. Crescita lineare e crescita logaritmica, confronto.	Par. 2.4.1 del testo n.1
4	15/10	Problema della ricerca: limite inferiore. Algoritmi ricorsivi. Calcolo del fattoriale.	Algoritmi ricorsivi.
5	15/10	Esercitazione: Ricerca e eliminazione in multi-insiemi con e senza compattazione: Soluzione n*occ(k) e soluzione lineare.
6	19/10	Problema delle Torri di Hanoi, algoritmo, analisi. Principio di induzione. Crescita esponenziale.	Par. 1.2 del testo 1. Cap.1 del testo 2.
7	22/10	Divide et impera. Ricerca binaria ricorsiva. Conto delle occorrenze. Determinazione del minimo. Ordinamento per selezione.	Par.2.4.1, 2.4.2, 2.5 del testo 1.
8	25/10	Merge: defnizione e analisi. MegeSort, codice e simulazione.	Par.2.4.3 del testo 1.
9	30/10	Procedura Merge. Soluzioni principali equazioni di ricorrenza. Ordinamento ottimo di 3 elementi. Limite inferiore del problema dell'ordinamento	Par. 2.5.3 del testo 1, Limiti inferiori
10	30/10	Esercitazione: Ricerca dell'elemento moda in insiemi non ordinati e ordinati. Modifica di SelectionSort, ove a ogni iterazione si seleziona minimo e massimo.
11	04/11	Numeri di Fibonacci, definizione e calcolo. Algoritmi di varia complessità.	I numeri di Fibonacci
12	12/11	Algoritmi di ordinamento: QuickSort.Algortimo Distribuzione. Valutazione caso pessimo, caso ottimo e caso medio. Ricorrenze.	Par.2.5.4 fino a pag. 52 primo capoverso (compreso), del testo 1.
13	12/11	Esercitazione. Unione, Intersezione e differenza tra due insiemi ordinati in tempo lineare. Esercizio di interpretazione di codice.
14	19/11	Algoritmo di ordinamento in tempo lineare. Discussione sull'applicabilità. Definizione degli ordini di grandezza "O" e "Omega". Rappresentazione e scansione di tabelle bidimensionali.	Ordinamento lineare
15	19/11	Esercitazione. Esercizi di scorrimento di matrici bidimensionali per righe per colonne e a serpentina. Casi di ordinamento lineare
16	2/12	La tecnica della programmazione dinamica. Numeri di Fibonacci. Il problema dell'edit distance.	La programmazione dinamica
17	6/12	Edit distance: ricostruzione allineamento.Il problema dello String matching.
18	9/12	Calcolabilittà: Problemi indecidibili, il problema dell'arresto. Problemi intrattabili, problemi NP-completi. Problema del sottografo completo. Problemi del ciclo Euleriano e del ciclo Hamiltoniano.	Par. 1.2.2, 1.3 del testo 1 I problemi NP-completi L'indecidibilità
19	9/12	Esercitazione: esercizi riassuntivi	Soluzioni compitino 17/12/2008
20	13/12	alberi, alberi binari, visita anticipata e simmetrica; alberi binari di ricerca in confronto alla ricerca binaria, inserzione, eliminazione; Cenni alla memorizzazione di alberi.	par. 4.1 e 5.4.1 del testo 1.
21	17/12	Esercitazione scritta.	Esercizi