Next: Lezione 1 Up: Matematica Discreta 2003/2004

Matematica Discreta (II modulo)

Domenico Luminati

Date: a.a. 2003/2004

Questo breve dispensa raccoglie gli argomenti trattati nei corsi di Matematica Discreta da me tenuti in vari anni accademici dal 1999 al 2004.

Essa, non vuole sostitutire i libri di testo, che restano quelli indicati nel programma del corso ed ai quali in alcune parti si rimanda esplicitamente, ma si pone soltanto l'obiettivo di dare allo studente una traccia da seguire per la preparazione dell'esame.

Lezione 1
- Insiemi e operazioni tra insiemi
- Relazioni, funzioni parziali e funzioni totali
Lezione 2
- Equipotenza di insiemi
- I numeri naturali: gli assiomi di Peano
- Il principio di induzione (prima forma)
- Il teorema di ricorsione
Lezione 3
- Le operazioni sui naturali
- L'ordinamento dei naturali
- Insiemi ordinati
- L'ordinamento dei naturali e le operazioni
- Insiemi finiti: il Lemma dei cassetti
Lezione 4
- Cardinalità degli insiemi finiti
- Sottinsiemi di un insieme finito
- Scommettiamo che due di voi hanno lo stesso compleanno?
Lezione 5
- Insiemi infiniti: l'assioma della scelta
Lezione 6
- Insiemi numerabili
- Confronto di cardinalità: il Teorema di Cantor-Bernstein
- La tricotomia dei cardinali
- Il procedimento diagonale di Cantor
Lezione 7
- Operazioni tra cardinalità
- L'assioma di buon ordinamento
- Il principio di induzione (seconda forma)
- La divisione euclidea
Lezione 8
- Scrittura in base arbitraria dei naturali.
- Il coefficiente binomiale
- -sottinsiemi
- Perché non gioco al Superenalotto!
Lezione 9
- Divisibilità e sue prime proprietà
- Il massimo comun divisore: definizione, esistenza e unicità
- L'algoritmo di Euclide per il calcolo del M.C.D.
Lezione 10
- Proprietà dei numeri coprimi e caratterizzazione dei numeri primi
- Il minimo comune multiplo: definizione, esistenza e unicità
- Il teorema fondamentale dell'Aritmetica
- Esistenza di infiniti numeri primi
Lezione 11
- Definizione di congruenza e prime proprietà
- Classi d'equivalenza
- Classi di congruenza
- Le classi modulo sono esattamente
- Somma e prodotto di classi di congruenza
Lezione 12
- Il teorema cinese del resto
- Elementi invertibili modulo
Lezione 13
- Equazioni lineari modulo
- Il piccolo teorema di Fermat
- Crittografia RSA
Lezione 14
- Definizione di grafo
- Alcuni grafi notevoli
- Sottografi e sottografi indotti
- Morfismi ed isomorfismo di grafi
Lezione 15
- Una stima del numero di grafi non isomorfi su vertici
- Passeggiate, cammini e cicli
- La relazione di essere congiungibili
Lezione 16
- Componenti connesse di un grafo
- Le componenti connesse sono invarianti per isomorfismo
- Grafi connessi
- La matrice di adiacenza di un grafo finito
Lezione 17
- Grado di un vertice
- Il lemma delle strette di mano
- Score di un grafo
- Teorema dello score
Lezione 18
- Definizione di grafo euleriano
- Caratterizzazione dei grafi euleriani
- Definizione di grafo hamiltoniano
- Grafo duale di un grafo dato
- è connesso allora anche il suo duale lo è
- Se è euleriano allora il suo duale è hamiltoniano
Lezione 19
- Alcune costruzioni con i grafi
- Definizione di grafo 2-connesso
- Prima caratterizzazione dei grafi 2-connessi
- Seconda caratterizzazione dei grafi 2-connessi
Lezione 20
- Alberi
- Il teorema di caratterizzazione degli alberi
- Il teorema di caratterizzazione degli alberi finiti
Lezione 21
- Albero di copertura
- Alberi radicati
- La relazione $\to$ di ``paternità'' in un albero radicato
Lezione 22
- L'ordinamento degli alberi radicati
- Induzione sugli alberi radicati
- Il lemma di König
Lezione 23
- Il lemma di Zorn
- Esistenza di alberi generatori: il caso infinito
Soluzione di alcuni degli esercizi proposti

Domenico Luminati 2004-03-18