Algoritmi e strutture dati T2/2006-2007

Da WikiDsy.

Indice

News

. LUNEDI 15 GENNAIO CI SARA' LEZIONE CON AGUZZOLI E NON CON TORELLI



.

Informazioni generali

.

Docenti


Prof. Torelli / Prof. Aguzzoli per il laboratorio.

Corsi di laurea


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


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


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.



Altro materiale consigliato

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

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

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

Lunedì 6 Novembre

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

Mercoledì 8 Novembre

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
  • 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