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

1. 25.09.17 (ore 1).
   Introduzione al corso: informazioni pratiche; descrizione programma; motivazioni.

   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.
   

2. 28.09.17 (ore 3).
   Definizione di gruppo, anello, campo. Esempi. Teorema della divisione. Definizione della relazione di congruenza e relative proprieta', ogni intero e' congruo al suo resto modulo d; due interi sono congrui modulo d se e solo se hanno lo stesso resto quando divisi per d. 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.
3. 02.10.17 (ore 2).
   Ulteriori osservazioni sull'algoritmo dei quadrati ripetuti.
   Definizione dell'anello, Z/nZ, delle classi di resto modulo n. Esempi. 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).
4. 06.10.17 (ore 3).
   Dimostrazione del Lemma di Euclide. 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.
   Proposizione: Due interi a e b sono co-primi se e solo esistono x e y interi tali che xa+yb=1.
   Proposizione: l'anello delle classi di resto Z/nZ e' un campo se e solo se n e' un numero primo.
   Proposizione: Se a divide bc e a e b sono primi tra loro, allora a divide c.
   
5. 09.10.17 (ore 2)
   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.
   Introduzione al teorema cinese del resto: Esempi di applicazione resto e sistemi di congruenze.
   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 è un isomorfismo di anelli, in particolare è biunivoca. Si osserva che questo e' equivalente all'esistenza e unicita' della soluzione (modulo n) di un sistema di congruenze. Teorema cinese del resto (Sun-Tsu 280-473, Chin Chiu Shao 1247) come teorema di esistenza e unicita' della soluzione di un sistema di congruenze, che soddisfi le opportune ipotesi. Dimostrazione dell'unicita'.
6. 13.10.17 (ore 3)
   Dimostrazione costruttiva dell'esistenza di una soluzione (Teorema cinese del resto): descriviamo una procedura,basata sull'algoritmo euclideo esteso, che determina una soluzione esplicita.
   Esempio di applicazione del teorema cinese del resto: caso molto semplice dello schema di condivisione di un segreto (secret sharing scheme). Questi schemi sono stati introdotti indipendentemente da A. Shamir e G. R. Blakley nel 1979.
   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, come gia' dimostrato, Z/nZ e' un campo se e solo se n e' primo.
   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).
   Calcolo della funzione di Eulero di un naturale, quando e' nota la sua scomposizione in primi.
7. 16.10.2017 (ore 2)
   Algoritmo RSA in dettaglio.
   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; 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. Differenza qualitativa tra algoritmi che eseguono in tempo polinomiale ed esponenziale.

   Per approfondimenti: Secret sharing.
   Twenty years of attacks on the RSA cryptosystem di Dan Boneh.
   Per approfondimenti: 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
   

8. 17.10.2017 (ore 2)
   Introduzione alla teoria della complessita' computazionale. Problemi decisionali. 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: L_Pr=insieme dei numeri primi
   L_EC=insieme dei grafi connessi che ammettono un circuito Euleriano
   L_HC=insieme dei grafi connessi che ammettono un circuito Hamiltoniano
   L_TSP=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
   L_SAT=insieme delle formule Booleane AND of OR's soddisfacibili
   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.
   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, e i capitoli 17 e 18 del libro A walk through combinatorics, Miklos Bona citato anche nella scorsa lezione.
   Per la teoria dei grafi vedere, ad esempio: Corso di teoria dei grafi, Carlo Casolo e il libro di Bona succitato.

9. 20.10.2017 (3 ore)
   Dati due linguaggi L ed L' definiamo quando L e' riconducibile ad L', L≤_pL'. Definizione di NP completezza.
   Teorema (Cook, 1961): L_SAT 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: L_HC e L_TSP.
   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, dei campi: F₂[x]/(x²+x+1), con 4 elementi; campo dei numeri complessi C come R[x]/x²+1; F₂[x]/(x³+x+1), con 8 elementi. Per ognuno dei campi costruiti si analizzano somma e prodotto, si fanno diversi calcoli e si osservano diverse proprieta'.

   Per approfondimenti: 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).
   

10. 23.10.2017 (ore 2)
    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)={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.
11. 30.10.2017 (2 ore)
    Dimostrazione del Lemma enunciato alla fine della lezione precedente. 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. Proprieta' fondamentali.
12. 3.11.2017 (3 ore)
    Dimostrazione delle proprieta' dei polinomi ciclotomici. Definizione di caratteristica di un campo. Criterio per stabilire se una radice n-esima di 1 in un campo K e' n-esima primitiva. Teorema di Gauss: un sottogruppo finito del gruppo moltiplicativo di un campo e' ciclico. 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 gⁿ=e allora ord(g) divide n.
13. 6.11.2017 (2 ore)
    Sottogruppi. Gruppo quoziente (per gruppi abeliani). L'ordine di un sottogruppo divide l'ordine del gruppo. Sottogruppo generato da un elemento. Dimostrazione della proposizione enunciata alla fine della scorsa lezione. 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 degli anelli quozienti F_p[x]/< f >.
    F_p[x]/< f > e' un campo se e solo se f e' irriducibile in F_p[x].
    F_p e' un sottocampo di L:=F_p[x]/< f >
    Il polinomio f e' in F_p[x] e quindi in L[x]. L'elemento [x] in L e' una radice di f. Quindi abbiamo costruito una estensione di F_p a un campo L che contiene una radice del polinomio f, irriducibile in F_p[x].
    Il campo L= F_p[x]/< f > ha pⁿ elementi.
    
14. 7.11.2017 (2 ore)
    Proposizione: sia F un campo finito, allora esistono p primo ed f polinomio irriducibile in F_p[x] tali che F e' isomorfo a F_p[x]/< f >.
    Corollario: Un 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 pⁿ elementi. Il campo F e' unico a meno di isomorfismi. Se q=pⁿ denotiamo con F_q tale campo. Dimostriamo prima l'esistenza. Lemma *: sia f un fattore irriducibile in F_p[x] del polinomio ciclotomico phi_pⁿ-1, allora il grado di f e' uguale a n. Questo Lemma implica la parte di esistenza del teorema. Dimostriamo il Lemma, occorre un Lemma tecnico di cui omettiamo la semplice dimostrazione: siano r,s,t naturali con r>1, allora r^s-1 divide r^t-1 se e solo se s divide t.
15. 13.11.2017 (ore 2)
    Dimostrazione del lemma enunciato alla fine della precedente lezione: sia f un fattore irriducibile in F_p[x] del polinomio ciclotomico phi_pⁿ-1, allora il grado di f e' uguale a n. Omettiamo invece la dimostrazione della parte di unicita'.
    Dimostrazione del seguente teorema: sia f un polinomio in F_p[x], sia R l'anello F_p[x]/< f > e sia F : R ---> R la mappa di Frobenius, cosi' definita f(v)=v^p. Si consideri R come spazio vettoriale su F_p. Allora
    1) F e' lineare 2) f e' irriducibile in F_p[x] se e solo se Ker(F)={0} e Ker(F-I)=F_p.
    Esempio di applicazione.
16. 17.11.2016 (ore 3) Dimostrazione del teorema enunciato la volta scorsa: parte I: se f e' irriducibile allora Ker(F)={0} e Ker(F-I)=F_p. Dimostrazione per assurdo. Un sottoprodotto della dimostrazione, come gia' mostrato con l'esempio svolto, e' proprio l'algoritmo di Berlekamp per la fattorizzazione di polinomi in F_p[x].
    Parte II: se Ker(F)={0} e Ker(F-I)=F_p allora f e' irriducibile in F_p[x]. Sappiamo che f irriducibile in F_p se e solo se R e' un campo, quindi dimostriamo, essenzialmente con strumenti di algebra lineare che R e' un campo. Questa seconda parte della dimostrazione e' stata solo delineata brevemente e non svolta.
    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.
17. 20.11.2017 (ore 2)
    Distanza di Hamming: definizione e proprieta'. Distanza d(x,C) di una parola w in Aⁿ 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 B_s(x) e B_s(x).
    Un codice C segnala al piu' s errori in se, per ogni x in C, B_s(x)∩C={x}.
    Teorema: un codice C segnala al piu' s errori se e solo se d(C)≥s+1
    Esempio
    Un codice corregge al piu' s errori se per ogni parola w in Aⁿ 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 B_s(c).
    Teorema: un codice C corregge al piu' s errori se e solo se d(C)≥2s+1.
    Esempio
    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 B_s(c)∩B_s(c')=vuoto. 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).
18. 24.11.2017 (ore 3)
    Codici lineari. Definizione: un codice lineare e' un sottospazio vettoriale di F_qⁿ (q=p^r con p primo). Esempi. Prodotto scalare in F_qⁿ. Definizione di ortogonale di C. Proprieta'. Definizione di matrice generatrice G e matrice di controllo di parita' H di un codice lineare: 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 F_qⁿ appartiene a C se e solo se Hx^t=0; x in F_qⁿ appartiene all'ortogonale di C se e solo se Gx^t=0; una matrice H' M_(n-k),n(F_q) di rango n-k e' una matrice di controllo di parita' di C se e solo se G(H')^t=0; una matrice G' M_k,n(F_q) di rango k e' una matrice generatrice di C se e solo se H(G')^t=0.
    Peso di Hamming di una parola x in F_qⁿ, 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. 27.11.2017 (ore 2)
    Codici equivalenti. Definizione di GP(n,F_q): gruppo delle permutazioni generalizzate. Proposizione: il gruppo delle permutazioni generalizzate coincide con il sottogruppo degli isomorfismi di F_qⁿ che conservano il peso. 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 esiste una permutazione generalizzata di F_qⁿ 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.
    Proposizione: due codici equivalenti hanno lo stesso peso e la stessa distanza.
    La matrice generatrice G di un codice si dice in forma standard se G=(I_k|X).
    La matrice di controllo di parita' H di un codice si dice in forma standard se H=(X|I_n-k).
    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.
    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 ("per ogni riga all'avanti e all'indietro") e poi eventualmente operare sulle colonne.
    Corollario: ogni codice lineare C e' equivalente a un codice C' che ha una matrice di controllo di parita' in forma standard.
20. 1.12.2017 (ore 2)
    Fissato q, i parametri n,M,d sono parametri essenziali per il codice. Problema di ottimizzazione: fissati n e d qual e' la taglia massima Max tale che se M'> Max non esiste un codice (n,M',d)?
    Il Teorema di Hamming 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.
    Codici di Hamming: definizione del codice di Hamming Ham(r,q) (e' in realta' una classe di codici equivalenti). Esempio. I parametri dei codici di Hamming. In particolare i codici di Hamming hanno distanza 3 e sono codici perfetti.

    Lezione tenuta dal Professor Silvio Dolfi.

21. 4.12.2017 (ore 2)
    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 dunque q^n-k elementi, ognuno di questi e', come sappiamo, una classe laterale (coset).
    Sia w la parola ricevuta. Nella decodifica a minima distanza cerco c in C che minimizza d(w,c). Poiche' d(w,c)=wt(w-c), cerco la parola w-c, con c in C, di peso minimo. Osservazione importante: w-c appartiene alla stessa classe di w. Dunque cerco la parola nella classe di w, ossia in w+C, di peso minimo.
    Siamo quindi interessati a individuare, in ogni classe, le parole di peso minimo. In ogni classe prendiamo LA (o una, se ce n'e' piu' d'una) parola di peso minimo, questa e' per definizione il capoclasse (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 capoclasse, 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 decodifica a minima distanza e' il seguente: ricevo w. Controllo la tabella e individuo il capoclasse err(w) corrispondente a w. Decodifico con c=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).
    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)=(Hw^t)^t. La parola 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.
22. 11.12.2017 (ore 2)
    Riepilogo della lezione precedente. Decodifica a sindrome per un codice lineare. Costruzione della tabella delle sindromi. Definizione di codice ciclico. Enunciato del teorema di classificazione dei codici ciclici. Dimostrazione del primi punti, fino all'identificazione tra codici ciclici in F_qⁿ e ideali in F_q[x](xⁿ-1).
23. 12.12.2017 (ore 2)
    Seconda parte della dimostrazione del teorema di classificazione dei codici ciclici. Costruzione di una matrice di generatrice e di controllo di parita di un codice ciclico a partire dal suo polinomio generatore. Esempi. I codici di Reed Solomon come codici ciclici. Cenno alla decodifica dei codici ciclici.
24. 15.12.2017 (ore 3)
    Riepilogo sui codici ciclici e sulla loro decodifica. Esempio di decodifica di un codice ciclico. Bounds: Singleton bound, per codici generici e per codici lineari. Sphere packing bound. Gilbert-Varshamov bound (solo l'enunciato). Bounds asintotici, significato, funzione di entropia, l'importanza dei codici di Goppa. I codici di Reed Solomon verificano l'uguaglianza nel Singleton bound.

    Per approfondimenti: Un articolo utile sui codici ciclici: An introduction to linear and cyclic codes di D. Augot, E. Betti e E. Orsini.
    "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).
    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.