La matematica discreta nell'informatica. Introduzione alla combinatoria di funzioni, partizioni insiemistiche, partizioni intere e permutazioni. Principio di inclusione-esclusione e applicazioni.
Funzioni generatrici razionali e algebriche.
Insiemi parzialmente ordinati e reticoli; analisi formale dei concetti; reticoli distributivi e algebre di Boole; connessioni di Galois; CPO e teoremi di punto fisso; reticoli algebrici.
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. Al termine del corso gli studenti avranno acquisito un bagaglio di conoscenze piuttosto dettagliato riguardo alcuni aspetti di combinatoria enumerativa e teoria degli insiemi parzialmente ordinati e reticoli e saranno in grado di affrontare e risolvere problemi di media difficoltà in tali ambiti. Il corso fornisce anche le basi necessarie per ulteriori approfondimenti nell'ambito della matematica discreta.
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
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
Consegna di esercizi svolti durante l'anno, seminario (di una decina di minuti) su un argomento pertinente al corso ma non coperto durante le lezioni, esame orale (una domanda sulla parte di combinatoria, una domanda sulla parte di insiemi parzialmente ordinati e reticoli).
Programma del corso
La matematica discreta nell'informatica.
Introduzione alla combinatoria enumerativa: funzioni, funzioni iniettive e suriettive 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 distributivi e algebre di Boole; teoremi di rappresentazione di Stone e di Birkhoff; operatori di chiusura e connessioni di Galois; insiemi parzialmente ordinati completi e teoremi di punto fisso; strutture di chiusura algebriche, operatori di chiusura algebrici e reticoli algebrici.
Algebre di incidenza e funzioni di Möbius; teorema di inversione di Möbius; calcolo della funzione di Möbius; alcune applicazioni (il problema delle collane, il polinomio cromatico di un grafo, l'enumerazione dei grafi connessi).
Funzioni generatrici: 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); i numeri di Catalan.