- Oggetto:
- Oggetto:
Algebra Computazionale
- Oggetto:
Anno accademico 2007/2008
- Codice dell'attività didattica
- S8494
- Docente
- Prof. Umberto Cerruti (Titolare del corso)
- Corso di studi
- Laurea Magistrale in Matematica
- Anno
- 4° anno 5° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- A scelta dello studente
- Crediti/Valenza
- 7
- SSD dell'attività didattica
- MAT/02 - algebra
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
Il corso di Algebra Computazionale ha quattro obiettivi principali:1) Porre le basi per la comprensione delle tecniche attualmente utilizzate nei test di primalità, nella fattorizzazione degli interi e nello studio delle successioni di numeri interi.
2) Evidenziare l'importanza degli aspetti computazionali della Matematica, cioè dei tentativi di rispondere a domande del tipo: "come si fa a ... "
3) Mostrare l'unità della Matematica, attraverso lo studio di problematiche, come il "riconoscimento dei numeri primi", che provengono dall'antichità e che hanno coinvolto molti settori di ricerca: Teoria dei Numeri, Algebra, Analisi, Combinatoria, Geometria ...
4) Dare il giusto rilievo al lato estetico della Matematica, alla sorpresa e alla meraviglia che derivano dai teoremi. E' proprio lo stupore che ha spinto molti grandi matematici, come Eulero e Gauss, a dare diverse dimostrazioni di un medesimo risultato. Ciò che conta non è solo il luogo dove si giunge, ma anche la strada che si fa per arrivarci.
- Oggetto:
Risultati dell'apprendimento attesi
Gli studenti apprendono alcune tecniche matematiche utili e significative che riguardano, tra l'altro, i numeri primi, la fattorizzazione, le successioni ricorrenti, le curve ellittiche, le frazioni continue e le loro applicazioni informatiche.- Oggetto:
Programma
Pre-requisiti in ingresso e competenze minime in uscita
Pre-requisiti (in ingresso)
Insegnamenti fornitori
Una buona conoscenza delle basi dell’algebra e della matematica discreta
Matematica Discreta, Algebra I e Algebra II
Competenze minime (in uscita)
Insegnamenti fruitori
Complessità computazionale. Metodi avanzati per testare la primalità di un numero e per la fattorizzazione. Distribuzione dei numeri primi: teoremi di Chebyshev e di Bertrand. Caratteri dei gruppi abeliani. Conseguenze della ERH. Teorema AKS. Applicazioni della teoria delle curve ellittiche. Frazioni continue e loro applicazioni. Problemi di irrazionalità e trascendenza.
Il corso prepara alla ricerca e viene utilizzato per la stesura di tesi e per il Dottorato. Gli argomenti hanno applicazioni pratiche, per esempio alla Crittografia.
6. Programma, articolazione e carico didattico
Argomento
Ore
Lezione
Totale Ore di Carico Didattico
Successioni ricorrenti. Metodi di primalità e fattorizzazione.
12
12
Caratteri dei gruppi abeliani finiti e caratteri modulari.
6
6
Complessità computazionale. Distribuzione dei numeri primi, teoremi di Chebyshev e Bertrand, conseguenze della ERH. Teorema AKS.
16
16
Applicazioni della teoria delle curve ellittiche.
10
10
Frazioni Continue e applicazioni. Irrazionalità e trascendenza.
12
12
Totale
56
56
Il corso tratta di argomenti di teoria dei numeri, con particolare attenzione agli aspetti computazionali. Il programma può variare di anno in anno. Quello che segue è relativo all'a.a. 2006-07.
Complessità computazionale, problemi P, NP, NP-completi. Crittografia a chiave pubblica, Knapsack e RSA. Successioni ricorrenti del secondo ordine. Criteri di Lucas, Pepin, Pocklington, Morrison. Numeri primi di Mersenne e di Fermat. Caratteri dei gruppi abeliani finiti. Trasformata discreta di Fourier. Caratteri modulari e funzioni L di Dirichlet. La distribuzione dei primi. Teoremi di Chebyshev, di Bertrand etc. La congettura di Riemann e la congettura di Riemann estesa. Loro conseguenze. Il Teorema di Agrawal, Kayal e Saxena (AKS). Il gruppo delle curve ellittiche. Strutture deboli. Metodi ECM e ECPP. Frazioni continue e loro applicazioni. L'equazione di Pell. Cenni su irrazionalità e trascendenza.Testi consigliati e bibliografia
- Oggetto:
- Vedi in Materiale DidatticoMateriale didattico
I testi base consigliati per il corso sono:1. Victor Shoup A computational introduction to number theory Cambridge University Press ( Il testo viene distribuito gratuitamente qui: http://shoup.net/ntb/
2. K. Ireland, M. Rosen A classical introduction to modern number theory Springer
3. Hans Riesel - Prime numbers and computer methods for factorization Birkhauser
4. Richard Crandall, Carl Pomerance - Prime numbers : a computational perspective - Springer
E fortemente consigliato lutilizzo del seguente materiale per approfondimenti e integrazioni:
1. Andrew M. Rockett, Peter Szusz - Continued fractions - World scientific
2. Song Y. Yan Number Theory for Computing - Springer
- Oggetto:
Note
Modalità di verifica/esame
L'esame si svolge, di norma, come segue:
lo studente scrive una relazione su un argomento concordato con il docente e la presenta in un seminario davanti alla commissione.- Oggetto: