Matematica Discreta 2
a.a. 1999/2000
Dott. Domenico Luminati
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
-
N. L. Biggs, Discrete Mathematics, Oxfors Science Publications,1998
-
J. Matousek, J. Nesetril, Invitation to Discrete Mathematics,
Oxford University Press, 1998
-
P. J. Cameron, Combinatorics: Topics, tecniques, algorithms, Cambridge
University Press
-
A. Facchini, Algebra X informatica, Decibel-Zanichelli
-
B. Scimemi, Algebretta, Decibel ed.
-
B. Bollobas, Modern Graph Theory, Springer-Verlag, 1998.
Per maggiori informazioni, si vedano le
pagine
del corso.