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





===== Anno accademico 2017/2018 =====














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





**Docenti Teoria/Esercitazioni:**  [[http://www.di.unipi.it/~pagli/|Linda Pagli]] ([[informatica:all-b:start|corso B]]) e  [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]] ([[informatica:all-a:start|corso A]]) 

**Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://pages.di.unipi.it/sirbu/|Alina Sirbu]], [[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 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.

**Semestre:** secondo.

**Ricevimento studenti:**  su appuntamento inviarndo e-mail a linda.pagli@unipi.it).

===== Anni accademici precedenti =====
  * [[informatica/all-b/algoB_17/start|A.A. 2016/2017]]
  * [[informatica/all-b/algoB_16/start|A.A. 2015/2016]]
  * [[informatica/all-b/algoB_15/start|A.A. 2014/2015]]
===== Orario Lezioni =====


^           Orario delle Lezioni           ^^^^
|Martedì    |  9-11  |   E     | Teoria  |
|Martedì   |  14-16  |  H, I, M   | Laboratorio  |
|Mercoledì  |  14-16  |   E      | Teoria  |
|Giovedì    |  9-11  |    E    | Teoria  | 



Si pregano gli studenti che dispongono di un portatile di portarlo **in Laboratorio**.

===== 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.
   * 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à__. 
   * 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. 
   * **LA PROVA ORALE E QUELLA DI LABORATORIO POSSONO ESSERE SOSTENUTE IN QUALUNQUE ORDINE E SOLO DOPO AVER SUPERATO LA PROVA SCRITTA.**
   * Se la prova orale non viene superata, occorre ripetere soltanto quella.
   * **SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE TUTTE LE PROVE GIA' SOSTENUTE. **
   * Chiaramente la registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo.




Per avere una idea della tipologia delle prove, si consultino i testi dell'[[.algoB_16:|anno scorso]].

**Prossime date per la prova scritta:**

^ Data ^ Tipo Prova ^ Documento ^ Note ^
| 4/4/2018| primo compitino| {{ :informatica:all-b:ris-17-18_1.pdf |risultati primo compitino}}|Sono ammessi al secondo compitino gli studenti con voto ≥ 17. Gli insufficienti non sono riportati. Correzione e visione dei compiti 11/04/2018 dalle 14 aula E|
| 30/05/18 \\ ore 9-11 | Secondo Compitino | {{ :informatica:all-a:algo_300518_versione_1.1_.pdf |testo}}, {{ :informatica:all-a:sol_compitino_2.pdf |soluzione}}, {{:informatica:all-b:risultati_risultati.csv.pdf |lista dei risultati}} .| Per la correzione e visione del compito: Aula A1, martedì 5 giugno, ore 10:00.\\ La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto di media (valido solo per i compitini) viene perso se si decide di sostenere la prova orale, la quale è quindi **facoltativa** per chi ha passato i compitini, ma può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in **qualunque appello**.  |
| 22/06/18 | Primo Appello | {{ :informatica:all-a:algo_220618.pdf |testo}}, {{ :informatica:all-a:soluzione_algo_220618.pdf |soluzione}}, {{ :informatica:all-b:ris2206202matricole.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18).| Per la correzione e visione del compito: Aula C, lunedì 25 giugno, ore 16:00.\\ La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi **facoltativa** e può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in **qualunque appello** o **ricevimento** del docente. |  
| 13/07/18 \\ ore 9-11 | Secondo appello |{{:informatica:all-b:algo_130718.pdf |testo}}{{ :informatica:all-b:soluzione_del_13-7-2018.pdf | soluzione}} {{ :informatica:all-b:ris1372018.pdf |lista dei risultati}}| Insufficienti e annullati non compaiono nella lista. Per la correzione e visione del compito: Aula C1, lunedì 16 luglio, ore 11:00 e lunedì 23 luglio ore 11.30 ufficio Pagli. Per registrazione 23/7/2018 ore 16.00 ufficio Pagli.|
| 04/09/18 \\ ore 9-11 | Terzo appello |{{ :informatica:all-a:algo_040918.pdf |testo}} {{ :informatica:all-b:rism040918.pdf|lista dei risultati}} | Gli studenti interessati a sostenere la prova orale (opzionale) devono inviare un'email alla docente.\\ La registrazione del voto (avendo superato anche il laboratorio) e l'orale (opzionale) possono avvenire in qualunque appello. La prossima data utile per la registrazione e la visione del compito è venerdì 7 settembre, dalle 15.00, studio Pagli.  |  |
| 21/01/19 \\ ore 9-11 | Quarto appello |{{:informatica:all-b:algo210119-5.pdf|testo}} {{ :informatica:all-b:pagli_20190121_132806.pdf | soluzione}} {{ :informatica:all-b:rismat21_1_19_.pdf |risultati}}| Sono ammessi all'esame di laboratorio gli studenti che hanno riportato un voto >= 17. Per la visone del compito e la registrazione giovedì 24 dalle 11.30, studio Pagli.|
| 12/02/19 \\ ore 14-16 | Quinto appello|{{:informatica:all-b:algob_18:algo120219.pdf|testo}}{{:informatica:all-b:algob_18:sol120219.pdf| soluzione}} {{:informatica:all-b:algob_18:ris120219.pdf|risultati corsi A e B}}| Sono ammessi all'esame di laboratorio gli studenti che hanno riportato un voto >= 16. Per la visione del compito presentarsi il 13 febbraio alle 9, nello studio del prof. Ferragina. Per la registrazione dopo il laboratorio: ufficio Pagli il 21/2/2019 alle 10.|

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

^ Data ^ Ora ^ Aule ^  
|29/06/2018| 9.30|
|07/09/2018| 14.00| 


**Prossime date per le prove orali:**
^ Data ^ Ora ^ Aula ^ Note ^
|29/06/2018|re 11.30 | ufficio pagli|
|16/07/2018| ore 11 | Aula C1 |
===== 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-b:alberi2-3.pdf|Solo pagine 161-166}}.
  * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione)//. Pearson, 2012. {{:informatica:all-b:alberibinari.pdf|Solo pagine 87-96}}.
  * **[BFL]** A. Bernasconi, P. Ferragina, F. Luccio. //Elementi di Crittografia //. Pisa University Press, 2015. Solo il capitolo 3.
 

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://algo1718.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 (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 ^  
| 20/02/2018 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.|{{:informatica:all-b:12monete.pdf|12 monete}} |
| 20/02/2018 | **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}} |
| 21/02/2018 | 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 e pessimo. Selection sort: analisi di complessità.| [CLRS] cap 1, cap 2: 2.1, 2.2.|
| 22/02/2018 | Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. |[CLRS] cap 3. {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}}  {{:informatica:all-b:esercizi0-2017.pdf|Esercizi}} {{ :informatica:all-b:notazioniasintotiche.pdf|Notazioni O,Omega e Teta}}|
| 27/02/2018 | Paradigma del Divide et Impera.  MergeSort: algoritmo, correttezza e analisi di complessità (metodo iterativo e albero di ricorsione). | [CLRS] cap 2: 2.3, cap 4: introduzione, 4.4.| 
|27/02/2018 |**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}}|
|28/02/2018 | MergeSort: complessità con albero di ricorsione. **Esercitazione**: Ricerca sequenziale analisi del caso medio, soluzione esercizi proposti nella lezione del 22/2.|[CLRS] cap 1: 1.2 | 
|29/02/2018 |**Lezione non tenuta per emergenza neve** |  |
| 06/03/2018 | Ricerca binaria. Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmo del torneo. | [CLRS] cap 8: 8.1. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori.  |
| 06/03/2018 | **Laboratorio**:  Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} |
| 07/03/2018 | Limite inferiore alla complessità del Sorting. **Esercitazione**: MergeInsertionSort.   | [CLRS]   cap 8: 8.1, problema 2.1 pag.34 |
| 08/03/2017| Relazioni di ricorrenza: Teorema dell'esperto (Master Theorem) con esempi di applicazione. | cap 4: 4.5, 4.6.1.|
| 13/03/2018 | Moltiplicazione veloce di interi di //n// cifre. Moltiplicazione veloce di matrici. Algoritmo di Strassen.|{{ :informatica:all-a:prodotto_interi_e_matrici.pdf |Note di F. Luccio}} e di {{ :informatica:all-b:moltveloce.pdf|R. Grossi}} sulla moltiplicazione veloce di interi e matrici. | 
| 13/03/2018 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione4-1415.pdf|Slide}} |
| 14/03/2018| **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:Esercizi1-2017.pdf|Esercizi (ricorrenze, ricerca, ordinamento, divide et impera)}} |
| 15/03/2018 | Quicksort: proprietà, pseudocodice e analisi della complessità nel caso ottimo e pessimo. Discussione sul costo nel caso medio: analisi delle prestazioni per ripartizioni di proporzionalità costante. Quicksort randomizzato: discussione e pseudocodice. | [CLRS] cap 7: 7.1, 7.2, 7.3|
| 20/03/2018 | 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 (Note di F.Luccio)}}|
| 20/03/2018 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5-1617.pdf |Slide}}|
| 21/03/2018 | **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:Esercizi2-2015.pdf|Esercizi (divide et impera, ricorrenze, ordinamento)}}|
| 22/03/2018 | Heap: definizione, realizzazione implicita come array. Code di priorità, operazioni, definizione e realizzazione mediante heap.|[CLRS] cap 6: 6.1, 6.5.|
| 27/03/2018 | La struttura dati Heap: costruzione con Max-Heapify con analisi della complessità e correttezza.  L'algoritmo Heapsort. Esercizi sull'Heap | [CLRS] cap 6: 6.2, 6.3, 6.4. |  
| 27/03/2018 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-b:lezione6-1415.pdf|Slide}} |
| 28/03/2018 | **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:esercizi3-2015.pdf|Esercizi (heap)}}|
| 04/04/2018 | prima verifica scritta| {{ :informatica:all-b:algo_040418_versione_2_.pdf|compito1}} e {{ :informatica:all-b:algo_040418.pdf |compito2}} |
| 11/04/2018 | **Esercitazione**: correzione e discussione sugli esercizi del compitino. | |
| 12/04/2018 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3.  |
| | 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. | |
| 17/04/2017 | 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.|[CLRS] cap 11: 11.1, 11.2, 11.3, 11.3.1.|
| 17/04/2018 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} |
| 18/04/2018 | Tabelle hash a indirizzamento aperto: inserimento, ricerca, cancellazione; scansione lineare, scansione quadratica, doppio hashing; analisi al caso pessimo e medio (ricerca senza successo). Analisi del caso medio della ricerca |[CLRS] cap 11: 11.2, 11.4.  {{:informatica:all-b:hash.pdf|Tabelle hash (Note di F.Luccio)}}|
|24/04/2018 | Algoritmi ricorsivi su alberi binari. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore, predecessore).| [CLRS] cap 12: 12.1, 12.2. [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{:informatica:all-b:esercizialberi2016.pdf|Esercizi (alberi e alberi binari)}}|
| 24/04/2018 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}} {{ :informatica:all-a:e1.pdf |Esercizio 1 in aula.}}|
|26/04/2018 | Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). **Esercitazione**: progettazione di algoritmi efficienti su alberi. | [CLRS]  cap 12: 12.3.  {{:informatica:all-b:alberihash2017.pdf|Esercizi (dizionari, alberi binari, alberi binari di ricerca)}}|
|02/05/2018| 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:rotazioniavl-2016.pdf| rotazioni}}  | 
| 03/05/2018 | Generazione delle sequenze binarie. Generazione delle permutazioni. Esempi. | [CGGR]: {{:informatica:all-b:generaBinPerm.pdf | alcune note su generazione binarie e permutazioni}} |
| 08/05/2018 | Grafi: definizioni e allocazione in memoria. Il problema del ciclo euleriano e il problema del ciclo hamiltoniano: definizioni, e considerazioni computazionali. Enunciato del Teorema di Eulero. | Alcune {{ :informatica:all-a:eulero_vs_hamiltoniano.pdf |note}} su ciclo euleriano e hamiltoniano. [CLRS]: appendice B.4, cap 22: 22.1. |
| 08/05/2018 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezione9.pdf |Slide}}|
| 09/05/2018 | Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza, albero di visita in ampiezza e algoritmo PRINT-PATH.| [CLRS] cap 22: 22.2 |
| 10/05/2017 | Grafi: visita in profondità (DFS), analisi di complessità e correttezza, classificazione degli archi; ordinamento topologico di grafi diretti aciclici.| [CLRS] cap 22: 22.3, 22.4 con teo 22.12, {{ :informatica:all-b:esercizigrafi2017.pdf | Esercizi}} |
|  | Esercizi da svolgere/svolti su alberi e tabelle hash.| {{ :informatica:all-a:esercizi_alberi_e_tabelle_hash.pdf |Testo 1}} e {{ :informatica:all-a:esercizi_hash.pdf |testo 2}} |
| 15/05/2017 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci e del binomiale). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva, algoritmi LCS e PRINT-LCS.. |{{:informatica:all-b:PD.pdf|Programmazione Dinamica (note di F. Luccio)}} \\ [CLRS] cap 15: 15.4.| 
| 15/05/2018 | **Laboratorio**: Tabelle hash. | {{ :informatica:all-a:lezione10.pdf |Slide}} {{ :informatica:all-b:ht.pdf |Esercizio 1 in aula}}|
| 16/05/2018 | LCS: Sottostruttura ottima. Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmo ED.|{{:informatica:all-b:ED.pdf|Edit Distance (note di F. Luccio)}}. [CLRS] cap 15: 15.4. | 
| 17/05/2018 | Problema delle apparizioni approssimate. Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino.  Algoritmo enumerativo per il problema dello zaino basato su genera binarie. Algoritmi pseudopolinomiali.| [CLRS] cap 16: 16.2, {{:informatica:all-b:ZainoPD.pdf|Algoritmo PD per lo Zaino}}.  [CGGR]: {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}}. |
| 22/05/2018 | Teoria della complessità: le classi P e NP, i problemi NP completi . |[BFL]: {{ :informatica:all-b:p-np.pdf | Le classi P, NP e NPC}} {{ :informatica:all-b:pvsnp.pdf |PvsNP}}|
| 22/05/2018 | **Laboratorio**: Simulazione prova di esame. | | 
| 23/05/2018 | **Esercitazione**: esercizi di ripasso su Grafi. | |
| 24/05/2018 | **Esercitazione**: esercizi di ripasso su Programmazione Dinamica. | |
| 29/05/2018 | **Esercitazione**: esercizi di ripasso. | {{ :informatica:all-a:algo_010617.pdf |testo}} e {{ :informatica:all-a:soluzione_compitino_2.pdf |soluzione}} {{ :informatica:all-a:algo_050917.pdf |testo}} e {{ :informatica:all-a:soluzioni_-_05-09-2017.pdf |Soluzione}}| 
| 29/05/2018 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezione12grafi.pdf | Slide}}|
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
