- Oggetto:
- Oggetto:
Algebra Computazionale (DM 270) - a.a. 2012/13
- Oggetto:
Anno accademico 2012/2013
- Codice dell'attività didattica
- MFN0417
- Docente
- Prof. Umberto Cerruti (Titolare del corso)
- Corso di studi
- Laurea Magistrale in Matematica (D.M. 270)
- Anno
- 1° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- D.M. 270 - TAF C
- Crediti/Valenza
- 6
- SSD dell'attività didattica
- MAT/02 - algebra
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Orale
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
Il corso di Algebra Computazionale ha quattro finalità 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. Lo studente apprenderà i metodi attuali per determinare la primalità di un intero, la complessità di alcuni problemi algebrici, le utilizzazioni del gruppo delle cubiche, diverse tecniche contemporanee legate alle frazioni continue.
- Oggetto:
Risultati dell'apprendimento attesi
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 RH e della ERH. Teorema AKS. Applicazioni della teoria delle curve ellittiche. Frazioni continue e loro applicazioni. Equazione di Pell e unità quadratiche. Legami tra matrici, frazioni continue e ricorrenze.
- Oggetto:
Programma
Complessità computazionale. Classi P e NP.
Problema dei numeri primi, teorema di Pratt.
Esistono infiniti numeri primi: dimostrazioni di Euclide, Eulero, Polya, Erdos, Fustenberg…
Per ogni n esistono infiniti primi congrui a 1 modulo n.
Primalità: algoritmi deterministici e non polinomiali, polinomiali e non deterministici, polinomiali e deterministici ma condizionati.
Applicazioni del gruppo delle curve ellittiche alla primalità e alla fattorizzazione.
Il teorema AKS: metodo polinomiale, deterministico e non condizionato.
Il teorema di Nair.
Teoremi di Chebyshev e di Bertrand.
Caratteri dei gruppi abeliani finiti e funzioni L di Dirichlet.
Condizioni equivalenti alle congetture RH e ERH.
Frazioni continue.
Irrazionalità quadratiche.
Equazione di Pell e unità quadratiche.
Matrici, frazioni continue e ricorrenze lineari.
Computational complexity. P and NP classes.
Prime is in NP: Pratt’s theorem.
Several proofs of the infinitude of primes: Euclid, Euler, Polya, Erdos, Fustenberg…
There exists infinitely many prime congruent to 1 mod n, for every n.
Primality testing.
Elliptic curves and their applications to primality, factorization, cryptography.
AKS theorem.
Nair’s theorem.
Theorems of Chebyshev and Bertrand.
Characters of finite abelian groups and Dirichlet L functions.
RH and ERH equivalences.
Continued fractions.
Quadratic irrationalities.
Pell’s equation and quadratic units.
Matrices, continued fractions and linear recurrences.
Testi consigliati e bibliografia
- Oggetto:
Richard Crandall, Carl Pomerance - Prime numbers : a computational perspective - OPERA 223 Andrew M. Rockett, Peter Szusz - Continued Fractions - 11A 1992.ROCKET Victor Shoup - A Computational Introduction to Number Theory and Algebra - http://www.shoup.net/ntb/
- Oggetto:
Note
ALGEBRA COMPUTAZIONALE, MFN0417, 6 CFU: 6 CFU, MAT/02, TAF C (affine o integrativo), Ambito attività formative affini o integrative.
Modalità di esame:
Lo studente concorda con me un argomento da trattare, e scrive una relazione di 30/35 pagine, da consegnarsi in formato pdf per via elettronica. Espone poi il suo lavoro durante un seminario della durata di un'ora.
Vengono valutati, per assegnare il voto, il contenuto e la chiarezza del testo, e le capacità espositive e la comprensione della materia da parte del candidato.
- Oggetto:
