CORSO CHIUSO

Il corso di Elementi di Algebra e Logica da 5 crediti non esiste piu'. A partire dall'anno accademico 2011-2012, e' stato sostituito con il corso di Algebra e Logica, nell'ambito del corso di Laurea in Ingegneria Informatica:

Algebra e Logica 2011

ORARIO

Laurea Triennale, anno 1, crediti 5.
Primo semestre (secondo emisemestre): 30 novembre 2009 - 6 febbraio 2010.

PROGRAMMA

Insiemi e operazioni sugli insiemi. Funzioni iniettive, suriettive, invertibili. Cardinalita'. Induzione matematica. Funzioni definite per ricorrenza. Relazioni. Relazioni di equivalenza su un insieme, classi di equivalenza, insieme quoziente. Relazioni di ordine parziale, diagramma di Hasse di un insieme finito parzialmente ordinato, elementi massimali e minimali, massimo e minimo assoluto. Maggioranti, minoranti, estremo superiore e inferiore di un sottoinsieme. Insiemi bene ordinati. Aritmetica sui numeri interi: divisione con resto, massimo comun divisore, algoritmo euclideo. Numeri primi, Teorema Fondamentale dell'Aritmetica. Congruenze e sistemi di congruenze. Teorema cinese del resto. Aritmetica modulare. Gruppi, anelli, campi. Teorema di Lagrange, piccolo teorema di Fermat. Applicazioni: test di primalita' di Miller Rabin, sistema crittografico a chiave pubblica RSA. Reticoli, ordinamento parziale su un reticolo, Isomorfismi di reticoli. Reticoli limitati, distributivi, complementati, booleani. Algebre di Boole. Espressioni booleane: forma normale disgiuntiva, forma normale disgiuntiva completa, implicanti primi e forme minimali. Metodo del consenso. Predicati e quantificatori.
Programma settimanale e programma per gli esami.

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

• seventlab Registrazioni video delle lezioni del corso di Elementi di Algebra e Logica, tenute dal prof. Giuseppe Pareschi.
• PARI/GP computer algebra system for doing fast computations in number theory. (version 2.2.11-α) or (version 2.03.01-β for Windows)
• User's Guide to PARI/GP:   GPTutorial1    GPTutorial2
• Fattorizzazione di numeri  online
• Mathematics for Computer Science, MIT-OPEN-COURSEWARE link al corso
• Discrete Mathematics for Computer Science, Univ. of California Berkeley link al corso
• Elementi di Algebra e Logica, anni passati:   2001-02   2002-03   2003-04  2004-05   2008-09  
• Foto EAL2010 1.   2.   3.   4.   5.   6.  
• Erasmus 2010-2011 come fare: doc
• Algebre di Boole: wikipedia
• Calcolo Proposizionale: wikipedia

ESAMI

L'esame consiste in un compito scritto.
Per superare l'esame è necessario fare un compito scritto sufficiente (voto almeno 18).

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, appunti o palmari.
Non è consentito uscire durante il compito.

• Appello 1: Soluzioni: pdf
• Appello 2: Soluzioni: pdf
• Appello 3: Testo esame pdf
• Appello 4: Testo esame pdf
• Appello 5: Testo esame pdf

APPUNTI

• Preliminari pdf
• Funzioni e cardinalita' pdf
• Induzione pdf
• Relazioni 1 pdf
• Relazioni 2 pdf
• Aritmetica sugli interi, congruenze, Teorema Cinese del Resto (nota1)pdf
• Aritmetica sugli interi, etc..: complementi pdf
• Gruppi, anelli, campi pdf (nota2)
• Reticoli pdf
• Algebre di Boole pdf
• Funzioni booleane pdf
• Forme minimali di una funzione polinomiale pdf

ESERCIZI

Esercizi settimanali

• Esercizi1-2009 (insiemi, cardinalita', induzione, funz. ricorsive) pdf
• Esercizi2-2009 (relazioni) pdf
• Esercizi3-2009 (aritmetica sugli interi, congruenze) pdf
• Esercizi4-2009 (calcolo modulo n) pdf
• Esercizi5-2009 (gruppi e applicazioni) pdf
• Esercizi6-2009 (reticoli) pdf
• Esercizi7-2009 (algebre di Boole) pdf
• Esercizi8-2009 (logica & mix finale) pdf

Esercizi svolti

• Esercizi1 (insiemi, cardinalita', induzione, funz. ricorsive) pdf   Soluzioni pdf
• Esercizi2 (relazioni) pdf   Soluzioni pdf
• Esercizi3 (aritmetica sugli interi, congruenze) pdf   Soluzioni pdf
• Esercizi4 (gruppi, anelli e campi) pdf   Soluzioni pdf
• Esercizi5 (test di Miller-Rabin, criptosistema RSA) pdf   Soluzioni pdf
• Esercizi5bis (esercizi risolti sul criptosistema RSA) pdf
• Esercizi6 (reticoli) pdf    Soluzioni pdf
• Esercizi7 (Algebre di Boole) pdf
• Esercizi8 (Logica) pdf   Soluzioni pdf

VARIE

• RSA Sito Ufficiale
• L. Adleman: conferenza all'ACM per il premio Turing 2002.
• Numeri di Mersenne
• GIMPS
• La sfera magica
• Foto di RSA Ron Rivest, Adi Shamir, Len Adleman.
• Foto di AKS Agrawal, Kayal, Saxena (Palo Alto, primavera 2004).
• Erasmus 2010-2011 come fare: doc
• L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria
in Europa.