DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Algoritmica e Laboratorio - Corso A ======

===== 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]]



(**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.

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 =====

**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 |
 


===== Obiettivi del Corso ===== 
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. 

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'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'[[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 =====

** Il secondo compitino è riservato solo agli studenti che hanno preso un voto ≥ 18 al primo compitino **



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  | |



===== Libri di testo =====

  * **[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]].
 

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 [[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]]





===== 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.


|===== Registro delle Lezioni =====

^ 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.}} |
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
