La matematica discreta nell'informatica. Introduzione alla combinatoria di funzioni, partizioni insiemistiche, partizioni intere e permutazioni. Principio di inclusione-esclusione e applicazioni.
Funzioni generatrici e loro utilizzo per l’enumerazione di strutture combinatorie.
Insiemi parzialmente ordinati e reticoli; analisi formale dei concetti; connessioni di Galois; CPO e teoremi di punto fisso; domini e information systems.
Algebre di incidenza; inversione di Moebius e applicazioni.
M. Cerasoli, F. Eugeni, M. Protasi, Elementi di Matematica Discreta, Zanichelli.
B. A. Davey, H. A. Priestley, Introduction to lattices and order, Cambridge University Press.
E. Munarini, N. Zagaglia Salvi, Matematica Discreta, Citta’ Studi Edizioni.
R. P. Stanley, Enumerative Combinatorics, vol. I e II, Cambridge University Press.
Obiettivi Formativi
Il corso mira a fornire gli elementi di base della combinatoria enumerativa e algebrica e della teoria degli insiemi parzialmente ordinati e dei reticoli, con riferimento anche alle loro applicazioni all'informatica teorica.
Prerequisiti
Nozioni di base di Informatica e di algebra lineare.
Metodi Didattici
Lezioni frontali
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Orario di ricevimento: su appuntamento
Recapito:
Dipartimento di Matematica e Informatica "Ulisse Dini"
Viale Morgagni, 65
50134 FIRENZE
Tel: 055 2751484
Fax: 055 4237436
E-mail: luca.ferrari@unifi.it
Durante il corso verranno assegnati alcuni esercizi da svolgere, la cui consegna sara’ necessaria per sostenere l’esame orale.
Modalità di verifica apprendimento
Esame orale
Programma del corso
La matematica discreta nell'informatica. Introduzione alla combinatoria enumerativa: funzioni, funzioni iniettive, suriettive e monotone e numeri speciali associati alla loro enumerazione; the twelvefold way; combinatoria enumerativa elementare di partizioni insiemistiche, partizioni di interi e permutazioni.
Il principio di inclusione-esclusione e alcune sue applicazioni: il problema dei derangements, l'enumerazione delle funzioni suriettive, la funzione Phi di Eulero, il problema dei menages.
Funzioni generatrici: nozioni di base, manipolazione di funzioni generatrici, funzioni generatrici razionali e algebriche, applicazioni all’enumerazione di strutture combinatorie.
Insiemi parzialmente ordinati e reticoli: concetti di base e principali applicazioni informatiche; analisi formale dei concetti; operatori di chiusura e connessioni di Galois; insiemi parzialmente ordinati completi e teoremi di punto fisso; domini e information systems.
Algebre di incidenza e funzioni di Moebius; teorema di inversione di Moebius; alcune applicazioni (il problema delle collane, il polinomio cromatico di un grafo).