Introduzione all'uso della Matematica Discreta nell'Informatica. Serie formali e funzioni generatrici. Funzioni generatrici razionali, algebriche e D-finite. Permutazioni a motivo escluso. Teoria delle specie combinatorie. Generazione esaustiva di strutture combinatorie: algoritmi lessicografici e codici Gray. Metodi algoritmici per strutture discrete: problemi di ricostruzione, consistenza ed unicita’ di insiemi finiti di punti con e senza informazioni a priori.
Enumerative Combinatorics vol.I e II
CAMBRIDGE University Press.
E. Munarini, N. Zagaglia Salvi, Matematica Discreta, Citta’ Studi
Edizioni.
D.E. Knuth, The Art of Computer Programming, vol. 4, Addison-Wesley
Discrete Tomography: Foundations, Algorithms and Applications – G.T. Herman and A. Kuba eds. – Springer - 1999
Obiettivi Formativi
Conoscenze:
Utilizzo delle funzioni generatrici per l’enumerazione delle strutture
combinatorie, anche in connessione con l’analisi degli algoritmi.
Tecniche per la generazione di strutture combinatorie.
Tecniche per l’analisi e la ricostruzione di strutture discrete.
Competenze acquisite:
Competenze nel campo della Combinatoria e delle sue applicazioni nei
problemi informatici.
Capacita’ acquisite al termine del corso:
Al termine del corso gli studenti dovrebbero aver acquisito la capacita’ di
affrontare e risolvere un elevato numero di problemi di enumerazione
con lo strumento delle funzioni generatrici, anche in vista di applicazioni
all’analisi degli algoritmi. Dovrebbero inoltre essere in grado di utilizzare
e progettare algoritmi per la generazione di strutture combinatorie e per la loro ricostruzione in tempo polinomiale, qualora possibile, altrimenti determinare la NP-completezza del problema.
Prerequisiti
Corsi raccomandati:
Informatica
Algebra
Strutture Discrete
Linguaggi Formali e Codici
Logica e Calcolabilita’
Metodi Didattici
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attivita’ formative di tipo
individuale: 153
Numero di ore relative alle attivita’ in aula: 72
Numero di ore relative ad attivita’ di laboratorio (lezioni in laboratorio): 0
Numero di ore relative ad attivita’ di esercitazioni (in laboratorio e in
campo): 0
Numero di ore relative ad attivita’ seminariali: 0
Numero di ore relative ad attivita’ di stage: 0
Numero di ore per prove in itinere: 0
Altre Informazioni
Frequenza delle lezioni ed esercitazioni:
Non obbligatoria
Strumenti a supporto della didattica:
Nessuno
Orario di ricevimento:
Su appuntamento
Recapito:
Viale Morgagni, 65 - 50134 Firenze
Tel: 055 2751484 (Ferrari)
055 2751482 / 329 2985755 (Barcucci)
055 2751476 (Frosini)
E-mail: luca.ferrari@unifi.it
elena.barcucci@unifi.it
andrea.frosini@unifi.it
Web: http://www.dsi.unifi.it/~ferrari/
e-l.unifi.it
Modalità di verifica apprendimento
Prova orale, consistente in 3 prove distinte: una prova dulla parte di funzioni generatrici (un paio di domande sul contenuto del corso), una prova sulla parte di generazione di strutture, un seminario di approfondimento su uno degli argomenti trattati a lezione sulla parte di tomografia discreta.
Programma del corso
Introduzione all’uso della Matematica Discreta e della Combinatoria Enumerativa in Informatica con esempi e applicazioni. Introduzione del concetto di funzione generatrice ed esempi. Algebra delle serie formali di potenze. Funzioni generatrici razionali e classi di oggetti razionali (cammini nel piano, poliomini, alberi, permutazioni). Funzioni generatrici algebriche e classi di oggetti algebriche (cammini nel piano, poliomini, alberi, permutazioni). Metodologia di Schutzenberger. Funzioni generatrici D-finite e successioni P-ricorsive. Algoritmi per l'ordinamento di permutazioni (Stacksort, Popstacksort, Queuesort, IR-Dequesort); permutazioni a motivo escluso. Teoria delle specie combinatorie. Generazione di oggetti combinatori (tuple, permutazioni, partizioni, combinazioni, alberi). Algoritmi lessicografici. Codici Gray combinatori: aspetti algoritmici e graph-theoretic.
Definizione dei problemi di ricostruzione, consistenza ed unicita’ per strutture discrete a partire da proiezioni. Risultati presenti in letteratura. Esempi di problemi NP-hard e polinomiali. Introduzione di vincoli geometrici