====== Anno 2010-2011====== Docenti: **Roberto Grossi**, **Linda Pagli**, **Nadia Pisanti** === Avviso === Correzione compiti e verbalizzazione venerdì 18 febbraio ore 11:00 e lunedì 28 febbraio ore 11:00 presso lo studio della prof.ssa Pagli. === Obiettivi di apprendimento === In questo corso studieremo, progetteremo e analizzeremo soluzioni algoritmiche e strutture di dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato, quali interi, stringhe, punti (geometrici), alberi, grafi. Questo corso costituisce un naturale approfondimento e ampliamento delle conoscenze di base apprese nel percorso della laurea triennale. Il suo syllabus è organizzato per ambiti applicativi, al fine di contestualizzare le tecniche studiate nella realizzazione di software efficiente per essi, e così da consentire adattamenti e specializzazioni di anno in anno che si renderanno necessari e/o opportuni. === Programma === == Accesso ai dati e loro compressione == * Compressione di testi e di interi * Strutture di dati randomizzate * Motori di ricerca: liste invertite == Memorie gerarchiche == * Modelli di computazione * Permutazioni e ordinamenti * Dizionari == Stringologia == * Matrice dei suffissi * Albero dei suffissi * Algoritmi di pattern matching == Strutture di dati evolute == * Strutture di dati distribuite * Analisi competitiva * Algoritmi on-line == Problemi "difficili" e loro soluzione == * I problemi NP-hard * Algoritmi di approssimazione * Algoritmi randomizzati == Registro delle lezioni == * [[http://unimap.unipi.it/registri/printregistriNEW.php?re=46787:::&ri=5777|Collegamento a UNIMAP]] === Materiale didattico === * PROBLEMI DIFFICILI E APPROSSIMAZIONE * {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|dispensa_1.0.pdf: capitolo 9 del testo Crescenzi, Gambosi, Grossi}} * {{:magistraleinformatica:alg2:algo2_10:dispensa.pdf|dispensa_1.1.pdf (a cura di P. Crescenzi)}} * {{:magistraleinformatica:alg2:algo2_10:alg2_21-12.pdf|appunti_1.2 (a cura di E. Dinelli)}} * [[http://www.csc.kth.se/~viggo/wwwcompendium/|Sito dedicato a problemi di ottimizzazione NP-hard]] * [[http://www.tsp.gatech.edu|Sito dedicato al problema del commesso viaggiatore (TSP)]] * {{:magistraleinformatica:alg2:dispensa_1.pdf|dispensa_2.0.pdf: non-determinismo (a cura di Horowitz-Sahni)}} * L'esempio 12.2 contiene degli errori: individuarli. * Teoremi 12.5 e 12.7 senza dimostrazione. * Nel Teorema 12.8, k>=(1+e)n deve essere: k>=1+en. * [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/libro.html|dispensa_3.0: capitolo 2 del testo Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi]] * studiare soltanto: pp.39-47, paragrafo 2.2.2 * {{:magistraleinformatica:alg2:algo2_10:maxclique.pdf|dispensa_3.1}} * {{:magistraleinformatica:alg2:algo2_10:maxsat.pdf|dispensa_3.2: varianti di max-sat (da consultare)}} * STRINGOLOGIA * Exact matching ({{:magistraleinformatica:alg2:patternmatching1.pdf|}}, {{:magistraleinformatica:alg2:patternmatching2.pdf|}}) * Aho-Corasick{{:magistraleinformatica:alg2:uno.pdf|}} * Karp-Rabin {{:magistraleinformatica:alg2:due.pdf|}} * Suffix tree {{:magistraleinformatica:alg2:tre.pdf|}} * Suffix array {{:magistraleinformatica:alg2:quattro.pdf|}} * ALGORITMI ON LINE * Move to front {{:magistraleinformatica:alg2:mtf.pdf|}} * Algoritmi per il problema del paging {{:magistraleinformatica:alg2:paging.pdf|}} * Web Caching: algoritmi Greedy Dual e Greedy Dual Size {{:magistraleinformatica:alg2:algo2_10:gds.pdf|}} * HASHING DISTRIBUITO * Consistent Hashing {{:magistraleinformatica:alg2:algo2_10:consistenthashing.pdf|dispensa}} * Dalla tesi di master di Daniel M. Lewin{{:magistraleinformatica:alg2:ch1.pdf|prima parte}}{{:magistraleinformatica:alg2:ch2.pdf|seconda parte}}. Studiare fino all'enunciato del teorema 2.2.3. Poi i lemmi 2.2.5 e 2.2.6. * ALGORITMI RANDOMIZZATI * QUICKSORT randomizzato {{:magistraleinformatica:alg2:algo2_10:randqs.pdf|}} * Test di primalità di Miller&Rabin {{:magistraleinformatica:alg2:alg-random.pdf|}} * CUCU Hashing {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|}} * MEMORIE GERARCHICHE * Modelli di computazione, permutazioni e ordinamenti: J. S. Vitter. Algorithms and Data Structures for External Memory, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008. Also published as Volume 2, Issue 4 of Foundations and Trends in Theoretical Computer Science [[http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf|VERSIONE ELETTRONICA (introduzione, sezione 2.1, capitolo 3, sezione 5.2, sezione 5.6, sezione 11.1)]] === Risultati e Soluzioni === * VOTI FINALI PER I COMPITINI (voti dei due compitini, con media approssimata per eccesso e incrementata di tre punti per il punteggio finale): OMISSIS N.B.: per incrementare il voto finale, l'unica possibilità è quella di ripetere la prova nei prossimi appelli * Compitino del 15.12.2010 {{:magistraleinformatica:alg2:algo2_10:primo_compitino_2010.pdf|testo}} * Compitino del 26.01.2011 {{:magistraleinformatica:alg2:algo2_10:secondo_compitino_2010.pdf|testo}} * Risultati: OMISSIS * VOTI FINALI APPELLO DEL 1/2/2011 OMISSIS * VOTI FINALI APPELLO DEL 16/2/2011 OMISSIS * Risultati APPELLO DEL 06/06/2011: OMISSIS * Risultati APPELLO DEL 21/06/2011: OMISSIS * Risutati APPELLO DEL 07/07/2011: OMISSIS * Risutati APPELLO DEL 09/09/2011: OMISSIS * TESTI DI ALCUNI ESAMI: {{:magistraleinformatica:alg2:algo2_10:algo2_110621.pdf|}},{{:magistraleinformatica:alg2:algo2_10:algo2_110606.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-01-02-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-16-02-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-26-01-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-30-11-10.pdf|}}