Corso di Laurea in Ingegneria dei Modelli e Sistemi
Anno Accademico 2007-2008

MATEMATICA DISCRETA

Docente: LAURA GEATTI

CORSO CHIUSO



ORARIO

3 bimestre: 3 marzo - 24 aprile 2008.
Ricevimento: Mercoledi', ore 16, Aula 5PP2.



PROGRAMMA

Richiami di teoria degli insiemi. Cardinalita'. Elementi di calcolo combinatorio. Numeri complessi. Funzioni definite per ricorrenza ed equazioni alle differenze finite. Relazioni e grafi diretti. Relazioni di ordine parziale. Relazioni di equivalenza, insieme quoziente. Aritmetica sui numeri interi. Congruenze e sistemi di congruenze. Teorema cinese del resto. Cenni a gruppi, anelli e campi. L'anello delle classi resto Zn . Funzione di Eulero. Teorema di Lagrange. Piccolo Teorema di Fermat. Test di primalita'. Il criptosistema RSA. Radici primitive e logaritmo discreto in Zp *. Calcolo dell'indice e baby-steps-giants-steps. Applicazioni del logaritmo discreto in crittografia: Diffie-Hellman-Merkle key exchange, criptosistema ElGamal.
Programma settimanale e Programma per gli esami.

Riferimenti bibliografici:
  • R.J. McEliece, R.B. Ash, C. Ash, Introduction to Discrete Matematics, McGraw-Hill Book Comapny
  • K. Rosen, Discrete mathematics and its applications, McGraw-Hill International Editions
  • R. Lidl, G. Pilz, Applied Abstract Algebra, UTM, Springer-Verlag

Siti utili:

ESAMI

L'esame consiste in un compito scritto.
Per superare l'esame e' necessario fare un compito scritto sufficiente oppure i due esoneri entrambi sufficienti.

Per partecipare agli scritti, e' necessario iscriversi mediante il MODULO predisposto di volta in volta su questo sito.
Presentarsi con un documento di riconoscimento.
Non e' consentito uscire durante gli scritti.
Non sono consentiti libri, appunti o palmari.

Appelli sessione invernale

Esonero 1: Risultati html Soluzioni pdf
Esonero 2 & Appello 1: Risultati html Soluzioni esonero 2 pdf Soluzioni appello 1 pdf
Appello 2: Risultati html   Soluzioni pdf (in arrivo)

Appelli sessione autunnale

Appello 3: venerdi' 12 settembre 2008, ore 10,30 -- 12,30, Aula 2 PP1
Appello 4: 11 ottobre 2008, ore 11-13, Ufficio Geatti



APPUNTI ED ESERCIZI

  • Numeri complessi (con esercizi) pdf
  • Aritmetica sugli interi pdf
  • Gruppi, anelli, campi pdf
  • La funzione di φ di Eulero pdf
  • Miller-Rabin primality test in Wikipedia
  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica,
    Didattica delle Scienze 137 (1988), 48–54. (pdf)
    Per aggiornamenti su fattorizzazione, test di primalita', etc..., vedi "Numerologia" in TEN2007)
  • Fattorizzazione interattiva
  • RSA demo    Gli inventori Adi Shamir, Ron Rivest, Len Adelman: foto
  • L. Adleman: conferenza all'ACM per il premio Turing 2002.
  • Nota sulle radici primitive modulo p pdf.
  • Baby-step-Giant-step method in Wikipedia.    L'inventore Dan Shanks: foto
  • Calcolo dell'indice in Wikipedia.
  • Calcolo di un logaritmo discreto usando il metodo del calcolo dell'indice: Esempio.
  • ElGamal encryption in Wikipedia.    L'inventore Taher ElGamal: foto
  • Diffie-Hellman-Merkle key exchange in Wikipedia.    Gli inventori Ralph Merkle, Martin Hellman, Whit Diffie: foto


Esercizi settimanali
  • Esercizi1: (Insiemi, funzioni, cardinalita', induzione, funz. ricorsive) pdf
  • Soluzioni Esercizi1 pdf
  • Altri esercizi su questi argomenti da corsi di anni passati: pdf, pdf, pdf.

  • Esercizi2: (equazioni alle differenze finite) pdf
  • Altri esercizi su questi argomenti da corsi di anni passati: pdf

  • Esercizi3: (Relazioni, aritmetica sugli interi) pdf
  • Altri esercizi su questi argomenti da corsi di anni passati: pdf, pdf

  • Esercizi4: (aritmetica sugli interi, congruenze, sistemi di congruenze) pdf
  • Altri esercizi su questi argomenti da corsi di anni passati: pdf, pdf, pdf, pdf, pdf

  • Esercizi5: (gruppi, anelli, campi, Zn, Z*n ) pdf
  • Altri esercizi su questi argomenti da corsi di anni passati: pdf

  • Esercizi6: (Test di primalita', RSA) pdf

  • Esercizi7: (Logaritmo discreto) pdf

  • Esercizi8: (Logaritmo discreto e applicazioni in crittografia) pdf








  • L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria in Europa.