informatica:all-a:all12:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
informatica:all-a:all12:start [07/02/2013 alle 20:52 (12 anni fa)] – versione precedente ripristinata anna bernasconi | informatica:all-a:all12:start [13/02/2014 alle 11:16 (11 anni fa)] (versione attuale) – [Anni accademici precedenti] Linda Pagli | ||
---|---|---|---|
Linea 1: | Linea 1: | ||
+ | |||
+ | ====== Algoritmica e Laboratorio - Corso A ====== | ||
+ | |||
===== Informazioni Generali ===== | ===== Informazioni Generali ===== | ||
- | **Docente**: Linda Pagli | + | **Docenti:** |
+ | |||
+ | |||
+ | (**Docenti corso B:** [[http:// | ||
+ | |||
+ | **Assistente: | ||
**Impegno: | **Impegno: | ||
Linea 11: | Linea 19: | ||
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. | ||
+ | |||
+ | ===== Anni accademici precedenti ===== | ||
+ | * [[informatica: | ||
+ | * [[informatica: | ||
+ | * [[informatica: | ||
+ | |||
+ | ===== Orario Lezioni ===== | ||
+ | |||
+ | ^ | ||
+ | |Martedì | ||
+ | |Mercoledì | 11-13 | | ||
+ | |Giovedì | ||
+ | |Venerdì | ||
+ | |||
+ | |||
+ | Si pregano gli studenti che dispongono di un portatile di portarlo **in Laboratorio**. | ||
+ | |||
+ | ===== Obiettivi del Corso ===== | ||
+ | L' | ||
+ | |||
+ | 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. | ||
+ | ===== Modalità e Appelli di Esame===== | ||
+ | |||
+ | L' | ||
+ | |||
+ | * Una prova scritta con esercizi atti a valutare l' | ||
+ | * 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' | ||
+ | |||
+ | |||
+ | ^ Data ^ Tipo Prova ^ Documento ^ Note ^ | ||
+ | | 03/04/2013, ore 11.00 | Scritto (primo compitino)|{{: | ||
+ | | 30/05/2013, ore 9.00 | Scritto (secondo compitino)|{{: | ||
+ | | 12/06/2013, ore 9.00 | Scritto (primo appello)|{{: | ||
+ | | 12/07/2013, ore 9.00 | Scritto (secondo appello)|{{: | ||
+ | | 9/09/2013, ore 15.00 | Scritto | {{: | ||
+ | | 4/11/2013, ore 14.00 | Scritto | {{: | ||
+ | | 21/01/2014, ore 9.30 | Scritto | {{: | ||
+ | | 7/02/2014, ore 9.30 |Scritto ||{{: | ||
+ | Prossime date per le prove di laboratorio: | ||
+ | ^ Data ^ Ora ^ Aule ^ | ||
+ | | 11/06/2013 | 9:30 |H e M | | ||
+ | | 14/06/2013 | 9:30 |H e M | | ||
+ | | 16/07/2013 | 9:30 |H e M | | ||
+ | | 12/09/2013 | 9:30 |H e M | | ||
+ | | 24/01/2014 | 9:30 |H e M | | ||
+ | |||
+ | Prossime date per le prove orali: | ||
+ | ^ Data ^ Ora ^ Aule ^ | ||
+ | | 11/06/2013 | dopo il laboratoio |ufficio Pagli | | ||
+ | | 14/06/2013 | 9-13 |aula L | | ||
+ | | 24/06/2013 | 9:30 |ufficio Pagli| | ||
+ | | 16/07/2013 | 11:00 |ufficio Pagli| | ||
+ | | 17/07/2013 | 9.00 |ufficio Pagli| | ||
+ | | 24/01/2014 | 11:00 |ufficio Pagli| | ||
+ | | 11/02/2014 | 15:30 |ufficio Pagli| | ||
+ | |||
+ | |||
+ | ===== Libri di testo ===== | ||
+ | |||
+ | * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, | ||
+ | | ||
+ | * **[CGG]** P. Crescenzi, G. Gambosi, R. Grossi. //Strutture di dati e algoritmi: progettazione, | ||
+ | |||
+ | |||
+ | * **[CLRS]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. // | ||
+ | |||
+ | Per il laboratorio, | ||
+ | * **[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//, | ||
+ | |||
+ | ===== Materiale per il Laboratorio ===== | ||
+ | |||
+ | * **__Prerequisito__**: | ||
+ | * **__Strumenti per la programmazione__**: | ||
+ | ===== Programma del corso ===== | ||
+ | |||
+ | |||
+ | - Breve introduzione a problemi computazionali, | ||
+ | - Complessità computazionale: | ||
+ | - Limiti del calcolo: albero di decisione, limiti superiori e inferiori. | ||
+ | - Divide-et-impera, | ||
+ | - 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: '' | ||
+ | - Sottosequenza di somma massima. | ||
+ | - Programmazione dinamica: LCS, Partizione e Zaino | ||
+ | - Algoritmi randomizzati: | ||
+ | - Generazione di combinazioni e permutazioni | ||
+ | - Analisi ammortizzata: | ||
+ | - 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/ | ||
+ | - Grafi III: Minimum Spanning Tree e Shortest Path. | ||
+ | |||
+ | ===== Lavagna ===== | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | ===== Registro delle Lezioni ===== | ||
+ | ^ Data ^ Argomento ^ Rif. Biblio ^ | ||
+ | | 19/02/2013 | Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio | {{: | ||
+ | | 20/02/2012 | **Laboratorio**: | ||
+ | | 21/02/2012 | **Laboratorio**: | ||
+ | | 22/02/2013 | Problemi intrattabili: | ||
+ | | 27/02/2012 | **Laboratorio**: | ||
+ | | 28/02/2012 | **Laboratorio**: | ||
+ | | 01/03/2013 | Teoria della calcolabilità. Insiemi numerabili.Esistenza di problemi non decidibili. Il problema dell' | ||
+ | | 05/03/2013 | Rappresentazione degli elementi di un insieme con vettore di appartenenza. Generazione di tutte le stringhe binarie, applicazione a PARTITION. Generazione di tutte le permutazioni, | ||
+ | | 06/03/2013 | Il certificato polinomiale. Nozione di Riduzione Polinomiale. Problemi NP-completi. Il Problema SAT. | [CGGR]: {{: | ||
+ | | 07/03/2013 | **Laboratorio**: | ||
+ | | 08/03/2013 | Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano, | ||
+ | | 12/03/2013 | Notazione asintotica: Theta, O-grande, Omega-grande, | ||
+ | | 13/03/2013 | Insertion Sort, analisi. Limiti inferiori: tecnica della dimensione dell' | ||
+ | | 14/03/2013 | **Laboratorio**: | ||
+ | |15/03/2013 |Esercitazione: | ||
+ | | 19/03/2013 | Il problema della ricerca: ricerca binaria ricorsiva; Analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort.| [CGGR]: cap 3; [CGG]: cap. 2; | | ||
+ | | 20/03/2013 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Equazioni di ricorrenza: | ||
+ | | 21/03/2012 | **Laboratorio**: | ||
+ | | 22/03/2013 | Randomized-Quicksort: | ||
+ | | 26/03/2013 | Moltiplicazione veloce di interi e matrici. Esercitazione: | ||
+ | | 27/03/2013 | Selezione dell' | ||
+ | | 3/04/2013 | {{: | ||
+ | | 9/04/2013 | Correzione della prima prova di verifica intermedia. | ||
+ | |10/04/2013 | Operazioni Enqueue, First, Dequeue per un Heap di massimo. Complessità. Allocazione implicita in array. HeapSort. |[CGGR]: cap 2 ; [CGG]: cap. 8; | | ||
+ | | 11/04/2012 | **Laboratorio**: | ||
+ | | 12/04/2012 | Ordinamento di interi: Counting sort e Radix Sort. Introduzione alla Programmazione Dinamica.|{{: | ||
+ | | 16/04/2013 | Programmazione Dinamica: Edit Distance, Longest Common Subsequence (introduzione al problema).|{{: | ||
+ | | 17/04/2013 | Programmazione Dinamica: Longest Common Subsequence, | ||
+ | | 18/04/2013 | **Laboratorio**: | ||
+ | | 19/04/2013 | Programmazione Dinamica: Il problema dello Zaino. Pseudopolinomialità. Esercizi sulla programmazione dinamica. |[CGGR]: cap 6; [CGG]: cap 2; {{: | ||
+ | | 23/04/2013 | Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi con un numero qualsiasi di figli: memorizzazione binarizzata. Dizionari. |[CGGR]: cap 1, cap 3, cap 4; [CGG]: cap 4, cap 5; | | ||
+ | | 24/04/2013 | Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione. |[CGGR]: cap 4; [CGG]: cap 5; | | ||
+ | | 26/04/2013 | Esercitazione: | ||
+ | | 30/04/2013 | Alberi binari 1-bilanciati: | ||
+ | | 3/05/2013 | Esercitazione: | ||
+ | | 07/05/2013 | Dizionari: funzioni hash, realizzazione del dizionario con tabelle hash con liste di trabocco e a indirizzamento aperto. Il problema della cancellazione. |[CGGR]: cap 4; [CGG]: cap 5; | | ||
+ | | 08/05/2013 | Dizionari: tabelle hash a indirizzamento aperto: analisi al caso medio; scansione lineare, quadratica, doppio hash. |[CGGR]: cap 4; [CGG]: cap 5; {{: | ||
+ | | 09/05/2013 | **Laboratorio**: | ||
+ | | 10/05/2013 | Grafi: definizioni, | ||
+ | | 14/05/2013 | Visita in ampiezza di un grafo: analisi e proprietà. Visita in profondità. Ordinamento topologico di un grafo diretto aciclico. | ||
+ | | 15/05/2013 | Ordinamento topologico di un DAG: algoritmo e analisi. Ricerca di cammini minimi su grafi pesati: algoritmo di Dijkstra. | ||
+ | | 16/05/2013 | **Laboratorio**: | ||
+ | | 17/05/2013 | Algoritmo di Dijkstra: simulazione, |
informatica/all-a/all12/start.1360270334.txt.gz · Ultima modifica: 07/02/2013 alle 20:52 (12 anni fa) da anna bernasconi