Differenze tra le versioni di "Algoritmi e strutture dati T2/2006-2007"

Da WikiDsy.
(→‎Giovedì 19 Ottobre)
(→‎Giovedì 19 Ottobre)
 
(75 versioni intermedie di 7 utenti non mostrate)
Riga 1: Riga 1:
 
[[Categoria:Corsi 2006-2007]]
 
[[Categoria:Corsi 2006-2007]]
 
== News ==
 
== News ==
−
.
 
−
 
−
*'''[http://www.dsi.unimi.it/avviso.php?z=0;pagina=avvisistudenti;id=4438 Calendario Corso nella settimana dal 2 al 13 Ottobre] '''
 
−
 
  
 
----
 
----
Riga 142: Riga 138:
 
=== Giovedì 5 Ottobre 2006 ===
 
=== Giovedì 5 Ottobre 2006 ===
 
'''.''Laboratorio''.'''
 
'''.''Laboratorio''.'''
−
 
+
http://homes.dsi.unimi.it/~aguzzoli/algo.htm
 
*Introduzione alla parte di laboratorio del corso
 
*Introduzione alla parte di laboratorio del corso
 
*Cenni storici sul [http://it.wikipedia.org/wiki/C_(linguaggio) '''linguaggio C''']
 
*Cenni storici sul [http://it.wikipedia.org/wiki/C_(linguaggio) '''linguaggio C''']
Riga 158: Riga 154:
 
=== Venerdì 6 Ottobre 2006 ===
 
=== Venerdì 6 Ottobre 2006 ===
  
−
non sono potuto andare a lezione chi c'era può inserire gli argomenti svolti
+
* Analisi degli algoritmi (cap 2.2)
 +
* Analisi di Counting Sort
  
 
=== Lunedì 9 Ottobre ===
 
=== Lunedì 9 Ottobre ===
Riga 174: Riga 171:
 
*Il concetto di ordinamento in loco
 
*Il concetto di ordinamento in loco
 
*Gli Algoritmi Divide et Impera
 
*Gli Algoritmi Divide et Impera
−
**Merge Sort
+
*[http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/mergeSort/mergeSort.html '''Merge Sort''']
 
**Esempi di merge sort con figure
 
**Esempi di merge sort con figure
 
**Pseudocodice Merge Sort
 
**Pseudocodice Merge Sort
Riga 180: Riga 177:
 
=== Giovedì 12 Ottobre ===
 
=== Giovedì 12 Ottobre ===
 
'''.''Laboratorio''.'''
 
'''.''Laboratorio''.'''
 +
http://homes.dsi.unimi.it/~aguzzoli/algo.htm
 
*riassunto della Prima lezione
 
*riassunto della Prima lezione
 
*printf
 
*printf
Riga 192: Riga 190:
 
=== Venerdì 13 Ottobre ===
 
=== Venerdì 13 Ottobre ===
  
−
  CHI VUOLE AGGIORNARE ?
+
*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 ===
 
=== Lunedì 16 Ottobre ===
Riga 210: Riga 216:
 
*''Il classico (1202!) problema dei conigli ''
 
*''Il classico (1202!) problema dei conigli ''
 
=== Mercoledì 18 Ottobre ===
 
=== Mercoledì 18 Ottobre ===
−
*'''Cap. 3.2''' Ricorrenze  
+
*'''Cap. 4''' Ricorrenze  
 
**Il metodo di sostituzione  
 
**Il metodo di sostituzione  
 
**Il metodo dell’albero di ricorsione  
 
**Il metodo dell’albero di ricorsione  
 
**Il metodo dell’esperto  
 
**Il metodo dell’esperto  
 +
 +
 +
 +
*(Il metodo iterativo (CENNI))
 +
 
*''Il classico (1202!) problema dei conigli ''(soluzione)
 
*''Il classico (1202!) problema dei conigli ''(soluzione)
 +
http://utenti.quipo.it/base5/fibonacci/fibonacci.htm,
 +
 +
yn0n3J  <a href="http://bpxosgzvgfcs.com/">bpxosgzvgfcs</a>, [url=http://dzxnapvhrhug.com/]dzxnapvhrhug[/url], [link=http://ipqzvxjpjlrp.com/]ipqzvxjpjlrp[/link], http://gqekwyuchnpw.com/
 +
 +
=== 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 ===
 +
[http://homes.dsi.unimi.it/~torelli/Grafi%20e%20alberi2e.pdf Dispense usate per questa lezione]
 +
*Grafi e Alberi come Linguaggi
 +
**Grafi Orientati
 +
**Grafi non orientati
 +
*Alberi
 +
 +
 +
===Lunedì 30 Ottobre ===
 +
*[http://homes.dsi.unimi.it/~torelli/Grafi%20e%20alberi2e.pdf '''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 ===
 +
 +
*[http://homes.dsi.unimi.it/~torelli/Gli%20heap2e.pdf '''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
 +
*[http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/quickSort/quick.html '''Quick Sort''']
 +
**Analisi dei costi di Quick Sort
 +
 +
===Mercoledì 8 Novembre===
  
−
=== Giovedì 19 Ottobre ===
+
===Giovedì 9 Novembre ===
 
'''.''Laboratorio''.'''
 
'''.''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
 +
**[http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/radixSort/radixSort.html '''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
 +
si nu ricchion
 +
 +
===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''
 +
 +
[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/e4.zip 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
 +
*[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/e5.zip 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
 +
 +
[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/e6.zip Esercizi]
 +
 +
 +
===Venerdì 19 Gennaio===
 +
 +
*Alberi Ricoprenti minimi
  
−
Il 26 Ottobre si terrà la prima lezione in laboratorio.
+
*Gli algoritmi di Kruskal e Prim
−
Ha raccolto nome, cognome e matricola per attivare l'utenza di laboratorio
 

Versione attuale delle 10:56, 15 gen 2011

Indice

News


.

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,

yn0n3J <a href="http://bpxosgzvgfcs.com/">bpxosgzvgfcs</a>, [url=http://dzxnapvhrhug.com/]dzxnapvhrhug[/url], [link=http://ipqzvxjpjlrp.com/]ipqzvxjpjlrp[/link], http://gqekwyuchnpw.com/

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

si nu ricchion

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


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


Venerdì 19 Gennaio

  • Alberi Ricoprenti minimi
  • Gli algoritmi di Kruskal e Prim
Estratto da "https://wiki.dsy.it/index.php?title=Algoritmi_e_strutture_dati_T2/2006-2007&oldid=20811"