Visualizza wikitesto di Algoritmi e strutture dati Turno 2/2005-2006

[[Categoria:Corsi 2005-2006]]
<!-- non cancellare le righe precedenti -->

'''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 [http://it.wikipedia.org/wiki/Huffman Huffman]
*[http://it.wikipedia.org/wiki/Legge_di_Zipf 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''':

*[http://it.wikipedia.org/wiki/Linguaggio_imperativo Linguaggio imperativo]
*Linguaggio di basso livello
*[http://it.wikipedia.org/wiki/Programmazione_strutturata Programmazione strutturata]
*Definizione di funzione
*[http://it.wikipedia.org/wiki/Compilatore Compilatore]
*Fasi di compilazione: [http://it.wikipedia.org/wiki/Preprocessing 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
*[http://it.wikipedia.org/wiki/Insertion_sort 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''':

*[http://it.wikipedia.org/wiki/Insertion_sort 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''':

*[http://it.wikipedia.org/wiki/Numero_di_Fibonacci Numeri di Fibonacci]
*Formula Eulero Binet