Ingegneria dei Modelli e Sistemi
Anno Accademico 2007-2008, 3 bimestre.
Programma di MATEMATICA DISCRETA
PRIMA SETTIMANA:
Richiami su insiemi e operazioni sugli insiemi, funzioni iniettive,
suriettive, biettive. Cardinalita' di un insieme. Insiemi numerabili e non
numerabili.
Principi di conteggio: regola della somma e del prodotto (cardinalita'
dell'unione disgiunta e del prodotto cartesiano), principio di inclusione
esclusione, pigeon hole principle, k-sottoinsiemi ordinati e
k-sottoinsiemi non ordinati di un insieme di n elementi, sviluppo del
binomio di Newton e coefficienti binomiali, identita' di Tartaglia.
k-stringhe ordinate e k-stringhe non ordinate di n simboli con
ripetizioni.
Successioni definite per ricorrenza. Equazioni alle differenze finite di
grado k lineari a coefficienti costanti: struttura delle soluzioni,
soluzione generale nel caso omogeno, con polinomio caratteristico a
radici reali.
M.A.A.:
Cap.1, Sez. 1.1, 1.2, 1.3(no "truth tables"), 1.5.
Cap.2, Sez. 2.1, 2.2, 2.3, 2.4, 2.6.
Cap.10, Sez. 10.1.
SECONDA SETTIMANA:
Equazioni alle differenze finite di grado k lineari a coefficienti
costanti non omogenee: metodi per determinare soluzioni particolari.
Numeri complessi.
Equazioni alle differenze finite di grado 2 lineari a coefficienti
costanti, con polinomio caratteristico a radici complesse coniugate.
Esempi.
M.A.A.:
Cap.10, Sez. 10.1, 10.2, 10.4.
TERZA SETTIMANA:
Relazioni. Relazioni di ordine parziale e diagrammi di Hasse. Relazioni di
equivalenza, partizione dell'insieme in classi di equivalenza, insieme
quoziente.
Aritmetica sugli interi: divisione con resto, massimo comun divisore,
algoritmo euclideo, equazioni diofantee di primo grado. Numeri primi,
teorema fondamentale dell'aritmetica.
M.A.A.:
Cap.1, Sez. 1.4.
Dispense "Aritmetica sugli interi", p. 1-5.
QUARTA SETTIMANA:
Espressione di un numero in base arbitraria
mediante l'algoritmo euclideo. Relazione di congruenza modulo n.
Classi resto e calcolo modulo n. Congruenze e sistemi di
congruenze. Il Teorema cinese del resto.
Dispense "Aritmetica sugli interi", p. 6-10.
QUINTA SETTIMANA:
Cenni a gruppi, anelli, campi. Esempi. L'anello Zn
delle classi resto modulo n. Il gruppo degli elementi invertibili
Z*n. Calcolo dell'inverso in
Z*n. Il teorema di Lagrange, il Piccolo
Teorema di Fermat. Calcolo di potenze modulo n.
Dispense "Gruppi, anelli, campi", p. 1-9, 12-13.
SESTA SETTIMANA:
La funzione di Eulero. Equazioni in
Zn. Test di primalita' di Miller-Rabin. Il
criptosistema RSA.
Dispense "Gruppi, anelli, campi", p. 9-11, 14-15.
R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica.
SETTIMA SETTIMANA:
Radici primitive e logaritmo discreto in
Z*p. Calcolo dell'indice.
OTTAVA SETTIMANA:
Baby-steps-giant-steps per il calcolo del logaritmo discreto in
Z*p. Applicazioni del logaritmo discreto in
crittografia: Diffie-Hellman key exchange, crittosistema ElGamal.
Programma Esonero 1:
argomenti svolti nelle prime 4 settimane (entro venerdi' 28 marzo)
e relativi fogli di esercizi.
Programma Esonero 2:
argomenti svolti nelle ultime 4 settimane
e relativi fogli di esercizi.
Programma Appelli:
argomenti svolti durante le otto settimane di corso.
N.B. Gli esercizi assegnati alla fine di ogni settimana fanno
parte integrante del programma.