L'ultima
lezione del corso di Strutture Discrete si terrà lunedì
16 dicembre, alle ore 15.30, e durerà 2 ore.
Nell'ultima
lezione descriveremo le partizioni noncrossing come ulteriore
interpretazione combinatoria dei numeri di Catalan, quindi
dimostreremo una ricorrenza lineare a coefficienti polinomiali e
l'identità di Touchard per i numeri di Catalan.
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, multinsiemi, partizioni di
interi, composizioni 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, i numeri Euleriani.
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); la
funzione di Möbius di un reticolo distributivo.
Funzioni
generatrici: introduzione
del concetto di funzione generatrice ed esempi; algebra delle serie
formali di potenze; tipi di funzioni generatrici e algebra di
incidenza; 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.
Testi di consultazione.
M. Aigner, Combinatorial Theory, Springer.
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, Cambridge University Press.
Modalita' d'esame.
L’esame prevede le seguenti prove:
1) risoluzione, preferibilmente (ma non necessariamente) in gruppi di alcune persone, di esercizi assegnati durante le lezioni. Gli esercizi saranno reperibili su questa pagina web. Per l'anno accademico 2010/2011, gli esercizi sono reperibili a questo link. Per l'anno accademico 2011/2012, gli esercizi sono reperibili a questo link. Per l'anno accademico 2012/2013, gli esercizi sono reperibili a questo link. Per l'anno accademico 2013/2014, gli esercizi sono reperibili a questo link. Per l'anno accademico 2014/2015 gli esercizi sono reperibili a questo link. Per l'anno accademico 2015/2016 gli esercizi sono reperibili a questo link. Per l'anno accademico 2016/2017 gli esercizi sono reperibili a questo link. Per l'anno accademico 2017/2018 gli esercizi sono reperibili a questo link. Per l'anno accademico 2018/2019 gli esercizi sono reperibili a questo link. Per l'anno accademico 2019/2020 gli esercizi sono reperibili a questo link. Per l'anno accademico 2020/2021 gli esercizi sono reperibili a questo link. Per l'anno accademico 2021/2022 gli esercizi sono reperibili a questo link. Per l'anno accademico 2022/2023 gli esercizi sono reperibili a questo link. Per l'anno accademico 2023/2024 gli esercizi sono reperibili a questo link. Per l'anno accademico 2024/2025 gli esercizi sono reperibili a questo link. La consegna degli esercizi risolti dovrà avvenire almeno 7 giorni prima della data fissata per la prova orale (preferibilmente anche qualche giorno prima!), a mano o per posta elettronica. La mancata consegna entro il termine previsto non consentirà di accedere alle prove successive.
2) esposizione (della durata di 10 minuti al massimo) di un argomento a scelta, collegato al programma del corso ma non svolto a lezione; possibili suggerimenti sono contenuti in questo file. Si consiglia comunque di comunicare preventivamente l'argomento scelto, in modo che io possa eventualmente consigliarvi dove reperire del materiale adatto.
3) prova orale.
Se la prima prova non viene superata, non è possibile accedere alle successive; di norma, la seconda e la terza prova vengono sostenute insieme.
Le date dei prossimi esami sono le seguenti:
I appello invernale:
-)
23/1/2025, ore 10.30, aula 207;
II appello invernale:
-)
12/2/2025, ore 10.30, aula 207.