Codice insegnamento

4S001098

Docente

Francesca Mantese

Coordinatore

Francesca Mantese

Crediti

6

Lingua di erogazione

Inglese

Settore Scientifico Disciplinare (SSD)

MAT/02 - ALGEBRA

Periodo

I semestre dal 2 ott 2023 al 26 gen 2024.

Corsi Singoli

Autorizzato

Orario Lezioni Moodle Seminari 0

Obiettivi di apprendimento

L'insegnamento si propone di fornire allo studente i concetti e le tecniche fondamentali della teoria dei codici per la correzione di errori, con particolare attenzione ai codici lineari e ciclici. Gli argomenti saranno trattati sia da un punto di vista teorico che computazionale. Inoltre nella prima parte del corso si richiameranno concetti di base di algebra e si studieranno in modo approfondito i campi finiti. Al termine dell'insegnamento lo studente conoscerà la terminologia e i risultati piu' rilevanti in teoria dei codici, i principali codici lineari e ciclici, e i loro algoritmi di codifica e decodifica. Sarà inoltre in grado di produrre argomentazioni e dimostrazioni rigorose su questi temi e sarà in grado di leggere articoli e testi avanzati.

Prerequisiti e nozioni di base

Algebra lineare, nozioni di base di teoria dei gruppi e teoria degli anelli

Programma

-Richiami su gruppi, anelli, campi
-campi finiti
- Polinomi e l'Algoritmo Euclideo
-elementi primiti
-costruzione e classificazione dei campi finiti
-Cyclotomic cosets e polinomi minimi
-Concetti di base sui codici lineari
- Codici lineari, matrici generatrici e di parita'
- Codici duali
- Pesi e distanze
- Nuovi codici costruiti da codici esistenti
- Codici equivalenti
- Altre equivalenze tra codici
-Codici di Hamming
-Codifica, decodifica e Teorema di Shannon
- Sphere Packing Bound, covering radius, e codici perfetti
-Concetti di base sui codici ciclici
- Idempotenti e moltiplicatori
- Zeri di un codice ciclico
- Distanza minima dei codici ciclici
- Codici BCH
- Codici di Reed–Solomon
- Decodifica dei codici BCH
- L'algoritmo di decodifica di Peterson–Gorenstein–Zierler
- L'algoritmo di decodifica di Berlekamp–Massey
- L'algoritmo di decodifica di Sugiyama
- Decodifica nei CD
- Codici dalla geometria algebrica
- Rivisitazione dei codici di Reed–Solomon
- Codici di Goppa
- Il Gilbert–Varshamov Bound
- I codici di Goppa e il Gilbert–Varshamov Bound

Bibliografia

Modalità didattiche

Le lezioni e le esercitazioni si svolgeranno in presenza.
Appunti, esercizi e materiale aggiuntivo saranno resi disponibili sulla piattaforma Moodle del corso.

Modalità di verifica dell'apprendimento

L'esame consiste in una prova scritta in cui lo studente dovrà risolvere esercizi e rispondere a domande sugli argomenti trattati a lezione. Il voto ottenuto nella prova scritta potra' essere migliorato con il voto ottenuto presentando regolarmente gli esercizi assegnati per casa, e/o con una prova orale. Solo gli studenti che hanno superato la prova scritta possono sostenere la prova orale. In caso di esito positivo, il voto della prova scritto sara' valido fino all'ultimo appello disponibile nell'anno accademico in corso (febbraio 2025).

Criteri di valutazione

Per superare l'esame gli studenti devono dimostrare di:
- conoscere e aver compreso i concetti fondamentali della teoria dei codici per la correzione di errori
- avere un'adeguata capacità di risolvere problemi, sia da un punto di vista teorico che computazionale.
- saper argomentare i loro ragionamenti con rigore matematico.

Criteri di composizione del voto finale

Il voto finale sara' dato dal voto ottenuto nella prova scritta, oppure dalla media della prova scritta e della prova orale.

Lingua dell'esame

Inglese