Corso di Laurea in Ingegneria Informatica
Anno Accademico 2008-2009
Primo semestre (emisemestre 2)
Programma di ELEMENTI DI ALGEBRA E LOGICA



PRIMA SETTIMANA: Insiemi ed operazioni sugli insiemi. Funzioni iniettive, suriettive, invertibili. Cardinalita'. Induzione matematica. Funzioni definite per ricorrenza.
L&L., Cap I, Sez.1,2,3,4,5,6,7,8,9,10. Cap III: Sez.1,2,3,5,6,7, Eserc. 3.13, 3.16, 3.28.
Esercizi 1.

SECONDA SETTIMANA: 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, sup e inf di un sottoinsieme. Insiemi totalmente ordinati, insiemi bene ordinati.
Aritmetica sui numeri interi: divisione con resto, divisibilita', massimo comun divisore. L'algoritmo euclideo per il calcolo del massimo comun divisore.
L&L., Cap.II: Sez.1,2,3,4,6,8,9, Cap.XIV: Sez.3,5,7.
nota1: pag.1-4.
Esercizi 2.

TERZA SETTIMANA: Versione estesa dell'algoritmo di Euclide. Equazioni lineari diofantee in due incognite. Congruenze modulo n.
nota1: pag.5-8.
Esercizi 3: eccetto n. 18, 24.

QUARTA SETTIMANA: Sistemi di congruenze. Il Teorema Cinese del Resto. Gruppi, anelli e campi: esempi. Il gruppo additivo Zn, il gruppo moltiplicativo Zn*. Il campo Zp, con p primo. Il teorema di Lagrange. Il Piccolo Teorema di Fermat. Applicazioni al calcolo di potenze modulo n (cenni).
nota1: pag.9-11.
nota2: pag.1-6; pag.6-9 (cenni).
Esercizi 3: n.18, 24.
Esercizi 4: n.1-10.

QUINTA SETTIMANA: Il criptosistema RSA. Il test di primalita' di Miller Rabin.
R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica.
nota2: pag.15-17.
Esercizi 5.

SESTA SETTIMANA: Reticoli: assiomi di definizione, ordinamento parziale su un reticolo, isomorfismi di reticoli. Esempi. Reticoli limitati, reticoli distributivi, reticoli complementati, reticoli booleani.
L&L., Cap.XIV: Sez. 8 (tranne dualita' e Teorema 14.2), 9, 10,11.
Esercizi 6.

SETTIMA SETTIMANA: Algebre di Boole. L'algebra di Boole del calcolo proposizionale. Espressioni booleane: forma normale disgiuntiva (somma di prodotti), forma normale disgiuntiva completa (somma di prodotti completa).
L&L., Cap.XV: Sez.1,2,4,5,6,7,8 ed esercizi: 15.1, 15.2, 15.3, 15.5 (cenni), 15.6 (cenni), 15.7 (cenni), 15.8 (cenni), 15.10 -- 15.14.
Esercizi 7 (parte 1), Esercizi 8 (parte 1). Cap.IV: Sez.1,2,3, 5,6,7,8.

OTTAVA SETTIMANA: Espressioni booleane: implicanti primi, forme minimali. Metodo del consenso per la determinazione degli implicanti primi. Predicati e quantificatori.
L&L., Cap.XV: Sez.9, esercizi: 15.15 -- 15.21, 15.53 -- 15.59. Cap.IV: Sez.11, 12, esercizi 4.3 -- 4.7, 4.10, 4.17 -- 4.20.





N.B. Gli esercizi presenti sulla pagina web del corso fanno parte integrante del programma.





Programma Esonero 2:
argomenti svolti nelle ultime 4 settimane;
Esercizi 4: n. 5 -- 24.
Esercizi 5: esclusi n. 3, 4, 10, 11, 12, 13.


Programma Appelli:
argomenti svolti durante le otto settimane di corso ed Esercizi 1,2,3,4,5,6,7,8.
N.B.: Esercizi 5: esclusi n. 3, 4, 10, 11, 12, 13.