- Algebraic Combinatorics
- Summary
Course Syllabus
Obiettivi
Coerentemente con gli obiettivi formativi del Corso di Studio,
l'insegnamento si propone di fornire allo studente le conoscenze
riguardanti l'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. Tempo permettendo verranno impartiti alcuni rudimenti su linguaggi di
programmazzione simbolica come Magma e Gap. Tali strumenti servono ad
enfatizzare gli aspetti sperimentali della scoperta matematica. Verranno altresì fornite le competenze necessarie a comprendere e analizzare le principali tecniche e metodi dimostrativi connessi all teoria, e le abilità
utili ad applicarle per risolvere esercizi e affrontare problemi.
Contenuti sintetici
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.
Prerequisiti
Algebra Lineare, Teoria dei Gruppi, Teoria dei Campi Finiti, Nozioni elementari di Termodinamica e Probabilità.
Modalità didattica
L'insegnamento prevede lezioni frontali per 56 ore (8 CFU), articolate
in: lezioni teoriche in cui si fornisce la conoscenza di definizioni,
risultati e teoremi rilevanti e altre in cui si intende fornire
competenze e abilità necessarie per utilizzare tali nozioni nella
risoluzione di esercizi e nell'analisi di problemi
Materiale didattico
Testo di Riferimento:
- Hall,
Notes on Coding Theory, 2005
- Appunti videoscritti delle singole lezioni reperibili su questa piattaforma.
- Appunti scritti in LaTeX in formato pdf 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
Periodo di erogazione dell'insegnamento
Secondo semestre.
Modalità di verifica del profitto e valutazione
L'esame inizia con la discussione della risoluzione con l’ausilio del programma di manipolazione simbolica Magma di un problema precedentemente concordato.
Al termine di tale discussione verra' effettuata un'interrogazione orale in cui vengono accertate sia l'acquisizione dei contenuti teorici impartiti nel corso sia le capacita' di analisi e risoluzione di problemi.
Entrambe gli aspetti contribuiscono allo stesso modo per la decisione del voto d'esame.
Nel caso di esito finale negativo verra' comunicato al candidato se e' necessario risolvere un nuovo esercizio o se, quello gia' risolto, possa essere considerato valido per una nuova prova orale.
Fino all’esaurimento della corrente emergenza sanitaria, la prova orale
dell’esame si svolgerà da remoto mediante piattaforma WebEx o analoga,
con accesso reso disponibile sulla pagina e-learning dell’insegnamento.
Orario di ricevimento
Su appuntamento. A causa dell'emergenza sanitaria, il ricevimento si svolgerà in modalità telematica mediante piattaforma WebEx o analoga.
Aims
In line with the aims of the CdS, the course will provide students the knowhow necessary to deal with transmission of information via noicy channels, in order to analyze optimal error-correcting and -detecting procedures. Time permitting some rudiments of programming languages as Magma and Gap will be imparted. These tools serve to emphasize sperimental aspects of mathematical discovery. We will also impart the necessary skills to comprehend and analyze the main technical and proof methods.
Those will be tested via problem solving and resolutionef exercises related to the contents of the course.
Contents
Information Theory, messages transmission, error probability, entropy, Shannon’s Theorem, symmetric channel, Error-correcting codes, alphabet, finite fields, linear codes, Hamming codes, cyclic codes, Reed-Solomon and Reed-Muller codes, Weight preserving maps, MacWilliams’ Theorems, Invariant Theory of Finite Groups.
Detailed program
- Information Theory, messages transmission, noisy channels, error probability, entropy, Shannon’s Theorem, symmetric channel.
- Error-correcting codes, alphabet, finite fields, linear codes, Hamming codes, cyclic codes, Reed-Solomon and Reed-Muller codes.
- Upper and lower Bounds, Sphere Packing, Gilbert-Varshamov, Perfect codes and their classification.
- Weight preserving maps, MacWilliams’ Theorem, Monomial maps, Wilson Theorem.
- Weight enumerator polynomials, MacWilliams’ Theorem, self-dual codes, isotropic vectors, Witt Theorem,.
- Invariant Theory of Finite Groups, primary and secondary invariants, Cohen-Macaulay rings, groups generated by pseudo-reflection, Shephard-Todd Theorem.
Prerequisites
Algebra I and II, Linear Algebra, Group Theory, Finite Field Theory, Elementary notions of Thermodynamics and Probability.
Teaching form
The course consists of Lectures for 8 credits. They will give knowledge of basic definitions, relevant results and theorems. On the other side, we intend to give skills to use results and knowledge in solving exercises and analysing problems
Because the evolution
of Covid-19 health emergency, at the moment (A / A 2020/21) it is not
possible to say if the lectures will be in presence; in any case the
lectures of this course will be videotaped and will be available to
students on the e-learning platform.
Textbook and teaching resource
Textbooks:
- Hall, Notes on Coding Theory, 2005
- Tablet taken notes available on this platform.
- LaTeX Notes in pdf format available on this platform.
Further Readings:
- 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
Semester
Second semester.
Assessment method
The exam starts with a discussion concerning the solution with the support of the programming language Magma of a previously assigned problem.
This will immediately be followed by an oral enquiry assessing both the student's acquisition of the course contents and her/his capabilities of analyzing and solving problems. Both aspects equally contribute to the final score.
In case of failure the student will be told if a new problem (or a better solution for the old one) is requested in order to face a new oral exam.
Pending the current health emergency, the oral exam will be held online through WebEx or analogous, with access made available on the e-learning website.
Mark range: 18-30/30.
Office hours
By appointment. Due to the current health emergency, student reception will be carried out online through WebEx or analogous.