Insegnamento mutuato da: B012999 - METODI MATEMATICI PER L'INFORMATICA Laurea Magistrale in MATEMATICA Curriculum APPLICATIVO
Lingua Insegnamento
Italiano
Contenuto del corso
ntroduzione all'uso della Matematica Discreta e della Combinatoria Enumerativa nell'Informatica. Serie formali e funzioni generatrici. Funzioni generatrici razionali e algebriche. Cenni a metodi di analisi asintotica per la stima dei coefficienti di una funzione generatrice. 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
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). Teorema di inversione di Lagrange. Funzioni generatrici algebriche e classi di oggetti algebriche (cammini nel piano, poliomini, alberi, permutazioni). Metodologia di Schutzenberger. Cenni a metodi di analisi asintotica per la stima dei coefficienti di una funzione generatrice; applicazioni all’analisi degli algoritmi. 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