Docenti: Laura GEATTI
e
Giuseppe PARESCHI
Tutore: Valerio TALAMANCA
CORSO CHIUSO
PROGRAMMA
Insiemi: operazioni sugli insiemi, induzione matematica. Relazioni: chiusura di relazioni, relazioni di equivalenza, ordinamenti
parziali.
Funzioni: funzioni iniettive, suriettive, invertibili; crescita logaritmica, polinomiale, esponenziale; complessita'
degli algoritmi; famiglie di insiemi, cardinalita'.
Proprieta' dei numeri interi e applicazioni: algoritmo della divisione, numeri primi, massimo comun divisore, algoritmo euclideo,
fattorizzazione in numeri primi; congruenze, aritmetica modulare, teorema di Fermat, sistema crittografico a chiave pubblica RSA.
Insiemi ordinati e reticoli: insiemi ordinati, diagrammi di Hasse, estremo superiore ed estremo inferiore, reticoli, reticoli distributivi;
complementi.
Logica e algebre di Boole: forme proposizionali, tautologie e contraddizioni, equivalenza logica, algebra delle forme proposizionali;
condizionali e bicondizionali, predicati e quantificatori, negazione; algebre di Boole, algebre di Boole come reticoli, espressioni in somme di
prodotti, espressioni minimali, circuiti logici.
Programma dettagliato
Testi consigliati
S. Lipschutz, M. Lipson,
Discrete Mathematics,
Schaum's Outlines, McGraw-Hill 1997.
R. Schoof , Fattorizzazione e criptosistemi a chiave pubblica,
Didattica delle Scienze 137 (1988), 48–54.
pdf
Siti utili
Corso Elementi di Algebra e Logica, AA. 2002–2003
Corso Elementi di Algebra e Logica, AA. 2001–2002
Fattorizzazione di numeri
La sfera magica
Numeri di mersenne
Il piu' grande numero primo
GIMPS
RSA
RSA demo
Sfide RSA
RSA Foto1: Shamir, Rivest,
Adleman
RSA Foto2: Rivest, Shamir,
Adleman
AKS Agrawal, Kayal,
Saxena
ESAMI
L'esame consiste in un compito scritto.
Per superare l'esame è necessario fare un compito
scritto sufficiente, oppure i due esoneri entrambi sufficienti.
Per partecipare agli scritti, e' necessario iscriversi nelle liste predisposte
di volta in volta su questo sito.
Portare un documento di riconoscimento.
Non sono consentiti libri o appunti.
Non è consentito uscire durante il compito.
Soluzioni Esonero 1.
Soluzioni Esonero 2.
Soluzioni Appello 1.
Soluzioni Appello 2.
Soluzioni Appello 3.
Soluzioni Appello 4.
APPUNTI ED ESERCIZI
- Appunti1 (aritmetica sugli interi, congruenze, Teorema Cinese del Resto) pdf
- Appunti2 (Gruppi, anelli, campi) pdf
- Esercizi1 (insiemi, cardinalita', induzione, funz. ricorsive) pdf
- Esercizi2 (relazioni) pdf
- Esercizi3 (aritmetica sugli interi, congruenze) pdf
- Esercizi4 (gruppi, anelli) pdf
- Esercizi5 (RSA, test di primalita') pdf
- Esercizi6 (reticoli) pdf
- Esercizi7 (algebre di Boole) pdf
- Esercizi8 (logica) pdf
VARIE
