| Prossima revisione | Revisione precedente |
| informatica:all-a:all15:start [17/02/2016 alle 10:50 (9 anni fa)] – creata Linda Pagli | informatica:all-a:all15:start [17/02/2016 alle 13:00 (9 anni fa)] (versione attuale) – [Anni accademici precedenti] Linda Pagli |
|---|
| Algoritmica e Laboratorio - Corso A | ====== Algoritmica e Laboratorio - Corso A ====== |
| |
| Anno accademico 2015/2016 | ===== Informazioni Generali ===== |
| |
| | **Docenti:** [[http://www.di.unipi.it/~pagli/|Linda Pagli]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]], [[http://www.di.unipi.it/~rosone/ |Giovanna Rosone]], [[http://zola.di.unipi.it/andrea |Andrea Farruggia]] |
| |
| Informazioni Generali | |
| |
| Docenti: Linda Pagli, Rossano Venturini, Andrea Marino, Andrea Farruggia | |
| |
| (Docenti corso B: Anna Bernasconi, Rossano Venturini, Nadia Pisanti, Andrea Farruggia | (**Docenti [[informatica:all-b:start|corso B]]:** [[http://www.di.unipi.it/~annab/|Anna Bernasconi]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]], [[http://www.di.unipi.it/~pisanti/|Nadia Pisanti]], [[http://zola.di.unipi.it/andrea |Andrea Farruggia]] |
| |
| Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. | |
| |
| Semestre: secondo. | |
| |
| Ricevimento studenti: dopo ogni lezione e su appuntamento. | **Impegno:** 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. |
| | |
| | **Semestre:** secondo. |
| | |
| | **Ricevimento studenti:** dopo ogni lezione e su appuntamento. |
| |
| Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti. | Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti. |
| |
| | ===== AVVISO ===== |
| |
| AVVISO | **La lezione del giorno 15/05/2015 (esercitazione) è spostata al 14/05/2014 dalle 14 alle 16 in aula A** |
| | ===== Anni accademici precedenti ===== |
| | * [[informatica/all-a/all14:|A.A. 2013/2014]] |
| | * [[informatica/all-a/all13:|A.A. 2012/2013]] |
| | * [[informatica/all-a/all11:|A.A. 2011/2012]] |
| | |
| | |
| | |
| | ===== Orario Lezioni ===== |
| |
| | ^ Orario delle Lezioni ^^^^ |
| | |Martedì | 14-16 | H, M | Laboratorio | |
| | |Mercoledì | 11-13 | A | Teoria | |
| | |Giovedì | 14-16 | A | Teoria | |
| | |Venerdì | 11-13 | A | Teoria | |
| | |
| |
| Anni accademici precedenti | |
| |
| A.A. 2014/2015 | ===== Obiettivi del Corso ===== |
| A.A. 2013/2014 | L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo. |
| A.A. 2012/2013 | |
| |
| Orario Lezioni | Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe. |
| |
| Orario delle Lezioni | |
| Martedì 11-13 A Teoria | |
| Mercoledì 11-13 A Teoria | |
| Giovedì 16-18 H, M Laboratorio | |
| Venerdì 11-13 A Teoria | |
| Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio. | |
| |
| | ===== Modalità e Appelli di Esame===== |
| | |
| | L'esame consiste di tre prove: |
| |
| Obiettivi del Corso | * Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio. |
| | * Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un __test di idoneità__ il cui superamento permette allo studente di essere ammesso a sostenere la prova orale. |
| | * Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta. |
| |
| L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo. | Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella. |
| |
| Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe. | Per avere una idea della tipologia delle prove, si consultino i testi dell'[[http://www.cli.di.unipi.it/doku/doku.php/informatica/all-a/all14/start|anno scorso]]. |
| |
| | ^ Data ^ Tipo Prova ^ Documento ^ Note ^ |
| | | 14/04/2015, ore 11.00 | Scritto (primo compitino)|{{:informatica:all-b:algo1_140415.pdf|}} |{{:informatica:all-a:risalg14-4-2015.pdf|lista dei risultati}}.| |
| | | 29/05/2015, ore 9.00 | Scritto (secondo compitino)|{{:informatica:all-b:Algo1_290515.pdf|testo}} e {{:informatica:all-b:Algo1_290515SOL.pdf|soluzioni}} | {{:informatica:all-a:risalg29-5-2015.pdf|lista dei risultati|}}. **Visione scritti:** martedì 3 giugno, dalle 12:00 alle 13:00, ufficio pagli. | |
| | | 10/06/2015, ore 9:30 | Orali | | ufficio pagli | |
| | | 12/06/2015, ore 9:30 | Scritto | {{:informatica:all-a:algo1_120615.pdf|testo}} e {{:informatica:all-a:sol12_615.pdf|soluzioni}} |{{:informatica:all-a:risalg12_6_2015.docx|lista dei risultati|}} **Visione scritti:** martedì 16 giugno, dalle 11:00 alle 13:00, ufficio pagli. | |
| | | 01/07/2015, ore 9:30 | Orali | | ufficio pagli | |
| | | 03/07/2015, ore 9:30 | Scritto |{{:informatica:all-b:algo1_0307.pdf|testo}} e {{:informatica:all-b:Algo1_0307sol.pdf|soluzioni}}|{{:informatica:all-a:risalg3_7_2015.pdf|lista dei risultat}} **Visione scritti:** lunedì 6 luglio ore 11-12 ufficio Bernasconi | |
| | | 14/07/2015, ore 9:30 | Orali | | ufficio pagli | |
| | | 10/09/2015, ore 14:30 | Scritto |{{:informatica:all-b:Algo1_100915.pdf|testo}} e {{:informatica:all-b:Algo1_100915sol.pdf|soluzioni}} |{{:informatica:all-a:ris10-9-2015.pdf|lista dei risultati}} | |
| | | 15/09/2015, ore 14:00 | Orali | | ufficio pagli | |
| | | 11/01/2016, ore 9:00 | Scritto |{{:informatica:all-a:algo1_110116.pdf|testo}} e {{:informatica:all-b:Algo1_110116SOL.pdf|soluzioni}} |**Risultati**: nessun compito è risultato sufficiente. **Visione scritti:** su appuntamento. | |
| | | 01/02/2016, ore 9:00 | Scritto |{{:informatica:all-a:algo1_010216.pdf|testo}} e {{:informatica:all-a:sol-algo1_010216.pdf|soluzioni}}|**Risultati**:{{:informatica:all-a:ris1-2-2016.pdf|lista dei risultati}} **Visione scritti:** su appuntamento. | |
| | | 08/02/2015, ore 10:00 | Orali | | ufficio pagli | |
| | ===== ATTENZIONE ===== |
| |
| Modalità e Appelli di Esame | ** Il secondo compitino è riservato solo agli studenti che hanno preso un voto ≥ 18 al primo compitino ** |
| |
| L'esame consiste di tre prove: | |
| |
| Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio. | |
| Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un test di idoneità il cui superamento permette allo studente di essere ammesso a sostenere la prova orale. | |
| Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta. | |
| 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'anno scorso. | Prossime date per le prove di laboratorio: |
| | ^ Data ^ Ora ^ Aule ^ Documento ^ |
| | | 04/06/2015 | 9:00 | H-M-I | {{:informatica:all-b:esame_040615.pdf|Testo}} {{:informatica:all-b:testset.zip|TestSet}}| |
| | | 22/06/2015 | 9:00 | H-M-I | {{:informatica:all-b:esame20150622.zip|Testo}} | |
| | | 09/07/2015 | 9:00 | H-M-I | | |
| | | 15/09/2015 | 9:00 | H-M-I | | |
| | | 06/11/2015 | 10:00 | M | Appello straordinario | |
| | | 13/01/2016 | 9:00 | H-M-I | | |
| | | 03/02/2016 | 9:00 | H-M-I | | |
| |
| Data Tipo Prova Documento Note | |
| 14/04/2015, ore 11.00 Scritto (primo compitino) algo1_140415.pdf lista dei risultati. | |
| 29/05/2015, ore 9.00 Scritto (secondo compitino) testo e soluzioni lista dei risultati|. Visione scritti: martedì 3 giugno, dalle 12:00 alle 13:00, ufficio pagli. | |
| 10/06/2015, ore 9:30 Orali ufficio pagli | |
| 12/06/2015, ore 9:30 Scritto testo e soluzioni lista dei risultati| Visione scritti: martedì 16 giugno, dalle 11:00 alle 13:00, ufficio pagli. | |
| 01/07/2015, ore 9:30 Orali ufficio pagli | |
| 03/07/2015, ore 9:30 Scritto testo e soluzioni lista dei risultat Visione scritti: lunedì 6 luglio ore 11-12 ufficio Bernasconi | |
| 14/07/2015, ore 9:30 Orali ufficio pagli | |
| 10/09/2015, ore 14:30 Scritto testo e soluzioni lista dei risultati | |
| 15/09/2015, ore 14:00 Orali ufficio pagli | |
| 11/01/2016, ore 9:00 Scritto testo e soluzioni Risultati: nessun compito è risultato sufficiente. Visione scritti: su appuntamento. | |
| 01/02/2016, ore 9:00 Scritto testo e soluzioni Risultati:lista dei risultati Visione scritti: su appuntamento. | |
| 08/02/2015, ore 10:00 Orali ufficio pagli | |
| |
| ATTENZIONE | |
| |
| Il secondo compitino è riservato solo agli studenti che hanno preso un voto ≥ 18 al primo compitino | ===== Libri di testo ===== |
| |
| Prossime date per le prove di laboratorio: | * **[CLRS]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduzione agli algoritmi e strutture dati//. McGraw-Hill, Terza edizione, 2010. |
| | |
| | |
| | |
| | * **[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]]. |
| | |
| |
| Data Ora Aule Documento | Per il laboratorio, un testo fra: |
| 04/06/2015 9:00 H-M-I Testo TestSet | * **[KR]** B.W. Kernighan, D.M. Ritchie. //Il Linguaggio C//, Pearson-Prentice Hall, seconda edizione, 2008. |
| 22/06/2015 9:00 H-M-I Testo | * **[KP]** A. Kelley, I. Pohl. //C: Didattica e Programmazione//, Addison-Wesley, quarta edizione, 2004. |
| 09/07/2015 9:00 H-M-I | ===== Materiale per il Laboratorio ===== |
| 15/09/2015 9:00 H-M-I | |
| 06/11/2015 10:00 M Appello straordinario | |
| 13/01/2016 9:00 H-M-I | |
| 03/02/2016 9:00 H-M-I | |
| |
| Libri di testo | * **__Prerequisito__**: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro "Il Linguaggio C", B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008. |
| | * **__Strumenti per la programmazione__**: Un editore testuale (tipo ''Emacs''), e il compilatore ''gcc'', sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di //coding// che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come [[http://www.eclipse.org/|Eclipse]] esteso con il suo plug-in [[http://www.eclipse.org/cdt/|Eclipse C/C++ Development Tooling]]. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come [[http://www.virtualbox.org/|VirtualBox]], con una qualunque distribuzione Linux. Il **consiglio** è però quello di adoperare la combinazione minimale ''editor+gcc'' al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi **soltanto** sugli aspetti di //coding// degli algoritmi. |
| | * **__Sistema di Autovalutazione__**: [[http://vinello.isti.cnr.it:10000]] |
| |
| [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010. | |
| [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/. Errata. | |
| Per il laboratorio, un testo fra: | |
| |
| [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008. | |
| [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004. | |
| |
| Materiale per il Laboratorio | |
| |
| Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008. | |
| Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi. | |
| Sistema di Autovalutazione: http://vinello.isti.cnr.it:10000 | |
| |
| Programma del corso | ===== Programma del corso ===== |
| | - Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME). |
| | - Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio. |
| | - Limiti del calcolo: albero di decisione, limiti superiori e inferiori. |
| | - Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale. |
| | - Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento. |
| | - Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort. |
| | - Ordinamento di interi: Counting sort, Radix Sort. |
| | - Ordinamento di stringhe: ''qsort''-based. |
| | - Sottosequenza di somma massima. |
| | - Programmazione dinamica: LCS, Partizione e Zaino |
| | - Algoritmi randomizzati: Quicksort. |
| | - Generazione di combinazioni e permutazioni |
| | - Analisi ammortizzata: doubling di array, contatore binario, k ricerche. |
| | - Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto). |
| | - Alberi: rappresentazione e visite. |
| | - Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico. |
| | - Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse. |
| | - Grafi III: Minimum Spanning Tree e Shortest Path. |
| |
| Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME). | |
| Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio. | |
| Limiti del calcolo: albero di decisione, limiti superiori e inferiori. | |
| Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale. | |
| Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento. | |
| Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort. | |
| Ordinamento di interi: Counting sort, Radix Sort. | |
| Ordinamento di stringhe: qsort-based. | |
| Sottosequenza di somma massima. | |
| Programmazione dinamica: LCS, Partizione e Zaino | |
| Algoritmi randomizzati: Quicksort. | |
| Generazione di combinazioni e permutazioni | |
| Analisi ammortizzata: doubling di array, contatore binario, k ricerche. | |
| Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto). | |
| Alberi: rappresentazione e visite. | |
| Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico. | |
| Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse. | |
| Grafi III: Minimum Spanning Tree e Shortest Path. | |
| Data Argomento Rif. Biblio | |
| 24/02/2015 Concetto di algoritmo, moltiplicazione Egizia e problema delle 12 monete. 12 monete | |
| 25/02/2015 Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: correttezza e analisi di complessità al caso ottimo, medio e pessimo. [CLRS]: cap 1, cap 2: 2.1, 2.2. | |
| 26/02/2015 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Funzioni e puntatori. Cap. 2-3, Sez. 4.1-4.5, 5.1-5.5 e 7.1-7.4 di [KR]. Lucidi | |
| 27/02/2015 Paradigma del Divide et Impera. Merge: definizione, correttezza e complessità. Merge-Sort: definizione [CLRS]: cap : 2.3 | |
| 03/03/2015 Merge-Sort: analisi. Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo. [CLRS]: cap 3. | |
| 04/03/2015 Limite inferiore per il problema dell'ordinamento, esempio con 3 elementi, albero di decisione. Esercizi e esempi di notazioni asintotiche [CLRS]: cap 3. Cap.8 sez.1 | |
| 05/03/2015 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi | |
| 06/03/2015 Il problema della ricerca. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo. limiti inferiori | |
| 10/03/2015 Limiti inferiori: tecnica dell'oracolo o avversario, limite inferiore per la determinazione del primo e del secondo. Esercizi di ripasso Esercizi1oracol.pdf | |
| 11/03/2015 Metodi di soluzione dell'equazioni di ricorrenza: metodo iterativo, albero di ricorsione, metodo dell'esperto. [CLRS]: cap 4, sezioni da 4.4 a 4.6 | |
| 12/03/2015 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Lucidi | |
| 13/03/2015 Dimostrazione del teorema principale (solo per potenze esatte). Moltiplicazione veloce di interi. Esercizi. Moltiplicazione veloce di interi (Prof. Grossi) | |
| 17/03/2015 Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato. [CLRS] cap 7: 7.1, 7.2, 7.3. | |
| 18/03/2015 Quicksort randomizzato: analisi della complessità nel caso medio. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare. [CLRS] cap 7: 7.4.2, cap 9: 9.1, 9.2 (senza analisi nel caso medio). Numero di confronti di Randomized-Quicksort (Prof. Luccio) | |
| 19/03/2015 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Lucidi | |
| 20/03/2015 Esercitazione: progettazione di algoritmi e analisi di complessità. Esercizi | |
| 24/03/2015 Heap: definizione, realizzazione implicita come array, proprietà. Code di priorità: definizione, operazioni, realizzazione mediante heap. [CLRS] cap 6: 6.3, 6.4, 6.5. | |
| 25/03/2015 Nuove proprietà. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. [CLRS] cap 6: 6.1, 6.2, 6.3. | |
| 26/03/2015 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Lucidi QuickSortParziale Partizionamento | |
| 27/03/2015 HeapSort. Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort [CLRS] cap 8: 8.2. | |
| 31/03/2015 Radix Sort [CLRS] cap.8: 8.3. Esercitazione: progettazione di algoritmi e analisi di complessità. Esercizi (heap) | |
| 1/04/2015 Esercitazione: progettazione di algoritmi e analisi di complessità. | |
| 2/04/2015 Laboratorio: Qsort e ripasso delle struct. Lucidi | |
| 14/04/2015 Prima prova di verifica intermedia. | |
| 15/04/2015 Correzione della prima prova di verifica intermedia. Alberi binari: visite, algoritmi ricorsivi su alberi binari. [CLRS] cap 10: 10.4. [CGGR]: Algoritmi ricorsivi su alberi binari | |
| 16/04/2015 Laboratorio: Esercizi d'esame: qsort e struct. Lucidi | |
| 17/04/2015 Alberi binari di ricerca: definizione, max, min, predecessore, successore, ordinamento. [CLRS] cap 12: 12.1, 12.2. | |
| 21/04/2015 Alberi binari di ricerca: inserimento, cancellazione, costruzione e analisi. [CLRS] cap 12: 12.3 | |
| 22/04/2015 Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). [CGGR]: Alberi AVL, rotazioni. | |
| 23/04/2015 Laboratorio: Liste. Lucidi | |
| 24/04/2015 Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. EserciziAB | |
| 28/04/2015 Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio). [CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1. | |
| 29/04/2015 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica. [CLRS] cap 11: 11.4. Dispense Prof. Luccio. Esercizi su dizionari e alberi | |
| 30/04/2015 Laboratorio: Alberi Lucidi | |
| 5/05/2015 Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema dell'“Edit Distance”, definizione, proprietà, regola ricorsiva e ricostruzione della soluzione programmazione_dinamica edit_distance.pdf | |
| 6/05/2015 Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva, ricostruzione della soluzione [CLRS] cap 15: 15.4. | |
| 7/05/2015 Laboratorio: Tabelle Hash. Lucidi | |
| 8/05/2015 LCS: ottimalità della sottostruttura. Stampa LCS iterativo e ricorsivi. Apparizioni approssimate di una sequenza in un testo (cenni). Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). Esercizi su dizionari e alberi Soluzioni | |
| 12/05/2015 Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. [CLRS] cap 16: 16.2, esercizio 16.2.2. pseudopolinomialità. | |
| 13/05/2015 Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello Zaino. Introduzione ai grafi e BFS. [CGGR]: generazione delle sequenze binarie, Esercizi sulla Programmazione Dinamica, [CLRS] cap 22: 22.1, 22.2. | |
| 14/05/2015 Esercitazione: coda implementata con array, visita in ampiezza di un albero binario, esercizi sulla Programmazione Dinamica [CLRS] cap 10: 10.1.Soluzioni | |
| 14/05/2015 Laboratorio: Simulazione della prova di laboratorio. | |
| 19/05/2015 Grafi: visita in profondità (DFS); classificazione degli archi; ordinamento topologico di grafi diretti aciclici. [CLRS] cap 22: 22.3, 22.4. | |
| 20/05/2015 Esercitazione: progettazione di algoritmi efficienti su grafi. Esercizi | |
| 21/05/2015 Laboratorio: Soluzione della prova di laboratorio della scorsa settimana. soluzione | |
| 22/05/2015 Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Le classi di complessità P e NP: introduzione. calcolabilità | |
| 26/05/2015 Teoria della complessità: classe P; nozione di certificato polinomiale e classe NP; nozione di riduzione polinomiale; problemi NP-completi. Esempi: problema del ciclo euleriano; generazione di tutte le permutazioni e problema del ciclo hamiltoniano; riduzione SAT - Clique. [CLRS] cap 34: 34.1. Lucidi Generazione delle permutazioni e problema del ciclo hamiltoniano. | |
| |
| informatica/all-a/start.txt · Ultima modifica: 17/02/2016 alle 11:46 (44 secondi fa) da Linda Pagli | |===== Registro delle Lezioni ===== |
| Strumenti Pagina | |
| Modifica questa pagina | |
| Revisioni precedenti | |
| Puntano qui | |
| Sottoscrivi modifiche | |
| Torna su | |
| Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki | |
| |
| | ^ Data ^ Argomento ^ Rif. Biblio ^ |
| | | 24/02/2015 | Concetto di algoritmo, moltiplicazione Egizia e problema delle 12 monete. |{{:informatica:all-b:12monete.pdf|12 monete}} | |
| | | 25/02/2015 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: correttezza e analisi di complessità al caso ottimo, medio e pessimo.| [CLRS]: cap 1, cap 2: 2.1, 2.2.| |
| | | 26/02/2015 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Funzioni e puntatori. | Cap. 2-3, Sez. 4.1-4.5, 5.1-5.5 e 7.1-7.4 di [KR]. {{:informatica:all-b:lezione1-1415.pdf|Lucidi}}| |
| | | 27/02/2015 | Paradigma del Divide et Impera. Merge: definizione, correttezza e complessità. Merge-Sort: definizione| [CLRS]: cap : 2.3| |
| | | 03/03/2015 | Merge-Sort: analisi. Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo. | [CLRS]: cap 3.| |
| | | 04/03/2015 | Limite inferiore per il problema dell'ordinamento, esempio con 3 elementi, albero di decisione. Esercizi e esempi di notazioni asintotiche| [CLRS]: cap 3. Cap.8 sez.1| |
| | | 05/03/2015 | **Laboratorio**: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lezione2-1415.pdf|Lucidi}}| |
| | | 06/03/2015 |Il problema della ricerca. 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}}| |
| | | 10/03/2015 |Limiti inferiori: tecnica dell'oracolo o avversario, limite inferiore per la determinazione del primo e del secondo. Esercizi di ripasso| {{{:informatica:all-a:esercizi1-2015.pdf|Esercizi1}}{{:informatica:all-a:oracol.pdf|}}| |
| | | 11/03/2015 |Metodi di soluzione dell'equazioni di ricorrenza: metodo iterativo, albero di ricorsione, metodo dell'esperto.| [CLRS]: cap 4, sezioni da 4.4 a 4.6| |
| | | 12/03/2015 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. | {{:informatica:all-b:lezione3-1415.pdf|Lucidi}} | |
| | |13/03/2015 | Dimostrazione del teorema principale (solo per potenze esatte). Moltiplicazione veloce di interi. Esercizi.|{{:informatica:all-b:moltveloce.pdf|Moltiplicazione veloce di interi (Prof. Grossi)}}| |
| | |17/03/2015 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato.| [CLRS] cap 7: 7.1, 7.2, 7.3.| |
| | |18/03/2015 | Quicksort randomizzato: analisi della complessità nel caso medio. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare.| [CLRS] cap 7: 7.4.2, cap 9: 9.1, 9.2 (senza analisi nel caso medio). {{:informatica:all-b:quicksort.pdf|Numero di confronti di Randomized-Quicksort (Prof. Luccio)}}| |
| | | 19/03/2015 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione4-1415.pdf|Lucidi}} | |
| | |20/03/2015 | **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:Esercizi2-2015.pdf|Esercizi}}| |
| | |24/03/2015 | Heap: definizione, realizzazione implicita come array, proprietà. Code di priorità: definizione, operazioni, realizzazione mediante heap.|[CLRS] cap 6: 6.3, 6.4, 6.5.| |
| | |25/03/2015 | Nuove proprietà. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. |[CLRS] cap 6: 6.1, 6.2, 6.3.| |
| | |26/03/2015 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{:informatica:all-b:lezione5-1415.pdf|Lucidi}} {{:informatica:all-b:quicksort_parziale.c.zip|QuickSortParziale}} {{:informatica:all-b:partition.pdf|Partizionamento}} | |
| | |27/03/2015 |HeapSort. Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort |[CLRS] cap 8: 8.2.| |
| | |31/03/2015 |Radix Sort [CLRS] cap.8: 8.3. **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:esercizi3-2015.pdf|Esercizi (heap)}}| |
| | | 1/04/2015 | **Esercitazione**: progettazione di algoritmi e analisi di complessità.| | |
| | | 2/04/2015 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-b:lezione6-1415.pdf|Lucidi}} | |
| | | 14/04/2015 | {{:informatica:all-b:algo1_140415.pdf | Prima prova di verifica intermedia. }}| | |
| | | 15/04/2015 | Correzione della prima prova di verifica intermedia. Alberi binari: visite, algoritmi ricorsivi su alberi binari.| [CLRS] cap 10: 10.4. [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}}| |
| | | 16/04/2015 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{:informatica:all-b:lezione9.pdf|Lucidi}} | |
| | | 17/04/2015 | Alberi binari di ricerca: definizione, max, min, predecessore, successore, ordinamento.| [CLRS] cap 12: 12.1, 12.2.| |
| | | 21/04/2015 | Alberi binari di ricerca: inserimento, cancellazione, costruzione e analisi.| [CLRS] cap 12: 12.3| |
| | | 22/04/2015 | Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni).| [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}}, {{:informatica:all-b:figureAVL.pdf| rotazioni}}.| |
| | | 23/04/2015 | **Laboratorio**: Liste. | {{:informatica:all-a:lezione8-1415.pdf|Lucidi}}| |
| | | 24/04/2015 | **Esercitazione**: progettazione di algoritmi efficienti su alberi binari, ABR e AVL.|{{:informatica:all-b:esercizialberi2014.pdf|EserciziAB}}| |
| | | 28/04/2015 | Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio).|[CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1. | |
| | | 29/04/2015 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica. |[CLRS] cap 11: 11.4. {{:informatica:all-b:hash.pdf|Dispense Prof. Luccio}}. {{:informatica:all-b:esercizi_su_dizionari_e_alberi.pdf|Esercizi su dizionari e alberi}} | |
| | | 30/04/2015 | **Laboratorio**: Alberi| {{:informatica:all-b:lezione9-1415.pdf|Lucidi}}| |
| | | 5/05/2015 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema dell'"Edit Distance", definizione, proprietà, regola ricorsiva e ricostruzione della soluzione | {{:informatica:all-b:PD.pdf)|programmazione_dinamica}} {{:informatica:all-a:edit_distance.pdf|}}| |
| | | 6/05/2015 | Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva, ricostruzione della soluzione|[CLRS] cap 15: 15.4. | |
| | | 7/05/2015 | **Laboratorio**: Tabelle Hash. | {{:informatica:all-b:lezione10-1415.pdf|Lucidi}} | |
| | | 8/05/2015 | LCS: ottimalità della sottostruttura. Stampa LCS iterativo e ricorsivi. Apparizioni approssimate di una sequenza in un testo (cenni). Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi).| {{:informatica:all-b:esercizi_su_dizionari_e_alberi.pdf|Esercizi su dizionari e alberi}} {{:informatica:all-b:SoluzioniDizionari.pdf|Soluzioni}} | |
| | | 12/05/2015 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. | [CLRS] cap 16: 16.2, {{:informatica:all-b:ZainoPD.pdf|esercizio 16.2.2}}. {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}}.| |
| | | 13/05/2015 |Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello Zaino. Introduzione ai grafi e BFS. |[CGGR]: {{:informatica:all-b:generaBinPerm.pdf |generazione delle sequenze binarie}}, {{:informatica:all-b:esercizipd.pdf|Esercizi sulla Programmazione Dinamica}}, [CLRS] cap 22: 22.1, 22.2.| |
| | | 14/05/2015 |**Esercitazione**: coda implementata con array, visita in ampiezza di un albero binario, esercizi sulla Programmazione Dinamica| [CLRS] cap 10: 10.1.{{:informatica:all-b:esercizipd-sol.pdf|Soluzioni}}| |
| | | 14/05/2015 | **Laboratorio**: Simulazione della prova di laboratorio. | | |
| | | 19/05/2015 | Grafi: visita in profondità (DFS); classificazione degli archi; ordinamento topologico di grafi diretti aciclici. | [CLRS] cap 22: 22.3, 22.4.| |
| | | 20/05/2015 | **Esercitazione**: progettazione di algoritmi efficienti su grafi.|{{:informatica:all-b:eserciziGRAFI.pdf|Esercizi}}| |
| | | 21/05/2015 | **Laboratorio**: Soluzione della prova di laboratorio della scorsa settimana. |{{:informatica:all-a:ex-3.pdf|soluzione}}| |
| | | 22/05/2015 | Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Le classi di complessità P e NP: introduzione.|{{:informatica:all-a:calcolabilita2015.pdf|calcolabilità}}| |
| | | 26/05/2015 | Teoria della complessità: classe P; nozione di certificato polinomiale e classe NP; nozione di riduzione polinomiale; problemi NP-completi. Esempi: problema del ciclo euleriano; generazione di tutte le permutazioni e problema del ciclo hamiltoniano; riduzione SAT - Clique. | [CLRS] cap 34: 34.1. {{:informatica:all-b:PNP2015.pdf|Lucidi}} {{:informatica:all-b:permutazioni.pdf |Generazione delle permutazioni e problema del ciclo hamiltoniano.}} | |
