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
- 2022/2023
- 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
