|
|
| Riga 1: |
Riga 1: |
| − | [[Categoria:Corsi 2007-2008]]
| |
| | | | |
| − | ===AVVISI===
| |
| − | * La prima lezione di laboratorio sarà martedì 2 ottobre in aula '''G11''' (Settore Didattico, via Celoria)
| |
| − | * La lezione di martedì 2 ottobre non si terrà.
| |
| − | * Da giovedi 11 ottobre le lezioni ed i laboratori tranne il laboratorio di venerdì si svolgeranno in aula V2
| |
| − | *Nuova variazione: il laboratorio di martedì si svolge in aula '''309'''
| |
| − |
| |
| − | === Orari ===
| |
| − | * ''Lezione''
| |
| − | ** '''Lunedì''', 10:30-12:30, aula V2
| |
| − | ** '''Martedì''', 08:30-10:30, aula V2
| |
| − | ** '''Giovedì''', 08:30-10:30, aula V2
| |
| − | ** '''Venerdì''', 10:30-12:30, aula 405
| |
| − |
| |
| − | * ''Laboratorio''
| |
| − | ** '''Martedì''', 10:30-12:30, aula 309
| |
| − | ** '''Giovedì''', 10:30-12:30, aula V2
| |
| − |
| |
| − | ===Scaglione alfabetico ===
| |
| − |
| |
| − | Il turno è unico.
| |
| − |
| |
| − | ===Docenti===
| |
| − |
| |
| − | [http://homes.dsi.unimi.it/~goldwurm/home.html Massimiliano Goldwurm] (teoria)
| |
| − |
| |
| − | [http://homes.dsi.unimi.it/~fiorenti/ Camillo Fiorentini] (laboratorio)
| |
| − |
| |
| − | ===Programma===
| |
| − | * [http://homes.dsi.unimi.it/~goldwurm/algo/#PROGRAMMA Programma del corso]
| |
| − | * [http://homes.dsi.unimi.it/~goldwurm/algo/#PROGLAB Programma di laboratorio]
| |
| − |
| |
| − | ===Orari ricevimento===
| |
| − | * [http://homes.dsi.unimi.it/~goldwurm/algo/#ORARI Massimiliano Goldwurm]
| |
| − | * [http://homes.dsi.unimi.it/~fiorenti/labalg07.html Camillo Fiorentini]
| |
| − |
| |
| − | ===Altre informazioni e links===
| |
| − | * [http://homes.dsi.unimi.it/~goldwurm/algo/#ESAMI Modalità d'esame]
| |
| − | * [http://dsy.it/forum/forumdisplay.php?s=&forumid=207 Forum di Algoritmi su DSY]
| |
| − | * [http://dsy.it/forum/forumdisplay.php?s=&forumid=25 Files di Algoritmi su DSY]
| |
| − |
| |
| − | ===Siti del corso===
| |
| − | *[http://homes.dsi.unimi.it/~goldwurm/algo/ Sito del corso]
| |
| − | *[http://homes.dsi.unimi.it/~fiorenti/labalg07.html Sito del laboratorio]
| |
| − |
| |
| − | ===Materiale didattico===
| |
| − |
| |
| − | *[http://homes.dsi.unimi.it/~goldwurm/algo/#TESTI Dispense e testi consigliati]
| |
| − | *[http://homes.dsi.unimi.it/~goldwurm/algo/#TEMI Esercizi e temi d'esame]
| |
| − | *Ultimi temi d'esame ([http://homes.dsi.unimi.it/~goldwurm/algo/ultimitemi.ps ps],[http://homes.dsi.unimi.it/~goldwurm/algo/ultimitemi.pdf pdf])
| |
| − |
| |
| − | ==Diario del corso==
| |
| − |
| |
| − | ===Lezione 01/10/2007===
| |
| − | *Definizione di algoritmo
| |
| − | *Definizione di problema
| |
| − | *Tipi di problemi
| |
| − | *#di decisione
| |
| − | *#di ricerca
| |
| − | *#di conteggio
| |
| − | *#di ottimizzazione
| |
| − | *Complessità di un algoritmo
| |
| − | *Tipi di difficoltà (problematiche)
| |
| − | *#SINTESI
| |
| − | *#ANALISI
| |
| − | *#CLASSIFICAZIONE
| |
| − |
| |
| − | ===Lezione 02/10/2007===
| |
| − | lezione annullata
| |
| − |
| |
| − | ===Laboratorio 02/10/2007===
| |
| − | *Presentazione
| |
| − | *Caratteristiche del linguaggio C
| |
| − | *Differenze e somiglianze con JAVA
| |
| − | **C è per la programmazione strutturata, non ad oggetti
| |
| − | **In C non esistono i metodi ma le funzioni, + o - eguali ai metodi statici di JAVA
| |
| − | **C non è cross-latform, va ricompilato per ogni computer
| |
| − | **(...)
| |
| − | *Compilazione: codice sorgente -> pre-processore -> codice sorgente preprocessato -> compilatore -> codice oggetto -> linker -> codice eseguibile
| |
| − | * #INCLUDE
| |
| − |
| |
| − | ===Lezione 04/10/2007===
| |
| − | '''non ho potuto partecipare alla lezione, aggiungete particolari se riuscite'''
| |
| − |
| |
| − | *Macchina RAM
| |
| − | *Istruzioni macchina RAM
| |
| − | *Semantica del linguaggio RAM
| |
| − | *Nozione di stato
| |
| − | *Nozione di transizione fra stati
| |
| − |
| |
| − | ===Laboratorio 04/10/2007===
| |
| − | Processo dal file srgente alleseguibile:
| |
| − | *Passaggio 1: pre-processazione
| |
| − | **gcc -E ''nomefile''.c esegue solo la precompilazione
| |
| − | **Direttive al pre-processore
| |
| − | **# #DEFINE
| |
| − | **# #INCLUDE
| |
| − | *Passaggio 2: compilazione
| |
| − | **gcc -c ''nomefile''.c esegue la precompilazione e la compilazione
| |
| − | **risultato in file codice oggetto binario (xxx'''.o''')
| |
| − | **le funzioni di cui c'è il prototipo (inserito o meno in fase di pre-compilazione) '''non''' sono sostituite dal loro codice, lo fa il ''linker'' al passaggio successivo.
| |
| − | *Passaggio 3: linking
| |
| − | **collega i prototipi al loro codice
| |
| − | **Modularità
| |
| − | ***gcc x1.o x2.o unisce i due files compilati separatamente
| |
| − | ***ci deve essere '''un solo main''' in almeno uno dei file uniti assieme
| |
| − | ***'''non''' ci devono essere più definizioni della stessa funzione
| |
| − |
| |
| − | ALTRO:
| |
| − | *gcc -ansi ''nomefile''.c esegue la compilazione secondo lo standard ANSI
| |
| − | *gcc -pedantic ''nomefile''.c esegue la compilazione con un livello di dettaglio del debug estremamente avanzato
| |
| − | *gcc -Wall ''nomefile''.c esegue la compilazione con tutti i warning
| |
| − |
| |
| − | ===Lezione 05/10/2007===
| |
| − | *Proprietà della computazione
| |
| − | *Criteri di costo
| |
| − | **Uniforme
| |
| − | **Logaritmico
| |
| − | *Esempi
| |
| − |
| |
| − | ===Lezione 08/10/2007===
| |
| − | *Criterio uniforme e criterio logaritmico
| |
| − | *Costo delle operazioni della macchina RAM con criterio logaritmico
| |
| − | *Esempi di valutazione di spazio e tempo con i due criteri e paragone dei risultati
| |
| − |
| |
| − | ===Lezione 09/10/2007===
| |
| − | *Notazione asintotica
| |
| − | *Relazioni e loro significato
| |
| − | **asintotico
| |
| − | **O grande
| |
| − | **o piccolo
| |
| − | **Omega grande
| |
| − | **Ordine di grandezza
| |
| − | *Regole generali di confronto
| |
| − | *Rapporti fra relazioni
| |
| − |
| |
| − | ===Laboratorio 09/10/2007===
| |
| − | *printf
| |
| − | *scanf
| |
| − | *if..then
| |
| − | *esempi ed esercizi in classe (vedere dispense di laboratorio)
| |
| − |
| |
| − | ===Lezione 11/10/2007===
| |
| − | *Ripasso relazioni (o piccola, ...)
| |
| − | *Sommatorie
| |
| − | **le più comuni: ''geometrica'', somme di polinomi
| |
| − | *Primi due metodi per calcolare le somme:
| |
| − | **derivazione
| |
| − | **perturbazione
| |
| − |
| |
| − | ===Laboratorio 11/10/2007===
| |
| − | *Variabili
| |
| − | **attributi
| |
| − | **#nome
| |
| − | **#tipo
| |
| − | **#valore
| |
| − | *Funzioni
| |
| − | **parametri
| |
| − | **si raccomanda di documentarle
| |
| − | **il return di un valore di tipo errato determina un ''cast'' automatico
| |
| − | *Prototipi
| |
| − | **definizione
| |
| − | *Record di attivazione delle funzioni
| |
| − | **contenuti
| |
| − | **#variabili locali
| |
| − | **#informazioni per poter riprendere il programma chiamante all'istruzione giusta
| |
| − | **allocato nello stack di sistema con procedura LIFO
| |
| − | **''PUSH''/''POP''
| |
| − | *Variabili globali
| |
| − | *Criteri di visibilità
| |
| − | *Tempo di vita di una variabile
| |
| − |
| |
| − | ===Lezione 12/10/2007===
| |
| − | *Terzo metodo per calcolare le somme:
| |
| − | **integrazione per funzioni decrescenti e crescenti monotone
| |
| − | *vari esempi di applicazione dell'integrazione
| |
| − | *ripresa della Formula di Stirling
| |
| − |
| |
| − | ===Lezione 15/10/2007===
| |
| − | '''non ero presente, aggiungerò gli argomenti appena possibile'''
| |
| − |
| |
| − | ===Lezione 16/10/2007===
| |
| − | *Vettori
| |
| − | *Matrici
| |
| − | *Record
| |
| − | *Tabelle
| |
| − | *esempi
| |
| − |
| |
| − | ===Laboratorio 16/10/2007===
| |
| − | *Input/output
| |
| − | **caratteri e loro rappresentazione
| |
| − | **getchar()
| |
| − | **redirezione dello standard input
| |
| − | **end-of-file
| |
| − | **putchar()
| |
| − | **redirezione output
| |
| − | *Esercizi
| |
| − |
| |
| − | ===Lezione 18/10/2007===
| |
| − | *Liste (''non ero presente, se potete aggiungere particolari ve ne sarei grato'')
| |
| − |
| |
| − | ===Laboratorio 18/10/2007===
| |
| − | *Espressioni
| |
| − | **semplici
| |
| − | ***costanti
| |
| − | ***variabili
| |
| − | **composte (espressioni aritmetiche, invocazione metodi)
| |
| − | *Puntatori
| |
| − | **assegnamenti fra puntatori (compatibilità di tipo)
| |
| − | **esempi
| |
| − | **Dereferenziazione di un puntatore (operatore '''*''')
| |
| − |
| |
| − | ===Lezione 19/10/2007===
| |
| − | *Pile
| |
| − | **Insiemi utili per la definizione
| |
| − | **Operazioni
| |
| − | ***IS_EMPTY
| |
| − | ***TOP(S)
| |
| − | ***POP(S)
| |
| − | ***PUSH(S, u)
| |
| − | **Implementazioni delle pile
| |
| − | ***Tabella
| |
| − | ***Lista concatenata
| |
| − | *Code
| |
| − | **Insiemi utili per la definizione
| |
| − | **Operazioni
| |
| − | ***IS_EMPTY
| |
| − | ***FRONT(Q)
| |
| − | ***DEQUEUE(Q)
| |
| − | ***ENQUEUE(Q, u)
| |
| − | **Implementazioni delle code
| |
| − | ***Tabella
| |
| − | ***Lista concatenata
| |
| − | *Allineamenti ed insiemi
| |
| − | **allineamenti
| |
| − | **#permutazione
| |
| − | **#disposizione
| |
| − | **#*semplice
| |
| − | **#*complessa
| |
| − | **insiemi
| |
| − | **#combinazione
| |
| − | **#*semplice
| |
| − | **#*complessa
| |
| − |
| |
| − | ===Lezione 22/10/2007===
| |
| − | *Grafi
| |
| − | **non orentati
| |
| − | **orientati
| |
| − | *Implementazioni
| |
| − | **matrice
| |
| − | **coppia di tabelle
| |
| − | **lista concatenata
| |
| − | *definizione di cammino
| |
| − | *definizione di ciclo
| |
| − | *definizione di sottografo
| |
| − | *definizione di grafo connesso
| |
| − | *relazione di connessione
| |
| − | **proprietà: transitiva, riflessiva, generalmente '''non''' simmetrica
| |
| − | *relazione di raggiungibilità
| |
| − |
| |
| − | ===Lezione 23/10/2007===
| |
| − | *alberi
| |
| − | *albero di copertura
| |
| − | *foresta
| |
| − | *albero con radice
| |
| − | *rappresentazione di albero tramite tabella
| |
| − | *clique
| |
| − | *indipendent set
| |
| − | *padre,figlio,foglia,radice,fratelli,predecessore,successore, altezza, profondità
| |
| − | *albero bilanciato
| |
| − |
| |
| − | ===Laboratorio 23/10/2007===
| |
| − | *esercizi su puntatori
| |
| − | *esercizi su frazioni e passaggio parametri
| |
| − |
| |
| − | ===Lezione 25/10/2007===
| |
| − | *visita di grafi per ampiezza
| |
| − | *esercizi
| |
| − | ===Laboratorio 25/10/2007===
| |
| − | *ripasso tipi di dato
| |
| − | *revisione esercizi del laboratorio precedente
| |
| − | ===Lezione 26/10/2007===
| |
| − | *alberi ordinati
| |
| − | **rappresentazione in memoria
| |
| − | ***liste di adiacenza
| |
| − | ***3 vettori
| |
| − | **Tipi di attraversamento
| |
| − | ***in preordine
| |
| − | ***in postordine
| |
| − | *alberi binari
| |
| − | **alberi binari completi
| |
| − | **rappresentazione in memoria
| |
| − | ***2 vettori
| |
| − | **Tipi di attraversamento
| |
| − | ***in preordine
| |
| − | ***in postordine
| |
| − | ***in ordine simmetrico
| |
| − |
| |
| − | ===Lezione 29/10/2007===
| |
| − | '''ero assente'''
| |
| − |
| |
| − | ===Lezione 30/10/2007===
| |
| − | *ricorsione terminale
| |
| − | *procedura di ricerca binaria
| |
| − | **tempi e spazi (criterio uniforme)
| |
| − | *attraversamento in preordine
| |
| − | **procedura
| |
| − | **versione iterativa
| |
| − | *attraversamento in profondità
| |
| − | **procedura
| |
| − | **versione iterativa
| |
| − |
| |
| − | ===Laboratorio 30/10/2007===
| |
| − | *esercizi su equazioni e interi
| |
| − |
| |
| − | ===Lezione 01/11/2007===
| |
| − | '''vacanza'''
| |
| − | ===Lezione 05/11/2007===
| |
| − | *Mergesort
| |
| − | **ordine di grandezza (tempo e spazio) di Mergesort
| |
| − |
| |
| − | ===Lezione 06/11/2007===
| |
| − | '''non c'ero'''
| |
| − | ===Lezione 08/11/2007===
| |
| − | '''non c'ero'''
| |
| − |
| |
| − | ===Laboratorio 08/11/2007===
| |
| − | *aritmetica dei puntatori
| |
| − | *esercizi sugli array
| |
| − |
| |
| − | ===Lezione 09/11/2007===
| |
| − | *prodotto di matrici
| |
| − | *algoritmo di strasse
| |
| − | *esercizi vari con calcolo di tempi di cacolo e spazi di memoria
| |
| − |
| |
| − | ===Settimana 12/11/2007->16/11/2007 ===
| |
| − | '''non ero a Milano'''
| |
| − |
| |
| − | ===Lezione 19/11/2007===
| |
| − | *strutture dati astratte
| |
| − | *dizionari
| |
| − | *dizionari ordinati
| |
| − | *partizioni
| |
| − | *hashing
| |
| − |
| |
| − | ===Lezione 20/11/2007===
| |
| − | *alberi di ricerca binaria
| |
| − | *rappresentazione in memoria
| |
| − | *operazioni
| |
| − | **member
| |
| − | **insert
| |
| − | **delete
| |
| − | **min
| |
| − | **max
| |
| − |
| |
| − | ===Laboratorio 20/11/2007===
| |
| − | *esercizi su insertionsort, quicksort
| |
| − | ===Lezione 22/11/2007===
| |
| − | *alberi di ricerca binaria
| |
| − | *strutture bilanciate
| |
| − | *alberi 2-3
| |
| − | *operazioni
| |
| − | **MIN
| |
| − | **MAX
| |
| − | **MEMBER
| |
| − | **CERCA
| |
| − | **INSERISCI
| |
| − | **RIDUCI
| |
| − | ===Laboratorio 22/11/2007===
| |
| − | *String come array di char
| |
| − | * 0 = '\0' = End OF File != "0"
| |
| − |
| |
| − | ===Lezione 23/11/2007===
| |
| − | *ripasso alberi 2-3
| |
| − | *ripasso operazioni fatte
| |
| − | *operazioni
| |
| − | **DELETE
| |
| − | **CANCELLA
| |
| − | ===Lezione 26/11/2007===
| |
| − | '''non c'ero'''
| |
| − | ===Lezione 27/11/2007===
| |
| − | *B-alberi
| |
| − | ===Laboratorio 27/11/2007===
| |
| − | ===Lezione 29/11/2007===
| |
| − | ''da svolgersi''
| |
