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

 
===== Informazioni Generali =====

**Docenti:**  [[http://www.di.unipi.it/~pagli/|Linda Pagli]],[[http://pages.di.unipi.it/pibiri |Giulio Pibiri]]

**Impegno:** 9 CFU di cui 6 teoria/esercitazioni e 3 Laboratorio.

**Semestre:** primo.

**Ricevimento studenti:** dopo ogni lezione oppure su appuntamento.


===== AVVISO =====

** su [[http://mediateca.unipi.it]] sono a disposizione disposizione le video-lezioni dell'anno 2015/2016. Bisogna registrarsi con le credenziali di ateneo.**

===== NUOVO AVVISO =====
** RISULTATI APPELLO STRAORDINARIO DEL 31/10/2016, Corsi A e B ** 

{{:informatica:all-a:ris31-10-16.pdf|Risultati}} 

Visione scritti e orali su appuntamento.

===== NUOVO AVVISO =====
All'indirizzo http://dijkstra.di.unipi.it/#/lessons
i compiti degli appelli passati (a.a. 2015-16) sono adesso disponibili.
===== Anni accademici precedenti =====
   * [[http://didawiki.di.unipi.it/doku.php/informatica/all-a/start|A.A. 2015/2016]]
  
   
  
   
===== Orario Lezioni =====

^           Orario delle Lezioni           ^^^^
|Giovedì   | 14-18  |  N1   |
|Venerdì   | 14-18  |  M    | 
 


===== Obiettivi del Corso ===== 
Il corso è rivolto a studenti, che per motivi di vario tipo, non sono riusciti a superare il corso regolare di algoritmi e laboratorio il primo anno di studi. 
Il corso è costituito da brevi lezioni riassuntive sugli argomenti di base e da esercitazioni pratiche in cui si discuteranno e risolveranno problemi di vario tipo, definendo limiti inferiori, confrontando soluzioni diverse, analizzando correttezza e complessità.
Il corso ha una natura più pratica che teorica e verrà organizzato anche in funzione dei fruitori. Agli studenti che hanno intenzione di frequentarlo sarà richiesta un partecipazione attiva. 
Consiste di due gruppi di lezioni di due ore ciascuna il pomeriggio del giovedì dalle 14 alle 18 e del venerdì dalle 14 alle 18. Sono previsti vari compiti scritti. 

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 di questo corso coincide con quello di Algotimica e Laboratorio di 12 crediti.
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://didawiki.di.unipi.it/doku/doku.php/informatica/all-a/start|anno scorso]].



===== 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://dijkstra.di.unipi.it]]





===== 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 ^
| 22/09/2016 |introduzione al corso: problemi, algoritmi, limiti inferiore e superiore. Algoritmi facili e difficili|  |
| 22/09/2016 |Test scritto per stabilire la preparazione degli studenti| {{:informatica:alr:allrec.docx|}} |
| 23/09/2016 |Correzione degli esercizi del test|  |
| 23/09/2016 |Divide et Impera, MergeSort,Merge-SelectionSort, soluzione di equazioni di ricorrenza col metodo della sostituzione| [CLRS]: cap 2 |
| 29/09/2016 |Divide et Impera: esercizi, soluzione equazioni di ricorrenza con l'albero di ricorsione|[CLRS]:cap 2|
| 29/09/2016 | Word model e bit model, alberi di decisione per il problema dell'ordinamento| [CLRS]: cap 8.1 |
| 30/09/2016 | Ricerca Binaria. Partition e QuickSort. Analisi caso ottimo, caso pessimo. Randomized QuickSort| [CLRS]: cap 7, escluso 7.4.2 {{:informatica:all-b:quicksort.pdf|Numero di confronti di Randomized-Quicksort (Appunti del Prof. Luccio)}} |
| 30/09/2016 |Divide et Impera: esercizi, soluzione equazioni di ricorrenza con l'albero di ricorsione |  | 
| 06/10/2016 |Problema della Selezione. QuickSelect; Teorema dell'esperto per risolvere le ricorrenze  |[CLRS]:9.2,4.5] |
| 06/10/2016 |Applicazione del teorema dell'esperto. Esercizi di Divide et Impera | |
| 07/10/2016 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{:informatica:all-a:lezione1-1516.pdf|Lucidi}}.| |
| 07/10/2016 | **Laboratorio**:  Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{:informatica:all-a:lezione1-1516.pdf|Lucidi}}.| |
| 13/10/2016 |Heap come coda con priorità, operazioni di inserzione e estrazione del massimo. Implementazione con array e costruzione dell'Heap. HeapSort |[CLRS]:cap 6] |
| 13/10/2016 |Esercizi di simulazione, di dimostrazione di proprietà e di utilizzo della struttura Heap|
| 14/10/2016 | **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-1516.pdf|Lucidi}}|
| 14/10/2016 | **Laboratorio**: Esercizi. | |
| 20/10/2016 |Stabilità di un algoritmo di ordinamento. Sorting in tempo lineare: CountingSort e RadixSort|[CLRS]:cap 8.1, 8.2 e 8.3] |
| 20/10/2016 |Esercitazione scritta | {{:informatica:alr:es_ott2016.pdf|compito}},{{:informatica:alr:1.pdf|sol-es1}}, {{:informatica:alr:2-3.pdf|sol-es2-3}}, {{:informatica:alr:4.pdf|sol-es4}}|
| 21/10/2016 | **Laboratorio**: Array di stringhe; Selection, Insertion e Quick Sort su interi e stringhe; struct, typedef e qsort. | {{:informatica:alr:lezione4.pdf|Lucidi}} {{:informatica:alr:lezione5.pdf|Lucidi}} {{:informatica:alr:lezione6.pdf|Lucidi}} |
| 21/10/2016 | **Laboratorio**: Esercizi. |
| 27/10/2016 | 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. |
| 27/10/2016 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. Esercizi. |[CLRS] cap 11: 11.4. {{:informatica:all-b:hash.pdf|Dispense Prof. Luccio}}|
| 28/10/2016 | **Laboratorio**: Liste mono e bidirezionali. Alberi binari di ricerca. Esercizi. |{{:informatica:alr:lezione8-1415.pdf|Lucidi}} {{:informatica:alr:lezione9.pdf|Lucidi}}|
| 10/11/2016 |Alberi, alberi binari; trasformazione da albero a albero binario. Visite. Divide et impera su alberi. Calcolo di dimensione, altezza e profondità. Esercizi. |[CGGR] cap. 3.8. |
| 10/11/2016 |Alberi binari di ricerca, definizione e complessità delle operazioni di ricerca, inserzione e cancellazione, minimo e massimo, predecessore e successore, ordinamento. Minimo antenato comune.|[CLRS] cap 12.1, 12.2,12.3 |
| 11/11/2016 | **Laboratorio**: Tavole hash con liste concatenate. Esercizi. |{{:informatica:alr:lezione10-1415.pdf|Lucidi}}|
|17/11/2016 | Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni.).| [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}},  {{:informatica:all-b:figureAVL.pdf| rotazioni}}.|
| 17/11/2016 | Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione,  algoritmi ED e ALLINEA.| {{:informatica:all-b:ED.pdf|Edit Distance (dispense Prof. Luccio)}}. |
| 18/11/2016 | **Laboratorio**: Esercizi.|
| 24/11/2016 | Altri problemi di Programmazione Dinamica: Apparizioni approssimate e esercizi | {{:informatica:all-b:ED.pdf|Edit Distance (dispense Prof. Luccio)}}. |
| 24/11/2016 | Il problema dello Zaino, algortimi greedy, algoritmo esponenziale con GeneraBinarie, algortimo di programmazione dinamica. ||
| 25/11/2016 | **Laboratorio**: Esercizi.|
| 01/12/2016 | Grafi: Notazione, definizioni, memorizzazione. Visita BFS, Alberi BFS e cammini minimi. Visita DFS, foresta DFS e classificazione degli archi| [CLRS] cap 22.1, 22.2,22.3 |
| 01/12/2016 | Ordinamento topologico, Esercizi| [CLRS] cap 22.4 |
| 02/12/2016 | Esercizi riassuntivi sui grafi|  |