Matematica Discreta A

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I001

Crediti:

Semestre:

Sigla:

Docente

Carlo Traverso

Tel. st. 23-213, cell. 3476689739

Obiettivi di apprendimento

Il corso si propone di fornire un'introduzione ai temi di algebra astratta tramite gli esempi dell'aritmetica degli interi e dei polinomi, e dell'algebra lineare, esponendo anche alcune semplici applicazioni di interesse informatico.

Programma

Preliminari, numeri interi.
Insiemi e applicazioni. Esempi di gruppi, anelli e campi. L'anello degli interi: principio del buon ordinamento, principio di induzione. Teorema di divisione, MCD e mcm, algoritmo di Euclide, identita` di Bezout. Numeri primi, teorema di fattorizzazione unica. Numeri in base a. Congruenze, risoluzione di una congruenza lineare. L'anello Zn. Esponenziazione rapida.
Elementi di algebra astratta.
Relazioni di equivalenza, relazioni di equivalenza e applicazioni. Operazioni binarie, magma, omomorfismi, isomorfismi. Prodotto diretto. Relazione compatibile con una operazione, magma quoziente, teorema di omomorfismo. Gruppi e sottogruppi, ordine di un elemento, teorema di Lagrange, gruppi ciclici. Omomorfismi di gruppo. Anelli, divisori di zero. Prodotti diretti, sistemi di congruenze, teorema cinese dei resti. La funzione Phi di Eulero. Teorema di Fermat e di Eulero.
I polinomi.
Polinomi, teorema di divisione; radici e teorema di Ruffini; teorema di fattorialita`. Congruenze fra polinomi, l'anello K[x]/f(x).
Applicazioni.
Crittografia a chiave pubblica.
Sistemi e matrici.
Operazioni sulle matrici, operazioni elementari per riga e per colonna, matrici elementari. Sistemi lineari, algoritmo di Gauss. Matrici invertibili e calcolo della matrice inversa.
Algebra lineare.
Spazi vettoriali, sottospazi. Intersezione, e somma di sottospazi, supplementare di un sottospazio. Basi e cambiamenti di basi, coordinate. Dimensione di uno spazio vettoriale. Rango, teorema di Rouche'-Capelli. Applicazioni lineari e matrici associate, nucleo e immagine e formula delle dimensioni. Dimensione dello spazio delle soluzioni di un sistema lineare omogeneo. Formula di Grassmann. Lo spazio vettoriale Hom(V,W).
Determinante e diagonalizzazione.
Determinante e sue proprieta`, teorema di Binet. Applicazioni e matrici diagonalizzabili, autovalori e autovettori, teorema di diagonalizzazione.
Applicazioni.
Interpolazione di Lagrange, codici correttori.

Ore lezione:

Ore esercitazione:

Bibliografia

L. Childs, ``Algebra, un'introduzione concreta'', ETS, Pisa
F. Odetti, M. Raimondo, ``Elementi di algebra lineare e geometria analitica'', ECIG, Genova

Modalità di esame

Scritto e orale