Strumenti Utente

Strumenti Sito


informatica:all-b:algob_14:start

Differenze

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

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione
Revisione precedente
informatica:all-b:algob_14:start [05/02/2015 alle 13:59 (7 anni fa)]
anna bernasconi
informatica:all-b:algob_14:start [08/05/2015 alle 13:32 (7 anni fa)] (versione attuale)
anna bernasconi [Modalità e Appelli di Esame]
Linea 3: Linea 3:
  
  
-===== Anno accademico 2014/2015 =====+===== Anno accademico 2013/2014 =====
  
  
Linea 20: Linea 20:
 ===== 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. 
Linea 38: Linea 38:
 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  |        | Teoria +|Martedì    |  11-13  |        | Teoria 
-|Mercoledì  |  11-13  |        | Teoria  |+|Mercoledì  |  11-13  |        | Teoria  |
 |Giovedì    |  14-16  |  H,M     | Laboratorio  | |Giovedì    |  14-16  |  H,M     | Laboratorio  |
-|Venerdì    |  11-13  |        | Teoria |+|Venerdì    |  11-13  |        | Teoria |
    
  
Linea 68: Linea 67:
 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|}} | | 
 +| 28/05/2014, ore 11.00 | Scritto (secondo compitino)|{{:informatica:all-b:algo1_28052014.pdf|}} | | 
 +| 09/06/2014, ore 11.00 | Scritto |{{:informatica:all-b:algo1_090614.pdf|}} | | 
 +| 08/07/2014, ore 9:30 | Scritto |{{:informatica:all-a:algo1_08072014.pdf|}},  {{:informatica:all-b:algo1_08072014sol.pdfSoluzioni}} | | 
 +| 08/09/2014, ore 9.30 | Scritto |{{:informatica:all-a:algo1_08092014.pdf|}},  {{:informatica:all-b:algo1_08092014sol.pdfSoluzioni}}| |   
 +| 04/11/2014, ore 9.00 | Scritto |{{:informatica:all-b:algo1_04112014.pdf|}}| | 
 +| 14/01/2015, ore 9.00 | Scritto |{{:informatica:all-a:algo1_14012015.pdf|}},{{:informatica:all-a:algo140115sol.pdf|}} | |  
 +| 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
  
  
Linea 90: Linea 112:
  
      
- 
-  * **[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: 
Linea 127: Linea 146:
 ===== 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.}}| | 
 + 
 + 
 + 
 + 
informatica/all-b/algob_14/start.1423144774.txt.gz · Ultima modifica: 05/02/2015 alle 13:59 (7 anni fa) da anna bernasconi