Anno di corso: 1

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 8
Tipo: A scelta dello studente
Crediti: 8
Tipo: A scelta dello studente
Crediti: 10
Tipo: A scelta dello studente
Crediti: 10
Tipo: A scelta dello studente

Anno di corso: 2

Crediti: 8
Crediti: 16
Tipo: A scelta dello studente
Crediti: 39
Tipo: Lingua/Prova Finale

COMBINATORICA ALGEBRICA

Scheda dell'insegnamento

Anno accademico di regolamento: 
2018/2019
Anno di corso: 
1
Anno accademico di erogazione: 
2018/2019
Tipo di attività: 
Obbligatorio a scelta
Lingua: 
Italiano
Crediti: 
8
Ciclo: 
Secondo Semestre
Ore di attivita' didattica: 
56
Prerequisiti: 

Algebra Lineare, Teoria dei Gruppi, Teoria dei Campi Finiti, Nozioni elementari di termodinamica e probabilità.

Moduli

Metodi di valutazione

Tipo di esame: 
Orale
Modalita' di verifica dell'apprendimento: 

Esame orale e risoluzione di esercizi con l’ausilio del programma di manipolazione simbolica Magma.

Valutazione: 
Voto Finale

Obiettivi formativi

Acquisizione degli strumenti per la trasmissione di informazione su canali con rumore, al fine di analizzare procedure di scambio ottimali nella rilevazione e correzione di errori.

Contenuti

Teoria dell’Informazione, trasmissione messaggi, probabilita' di errore, entropia, Teorema di Shannon, canale simmetrico, codici correttori di errore, alfabeti, campi finiti, codici lineari, codici di Hamming, ciclici, di Reed-Solomon e Muller, polinomio enumeratore, Teoremi di MacWilliams. Teoria invarianti gruppi finiti.

Programma esteso

Trasmissioni con rumore, alfabeto, parole di lunghezza fissata, codici a blocchi; canale simmetrico m-ario con probabilità p, codici di ripetizione, codice binario di Hamming (7,4,3); distanza di Hamming, lunghezza, dimensione e distanza minima di un codice, sphere packing bound, Gilbert-Varshamov bound, codici perfetti, cenni ai codici di Golay e di Hamming; Codici lineari, peso minimo, estensione di codici; Matrice generatrice di un codice, forma sistematica e standard, codici duali, matrici di controllo, distanza minima di un codice lineare; Cenni all'aritmetica dei campi finiti; Esistenza di codici autoduali, spazi simplettici e ortogonali; Decodifica di codici lineari, coset leaders, sindromi; Spazi proiettivi, decomposizione in spazi affini, codici di Hamming, codici 1-perfetti, unicità monomiale, traslati di codici lineari; Duali di codici di Hamming, codici a peso costante, teorema di Bonisoli; Gruppo degli automorfismi dei codici di Hamming; Struttura campi finiti, elementi primitivi; Polinomi ciclotomici su campi finiti; Fattorizzazione di x^n-1, polinomi minimi, struttura automorfismi campo finito, cenni teoria di Galois; classi ciclotomiche, gradi fattori irriducibili x^n-1, formula d’inversione di Moebius; Definizione di codici ciclici, Teorema di Prange; Duale codice ciclico, polinomi generatori; Generazione di codici ciclici, codici di Golay come codici ciclici, BCH bound; Teorema di MacWilliams sull’estensione di mappe lineari preservanti pesi a trasformazioni globali monomiali; Polinomi enumeratori, teorema di MacWilliams, esempi C=0, C=Rep e loro duali, caratteri di un gruppo; Esempi di anelli con caratteri non degeneri, leggi di ortogonalita'; Teorema di Lloyd sui codici perfetti; Introduzione alla teoria degli invarianti dei gruppi finiti, Teoremi di Noether e di Molien, serie di Hilbert-Poincaré, gruppi generati da pseudo-riflessioni, anelli di Cohen-Macaulay, Teorema di Chevalley-Shephard-Todd.

Bibliografia consigliata

Testo di Riferimento: Hall, Notes on Coding Theory, 2005 e appunti videoscritti delle singole lezioni sono reperibili su questa piattaforma.
Altri Testi:
Huffman and Pless, Fundamentals of error-correcting codes, 2010
MacWilliams and Sloane, The Theory of Error-Correcting Codes, 1977
Smith, Polynomial invariants of finite groups, 1995

Modalità di erogazione

Convenzionale

Metodi didattici

Lezioni: 8 CFU