Matematica Discreta 2012/2013

        PROGRAMMA di MATEMATICA DISCRETA (9 CFU)   -   a.a. 2012-2013                       ( prof. Fabio GAVARINI ) INSIEMI, CORRISPONDENZE, RELAZIONI, OPERAZIONI   Insiemi; sottoinsiemi, sovrainsiemi, inclusione. Famiglie. L'insieme delle parti; partizioni. Operazioni tra insiemi. Corrispondenze tra insiemi. Immagine o controimmagine di sottoinsiemi; corrispondenza inversa; composizione. Funzioni. Caratterizzazione delle famiglie come funzioni. Restrizione di una funzione. Funzioni iniettive, suriettive o biiettive; biiettività e corrispondenza inversa. Composizione di funzioni; funzioni invertibili. Funzioni caratteristiche in un insieme. La biiezione naturale tra l'insieme delle parti di un insieme A e l'insieme delle funzioni caratteristiche in A. Relazioni in un insieme. Proprietà notevoli possibili per una relazione. Relazioni di preordine; relazioni d'ordine. Rela-zioni di equivalenza. La congruenza modulo n tra interi; equivalenze associate a funzioni. Classi di equivalenza, rappresentanti; insieme quoziente. Biiezione tra equivalenze in X e partizioni di X. Decomposizione canonica di una funzione. Operazioni; gruppoidi, semigruppi, monoidi, gruppi. Il monoide libero A* su un insieme A. Permutazioni di un insieme; le permutazioni formano un gruppo per la composizione. Insiemi con due operazioni; semianelli, anelli, campi. L’insieme delle parti (di un insieme) è un anello commutativo unitario per differenza simmetrica e intersezione. Bibliografia: [Ca] Capitolo I, paragrafi 1, 2, 3 e 4 - [G-P] files Insiemi , Funzioni e cardinalità , Relazioni 1 , Gruppi, anelli, campi - [L-L] Chapters 1, 2 e 3; Appendix B - [PC] Capitolo 1, paragrafi 1, 2 e 3; Capitolo 4, paragrafo 1; Capitolo 5, paragrafi 1 e 2 - Videolezioni: Insiemi , Corrispondenze , Funzioni 1 , Funzioni 2 , Funzioni caratteristiche , Relazioni , Equivalenze 1 , Equivalenze 2 , Operazioni 1 , Operazioni 2 NUMERI NATURALI, CALCOLO COMBINATORIO   Il Sistema dei Numeri Naturali (=S.N.N.). Il Principio di Induzione Debole (=Pr.I.D.). Ordinamento, somma e prodotto tra naturali; i numeri formano un semianello in cui l'ordine è compatibile con le operazioni. Principio di Induzione Forte (=Pr.I.F.), Principio del Minimo (=Pr.M.): equivalenza tra Pr.I.D., Pr.I.F. e Pr. M. (cenni). Dimostrazioni per induzione. Divisione con resto tra naturali. Numerazione in base arbitraria: scrittura posizionale (di un naturale) in base arbitraria. Calcolo del numero di: (1) funzioni da un insieme finito ad un altro ("disposizioni con ripetizione"); (2) funzioni iniettive da un insieme finito ad un altro ("disposizioni senza ripetizione"); (3) permutazioni di un insieme finito in sé stesso: il fattoriale di n; (4) sottoinsiemi con k elementi in un insieme con n elementi ("combinazioni di k elementi scelti tra n"): coefficienti binomiali; (5) partizioni di un insieme con n elementi in sottoinsiemi con numero di elementi assegnato: coefficienti multinomiali. La formula di Newton per lo sviluppo delle potenze di un binomio e per lo sviluppo delle potenze di un multinomio. Il triangolo di Pascal-Tartaglia. Bibliografia: [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafi 1 e 5 ; Capitolo II, paragrafo 2 - [G-P] files Induzione , Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [L-L] Chapter 1, section 8; Chapter 5, sections 1 to 5; Chapter 6, sections 1 to 3; Chapter 11, sections 3 - [PC] Capitolo 1, paragrafi 4 e 6; Capitolo 2, paragrafo 10 - Videolezioni: Naturali , Induzione , Divisione , Numerazione CARDINALITÀ, NUMERI CARDINALI   Equipotenza tra insiemi: riflessività, simmetria, transitività. Cardinalità di un insieme, numeri cardinali. Insiemi finiti, o numerabili o infiniti non numerabili. Ordinamento tra cardinali; Teorema di Schroeder-Bernstein (senza dimostrazione). Caratterizzazione degli insiemi infiniti (per un insieme X): (1) X è infinito, (2) esiste una funzione iniettiva dall'insie-me dei numeri naturali ad X, (3) esiste un sottoinsieme proprio di X che è equipotente ad X stesso. 1o Teorema di Cantor: L'unione di una famiglia finita (non vuota) o numerabile di insiemi numerabili è numerabile. 2o Teorema di Cantor: La cardinalità dell'insieme delle parti di X è strettamente maggiore della cardinalità di X. I cardinali infiniti superiori Aleph_n . La cardinalità del continuo: |R| = |P (N)| ; l'ipotesi del continuo generalizzata (cenni). Bibliografia: [AaVv] file Cardinalità (D'Andrea) - [Ca] Capitolo I, paragrafo 6 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7 - [PC] Capitolo 1, paragrafo 5 Videolezioni: Cardinalità 1 , Cardinalità 2 NUMERI INTERI, CONGRUENZE, ARITMETICA MODULARE   Richiami sui numeri interi: operazioni, ordine, valore assoluto. Costruzione degli interi a partire dai naturali, come "naturali + i negativi". Fattorizzazione in un monoide. Divisibilità; elementi invertibili, elementi associati. Elementi riduci-bili, elementi irriducibili, elementi primi; ogni primo è irriducibile. Fattorizzazioni banali, fattorizzazioni equivalenti. Massimo comun divisore (=MCD) e minimo comun multiplo (=mcm). Elementi coprimi (=primi tra loro). Divisione con resto tra interi: esistenza e unicità di quoziente e resto (positivo). Esistenza del MCD in Z, e identità di Bézout per esso: calcolo con l'algoritmo euclideo delle divisioni successive. Tra i numeri interi, ogni irriducibile è primo. Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi non nulli e non invertibili. Teorema di Euclide: Esistono infiniti interi irriducibili (a due a due non associati). Forma esplicita di MCD(a,b) e di mcm(a,b); la relazione MCD(a,b) mcm(a,b) = a b . Equazioni diofantee: definizione, criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione. Congruenze in Z (modulo n). Ogni congruenza è una equivalenza; descrizione delle classi di congruenza e dell'insieme quoziente Z_n . Somma e prodotto in Z_n . Teorema: Z_n è un anello commutativo unitario (senza dimostrazione). Criteri di divisibilità in Z. Proposizione: Z_n è un dominio <=> n è irriducibile (=primo) <=> Z_n è un campo. Equazioni congruenziali in Z: risolubilità, algoritmo risolutivo. Elementi invertibili in Z_n ; criterio di invertibilità, calcolo dell'inverso. Il gruppo moltiplicativo U(Z_n) degli elementi invertibili di Z_n ; la funzione di Eulero. Ripetitività delle potenze in Z_n . Il Piccolo Teorema di Fermat, il Teorema di Eulero (senza dimostrazione); calcolo di potenze in Z_n . Sistemi di equazioni congruenziali; il Teorema Cinese del Resto (senza dimostrazione). Il metodo crittografico RSA. Bibliografia: [AaVv] files Numeri interi (D'Andrea), paragrafo 4 , Congruenze, aritmetica modulare(D'Andrea), paragrafi 1 e 2 - [Ca] Capitolo II, paragrafi da 1 a 6 - [G-P] files Aritmetica sugli interi, congruenze, Teorema Cinese del Resto , Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 1 to 9 - [PC] Capitolo 2, paragrafi da 1, 2, 3, 6, 7, 8 e 9 RETICOLI, ALGEBRE DI BOOLE, FUNZIONI BOOLEANE   Relazioni d'ordine. Diagramma di Hasse. Sottoinsiemi ordinati, ordine prodotto. Principio di Dualità per insiemi ordinati. Elementi minimali (o massimali), minimo (o massimo) per un sottoinsieme in un insieme ordinato E. Reticoli. Principio di Dualità per reticoli. Limiti, complementi, distributività; elementi v-riducibili o v-irriducibili; ato-mi. Teorema di v-Fattorizzazione Unica (in v-irriducibili) per reticoli finiti distributivi. Teorema di v-Fattorizzazione Unica (in atomi) per reticoli finiti distributivi complementati (=algebre di Boole). Isomorfismi tra reticoli, reticoli isomorfi; sottoreticoli. Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N_5 o a M_5 (senza dimostrazione). Algebre di Boole. Principio di Dualità per algebre di Boole. Anelli booleani. Teorema di Equivalenza: “Algebra di Boole” e “anello booleano unitario” sono nozioni equivalenti (soltanto la definizione delle corrispondenze). Isomorfismi tra algebre di Boole, algebre di Boole isomorfe. Teorema (Stone - finito): Ogni algebra di Boole finita è isomorfa all'insieme delle parti dell'insieme dei suoi atomi. Sottoalgebre di Boole. Teorema (Stone - generale): Ogni algebra di Boole è isomorfa ad una sottoalgebra di Boole dell'insieme delle parti di un opportuno insieme (senza dimostrazione). Funzioni booleane, polinomi booleani. Equivalenza tra polinomi booleani. Prodotti, prodotti fondamentali; somme di prodotti. Forma normale disgiuntiva di un polinomio; calcolo tramite (1) "tavole di verità", o (2) manipolazioni successive. Forme minimali di un polinomio booleano. Gli implicanti primi di un polinomio booleano. Somme di prodotti irridondanti. Il Metodo del Consenso per calcolare la somma degli implicanti primi di f, e una sua forma minimale. Bibliografia: [Ca] Capitolo I, paragrafo 3(B) - [G-P] files Relazioni - 2 , Reticoli , Algebre di Boole , Funzioni booleane , Forme minimali di una funzione polinomiale - [L-L] Chapter 14, sections 1 to 5 and 7 to 11; Chapter 15, sections 1 to 9 - Videolezioni: Insiemi ordinati , Reticoli 1 , Reticoli 2 , Reticoli 3 , Algebre di Boole 1 , Algebre di Boole 2 FUNZIONI RICORSIVE, EQUAZIONI ALLE DIFFERENZE   Funzioni (o "successioni") ricorsive; equazione ricorsiva, grado e dati iniziali. Casi particolari: lineari, lineari omogenee, lineari a coefficienti costanti, lineari omogenee a coefficienti costanti (=l.o.c.c). Teorema di Ricorsione: Esiste un’unica funzione che soddisfa una data equazione ricorsiva e ha dati iniziali assegnati. Proposizione: L'insieme S delle successioni soluzioni di un'equazione ricorsiva lineare omogenea di ordine k è chiuso per la somma e per il prodotto con uno scalare; inoltre, esistono k successioni a_1, ... , a_k in S tali che ogni successione in S si possa scrivere in modo unico come combinazione lineare delle successioni a_1, ... , a_k (cenni di dimostrazione). Strategia di calcolo di una funzione ricorsiva lineare omogenea. Metodo di calcolo esplicito per funzioni ricorsive l.o.c.c. nei casi: (1) di grado 1; (2) di grado 2, con due radici reali distinte; (3) di grado 2, con una sola radice reale. Bibliografia: [G-P] file Equazioni alle differenze finite (cenni) - [L-L] Chapter 3, section 6; Chapter 6, sections 6, 7 and 8 - Videolezioni: Funzioni ricorsive 1 , Funzioni ricorsive 2 , Funzioni ricorsive 3.1 • • • • • • • • • • • • • • • TESTI (libri, dispense, videolezioni, ecc.) consigliati:   [AaVv] - Autori Varî, Materiale vario disponibile in rete (per gentile concessione degli autori) - alla pagina http://www.mat.uniroma2.it/~gavarini/page-web_files/mat-didat.html#Mat-Dis_altro-mat   [Ca] - G. Campanella, Appunti di Algebra 1 (per gentile concessione dell'autore) - alla pagina http://www.mat.uniroma2.it/~gavarini/page-web_files/mat-didat_data/dispense-ecc/Algebra_1_-_dispense_di_Campanella.rar   [Ga] - F. Gavarini, Videolezioni varie - alla pagina http://didattica.uniroma2.it/files/index/insegnamento/144372   [G-P] - L. Geatti, G. Pareschi, Appunti varî (per gentile concessione degli autori) - alla pagina http://www.mat.uniroma2.it/~gavarini/page-web_files/mat-didat_data/Algebra-Logica_(ING-INF)/Pagina_Web_Algebra-Logica_2012-13/AL_2012-13.html#app_alg-log   [L-L] - S. Lipschutz, M. Lipson, Discrete Mathematics, 3rd Edition, Schaum's Outlines, McGraw-Hill, 2007   [PC] - G. M. Piacentini Cattaneo, Algebra - un approccio algoritmico, ed. Decibel/Zanichelli, Padova, 1996 ________________________________________________________________________________________________________________________________________