Il programma si suddivide in una parte di matematica "di base", in cui si affrontano i primi rudimenti di teoria dei numeri, e in una parte dedicata ad alcune applicazioni delle strutture matematiche introdotte, precisamente la crittografia e alla teoria codici autocorrettivi.
Concrete abstract algebra
Niels Lauritzen
Cambridge University Press (2003)
Coding Theory: A First Course
San Ling, Chaoping Xing
Cambridge University Press (2004)
Obiettivi Formativi
Il corso si propone di fornire strumenti e metodi per lavorare nel "discreto", insieme ad una introduzione ad alcune applicazioni, che consenta anche di cominciare ad orientarsi nella moderna letteratura scientifica.
Prerequisiti
Algebra lineare elementare
Metodi Didattici
Lezioni frontali alla lavagna, con partecipazione attiva degli studenti.
Distribuzione di schede di esercizi.
Modalità di verifica apprendimento
Esame orale
Programma del corso
Il programma si suddivide in una parte di matematica "di base", in cui si affrontano i primi rudimenti di teoria dei numeri, e in una parte dedicata ad alcune applicazioni delle strutture matematiche introdotte, precisamente la crittografia e alla teoria codici autocorrettivi. Più in dettaglio:
a) primi rudimenti di teoria dei numeri I (classi di resto fino alla funzione e teorema di Eulero);
b) breve introduzione alla crittografia a chiave pubblica e algoritmo crittografico RSA (applicazione di (a));
c) primi rudimenti di teoria dei numeri II (polinomi a coefficienti in Z/pZ, campi finiti);
d) breve introduzione alla teoria della complessità (macchina di Turing; definizione di linguaggio; classi P, NP, NP completa; P vs NP)
e) teoria dei codici (applicazione di (c)): codici, distanza di Hamming, capacità correttiva, codici lineari, codifica e decodifica a minima distanza, in particolare decodifica a sindrome, codici ciclici, bounds (Hamming, Singleton, Gilbert-Varshamov).