Strumenti Utente

Strumenti Sito


informatica:all-a:all08:start

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

Prossima revisione
Revisione precedente
informatica:all-a:all08:start [17/02/2010 alle 14:36 (12 anni fa)]
127.0.0.1 modifica esterna
informatica:all-a:all08:start [31/08/2010 alle 18:06 (12 anni fa)] (versione attuale)
peppe
Linea 25: Linea 25:
  
 ^ Data ^ Tipo Prova ^ Documento ^ Note ^ ^ Data ^ Tipo Prova ^ Documento ^ Note ^
-| 07/04/09 | 1° Compitino | {{:informatica:all-a:all09:algo1sol_090407.pdf|testo e soluzione}} | | +| 07/04/09 | 1° Compitino | {{:informatica:all-a:all08:algo1sol_090407.pdf|testo e soluzione}} | | 
-| 25/05/09 | 2° Compitino | {{:informatica:all-a:all09:algo1sol_090525.pdf|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) il primo compitino. | +| 25/05/09 | 2° Compitino | {{:informatica:all-a:all08:algo1sol_090525.pdf|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) il primo compitino. | 
-| 28/05/09 | Prova Lab | {{:informatica:all-a:all09:Lab20090528.zip|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) **entrambi** i compitini. Laboratori H e M ore 16.|  +| 28/05/09 | Prova Lab | {{:informatica:all-a:all08:Lab20090528.zip|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) **entrambi** i compitini. Laboratori H e M ore 16.|  
-| 10/06/09 | Appello 1 | {{:informatica:all-a:all09:algo1_090610.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090610.zip|prova di laboratorio con soluzione}} | Prova di Algoritmica ore 9, aule H,I,M,A1,L1. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | +| 10/06/09 | Appello 1 | {{:informatica:all-a:all08:algo1_090610.pdf|testo dello scritto}} e {{:informatica:all-a:all08:lab20090610.zip|prova di laboratorio con soluzione}} | Prova di Algoritmica ore 9, aule H,I,M,A1,L1. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | 
-| 26/06/09 | Appello 2 | {{:informatica:all-a:all09:algo1_090626.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090626.pdf|prova di laboratorio}} , {{:informatica:all-a:all09:lab20090626-testcase.zip|casi di test}} | Prova di Algoritmica ore 9, aule A1,D1,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | +| 26/06/09 | Appello 2 | {{:informatica:all-a:all08:algo1_090626.pdf|testo dello scritto}} e {{:informatica:all-a:all08:lab20090626.pdf|prova di laboratorio}} , {{:informatica:all-a:all08:lab20090626-testcase.zip|casi di test}} | Prova di Algoritmica ore 9, aule A1,D1,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | 
-| 14/07/09 | Appello 3 | {{{{:informatica:all-a:all09:algo1sol_090714.pdf|testo dello scritto}} e {{{{:informatica:all-a:all09:lab20090714.pdf|prova di laboratorio}} | Prova di Algoritmica ore 9, aule A,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | +| 14/07/09 | Appello 3 | {{{{:informatica:all-a:all08:algo1sol_090714.pdf|testo dello scritto}} e {{{{:informatica:all-a:all08:lab20090714.pdf|prova di laboratorio}} | Prova di Algoritmica ore 9, aule A,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | 
-| 11/09/09 | Appello 4 | {{:informatica:all-a:all09:algo1sol090911.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090911.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9, aule A. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | +| 11/09/09 | Appello 4 | {{:informatica:all-a:all08:algo1sol090911.pdf|testo dello scritto}} e {{:informatica:all-a:all08:lab20090911.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9, aule A. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | 
-| 11/01/10 | Appello 5 | {{:informatica:all-a:all09:algo1_100111.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20100111.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | +| 11/01/10 | Appello 5 | {{:informatica:all-a:all08:algo1_100111.pdf|testo dello scritto}} e {{:informatica:all-a:all08:lab20100111.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. | 
-| 11/01/10 | Appello 6 | {{:informatica:all-a:all09:algo1_100201.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20100201.pdf|prova di laboratorio}}  |  |+| 11/01/10 | Appello 6 | {{:informatica:all-a:all08:algo1_100201.pdf|testo dello scritto}} e {{:informatica:all-a:all08:lab20100201.pdf|prova di laboratorio}}  |  |
  
 ======= Libro di testo ======= ======= Libro di testo =======
Linea 76: Linea 76:
  
 ^ Data ^ Argomento ^ Rif. Biblio ^ ^ Data ^ Argomento ^ Rif. Biblio ^
-| 23/2/09 | **Laboratorio**: richiami di linguaggio C. Editing, compilazione, debugging. | {{:informatica:all-a:all09:lez1.zip|C code}}| +| 23/2/09 | **Laboratorio**: richiami di linguaggio C. Editing, compilazione, debugging. | {{:informatica:all-a:all08:lez1.zip|C code}}| 
-| 24/2/09 | **Laboratorio**: richiami di linguaggio C. Istruzioni varie e operatori, printf, scanf, vettori| Cap. 2-3, 7.1-7.4 di [KR], {{:informatica:all-a:all09:lez2.zip|C code}}| +| 24/2/09 | **Laboratorio**: richiami di linguaggio C. Istruzioni varie e operatori, printf, scanf, vettori| Cap. 2-3, 7.1-7.4 di [KR], {{:informatica:all-a:all08:lez2.zip|C code}}| 
-| 26/2/09 | **Laboratorio**: richiami di linguaggio C. Puntatori, funzioni e passaggio parametri | Cap. 5 di [KR], {{:informatica:all-a:all09:lez3.pdf|slides}}, {{:informatica:all-a:all09:lez3.zip|C code}}| +| 26/2/09 | **Laboratorio**: richiami di linguaggio C. Puntatori, funzioni e passaggio parametri | Cap. 5 di [KR], {{:informatica:all-a:all08:lez3.pdf|slides}}, {{:informatica:all-a:all08:lez3.zip|C code}}| 
-| 27/2/09 | **Laboratorio**: richiami di linguaggio C. Allocazione dinamica della memoria (malloc), stringhe, vettori bidimensionali. \\ //Esercizio per casa//: calcolo del bigramma di massima frequenza in una stringa. | Cap. 4 di [KR],{{:informatica:all-a:all09:lez4.pdf|slides}}, {{:informatica:all-a:all09:lez4.zip|C code}}|+| 27/2/09 | **Laboratorio**: richiami di linguaggio C. Allocazione dinamica della memoria (malloc), stringhe, vettori bidimensionali. \\ //Esercizio per casa//: calcolo del bigramma di massima frequenza in una stringa. | Cap. 4 di [KR],{{:informatica:all-a:all08:lez4.pdf|slides}}, {{:informatica:all-a:all08:lez4.zip|C code}}|
 | 2/3/09 | Introduzione al corso: prerequisiti, definizione di algoritmo, modello RAM, problema formale e istanza, dimensione di una istanza, complessità in tempo e spazio, analisi asintotica al caso pessimo e caso medio, numero passi, confronto tra algoritmi.| Sez. 1.4 e 2.1 di [CGG]| | 2/3/09 | Introduzione al corso: prerequisiti, definizione di algoritmo, modello RAM, problema formale e istanza, dimensione di una istanza, complessità in tempo e spazio, analisi asintotica al caso pessimo e caso medio, numero passi, confronto tra algoritmi.| Sez. 1.4 e 2.1 di [CGG]|
 | 3/3/09 | Problema della sottosequenza di somma massima: algoritmi e analisi di complessità in tempo al caso pessimo. Classi P, NP e NP-completi (cenni). Risolvere vs Verificare. Un esempio di problema NP-Completo: Subset sum. | Sez. 2.3 di [CGG] |  | 3/3/09 | Problema della sottosequenza di somma massima: algoritmi e analisi di complessità in tempo al caso pessimo. Classi P, NP e NP-completi (cenni). Risolvere vs Verificare. Un esempio di problema NP-Completo: Subset sum. | Sez. 2.3 di [CGG] | 
 | 4/3/09 | Problemi EXP-TIME. Problemi decidibili //vs// indecidibili. Tecnica della diagonalizzazione. Problema della fermata. | Sez. 1.1, 1.2, 1.2.1 e 1.3 di [CGG]. Non fare 1.2.2.| | 4/3/09 | Problemi EXP-TIME. Problemi decidibili //vs// indecidibili. Tecnica della diagonalizzazione. Problema della fermata. | Sez. 1.1, 1.2, 1.2.1 e 1.3 di [CGG]. Non fare 1.2.2.|
-| 5/3/09 | **Laboratorio**: Problema del Maggioritario: soluzione quadratica e lineare.\\ //Esercizio per casa//: coding delle 3 soluzioni per il problema della "sottosequenza di somma massima". | {{:informatica:all-a:all09:lez5.pdf|esercizi}}, {{:informatica:all-a:all09:testfile.zip|testfile}}, {{:informatica:all-a:all09:code5.zip|C code}}|+| 5/3/09 | **Laboratorio**: Problema del Maggioritario: soluzione quadratica e lineare.\\ //Esercizio per casa//: coding delle 3 soluzioni per il problema della "sottosequenza di somma massima". | {{:informatica:all-a:all08:lez5.pdf|esercizi}}, {{:informatica:all-a:all08:testfile.zip|testfile}}, {{:informatica:all-a:all08:code5.zip|C code}}|
 | 9/3/09 | Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta. Alcuni esercizi sulla notazione e sua interpretazione in termini di complessità di algoritmi e/o problemi. Introduzione al problema dell'ordinamento e algoritmo SelectionSort con analisi della complessità. | Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG]. | | 9/3/09 | Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta. Alcuni esercizi sulla notazione e sua interpretazione in termini di complessità di algoritmi e/o problemi. Introduzione al problema dell'ordinamento e algoritmo SelectionSort con analisi della complessità. | Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG]. |
-| 10/3/09 | Insertion Sort: proprietà e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni. Esempi: min/max, ricerca di una chiave, ordinamento. Problema della ricerca di una chiave: scansione e ricerca binaria (iterativa e ricorsiva).| Sez. 2.2.2 e 2.3.1 e 2.4 di [CGG]. Studiare anche questo {{:informatica:all-a:all09:lucciolb.pdf|approfondimento}} dal libro di F. Luccio "La struttura degli algoritmi" (Boringhieri, 1982). |+| 10/3/09 | Insertion Sort: proprietà e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni. Esempi: min/max, ricerca di una chiave, ordinamento. Problema della ricerca di una chiave: scansione e ricerca binaria (iterativa e ricorsiva).| Sez. 2.2.2 e 2.3.1 e 2.4 di [CGG]. Studiare anche questo {{:informatica:all-a:all08:lucciolb.pdf|approfondimento}} dal libro di F. Luccio "La struttura degli algoritmi" (Boringhieri, 1982). |
 | 11/3/09 | Tecnica "divide et impera". Relazioni di Ricorrenza e teorema per la loro risoluzione (con dimostrazione). Risoluzione ricorsiva del problema "del massimo" e analisi di complessità. MergeSort: algoritmo, proprietà, e analisi della complessità.| Sez. 2.5.1 e 2.5.3 di [CGG], con teorema e sua dimostrazione alle pagine 10-11 dell'Errata Corrige. | | 11/3/09 | Tecnica "divide et impera". Relazioni di Ricorrenza e teorema per la loro risoluzione (con dimostrazione). Risoluzione ricorsiva del problema "del massimo" e analisi di complessità. MergeSort: algoritmo, proprietà, e analisi della complessità.| Sez. 2.5.1 e 2.5.3 di [CGG], con teorema e sua dimostrazione alle pagine 10-11 dell'Errata Corrige. |
-| 12/3/09 | **Laboratorio**: Lettura di un array da tastiera senza conoscerne la lunghezza: tecnica del //doubling//. Calcolo del numero di elementi distinti in un array ordinato. \\ //Esercizio per casa//: coding di Selection Sort e Insertion Sort. | {{:informatica:all-a:all09:lez6.pdf|esercizi}}, {{:informatica:all-a:all09:testfile6.zip|testfile}}, {{:informatica:all-a:all09:code6.zip|C code}}|+| 12/3/09 | **Laboratorio**: Lettura di un array da tastiera senza conoscerne la lunghezza: tecnica del //doubling//. Calcolo del numero di elementi distinti in un array ordinato. \\ //Esercizio per casa//: coding di Selection Sort e Insertion Sort. | {{:informatica:all-a:all08:lez6.pdf|esercizi}}, {{:informatica:all-a:all08:testfile6.zip|testfile}}, {{:informatica:all-a:all08:code6.zip|C code}}|
 | 16/3/09 | Moltiplicazione veloce di due interi di n cifre. Esercizi sul calcolo della complessità di algoritmi ricorsivi. Calcolo del numero x di occorrenze di un elemento in un vettore parzialmente ordinato di lunghezza n: soluzione O(n), soluzione di costo O(log n + x), soluzione di costo O(logn).    | Sez. 2.5.2 | | 16/3/09 | Moltiplicazione veloce di due interi di n cifre. Esercizi sul calcolo della complessità di algoritmi ricorsivi. Calcolo del numero x di occorrenze di un elemento in un vettore parzialmente ordinato di lunghezza n: soluzione O(n), soluzione di costo O(log n + x), soluzione di costo O(logn).    | Sez. 2.5.2 |
-| 17/3/09 | Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di "distribuzione. qsort del C come quicksort + insertionSort  | Sez. 2.5.4 e per altra tecnica di distribuzione (oltre al codice 2.14) studiare anche questi {{:informatica:all-a:all09:altropivot.pdf|appunti}}|+| 17/3/09 | Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di "distribuzione. qsort del C come quicksort + insertionSort  | Sez. 2.5.4 e per altra tecnica di distribuzione (oltre al codice 2.14) studiare anche questi {{:informatica:all-a:all08:altropivot.pdf|appunti}}|
 | 18/3/09 | Quicksort randomizzato. QuickSelect. Genera Binarie. Genera Permutazioni. | Sez. 1.2.2 | | 18/3/09 | Quicksort randomizzato. QuickSelect. Genera Binarie. Genera Permutazioni. | Sez. 1.2.2 |
-| 19/3/09 | **Laboratorio**: Implementazione del Quick Sort.\\ //Esercizio per casa//: coding del Quicksort con three-way partition. | {{:informatica:all-a:all09:lez7.pdf|esercizi}},  {{:informatica:all-a:all09:code7.zip|C code}}|+| 19/3/09 | **Laboratorio**: Implementazione del Quick Sort.\\ //Esercizio per casa//: coding del Quicksort con three-way partition. | {{:informatica:all-a:all08:lez7.pdf|esercizi}},  {{:informatica:all-a:all08:code7.zip|C code}}|
 | 23/3/09 | Programmazione dinamica e ricorsione con tabulazione (memoization): esempio con i numeri di Fibonacci. Sottosequenza comune più lunga: regola ricorsiva.| Sez. 2.7 tutta | | 23/3/09 | Programmazione dinamica e ricorsione con tabulazione (memoization): esempio con i numeri di Fibonacci. Sottosequenza comune più lunga: regola ricorsiva.| Sez. 2.7 tutta |
 | 24/3/09 | Programmazione dinamica: Sottosequenza comune più lunga (lunghezza) -- metodo di riempimento della tabella per riga/colonna/diagonale. Calcolo di una sottosequenza comune avente la lunghezza massima, calcolo della tabella in spazio ridotto (due sole righe). Partizione di un insieme di interi: regola ricorsiva.| | | 24/3/09 | Programmazione dinamica: Sottosequenza comune più lunga (lunghezza) -- metodo di riempimento della tabella per riga/colonna/diagonale. Calcolo di una sottosequenza comune avente la lunghezza massima, calcolo della tabella in spazio ridotto (due sole righe). Partizione di un insieme di interi: regola ricorsiva.| |
 | 25/3/09 | Partizione di un insieme di interi: tabella e calcolo di una soluzione. Problemi NP-completi e algoritmi pseudo-polinomiali. Esercizio su "calcolo del minimo numero di caratteri da inserire in una stringa per renderla palindroma".| | | 25/3/09 | Partizione di un insieme di interi: tabella e calcolo di una soluzione. Problemi NP-completi e algoritmi pseudo-polinomiali. Esercizio su "calcolo del minimo numero di caratteri da inserire in una stringa per renderla palindroma".| |
-| 26/3/09 | **Laboratorio**: Esercizi con qsort su array di interi e stringhe.\\ //Esercizio per casa//: ricerca su un array di stringhe ordinate e esercizio Divide-et-impera.| {{:informatica:all-a:all09:lez8.pdf|esercizi}},  {{:informatica:all-a:all09:code8.zip|C code}}| +| 26/3/09 | **Laboratorio**: Esercizi con qsort su array di interi e stringhe.\\ //Esercizio per casa//: ricerca su un array di stringhe ordinate e esercizio Divide-et-impera.| {{:informatica:all-a:all08:lez8.pdf|esercizi}},  {{:informatica:all-a:all08:code8.zip|C code}}| 
-| 30/3/09 | Counting Sort ed esercizi. Esempio di calcolo della tabella per la sottosequenza comune più lunga tra due stringhe.| {{:informatica:all-a:all09:countingsort.pdf|appunti}} prestando attenzione al fatto che nello pseudo-codice gli indici degli array iniziano da 1|+| 30/3/09 | Counting Sort ed esercizi. Esempio di calcolo della tabella per la sottosequenza comune più lunga tra due stringhe.| {{:informatica:all-a:all08:countingsort.pdf|appunti}} prestando attenzione al fatto che nello pseudo-codice gli indici degli array iniziano da 1|
 | 31/3/09 | Esercizi su Divide-et-impera. Ordinamento dei suffissi di un testo con soluzione più che quadratica.| | | 31/3/09 | Esercizi su Divide-et-impera. Ordinamento dei suffissi di un testo con soluzione più che quadratica.| |
-| 1/4/09 | Ordinamento dei suffissi di un testo con il ''qsort''. Radix sort e analisi della complessità. | {{:informatica:all-a:all09:radixsort.pdf|appunti}} +| 1/4/09 | Ordinamento dei suffissi di un testo con il ''qsort''. Radix sort e analisi della complessità. | {{:informatica:all-a:all08:radixsort.pdf|appunti}} 
-| 2/4/09 | Multi-key Quicksort, e analisi della sua complessità. Fingerprint di Karp-Rabin, analisi, e suo uso nel problema del dizionario di stringhe.  | {{:informatica:all-a:all09:mkqs.pdf|appunti}} su Multi-key quicksort, prestare attenzione al fatto che le stringhe hanno indici da 1 invece che 0, e quindi in classe abbiamo messo l invece di l+1. Per quanto riguarda KR-fingerprint si legga questo estratto di {{:informatica:all-a:all09:10_kr.pdf|libro}}.|+| 2/4/09 | Multi-key Quicksort, e analisi della sua complessità. Fingerprint di Karp-Rabin, analisi, e suo uso nel problema del dizionario di stringhe.  | {{:informatica:all-a:all08:mkqs.pdf|appunti}} su Multi-key quicksort, prestare attenzione al fatto che le stringhe hanno indici da 1 invece che 0, e quindi in classe abbiamo messo l invece di l+1. Per quanto riguarda KR-fingerprint si legga questo estratto di {{:informatica:all-a:all08:10_kr.pdf|libro}}.|
 | 6/4/09 | Esercitazione pre-compitino.  | | | 6/4/09 | Esercitazione pre-compitino.  | |
-| | **Challenge:** E' dato un [[http://www.di.unipi.it/~ferragin/Challenge/testoProva.txt|testo]] che contiene una sottostringa ripetuta due volte e di lunghezza circa 1600 caratteri. Tutte le altre sottostringhe che si ripetono in questo testo hanno una lunghezza inferiore a 300 caratteri. Progettare un algoritmo che scopre quella sottostringa e la stampa a video.\\ **Gruppi di lavoro:** composti da al massimo 2 studenti.\\  **Codice:** Utilizzare questo esempio di [[http://www.di.unipi.it/~ferragin/Challenge/CodiceEsempio.c|programma C]] per poter leggere il testo dal suddetto file.\\ **Come partecipare:** La soluzione --frase ripetuta e codice dell'algoritmo in C-- deve essere spedita via email a ''ferragina@di.unipi.it'' entro le ore 20:00 del 14 Aprile 2009. L'email deve avere soggetto "Challenge Corso A", e deve riportare i nomi e le email degli studenti che l'hanno ottenuta.  | Una possibile {{:informatica:all-a:all09:challenge.zip|soluzione}}. Hanno partecipato con successo i gruppi: Ciccarelli-Miglianesi, Guelfi, Zanotto-Sabadin.| +| | **Challenge:** E' dato un [[http://www.di.unipi.it/~ferragin/Challenge/testoProva.txt|testo]] che contiene una sottostringa ripetuta due volte e di lunghezza circa 1600 caratteri. Tutte le altre sottostringhe che si ripetono in questo testo hanno una lunghezza inferiore a 300 caratteri. Progettare un algoritmo che scopre quella sottostringa e la stampa a video.\\ **Gruppi di lavoro:** composti da al massimo 2 studenti.\\  **Codice:** Utilizzare questo esempio di [[http://www.di.unipi.it/~ferragin/Challenge/CodiceEsempio.c|programma C]] per poter leggere il testo dal suddetto file.\\ **Come partecipare:** La soluzione --frase ripetuta e codice dell'algoritmo in C-- deve essere spedita via email a ''ferragina@di.unipi.it'' entro le ore 20:00 del 14 Aprile 2009. L'email deve avere soggetto "Challenge Corso A", e deve riportare i nomi e le email degli studenti che l'hanno ottenuta.  | Una possibile {{:informatica:all-a:all08:challenge.zip|soluzione}}. Hanno partecipato con successo i gruppi: Ciccarelli-Miglianesi, Guelfi, Zanotto-Sabadin.| 
-| 16/4/09 | **Laboratorio**: Le //struct// in ''C''. \\ //Esercizio per casa//: Leggere una stringa da stdin, costruire tutti i suoi //k//-grammi (dove //k// è passato come input), contare le loro frequenze, e poi ordinarli in ordine decrescente di frequenza.    | Sez. 6.1-6.4 di [KR] e {{:informatica:all-a:all09:code9.zip|C code}}. |+| 16/4/09 | **Laboratorio**: Le //struct// in ''C''. \\ //Esercizio per casa//: Leggere una stringa da stdin, costruire tutti i suoi //k//-grammi (dove //k// è passato come input), contare le loro frequenze, e poi ordinarli in ordine decrescente di frequenza.    | Sez. 6.1-6.4 di [KR] e {{:informatica:all-a:all08:code9.zip|C code}}. |
 | 20/4/09 | Le liste: definizione e codice C. Operazioni di ricerca per chiave e posizione, inserimento e cancellazione. Esercizio su: inclusione tra due liste. Il problema UNION-FIND e sua soluzione efficiente. | Sez. 3.1 e 3.4.1| | 20/4/09 | Le liste: definizione e codice C. Operazioni di ricerca per chiave e posizione, inserimento e cancellazione. Esercizio su: inclusione tra due liste. Il problema UNION-FIND e sua soluzione efficiente. | Sez. 3.1 e 3.4.1|
 | 21/4/09 | L'analisi ammortizzata: Union-Find, k-ricerche in un vettore, il contatore binario, array dinamico. L'analisi competitiva: Move-To-Front. | Sez. 3.4.2 e 3.4.3. | | 21/4/09 | L'analisi ammortizzata: Union-Find, k-ricerche in un vettore, il contatore binario, array dinamico. L'analisi competitiva: Move-To-Front. | Sez. 3.4.2 e 3.4.3. |
-| 23/4/09 | **Laboratorio**: Esercizi con le liste. Creazione di una lista e stampa dei suoi elementi. Ricerca in una lista e Move-To-Front.  | {{:informatica:all-a:all09:lez10.pdf|esercizi}} {{:informatica:all-a:all09:code10.zip|C code}} | +| 23/4/09 | **Laboratorio**: Esercizi con le liste. Creazione di una lista e stampa dei suoi elementi. Ricerca in una lista e Move-To-Front.  | {{:informatica:all-a:all08:lez10.pdf|esercizi}} {{:informatica:all-a:all08:code10.zip|C code}} | 
-| 27/4/09 | Algoritmi Greedy: Interval Scheduling e Codice di Huffman. | {{:informatica:all-a:all09:greedy1.pdf|appunti}} su Interval Scheduling e {{:informatica:all-a:all09:greedy2.pdf|appunti}} su Codice di Huffman |+| 27/4/09 | Algoritmi Greedy: Interval Scheduling e Codice di Huffman. | {{:informatica:all-a:all08:greedy1.pdf|appunti}} su Interval Scheduling e {{:informatica:all-a:all08:greedy2.pdf|appunti}} su Codice di Huffman |
 | 28/4/09 | Codice di Huffman: esempio e dimostrazione di ottimalità. | | | 28/4/09 | Codice di Huffman: esempio e dimostrazione di ottimalità. | |
 | 29/4/09 | Tabelle hash: definizione, proprietà, gestione dei conflitti (liste di trabocco e indirizzamento aperto), con analisi della complessità al caso pessimo e al caso medio. | Sez. 5.1-5.3 | | 29/4/09 | Tabelle hash: definizione, proprietà, gestione dei conflitti (liste di trabocco e indirizzamento aperto), con analisi della complessità al caso pessimo e al caso medio. | Sez. 5.1-5.3 |
-| 30/4/09 | **Laboratorio**: Esercizi con le tabelle hash con gestione dei conflitti tramite liste di trabocco. | {{:informatica:all-a:all09:lez11.pdf|esercizi}} {{:informatica:all-a:all09:code11.zip|C code}}|+| 30/4/09 | **Laboratorio**: Esercizi con le tabelle hash con gestione dei conflitti tramite liste di trabocco. | {{:informatica:all-a:all08:lez11.pdf|esercizi}} {{:informatica:all-a:all08:code11.zip|C code}}|
 | 4/5/09 | Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo. | Tutta la sez. 4.1| | 4/5/09 | Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo. | Tutta la sez. 4.1|
 | 5/5/09 | Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo. | Sez. 5.4| | 5/5/09 | Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo. | Sez. 5.4|
 | 6/5/09 | Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria. | Sez. 5.4| | 6/5/09 | Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria. | Sez. 5.4|
-| 7/5/09 | **Laboratorio**: Esercizi con alberi. | {{:informatica:all-a:all09:lez12.pdf|esercizi}} {{:informatica:all-a:all09:code12.zip|C code}} {{:informatica:all-a:all09:eserciziliste.pdf|ulteriori esercizi sulle liste}}|+| 7/5/09 | **Laboratorio**: Esercizi con alberi. | {{:informatica:all-a:all08:lez12.pdf|esercizi}} {{:informatica:all-a:all08:code12.zip|C code}} {{:informatica:all-a:all08:eserciziliste.pdf|ulteriori esercizi sulle liste}}|
 | 11/5/09 | Trie: definizione, proprietà, ricerca esatta/prefisso, inserimento di una chiave. Richiami di Code e Pile, con loro implementazione mediante array e lista.  | Sez. 5.6.1, 7.1, 7.3 | | 11/5/09 | Trie: definizione, proprietà, ricerca esatta/prefisso, inserimento di una chiave. Richiami di Code e Pile, con loro implementazione mediante array e lista.  | Sez. 5.6.1, 7.1, 7.3 |
 | 12/5/09 | La struttura dati Heap: definizione, proprietà, ricerca, Enqueue, Dequeue, decreaseKey, Heapify. | Sez. 8.1 e 8.2 | | 12/5/09 | La struttura dati Heap: definizione, proprietà, ricerca, Enqueue, Dequeue, decreaseKey, Heapify. | Sez. 8.1 e 8.2 |
 | 12/5/09 | //Esercitazione// |  | | 12/5/09 | //Esercitazione// |  |
 | 13/5/09 | Costruzione Heap e heapsort. Grafi: terminologia e notazione. | Sez. 8.2.3 e 6.1 | | 13/5/09 | Costruzione Heap e heapsort. Grafi: terminologia e notazione. | Sez. 8.2.3 e 6.1 |
-| 14/5/09 | **Laboratorio**: Esercizi su Heap e Alberi.\\ E' stata descritta la modalità di svolgimento della prova di laboratorio, il file ''mainCompito.c'', qui in allegato, contiene lo schema di codice C preliminare che verrà distribuito all'inizio di ogni prova. | {{:informatica:all-a:all09:lez13.pdf|esercizi}}, {{:informatica:all-a:all09:testfile13.zip|testfile}}|+| 14/5/09 | **Laboratorio**: Esercizi su Heap e Alberi.\\ E' stata descritta la modalità di svolgimento della prova di laboratorio, il file ''mainCompito.c'', qui in allegato, contiene lo schema di codice C preliminare che verrà distribuito all'inizio di ogni prova. | {{:informatica:all-a:all08:lez13.pdf|esercizi}}, {{:informatica:all-a:all08:testfile13.zip|testfile}}|
 | 18/5/09 | Grafi: rappresentazione e chiusura transitiva. Visita BFS. | Sez. 6.1.2, 6.1.3, 7.4.1 | | 18/5/09 | Grafi: rappresentazione e chiusura transitiva. Visita BFS. | Sez. 6.1.2, 6.1.3, 7.4.1 |
-| 19/5/09 | Visita DFS. DAG e ordinamento topologico | Sez. 7.4.2, 7.5.1. {{:informatica:all-a:all09:graph.pdf|Note}} dal libro Cormen //et al//, non fare le dimostrazioni del teo 22.7, 22.9 e 22.10. |+| 19/5/09 | Visita DFS. DAG e ordinamento topologico | Sez. 7.4.2, 7.5.1. {{:informatica:all-a:all08:graph.pdf|Note}} dal libro Cormen //et al//, non fare le dimostrazioni del teo 22.7, 22.9 e 22.10. |
 | 19/5/09 | Esercitazione | ore 16-18 aula E, ore 18-19 prova del //sistema di sottomissione// per la prova in Lab. | | 19/5/09 | Esercitazione | ore 16-18 aula E, ore 18-19 prova del //sistema di sottomissione// per la prova in Lab. |
 | 20/5/09 | Componenti (fortemente) connesse | Sez. 7.5.2| | 20/5/09 | Componenti (fortemente) connesse | Sez. 7.5.2|
 | 21/5/09 | Ricevimento studenti | Ore 17, studio Ferragina | | 21/5/09 | Ricevimento studenti | Ore 17, studio Ferragina |
informatica/all-a/all08/start.1266417364.txt.gz · Ultima modifica: 31/08/2010 alle 18:06 (12 anni fa) (modifica esterna)