Corso di Laurea in Ingegneria Informatica       
Anno Accademico 2008-2009

Elementi di Algebra e Logica

Docente: Laura Geatti   Tutore: Hendrik Verhoek

CORSO CHIUSO

ORARIO

Laurea Triennale, anno 1, crediti 5.
Primo semestre (secondo emisemestre): 24 novembre 2008 -- 31 gennaio 2009

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)
• nota1: Aritmetica sugli interi, congruenze, Teorema Cinese del Resto.pdf
• nota2: Gruppi, anelli, campi. pdf

Siti utili

• 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
• L. Adleman: conferenza all'ACM per il premio Turing 2002.
• Numeri di Mersenne
• GIMPS
• La sfera magica
• Elementi di Algebra e Logica, anni passati:   2001-02   2002-03   2003-04  2004-05  




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



• Esonero 1: Soluzioni pdf
• Esonero 2: Soluzioni pdf
  
• Appello 1: Soluzioni pdf
• Appello 2: Soluzioni pdf
• Appello 3: Soluzioni pdf
• Appello 4: Soluzioni pdf
  
• Appello 5: Soluzioni pdf
  
  




ESERCIZI

• 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
• Esercizi6 (reticoli) pdf    Soluzioni (senza figure) pdf
• Esercizi7 (Algebre di Boole) pdf
• Esercizi8 (Logica) pdf   Soluzioni pdf




VARIE

• RSA Sito Ufficiale
• Foto di RSA Ron Rivest, Adi Shamir, Len Adleman.
• Foto di AKS Agrawal, Kayal, Saxena (Palo Alto, primavera 2004).
• L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria in Europa.