Introduzione all'uso della Matematica Discreta nell'Informatica. Funzione generatrice di linguaggi regolari e context-free, metodologia di Schutzenberger. Funzioni generatrici D-finite. Permutazioni a motivo escluso. 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.
R. P. Stanley, Enumerative Combinatorics vol.I e II, CAMBRIDGE University Press.
M. Bona, Combinatorics of Permutations, Chapman&Hall/CRC.
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://web.math.unifi.it/users/ferrari/
e-l.unifi.it
Modalità di verifica apprendimento
Prova orale, consistente in 3 prove distinte: una prova sulla 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. Cenni a linguaggi e grammatiche regolari e context-free. Funzione generatrice di un linguaggio, 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. Transfer-matrix method. Teorema di inversione di Lagrange. Strutture esponenziali.
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