Corsi:

Ricevimento studenti:

Il Prof. Ausiello riceve gli studenti tutti i martedė, dalle 16.00 alle 18.00, presso l'ufficio B220 a Roma, Via Ariosto 25.

Corsi non pių erogati:

Argomenti di Tesi

 Nell'ambito del corso di Informatica Teorica sono disponibili tesi riguardanti essenzialmente A titolo puramente indicativo si presentano alcuni temi su cui sono in corso o sono programmate tesi di laurea.
  1. Studio di tecniche euristiche utilizzate per la risoluzione approssimata di problemi complessi (ad esempio tecniche di ricerca locale, tecniche greedy ecc.) e analisi delle loro prestazioni per varie tipologie di problemi, con lo scopo di individuare per quali tipi di problemi esse consentano di ottenere soluzioni approssimate di 'buona qualita'.
  2. Progetto e sperimentazione di algoritmi approssimati per problemi di ottimizzazione complessi che nascono nell'ambito dell'accesso alle informazioni nel web (ad esempio, studio di strategie di instradamento di uno o piu' agenti software per ottimizzare i tempi di ricerca di informazioni nel web).
  3. Progetto e sperimentazione di algoritmi on-line, vale a dire algoritmi che devono cominciare a servire una sequenza di richieste prima che l'intera sequenza da servire sia nota. La qualita' di algoritmi di tale tipo viene valutata confrontando il tempo di esecuzione richiesto dall'algoritmo on-line con il tempo di esecuzione di un algoritmo ottimo off-line che conoscesse in anticipo tutta la sequenza delle richieste da servire. Lo studio di algoritmi on-line efficienti e' utile in molti contesti applicativi:
    • scheduling (sequenziamento) di lavori su piu' processori o su piu' macchine,
    • problemi di gestione ottima della paginazione in un sistema di elaborazione o problemi di scelta delle pagine presenti nel web che e' opportuno mantenere nella cache di un server per ottimizzare i tempi di accesso alle informazioni,
    • problemi di instradamento, come quelli che ad esmpio sorgono quando uno o piu' veicoli devono servire una serie di richieste di trasporto di merci o passeggeri da una localita' ad un'altra o quando un riparatore riceve diverse chiamate e deve servirle in modo di minimizzare il tempo di attesa medio dei clienti.
  4. Progetto e sperimentazione di algoritmi per la gestione dinamica di grafi. In molti contesti applicativi le strutture informative che modellano la realta' di interesse vengono aggiornate durante l'elaborazione. Ad esempio se una rete e' modellata con un grafo e nuovi processori vengono aggiunti o i link o i processori esistenti hanno dei malfunzionamenti e' come se il grafo venisse modificato con inserimenti ed eliminazioni di nodi e di archi. In tal caso se precedentemente e' stato calcolato un minimo albero ricoprente del grafo si vuole aggiornare tale albero al nuovo grafo senza doverlo ricalcolare dall'inizio.
  5. Progetto e sperimentazione di algoritmi per ipergrafi orientati. Gli ipergrafi orientati sono una generalizzazione dei grafi orientati e vengono utilizzati in vari problemi come nella gestione dipendenze funzionali nelle basi di dati, nell'analisi di formule logiche di tipo implicativo (formule di Horn), nei problemi di diagnostica ecc. Molti problemi aperti in questo campo riguardano l'estensione agli ipergrafi di problematiche classiche dei grafi (cammini minimi, colorazione, planarita', ecc.)
Tutte le tesi svolte nell'ambito del corso di Informatica Teorica sono collegate alle attivita' di ricerca del Gruppo di Ingegneria degli Algoritmi del Dipartimento di Informatica e Sistemistica e consentono agli studenti di Gli studenti piu' preparati potranno essere inseriti sia durante sia dopo la tesi nei progetti di ricerca nazionali e internazionali cui partecipa il Gruppo stesso. Informazioni dirette e aggiornate sui temi di possibili tesi di Informatica Teorica possono essere chieste al Prof. Ausiello (ausiello@dis.uniroma1.it) Ulteriori informazioni possono essere chieste a