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


===== Anno accademico 2019/2020 =====

===== IMPORTANTE =====

A partire dal 9 marzo Le lezioni si svolgeranno telematicamente nelle ore previste dall'orario.

Per partecipare accedere all'URL:

**http://unipi.it/corsionline

**ed eseguire le istruzioni della guida per partecipare alle lezioni su Teams di Microsoft.

Il ricevimento studenti sarà fatto via mail, oppure via Skype su appuntamento.



===== Informazioni per le lezioni di laboratorio =====
 
Le lezioni di laboratorio si svolgeranno on line (streaming), a partire da martedì 10 marzo alle ore 11 sulla piattaforma Meet di Google. 

**Attenzione: le lezioni non saranno registrate. Seguitele rispettando gli orari del corso.**

Gli studenti del corso di laurea in Informatica sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo [[https://meet.google.com/dfz-nrtj-vex|link]]

Gli studenti del corso di laurea in Data Science sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo [[https://meet.google.com/fci-jqui-ixb|link]]


Gruppo Telegram con gli assistenti di laboratorio: [[https://t.me/joinchat/ASipw0Z4bi_AysizF4GFhQ|link]]


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

**Docenti Teoria/Esercitazioni:**  [[http://www.di.unipi.it/~pagli/|Linda Pagli]] e [[http://sbrinz.di.unipi.it/~peppe/|Giuseppe Prencipe]]  ([[informatica:all-a:start|corso A]])

**Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://hpc.isti.cnr.it/~nardini/|Franco Maria Nardini]], 
[[http://pages.di.unipi.it/rossano/|Rossano Venturini]] 

**Impegno:** 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. 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.

**Semestre:** secondo.

**Ricevimento studenti:** Pagli: su appuntamento, scrivere a linda.pagli@unipi.it

**Ricevimento studenti** Prencipe:  Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento)

**Ricevimento studenti** Bernasconi: Mercoledì, dalle 9 alle 11, sulla piattaforma 
[[https://meet.google.com/dfz-nrtj-vex|Meet di Google]]. Ricevo inoltre via Skype su appuntamento. Tramite mail avverrà lo scambio dei contatti skype e l'accordo sul giorno e sull'orario. 


**Registro delle lezioni:** si tratta del [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=3290010::::&ri=080240|registro ufficiale]] che riporta quanto indicato nel seguito.

===== Anni accademici precedenti =====
   * [[.all19:|A.A. 2018/2019]]
   * [[.all18:|A.A. 2017/2018]]
   * [[.all17:|A.A. 2016/2017]]
   * [[.all16:|A.A. 2015/2016]]
   * [[.all15:|A.A. 2014/2015]]
   * [[.all14:|A.A. 2013/2014]]
   * [[.all12:|A.A. 2012/2013]]

===== Gruppi Laboratorio =====

**NEWS**: Starting from Tuesday March 3rd, the Python Lab slot dedicated to Data Science Master Degree students is anticipated at 11:00-13:00 (still in class-room I). Therefore Data Science students should head to that time slot, while first year students are now allowed to attend the C Lab class at 14:00 even in classroom I.\\

^ Gruppo ^ Aula e orario ^ 
|A1    | Aula H, martedì 11:00 - 13:00|
|A2   | Aula M, martedì 11:00 - 13:00|
|A3 (Riservata a studenti della LM in Data Science - Dedicated to Data Science Master students)  | Aula I, martedì 11:00 - 13:00|
 
===== Orario Lezioni =====

^           Orario delle Lezioni           ^^^^
| Lunedì   | 11-13  | aula E | Teoria   |
| Martedì  | 11-13  | aule H-I-M | Laboratorio |
| Giovedì  | 16-18  | aula E | Teoria  |
| Venerdì  | 9-11  | aula E | 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=====
 
MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE

L'esame degli appelli estivi consistono in due prove obbligatorie:

    * Una **prova di Laboratorio** che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi. La prova avra’ luogo sulla consueta piattaforma d’esame accessibile via browser, e sara’ validata da un colloquio orale immediatamente successivo.  Tale prova è da intendersi come un __test di idoneità__.
    * Una **prova orale** sul programma del corso la cui valutazione finale è __in trentesimi__, atta a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" dello studente.
    * La prova orale puo' essere sostenuta solo dopo aver superato la prova di Laboratorio.  
    * Le prove possono essere sostenute in appelli diversi.  
    * Se la prova orale non viene superata, occorre ripetere soltanto quella.

Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria. **Attenzione**: la scadenza per iscriversi non sara’ molto a ridosso delle prove d’esame, controllate l'apposito portale.\\

DATA SCIENCE STUDENTS: PLEASE CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS

**Prossime date per la prova di Laboratorio:**

^ Data ^ Tipo Prova ^ Documenti ^ Aula Virtuale ^
| 26/5/2020 | 09:00 | Laboratorio |    |
| 16/6/2020 | 09:00 | Laboratorio |    |
| 07/07/2020 | 09:00 | Laboratorio |    |
| 01/09/2020 | 09:00 | Laboratorio |    |
| 11/01/2021 | 14:00 | Laboratorio |  [[https://meet.google.com/dfz-nrtj-vex | QUI ]]  |
| 01/02/2021 | 14:00 | Laboratorio |  [[https://meet.google.com/dfz-nrtj-vex  | QUI ]]  |
| 22/03/2021 | 14:30 | Laboratorio |  [[https://meet.google.com/dfz-nrtj-vex  | QUI ]]  |
| 8/06/2022 | 9:00 | Laboratorio |  [[https://meet.google.com/dfz-nrtj-vex  | QUI ]]  |

**Prossime date per la prova orale:**

Gli orali della I sessione autunnale si svolgeranno il 3 Settembre, a partire dalle ore 14:00: 

[[https://agende.unipi.it/ssc-vme-ekp]]


Per la discussione orale, si utilizza il canale Teams che è stato utilizzato per lo svolgimento delle lezioni.

**Prossime date per la prova di laboratorio linguaggio Python per studenti della LM in Data Science:**

^ Data ^ Ora ^ Tipo Prova ^ Avvisi ^ Aula Virtuale ^ Iscrizione ^  
| 26/5/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 24/05/2020 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 21/5 |
| 16/6/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 14/06/2020 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 11/6 |
| 7/7/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 5/7/2020 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 2/7/2020 |
| 1/9/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/8/2020 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 27/8/2020 |
| 27/10/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 25/10/2020 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 19/10/2020 |
| 11/01/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 09/01/2021 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] |  |
| 01/02/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/01/2021 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. |
| 23/03/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 21/03/2021 all'indirizzo email rossano.venturini@unipi.it.  |  [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. |
===== Registrazioni delle Lezioni =====
[[http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/AlgoLezioniVideo2020]]


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

  * **[CLRS]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduzione agli algoritmi e strutture dati//. McGraw-Hill, Terza edizione, 2010. 
  * **[DFI]** C. Demetrescu, I. Finocchi, G. Italiano. //Algoritmi e strutture dati//. McGraw-Hill, Seconda edizione, 2008. {{:informatica:all-a:parte_libro_dfi_.pdf|Solo pagine 161-165}}.
  * **[FL]** P. Ferragina, F. Luccio. //Il Pensiero Computazionale: dagli algoritmi al coding//. Il Mulino, 2017. Solo pagine 64-65, Capitolo 7 e Capitolo 10.

 
 

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.
  * [[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio]]  
  * [[https://github.com/jfet97/UniPiComputerScience| Altro materiale di supporto per il laboratorio preparato da uno studente]]
  * **__Sistema di Autovalutazione__**: [[http://algo1920.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 "dell'esperto".
  - 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 (Alberi 2-3), 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 ^ 
| 17/02/2020 | Questioni organizzative: pagina web, laboratori, ricevimento studenti e modalità di esame.\\ Introduzione al corso: nozione di algoritmo, problema, dimensione dell'input, limite inferiore/superiore alla complessità di un problema/algoritmo. Analisi di un problema semiserio: il problema delle 12 monete. | Capitolo 1 del CLRS, e [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] |
| 18/02/2020 | **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.pdf |Slide}} |
| 20/02/2020 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio: caso pessimo, caso ottimo e caso medio. Notazione asintotica: O-grande, Omega e Theta, o-piccolo e omega-piccolo.  | CLRS: Capitolo 3. |
| 21/02/2020 | InsertionSort: algoritmo, correttezza e complessita'. SelectionSort (correttezza e analisi sul libro di testo). Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo e minimo di un vettore.| |
| 24/02/2020 | MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. Consultare [FL]. |
| 25/02/2020 | **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-a:Lezione2.pdf |Slide}} |
| 27/02/2020 | Algoritmi polinomiali ed esponenziali: definizione, confronto e caso di PC k-volte più veloce, con considerazioni. Problema della Torre di Hanoi: definizione, risoluzione con algoritmo ricorsivo e valutazione della complessità con relazione di ricorrenza. | Consultare [FL]. |
| 28/02/2020 | Teorema dell'esperto, esempi, e sua dimostrazione per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte)    |
| 02/03/2020 | Esercitazione: Ordini di grandezza, Ricerca sequenziale e varie versioni ricerca binaria. Analisi complessità|{{ :informatica:all-a:esercitazione_1.pdf |Es 1}} |
| 03/03/2020 | **Laboratorio**:  Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} |
| 09/03/2020 | Esercitazione: Ricerca Binaria Sinistra, limiti inferiori al problema della ricerca,  problema 2.1 pag. 37 del Cormen: MergeInsertionSort|{{ :informatica:all-a:esercitazione_2.pdf |Es 2}} |
| 10/03/2020 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} |
|12/03/2020 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmi per determinare il primo e secondo, algoritmo del doppio torneo.| [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori. [CLRS] cap 8: 8.1. {{ :informatica:all-a:lez12marzo.pdf |lavagna}} |
| 13/03/2020 | Quicksort: descrizione intuitiva, pseudo-codice, versione randomizzata, analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Studiare anche Partizione di Hoare (Problema [CLRS] 7.1) e Partizione con elementi uguali (Problema [CLRS] 7.2). Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare.  | [CLRS] cap 7 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}). \\ cap 9: 9.1, 9.2 |
| 16/03/2020 | Limiti inferiori con la tecnica dell'avversario: problema del primo e secondo. Partizione con elementi uguali (Problema [CLRS] 7.2). Moltiplicazione nel bit model |{{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} Note di F. Luccio su {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}} {{ :informatica:all-a:lez16marzo.pdf |lavagna
}}|
| 17/03/2020| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}|
| 19/03/2020 | Moltiplicazione Egizia e Moltiplicazione Rapida, Moltiplicazione di matrici: Algoritmo di Strassen. Introduzione alle cose con priorità |{{ :informatica:all-a:lez19m.pdf |lavagna}} |
| 20/03/2020 | La struttura dati Heap: proprietà, esempi, Max-Heapify con analisi della complessità e correttezza. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. Heapsort. | [CLRS] cap 6: 6.1 - 6.5.  |
| 23/03/2020 | Code di priorità: definizione, operazioni, realizzazione mediante heap. 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). Funzioni hash: metodo della divisione. | [CLRS] cap 6: 6.1 - 6.5. cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2.|
| 24/03/2020 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} |
| 26/03/2020 | Funzioni hash: metodo della moltiplicazione. Dizionari: realizzazione con tabelle a indirizzamento aperto e analisi di ricerca senza successo e inserimento. Probing lineare, quadratico, e con double hashing. Tabelle hash con stringhe come chiavi. | [CLRS] cap 11: 11.3.2, 11.4. |
|  | Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari. |  |
| 27/03/2020 |Esercitazione. Dimostrazioni per induzione su alberi binari. Simulazione di HeapSort. Equazioni di ricorrenza| {{ :informatica:all-a:ese3.pdf |lavagna}} |
| 30/03/2020 | Esercitazione scritta | |
| 31/03/2020 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} |
| 02/04/2020 | Esercitazione. Esercizi vari su Heap e HeapSort.| {{ :informatica:all-a:eser4.pdf |lavagna}} |
| 03/04/2020 | Esercitazione. Esercizi di simulazione di tabelle hash con diversi metodi gestione delle collisioni. Il problema della cancellazione nell'open hash, uso della marcatura. | {{ :informatica:all-a:e5.pdf |lavagna}} |
| 06/04/2020 | Definizione di albero, con radice, ordinato k-ario. Algoritmi ricorsivi su alberi binari, dimensione, altezza. Visite, Paradigma generale tipo Divide et Impera, con equazioni di ricorrenza  | [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{ :informatica:all-a:lez6.pdf | lavagna}}  | 
| 07/04/2020 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}}|.
| 09/04/2020 | Trasformazione da albero  ordinato ad albero binario. Alberi binari di ricerca. Operzioni di ricerca, inserzione, cancellazione, ordinamento, minimo, massimo, predecessore e successore. | [CLRS] cap 12: 12.1, 12.2, 12.3 (senza alg TRASPLANT).  {{ :informatica:all-a:leza9aprile.pdf |lavagna}}| 
| 16/04/2020 | Alberi bilanciati in altezza: alberi AVL. Studio del caso pessimo: Alberi di Fibonacci. Rotazioni dopo inserzione e cancellazione, esempi. | [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}},  {{:informatica:all-b:rotazioniavl.pdf| rotazioni}}  {{ :informatica:all-a:lez16aprilr.pdf |lavagna}}|
| 17/04/2020 | Esercitazione. alberi binari, alberi binarizzati, inserzioni in albero AVL.  |{{ :informatica:all-a:lez17aprile.pdf |lavagna}} |
| 20/04/2020 | Array di dimensione variabile. Sorting in tempo lineare: Counting Sort e Radix Sort.  |[CGGR] par 1.1.3, [CLRS] cap 8: 8.2, 8.3 {{ :informatica:all-a:arrayvariabili.pdf |array variabili}}{{ :informatica:all-a:lez20aprile.pdf |lavagna}}|
| 21/04/2020 | **Laboratorio**: Tabelle Hash. | {{ :informatica:all-b:lezionehash.pdf |Slide}} \\ {{:informatica:all-a:Esercizio1.pdf |Esercizio 1}} {{:informatica:all-a:Esercizio2.pdf |Esercizio 2}} |
| 23/04/2020 |Esercitazione. Radix Sort, esempi e confronti. Esercizi su alberi binari di ricerca. |  {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}}{{ :informatica:all-a:lez23aprile.pdf |lavagna}} | 
| 24/04/2020 |Introduzione alla Programmazione Dinamica. Generazione dei numeri di Fibonacci. Il problema della Longest Common Subsequence. |[CLRS] cap 15: 15.4.{{ :informatica:all-a:lez24aprilr.pdf |lavagna}} |
| 27/04/2020 |Programmazione Dinamica. Il problema della Edit Distance |[[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note del Prof.
 Luccio]].{{ :informatica:all-a:lez27aprile.pdf |lavagna}}  |
| 28/04/2020 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}} \\ {{:informatica:all-a:Esercizio1AB.pdf |Esercizio 1}} {{:informatica:all-a:Esercizio2AB.pdf |Esercizio AVL}}|
| 30/04/2020 |Esercitazione. Esercizi di Programmazione Dinamica. |{{ :informatica:all-a:algo1_090614.pdf | esercizio 3}} {{ :informatica:all-a:esercizipd.pdf | scacchiere}}  |
| 04/05/2020 |Il problema dello Zaino e dello Zaino frazionato. Algoritmo greedy per lo Zaino frazionato.  Programmazione Dinamica per lo Zaino. Pseudopolinomialità. Algoritmo brute force per lo Zaino.  |[CGGR] par 6.5{{ :informatica:all-a:lez4maggio.pdf | lavagna }}|
| 05/05/2020 | **Laboratorio**: simulazione prova d'esame.|{{ :informatica:all-a:SolAlberi.pdf |Slide}} |
| 07/05/2020 |Introduzione ai grafi. Definizioni. Rappresentazione con Matrice e liste di adiacenza. Visita BFS. |[CLRS] cap.22, 22.1 e 22.2 fino a analisi e appendice B4, {{ :informatica:all-a:all7maggio.pdf |lavagna}}|
|11/05/2020 |Grafi: albero BFS, Vista DFS, foresta DFS. Etichettamento degli archi. Esempi |[CLRS] cap.22, 22.2 {{ :informatica:all-a:lez11maggio.pdf |lavagna}}|
|12/05/2020 | **Laboratorio**: grafi. |{{ :informatica:all-a:lezionegrafi20.pdf |Slide}} {{:informatica:all-a:grafobipartito.pdf |Esercizio 1 (Grafo Bipartito)}} {{ :informatica:all-b:ese2_grafi.pdf| Esercizio 2 (grafo connesso)}}|
|14/05/2020 |Grafi: DAG e Ordinamento Topologico. BFS per grafi dinamici. Esempi |[CLRS] cap.22, 22.3 e 22.4, [CGGR] pag.225|
|15/05/2020 |Esercitazione: esercizi sui grafi| {{ :informatica:all-b:esercizigrafi2017.pdf | Esercizi}} {{ :informatica:all-a:lez15maggio.pdf |lavagna}}|
|18/05/2020 |Il problema P e NP. Introduzione all'NP-Completezza|{{ :informatica:all-a:pvsnp.pdf |PvsNP}} |
|19/05/2020 | **Laboratorio**: esercitazione finale | {{ :informatica:all-b:solgrafi.pdf |Slide}}|
|21/05/2020 | Verifica polinomiale. NP-Completezza, Definizioni. Riducibilità polinomiale. Teorema di Cook-Levin (senza dimostrazione), esempi di riduzioni. |Su P vs NP si consultino: {{ :informatica:all-a:p-np.pdf |nota 1}} e {{ :informatica:all-a:altre_note.pdf |nota 2}}, quest'ultima nelle pagine 4-6. {{ :informatica:all-a:all21maggio.pdf |lavagna}} |
|22/05/2020 | Esercitazione: esercizi su grafi, programmazione dinamica, algoritmi enumerativi e verifica polinomiale.| {{ :informatica:all-a:pagli_20190529_173206.pdf|GeneraBinarie e GeneraPermutazioni}} {{ :informatica:all-a:ese22maggio.pdf |lavagna}} |