Indico con s.d. i risultati enunciati senza dimostrazione.

1. 23.09.12 (ore 2).
   Introduzione al corso: informazioni pratiche, programma, motivazioni, collegamenti, testi di riferimento.
   Introduzione al sistema crittografico RSA-- sistema di crittografia a chiave pubblica--per la trasmissione di dati. Essenzialmente le chiavi pubbliche sono un numero naturale N (prodotto di due numeri primi molto grandi) e un numero naturale e scelto opportunamente; la chiave privata e' un altro numero d, segreto, che si utilizza per la decrittazione. Per iniziare a curiosare: 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.
   Teoria dei codici: si spiega, attraverso alcuni esempi banali, di cosa si occupa la teoria dei codici autocorrettivi e cosa significa autocorrettivo. Distanza di Hamming ed esempi di decodifica a minima distanza. Come aumentare l'efficienza di correzione a scapito della velocita' di trasmissione (ridondanza dei dati).

2. 26.09.12 (ore 3).
   Numeri naturali, numeri interi, definizione di gruppo, gruppo commutativo, anello, anello commutativo, campo. Esempi, tra cui F₂. Divisione con resto (teorema s.d.). Definizione di divisore. Congruenze: definizione di congruenza modulo un intero positivo d. La congruenza e' una relazione di equivalenza. Ogni numero e' congruo, modulo d, al suo resto quando viene diviso per d. Due numeri sono congrui tra loro modulo d se e solo se hanno lo stesso resto quando vengono divisi per d. La congruenza conserva somma e prodotto. L'insieme delle classi di resto modulo d e' un anello commutativo con d elementi. Esempi e relative tabelle additive e moltiplicative. L'importante identita' [xy]_d=[[x]_d[y]_d]_d con x,y numeri interi. Su questa si basa l'algoritmo dei quadrati ripetuti per calcolare il resto con dividendi molto grandi. Esempio svolto: calcolo del resto della divisione di 1211 per 21. Sia div(n) l'insieme dei divisori di un intero n. Nota che div(0)={0,1,2,3,...}=N Lemma (Euclide): Siano m,n in Z. Allora esiste unico d in N tale che div(m) intersecato div(n) e' uguale a div(d). Dimostrazione unicita'.
3. 30.09.2013 (ore 2)
   Massimo comun divisore: esistenza e unicita' (Lemma di Euclide (Euclide (300 a.C.))). Algoritmo Euclideo (Euclide (300 a.C.)) per determinare il massimo comun divisore, gcd(m,n), tra due interi m e n. Algoritmo Euclideo esteso per determinare interi x e y tali che xm+yn=gcd(m,n). Definizione: m e n sono primi tra loro se gcd(m,n)=1.
4. 03.10.2013 (ore 3).
   Proposizione: m e n sono primi tra loro se e solo se esistono x e y tali che xm+yn=1.
   Proposizione: Se a divide bc e a e b sono primi tra loro, allora a divide c.
   Proposizioni: 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: l'applicazione resto r da Z/NZ a Z/n₁Z x ... Z/n_rZ, con n=n₁...n_r e gcd(n_i,n_j)=1 è biunivoca (è infatti un isomorfismo di anelli (dimostrata solo la biunivocita').
   Dimostrazione del teorema cinese del resto mediante algoritmo esplicito per determinare una soluzione, basato sull'algoritmo euclideo esteso. Esempio di applicazione del teorema cinese del resto: caso semplice del Shamir secret sharing.
   Per iniziare a curiosare: Secret sharing.
   Definizione della funzione φ di Eulero (1707-1783) sui naturali.
5. 07.10.2013 (ore 2).
   Proposizione: Se n e m sono primi tra loro, allora φ(mn)=φ(m)φ(n).
   (Z/nZ)^* e' un gruppo, il gruppo degli invertibili dell'anello Z/nZ. Z/nZ e' un campo se e solo se n e' primo. Teorema di Eulero: siano a,n interi primi tra loro, n naturale. Allora a^φ(n)≡ 1(mod n).
   Algoritmo RSA in dettaglio.
6. 10.10.2013 (ore 3) Algoritmo RSA in dettaglio (continuazione).
   Numeri primi: definizione; crivello di Eratostene; Lemma: ogni naturale non nullo e' prodotto di primi; Teorema (Euclide): ci sono infiniti numeri primi; Lemma: se un primo p divide il prodotto di due interi ab, allora o p divide a oppure o divide b. Teorema: ogni naturale non nullo si scompone univocamente (a meno dell'ordine) nel prodotto di numeri primi; massimo comun divisore e minimo comune multiplo a partire dalla scomposizione in fattori primi; il calcolo della funzione di Eulero nota la scomposizione in fattori primi di un naturale.
   Introduzione alla teoria della complessita' computazionale: definizione grossolana di algoritmo, algoritmi polinomiali. Diciamo che un problema e' facile (feasible) se e solo se ammette un algoritmo polinomiale (The Cobham-Edmond thesis (1964-65)). Diciamo che un problema e' non trattabile (intractable) se NON ammette un algoritmo polinomiale. Differenza qualitativa tra algoritmi polinomiali ed esponenziali. Esempio di problema decisionale: determinare se un grafo ammette un circuito Euleriano.

   Tra il materiale utilizzato per l'introduzione alla teoria della complessita' : Conferenza di Vijaya Ramachandran: P vs NP problem, tenuta al Clay Mathematics Institute e i capitoli 17 e 18 del libro A walk through combinatorics, Miklos Bona, sia la seconda che la terza edizione contengono i capitoli sulla teoria della complessita'.
   Per la teoria dei grafi vedere, ad esempio: Corso di teoria dei grafi, Carlo Casolo e il libro di Bona succitato.

   Per iniziare a curiosare: The largest known primes; Great internet Mersenne (1588-1648) prime search; a brief survey of integer factorization algorithms; Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1995) ; 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. Un survey interessante Numbers at work and Play, IE Shparlinski pubblicato nel volume AMS Notices, Febuary 2010 Volume 57 Issue 03 tutto dedicato alla crittografia. Ancora sull'algoritmo di Shor: The Mathematics Behind Quantum Computing: Part I Part II ; The discovery of the Pentium division flaw, from Thomas Nicely home page; Randomness and pseudorandomnes, di Avi Wigderson, scarica il file Summer 2009 da qui

7. 14.10.2013 (ore 2)
   Definizione di problema decisionale. Il problema del circuito di Eulero e' decisionale. Enunciato del teorema di Eulero: un grafo connesso ha un circuito Euleriano se e solo se tutti i suoi nodi hanno grado pari. Questo ci permette di affermare che esiste un algoritmo che esegue in tempo polinomiale (infatti O(n)) che risolve il problema del circuito di Eulero. Altri esempi di problemi decisionali (rimetto nella lista anche quello del circuito Euleriano):
   CE: problema del circuito Euleriano Pr: un numero intero assegnato e' primo?
   SAT: problema di soddisfacibilita' di formule booleane "and of or's" (forma normale congiuntiva (CNF))
   HC: problema del circuito Hamiltoniano; TSP: problema del commesso viaggiatore (circuito Hamiltoniano con peso minore di un peso assegnato.
   Cenno alla macchina di Turing per misurare l'efficienza di un algoritmo. Un passo e' un movimento della testina, il tempo di esecuzione e' il numero di passi.
   Un linguaggio L e' l'insieme di tutti gli oggetti per cui la risposta a un dato problema e' SI'. Con riferimento ai problemi succitati avremo: L_CE, L_Pr, L_SAT, L_HC, L_TSP.
   Una macchina di Turing T accetta il linguaggio L se dato un input x, T si ferma nello stato SI' se x e' in L e T si ferma nello stato NO se x NON e' in L.
   Classe di complessita' P (polinomiale): Un linguaggio L e' in P se esistono una macchina di Turing T e un intero positivo k tali che T accetta L in O(n^k) passi, dove n e' la taglia nell'input.
   Ossia l'appartenenza a L puo' essere testata da un algoritmo che esegue in tempo polinomiale.
   Per la classe NP diamo la seguente definizione, che NON utilizza la macchina di Turing non deterministica, con la quale si puo' dare una definizione equivalente ed alternativa a quella che segue e da cui deriva la denominazione della classe.
   Classe di complessita' NP (non deterministic polynomial time verification algorithm): Un linguaggio L e' in NP se esistono una macchina di Turing T e un intero positivo k tali che:
   --per ogni x in L esiste un testimone (detto anche certificato) W(x) tale che, quando a T viene fornito l'input (x,T(x)), T riconosce che x e' in L in O(n^k) passi.
   --per ogni x non in L tale testimone non esiste. Ossia comunque si prenda W'(x), l'input (x,W'(x)) non determinera' la falsa risposta x in L.
   Tutti i linguaggi citati sono in NP. Per ognuno forniamo il certificato, in particolare per L_Pr, la cui appartenenza a NP risale al '75 (certificato di Pratt). I linguaggi L_CE e L_Pr sono anche in P (per L_Pr in P vedi articolo del 2004, citato nella lezione precedente)
   Quindi brevemente NP e' la classe dei linguaggi per cui, per ogni input nel linguaggio, la prova di appartenenza puo' essere verificata in tempo polinomiale.
   Classe di complessita' coNP: Un linguaggio L e' in coNP se esistono una macchina di Turing T e un intero positivo k tali che:
   --per ogni x non in L esiste un testimone (detto anche certificato) W(x) tale che, quando a T viene fornito l'input (x,T(x)), T riconosce che x e' non in L in O(n^k) passi.
   --per ogni x in L tale testimone non esiste. Ossia comunque si prenda W'(x), l'input (x,W'(x)) non determinera' la falsa risposta x non in L.
   Si prenda ad esempio il linguaggio L_Pr: e' banale mostrare che e' nella classe coNP--il certificato W(n) di un naturale n non in L_Pr e' un divisore di n-- mentre non e' affatto banale mostrare che e' nella classe NP.
   P e' contenuto nell'intersezione di NP e coNP.
   Il problema P vs NP. Un linguaggio L' e' riducibile a L se ogni input per L' puo' essere trasformato da una macchina di Turing deterministica, in tempo polinomiale, in un input per L (scriviamo L'≤_pL). Esempio: L_HC≤_pL_TSP.
   Un linguaggio L si dice NP-completo se:
   -- L e' in NP
   -- ogni linguaggio L' in NP e' riducibile a L in tempo polinomiale
   Teorema (Cook, 1961): SAT e' NP completo. Proposizione: Se L e' NP completo e L≤_pL', allora L' e' NP completo. Ad ora si conoscono migliaia di linguaggii NP completi.
   Fatto: P=NP se e solo se un linguaggio completo e' in P (segue dalla definizione di NP completezza).

   Ulteriore bibliografia:
   -- Notes on Complexity Theory, Jonathan Katz (2011)
   -- Il problema P vs NP, pagina del Clay Mathematics Institute
   --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).
   

8. 17.10.2013 (ore 3)
   Struttura della macchina di Turing. Campi finiti: l'anello delle classi di resto modulo un naturale n e' un campo se e solo se n e' primo. Esempio: costruzione del campo dei numeri complessi C come campo quoziente dell'anello dei polinomi a coefficienti in R, modulo l'ideale generato dal polinomio irriducibile x²+1. Tale esempio fornisce una motivazione per lo studio dei polinomi. L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A. Grado di un polinomio. Sia d un polinomio a coefficienti in un campo K. Dato f in K[x] esistono unici q e r in K[x] tali che f=qd+r, con deg(r)< deg(d) o r=0.
   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.
   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)={a₁,...,a_r} allora f=q(x-a₁)^ν_a1(p)...(x-a_r)^ν_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 f² 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.
   
9. 21.10.2013 (2 ore)
   Radici di 1 in C: definizione, radici n-esime primitive di 1 in C (caratterizzazione e proprieta'). Polinomi ciclotomici: definizione, esempi e proprieta'.
10. 24.10.2013 (3 ore)
    Definizione di sottogruppo H di un gruppo G; definizione di classe laterale sinistra; G/H=insieme delle classi laterali sinistre (se H e' normale, in particolare se G e' commutativo, G/H e' un gruppo). Prop: sia H un sottogruppo di un gruppo finito G, allora la cardinalita' di H divide la cardinalita' di G. Definizione di potenza intera di un elemento g in un gruppo G. Definizione di ordine di un elemento di G: ord(g). Sia G finito, allora ord(g) divide cardinalita' di G per ogni g in G. Sia g in G di ordine finito e sia r un intero tale che g^r=1, allora ord(g) divide r. Sia A un anello e sia I un ideale di A. Allora A/I e' un anello. Z e' un anello a ideali principali. L'esempio di Z/(n)=Z/nZ, anello delle classi di resto modulo n. Sia f: A ---> B un omomorfismo di anelli. Allora Ker(f) e' un ideale di A e l'applicazione naturale da A/Ker(f) in B indotta da f e' un omomorfismo iniettivo.
    Caratteristica di un campo. Radici n-esime primitive di 1 in un campo K. Criterio per determinare se un elemento a di K e' una radice n-esima primitiva utilizzando i polinomi ciclotomici.
11. 28.10.2013 (2 ore)
    Definizione di gruppo ciclico. Esempi. Teorema di Gauss: sia G un sottogruppo FINITO del gruppo moltiplicativo di un campo, allora G e' ciclico.
    Si considera l'anello F_p[x]/(f), con f in F_p[x]. Esempi. Cardinalita' di F_p[x]/(f). Definizione di polinomio irriducibile. Prop. L'anello F_p[x]/(f) e' un campo se e solo se f e' un polinomio irriducibile. Si osserva che il campo F_p[x]/(f) ha caratteristica p.
12. 31.10.2013 (3 ore)
    Lezione seminariale tenuta da Guido Cocchi, attualmente studente del secondo anno del corso di Laura Magistrale in Ingegneria Informatica (presente la docente): il problema del logaritmo discreto, l'algoritmo Diffie-Hellman, l'algoritmo di Shanks.
    Sia A un anello commutativo e I un ideale di A, il quoziente A/I e' un campo se e solo se I e' un ideale massimale. Un polinomio irriducibile in K[x] non ha radici in K, un polinomio di grado due o tre senza radici in K e' irriducibile in K[x]. Lemma: Sia F un campo finito. Allora esistono un naturale p, primo, e un polinomio irriducibile f in F_p[x], tali che F_p[x]/(f) e' isomorfo a F. Corollario: un campo finito F ha cardinalita' uguale alla potenza di un primo. Teorema di esistenza e unicita': Siano P un primo e n un naturale, n>0.
    a) Allora esiste un polinomio irriducibile f in F_p[x] di grado n (si ottiene quindi il campo F_p[x]/(f) di cardinalita' pⁿ).
    b) Siano F e F' due campi con la stessa cardinalita' finita, allora F e F' sono isomorfi.
    Per dimostrare a) dimostriamo: Teorema: Sia p un primo e sia f un fattore irriducibile di Phi_pⁿ-1 in F_p[x], allora f ha grado n.
13. 04.11.2013 (2 ore)
    Completamento della dimostrazione del Teorema di esistenza e unicita'. Teorema: Il polinomio X^pn-1-X in F_p[x] e' il prodotto di tutti e soli i polinomi monici irriducibili di F_p di grado d, con di compreso tra 0 e n e d che divide n. Inoltre ogni fattore ha molteplicita' 1.
    Corollario: Sia N_d il numero dei polinomi monici irriducibili di grado d in F_p, allora pⁿ=&sum_{d | n}d N_d.
    Da cui la formula diretta per N_n scritta utilizzando la funzione di Moebius (vedere ad esempio in questo file l'esempio numero 3).
    Caso particolare della formula nel caso in cui n sia primo.
14. 07.11.2013 (3 ore)
    Dimostrazione del teorema enunciato la lezione precedente. Definizione della mappa di Frobenius (1849-1917) dall'anello F_p[x]/< f > in se. F_p[x]/< f > e' uno spazio vettoriale su F_p di dimensione uguale al grado di f. La mappa di Frobenius e' un omomorfismo di anelli e una applicazione lineare.
    Teorema: Un polinomio f e' irriducibile se e solo se Ker(F)=0 e Ker(F-I)= F_p.
    Prima parte della dimostrazione: f irriducibile implica Ker(F)=0 e Ker(F-I)=F_p. La dimostrazione da' un algoritmo per la fattorizzazione di polinomi (algoritmo di Berlekamp). Esempio di applicazione dell'algoritmo. Esempio di applicazione dell'algoritmo di Berlekamp.
    Seconda parte della dimostrazione: Ker(F)=0 e Ker(F-I)=F_p implica f irriducibile.
    
15. 11.11.2013 (2 ore)
    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: dato da un alfabeto (diamo la definzione 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. Criterio di decodifica a massima probabilita' (MPD). Criterio di decodifica a massima probabilita' incompleto (IMPD). Criterio di decodifica a massima probabilita' completo (CMPD). Esempio con BSC. Distanza di Hamming, definizione e proprieta'. Criterio di decodifica a minima distanza (DMD). Il procedimento di decodifica a minima distanza e' detto anche nearest neighbour decoding.
    Proposizione: Per un canale senza memoria e fortemente simmetrico le decodifiche a massima probabilita' e minima distanza coincidono. Per curiosare: "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).
16. 14.11.2013 (3 ore)
    Distanza di Hamming di un codice. Distanza d(x,C) di una parola w in Aⁿ da un codice C. Definizione di sfera aperta e chiusa di centro x e raggio s, denotate (in questo registro) rispettivamente con B_s(x) e B_s(x). Un codice C segnala al piu' s errori in DMD se per ogni x in C B_s(x)∩C={x}. Un codice C corregge al piu' s errori in DMD se per ogni w in Aⁿ tale che d(w,C)≤s esiste un'unica parola x in C tale che w appartiene a B_s(x). Lemma: Sia C un codice in Aⁿ_q. Allora d(C)≥2s+1 se e solo se B_s(x)∩B_s(y)=∅ per ogni x e y in C, x diverso da y.
    Proposizione:(i) un codice C segnala al piu' s errori se e solo se d(C)≥s+1; (ii) un codice C corregge al piu' s errori se e solo se d(C)≥2s+1
    Un codice C si dice di tipo (n,M,d)_q se C e' contenuto in Aⁿ, la cardinalita' di A, |A|, e' q, la cardinalita' di C, |C|, e' M e d=d(C). La capacita' di rilevare/correggere errori con la decodifica a minima distanza dipende dal parametro d, precisamente:un codice (n,M,d)_q rileva al piu' d-1 errori e corregge al piu' [(d-1)/2] errori (il numero [(d-1)/2] indica la parte intera inferiore di (d-1)/2). Denotiamo con e=[(d-1)/2]. Teorema di Hamming (limitazione superiore per M in funzione di n, q ed e). Lemma: formula per il numero di parole di Aⁿ contenute in una palla chiusa di raggio r. Definizione di codice perfetto. Esercizio: dimostrare che se (n,M,d)_q e' perfetto allora d e' dispari. Codici lineari: definizione. Esempi. Prodotto scalare in F_qⁿ. Ortogonale di un codice lineare. La somma delle dimensioni di C e del suo ortogonale e' n. L'ortogonale dell'ortogonale di C e' C. Definizione di matrice generatrice G e matrice di controllo di parita' H di un codice lineare. Caratterizzazione di un codice e del suo ortogonale a partire rispettivamente dalla matrice di controllo di parita' e dalla matrice generatrice.
17. 18.11.2013 (2 ore)
    Peso di Hamming di un elemento in F_qⁿ. Peso di Hamming di un codice lineare. Dato C codice lineare per e distanza di C sono uguali. Proposizione: sia C un codice lineare in F_qⁿ di dimensione k. Sia H una matrice di controllo di parita' di C. Allora:
    (i) d(C)≥l se e solo se non ci sono l-1 colonne di H linearmente dipendenti
    (ii) d(C)≤l se e solo se esistono l colonne di H linearmente dipendenti.
    (iii) d(C)=l se e solo se non ci sono l-1 colonne di H linearmente dipendenti ed esistono l colonne di H linearmente dipendenti.
    Esempi di operazioni sulla matrice generatrice di un codice. Definizione di matrice generatrice in forma standard. Definizione di matrice di controllo di parita' in forma standard.
18. 21.11.2013 (3 ore)
    Definizione: una applicazione lineare f da F_qⁿ in se' conserva la distanza di Hamming se per ogni coppia di elementi x,y in F_qⁿ si ha d(f(x),f(y))=d(x,y) (equivalentemente: se per ogni x in F_qⁿ si ha wt(f(x)=wt(x)). Osservazione: ogni applicazione lineare da F_qⁿ in se'che conserva la distanza di Hamming e' un isomorfismo. Chiamiamo un isomorfismo che conserva la distanza Hamming un'isometria.
    Definizione del gruppo delle permutazioni generalizzate, GP(n,F_q): e' il sottogruppo del gruppo degli isomorfismi, GL(n,F_q), di F_qⁿ, generato dalle permutazioni e dagli isomorfismi del tipo diag(l₁,...,l_n). Proposizione: GP(n,F_q) coincide con il sottogruppo degli isomorfismi di F_qⁿ che conservano la distanza di Hamming (isometrie). Definizione: due codici lineari C e C' in F_qⁿ si dicono equivalenti se esiste f: F_qⁿ ---> F_qⁿ in GP(n,F_q) tale che f(C)=C'.
    Teorema (Florence MacWlliams) Siano C e C' due codici linearin in F_qⁿ, se C e C' sono isometrici, ossia, se esiste f:C--->C' isomorfismo che conserva la distanza, allora C e C' sono equivalenti, ossia f estende a un'isometria di F_qⁿ. S.D. Per una dimostrazione vedi qui, il pdf e' disponibile.
    Proposizione: due codici equivalenti hanno lo stesso peso e la stessa distanza. Osservazione: sia G la matrice generatrice di un codice C, le seguenti operazioni sulle righe di G producono una nuova matrice generatrice di C: scambiare due righe tra loro, moltiplicare una riga per uno scalare diverso da zero, sostituire una riga con la riga stessa sommata a una combinazione lineare delle altre. Le seguenti operazioni sulle colonne producono una matrice, che definisce, come matrice generatrice, un codice C' equivalente a C. Teorema: ogni codice lineare C e' equivalente a un codice C' che ha una matrice generatrice in forma standard. Dim: applicare la riduzione di Gauss e l'osservazione precedente. Proposizione: Sia G=(I_k|X) matrice generatrice di un codice C in forma standard, allora la matrice H=(-X^t|I_n-k) e' una matrice di controllo di parita' per C. Processo di codifica per un codice lineare. Message digits, check digits. Processo di decodifica a minima distanza (DMD) per un codice lineare. Sia C un codice lineare in F_qⁿ di dimensione k. Si considera lo spazio vettoriale quoziente F_qⁿ/C. Tale spazio ha dimensione n-k e ha q^n-k elementi, ognuno di questi e', come sappiamo, una classe laterale (coset). Osservazione importante: nella decodifica a minima distanza di una parola ricevuta w con una parola x in C, la parola w-x e' una parola della classe di w. Poiche' d(w,x)=wt(w-x), la parola w-x e' una parola nella classe di w di peso minimo. Siamo quindi interessati a individuare, in ogni classe, le parole di peso minimo. In ogni classe scegliamo una parola di peso minimo, questa e' per definizione il coset leader della classe. La tabella standard (standard array) e' costituita in questo modo: la prima colonna, a_i1, di q^n-k elementi, da' la lista dei coset leader, con a₁₁=0. Per ogni coset leader la riga corrispondente da' la lista degli elementi della classe, ossia fissato i, per ogni j, a_ij=a_1j+a_i1. Si segnalano con un asterisco le classi che hanno piu' di un elemento minimo. Il procedimento di decododifica a minima distanza e' il seguente: ricevo w. Controllo la tabella e individuo il capoclasse err(w) corrispondente a w. Decodifico con x=w-err(w), che e' la prima parola della colonna di w. Se w appartiene a una riga asteriscata o richiedo la trasmissione (decodifica incompleta) e procedo come sopra (decodifica completa).
    Decodifica a sindrome. Sia C un codice lineare [n,k,d]_q, con matrice generatrice G e matrice di controllo di parita' H. Definiamo l'applicazione lineare S_H:F_qⁿ--->F_q^n-k come S_H(w)=wH^t. L'elemento S_H(w) si dice sindrome di w. L'applicazione lineare S_H e' suriettiva, il suo nucleo e' C. Proposizione: L'applicazione S_H induce un'isomorfismo da F_qⁿ/C in F_q^n-k. Dim: immediata utilizzando quanto fatto in precedenza. Costruiamo una tavola detta syndrome look-up table nel modo seguente: la prima colonna coincide con la prima colonna dello standard array, da' quindi una lista di coset leader, con primo elemento 0. La seconda colonna associa ad ogni coset leader u la sua sindrome S_H(u). Anche qui indichiamo con asterisco le righe (classi) in cui non c'e' un'unica parola di peso minimo. Miglioriamo questa tabella. Proposizione: l'applicazione S_H e' iniettiva su B_e(0), dove e e' come al solito la parte intera inferiore di d-1/2 e rappresenta la capacita' correttiva del codice.
    Corollario: ogni parola in B_e(0) e' l'unica parola di peso minimo nella propria classe.
    Costruiamo la syndrome look-up table mettendo, per prime nella prima colonna, tutte le parole in B_e(0), partendo da 0. Le righe (classi) corrispondenti NON saranno asteriscate. Completiamo con i rimanenti coset leaders.
    Procedimento di decodifica a sindrome (sempre DMD): ricevo la parola w. Passo 1: calcolo S_H(w). Passo 2: mediante la tabella syndrome look-up table individuo il coset leader corrispondente err(w). Passo 3: decodifico con x=w-err(w). Osservazione: se S_H(w) appartiene a S_H(B_e(0))--ossia se w sta sulla riga corrispondente a un coset leader in B_e(0)--la decodifica e' esatta, ossia x e' l'unica parola di C tale che d(w,x)= d(w,C). Esempi.
19. 25.11.2013 (ore 2)
    Lemma[versione del bound di Singleton per codici lineari] sia C un codice lineare [n,k,d]_q. Allora d≤ n-k+1.
    Denotiamo con Vⁿ_q(s) il numero dei punti contenuti in una palla chiusa B_s(x) in Aⁿ, che abbiamo determinato in precedenza e ricordiamo il seguente limite superiore: per un codice di tipo (n,M,d)_q si ha M≤ qⁿ/ Vⁿ_q(e), dove e e' la parte inferiore intera di (d-1)/2 (Hamming bound, e' un esempio di upper bound per M). Costruiamo i codici di Hamming, che sono un esempio di codici linerari perfetti:
    definizione di spazio proiettivo P(F_q^r); P(F_q^r); contiene esattamente s=(q^r-1)/(q-1) punti; definizione di un codice Ham(r,q) mediante la matrice di controllo di parita'. I parametri di Ham(r,q) sono [s,s-r,3]_q e vale l'uguaglianza nell'Hamming bound.
    I codici Ham(r,q) sono tutti equivalenti come codici lineari (per esercizio).
    Proposizione: Sia C un codice lineare [n,k,d]_q (ricordiamo che k≤ n e d≤ n-k+1). Allora:
    (i) [costruzione per allungamento] per ogni r≥ 1 esiste un codice lineare [n+r,k,d]_q;
    (ii)[estrazione di un sottocodice]per ogni 1 ≤ r≤ k-1 esiste un sotto-codice lineare [n,k-r,d]_q di C;
    (iii)[puncturing] per ogni 1 ≤ r≤ d-1 esiste un sotto-codice lineare [n-r,k,d-r]_q di C;
    (iv) per ogni 1 ≤ r≤ d-1 esiste un codice lineare [n,k,d-r]_q di C;
    (v) per ogni 1 ≤ r≤ k-1 esiste un codice lineare [n-r,k-r,d]_q di C;
    (vi) siano C₁ e C₂ codici lineari con parametri rispettivamente [n₁,k₁,d₁]_q e [n₂,k₂,d₂]_q. Si definisce il codice C₁⊕C₂ con parametri [n₁+n₁,k₁+k₂,min{d₁,d₂}]_q.
    
20. 28.11.2014 (ore 3) Codici MDS (maximum distance separable): un codice [n,k,d]_q si dice MDS se d=n-k+1. Teorema di unisolvenza: Siano a₁,...,a_m elementi distinti in un campo K. Sia n≤ m. Allora l'applicazione ev_a:k[x]_≤n-1---> K^m cosi' definita: ev_a(p)=(p(a₁),...,p(a_m)) e' lineare e iniettiva. Se n=m e' un isomorfismo di spazi vettoriali. Prima costruzione dei codici di Reed-Solomon RS(k,q); parametri [q-1,k,n-k+1]_q. Bounds: definiamo A_q(n,d) la taglia massima raggiungibile da un codice di lunghezza n e distanza d; definiamo B_q(n,d) la taglia massima raggiungibile da un codice lineare di lunghezza n e distanza d.
    Si ha: B_q(n,d)≤ A_q(n,d)≤ qⁿ;
    B_q(n,1)≤ A_q(n,1)=qⁿ;
    B_q(n,n)≤ A_q(n,n)=q.
    Teorema: fissata la potenza di un primo q, siano n,k,d interi tali che: 2 ≤ d ≤ n, 1 ≤ k ≤ n e V^n-1_q(d-2)≤ n-k. Allora esiste un codice lineare [n,k,d']_q, con d' ≥ d. Corollario [Gilbert-Varshamov lower bound]: Fissato q, per d,n tali che 2 ≤ d ≤ n si ha;
    B_q(n,d)≥ q^{n-⌈ log_q( Vn-1_q(d-2)+1)⌉} ≥ q^n-1/ V^n-1_q(d-2).
    Introduzione ai bounds asintotici.
    Per iniziare a curiosare: 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.
    
21. 2.12.2013 (ore 2)
    Bounds asintotici; versione asintotica del bound di Gilbert-Varshamov. Note sintetiche su quanto trattato in questa lezione e nella precedente.
    
22. 5.12.2013 (ore 3)
    Codici ciclici: definizione e teorema di classificazione: i codici lineari ciclici in F_qⁿ sono in corrispondenza biunivoca con i divisori monici del polinomio xⁿ-1 in F_q[x]. Questo deriva dal fatto che i codici ciclici in F_qⁿ sono in corrispondenza biunivoca con gli ideali dell'anello F_qⁿ[x]/(xⁿ-1) e quindi con gli ideali di F_qⁿ[x] che contengono il polinomio xⁿ-1.
    Sia g di grado n-k in F_q[x] il polinomio generatore del codice ciclico C in F_qⁿ, allora la dimensione di C e' k. Matrice generatrice di un codice ciclico a partire dal polinomio generatore. Esempi di codici ciclici. Esempio di codici ciclici in F_qⁿ equivalenti e generati da polinomi diversi. Introduzione alla decodifica dei codici ciclici e alla costruzione di una matrice di controllo di parita' a partire dal polinomio generatore g. L'argomento verra' ripreso nella prossima lezione.
23. 9.12.2013 (ore 2)
    Proposizione: l'ortogonale di un codice ciclico e' ciclico. Sia C un codice ciclico in F_qⁿ con polinomio generatore g di grado (n-k). Si definisce il polinomio di controllo di parita' di C. Matrice di controllo di parita' di un codice ciclico. Per un codice ciclico e' sempre possibile determinare una matrice H di controllo di parita' della forma (I_n-k|A). Utilizzando H, una parola s in F_q^n-k e' la sindrome di una parola w in F_qⁿ se e solo se per i polinomi corrispondenti si ha che s(x) e' il resto della divisione del polinomio w(x) per g. Si ha quindi che s e w, come elementi di F_qⁿ, appartengono alla stessa classe laterale in F_qⁿ/C e quindi, se wt(s) non supera la capacita' correttiva del codice, la decodifica di w a minima distanza e' w-s. Esempi.
    Un articolo utile sui codici ciclici: An introduction to linear and cyclic codes di D. Augot, E. Betti e E. Orsini.
24. 12.12.2013 (ore 3)
    Decodifica di codici ciclici: algoritmo di decodofica error trapping ; esempi (Sezione 7.4 del testo di riferimento).
25. 16.12.2013 (ore 2)
    Lezione seminariale tenuta da Tomaso Trinci, attualmente studente del primo anno del corso di Laura Magistrale in Matematica (presente la docente): presentazione di uno schema di rintracciamento traditori interno al sistema di protezione Advanced Access Content System (AACS), utilizzato per Blu-ray e HD DVD. Tale schema di rintracciamento e' costruito utilizzando due codici Reed-Solomon concatenati (per approfondimenti vedere ad esempio Traitor Tracing for Prerecorded and Recordable Media e relativa bibliografia).
    Errori di tipo burst e codici ciclici correttori di errori di tipo burst; descrizione dell'algoritmo di decodifica, senza dimostrazione (Sezione 7.5 del testo di riferimento).