Algoritmi e strutture dati Turno 2/2005-2006

Algoritmi e strutture dati è un corso fondamentale del 2° anno di informatica.

Docenti

Mauro Torelli e Camillo Fiorentini

Orari delle lezioni

• Lun 15.30 - 17.30(effettivo: 15.55 - 17.25) IN AULA G24
• Mar 15.30 - 17.30(effettivo: 15.55 - 17.25) IN AULA G24
• Mer 15.30 - 18.30 LABORATORIO C IN AULA G24
• Ven 16.30 - 19.30(effettivo: 17.00 - 18.30) IN AULA G21

Orario di ricevimento studenti

• venerdì ore 18.30 precise in aula G11 al Settore Didattico (Via Golgi) solo se c'è lezione

oppure

• lunedì ore 10-11 nello studio del professor Torelli(P105) al DSI – Via Comelico.

Sito del corso

http://homes.dsi.unimi.it/~torelli/algoritmi.html

http://homes.dsi.unimi.it/~fiorenti/labalg05.html per laboratorio

Materiale didattico

"Introduzione agli algoritmi e strutture dati" Seconda edizione McGraw-Hill (Cormen, Leiserson, Rivest, Stein)

Per il laboratorio va bene qualsiasi libro di C ANSI

Consigliati:

"C didattica e programmazione" 4° edizione

oppure

"Il linguaggio C. Principi di programmazione e manuale di riferimento." 2° Edizione

Il compilatore di riferimento è GCC.

Links utili

http://www.algoteam.dsi.unimi.it/

http://streaming.dico.unimi.it per videolezioni

Modalità d'esame

L’esame consisterà prima in un progetto in C con l'utilizzo degli algoritmi studiati col professor Torelli e, chi passa il progettino, farà un orale (di solito 40 minuti).

Diario del corso

Lezione di Lunedì 3-10-05

Argomenti trattati nella lezione di oggi:

• Codice Huffman
• Legge di Zipf
• Definizione di algoritmo ottimo
• Definizione di codice
• Definizione di prefisso
• Definizione di codice prefisso

Lezione di Martedì 4-10-05

Argomenti trattati nella lezione di oggi:

• Prodotto di concatenazione
• Lunghezza di una parola
• Proprietà del prodotto di concatenazione (associatività)
• Prodotto di due linguaggi
• Chiusura di Kleene
• Definizione di alberi completi
• Albero pienamente binario

Lezione di Mercoledì 5-10-05

Argomenti trattati nella lezione di oggi:

• Catena di addizione generata da L
• Dimostrazione che il codice di Huffman è ottimo
• Insieme indipendente massimo di un grafo
• Insieme indipendente massimale di un grafo
• Fattore
• Trasposizione
• Parola semplice
• Grafo orientato
• Sottocammino
• Ciclo
• Grafo non orientato
• Grado di un vertice
• Cappio
• Cammino di lunghezza k
• Vertice isolato

Lezione di Venerdì 7-10-05 (LAB)

Argomenti trattati nella lezione di oggi:

• Linguaggio imperativo
• Linguaggio di basso livello
• Programmazione strutturata
• Definizione di funzione
• Compilatore
• Fasi di compilazione: preprocessing, compilazione vera e propria, linker
• Funzioni di libreria

Lezione di Venerdì 10-10-05

Argomenti trattati nella lezione di oggi:

• Ciclo nei grafi non orientati
• Grafo connesso
• Cammino semplice
• Sottografo
• Grafo aciclico
• Albero libero
• Albero radicato
• Linguaggio ereditario
• Profondità di un nodo
• Altezza di un albero
• Albero binario

Lezione di Venerdì 11-10-05

Argomenti trattati nella lezione di oggi:

• Linguaggio binario
• Codifica di un albero
• Albero k-ario
• Albero ordinato ristretto a k figli
• Algoritmo select sort (solo accennato, non c'è nel libro). Scandisce tutto l'array dall'ultimo elemento al primo. Viene cercato l'elemento max per ogni iterazione. L'elemento max viene scambiato col corrente.
• Heap
• Albero binario completo

Lezione di Venerdì 12-10-05 (LAB)

Argomenti trattati nella lezione di oggi:

• Funzione
• Programma
• Variabile
• Creata funzione lireToEuro che converte lire in euro
• Fasi di compilazione

Lezione di Venerdì 14-10-05

Argomenti trattati nella lezione di oggi:

Lezione di Venerdì 17-10-05

Argomenti trattati nella lezione di oggi:

• Ordinamento parziale
• Analisi ammortizzata
• Relazione di ricorrenza
• Nell'heap length[A] dove A è un array contenente gli elementi dell'heap, heap_size[A]
• Heapify
• Heapsort

Lezione di Venerdì 18-10-05

Argomenti trattati nella lezione di oggi:

• Coda di priorità
• Proprietà insert maximum extract-max
• Algoritmo
• Insertion sort

Lezione di Venerdì 19-10-05 (LAB)

Argomenti trattati nella lezione di oggi:

• Cast
• Dati due punti(ognuno con ascissa e ordinata) abbiamo costruito una funzione che calcoli l'area del rettangolo costruito
• Ombreggiamento

Lezione di Venerdì 24-10-05

Argomenti trattati nella lezione di oggi:

• Insertion sort
• Calcolo del caso peggiore

Lezione di Venerdì 25-10-05 (LAB)

Argomenti trattati nella lezione di oggi:

• Espressione
• Puntatori
• Data una frazione semplificarla

Lezione di Venerdì 2-11-05

Argomenti trattati nella lezione di oggi:

• Numeri di Fibonacci
• Formula Eulero Binet