|
1021828 -
MATEMATICA DISCRETA
(obiettivi)
IL CORSO SI PROPONE DI FORNIRE ALLO STUDENTE UN’INTRODUZIONE ALLA MATEMATICA DISCRETA, CHE COSTITUISCE UNO DEI SETTORI PIÙ INNOVATIVI DELLA MATEMATICA. SVILUPPATO A PARTIRE DALLA SECONDA METÀ DEL NOVECENTO, E’ RICCO DI PROBLEMI STIMOLANTI E DI GRANDE UTILITÀ NELLE APPLICAZIONI. DURANTE IL CORSO, LO STUDENTE VERRÀ A CONTATTO CON UNA SERIE DI ARGOMENTI E PROBLEMI, DI TIPO COMPLETAMENTE DIVERSO DA QUELLI INCONTRATI IN ALTRI CORSI DI MATEMATICA TRADIZIONALI, E SVILUPPERÀ, ATTRAVERSO UN IMPEGNO SISTEMATICO RIVOLTO AL “PROBLEM SOLVING”, UN APPROCCIO CONCRETO ALLO STUDIO DI PROBLEMI DI GRANDE VALENZA FORMATIVA, SOPRATTUTTO PER LA FUTURA ATTIVITÀ PROFESSIONALE.
-
CAPPARELLI STEFANO
( programma)
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. Esistono infiniti numeri primi: dimostrazione di Euclide. Numeri perfetti. Numeri di Mersenne. (1.1-1.3 Appunti)
Esercizi.
Lezione 3: La dimostrazione di Euclide può essere adattata per dimostrare che esistono infiniti primi della forma 4n+3. Perché lo stesso ragionamento non funziona per dimostrare che esistono infiniti primi della forma 4n+1? (V. Appunti p.6)
Dimostrazione che la serie dei reciproci dei numeri primi diverge, da cui, come conseguenza, segue che i numeri primi sono infiniti.
Definizione di frazione continua e qualche calcolo semplice per scrivere frazioni come frazioni continue. Frazioni continue infinite. Il caso della frazione continua [1;1,1,1,1,1,…]. (Appunti 1.4,1.5)
Esercizi.
Lezione 4 e 5: Frazioni continue e algoritmo delle divisioni successive di Euclide. Convergente come migliore approssimazione razionale con denominatore piccolo. Metodo ricorsivo per calcolare rapidamente il valore di una frazione continua. Caso della sezione aurea e successione di Fibonacci.
Esercizi:
Definizione di relazione di congruenza. Insieme quoziente delle classi resto modulo n. Tabelle additive e moltiplicative di Z6 e Z7. Divisori dello zero. Elementi invertibili di Zn. Struttura di gruppo abeliano e di anello in Zn. Struttura di campo in Zn, quando n è primo. Proprietà delle congruenze. Come semplificare una congruenza. Lemma sulla potenza di un binomio modulo un primo. (Appunti 1.6 )
Esercizi:
Lezione 6: Criteri di divisibilità. Piccolo teorema di Fermat e sua dimostrazione. Risoluzione di congruenze lineari. Criterio per la risolubilità. Metodo di soluzione.
(Appunti 1.7)
Esercizi:
Lezione 7,8: Esercizi di risoluzione di congruenze lineari. Sistemi di conguenze: teorema cinese dei resti. Rappresentazione di un intero come “vettore” di sue classi di congruenza. Riduzione al caso di moduli coprimi.
Definizione della funzione φ di Eulero. Proprietà della funzione φ. Formula per la funzione φ in base alla fattorizzazione dell’intero n.
Introduzione alla nozione di Gruppo. Gruppo diedrale delle simmetrie di un triangolo equilatero. Simbologia e calcolo.
(Appunti 1.7,1.8 )
Esercizi:
Lezione 9: Definizione di Gruppo. Vari esempi. Gruppi diedrali e gruppi simmetrici. Ordine di un gruppo. Ordine di un elemento. Definizione di gruppo ciclico. Esempi. Generatori di un gruppo ciclico. Sottogruppi. Un sottogrupppo di un gruppo ciclico è ciclico. Gruppo delle radici n-esime di 1.
(Appunti 2.1, 2.2)
Esercizi:
Lezione 10,11: Teorema di Lagrange: dimostrazione e qualche conseguenza. Un gruppo avente ordine p primo è necessariamente ciclico. Se G è un gruppo finiti di ordine n, allora gn=e, per ogni gin G. Dimostrazione del Piccolo Teorema di Fermat come conseguenza del Teorema di Lagrange. Teorema di Eulero, anch’esso conseguenza del Teorema di Lagrange.
Omomorfismi. Nucleo, immagine di un omomorfismo. Iniettività e suriettività di un omomorfismo. Isomorfismo tra gruppi. Teorema di classificazione dei gruppi ciclici. Un particolare esempio di anello: S.
(Appunti 2.3, 2.4)
Esercizi:
Lezione 12: Nozione di campo e anello. Anello di polinomi. L’anello F[x] è euclideo se F è un campo. Divisione tra polinomi. Polinomi irriducibili. Verifica dell’irriducibilità di x4+1 come polinomio a coefficienti in Z3. Introduzione alla classificazione dei campi finiti (campi di Galois).
(Appunti 2.5)
Esercizi.
Lezione 13,14: Caratteristica di un campo. Sottocampo fondamentale. Teorema di classificazione dei campi finiti. Costruzione di campi finiti mediante polinomi irriducibili. Elementi primitivi.
(Appunti 2.6)
Introduzione alla crittografia. Definizione di cifrario. Cifrari classici: Cifrari affini. Cifrari monoalfabetici e polialfabetici. Cifrario di Hill. Cifrario di Vigénère.
(Appunti 3.1)
Esercizi.
Lezione 15: Criptoanalisi del cifrario di Vigénère. Test di Kasiski. Indice di coincidenza di Friedman. Crittografia a chiave pubblica. Metodo RSA.
Esercizi: Criptoanalisi di un testo.
Lezione 16,17: Metodo RSA. Protocollo Diffie-Hellman per lo scambio delle chiavi. Autenticazione delle firme.
[Appunti 3.2, 3.3, 3.4]
Esercizi.
Lezione 18: Esercizi. Ripasso. Metodo di fattorizzazione di Fermat.
Esercizi.
Lezione 19, 20: Esercitazione scritta.
Lezione 21: Introduzione alla teoria dei codici. Codici correttori e rilevatori. Distanza di Hamming. Distanza minima di un codice. Nozione di equivalenza di due codici. Il problema principale della teoria di codici.
[Appunti 4.1, 4.2, 4.3]
Lezione 22, 23: Sfere in Fqn. Disuguaglianza di Hamming. Codici perfetti. Qualche esempio e proprietà di A2(n,d). Codici lineari. Equivalenza di codici lineari. Codice di Hamming di tipo [7,4,3] a partire dal piano di Fano. Il codice di Hamming è perfetto.
[Appunti 4.3, 4.4]
Lezione 24: Distanza minima e peso minimo. Matrice generatrice di un codice lineare. Matrici generatrici di codici equivalenti. Operazioni elementari sulle righe e (alcune) sulle colonne. Matrice generatrice in forma standard. Ogni matrice si può porre in forma standard. Definizione di prodotto scalare su Fqn. Vettori isotropi. Complemento ortogonale di un codice: codice duale.
[Appunti 4.5, 4.6]
Esercizi.
Lezione 25: Matrice di controllo di parità H di un codice. Forma standard di H. Esempi. Sindrome di un vettore. Sindrome di una classe laterale. Decodifica per sindrome.
[Appunti 4.6, 4.7]
Lezione 26, 27: Famiglia di codici di Hamming, 1-correttori e perfetti. Introduzione alla combinatoria. Qualche esempio di problema combinatorio: ricoprimento di un reticolo. Numeri di Fibonacci. Alcune proprietà dei numeri di Fibonacci. Formula di Binet. Funzioni generatrici.
[Appunti 4.8, 5.1, 5.2]
Esercizi.
Lezione 28: Risoluzione di ricorrenze lineari omogenee. Serie formali, prodotto di convoluzione.
[Appunti 5.3, 5.4]
Esercizi.
Lezione 29: Successione dei numeri di Catalan. Ricorrenza quadratica. Funzione generatrice dei numeri di Catalan. Formula chiusa dell’n-esimo numero di Catalan. Triangolazioni di poligoni convessi.
Partizioni di interi. Funzione generatrice delle partizioni di interi. Problema del cambio di monete.
[Appunti 5.5, 6.1]
Esercizi.
Lezione 30, 31: Teorema di Eulero sulle partizioni in parti dispari e in parti distinte.
Coefficienti binomiali: alcune identità. Identità di convoluzione di Vandermonde: dimostrazione analitica e dimostrazione combinatoria.
Definizione di grafo e grafo semplice. Alcuni grafi notevoli: grafi completi, ipercubi, grafi bipartiti. Problema dei ponti di Konigsberg. Teorema di Eulero sui cammini euleriani. Matrice di adiacenza di un grafo.
[Appunti, 7.1, 7.3, 8.1,8.2,8.3, 8.6]
Esercizi.
Lezione 32, 33: Circuiti hamiltoniani. Teorema di Dirac e Torema di Ore. Grafi bipartiti e abbinamenti (matchings). Colorazione di grafi e applicazioni. Handshaking lemma. Esercitazione.
Esercitazione.
 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
(Date degli appelli d'esame)
|
6
|
MAT/03
|
24
|
36
|
-
|
-
|
Attività formative di base
|
ITA |
