- 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 programmazione 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
Le attuali disposizioni rettorali prevedono che la lezione sia fruibile sia in presenza che da remoto. Le lezioni verranno videoregistrate e saranno rese disponibili agli studenti sulla piattaforma e-learning del corso.
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 consiste in 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.
Le attuali disposizioni rettorali richiedono che la prova orale dell’esame si svolga in presenza a meno che lo studente non rientri in particolari e categorie riportate nel decreto rettorale. In tal caso la prova orale potrà essere sostenuta da remoto mediante piattaforma WebEx con accesso reso disponibile sulla pagina e-learning dell’insegnamento.
Orario di ricevimento
Su appuntamento.
Sustainable Development Goals
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
According to the present dispositions lectures can be attended either in presence or remotely; in any case the lectures will be videorecorded and made available 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 consists of an oral enquiry assessing both the student's acquisition of the course contents and her/his capabilities of analyzing and solving problems.
According to the actual dispositions the exam will be in presence unless the candidate belongs to one of the categories listed in the previously mentioned document. She/he must connect via webex exploiting a link reported on the e-learning page of the course.
Mark range: 18-30/30.
Office hours
By appointment.