Diario delle lezioni di Matematica Discreta 2017

 

Lunedì 20 febbraio 2017

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 da provare:

1.       Se ho due bottiglie di capacità di 2 e 3 litri e voglio riempire un secchio con esattamente n litri di acqua usando le due bottiglie, mi domando se si può fare per qualunque n? oppure solo per alcuni n?

2.       Se le capacità sono 2 e 4?

3.       Se ho capacità h e k (interi), quali n posso ottenere?

4.       Esplorare se sia vero o meno che un numero naturale n è primo se e solo se n divide 2n-2. Per esempio, abbiamo 27-2=126 e 126=18x7, mentre 26-2=62 che non è un multiplo di 6.

5.       Se p1,p2,p3,… sono i numeri primi ordinati in ordine crescente, il numero p1p2p3...pk+1 non è primo in generale. Definiamo una nuova successione di numeri primi così fatta: q1=2, sia q2 il massimo primo che divide q1+1, e quindi q2=3. Sia q3 il massimo primo che divide il numero q1q2+1; sia q4 il massimo primo che divide q1q2q3+1, etc. Verificare che la successione q1,q2,q3,… non è monotona calcolando q9 e q10.  

 

Mercoledì 22 febbraio 2017

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.

1.       Verificare che 257-2 non è divisibile per 57

2.       Verificare che 264-2 non è divisibile per 64

3.       Verificare che 2341-2  è divisibile per 341, pur non essendo 341 primo (341=11x31)

4.       Con riferimento all’esercizio 5 della lezione precedente, verificare che q9=4680225641471129 e q10=1368845206580129

5.       Ascoltare contemporaneamente il suono di una nota da 320 Hz e una da 560 Hz, si dovrebbe percepire anche una nota da 80 Hz.

6.       Esprimere come frazione continua.

 

Lunedì 27 febbraio 2017

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:

1.       Dimostrare che due numeri di Fibonacci successivi sono coprimi

2.       Dimostrare che per ogni intero positivo n maggiore o uguale a 2 abbiamo

Fn-1Fn-Fn-2Fn+1=(-1)n (Suggerimento: usare l’induzione e opportune matrici)

(cf. la “dimostrazione” grafica che 64=65, grazie a E. Marchi per il disegno)

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:

1.       Dimostrare il criterio di divisibilità per 9.

2.       Dimostrare il criterio di divisibilità per 11.

3.       Dimostrare un criterio di divisibilità per 7. (v., ad esempio, criterio per 7)

4.       Determinare le ultime due cifre di 513323. (v. una soluzione)

 

 

Mercoledì 1 marzo 2017

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:

1.       Risolvere la congruenza 3827x  8654 (mod 7)

2.       Inventare una congruenza che abbia almeno 4 soluzioni. Risolverla in dettaglio.

Lunedì 6 marzo 2017

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:

1.       Risolvere il sistema  32126x  123548 (mod 8), 24679x  35714 (mod 9), 751x  923 (mod 7)

2.       Risolvere il sistema x  3 (mod 24), x  3 (mod 18), x  3 (mod 6), x  1 (mod 7), x  3 (mod 8) (R. 435 modulo 504).

3.       Il comandante di un regimento di soldati vuole contare rapidamente gli uomini disponibili nella piazza d’armi. Ordina allora che si dispongano in fila per 2. I soldati eseguono ed un soldato rimane fuori dallo schieramento. Di nuovo, il comandante ordina che si dispongano in fila per 3. In tal modo nessun soldato rimane fuori. Ancora: schierati per 5, due soldati rimangono fuori. Schierati per 7 ne rimangono fuori 5. Schierati per 11 nessuno rimane fuori. Quanti soldati ci sono nella piazza d’armi? (R. 957)

4.       Rappresentare i numeri interi da 1 a 20 come coppie di resti della divisione ordinatamente per 5 e per 4. Quale coppia corrisponde al 7? Quale numero corrisponde alla coppia (3,4)? Quale numero corrisponde al prodotto (3,4)(2,2)? (R.:(2,3), 8,16)

5.       Disegnare una stella a 5 punte partendo da un punto,  senza staccare la penna dal foglio. Verificare che non è possibile farlo per n=6.  Quante stelle essenzialmente diverse esistono per n=7, n=8?

 

Mercoledì 8 marzo 2017

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:

1.       Verificare che Zn è un gruppo rispetto all’addizione.

2.       Verificare che Zn* è un gruppo rispetto alla moltiplicazione.

3.       Elencare tutti i generatori di Z12 .

4.       Elencare tutti i sottogruppi di Z12 .

5.       Scrivere tutte le radici 12-esime dell’unità e verificare che esse costituiscono un gruppo ciclico.

 

Lunedì 13 marzo 2017

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:

1.       Verificare che il gruppo C30 di tutte le radici trentesime dell’unità costituiscono un gruppo isomorfo a Z30.

2.       Determinare le radici trentesime primitive dell’unità. Descrivere tutti i possibili sottogruppi di Z30.

3.       Vedi qui.

 

 

Mercoledì 15 marzo 2017

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: Vedi qui.

 

Lunedì 20 marzo 2017

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: Vedi qui.

Mercoledì 22 marzo 2017

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.

Decrittare il seguente testo:

ILZHSMLRKAMRZAQSCVLGSUQKTAEQEFDVGTLGXOLPIIFEROFSPQLRPLXWWRRVSDHPNOQV

SCUSEIWVWSRMNQLNPEDZGVRIINGYVOCNKAWXCNVYWAFGQEZYYPLRKEINRODZCRZNXI

 

Lunedì 27 marzo 2017

Lezione 16,17: Metodo RSA. Protocollo Diffie-Hellman per lo scambio delle chiavi. Autenticazione delle firme.

[Appunti 3.2, 3.3, 3.4]

Esercizi: 

1.       Supponiamo di aver fissato i due primi p=7, q=13, e di aver scelto eA=11. Criptare il messaggio M=12.

2.       Stessi dati dell’esercizio precedente: decriptare il messaggio C=74.

3.       Ogni gruppo di tre lettere può essere accoppiato con un numero in base 26 e di conseguenza ad un numero (decimale) compreso tra 0 e 17575, dove AAA corrisponde a 0 e ZZZ corrisponde a 17575, in modo tale che ci sia una corrispondenza biunivoca tra i gruppi di tre lettere e questi numeri. Illustrare questo fatto trovando il numero che corrisponde alla parola UVA e trovare il gruppo di lettere che corrisponde al numero 16223. (Risposte: UVA=14066, 16223=XZZ)

4.         Di seguito trovate un testo criptato da decriptare. I parametri pubblici con cui questo testo è stato criptato sono n=18923, e=1261.

14130, 10818, 5594, 3821, 12370, 18360, 476, 2186, 13573, 8549,1085, 18849,

13095,15590, 16148, 16282, 5432,10344, 14234, 8224, 14130, 1357, 13987,

7432, 14694, 476, 2186, 13573, 5042, 16148, 10818, 4180, 8177, 16148, 3515,

17590, 7293, 11006, 15269, 10973, 2854, 4180, 6789, 16526, 7715, 14253,

12298, 14990, 11578, 17645, 8224, 14130, 1357, 5432, 16050, 7451, 14117, 472,

15061, 228, 10818, 16851, 6051, 2136, 5817, 5432, 18758, 4179, 1927, 2557, 2

La decriptazione richiede i seguenti passi:

a.       Fattorizzare n e calcolare φ(n).

b.      Calcolare l’inverso moltiplicativo d di 1261 modulo φ(n).

c.       Decriptare il messaggio elevando ciascun blocco a d modulo n.

d.      Recuperare il messaggio letterale a partire dai corrispondenti numerici ottenuti al passaggio precedente.

 

Mercoledì 29 marzo 2017

Lezione 18: Esercizi. Ripasso. Metodo di fattorizzazione di Fermat.

 

Esercizi:

1.       Illustrare il metodo di fattorizzazione di Fermat per ottenere la fattorizzazione di 23360947609

 

Lunedì 3 aprile 2017

Lezione 19, 20:  Prova di esonero. (I risultati non prima del prossimo lunedì)

 

Mercoledì 5 aprile 2017

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]

 

Lunedì 10 aprile 2017

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]

 

Mercoledì 12 aprile 2017

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:  

1.       Scrivere una matrice generatrice del codice di Hamming di tipo [7,4,3]. Trasformarla in forma standard.

2.       Scrivere un codice lineare di ripetizione su F4. Elencare tutti i vettori di questo codice.

3.       Scrivere una matrice generatrice del codice lineare binario in F25 definito dall’equazione x1+ x2+ x3+ x4+ x5=0.

4.       Calcolare il codice duale del codice C={00000,01101,10110,11011}.

 

Lunedì 17 aprile 2017

Pasquetta (vacanza)

 

Mercoledì 19 aprile 2017

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]

 

Lunedì 24 aprile 2017

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:

1.       Considerare il codice di ripetizione su F5 di lunghezza 3: C={000,111,222,333,444}. Ha matrice generatrice G=(111). Calcolare la matrice H.  Quante classi laterali ci sono?  Calcolare la sindrome di qualche classe laterale. Mostrare come funziona la decodifica per sindrome applicandola alla parola 224.

2.       Calcolare il codice Ham(2,5): trovare la matrice generatrice e verificare che è un codice perfetto.

3.       Dimostrare che la somma dei quadrati dei numeri di  Fibonacci consecutivi dal primo al k-esimo è uguale al prodotto di due Fibonacci consecutivi.

 

Mercoledì 26 aprile 2017

Lezione 28: Risoluzione di ricorrenze lineari omogenee. Serie formali, prodotto di convoluzione.

[Appunti 5.3, 5.4]

Esercizi:

1.       Fissato k intero positivo, contare quante soluzioni intere, non negative, esistono dell’equazione x1+x2+…+xk=n, al variare di n intero non negativo.

2.       Detto hn il numero dell’esercizio precedente, determinare la funzione generatrice della successione (hn).

3.       Scrivere la funzione generatrice della successione dei quadrati 1,4,9,16,25,36,…

 

Lunedì 1 maggio 2017

Festa del Lavoro (vacanza)

 

Mercoledì 3 maggio 2017

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:

1.       Supponiamo di avere due 1 e due -1 e di disporli in tutte le possibili maniere:

1,1,-1,-1

-1,-1,1,1

-1,1,-1,1

1,-1,1,-1

1,-1,-1,1

-1,1,1,-1

Per ciascuna di queste disposizioni, calcoliamo le somme parziali. Rispettivamente abbiamo

1,2,1,0

-1,-2,-1,0

-1,0,-1,0

1,0,1,0

1,0,-1,0

-1,0,1,0

Ci sono solo due successioni in cui le somme parziali non sono mai negative.

Domanda: se abbiamo tre 1 e tre -1, quante sono le disposizioni in cui le somme parziali non sono mai negative?

Indovinare una formula generale nel caso di n copie di 1 e n copie di -1. Come dimostrarla?

2.       Calcolare (1+q+q2+q3+q4) (1+q2+q4+q6+q8) (1+q3+q6+q9+q12). Riconoscere che il coefficiente di qn nel prodotto è proprio uguale al numero di modi di scrivere n come somma di 1,2,3 ma con non più di quattro 1, non più di quattro 2 e non più di quattro 3.

Per esempio, le partizioni di 5 sono le seguenti sette:

5

4+1

3+2

3+1+1

2+2+1

2+1+1+1

1+1+1+1+1

Tuttavia, le prime due usano interi diversi dai richiesti 1,2,3 e l’ultima usa più di quattro 1, in accordo con lo sviluppo

(1+q+q2+q3+q4) (1+q2+q4+q6+q8) (1+q3+q6+q9+q12)=1+q+2q2+3q3+4q4+4q5+6q6+6q7+7q8+8q9+8q10+8q11+…

Quante partizioni di 9 esistono di questo tipo?

Avviso: ai fini dell'assicurazione della qualità dei corsi di studio, come prescritto dalle indicazioni contenute nel sistema di Autovalutazione, Valutazione e Accreditamento (AVA),  gli studenti, devono compilare il "Questionario on line delle opinioni studenti ", quando il corso ha raggiunto i 2/3 del suo sviluppo. 
A tal fine si chiede al Centro InfoSapienza di attivare le procedure telematiche per la Rilevazione Opinioni Studenti sugli insegnamenti del secondo semestre per l'a.a. 2016-2017. La rilevazione riguarda tutti gli insegnamenti che si concluderanno con un esame o una prova di idoneità. L'accesso ai questionari degli insegnamenti del secondo semestre resterà aperto fino al 28 febbraio 2018. 
Si raccomanda vivamente affinché gli studenti frequentanti siano efficacemente sollecitati a pronunciarsi sugli insegnamenti seguiti, in primo luogo dai docenti nel corso delle lezioni, una volta completata la metà o i due terzi delle lezioni e comunque prima della loro fine. 
…

Al fine di una maggiore efficacia comunicativa, si raccomanda a Facoltà e/o Dipartimenti di: 
- segnalare anche nei siti web l'avvio della Rilevazione Opinioni Studenti 2016-2017 per gli insegnamenti del secondo semestre; 
- sollecitare i docenti a fornire agli studenti indicazioni per compilare i questionari online e a informarli sull'importanza dell'iniziativa e sulle garanzie di anonimato.  

lunedì 8 maggio 2017

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

lunedì 15 maggio 2017

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.

Mercoledì 18 maggio 2017

Esercitazione.

 

lunedì 22 maggio 2017

                Compito

venerdì 26 maggio 2017: correzione in corso.

lunedì 29 maggio 2017: Correzione terminata. Risultati buoni. Complimenti a tutti. La verbalizzazione avverrà in orario e data da stabilirsi dopo la prova scritta del 6 giugno. Il compito può essere visionato in orario di ricevimento (il martedì a partire dalle 14:30 o su appuntamento). Qui di seguito l’elenco.

Gli studenti di Matematica Discreta sono invitati per la verbalizzazione presso lo studio del docente martedì 13 giugno alle ore 11 (Via Scarpa 10) compresi i tre del seguente avviso: Risultati della prova di Matematica discreta

 

Gli appelli d’esame sono fissati per martedì 6 giugno ore 14 in aula 12 di Via Scarpa e venerdì 7 luglio ore 14 aula 13 di Via Scarpa.

Le prenotazioni per l’appello di giugno sono aperte e chiuderanno qualche giorno prima del 6.