Differenze tra le versioni di "Algoritmi e strutture dati Turno 2/2005-2006"

Da WikiDsy.
 
(18 versioni intermedie di 7 utenti non mostrate)
Riga 1: Riga 1:
−
'''Algoritmi e strutture dati''' è un corso fondamentale del 2° anno di informatica
+
[[Categoria:Corsi 2005-2006]]
−
=== Docenti === Mauro Torelli e Camillo Fiorentini
+
<!-- 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 ===
 
=== Orari delle lezioni ===
Riga 27: Riga 33:
 
=== Materiale didattico ===
 
=== Materiale didattico ===
  
−
'''"Introduzione agli algoritmi e strutture dati"''' Seconda edizione McGraw-Hill (Cormen, Leiserson, Rivest, Stein)
+
''"Introduzione agli algoritmi e strutture dati"'' Seconda edizione McGraw-Hill (Cormen, Leiserson, Rivest, Stein)
  
−
Per il laboratorio va bene qualsiasi libro di C ANSA
+
Per il laboratorio va bene qualsiasi libro di C ANSI
  
 
Consigliati:
 
Consigliati:
  
−
'''"C didattica e programmazione"''' 4° edizione
+
''"C didattica e programmazione"'' 4° edizione
  
 
oppure
 
oppure
  
−
'''"Il linguaggio C. Principi di programmazione e manuale di riferimento."''' 2° Edizione
+
''"Il linguaggio C. Principi di programmazione e manuale di riferimento."'' 2° Edizione
 +
 
 +
Il compilatore di riferimento è GCC.
  
−
Il compilatore di riferimento è GCC.
 
 
=== Links utili ===
 
=== Links utili ===
  
 
http://www.algoteam.dsi.unimi.it/
 
http://www.algoteam.dsi.unimi.it/
 +
 +
http://streaming.dico.unimi.it per videolezioni
  
 
=== Modalità d'esame ===
 
=== Modalità d'esame ===
Riga 53: Riga 62:
  
 
'''Argomenti trattati nella lezione di oggi''':
 
'''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

Versione attuale delle 07:28, 26 lug 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:

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:

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:

Estratto da "https://wiki.dsy.it/index.php?title=Algoritmi_e_strutture_dati_Turno_2/2005-2006&oldid=14566"