In questa pagina si trova materiale relativo al corso di
Matematica Discreta per
il corso di laurea in ingegneria elettronica,
Università di Roma Tre.
Avvisi:
L'esame è il 19 novembre alle 14.30 in aula N20.
Qui trovate il programma del corso.
Il testo consigliato è:
L. Berardi, A. Beutelspacher, Matematica Discreta, Franco Angeli.
Diario delle lezioni:
- 5 ottobre: Insiemi, funzioni fra insiemi. Insieme delle parti,
cardinalità dell'insieme delle parti. Principio di induzione.
- 6 ottobre:
Funzioni iniettive fra insiemi finiti.
Permutazioni.
- 7 ottobre: Coefficienti binomiali. Triangolo di Tartaglia.
- 8 ottobre:
Teorema binomiale. Principio dei cassetti e applicazioni.
- 9 ottobre: I numeri interi. Divisione col resto. Il massimo
comun divisore e l'algoritmo euclideo.
- 12 ottobre:
Identità di Bézout, soluzione di equazioni diofantee. Numeri
primi, teorema di Euclide
- 13 ottobre:
Teorema fondamentale dell'aritmetica. Congruenze.
- 14 ottobre: Proprietà delle congruenze. L'insieme
delle classi resto modulo n. Operazioni in questo insieme.
- 15 ottobre:
Invertibili in Z_n, e calcolo dell'inverso.
Funzione di Eulero.
- 16 ottobre:
Piccolo Teorema di Fermat. Teorema di Eulero.
Risoluzione di congruenze lineari.
- 19 ottobre: Congruenze lineari. Sistemi di congruenze.
- 20 ottobre:
Il teorema cinese dei resti.
- 21 ottobre: Esercitazione.
- 22 ottobre: Esonero.
- 23 ottobre:
Grafi: esempi, definizioni, notazioni. Isomorfismo fra grafi.
Valenza di un vertice.
Grafi completi e nulli.
- 26 ottobre:
Passeggiate, piste,
cammini, circuiti. Connessione, componenti connesse.
Grafi euleriani.
- 27 ottobre:
Teorema di Eulero. Grafi hamiltoniani.
- 28 ottobre:
Alberi e loro proprietà.
- 29 ottobre:
Minimo albero ricoprente. Algoritmo di Kruskal.
Cenni sulle colorazioni di verici.
- 30 ottobre:
Esercizi.
- 2 novembre: Numero cromatico. Algoritmo di colorazione.
Grafi bipartiti.
- 3 novembre:
Grafi orientati, reti, reti di flusso.
- 4 novembre:
Teorema del massimo flusso-minimo taglio.
- 5 novembre: Calcolo del massimo flusso e del minimo taglio.
- 6 novembre: Esercitazione.
Esercizi:
- Foglio 1. Insiemi, funzioni, permutazioni,
coefficienti binomiali.
-
Foglio 2. Massimo comun divisore, algoritmo di
Euclide, congruenze.
-
Foglio 3.
Risoluzione di congruenze. Invertibili in Zn.
-
Foglio 4.
Teoria dei grafi.
Se volete fare pratica con l'aritmetica modulare, provate qui.
(Nota: ricaricando la pagina ottenete nuovi esercizi)
Vi segnalo le
Note di teoria dei
grafi di
Francesco Bottacin
Testi di teoria dei grafi disponibili in rete: