Computational algebra (2017/2018)

Codice insegnamento
4S001098
Docenti
Francesca Mantese, Ihsen Yengui
Coordinatore
Francesca Mantese
crediti
6
Settore disciplinare
MAT/02 - ALGEBRA
Lingua di erogazione
Inglese
Periodo
II sem. dal 1-mar-2018 al 15-giu-2018.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

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.

Programma

Il corso consiste in lezioni in aula. Verranno forniti note ed esercizi per casa.

-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




Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
W. C. Huffman, V. Pless Fundamentals of Error-Correcting Codes Cambridge University Press 2010 0521131707
Lint, J. H. van Introduction to Coding Theory (Edizione 2) Springer-Verlag Berlin Heidelberg 1992 978-3-662-00174-5

Modalità d'esame

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.

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 2019).

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2017/2018 non sono ancora disponibili