Combinatoria enumerativa: numeri speciali associati all'enumerazione di classi di funzioni, partizioni insiemistiche, partizioni di interi e permutazioni. Il principio di inclusione-esclusione e alcune sue applicazioni. Insiemi parzialmente ordinati e reticoli: concetti di base e applicazioni informatiche; analisi formale dei concetti; insiemi parzialmente ordinati completi e teoremi di punto fisso. Algebre di incidenza e funzioni di Moebius; teorema di 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, Città Studi Edizioni.
R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press.
Obiettivi Formativi
Conoscenze: Il corso mira a fornire gli elementi di base della combinatoria enumerativa e della teoria degli insiemi parzialmente ordinati e dei reticoli, con particolare riferimento alle loro applicazioni all'informatica teorica.
Competenze acquisite: lo studente svilupperà alcuni strumenti fondamentali di combinatoria enumerativa e di teoria degli insiemi parzialmente ordinati e dei reticoli, particolarmente utili in informatica teorica.
Capacità acquisite (al termine del corso): Lo studente sarà in grado di risolvere esercizi e problemi di media difficoltà di combinatoria enumerativa e che coinvolgono concetti della teoria degli ordini parziali.
Prerequisiti
Corsi raccomandati: Informatica
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Modalità di verifica apprendimento
Esercizi da svolgere durante il corso ed 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.
Insiemi parzialmente ordinati e reticoli: concetti di base e principali applicazioni informatiche; analisi formale dei concetti; reticoli completi e connessioni di Galois; insiemi parzialmente ordinati completi e teoremi di punto fisso.
Algebre di incidenza e funzioni di Moebius; teorema di inversione di Moebius; alcune applicazioni (il problema delle collane, il polinomio cromatico di un grafo).