Algoritmi e strutture dati T2/2006-2007

News

.

• La prossima lezione di laboratorio Giovedì 26 Ottobre si terrà ina aula attrezzata 309 (VIA CELORIA)

---

.

Informazioni generali

.

Docenti

---

Prof. Torelli / Prof. Aguzzoli per il laboratorio.

Corsi di laurea

---

• Informatica

Modalità d'esame

---

Orale + Progetto Pagina Ufficiale Modalita' d'esame

N.B

• Non è possibile sostenere l'orale senza aver già consegnato il progetto
• il progetto e l'orale devono essere svolti nello stesso appello

---

Orari e luogo delle lezioni

Lunedì	Mercoledì	Giovedì(laboratorio)	Giovedi (laboratorio)	Venerdì
18:30-20:00 Aula 202 (celoria).	20:00-21:30 Aula 202 (celoria).	18:30-19:30 Aula 202.	19:30-21:30 Aula PC settore didattico .	18:30-20:00 Aula 202 (celoria).

Orario di ricevimento studenti

• Lunedì ore 10 -11 e martedì ore 18 -19, Via Comelico

-

Informazioni specifiche

Sito Ufficale del corso

• SITO UFFICIALE DEL CORSO (TORELLI)

N.B. Il Prof.Torelli tiene un Diario del corso sul suo sito che è sicuramente è più affidabile di quello che ci sforziamo di tenere sul dsy, riteniamo comunque utile portare avanti questo diario nella speranza che possa esser una risorsa aggiuntiva, non limitandosi a fornire un elenco degli argomenti svolti, ma più in generale fornendo notizie e informazioni sul corso, link e materiale inerente alle lezioni

Sito Ufficiale del laboratorio

• SITO UFFICIALE DEL LABORATORIO (AGUZZOLI)

Forum dsy Algoritmi

Forum su DSY.IT

Materiale Didattico

Programma del corso

Si può scaricare da qui

TESTI

---

Testo di riferimento

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill Italia, 2005 (oppure II edizione in inglese, 2002).

---

Altri Bibliografia

Testo per il laboratorio:

• Al Kelley, Ira Pohl, C – Didattica e programmazione, Pearson/Addison-Wesley, 2004 (oppure A Book on C, 4a edizione, in inglese).

Bibliografia di consultazione:

• M. Torelli, Appunti per il corso di Algoritmi e Strutture Dati, scaricabili da http://homes.dsi.unimi.it/~torelli/note.html
• A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso di Algoritmi e Strutture Dati), scaricabili da http://homes.dsi.unimi.it/~goldwurm/algo/
• R. Sedgewick, Algoritmi in C/C++, Addison-Wesley, 1993 (nuova edizione ampliata 2002).
• A.J. Kfoury, R.N. Moll, M.A. Arbib, A programming approach to computability, Springer, 1982.

---

Video delle lezioni

Le Videolezioni dell'anno accademico 2003/2004 sono disponibili sul sito Virtual Classroom

DISPENSE E LINK UTILI

Dispense prof Goldwurm

dispense Università di Urbino

dispense Università dell' Aquila

Compilatore GCC per Windows

Diario del corso

.

Lunedì 2 Ottobre 2006

• Introduzione al corso e alle modalità di esame
• Complessità del problema dell'ordinamento
  • che cosa si intende per complessità di un algoritmo
• Algoritmo di Counting Sort (altro link utile per capire il counting sort)
• Introduzione alle notazioni asintotiche O , Θ e Ω

Mercoledì 4 Ottobre 2006

• Ripasso Algoritmo Counting Sort - .link utile .per capire il counting sort
• Il concetto di algoritmo di ordinamento Stabile
• La complessità di un Algoritmo
• La complessità di un Problema
• Confrontare la coplessità di algoritmi
• Definizione formale delle notazioni asintotiche e relativi esempi
  • O O Grande(Limitato superiormete)
  • Ω Omega Grande (Limitato inferiormente)
  • Θ Theta(limite asintotico stretto)

Giovedì 5 Ottobre 2006

.Laboratorio. http://homes.dsi.unimi.it/~aguzzoli/algo.htm

• Introduzione alla parte di laboratorio del corso
• Cenni storici sul linguaggio C
• Caratteristiche generali del C
• Lo standard ANSI C
• primo programmino in c (il consueto Ciao Mondo)
• Il compilatore (useremo Gcc)
• Le direttive al preprocessore
  • Include
  • i file .h
• Il concetto di funzione
• Opzioni di Gcc
  • -ansi , -pedantic , -wall

Venerdì 6 Ottobre 2006

• Analisi degli algoritmi (cap 2.2)
• Analisi di Counting Sort

Lunedì 9 Ottobre

• Gli algoritmi probabilistici e la loro utilità
  • Accenni all'Algoritmo di Rabin Miller
• il concetto di Struttura di Dati
  • cosè una struttura di dati
  • la struttura di dati (dati+operazioni)
  • il concetto di Arità
• Introduzione di alcune strutture di dati: pila o stack , Alberi di ricerca binarif , Heap
• Insertion Sort

Mercoledì 11 Ottobre

• Insertion Sort
• Il concetto di ordinamento in loco
• Gli Algoritmi Divide et Impera
  • Merge Sort
  • Esempi di merge sort con figure
  • Pseudocodice Merge Sort

Giovedì 12 Ottobre

.Laboratorio. http://homes.dsi.unimi.it/~aguzzoli/algo.htm

• riassunto della Prima lezione
• printf
  • Opzioni di printf
• altri semplici programmini di esempio
• C ed il passaggio per valore
• L'utility make
• introduzione ai puntatori
• Bubble sort
• Introduzione agli Array in C

Venerdì 13 Ottobre

• Merge Sort: Albero delle chiamate ricorsive
• Notazioni standard e funzioni comuni:
  • Funzione Floor
  • Funzione Ceiling
  • Funzione Monotone
  • Fattoriale
  • Formula di Stirling
  • Piccolo Teorema di Fermat
• Ricorsione e Iterazione

Lunedì 16 Ottobre

• Cap. 3.2 NOTAZIONI STANDARD E FUNZIONI COMUNI
  • Funzioni Monotone
  • Floor e ceiling
  • Aritmetica modulare
  • Polinomi
  • Esponenziali
  • Logaritmi
  • Fattoriali
  • Iterazione di una funzione

• Ricorsione o ricorrenza
• teorema di Fermat

• Il classico (1202!) problema dei conigli

Mercoledì 18 Ottobre

• Cap. 4 Ricorrenze
  • Il metodo di sostituzione
  • Il metodo dell’albero di ricorsione
  • Il metodo dell’esperto

• (Il metodo iterativo (CENNI))

• Il classico (1202!) problema dei conigli (soluzione)

http://utenti.quipo.it/base5/fibonacci/fibonacci.htm,

Giovedì 19 Ottobre

.Laboratorio.

Il 26 Ottobre si terrà la prima lezione in laboratorio. Sono state racolti i dati ( nome, cognome e matricola ) per attivare l'utenza di laboratorio

http://homes.dsi.unimi.it/~aguzzoli/algo.htm

• Le stringhe sono array
• Elementi lessicali, operatori, espressioni
• Dichiarazioni, tipi fondamentali

Venerdì 20 Ottobre

come nella scorsa lezione

• Cap. 4 Ricorrenze
  • Il metodo di sostituzione
  • Il metodo dell’albero di ricorsione
  • Il metodo dell’esperto

Esempi di utilizzo dei 3 metodi su la ricorsione

Lunedì 23 Ottobre

• Ancora ricorsione
• Numeri di Fibonacci
• La formula di Eulero-Binet

Mercoledì 25 Ottobre

• la formula di Eulero - Binet
• nozioni di insiemistica(unione,intersezione....relazioni)
• Accenno ai linguaggi

Giovedì 26 Ottobre

.Laboratorio.

• Svolti esercizi in aula attrezzata

http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/e1.zip

Venerdì 27 Ottobre

Dispense usate per questa lezione

• Grafi e Alberi come Linguaggi
  • Grafi Orientati
  • Grafi non orientati
• Alberi

Lunedì 30 Ottobre

• I Grafi come linguaggi
  • Grafi Orientati
  • Grafi Non orientati
  • Cammini e Cicli
  • Lemma di Eliminazione dei cicli
  • Il concetto di Grado di un vertice
  • Grafi connessi
  • sottografi
• Alberi Binari
• Alberi k-Ari
• Alberi Completi a sx.
• alberi pienamente Binari
• Heap

Mercoledì 1 Novembre

Festa

Giovedì 2 Novembre

.Laboratorio.

• Inuput ed Output con getchar e putchar
• Input ed Output su file
• Operatori logici
• Controllo del flusso
  • If - Else
  • for
  • While
  • Do-While
  • Break
  • Continue
  • Switch
• Funzioni e stack
• Protottipi di funzione

Venerdì 3 Novembre

• Heap . (Dispense usate a lezione)
• La struttura dati Heap
  • Costruzione di un Heap
  • Heapify
• Uso degli Heap per implementare code con priorità
• Heap sort

Lunedì 6 Novembre

• Heap
  • Heap Sort
  • Analisi dei costi di Heapsort
• Quick Sort
  • Analisi dei costi di Quick Sort

Giovedì 26 Ottobre .Laboratorio.

Giovedì 9 Novembre

.Laboratorio.

• Svolti esercizi in aula attrezzata

http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/e2.zip