Corso di Laurea Triennale in Ingegneria Informatica       
Anno Accademico 2015-2016

Algebra e Logica

Docenti:    Laura Geatti    Andrea Iannuzzi

CORSO CHIUSO
Nell'anno accademico 2016-17 il corso sara' tenuto dal prof. Fabio Gavarini


ORARIO

1o Anno, crediti 6;    1o semestre: 28 settembre 2015 - 22 gennaio 2016.

   LUNEDI MARTEDI MERCOLEDI GIOVEDI VENERDI
   ore 9:30 - 11:15         Lezione
  Aula 2 		  Lezione
  Aula 2 		  
                 
   ore 16-18         Tutorato
  Aula A1 		     

Ricevimento: alla fine della lezione in aula, oppure su appuntamento.
(Ufficio Geatti: Dipartimento di Matematica - Studio 0122, telefono: 72594628 -Edificio Sogene, Piano terra, dente 1: qui )

PROGRAMMA

    Insiemi e operazioni sugli insiemi. Funzioni iniettive, suriettive, invertibili. Cardinalita'. Induzione matematica. 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. L'anello Zn. La funzione φ di Eulero. Teorema di Lagrange, Piccolo Teorema di Fermat. Applicazioni: 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. L'algebra di Boole del Calcolo Proposizionale. Predicati e quantificatori (cenni).
    Programma settimanale e linee guida per gli esami.

    Testo consigliato:
    • S. Lipschutz, M. Lipson, Discrete Mathematics, Schaum's Outlines, McGraw-Hill 1997.

    Siti utili:


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' obbligatorio iscriversi allo scritto attraverso il sito Delphi.
    Portare un documento di riconoscimento.
    Non sono consentiti libri, appunti, telefoni, ne' alcun tipo di apparecchio On-Off.
    Non è consentito uscire durante il compito.
    Chi entra consegna.

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


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)
  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54. pdf
  • Reticoli pdf
  • Algebre di Boole pdf   Algebre di Boole in wikipedia   Calcolo Proposizionale in wikipedia
  • Funzioni booleane pdf
  • Forme minimali di una funzione polinomiale pdf


ESERCIZI

Esercizi settimanali 2015-2016
  • Esercizi 1 (insiemi e funzioni) pdf
  • Esercizi 2 (cardinalita', induzione) pdf
  • Esercizi 3 (relazioni, relazioni di equivalenza) pdf
  • Esercizi 4 (relazioni, relazioni di ordine) pdf
  • Esercizi 5 (mcd, equazioni lineari diofantee in due incognite) pdf
  • Esercizi 6 (congruenze) pdf
  • Esercizi 7 (sistemi di congruenze; calcolo modulo n) pdf
  • Esercizi 8 (i gruppi (Zn,+) e (Z*n,*)) pdf
  • Esercizi 9 (gruppi e applicazioni) pdf
  • Esercizi 10 (mix prima parte del programma) pdf
  • Esercizi 11 (introduzione ai reticoli) pdf
  • Esercizi 12 (proprieta' dei reticoli) pdf
  • Esercizi 13 (algebre di Boole) pdf
  • Esercizi 14 (espressioni booleane) pdf
  • Esercizi 15 (espressioni booleane: forma disgiuntiva completa, forme minimali) pdf
  • Esercizi 16 (logica) 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
  • Esercizi6 (reticoli) pdf    Soluzioni pdf
  • Esercizi7 (Algebre di Boole) pdf   Soluzioni pdf
  • Esercizi8 (Logica) pdf   Soluzioni pdf


VARIE

  • 7 gennaio 2016: New Mersenne prime.
  • Il matematico Laszlo Babai propone un algoritmo efficiente per il confronto di reti link
  • Ron was wrong, Whit is right pdf
  • Electronic Frontier Foundation link
  • 25 gennaio 2013: Trovato nuovo primo di Mersenne 257885161-1.
  • 15 marzo 2011: Nuovo fattore di F17.
  • 8 marzo 2010: Trovato fattore record con ECM. Vedi annuncio
  • 3 febbraio 2010: Fattorizzato F14. Vedi annuncio
  • 7 gennaio 2010: Fattorizzato RSA-768. Vedi annuncio e articolo
  • 2 novembre 2005: E` stato fattorizzato RSA640. Comunicato stampa
  • RSA Sito Ufficiale
  • Numeri di Mersenne
  • GIMPS
  • La sfera magica
  • L. Adleman: conferenza all'ACM per il premio Turing 2002.
  • 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.