LINEE GUIDA PER GLI SCRITTI:
L'esame consiste in un compito scritto e verte sul programma svolto in classe durante il corso: teoria ed esercizi, come specificato nel programma dettagliato qui sotto. Gli esercizi assegnati ogni settimana fanno parte integrante del programma.
Il compito consiste in un certo numero di esercizi. Saranno richieste anche definizioni e semplici dimostrazioni.
Lo svolgimento degli esercizi deve contenere spiegazioni CHIARE, SINTETICHE, e COMPLETE: non sara' dato punteggio a risposte non motivate, anche se corrette.
AVVISO: chi deve fare un esame integrativo, perche' proveniente da altro corso di studi, e' pregato di contattarmi per fissare gli argomenti dell'esame. Inoltre mi avvisi qualche giorno prima dell'appello, in modo che io possa preparare il testo su misura.
Chi deve fare l'esame da 6 crediti: e' pregato di farmelo sapere prima dello scritto. Il programma non include calcolo combinatorio e grafi (cioe' gli argomenti delle settimane 11,12,13,14).
Prima settimana:
Insiemi e sottoinsiemi. L'insieme vuoto. Uguaglianza fra insiemi. Operazioni sugli insiemi: unione, intersezione, complementare, prodotto cartesiano, insieme delle parti. Esempi. Alcune proprieta' delle operazioni di unione e intersezione: associativita', distributivita', etc..
Preliminari pdf
Wikipedia wiki
Tavola riassuntiva link
Funzioni tra insiemi. Dominio, codominio, immagine. Funzioni iniettive, suriettive, biiettive. Composizione di funzioni. Associativita' della composizione. Funzione identita'. Inversa di una funzione biiettiva. Esempi.
Funzioni-Cardinalita', Sez. 1,2,3,4. pdf
Funzioni fra insiemi finiti. Permutazioni di un insieme. Cardinalita' di un insieme. Insiemi numerabili. Gli interi sono numerabili.
Funzioni-Cardinalita', Sez. 5. pdf; Esercizi1-svolti: n.1-15.
Seconda settimana:
I numeri naturali sono totalmente ordinati. Principio del minimo. Principio di induzione. Esempi: somma dei primi n numeri, somma dei primi n numeri dispari,
cardinalita' dell'insieme delle parti P(X) di un insieme finito X, somma geometrica.
I razionali e i reali come sviluppi decimali. Sviluppi decimali periodici.
Unione finita o numerabile di insiemi numerabili e' numerabile. I razionali sono numerabili. I reali non sono numerabili. Dato un insieme X, l'insieme delle parti P(X) ha cardinalita' superiore a quella di X.
L.L.M., Mathematics for Computer Science, Sez. 13.3 pdf
Relazioni fra gli elementi di due insiemi A e B come sottoinsiemi del prodotto cartesiano A x B. Funzioni. Relazioni su un insieme: riflessive, simmetriche, antisimmetriche, transitive. Relazioni di ordine parziale. Relazioni di equivalenza. Esempi: la relazione di equipotenza su una famiglia di insiemi, la relazione di contenenza sull'insieme delle parti di un insieme.
Relazioni1: pag. 1&2 (Def.1.1, Notaz.1.2, Es. 1.3, Es.1.7, No matrice di una relazione, No composizione); pag.3 pdf. Esercizi-svolti 2: n.1(a)(b), 4, 5.
Terza settimana:
Caratterizzazione dei numeri razionali mediante lo sviluppo decimale (periodico o limitato): dimostrazione e esempi.
Uso della serie geometrica per trovare la frazione che corrisponde ad un numero periodico. Introduzione ai numeri complessi; somma e prodotto, coniugio, modulo, inverso. Piano complesso, forma trigonometrica.
Numeri complessi pdf
La relazione di divisibilita' sui numeri naturali. Diagramma di Hasse di una relazione di ordine su un insieme finito. Relazioni di equivalenza: esempi. La relazione di congruenza modulo n sugli interi. Classi di equivalenza e partizione indotta.
Relazioni2: Sez.1; Relazioni1: Sez.3; Es.4.3.
Classi di equivalenza e partizione indotta. Relazioni di equivalenza: insieme quoziente. Esempi.
Relazioni1: pag.1-8.
Quarta settimana:
Proprieta' di campo dei numeri complessi.
Prodotti e potenze in forma trigonometrica.
Radici n-esime.
Esempi.
Numeri complessi pdf
Divisione con resto. Massimo comune divisore fra interi. L'algoritmo di Euclide.
L'identita' di Bezout. L'algoritmo di Euclide esteso. Equazioni lineari a coefficienti interi in due incognite: condizioni per l'esistenza di soluzioni intere, costruzione di una soluzione particolare, soluzione generale dell'equazione omogenea associata.
Nota1, pag.2-6.
Quinta settimana:
Teorema Fondamentale dell'Algebra (senza dimostrazione), esempi.
Conseguenza: decomposizione dei polinomi a coefficienti reali, esempi.
Introduzione alle successioni ricorsive. Equazioni ricorsive lineari, lineari omogenee, lineari a coefficienti costanti, lineari omogenee a coefficienti costanti. Proprieta' delle soluzioni di un'equazione ricorsiva omogenea.
Nota: Equazioni alle Differenze Finite.
Equazioni lineari a coefficienti interi in due incognite: soluzione generale. Congruenze modulo n: condizioni per l'esistenza di soluzioni intere, costruzione di una soluzione particolare, soluzione generale della congruenza omogenea associata, soluzione generale.
Nota1: pag. 7-9.
Sesta settimana:
Equazioni ricorsive: una combinazione lineare di soluzioni di equazione ricorsiva lineare omogenea e' ancora una soluzione (dimostrazione).
Equazione polinomiale associata ad equazione ricorsiva omogenea a coefficienti costanti. Soluzioni reali dell'equazione ricorsiva a partire dalle radici del polinomio associato: il caso della radice reale e quello della radice complessa. Esempi.
Equazioni ricorsive lienari omogenee a coefficienti costanti di grado 1.
Dimostrazione e esempi.
Equazioni ricorsive lienari omogenee a coefficienti costanti (reali) di grado 2: caso delle radici reali distinte, caso delle radici non reali.
Dimostrazione e esempi.
Nota: Equazioni alle Differenze Finite.
Sistemi di congruenze: condizioni per l'esistenza di soluzioni intere. Il Teorema Cinese del Resto. Esempi ed esercizi.
Nota1: pag. 9-11.
Il calcolo modulo n. Esempi ed esercizi.
Nota2: Esempio 1.7, Esempio 1.8, pag.4-6 (continua).
Settima settimana:
Equazioni ricorsive lineari omogenee di grado 2: caso del polinomio con soluzione doppia. Teorema di struttura delle soluzioni per equazioni ricorsive lineari non omogenee.
Suluzioni di equazioni ricorsive non omogenee con particolari termini noti.
Nota: Equazioni alle Differenze Finite.
Somma e prodotto su Zn . Introduzione ai gruppi. Il gruppo additivo Zn. Caratterizzazione delle classi resto che ammettono inverso moltiplicativo. Il gruppo moltiplicativo Zn*. Esempi.
Nota2: Esempio 1.7, Esempio 1.8, pag.2-6 (continua).
Calcolo dell'inverso di una classe in Zn*. Cardinalita' del gruppo Zn*: la funzione φ di Eulero.
Nota2: Esempio 1.7, Esempio 1.8, pag.2-6.
Nota: Funzione φ di Eulero, pdf pag.1-2 (meta').
Ottava settimana:
Il teorema di Lagrange e il Piccolo Teorema di Fermat.
Applicazioni al calcolo di grosse potenze modulo un intero ed ai test di primalita' (cenni).
Nota2, pag.7-10.
Il criptosistema a chiave pubblica R.S.A..
R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica pdf.
Relazioni di ordine: elementi massimali e minimali di un insieme ordinato. Massimo e minimo. Maggioranti e minoranti di un sottoinsieme di un insieme ordinato. Estremo superiore ed estremo inferiore, massimo e minimo di di un sottoinsieme di un insieme ordinato.
Nota Relazioni2: sezione 2.
Nona settimana:
Esercizi assortiti dai fogli settimanali.
Reticoli: definizione ed esempi. Proprieta' delle operazioni di inf e di sup in un reticolo. La relazione di ordine su un insieme munito di due operazioni binarie con le proprieta' di commutativita', associativita' e di assorbimento.
Nota Reticoli: sezioni 1,2, pag.1-3.
Reticoli limitati. Complemento di un elemento in un reticolo limitato. Reticoli distributivi. Un reticolo e' distributivo se e solo se non contiene maglie pentagonali o trirettangole. Unicita' del complemento in un reticolo limitato distributivo. Il caso dell'insieme delle parti di un insieme con la relazione di inclusione. Il caso dei divisori di un intero con la relazione di divisibilita'.
Nota Reticoli: sezione 3, pag.3-6.
Esercizi-svolti6: esercizi 1,2,3,4,5,6.
Decima settimana:
Reticoli booleani e algebre di Boole (cenni). L'algebra di Boole del calcolo proposizionale.
Nota Algebre di Boole: sezioni 1,2, pag.1-5.
Esercizi-svolti-7: esercizi n.1,2,3,4,5,6,7,8.
Esercizi-svolti-8: esercizi n.1,2,3,4,5,6,7.
Undicesima settimana:
Calcolo combinatorio: permutazioni di un insieme di n elementi. Pigeon-hole principle. Permutazioni e combinazioni di
r elementi da un insieme di n elementi. Stringhe ordinate e stringhe non ordinate di r elementi di n tipi, con possibili ripetizioni. Permutazioni di stringhe di r elementi di n tipi, con possibili ripetizioni.
Esercizi assortiti.
K. Rosen (quarta ediz.): cap.6, sez. 1,2,3,4,5, pag.385-428.
Dodicesima settimana:
Partizioni di un unsieme di n elementi: numeri di Bell e numeri di Stirling di seconda specie. La relazione di ricorrenza soddisfatta numeri di Bell e dai numeri Stirling di seconda specie. La cardinalita' delle funzioni
suriettive f : X --> Y da un insieme di n elementi in un insieme di k elementi. Esempi ed esercizi.
vedi: Wikipedia.
Tredicesima settimana:
Grafi e multigrafi, grafi e multigrafi diretti, grado di un vertice, lemma delle strette di mano. Sottografi. Isomorfismi di grafi. Cammini e circuiti su un grafo. Grafi connessi: esistenza di un cammino semplice fra due vertici in un grafo connesso. Circuiti e cammini euleriani. Caratterizzazione dei grafi che ammettono un circuito o un cammino euleriano (senza dim.). Condizioni sufficienti all'esistenza di circuiti hamiltoniani su un grafo: teoremi di Ore e Dirac (senza dim.). Alberi. Un grafo e' un albero se e solo se fra due vertici esiste un unico cammino semplice che li collega. Albero generatore in un grafo connesso. Grafi bipartiti. Accoppiamenti in un grafo bipartito. Caratterizzazione dei grafi bipartiti che ammettono un accoppiamento: Teorema di Hall. Colorazioni di un grafo e numero cromatico. Numero cromatico di un grafo unione disgiunta di due grafi, del grafo di n vertici (senza lati), di un albero, di un grafo bipartito.
K. Rosen (quarta ediz.): cap.7, sez.1(p.438-441), 2(p.445-450, p.453), 3(p.460-461), 4(p.467-469), 5(p.475-483), cap.8, sez.1 (p.528-529)
E. Lehman, F. Leighton, A: Sez. 5.1.1 - 5.1.3; pp. 131-135 (no dim.); 5.3.1 - 5.3.2; 5.6.3 - 5.6.4 (no dim.); 5.7.1 pdf.
Quattordicesima settimana:
Numero cromatico di un grafo completo con n vertici. Polinomio cromatico di un grafo. Polinomio cromatico di un grafo unione disgiunta di due grafi, del grafo con n vertici (senza lati), di un albero e del grafo completo con n vertici. Il Teorema di Cancellazione-Contrazione. Esempi.
R. Read, An Introduction to Chromatic Polynomials, pdf
(per scaricare questo file si deve essere collegati dal dominio uniroma2.it)
Sezioni: 1 - 3; 4 (solo Theorem 2); 5 (solo Theorem 5, no dim.); 10.
Quindicesima settimana:
Esercizi di riepilogo.
Fine