Lista delle tesi tematiche offerte dal Prof. G. Persiano

Corso di Laurea in Informatica

Gli studenti interessati a svolgere una tesi progettuale sono pregati di contattare direttamente il prof. G. Persiano.

CLR indica il testo Introduction to Algorithms di T. H. Cormen, C. E. Leiserson e R. L. Rivest.

Algoritmi Greedy.
La tesi consiste nella discussione della tecnica greedy di progettazione di algoritmi. Spunti possono essere considerati, oltre ai testi elencati di seguito, anche i problemi presentati nel cap. 17 di CLR.
- CLR cap. 17 e riferiemnti contenuti
- Papadimitriou, Steglitz,
  Combinatorial Optimization: Algorithms and Complexity
- Korte, Lovasz,
  Mathematical Structure underlying Greedy Algorithms ,
  Lecture Notes in Computer Science, vol. 117, pag. 205-209.
- Korte, Lovasz,
  Structural Properties of Greedoids,
  in Combinatorica, 3:359-374, 1983.
Analisi Ammortizzata.
La tesi consiste nella discussione dell'analisi ammortizzata degli algoritmi. Il testo di Tarjan riportato di seguito costituisce un'ottima fonte di riferimento. Spunti implementativi possono essere considerati anche i problemi presentati in CLR.
- CLR cap. 18 e riferimenti contenuti
- Tarjan,
  Amortized Computational Complexity,
  in SIAM Journal on Algebraic and Discrete Methods 6(2):306-318, 1985.
Flusso su Grafi.
La tesi consiste nella discussione di alcuni algoritmi presenti in letteratura per il calcolo del flusso massimo in un rete di flusso.
- CLR cap. 27 e riferimenti contenuti
- Papadimitriou, Steglitz,
  Combinatorial Optimization: Algorithms and Complexity
- J. van Leeuwen,
  Graph Algorithms, capitolo 10 di Handbook of Theoretical Computer Science, volume A.
String Matching.
La tesi consiste nella discussione di alcuni algoritmi presenti in letteratura per il problema dello string matching e di alcune sue variazioni.
- CLR cap. 34 e riferimenti contenuti
Algoritmi combinatoriali per la pianificazione di movimenti di robot su grafi.
La tesi consiste nella discussione di alcuni algoritmi presenti in letteratura per il problema della pianificazione di movimenti di robot su grafi.
- C. Papadimitriou, P. Raghavan, M. Sudan and H. Tamaki, Motion Planning on a Graph in Proc. of 35-th IEEE Symp. on Found. of Comp. Sc., (FOCS), 511--520, 1994. Disponibile anche presso lo studio del Prof. Persiano.
- V. Auletta, D. Parente, G. Persiano,
  Optimal Planning of Robot Motion on a Tree with Obstacles
  In Proceedings of the 4th Annual European Symposium on Algorithms. Lecture Notes in Computer Science vol. 1136, Springer Verlag. Disponibile anche presso lo studio del Prof. Persiano.
- V. Auletta, D. Parente, A. Monti, G. Persiano,
  A Linear Time Algorithm for the Feasibility of Pebble Motion on Trees,
  in Proc. of the Fifth Scandinavian Workshop on Algorithm Theory, SWAT'96, Reykjavik, Iceland, July 3-5, 1996, L.N.C.S. 1097, 259--270. Disponibile anche presso lo studio del Prof. Persiano.
Intrattabilità computazionale di un'estensione del Gioco del 15. La tesi consiste nella presentazione della prova di NP-hardness di una generalizzazione del problema del 15.
- D. Ratner and M. Warmuth, Finding a Shortest Solution for the (N by N)-Extension of the 15 Puzzle is NP-hard, Journal of Symbolic Computation, 10:111--137, 1990 Disponibile anche presso lo studio del Prof. Persiano.