Course Syllabus
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 autocorrezione di errore, e i fondamenti che vengono utilizzate per garantire la sicurezza dei piu' diffusi sistemi
crittografici moderni.
-
Conoscenza e capacità di comprensione
Al termine del corso, lo studente avrà acquisito una comprensione di base della matematica discreta, con particolare riferimento a: aritmetica modulare, congruenze, classi di resto, elementi introduttivi di teoria dei gruppi,
nozioni fondamentali di crittografia classica e teoria dei codici correttori d’errore. -
Capacità di applicare conoscenza e comprensione
Lo studente sarà in grado di applicare i concetti e le tecniche apprese per risolvere problemi concreti e formulare soluzioni in ambiti legati all’informatica, come la sicurezza dei dati e la trasmissione affidabile delle informazioni. -
Autonomia di giudizio
Lo studente svilupperà la capacità di ragionare in modo critico e autonomo sui concetti teorici appresi, analizzando la correttezza e l’efficacia di metodi matematici in contesti informatici. -
Abilità comunicative
Lo studente sarà in grado di esporre in modo chiaro e rigoroso i concetti matematici studiati, utilizzando il linguaggio simbolico e tecnico appropriato, sia in forma scritta che orale. -
Capacità di apprendere
Lo studente acquisirà strumenti logico-matematici che gli permetteranno di affrontare autonomamente l’apprendimento di contenuti più avanzati nell’ambito della matematica e dell’informatica teorica.
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. Codici ciclici.
Breve Introduzione ad alcuni sistemi CAS (Computer Algebra System) e.g. Magma, GAP, gp/pari o Sagemath.
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: F_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.
Le attività previste sono: 48 ore di lezione frontale in modalità erogativa e 20 ore di esercitazione frontale in
modalità erogativa.
Materiale didattico
Note del corso disponibili sulla piattaforma e-learning.
Testi di riferimento:
Childs, Lindsay N. "A concrete introduction to higher algebra. Second edition". Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1995.
Koblitz, Neal "A course in number theory and cryptography". Graduate Texts in Mathematics, 114. Springer-Verlag, New York, 1987.
Craven, David "Computing with Magma", https://web.mat.bham.ac.uk/D.A.Craven/docs/lectures/magma.pdf
Periodo di erogazione dell'insegnamento
Primo semestre.
Modalità di verifica del profitto e valutazione
L'accesso all'esame scritto richiede il superamento di una prova informatizzata.
Per accedere a tale prova e' necessario iscriversi al portale di WIMS https://wims.matapp.unimib.it/
Su tale portale sono disponibili 10 test di autovalutazione (uno per settimana di corso) che verranno gradualmente attivati.
Siete caldamente esortati a risolverli poiche' parte dell'esame consistera' in esercizi selezionati tra quelli dei test.
Non si effettueranno prove in itinere.
Al termine del corso verra' attribuito un bonus di xx punti se conseguito un punteggio yy ove
- xx=2 per 27<yy≤30;
- xx=1.5 per 22<yy≤27;
- xx=1 per 18≤yy<22.
Il bonus resta valido fino all'inizio del corso dell'anno successivo.
L'esame è suddiviso in cinque fasi:
- Test a scelta multipla per accertarsi che i concetti base siano stati acquisiti. Qui viene valutata l'esattezza delle risposte (max. 10 punti)
- Se sufficiente tale test dà accesso alla prova scritta consistente nella risoluzione di alcuni esercizi di routine (max. 10 punti)
- Assegnazione di un esercizio in cui si valuta la capacita' di rielaborare ed utilizzare la teoria ai fini del problem-solving (max. 6 punti)
- Richiesta di delineare uno dei Teoremi cardine del corso fornendo cenni di dimostrazione ed esempi (max. 4 punti)
- Prova orale richiede l'esposizione di asserti e dimostrazioni di teoremi, le definizioni, gli esempi/controesempi e le tecniche di calcolo.
E' obbligatoria per chi consegue nelle precedenti fasi un punteggio inferiore a 21, facoltativa altrimenti;
a chi consegue voto >= 27 e non sostiene l'orale verrà verbalizzato 27.
Non viene attribuito a priori nessun peso relativo alla prova orale rispetto alle precedenti prove.
Le prime due fasi vengono svolte accedendo alla piattaforma WIMS https://wims.matapp.unimib.it/
Orario di ricevimento
Su appuntamento.
Sustainable Development Goals
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.
-
Knowledge and understanding
By the end of the course, students will have acquired a foundational understanding of discrete mathematics, focusing on modular arithmetic, congruences, residue classes, basic elements of group theory, and introductory notions of classical cryptography and error-correcting codes. -
Applying knowledge and understanding
Students will be able to apply the learned concepts and techniques to solve practical problems and develop solutions in areas related to computer science, such as data security and reliable data transmission. -
Making judgements
Students will develop the ability to critically and independently analyze the theoretical concepts, evaluating the correctness and effectiveness of mathematical methods in computing contexts. -
Communication skills
Students will be able to clearly and rigorously explain the studied mathematical concepts, using appropriate symbolic and technical language, both in written and oral form. -
Learning skills
Students will acquire logical and mathematical tools that enable them to autonomously pursue further learning in advanced topics in mathematics and theoretical computer science.
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.
Brief Introduction to some CAS (Computer Algebra System) e.g. Magma, GAP, gp/pari or Sagemath.
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: F_p, with p a prime number. The ring of polynomials in one variable. Construction of finite fields using
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
Frontal lessons, exercises, individual study supported by e-learning teaching materials. The course is taught in
Italian.
The planned activities are: 48 hours of frontal lessons in delivery mode and 20 hours of frontal exercises in
delivery mode.
Textbook and teaching resource
Course notes avalaible on the e-learning platform.
Textbooks:
Childs, Lindsay N. "A concrete introduction to higher algebra. Second edition". Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1995.
Koblitz, Neal "A course in number theory and cryptography". Graduate Texts in Mathematics, 114. Springer-Verlag, New York, 1987.
Craven, David "Computing with Magma", https://web.mat.bham.ac.uk/D.A.Craven/docs/lectures/magma.pdf
Semester
First semester.
Assessment method
In order to access the written assessment one has to pass a computer assisted exam.
This requires inscription to the WIMS platform https://wims.matapp.unimib.it/
There 10 tests are available (one for each week of lectures). They will be gradually activated.
Their resolutions will allow you to tune in with the course contents. Moreover the first part of the exam will consist of a few
exercises selected among those of all tests.
There will be no partial assessments.
At the end of the lectures a bonus of xx will be assigned to a yy score according to following table:
- xx=2 if 27<yy≤30;
- xx=1.5 if 22<yy≤27;
- xx=1 if 18≤yy<22.
The bonus remains valid until the beginning of the following year's course.
The exam is divided into five phases:
- Multiple choice test to ensure that the basic concepts have been acquired. Here the accuracy of the answers is assessed (max. 10 points)
- If sufficient, this test gives access to the written test consisting of the resolution of some routine exercises (max. 10 points)
- Assignment of an exercise in which the ability to rework and use the theory for problem-solving purposes is assessed (max. 6 points)
- Request to outline one of the key theorems of the course providing hints of demonstration and examples (max. 4 points)
- Oral exam requires the presentation of assertions and demonstrations of theorems, definitions, examples/counterexamples and calculation techniques.
It is mandatory for those who obtain a score lower than 21 in the previous phases, optional otherwise;
for those who obtain a grade >= 27 and do not take the oral exam will be verbalized 27.
No weight is attributed a priori to the oral exam compared to the previous exams.
The first two phases are carried out by accessing the WIMS platform https://wims.matapp.unimib.it/
Office hours
By appointment
Sustainable Development Goals
Staff
-
Andrea Previtali
