| Entrambe le parti precedenti la revisione
Revisione precedente
Prossima revisione
|
Revisione precedente
Ultima revisione
Entrambe le parti successive la revisione
|
informatica:all-b:algob_14:start [05/02/2015 alle 13:59 (9 anni fa)]
anna bernasconi |
informatica:all-b:algob_14:start [08/05/2015 alle 13:31 (9 anni fa)]
anna bernasconi [Registro delle Lezioni] |
| |
| |
| ===== Anno accademico 2014/2015 ===== | ===== Anno accademico 2013/2014 ===== |
| |
| |
| ===== Informazioni Generali ===== | ===== Informazioni Generali ===== |
| |
| **Docenti:** [[http://www.di.unipi.it/~annab/|Anna Bernasconi]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]], [[http://www.di.unipi.it/~pisanti/|Nadia Pisanti]] | **Docenti:** [[http://www.di.unipi.it/~annab/|Anna Bernasconi]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]] |
| |
| |
| (**Docenti [[informatica:all-a:start|corso A]]:** [[http://www.di.unipi.it/~pagli/|Linda Pagli]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]]) | (**Docenti [[informatica:all-a:start|corso A]]:** [[http://www.di.unipi.it/~pagli/|Linda Pagli]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]]) |
| | |
| **Assistenti:** Giovanna Rosone | **Assistente:** Roberto Santoro |
| |
| **Impegno:** 12 CFU. | **Impegno:** 12 CFU. |
| Il corso consiste ogni settimana di tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti. | Il corso consiste ogni settimana di tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti. |
| ===== Anni accademici precedenti ===== | ===== Anni accademici precedenti ===== |
| * [[.algoB_14:|A.A. 2013/2014]] | * [[informatica:all-b/algob_13/start:|A.A. 2012/2013]] |
| * [[.algoB_13:|A.A. 2012/2013]] | |
| * [[informatica:all-a/all11/start|A.A: 2011/2012]] (NB: il corso è unico; per comodità vengono usate le pagine del corso A) | * [[informatica:all-a/all11/start|A.A: 2011/2012]] (NB: il corso è unico; per comodità vengono usate le pagine del corso A) |
| * [[.algoB_10:|A.A. 2010/2011]] | * [[informatica:all-b/algob_10/start:|A.A. 2010/2011]] |
| | |
| ===== Orario Lezioni ===== | ===== Orario Lezioni ===== |
| |
| ^ Orario delle Lezioni ^^^^ | ^ Orario delle Lezioni ^^^^ |
| |Martedì | 11-13 | B | Teoria | | |Martedì | 11-13 | A | Teoria | |
| |Mercoledì | 11-13 | B | Teoria | | |Mercoledì | 11-13 | A | Teoria | |
| |Giovedì | 14-16 | H,M | Laboratorio | | |Giovedì | 14-16 | H,M | Laboratorio | |
| |Venerdì | 11-13 | B | Teoria | | |Venerdì | 11-13 | A | Teoria | |
| | |
| |
| Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella. | Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella. |
| |
| Per avere una idea della tipologia delle prove, si consultino i testi dell'[[http://www.cli.di.unipi.it/doku/doku.php/informatica/all-b/algob_14/start|anno scorso]]. | Per avere una idea della tipologia delle prove, si consultino i testi dell'[[http://www.cli.di.unipi.it/doku/doku.php/informatica/all-b/algob_13/start|anno scorso]]. |
| |
| ^ Data ^ Tipo Prova ^ Documento ^ Note ^ | ^ Data ^ Tipo Prova ^ Documento ^ Note ^ |
| | | | | | | | 02/04/2014, ore 11.00 | Scritto (primo compitino)|{{:informatica:all-b:algo1_020414.pdf|}} |{{:informatica:all-b:VotiPrimoCompitino.pdf|lista dei risultati}}.| |
| | | 28/05/2014, ore 11.00 | Scritto (secondo compitino)|{{:informatica:all-b:algo1_28052014.pdf|}} |{{:informatica:all-b:SecondoCompitino.pdf|lista dei risultati}}. **Visione scritti e prima sessione orali**: martedì 3 giugno, dalle ore 9:15 in aula A1.| |
| | | 09/06/2014, ore 11.00 | Scritto |{{:informatica:all-b:algo1_090614.pdf|}} |{{:informatica:all-b:appgiugno.pdf|Risultati}}. **Correzione e visione scritti**: giovedì 12 giugno, ore 9:30 in aula B. **Orali**: lunedì 16 giugno, ore 9:15, aula B.| |
| | | 08/07/2014, ore 9:30 | Scritto |{{:informatica:all-a:algo1_08072014.pdf|}}, {{:informatica:all-b:algo1_08072014sol.pdf| Soluzioni}} |{{:informatica:all-b:AppLuglio.pdf|Risultati}}. **Visione scritti**: giovedì 10 luglio, ore 12:00 nel mio ufficio. **Orali**: mercoledì 16 luglio, ore 11:00 e ore 14:00, e giovedì 24 luglio, ore 14:00, nel mio ufficio.| |
| | | 08/09/2014, ore 9.30 | Scritto |{{:informatica:all-a:algo1_08092014.pdf|}}, {{:informatica:all-b:algo1_08092014sol.pdf| Soluzioni}}|{{:informatica:all-b:Votisettembre.pdf|Risultati}}. **Visione scritti**: giovedì 11 settembre, ore 10:00 nel mio ufficio. **Orali**: martedì 16 settembre, ore 9:30, nel mio ufficio e su appuntamento.| |
| | | 04/11/2014, ore 9.00 | Scritto |{{:informatica:all-b:algo1_04112014.pdf|}}|{{:informatica:all-b:votinovembre.pdf|Risultati}}. **Visione scritti**: mercoledì 5 novembre, ore 9:30 nel mio ufficio. **Orali**: su appuntamento.| |
| | | 14/01/2015, ore 9.00 | Scritto |{{:informatica:all-a:algo1_14012015.pdf|}},{{:informatica:all-a:algo140115sol.pdf|}} |{{:informatica:all-b:votigennaio.pdf|Risultati}}. **Visione scritti**: giovedì 15 gennaio, ore 11-13 ufficio Bernasconi. **Orali**: 20 gennaio ore 10 ufficio Bernasconi.| |
| | | 12/02/2015, ore 9.00 | Scritto |{{:informatica:all-a:algo1_12020215.pdf|}} |{{:informatica:all-b:voti120215.pdf|Risultati}}. **Visione scritti**: lunedì 16 febbraio, ore 12-13 ufficio Bernasconi. **Orali**: 18 febbraio, ore 10, ufficio Bernasconi (oppure su appuntamento).| |
| |
| |
| Prossime date per le prove di laboratorio: | Prossime date per le prove di laboratorio: |
| ^ Data ^ Ora ^ Aule ^ Documento ^ | ^ Data ^ Ora ^ Aule ^ Documento ^ |
| | | | | | | | 13/06/2014 | 9:00 |H, I, M |{{:informatica:all-b:lab20140613t1.pdf|Testo 1}} {{:informatica:all-b:lab20140613t2.pdf|Testo 2}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_13062014_1.zip|Test1]] [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_13062014_2.zip|Test2]]| |
| | | 27/06/2014 | 9:00 |H, I, M |{{:informatica:all-b:testo20140627.pdf|Testo}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_27062014.zip|Test]] | |
| | | 16/07/2014 | 9:00 |H, I, M |{{:informatica:all-b:testo20140716.pdf|Testo}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_16072014.zip|Test]] | |
| | | 15/09/2014 | 9:00 |H, I, M | {{:informatica:all-b:20140915.zip|Testo e test}} | |
| | | 06/11/2014 | 9:00 |I, M | {{:informatica:all-b:testo20141106.pdf|Testo}} e {{:informatica:all-b:testset20141106.zip|test}} | |
| | | 16/01/2015 | 9:00 |H, I, M | {{:informatica:all-b:testo20150116.pdf|Testo}} e {{:informatica:all-b:testset20150116.zip| test}} | |
| | | 17/02/2015 | 9:00 |H, I, M | | |
| |
| Prossime date per le prove orali: | Prossime date per le prove orali: |
| ^ Data ^ Ora ^ Aula ^ | ^ Data ^ Ora ^ Aula ^ |
| | | | | | | 03/06/2014 | 9:15 | aula A1 | |
| | | 16/06/2014 | 9:15 | aula B | |
| | | 30/06/2014 | 9:15 | ufficio Bernasconi | |
| | | 10/07/2014 | 9:30 | ufficio Bernasconi | |
| | | 16/07/2014 | 11:00, 14:00 | ufficio Bernasconi | |
| | | 24/07/2014 | 14:00 | ufficio Bernasconi | |
| | | 16/09/2014 | 9:30 | ufficio Bernasconi | |
| | | 20/01/2015 | 10:00 | ufficio Bernasconi | |
| | | 18/02/2015 | 10:00 | ufficio Bernasconi | |
| ===== Libri di testo ===== | ===== Libri di testo ===== |
| | |
| | * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione)//. Pearson, 2012. Sito web: [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/]]. [[http://tinyurl.com/d9ajvky |Errata]]. |
| | |
| | |
| | * **[CGG]** P. Crescenzi, G. Gambosi, R. Grossi. //Strutture di dati e algoritmi: progettazione, analisi e visualizzazione//. Addison-Wesley, 2005. Per approfondimenti ed errata: http://www.algoritmica.org/home |
| |
| |
| |
| | |
| |
| * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione)//. Pearson, 2012. Sito web: [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/]]. [[http://tinyurl.com/d9ajvky |Errata]]. | |
| | |
| |
| Per il laboratorio, un testo fra: | Per il laboratorio, un testo fra: |
| ===== Registro delle Lezioni ===== | ===== Registro delle Lezioni ===== |
| ^ Data ^ Argomento ^ Rif. Biblio ^ | ^ Data ^ Argomento ^ Rif. Biblio ^ |
| | | | | | | 18/02/2014 | Introduzione al corso: intervento del Prof. Roberto Grossi. | | |
| | | 19/02/2014 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{:informatica:all-b:lezione1.pdf|Lucidi}} {{:informatica:all-b:istruzioni.pdf|Istruzioni per testing}} | |
| | | 20/02/2014 | **Laboratorio**: Funzioni e puntatori. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lezione2.pdf|Lucidi}}| |
| | | 21/02/2014 | Nozioni di Algoritmo, Problema, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete. |{{:informatica:all-b:12monete.pdf|12 monete}}| |
| | | 25/02/2014 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo e caso medio. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi.| {{:informatica:all-b:2_asintotica.pdf|Notazione asintotica (dispensa Prof. Luccio)}}; [CGGR]: introduzione; {{:informatica:all-b:prerequisiti.pdf|Formule utili}}| |
| | | 26/02/2014 | **Laboratorio**: Puntatori, Array, e stringhe. Uso di Valgrind. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lezione3.pdf|Lucidi}}| |
| | | 27/02/2014 | **Laboratorio**: Allocazione dinamica della memoria. |{{:informatica:all-b:lezione4.pdf|Lucidi}}| |
| | | 28/02/2014 | Array di dimensione variabile. Selection Sort e Insertion Sort: proprietà e complessità al caso ottimo, medio e pessimo.| [CGGR]: cap. 1.| |
| | | 04/03/2014 | Algoritmi di ordinamento stabili. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo.|{{:{:informatica:all-b:limitiInf.pdf|limiti inferiori}}| |
| | | 05/03/2014 | Limite inferiore per l'ordinamento per confronti. Il problema della ricerca: ricerca binaria ricorsiva: analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort.| [CGGR]: pag 56, cap 3.| |
| | | 06/03/2014 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{:informatica:all-b:lezione5.pdf|Lucidi}} | |
| | | 07/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità.| | |
| | | 11/03/2014 | Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione.| {{:informatica:all-a:Ricorrenze.pdf| Ricorrenze (dispensa Prof. Luccio)}}.| |
| | | 12/03/2014 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio.| [CGGR]: cap 3 e cap 5.| |
| | | 13/03/2014 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione6.pdf|Lucidi}} | |
| | | 14/03/2014 | Selezione dell'elemento di rango r in un array (QuickSelect). Moltiplicazione veloce di interi e matrici.|[CGGR]: cap 3 e cap 5.| |
| | | 18/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità. |{{:informatica:all-b:esercizi2014.pdf|Esercizi}}| |
| | | 19/03/2014 | Code con priorità: definizione, operazioni Empty, Enqueue, Dequeue, First. Heap di massimo: definizione, proprietà e rappresentazione in memoria (allocazione implicita in un array). |[CGGR]: cap 2.| |
| | | 20/03/2014 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Puzzle: La scala e Corsa di cavalli | {{:informatica:all-b:lezione7.pdf|Lucidi}} {{:informatica:all-b:quicksort_parziale.c.zip|QuickSortParziale}} {{:informatica:all-b:partition.pdf|Partizionamento}} | |
| | | 24/03/2014 |Heap di massimo: implementazione delle operazioni Enqueue, First, Dequeue. HeapSort: definizione e analisi. |[CGGR]: cap 2.| |
| | | 25/03/2014 | Ordinamento di interi: Counting sort e Radix Sort. |{{:informatica:all-a:cormen-contingradixsort.pdf|[CLR] cap. 8}}| |
| | | 26/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità. | | |
| | | 27/03/2014 | **Laboratorio**: Qsort e ripasso delle struct|{{:informatica:all-b:lezione8.pdf|Lucidi}}| |
| | | 28/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità (heap, numeri di Fibonacci). | | |
| | | 02/04/2014 | {{:informatica:all-b:algo1_020414.pdf | Prima prova di verifica intermedia. }}| | |
| | | 08/04/2014 | Algoritmi per il calcolo dei numeri di Fibonacci. Correzione della prima prova di verifica intermedia.| | |
| | | 09/04/2014 | Introduzione alla Programmazione Dinamica. Distanza tra due stringhe (Edit Distance). | {{:informatica:all-a:pr_din.pdf|Programmazione dinamica (dispensa Prof. Luccio)}} ; [CGGR]: cap 6.| |
| | | 10/04/2014 | **Laboratorio**: Esercizi d'esame: qsort e struct|{{:informatica:all-b:lezione9.pdf|Lucidi}} | |
| | | 11/04/2014 | Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. |[CGGR]: cap 6.| |
| | | 15/04/2014 | Algoritmi pseudopolinomiali. Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. |[CGGR]: cap 6. {{:informatica:all-b:esercizipd.pdf|Esercizi}}| |
| | | 16/04/2014 | Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi cardinali. Alberi ordinali: memorizzazione binarizzata. |[CGGR]: cap 1, cap 3.| |
| | | 17/04/2014 | **Laboratorio**: Liste | {{:informatica:all-b:lezione10.pdf|Lucidi}}| |
| | | 30/04/2014 | Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione. |[CGGR]: cap 4.| |
| | | 02/05/2014 | Alberi binari 1-bilanciati: alberi di Fibonacci; dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni). |[CGGR]: cap 4; {{:informatica:all-b:rotazioniavl.pdf| lucidi}}.| |
| | | 06/05/2014 | Alberi AVL: esempio di inserimento con rotazioni, cancellazione: cenni. Introduzione alle tabelle hash. |[CGGR]: cap 4.| |
| | | 07/05/2014 | Dizionari: realizzazione con tabelle hash (con liste di trabocco e a indirizzamento aperto). |[CGGR]: cap 4.| |
| | | 07/05/2014 | **Esercitazione**: progettazione di algoritmi di programmazione dinamica per problemi su scacchiera.|{{:informatica:all-b:esercizipd-sol.pdf|EserciziPD: soluzioni}}| |
| | | 08/05/2014 | **Laboratorio**: Alberi| {{:informatica:all-b:lezione11.pdf|Lucidi}}| |
| | | 09/05/2014 | **Esercitazione**: progettazione di algoritmi efficienti su alberi binari, ABR e AVL.|{{:informatica:all-b:esercizialberi2014.pdf|EserciziAB}}| |
| | | 13/05/2013 | Grafi: definizioni, rappresentazione di grafi in memoria. |[CGGR]: cap 7.| |
| | | 14/05/2013 | Grafi: visita in ampiezza e in profondità; classificazione degli archi. |[CGGR]: cap 7.| |
| | | 14/05/2013 | **Esercitazione**: progettazione di algoritmi efficienti (dizionari e alberi). |{{:informatica:all-b:esercizi_su_dizionari_e_alberi.pdf|Esercizi}}, {{:informatica:all-b:soluzioniDiz.pdf|soluzioni}}.| |
| | | 15/05/2014 | **Laboratorio**: Tabelle Hash| {{:informatica:all-b:lezione12.pdf|Lucidi}}| |
| | | 16/05/2014 | Ordinamento topologico di un grafo diretto aciclico (DAG): algoritmo e analisi. |[CGGR]: cap 7.| |
| | | 20/05/2014 | Problemi indecidibili: il problema della fermata. Problemi intrattabili: le torri di Hanoi (algoritmo, analisi del numero di mosse); generazione delle stringhe binarie. | [CGGR] {{:informatica:all-b:Capitolo00.pdf|prologo}}.| |
| | | 21/05/2014 | Generazione di tutte le permutazioni. Le classi di complessità P e EXP. Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. Esempio di riduzione: SAT - Clique.| [CGGR] {{:informatica:all-b:Capitolo00.pdf|prologo}}, cap 8; {{:informatica:all-b:PNP.pdf|Lucidi}}.| |
| | | 21/05/2014 | Esercitazione: progettazione di algoritmi efficienti su grafi. |{{:informatica:all-b:soluzionigrafi.pdf| Esercizi e soluzioni}} | |
| | | 22/05/2014 | **Laboratorio**: Simulazione prova d'esame| | |
| | | 27/05/2014 | **Esercitazione**: certificati polinomiali e algoritmi di verifica.| | |
| | | 28/05/2014 | {{:informatica:all-b:algo1_28052014.pdf | Seconda prova di verifica intermedia.}}| | |
| | |
| | |
| | |
| | |
