
DIPARTIMENTO DI INFORMATICA Università di Torino

Modulo 1 (lezioni in Aula)

del corso di Algoritmi & Laboratorio (anno Accademico 2004-2005)

Docente: Ferruccio DAMIANI

ATTENZIONE:

Il contenuto di questo documento sarà continuamente aggiornato durante il corso.
Siccome
1. "1 CFU = 9 ore in aula + 16 ore di studio/lavoro individuale"
2. ogni settimana ci sono 6 ore di lezione in aula
per essere in grado di superare l'esame ogni studente dovrebbe dedicare (indicativamente) circa 10 ore di studio/lavoro individuale agli argomenti proposti durante le 6 ore settimanali di lezione in aula.
L'orario delle lezioni in aula e' il seguente (con inizio Mercoledi' 29 Settembre 2004):
- Martedi' 11-13 in Aula C
- Mercoledi' 11-13 in Aula C
- Venerdi' 11-13 in Aula C
A volte ci saranno delle lezioni nel seguente orario (IL DOCENTE LE ANNUNCERA' IN AULA, INOLTRE TALI LEZIONI COMPARIRANNO CON QUALCHE GIORNO DI ANTICIPO NELL' "ELENCO DELLE LEZIONI" RIPORTATO IN QUESTO DOCUMENTO):
- Lunedi' 14:00-16:00 in Aula C --- in tal caso (salvo diverse indicazioni fornite dal docente) siccome queste due ore di lezione (comuni a tutti e tre i turni) sottraggono due ore di laboratorio al turno 1:
  - il Mercoledi' successivo, gli studenti del TURNO 2 faranno solo 2 ore di esercitazioni in laboratorio, e
  - il Venerdi' successivo, gli studenti del TURNO 3 faranno solo 2 ore di esercitazioni in laboratorio.

ELENCO DELLE LEZIONI

NOTA: Molti dei "lucidi" proiettati a lezione (riportati nel seguito) costituiscono una rielaborazione (in alcuni casi minima, in altri consistente) di lucidi sviluppati

dal Prof. Ugo de'Liguoro per il Modulo 1 del corso di Algoritmi & Sperimentazioni dell'aa 2003/2004 (si segnala che il Prof. Ugo de'Liguoro tiene entrambi i moduli del corso di Algoritmi & Sperimentazioni dell'aa 2004/2005),
dalla Prof.ssa Maddalena Zacchi per il Modulo 1 del corso di Algoritmi & Laboratorio dell'aa 2003/2004,
dagli autori del libro Algoritmi e strutture dati , McGraw-Hill, 2004 (si ringrazia la McGraw-Hill per aver autorizzato la distribuzione di questo materiale agli studenti).
Di norma la "provenienza" dei lucidi e' segnalata. Eventuali errori contenuti nei lucidi (e, in generale, nelle pagine web del corso) sono da imputarsi unicamente al docente del presente corso (al quale andrebbero prontamente segnalati).
SUGGERIMENTO: stampate la versione dei lucidi raggiungibile dai link "stampe".
ATTENZIONE: STUDIARE SOLO SUI LUCIDI E SUGLI APPUNTI PRESI A LEZIONE NON PERMETTE DI RAGGUNGERE UN LIVELLO DI PREPARAZIONE SUFFICIENTE PER SUPERARE L'ESAME. All'esame (sia alla prova scritta per il Modulo 1 che al colloquio per il Modulo 2) sono richiesti dettagli e approfondimenti che (per ovvie ragioni di tempo) non possono essere considerati a lezione. E' QUINDI NECESSARIO STUDIARE SUI "RIFERIMENTI" (E FARE GLI ESERCIZI ASSEGNATI DAL DOCENTE). I lucidi e gli appunti presi a lezione sono una guida per lo studio dei "riferimenti". Dopo ogni lezione (o ciclo di lezioni dedicate ad un dato argomento) studiate sui "riferimenti" e, se qualcosa non vi e' chiaro, chiedete spiegazioni al docente all'inizio della lezione successiva!!!

I riferimenti tra parentesi graffe {...} sono relativi ad approfondimenti, che conviene ignorare ad una prima lettura. [Dem] abbrevia Demetrescu et al, Algoritmi e strutture dati; [Hor] abbrevia Horstmann, Concetti di informatica e fondamenti di Java 2; [Arn] abbrevia Arnold et al, Java, manuale ufficiale. Altri riferimenti sono forniti alle pagine web relative alle lezioni/esercitazioni del modulo 2 TENUTE IN AULA: il contenuto di tali lezioni sara' oggetto della prova scitta del modulo 1, quindi il contenuto di tali lezioni deve essere studiato anche da chi deve solo sostenere la parte di esame relativa al modulo 1.

Date	Orari	Lucidi	Riferimenti	Esercizi	Note
Mercoledi' 29/9	11:00-12:00	Introduzione (stampe)	Alcune utili relazioni
Mercoledi' 29/9 Venerdi' 1/10 Martedi' 5/10	12:00-13:00 11:00-13:00 11:00-13:00	Problemi e algoritmi (stampe) Correttezza degli algoritmi iterativi (stampe)	[Hor] pag.54-58(Sezione 2.8, Consigli per la produttivita' 2.2). [Hor] pag.82-83(Suggerimenti per la qualita' 3.1). [Hor] pag.89-90(Consigli per la produttivita' 3.1). [Hor] pag.94(Suggerimenti per la qualita' 3.2). [Hor] pag.99-101(Consigli per la produttivita' 3.2, Suggerimenti per la qualita' 3.3 e 3.4). [Hor] pag.104-107(Consigli pratici 3.1). [Hor] pag.116-117(Consigli per la produttivita' 3.3) [Hor] pag.193-195(Argomenti avanzati 5.1, Suggerimenti per la qualita' 5.1, Consigli per la produttivita' 5.1). [Hor] pag.201(Suggerimenti per la qualita' 5.2). [Hor] pag.204-206(Argomenti avanzati 5.2, Consigli per la produttivita' 5.2). [Hor] pag.211-213(Suggerimenti per la qualita' 5.3, Consigli per la produttivita' 5.3). [Hor] pag.240-242(Note di cronaca 6.1). [Hor] pag.246-248(Suggerimenti per la qualita' 6.1, Argomenti avanzati 6.2). [Hor] pag.250(Suggerimenti per la qualita' 6.2). [Hor] pag.256-258(Argomenti avanzati 6.4 e 6.5). [Hor] pag.263-267(Suggerimenti per la qualita' 6.3 e 6.4, Consigli pratici 6.1). [Hor] pag.275-278(Argomenti avanzati 6.8, Note di cronaca 6.2). [Hor] pag.748-767(Appendici A1 e A2).
Mercoledi' 6/10 Venerdi' 8/10	11:00-13:00 11:00-13:00	Verifica della correttezza dei cicli "for" (stampe) Correttezza degli algoritmi ricorsivi (stampe) Strutture dati (stampe)	[Hor] pag. 603-626(fino alla sezione 15.5 esclusa)	Assegnati nei lucidi.	L'esercizio E1 del modulo 2 si riferisce allo pseudo-codice contenuto nei lucidi fino a "Ricorsione". L'esecizio E2 del modulo 2 si riferisce ai lucidi "Strutture dati".
Martedi' 12/10 Mercoledi' 13/10 Venerdi' 15/10	11:00-13:00 11:00-13:00	L'efficienza degli algoritmi (stampe) Complessita' 1 (stampe) Complessita' 2 (stampe) Complessita' 3 (stampe)	[Dem] pag. xv-xviii(prefazione). [Dem] pag. 1-21(capitolo 1). [Dem] pag. 23-47,55-59(capitolo 2, escluse le sezioni 2.7 e 2.8).	Assegnati nei lucidi.
Martedi' 19/10	11:00-13:00	Svolgimento di esercizi alla lavagna: [Dem] Problema 2.5 (i primi 6 punti).		[Dem] Problema 2.5 (l'ultimo punto).
Mercoledi' 20/10	11:00-13:00	Introduzione alle collezioni (stampe) Lower bound e upper bound (stampe)	[Dem] pag. 61-80(capitolo 3). [Dem] pag. 419-430(appendice, fino alla sezione 17.5 esclusa).	Assegnati nei lucidi.
Venerdi' 22/10	11:00-13:00	LA LEZIONE E' SOSPESA a causa dello sciopero nazionale dei mezzi di trasporto.
Martedi' 26/10	11:00-13:00	LA LEZIONE E' SOSPESA in quanto il Senato Accademico (S.A.) ha indetto un dibattito sulla condizione della docenza universitaria, il 26 ottobre, dalle ore 10.00 alle ore 13.00, nell'Aula 1 di Palazzo Nuovo. In tali ore e' sospesa l'attivita' didattica. Le esercitazioni in laboratorio per il turno 1 (dalle 16:00 alle 18:00) si terranno regolarmente.	Intervento del Rettore in apertura della seduta del S.A. del 15/10/04, Comunicato stampa relativo alla Mozione del S.A. del 15/10/04, Avviso: a tutto il personale universitario (studenti inclusi).
Mercoledi' 27/10 Venerdi' 29/10	11:00-13:00 11:00-13:00	Ordinamento (stampe)	[Dem] pag. 81-113(capitolo 4).	Assegnati nei lucidi.
Martedi' 2/11 Mercoledi' 3/11	11:00-13:00 11:00-13:00	Alberi di ricerca (stampe) Code con priorita' (stampe)	[Dem] pag. 133-146,165-168(capitolo 6, escluse le sezioni 6.3,6.4,6.5,6.6). [Dem] pag. 187-192,207-209(capitolo 8, escluse le sezioni 8.2,8.3).	Assegnati nei lucidi.
Lunedi' 8/11	14:00-16:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA C) E' AL DI FUORI DELL'ORARIO CONSUETO. Tavole hash (stampe) Insiemi, mappe, e dizionari (stampe)	[Dem] pag. 169-185(capitolo 7).	Assegnati nei lucidi.
Martedi' 9/11	11:00-13:00	Union-find (stampe)	[Dem] pag. 211-236(capitolo 9).	Assegnati nei lucidi.
Venerdi' 12/11 Martedi' 16/11	11:00-13:00 11:00-13:00	Tecniche algoritmiche: divide et impera (stampe), programmazione dinamica (stampe), greedy (stampe).	[Dem] pag. 237-261(capitolo 10).	Assegnati nei lucidi.
Mercoledi' 17/11 Venerdi' 19/11	11:00-13:00 11:00-13:00	Grafi: introduzione (stampe), Grafi: visite (stampe),	[Dem] pag. 430-435(appendice, dalla sezione 17.5 inclusa fino alla fine). [Dem] pag. 263-287(capitolo 11).	Assegnati nei lucidi.
Lunedi' 22/11	14:00-16:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA C) E' AL DI FUORI DELL'ORARIO CONSUETO. Svolgimento di esercizi alla lavagna .
Martedi' 23/11 Mercoledi' 24/11 Venerdi' 26/11	11:00-13:00 11:00-13:00 11:00-13:00	Grafi: visita generica (stampe), Grafi: visita in ampiezza (stampe), Grafi: visita in profondita' (stampe), Grafi: ordinamento topologico (stampe), Grafi: componenti fortemente connesse (stampe).	[Dem] pag. 289-300(capitolo 11). [Dem] pag. 327-329(solo la sezione 13.4.1).	Assegnati nei lucidi.
Venerdi' 26/11	14:00-16:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA B) E' AL DI FUORI DELL'ORARIO CONSUETO. Svolgimento di esercizi alla lavagna .
Lunedi' 29/11	14:00-16:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA C) E' AL DI FUORI DELL'ORARIO CONSUETO. Grafi: minimo albero ricoprente (stampe), Grafi: ancora minimo albero ricoprente (stampe)	[Dem] pag.301-312,314-318(capitolo 12, esclusa la sezione 12.4).
Martedi' 30/11	11:00-13:00	LA LEZIONE E' SOSPESA a causa dello sciopero generale dell'intera giornata dei lavoratori dell'Universita', degli enti pubblici di ricerca, dell'ENEA, dell'AFAM contro: LE RIFORME CHE DEVASTANO IL SISTEMA DELLA RICERCA E DELL'ALTA FORMAZIONE PUBBLICA, IL TAGLIO DEI FINANZIAMENTI, IL "PRECARIATO INFINITO".	Che cos'e' il DDL Moratti. Un volantino del coordinamento contro il DDL-Moratti. Un volantino sindacale.
Mercoledi' 1/12	11:00-13:00	Grafi: cammini minimi (stampe), Grafi: ancora cammini minimi (stampe)	[Dem] pag.319-336,338-345(capitolo 13, esclusa la sezione 13.6).
Venerdi' 3/12	11:00-13:00	LA LEZIONE E' SOSPESA a causa di inderogabili impegni del docente.
Lunedi' 6/12	11:00-13:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA B) E' AL DI FUORI DELL'ORARIO CONSUETO (di solito in questo orario si tiene una lezione di Fondamenti dell'Informatica). Svolgimento di esercizi alla lavagna .
Lunedi' 6/12	16:00-18:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA C) E' AL DI FUORI DELL'ORARIO CONSUETO. Svolgimento di esercizi alla lavagna .
Martedi' 7/12	11:00-13:00	Svolgimento di esercizi alla lavagna .
Martedi' 7/12	16:00-18:00	ATTENZIONE: QUESTA LEZIONE (TENUTA IN AULA C) E' AL DI FUORI DELL'ORARIO CONSUETO. Svolgimento di esercizi alla lavagna .	...	...

[Corso di Studi di Informatica]


	Last update: Dec 17, 2004