|
Registro delle lezioni Matematica Discreta, F. Battaglia,
Anno Accademico 2018-19
Indico con s.d. i risultati enunciati senza dimostrazione.
- 24.09.18 (ore 2).
Introduzione al corso: informazioni pratiche; illustrazione dettagliata del programma e motivazioni.
Definizione di gruppo, anello, campo. Esempi.
Per approfondimenti:
algoritmo RSA
e anche
elliptic curve cryptography;
elementary theory and practice of elliptic curves cryptography,
the new generation of public key systems.
Vedere anche la sezione 4.1 qui
At risk - Public key encryption.
- 25.09.18 (ore 3).
Teorema della divisione. Definizione della relazione di congruenza e relative proprieta', ogni intero e' congruo
al suo resto modulo n; due interi sono congrui modulo n se e solo se hanno lo stesso
resto quando divisi per n. Somma e prodotto conservano la congruenza.
L'importante identita' [xy]d=[[x]d[y]d]d con x,y numeri interi. Algoritmo dei quadrati ripetuti.
Definizione dell'anello, Z/nZ, delle classi di resto modulo n. Esempi.
- 1.10.2018 (ore 2)
Z/nZ non e' un campo se n non e' primo.
Sia div(n) l'insieme dei divisori di un intero n. Nota: div(0)={0,1,2,3,...}=N. Lemma di Euclide (Euclide (300 a.C.):
Siano m,n in Z. Allora esiste unico d in N tale che div(m) intersecato div(n) e' uguale a div(d).
Definizione di massimo comun divisore tra due numeri interi.
Algoritmo di Euclide per il calcolo del massimo comun divisore.
Proposizione: il massimo comun divisore di due interi a e b si puo' scrivere come combinazione lineare intera di a e b: algoritmo Euclideo esteso per la dimostrazione e il
calcolo dei coefficienti della combinazione lineare.
- 2.10.2018 (ore 3)
Proposizione: Due interi a e b sono co-primi se e solo esistono
x e y interi tali che xa+yb=1.
Definizione di (Z/nZ)* come sottoinsieme di Z/nZ delle classi prime con n. (Z/nZ)*
e' un gruppo, il gruppo degli elementi invertibili dell'anello Z/nZ.
In particolare, si ha la
Proposizione: l'anello delle classi di resto Z/nZ e' un campo se e solo se n e' un numero primo.
Proposizione: siano a,b,c interi.
Se a divide bc e a e b sono primi tra loro, allora a divide c.
Proposizione: siano a,b,c interi.
Se gcd(a,b)=1, a divide c e b divide c, allora ab divide c;
Se gcd(a,b)=1 e gcd(a,c)=1 allora gcd(a,bc)=1.
Teorema cinese del resto (Sun-Tsu 280-473, Chin Chiu Shao 1247) :
esistenza e unicita' della soluzione di un sistema di congruenze, che
soddisfi le opportune ipotesi. Dimostrazione unicita'.
Dimostrazione costruttiva dell'esistenza di una soluzione basata sull'algoritmo euclideo esteso.
Il teorema cinese del resto e' equivalente alla
Proposizione: L'applicazione resto r da Z/nZ a Z/n1Z x ... Z/nrZ, con
n=n1...nr e gcd(ni,nj)=1 è un isomorfismo di anelli.
Esempio di applicazione del teorema cinese del resto: esempio semplice di uno schema di condivisione di un segreto
(secret sharing scheme). Questi schemi sono stati introdotti indipendentemente da
A. Shamir e G. R. Blakley nel 1979.
Per approfondimenti:
Secret sharing.
- 8.10.2018 (ore 2)
Dimostrazione della proposizione enunciata nella lezione precedente.
Definizione della funzione φ di Eulero (1707-1783).
Proposizione: Se n e m sono primi tra loro, allora φ(mn)=φ(m)φ(n).
Teorema di Eulero: siano a,n interi, primi tra loro, n naturale. Allora aφ(n)≡ 1(mod n).
Corollario: il piccolo teorema di Fermat.
- 9.10.2018 (ore 3)
Algoritmo RSA in dettaglio, in particolare come si determina la chiave privata.
Numeri primi, numeri di Mersenne.
Definizione di numero primo; Lemma: ogni naturale non nullo e' prodotto di primi; Teorema (Euclide): ci sono
infiniti numeri primi; Lemma: se un primo divide il prodotto di due interi, allora divide almeno uno dei fattori. Teorema: ogni naturale non nullo si scompone univocamente (a meno dell'ordine) nel prodotto di numeri
primi (s.d.)
Introduzione alla teoria della complessita' computazionale. Problemi decisionali e algoritmi di risoluzione. Esempi:
il problema dell'esistenza di un circuito Euleriano in un grafo assegnato e teorema di Eulero. Il problema dell'esistenza di un
circuito Hamiltoniano in un grafo assegnato. Il problema del commesso viaggiatore (Travelng Salesman Problem): esistenza di un
circuito Hamiltoniano in budget in un grafo pesato assegnato, con budget assegnato.
Per approfondimenti:
Twenty years of attacks on the RSA cryptosystem
di Dan Boneh.
The largest known primes- a summary,
Great internet Mersenne prime search,
Risultato
del 2013 sul primes gap, articolo divulgativo,
Risultato del 2013 sul primes gap, articolo originale
- 15.10.2018 (ore 2)
Il problema della soddisfacibilita' delle formule Booleane AND of OR's. Il problema della primalita'.
La macchina di Turing.
Cenno a due delle ipotesi principali alla base della teoria
della complessita' computazionale: la Church-Turing thesis e la Cobham-Edmonds thesis.
Definizione:
Un linguaggio L e' l'insieme di tutti gli oggetti per cui la risposta a un dato problema decisionale
e' si'.
Esempi:
LEC=insieme dei grafi connessi che ammettono un circuito Euleriano
LHC=insieme dei grafi connessi che ammettono un circuito Hamiltoniano
LTSP=insieme di coppie (G,B) con G grafo connesso pesato e B numero positivo tali che G
ammette un circuito Hamiltoniano con costo inferiore a B
LSAT=insieme delle formule Booleane AND of OR's soddisfacibili
LPr=insieme dei numeri primi
Definizione delle seguenti nozioni:
una macchina di Turing T accetta un linguaggio L;
un linguaggio L appartiene alla classe di complessita' computazionale P;
un linguaggio L appartiene alla classe di complessita' computazionale NP,
comprendente la nozione di testimone o certificato.
Brevemente P e' la classe dei linguaggi per cui, per ogni input, l'appartenenza o meno al linguaggio puo' essere
decisa in tempo polinomiale nella taglia dell'input.
NP e' la classe dei linguaggi per cui, per ogni input nel linguaggio, la prova di appartenenza
puo' essere verificata in tempo polinomiale nella taglia dell'input.
Per approfondimenti:
A walk through combinatorics, Miklos Bona, sia la seconda che la terza edizione contengono
capitoli sulla teoria della complessita' e una descrizione
chiara della macchina di Turing (cap. 17 e 18).
Notes on Turing machine,
L'articolo originale in cui Turing introdusse la macchina di Turing
On computable numbers, with an application to the Entscheidungsproblem A. Turing,
Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937).
Turing and the development of computational complexity di S. Homer e A. Selman (2011),
dove vengono illustrate anche le ipotesi di cui sopra.
Definizione di formula Booleana AND of OR's.
Il materiale utilizzato per l'introduzione alla teoria della complessita' comprende anche la:
Conferenza di Vijaya Ramachandran: P vs NP problem, tenuta
al Clay Mathematics Institute, molto chiara.
Per la teoria dei grafi vedere, ad esempio:
Corso di teoria dei grafi, Carlo Casolo e il libro di Bona succitato.
M. Agrawal, N. Kayal, N. Saxena, Primes is in P, Annals of Mathematics,
160 (2004) 781-793: We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.
Un articolo molto bello sul risultato precedente, di A. Graville, sul Bull. of AMS. Per la teoria della complessita' vedere anche ad esempio:
il libro
Computational Complexity: A Modern Approach Sanjeev Arora and Boaz Barak, Cambridge University Press. E, in relazione con l'RSA, l'articolo
Complexity theory and the RSA cryptosystem
J. Garlapati.
Il certificato di Pratt.
Gli articoli originali di Cook e Levine (indipendenti) sulla NP-completezza di SAT:
S. Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM
Symposium on Theory of Computing, (1971) pp. 151-158. L. Levin, Universal search problems (in russo),
Problems of Information Transmission, 9 (3):
(1973) 115-116, translated into English by Trakhtenbrot, B. A. A survey of Russian approaches to perebor
(brute-force searches) algorithms, Annals of the History of Computing 6 (4) (1984).
- 16.10.2018 (3 ore)
Dati due linguaggi L ed L' definiamo quando L e' riconducibile ad L', L≤pL'.
Definizione di NP completezza.
Teorema (Cook, 1961): LSAT e' NP completo. Proposizione: Se L e' NP completo e L≤pL', allora
L' e' NP completo. Ad ora si conoscono migliaia di linguaggi NP completi.
Altri esempi di linguaggi NP completi: LHC e LTSP.
P=NP se e solo se un linguaggio NP completo e' in P (segue dalla definizione di NP completezza).
Costruzione, in analogia con l'anello delle classi di resto modulo n, del
campo dei numeri complessi C come R[x]/x2+1.
POLINOMI: L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A.
Grado di un polinomio. Siano f,g sono in K[x], allora
deg(fg)=def(f)+deg(g). Gli elementi invertibili di K[x] sono tutti e soli i polinomi costanti non nulli.
Teorema della divisione:Sia d un polinomio a coefficienti in un anello A, diverso
da 0 e tale che il coefficiente del monomio di grado massimo e' invertibile. Allora, dato f in A[x], esistono unici q e r in A[x]
tali che f=qd+r, con deg(r)< deg(d) o r=0.
Definizione di radice di un polinomio. Denotiamo con V(p) l'insieme delle radici del polinomio p. Un elemento a in
K e' una radice del polinomio p se e solo se (x-a) divide p. Definizione di molteplicita', νa(p)
di una radice a del polinomio p.
Si ha
V(fg)=V(f)UV(g). Teorema: Sia F in
K[x]. Se V(f)={a1,...,ar} allora
f=q(x-a1)νa1(p)...(x-ar)νar(p), con q in K[x] e V(q) vuoto.
Inoltre νa1+...+νar≤deg(f).
Derivata di un polinomio e sue proprietà .
Lemma: Siano f,g due polinomi in K[x]. Se f2
divide g, allora f divide Dg;
l'elemento a in K e' una radice del polinomio f con molteplicità maggiore
di 1 se e solo se e' una radice di f e di Df.
Definizione d radice n-esima di 1 in un campo K. Definizione di radice primitiva n-esima di 1 in un campo K.
- 22.10.2018 (ore 2)
Radici n-esime di 1 nel campo dei complessi C: definizione, radici n-esime primitive di 1 in C (caratterizzazione e proprieta').
L'insieme delle radici n-esime di 1 in C e' un gruppo ciclico, ogni radice n-esima primitiva e' un generatore di tale gruppo.
Definizione dei polinomi ciclotomici. Esempi. Dimostrazione della prima proprieta' dei polinomi ciclotomici.
- 23.10.2018 (ore 3)
Dimostrazione della seconda proprieta' dei polinomi ciclotomici. Definizione di
caratteristica di un campo. Polinomi ciclotomici in un campo K qualunque.
Criterio per stabilire se una radice n-esima di 1 in un campo K e' n-esima primitiva.
Sia G un gruppo commutativo e H un sottogruppo, definizione di classi laterali e del gruppo quoziente G/H.
Sia G un gruppo e g un suo elemento. Definizione di ordine di g, ord(g). Proposizione: Sia G un gruppo finito, allora
ord(g) divide |G|, g|G|=e, se gn=e allora ord(g) divide n.
Teorema di Gauss: un sottogruppo finito del gruppo moltiplicativo di un campo e' ciclico.
Cenno al problema del logaritmo discreto.
Per approfondimenti:
Articolo sui problemi del logaritmo discreto e della fattorizzazione in
primi, risultati recenti sugli algoritmi di risoluzione di Pierrick Gaudry.
Algorithms for Quantum Computation:
Discrete Logarithms and Factoring di Peter W. Shor.
- 29.10.2018 (ore 2).
Definzione di ideale e di ideale principale. Definizione di polinomio irriducibile.
Proposizione: Se f in K[x] ha grado 1 allora e' irriducibile.
se f e' irriducibile in K[x] e grado di f >1 allora f non ha radici
se f ha grado 2 o 3 e non ha radici in K allora e' irriducibile in K[x]
Definizione del quoziente Fp[x]/< f >: identificazione con le classi dei resti modulo f, cardinalita' (pn)
e struttura di anello.
Fp[x]/< f > e' un campo se e solo se f e' irriducibile in Fp[x].
Fp e' un sottocampo di L:=Fp[x]/< f >
Il polinomio f e' in Fp[x] e quindi in L[x]. L'elemento [x] in L e' una radice di f. Abbiamo dunque costruito
una estensione di Fp a un campo L in cui f e' riducibile.
Esempi di campi con 9 e 27 elementi.
- 30.10.2018 (ore 3)
Proposizione: sia F un campo finito, allora esistono p primo ed f polinomio irriducibile in Fp[x] tali che
F e' isomorfo a Fp[x]/< f >.
Conseguenza: ogni campo finito F ha cardinalita' uguale alla potenza di un primo. Questo primo e' la caratteristica del
campo.
Teorema di esistenza e unicita': dati un primo p e un intero n positivo
esiste un campo F con pn elementi. Il campo F e' unico a meno di isomorfismi. Se q=pn denotiamo con
Fq tale campo. Dimostriamo prima l'esistenza. Enunciato*:
sia f un fattore irriducibile in Fp[x] del
polinomio ciclotomico phipn-1, allora il grado di f e' uguale a n. (*) implica la parte di
esistenza del teorema. Per la dimostrazione occorre un lemma tecnico di cui omettiamo la semplice dimostrazione:
siano r,s,t naturali con r>1, allora rs-1 divide rt-1 se e solo se s divide t.
Omettiamo per brevita' la dimostrazione della parte di unicita', abbiamo comunque tutti gli elementi per capirla
Introduzione all'algoritmo di Berlekamp.
- 5.11.2018 (ore 2)
Mappa di Frobenius, condizioni necessarie e sufficienti per l'irriducibilita' di un polinomio in Fp[x],
algoritmo di Berlekamp.La seconda parte del teorema, ossia la sufficienza, e' stata solo delineata e non svolta in tutti i dettagli
- 6.11.2018 (ore 3)
Teoria dei codici autocorrettivi.
Teoria dei codici: definizioni preliminari: alfabeto di taglia/cardinalita' q, parola q-aria, codice q-ario di lunghezza n,
taglia o cardinalita' M di un codice, codici di tipo (n,M)q, information rate di un codice.
Canale di comunicazione: e' dato da un alfabeto (diamo la definizione con lo stesso alfabeto in entrata e in uscita)
e da una matrice di probabilita' di trasmissione in avanti. Canale senza memoria. Canale simmetrico. Canale fortemente
simmetrico. BSC=binary simmetric channel.
Distanza di Hamming: definizione e proprieta'. Distanza d(x,C) di una parola w in An da un codice C. Decodifica a minima distanza. Proposizione: la decodfica a minima distanza e la decodifica a massima probabilita' coincidono quando il canale
e' senza memoria e fortemente simmetrico. Distanza di Hamming di un codice.
Definizione di sfera aperta e chiusa di centro x e raggio s, denotate
(in questo registro) rispettivamente con Bs(x) e
Bs(x).
Un codice C segnala al piu' s errori in se, per ogni x in C,
Bs(x)∩C={x}.
Teorema: un codice C segnala al piu' s errori se e solo se d(C)≥s+1
- 12.11.2018 (ore 2)
Un codice corregge al piu' s errori se per ogni parola w in An tale che d(w,C) minore o uguale a s si ha
che esiste un'unica parola c in C tale che w appartiene a Bs(c).
Teorema: un codice C corregge al piu'
s errori se e solo se d(C)≥2s+1.
Lemma: sia C un codice.
Allora d(C)≥2s+1 se e solo se per ogni c e c' in C, con c diversa da c', si ha
Bs(c)∩Bs(c')=vuoto.
Il Teorema di Hamming. Questo risultato da una limitazione superiore esplicita per la taglia
M di un codice in funzione di n,d,q.
Lemma: numero di parole in una palla chiusa di raggio r.
Dimostrazione del teorema di Hamming. Definizione di codice perfetto.
Teoria dei codici lineari: definizione di codice lineare. Dimensione di un codice lineare. Esempio: codice di ripetizione.
Per approfondimenti:
"probably no single work in this century has more profoundly altered man's understanding of communication than Shannon's
1948 paper A mathemathical theory of communication" (David Slepian (editor) in Key papers in the Development of Information Theory, IEEE Press, NY, 1974).
- 13.11.2018 (ore 2.30)
Prodotto scalare in Fqn.
Definizione di ortogonale di un codice C. Proprieta'. Definizione di matrice generatrice G e matrice di controllo di parita' H
di un codice lineare C: sia dim(C)=k, allora G e' una matrice
le cui righe costituiscono una base di C (dunque rango(G)=k), mentre H e' una matrice le cui righe costituiscono una base
dell'ortogonale di C (dunque rango(H)=n-k).
Proposizione: x in Fqn appartiene a C se e solo se
Hxt=0;
x in Fqn appartiene all'ortogonale di C se e solo se
Gxt=0;
una matrice H' M(n-k),n(Fq) di rango n-k e' una matrice di controllo di parita' di C
se e solo se G(H')t=0; una matrice G' Mk,n(Fq) di rango k e' una matrice
generatrice di C se e solo se H(G')t=0;
si ha C=Ker(H)={x in Fqn | Hxt=0} e C={xG | x in Fqk}.
Peso di Hamming di una parola x in Fqn, denotato con wt(x). Peso di Hamming, wt(C), di un codice C.
Proposizione: per un codice lineare C si ha d(C)=wt(C).
Calcolo della distanza mediante la matrice di controllo di parita' H. Proposizione: sia C un codice lineare e sia H una sua matrice di controllo di parita'. Allora si ha:
1) d(C) maggiore o uguale a l se e solo se ogni (l-1) colonne di H sono linearmente indipendenti.
2) d(C) minore o uguale a l se e solo se esistono l colonne di H linearmente dipendenti
3) d(C)=l se e solo se ogni (l-1) colonne di H sono linearmente indipendenti ed esistono l colonne di H linearmente dipendenti.
- 19.11.2018 (ore 2)
Codici equivalenti. Definizione di GP(n,Fq): gruppo delle permutazioni generalizzate. Proposizione:
il gruppo delle permutazioni generalizzate coincide con il sottogruppo degli isomorfismi di Fqn che conservano
il peso.
Definizione: due codici lineari C e C' in Fqn si dicono equivalenti se esiste
f: Fqn ---> Fqn in GP(n,Fq) tale che
f(C)=C'.
Teorema (Florence MacWlliams) Siano C e C' due
codici linearin in Fqn, se C e C' sono isometrici, ossia, se esiste f:C--->C'
isomorfismo che conserva la distanza, allora esiste una permutazione generalizzata di
Fqn che ristretta a C concide con f, in particolare C e C' sono equivalenti. S.D. Per una dimostrazione vedi
qui, il pdf e' disponibile.
Osservazione: due codici sono equivalenti se e solo se sono isometrici.
Osservazione: due codici equivalenti hanno la stessa distanza.
La matrice generatrice G di un codice si dice in forma standard se G=(Ik|X).
La matrice di controllo di parita' H di un codice si dice in forma standard se H=(X|In-k).
Proposizione: Sia G=(Ik|X) matrice generatrice di un codice C in forma standard, allora la matrice H=(-Xt|In-k)
e' una matrice di controllo di parita' per C.
Teorema: ogni codice lineare C e' equivalente a un codice C' che ammette una matrice generatrice in forma standard.
Dim: applicare la riduzione di Gauss ("per ogni riga all'avanti e all'indietro") e poi eventualmente operare sulle colonne.
- 20.11.2018 (ore 3)
Processo di codifica per un codice lineare utilizzando una matrice generatrice in forma standard.
Message digits, check digits.
Processo di decodifica a minima distanza (DmD) per un codice lineare.
Sia C un codice lineare in
Fqn di dimensione k. Si considera lo spazio vettoriale quoziente Fqn/C.
Tale spazio ha dimensione n-k e ha dunque qn-k elementi, ognuno di questi e', come sappiamo, una
classe laterale (coset).
Nozione di capoclasse (coset leader).
Tabella standard e decodifica.
Sia C un codice lineare [n,k,d]q, con matrice di controllo di parita' H. Definiamo l'applicazione lineare, detta sindrome, SH:Fqn--->Fqn-k
come SH(w)=(Hwt)t. La parola SH(w) si dice sindrome di w.
L'applicazione lineare SH e' suriettiva, il suo nucleo e' C.
Proposizione: L'applicazione SH induce un'isomorfismo da Fqn/C in Fqn-k.
Costruzione della tabella delle sindromi e decodifica a sindrome.
La sindrome e' iniettiva sulla palla di centro 0 e raggio e, questo implica una semplificazione nella costruzione della tabella delle sindromi.
26.11.2018 (ore 2)
Codici ciclici: teorema di classificazione dei codici ciclici; matrice generatrice di un codice ciclico a partire dal suo polinomio
generatore.
- 27.11.2018 (ore 3)
matrice generatrice di un codice ciclico a partire dal suo polinomio
generatore e relazione tra grado del polinomio generatore e dimensione del codice. Esempi. Codici ciclici equivalenti.
Polinomio reciproco. Polinomio generatore del codice ortogonale, anch'esso ciclico (da rivedere).
Matrice di controllo di partita' di un codice ciclico, forma canonica per la matrice di controllo di parita' di un codice ciclico.
Decodifica col resto, primi esempi.
- 3.12.2018 (ore 2)
Algoritmo di decofifica per codici ciclici di errori con una sequenza
ciclica di zeri sufficientemente lunga. Esempio.
Introduzione ai "bounds".
- 4.12.2018 (ore 3)
Sphere covering bound; Singleton bound, anche per codici lineari. Il bound di Gilbert-Varshamov. I codici di Reed-Solomon (definizione come codici ciclici). I codici di Reed-Solomon verificano
il Singleton bound. Bounds asintotici. Versione asintotica del bound di Gilbert-Varshamov, cenno
ai risultati di Goppa e Tfsasman-Vladut-Zink.
Approfondimenti: l'introduzione del seguente articolo
di M. Cheraghchi,
A. Shokrollahi, A. Wigderson
presenta in modo
preciso ed estremamente chiaro i bounds e cosa significa costruire codici con parametri estremali, anche per bounds
asintotici:
Computational Hardness and Explicit Constructions of
Error Correcting Codes
.
Nelle seguenti
note di Y. Lindell si trova il passaggio dal bound
di Gilbert-Varshamov alla sua versione asintotica, con notazioni compatibili con quelle del libro di testo.
In questa pagina si trova l'aggioramento continuo dei bounds sui
parametri di vari tipi di codici, la pagina e' esaustiva.
Note sintetiche con approfondimenti rispetto a quanto trattato a lezione.
- 10.12.2018 (ore 2)
Esercizi di riepilogo sulla teoria dei codici autocorrettivi.
- 11.12.2018 (ore 1:30)
Breve introduzione alla quantum computation.
Approfondimenti: testi utilizzati per la lezione
Quantum computation and quantum information, Nielsen, Chuang, Cambridge University Press, 2000;
Classical and quantum computation, Kitaev, Shen, Vyalyi, GTM 47, AMS 1999.
|