| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| matematica:asd:asd_13:start [08/05/2014 alle 12:29 (11 anni fa)] – [Avvisi] Roberto Grossi | matematica:asd:asd_13:start [25/07/2014 alle 14:32 (11 anni fa)] (versione attuale) – [Modalità d'esame] Roberto Grossi |
|---|
| ==== Avvisi ==== | ==== Avvisi ==== |
| |
| * IMPORTANTE: compilare il questionario disponibile su [[www.questionario.unipi.it]] | * IMPORTANTE: compilare il questionario [[http://www.questionario.unipi.it|disponibile in rete]] |
| * Il corso inizia **venerdì 28 febbraio ore 11 in aula E1**. | * Il testo del [[progetto_13|[progetto]]] e del [[mini_progetto_13|[mini-progetto]]] è disponibile. |
| * Il laboratorio inizia **venerdì 7 marzo ore 14 in aula M-lab**. | * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento. |
| * Sintesi degli argomenti svolti nel [[laboratorio_13|[laboratorio]]]. | * Sintesi degli argomenti svolti nel [[laboratorio_13|[laboratorio]]]. |
| * [[https://www.dropbox.com/sh/o7hyigl7ffbbbxa/Awg3RMaGgR|Immagini usate]] durante la lezione. | * [[https://www.dropbox.com/sh/o7hyigl7ffbbbxa/Awg3RMaGgR|Immagini usate]] durante la lezione. |
| * [[http://www.di.unipi.it/~grossi/html5/|Visualizzazioni in HTML5]] mostrate a lezione. | * [[http://www.di.unipi.it/~grossi/html5/|Visualizzazioni in HTML5]] mostrate a lezione. |
| * Esami: Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento. | |
| * Per il ricevimento, consultare la [[http://www.di.unipi.it/~grossi|homepage del docente]]. | * Per il ricevimento, consultare la [[http://www.di.unipi.it/~grossi|homepage del docente]]. |
| ==== Motivazioni ==== | ==== Motivazioni ==== |
| * [[progetto_13|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto). | * [[progetto_13|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto). |
| * Parte seconda, comune per tutti: | * Parte seconda, comune per tutti: |
| * verifica tramite l'orale basato sul programma dettagliato: Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (par.4.5 facoltativo, [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (solo par.5.1 e 5.2), Capitolo 6 (saltare), Capitolo 7 (par. 7.1, 7.2, 7.3.1), Capitolo 8 (tutto tranne par. 8.7 e 8.11). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]]. | * verifica tramite l'orale basato sul programma dettagliato: Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (più [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (solo par.5.1), Capitolo 6 (par. 6.1, 6.3, 6.4, 6.5), Capitolo 7 (par. da 7.1 a 7.4), Capitolo 8 (par. da 8.1 a 8.5 più par. 8.8). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]]. |
| |
| |
| ==== Programma ==== | ==== Programma ==== |
| |
| [[http://unimap.unipi.it/registri/printregistriNEW.php|Registro delle lezioni]] | [[http://unimap.unipi.it/registri/printregistriNEW.php?re=130300::::&ri=9172|Registro delle lezioni]] |
| |
| ^ Data ^ Argomento ^ Riferimenti e note ^ | ^ Data ^ Argomento ^ Riferimenti e note ^ |
| | 07.03.2014| Scheduling di lavori e ordinamento (insertion sort, selection sort), con analisi asintotica della complessità. Complessità di un algoritmo e di un problema, limiti superiori e inferiori. "Fooling argument" per limiti inferiori lineari. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.7, par.1.2]] | | | 07.03.2014| Scheduling di lavori e ordinamento (insertion sort, selection sort), con analisi asintotica della complessità. Complessità di un algoritmo e di un problema, limiti superiori e inferiori. "Fooling argument" per limiti inferiori lineari. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.7, par.1.2]] | |
| | 07.03.2014| Segmento di somma massima | [[laboratorio_13|lab]] | | | 07.03.2014| Segmento di somma massima | [[laboratorio_13|lab]] | |
| | 10.03.2014| Strutture di dati per rappresentare le istanze dei problemi: elementari e sequenze (array e liste). Memorizzazione di array e liste e impatto sul costo di accesso. Array di dimensione variabile. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.1, 0.2, 0.4, par. 1.1]] | | | 11.03.2014| Strutture di dati per rappresentare le istanze dei problemi: elementari e sequenze (array e liste). Memorizzazione di array e liste e impatto sul costo di accesso. Array di dimensione variabile. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.1, 0.2, 0.4, par. 1.1]] | |
| | 14.03.2014| Limiti superiori e inferiori per il problema dell'ordinamento mediante confronti. Semplici esempi di algoritmi lineari (ordinare zeri e uni mediante scambi). | [CGGR, teorema 2.4] | | | 14.03.2014| Limiti superiori e inferiori per il problema dell'ordinamento mediante confronti. Semplici esempi di algoritmi lineari (ordinare zeri e uni mediante scambi). | [CGGR, teorema 2.4] | |
| | 14.03.2014| Array di dimensione variabile | [[laboratorio_13|lab]] | | | 14.03.2014| Array di dimensione variabile | [[laboratorio_13|lab]] | |
| | 02.05.2014| Quicksort randomizzato: analisi con variabili indicatrici. Hash universale. | {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}} {{:matematica:asd:asd_13:clrs_universal_hashing.pdf|par 11.3.3}}| | | 02.05.2014| Quicksort randomizzato: analisi con variabili indicatrici. Hash universale. | {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}} {{:matematica:asd:asd_13:clrs_universal_hashing.pdf|par 11.3.3}}| |
| | 02.05.2014| Realizzazione del cuckoo hashing. | [[laboratorio_13|lab]] | | | 02.05.2014| Realizzazione del cuckoo hashing. | [[laboratorio_13|lab]] | |
| | 06.05.2014| Lezione | [rif] | | | 06.05.2014| Programmazione dinamica | [CGGR, par.6.1,6.3,6.4,6.5] | |
| | 09.05.2014| Lezione | [rif] | | | 09.05.2014| Rappresentazione e visita di grafi | [ [CGGR, par.7.1-7.3] | |
| | 09.05.2014| Laboratorio | [[laboratorio_13|lab]] | | | 09.05.2014| Esempi di programmazione dinamica | [[laboratorio_13|lab]] | |
| | 13.05.2014| Lezione | [rif] | | | 13.05.2014| Cammini minimi e algoritmo di Dijkstra. Pesi negativi: algoritmi di Bellman-Ford e Floyd-Warshall.| [CGGR, par.7.4] | |
| | 16.05.2014| Lezione | [rif] | | | 16.05.2014| Cammini euleriani e hamiltoniani. Classi di complessità P e NP. Colorazioni di grafi. Problema della soddisfacibilità (SAT). Riduzioni polinomiali e teorema di Cook-Levin (senza dimostrazione). | [CGGR, par. 8.1-8.5] | |
| | 16.05.2014| Laboratorio | [[laboratorio_13|lab]] | | | 16.05.2014| Generazione di grafi e visita in ampiezza | [[laboratorio_13|lab]] | |
| | 20.05.2014| Lezione | [rif] | | | 20.05.2014| Riduzione da 3-colorazione di mappe a SAT. Karp: riduzione da SAT a 3-SAT, e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.1-8.5, 8.8] | |
| | 23.05.2014| sospensione della didattica | elezioni | | | 23.05.2014| sospensione della didattica | elezioni | |
| | 23.05.2014| sospensione della didattica | elezioni | | | 23.05.2014| sospensione della didattica | elezioni | |
