Matematica Discreta (II modulo)

a.a. 1999/2000 
Domenico Luminati

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

1. N. L. Biggs, Discrete Mathematics, Oxfors Science Publications,1998
2. J. Matousek, J. Nesetril,  Invitation to Discrete Mathematics, Oxford University Press, 1998
3. P. J. Cameron, Combinatorics: Topics, tecniques, algorithms, Cambridge University Press
4. A. Facchini, Algebra X informatica, Decibel-Zanichelli
5. B. Scimemi, Algebretta, Decibel ed.
6. B. Bollobas, Modern Graph Theory, Springer-Verlag, 1998.