Matematica Discreta 2
a.a. 2004/2005
Domenico Luminati
Questo è il programma di massima del corso, che potrà essere
tagliato e/o modificato per esigenze di tempo.
1. Insiemi e cardinalità
-
Insiemi,relazioni, funzioni
-
Il teorema di Cantor
-
Il teorema di Cantor-Bernstein
2. I numeri interi
-
assiomi di Peano e induzione
-
equazioni ricorsive lineari
-
divisibilità, massimo comun divisore e minimo comune multiplo, fattorizzazione
unica
-
scrittura in base arbitraria dei numeri interi
-
congruenze, classi di resto, il teorema cinese
3. Calcolo combinatorio
-
Il lemma dei cassetti
-
contare gli elementi di particolari insiemi (prodotto cartesiano, applicazioni,
parti)
-
combinazioni, disposizioni, permutazioni
-
principio di inclusione ed esclusione, applicazioni surgettive, permutazioni
senza punti fissi
4. Grafi
-
grafi, alberi e foreste, il lemma di König
-
alberi generatori
-
grafi pesati
-
grafi euleriani e grafi hamiltoniani
-
grafi diretti, reti, teorema min-cut max-flow
Testi consigliati
La maggior parte degli argomenti svolti a lezione sono trattati nei due
libri:
- B. Scimemi, Algebretta, Decibel-Zanichelli, 1989
- J. Matousek, J. Nesetril, Invitation to Discrete
Mathematics, Oxford University Press, 1998
Altro materiale si può trovare su
- N. L. Biggs, Discrete Mathematics, Oxfors Science
Publications,1998
- A. Facchini, Algebra X informatica, Decibel-Zanichelli
A disposizione degli studenti c'è anche una dispensa reperibile sulle
pagine web del docente
Ulteriori approfondimenti, che vanno oltre le finalità del corso,
possono essere trovate nei seguenti libri:
- P. J. Cameron, Combinatorics: Topics, tecniques, algorithms, Cambridge
University Press
- B. Bollobas, Modern Graph Theory, Springer-Verlag, 1998.
Torna alla pagina principale.