Diario delle lezioni di Matematica Discreta 2016

Lunedì 22 febbraio 2016

Lezione 1 e 2: Una breve introduzione ai problemi e ai metodi della matematica discreta. Se si frequentano le lezioni assiduamente è sufficiente studiare sui miei Appunti di Matematica Discreta (Esculapio ed. 2016). In caso contrario, potrebbe essere necessario approfondire su alcuni dei seguenti testi consigliati:

a. Baldoni, Ciliberto, Piacentini Cattaneo: Aritmetica, Crittografia e Codici, Springer 2006

b. Biggs, Discrete Mathematics, Oxford, 2002

c. Brualdi, Introductory Combinatorics, Prentice Hall, 1999.

d. Cerasoli, Eugeni, Protasi, Elementi di Matematica Discreta, Zanichelli 1988

e. Knuth, The art of Computer Programming, Vol. I Addison Wesley, 1997

f. Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley 1988

g. Schroeder, Number Theory in Science and Communication, Springer 2009

La lettura del testo di Schroeder è particolarmente consigliata per le motivazioni che fornisce allo studio della teoria dei numeri e della matematica discreta.

Numeri naturali. Principio di induzione e principio del buon ordinamento. Massimo comun divisore e identità di Bézout. Teorema fondamentale dell’aritmetica. Numeri perfetti. Numeri di Mersenne. (1.1-1.3 Appunti)

Mercoledì 24 febbraio 2016

Lezione 3:

Svolgimento di esercizi su principio di induzione e identità di Bézout. Infinità dei numeri primi: dimostrazioni di Euclide ed Eulero. Cenni alla dimostrazione di Erdös. (1.4 Appunti)

Lunedì 29 febbraio 2016

Lezione 4 e 5: Cenni alle frazioni continue. Come scrivere la frazione continua di un numero razionale e di una radice quadrata.

Definizione della relazione di congruenza. Proprietà delle congruenze. Insieme quoziente. Insieme quoziente come gruppo abeliano e come anello. Tabelle additive e moltiplicative. Invertibilità e calcolo della classe inversa mediante l’identità di Bézout. Divisori di zero. Altre proprietà. Applicazione ai criteri di divisibilità. Piccolo Teorema di Fermat.

(Appunti 1.5, 1.6)

Mercoledì 2 marzo 2016

Lezione 6: Dimostrazione del Piccolo Teorema di Fermat. Risoluzione di congruenze lineari. Sistemi di congruenze. Teorema Cinese dei Resti.

(Appunti 1.6, 1.7)

Lunedì 7 marzo 2016

Lezione 7 e 8: Dimostrazione del Teorema Cinese dei Resti. Caso di sistemi con moduli non primi tra loro. La funzione di Eulero. Introduzione alla teoria dei gruppi: definizioni, esempi. Gruppi diedrali. Gruppi di permutazioni.

(Appunti 1.7, 1.8, 2.1)

Mercoledì 9 marzo 2016

Lezione 9: Esempi di gruppi. Z,Q,R,C con addizione, Q*,R*,C* con il prodotto, Z_n con l’addizione, R[x], GL₂(R), O₂(R). Struttura di gruppo abeliano sulla curva di equazione y²=x³-2x. Legge di cancellazione. Ordine di un gruppo. Ordine di un elemento di un gruppo. Gruppo delle radici n-esime di 1. Generatori. Radici n-esime primitive. Generatori di Z_n. Definizione di sottogruppo. Definizione di gruppo ciclico.

(Appunti 2.1, 2.2)

Lunedì 14 marzo 2016

Lezione 10 e 11: Proprietà dei gruppi ciclici. Teorema di Lagrange. Corollari. Teorema di Eulero. Omomorfismi di gruppi. Classificazione dei gruppi ciclici.

(Appunti 2.2, 2.3, 2.4)

Mercoledì 16 marzo 2016

Lezione 12: Definizione di Anelli e Campi. Esempi di anelli e di campi. Anelli di polinomi. Anelli euclidei.

(Appunti 2.5, 2.6)

Lunedì 21 marzo 2016

Lezione 13 e 14: Una diversa costruzione del campo con 9 elementi. Caratteristica di un campo. Sottocampo fondamentale. Ogni campo è uno spazio vettoriale a coefficienti sul suo sottocampo fondamentale. Teorema di Classificazione dei campi finiti. Costruzioni di un campo finito mediante anelli di polinomi e polinomi irriducibili. Esempi di calcolo.

Elementi di Crittografia. Crittografia classica: Cifrario di spostamento; cifrario affine; cifrario di sostituzione.

Cifrari polialfabetici: cifrario di Hill; cifrario di permutazione; cifrario di Vigénère.

(Appunti 2.6, 3.1)

Mercoledì 23 marzo 2016

Lezione 15: Criptoanalisi del cifrario di Vigénère. Test di Kasiski. Indice di coincidenza di Friedman. Cenni al One Time Pad. Definizione di segretezza perfetta di C. Shannon.

(Appunti extra)

Mercoledì 30 marzo 2016

Lezione 16: Esercitazione. Svolgimento degli esercizi assegnati il 23 marzo.

Lunedì 4 aprile 2016

Lezione 17 e 18: Prova di esonero.

Mercoledì 6 aprile 2016

Lezione 19: Protocollo Diffie-Helmann per lo scambio delle chiavi. Crittografia a chiave pubblica RSA.

Riferimenti: Diffie-Hellman paper, RSA paper

Lunedì 11 aprile 2016

Lezione 20 e 21: Introduzione alla teoria dei codici. Codici a blocchi. Distanza di Hamming. Parametri di un codice. Distanza minima. Calcolo o stima di A_q(n,d). Codici equivalenti. Disuguaglianza di Hamming. Codice Ham(7,4): piano di Fano. Codice perfetto. Codici lineari. Peso di una parola. Matrice generatrice di un codice.

Lettura consigliata: R.W.Hamming: The unreasonable Effectiveness of Mathematics

Mercoledì 13 aprile 2016

Lezione 22: Equivalenza di codici lineari. Matrici generatrici di codici equivalenti. Forma standard di una matrice generatrice. Codifica e decodifica del messaggio mediante standard array. Leader di una classe laterale.

Lunedì 18 aprile 2016

Lezione 23 e 24: Codice duale, matrice di controllo di parità. Decodifica per sindrome. Codici di Hamming: Ham(r,q), r intero positivo, q potenza di un primo. I codici Ham(r,q) sono perfetti.

Introduzione alla combinatoria enumerativa. Concetto di funzione generatrice, (cf. Trasformata zeta o Z-transform: http://ocw.usu.edu/Electrical_and_Computer_Engineering/Signals_and_Systems/lecture2.pdf

http://www.eas.uccs.edu/~mwickert/ece2610/lecture_notes/ece2610_chap7.pdf)

Funzioni generatrici di alcune successioni date per ricorrenza.

Mercoledì 20 aprile 2016

Lezione 25: Funzione generatrice dei numeri di Fibonacci. Formula di Binet. Coefficienti binomiali. Anello delle serie formali. Reciproco e inverso di una serie formale.

Mercoledì 27 aprile 2016

Lezione 26: Leggi ricorsive lineari omogenee, Numeri di Catalan.

Lunedì 2 maggio 2016

Lezione 27 e 28: Una funzione generatrice per i numeri di Catalan e una formula chiusa per essi. Partizioni di interi, diagrammi di Ferrers, Funzione generatrice delle partizioni. Teorema di Eulero su partizioni in parti distinte e parti dispari. Principi enumerativi elementari: regola della somma, del prodotto, della biiezione, del doppio conteggio. Principio dei cassetti o di Dirichlet. Alcune proprietà dei coefficienti binomiali. Identità di convoluzione di Vandermonde.

Mercoledì 4 maggio 2016

(Attenzione: InfoSapienza ha attivato le procedure telematiche per la Rilevazione Opinioni Studenti sugli insegnamenti del secondo semestre per l'a.a. 2015-2016. Siete invitati ad esprimere le vostre opinioni)

Lezione 29: Introduzione alla Teoria dei Grafi. Il problema dei ponti di Königsberg (Eulero 1736).

http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html

http://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem

Definizione di grafo semplice: spigoli, vertici, grado di un vertice. Handshaking lemma. Alcuni grafi speciali: grafi completi, cicli, ipercubi n-dimensionali. Grafi bipartiti. Condizione necessaria e suffciente affinché un grafo sia bipartito. Matching. Matching completo. Teorema del matrimonio di Hall.

Una attività divertente: http://www2.mps.mpg.de/homes/heller/downloads/files/SETI_rules.txt

Si tratta di scaricare un testo composto di una sola stringa binaria lunga 1,902,341 caratteri (435 pagine di testo). La sfida dell’autore, leggete nel link qui sopra, è di immaginare che la stringa sia stata ricevuta dallo spazio. Bisogna decriptarla. Potete collaborare con chi volete. I vincitori saranno annunciati il 3 giugno prossimo.

Lunedì 9 maggio 2016

Lezione 30 e 31: Matrice di adiacenza e di incidenza. Criterio di connettività mediante potenze della matrice di adiacenza. Isomorfismo di grafi. Teorema di Eulero: Condizione necessaria e sufficienza affinché un grafo sia euleriano. Grafi hamiltoniani. Condizione di Ore e di Dirac. Grafi planari. Formula di Eulero: f=e-v+2. Grafi di poliedri regolari. Teorema di Kuratowski. Colorazione di grafi. Teorema dei quattro colori (http://www.ams.org/notices/200811/tx081101382p.pdf) . Problema della calendarizzazione. Numero cromatico.

Mercoledì 18 maggio 2016 (attenzione al cambio di data)

Lezione 32: Esercitazione: Lista di esercizi Esercizi svolti

Lunedì 23 maggio ore 15:45-19 Seconda Prova d’esonero.

24 maggio: ho iniziato la correzione. I risultati appariranno qui.

Ricordatevi di prenotarvi su Infostud.

25 maggio: corretti 13 compiti su 21. Compiti in media buoni.

26 maggio: finita la correzione.

Risultati del secondo esonero e risultato finale

Avviso: la settimana prossimo sarò fuori Roma per un Convegno Scientifico. Leggerò la posta elettronica saltuariamente.

Ricordatevi la prenotazione su Infostud. La verbalizzazione avverrà secondo un calendario che apparirà su questa pagina o sulla mia ``home page’’ (http://www.dmmm.uniroma1.it/~stefano.capparelli/)

Primo appello d’esame: Aula 12 Via Scarpa ore 14 del 7 giugno 2016

Secondo appello d’esame: Aula 12 Via Scarpa ore 14 del 7 luglio 2016

Risultati del compito di Matematica Discreta del 7 luglio 16

Terzo appello d’esame: Aula 3 Via Scarpa ore 9 del 9 settembre 2016

Nel programma di studio riferito a Appunti di Matematica Discreta, Esculapio, 2016 si può omettere la parte dei polinomi ortogonali del paragrafo 7.2 e la parte sugli alberi del paragrafo 8.10.