COMPUTER ALGEBRA

Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente? Ecco come fare >>
English course description
Anno accademico
2019/2020
Docente
FABIO STUMBO
Crediti formativi
6
Periodo didattico
Secondo Semestre
SSD
MAT/02

Obiettivi formativi

L'obiettivo del corso è approfondire gli aspetti teorici alla base di alcuni importanti algoritmi algebrici comunemente usati nelle applicazioni con particolare riferimento alla fattorizzazione dei polinomi, alle basi di Groebner e alla Teoria dei Codici.

Le principali conoscenze acquisite sono:
* struttura dei campi finiti;
* algoritmo di Berlekamp;
* algoritmo di Buchberger;
* algoritmi di codifica e correzione degli errori per la trasmissione di messaggi.

Le principali abilità acquisite sono:
* saper fattorizzare polinomi ad una variabile a coefficienti razionali o in un campo finito;
* saper effettuare la divisione tra polinomi in più variabili;
* saper codificare e decodificare un messaggio ed essere in grado di riconoscere e correggere gli errori avvenuti durante la trasmissione secondo gli algoritmi studiati.

Prerequisiti

Sono sufficienti le conoscenze elementari di algebra acquisite nel corso di Algebra del primo anno. In particolare:
* nozioni sui gruppi, anelli e campi;
* struttura dei campi finiti;
* calcolo del MCD e algoritmo euclideo.

Contenuti del corso

Il corso prevede 48 ore di lezione frontale nel corso delle quali verranno svolti sia la teoria che gli esercizi.
La suddivisione approssimativa delle lezioni è:
1. Preliminari algebrici (4 ore):
* Algoritmo euclideo.
* Campi finiti.
* Elementi primitivi.
* Radici dell'unità e classi ciclotomiche
2. Fattorizzazione di polinomi in una variabile (4 ore):
* Algoritmo di Berlekamp.
* Lemma di Hensel.
* Fattorizzazione in Q[x].
3. Basi di Groebner (20 ore):
* Ideali monomiali.
* Algoritmo della divisione per polinomi in più variabili.
* Lemma di Dickson.
* Teorema della base di Hilbert.
* Sizigie
* Basi di Groebner.
* Algoritmo di Buchberger.
4. Codici autocorretivi (20 ore):
* Distanza di Hamming.
* Disuguaglianze di Hamming, Singleton e Gilbert-Varshamov.
* Codici lineari, codici di Hamming.
* Codici ciclici, codici BCH e codici Reed-Solomon.
* Codifica e decodifica.
* Decodica a sindromi, decodifica di Slepian.
* Decodifica di Meggitt nei codici ciclci
* Algoritmi di decodifica nei codici BCH: PGZ, Forney, Sugyiama, Berlekamp-Massey

Metodi didattici

Il corso è organizzato secondo lezioni frontali convenzionali, generalmente di 2 ore ciascuna.

Modalità di verifica dell'apprendimento

L'obiettivo della prova d'esame consiste nella verifica del raggiungimento
delle abilità previste.
Tale verifica viene effettuata tramite una prova scritta della durata di
3 ore e composta da esercizi riguardanti gli argomenti svolti a lezione.
La prova scritta è composta da domande e/o esercizi di punteggio
variabile per un totale non inferiore a 30.
Il totale dei punti ottenuti nella prova (limitato a 30 se maggiore) è
il voto riportato dallo studente.
L'esame è superato se il voto è almeno 18.
La prova orale è opzionale, su richiesta dello studente.
L'eventuale prova orale contribuisce al voto finale con un punteggio
compreso tra -3 e 3.

Testi di riferimento

1) Fabio Stumbo, Basi di Groebner
2) Fabio Stumbo, Teoria dei Codici