Syllabus del corso
Obiettivi
Lo studente sarà in grado di utilizzare alcuni strumenti dell'algebra astratta per risolvere ed analizzare alcuni problemi legati al mondo dell'informatica. Ad esempio, i fondamenti che permettono di utilizzare i codici per sistemi di auto correzione di errore, e i fondamenti che vengono utilizzate per garantire la sicurezza dei piu' diffusi sistemi crittografici moderni.
Contenuti sintetici
Introduzione alle strutture algebriche di base. Aritmetica modulare, campi finiti e gruppi di permutazioni. Breve introduzione alla crittografia. Teoria dei codici, codici lineari ed esempi classici di codici lineari.
Programma esteso
Richiami di base di aritmetica. Teorema fondamentale dell'aritmetica. Scomposizione in fattori primi. Algoritmo Euclideo delle divisioni successive per il calcolo del massimo comune divisore tra tue interi. Studio dei tempi di calcolo di questo algoritmo.
Richiami sulle relazioni di equivalenza. Congruenze modulo n. Insieme quoziente Z/nZ. Operazioni su un insieme numerico, strutture algebriche.
Strutture algebriche: gruppi e anelli. Sottogruppi normali, ideali di un anello, morfismi. Gruppi di permutazioni: numero di permutazioni e proprieta' fondamentali del gruppo simmetrico.
Struttura di Z/nZ . Congruenze lineari. Teorema cinese del resto. Funzione phi di Eulero e il suo uso in problemi di fattorizzazione.
Teorema di Eulero generalizzato. Descrizione del sistema crittografico RSA. Test di primalita'.
Campi finiti: Z_p con p un numero primo. Anello dei polinomi su un campo. Costruzione dei campi finiti a partire dall'anello dei polinomi.
Introduzione ai codici correttori di errore e ai codici lineari.
Prerequisiti
Sono necessarie le conoscenze matematiche della scuola media superiore e i contenuti del corso di Fondamenti dell'Informatica.
Modalità didattica
Lezioni frontali, esercitazioni, studio individuale supportato da materiali didattici in e-learning. Il corso e' erogato in italiano. Nel periodo di emergenza Covid-19 le lezioni si svolgeranno completamente da remoto sincrono e asincrono con alcuni eventi in presenza fisica.
Materiale didattico
Note del corso disponibili sulla piattaforma e-learning.
Testi di riferimento:
Elementi di Matematica Discreta e Algebra Lineare, Francesca Dalla Volta e Marco Rigoli, Pearson Education.
A Course in Number Theory and Cryptography, Neal Koblinz, Springer Verlag.
Periodo di erogazione dell'insegnamento
Primo semestre.
Modalità di verifica del profitto e valutazione
Esame scritto.
L'esame scritto consiste in
a) domande a risposta aperta di ragionamento e deduzione
b) nella risoluzione di esercizi che richiedono calcolo o sviluppo di una
soluzione ad un problema assegnato.
Prove parziali
Sono previste verifiche parziali a meta' corso e a fine corso che consistono in
a) domande a risposta aperta di ragionamento e deduzione
b) nella risoluzione di esercizi che richiedono calcolo o sviluppo di una soluzione a un problema dato.
Il superamento delle prove parziali sostituisce l'esame scritto.
Esame orale: facoltativo
Nel periodo di emergenza Covid-19 gli esami orali saranno solo telematici. Verranno svolti utilizzando la piattaforma WebEx e nella pagina e-learning dell'insegnamento verrà riportato un link pubblico per l'accesso all'esame di possibili spettatori virtuali.
Valutazione: voto finale
Orario di ricevimento
Su appuntamento.
Aims
At the end of the course the student is able to apply some results from abstract algebra to analyse and solve problems related to computer science. For instance, the basic rules used in the error-correcting codes, and the basic rules used to guarantee a high level of security in the modern cryptographic systems.
Contents
Introduction to the elementary algebraic structures. Modular arithmetic, finite fields and permutation groups. Brief introduction to cryptography. Coding theory, linear codes and classical examples of linear codes.
Detailed program
Basic Arithmetic. Fondamental theorem of arithmetic. Decomposition of a number in prime factors.
Review of Equivalence Relations. Congruences modulo n. Quotient sets and the example Z/nZ. Review of the basic operations in number field. Algebraic structures.
Algebraic structures: groups and rings. Normal subgroups, ideals of a ring, morphisms. Permutation groups: number of permutations and basic properties of the symmetric group.
The algebraic structure of the ring Z/nZ . Linear congruences and the Chinese remainder theorem. The Euler phi-function and its application to factorization problems.
Generalized Euler's theorem. Introduction on the RSA. Primality tests.
Finite fields: Z_p, with p a prime number.The ring of polynomials in one variable. Construction of finite fields using the polynomial rings.
Introduction to error-correcting codes and linear codes.
Prerequisites
The student is supposed to be familiar with the mathematics studied in High School and with the mathematical contents in the course Fondamenti dell'Informatica
Teaching form
Lectures, exercise classes, personal study supported by the e-learning platform. The course is delivered in italian.
Textbook and teaching resource
Course notes avalaible on the e-learning platform.
Textbooks:
Elementi di Matematica Discreta e Algebra Lineare, Francesca Dalla Volta e Marco Rigoli, Pearson Education.
A Course in Number Theory and Cryptography, Neal Koblinz, Springer Verlag.
Semester
First semester.
Assessment method
Written exam.
The written exam consists in
a) open-ended reasoning questions
b) solving numerical exercises or problems
Mid-term and end of term exams are provided. They consist in
a) open-ended reasoning questions
b) solving numerical exercises or problems
The mid-term and end of term exams substitute the written exam.
Oral exam: optional
Assessment: final mark
Office hours
On appointment.
Scheda del corso
Staff
-
Marina Avitabile