Algoritmi e strutture dati T2/2006-2007

News

. Torelli farà lezione anche Lunedì 22 e Mercoledì 24 gennaio)

---

.

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ì 9 Novembre

.Laboratorio.

• Svolti esercizi in aula attrezzata

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

Venerdì 10 Novembre

NON ERO A LEZIONE!

Lunedì 13 Novembre

• Ordinamento in tempo lineare
  • Counting Sort
  • Bucket sort
  • Radix Sort
• Limite inferiore per il problema dell'ordinamento
  • Albero delle decisioni per dimostrare il limite inferiore del problema dell'rdinamento
• L'algoritmo di Strassen (dalle dispese)

Mercoledì 15 Novembre

• Hash
• Tabelle Hash

Giovedì 16 Novembre

• Laboratorio

• Classi di memorizzazione
  • auto
  • extern
  • register
  • static
• RICORSIONE
  • Efficenza nella ricorsione
• Backtracking
  • Esempio Il gioco del cavallo
• Array
• Puntatori
• Aritmetica dei Puntatori

Venerdì 17 Novembre

• Strutture Dati Elementari
  • Stack
    • Operazioni su lo stack
  • Code
    • Operazioni su le code
  • Liste

Lunedì 20 Novembre

• Numeri di Matula

Mercoledì 22 Novembre

• Ripasso Alberi
• Hash
  • Tabelle Hash
  • Funzioni Hash
  • Il metodo della divisione
  • Il metodo della moltiplicazione
  • Hashing Universale
  • Hashing Perfetto

Giovedì 23 Novembre

• Laboratorio

• Svolti esercizi in aula PC

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

Venerdì 24 Novembre

• Ancora Hashing
  • Analisi dell hashing con concatenamento
  • Metodo Divisione e Moltiplicazione
  • Indirizzamento Aperto
  • Il Doppio Hashing

Lunedì 27 Novembre

• Alberi Binari
• Alberi Binari di ricerca
• Visita di Alberi
  • In Ordine
  • In Pre-Ordine
  • In Poost-Ordine
• Propietà Alberi Binari di ricerca
  • Ricerca del Minimo e del Max
  • predecessore e successore
  • inserimento e Cancellazione di una elemento
• Alberi Binari costruiti a caso

Mercoledì 29 Novembre

• Ripasso lezione precedente (visite alberi, max-min,successore predecessore..)
• Il linguaggio di Dyck
• Funzioni generatrici di alberi

Giovedì 30 Novembre

Laboratorio

• Arirmetica dei puntatori
• Allocazione Dinamica della Memoria
  • Malloc
  • Calloc
  • Free
  • Esempio MergeSort
• Manipolazione delle stringhe
• Array Multidimensionali
• Passare argomenti a Main
• Puntatori a funzioni

Venerdì 1 Dicembre

• I B-alberi
  • Operazioni su alberi B-ari
  • propietà
• Accenni agli Alberi rosso neri

Lunedì 4 Dicembre

• Gli Alberi Rosso-Neri
  • Propietà
  • Operazioni

Mercoledì 6 Dicembre

Non ero a lezione

Giovedì 7 Dicembre

        Festa

Venerdì 8 Dicembre

      Festa

Lunedì 11 Dicembre

• Programmazione Dinamica
  • Esempio Catena di Montaggio
  • Edempio prodotto di matrici

Mercoledì 13 Dicembre

• Programmazione Dinamica
• Dimostrazione soluzione ottima
• Breve introduzione hai problemi NP-COMPLETI
  • Problema commesso viaggiatore

Giovedì 14 Dicembre

Laboratorio

Esercizi

Venerdì 15 Dicembre

       Non ero a lezione

Lunedì 18 Dicembre

• Algoritmi Greedy
  • Esempio Attività

Mercoledì 20 Dicembre

• I Matroidi (Appunti Torelli)
  • Sistema d'indipendenza
  • Restrizioni e Rango
  • I Matroidi in relazione agli algoritmi GREEDY

Giovedì 21 Dicembre

Laboratorio

• Strutture - struct

• Unioni

• Typedef

• Stack (questa volta realizzato con memoria dinamica)

• Liste concatenate
  • operazioni sulle liste

• Liste Dopiamente Concatenate
  • Modifica delle operazioni

• Liste con la sentinella

• Le code

Lunedì 8 Gennaio

• Ancora sui matroidi

Mercoledì 10 Gennaio

• Analisi Ammortizzata
  • metodo del contabile
• Rapresentazione dei grafi
  • Matrici di adiacenza
  • Liste di adiacenza

Giovedì 11 Gennaio

Laboratorio

• Esercizi in aula attrezzata

Venerdì 12 Gennaio

• Analisi ammortizzata
• Strutture Dati per insiemi disgiunti
• funzione di ackermann

Lunedì 15 Gennaio

Lezione di laboratorio

• Le strutture dati nel C
• Gli alberi
  • Alberi Binari
  • Alberi di ricerca

ha detto il prof Aguzzoli che la prox lezione di laboratori (Giovedì 18 Gennaio prima finirà il programma)

Mercoledì 17 Gennaio

• ha ripreso la funzione di Ackermann
• Funzioni Ricorsive primitive
• ha iniziato il capitolo di Algoritmi per grafi
  • Algoritmi di visita di un grafo
    • In ampiezza
    • in profondità

Giovedì 18 Gennaio

Lezione di laboratorio

Prima parte finite dispense C

• Gli Alberi
• Alberi Bilanciati
  • Alberi Rosso-Neri in c

Esercizi