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
- 2017/2018
- Docente
- FABIO STUMBO
- Crediti formativi
- 6
- Periodo didattico
- Primo 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 Crittografia e alla Teoria dei Codici.
Le principali conoscenze acquisite sono:
* struttura dei campi finiti;
* significato di complessità computazionale di un algoritmo;
* caratteristiche fondamentali dei cifrari simmetrici ed asimmetrici;
* algoritmi di fattorizzazione di numeri e polinomi;
* test di primalità per numeri interi;
* algoritmi di codifica e correzione degli errori per la trasmissione di messaggi.
Le principali abilità acquisite sono:
* saper calcolare la complessità computazionale di un algoritmo;
* saper cifrare messaggi usando i cifrari studiati;
* riconoscere la primalità di un numero intero;
* fattorizzare un numero intero;
* saper fattorizzare polinomi a coefficienti interi o in un campo finito;
* 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 (12 ore):
* Algoritmo euclideo.
* Teorema di Eulero-Fermat.
* Sistemi di congruenze.
* Campi finiti.
* Elementi primitivi.
* Radici dell'unità e classi ciclotomiche
* Complessità computazionale.
2. Criptografia (6 ore):
* Permutazioni e sostituzioni.
* Algoritmi a sostituzione.
* Algoritmi a trasposizione.
* Algoritmo di Hill.
* Algoritmi simmetrici: DES e AES.
* Algoritmi a chiave pubblica: cifrario RSA, cifrario ElGamal.
* Funzioni di hash: SHA-1.
* Firma digitale: DSA.
3. Fattorizzazione dei numeri interi (4 ore):
* Crivelli: il crivello di Eratostene.
* Algoritmi di fattorizzazione: algoritmo (p-1) di Pollard, algoritmo Rho di Pollard.
* Test di primalità: algoritmo di Miller-Rabin, algoritmo AKS.
4. Fattorizzazione di polinomi (4 ore):
* Algoritmo di Berlekamp.
* Lemma di Hensel.
* Fattorizzazione in Q[x].
5. Codici autocorretivi (22 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, Computer Algebra, Ed. Aracne
2) Fabio Stumbo, Teoria dei Codici
