Matematica Discreta 2

a.a. 2000/2001

Programma

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 principio della piccionaia (pigeon hole principle)
• Numero di 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.