Matematica Discreta, Informatica Sede di Brindisi

Inizio lezioni 26 Settembre 2011, orario 9-13. Aula II.

Programma PROVVISORIO del corso

(Il programma deifnitivo sara' l'unione degli argomenti elencati nel Diario delle Lezioni)

Il corso di Matematica discreta, da questo anno e' di 9 CFU: sono stati amumentati i CFU per fare piu' esercizi, ma gli argomenti trattati e il programma sono rimasti invariati (o forse ridotti). Pertanto, gli studenti degli anni precedenti dovranno superare lo stesso tipo di esame che varra' 6 o 8 o 9 CFU a seconda del proprio piano di studio.

ESERCIZI

Alcuni esercizi (v2) dati a lezione (raccolta molto incompleta che spera di essere aggiornata presto). Altri esercizi (v1) non dati a lezione. Prova di Esonero 2 novembre. Esercizi del 9 novembre.

ALTRI ESERCIZI

Alcuni esercizi sulla seconda parte esercizi (9 dicembre)

Altri esercizi del 16 dicembre 2011(simili ad una prova di esonero).

ESONERI:

ESONERO: 16 Novembre 2011 ore 9.30 FAQ: Durata: 2 ore. Aula II e Aula Magna. Portare un documento di validita' e una calcolatrice non si puo' usare quella del cellulare).

Puo' partecipare all'esonero solo chi ha seguito il corso e ha studiato. E' sconsigliata vivamente la partecipazione all' esonero a chi non ha studiato (NON si viene a vedere come e' ne tantomeno a tentarlo). L'esonero si supera con la votazione di 18/30. Al secondo esonero (prima di natale) potra' partecipare solo chi ha superato il primo.

Testi del primo esonero. RISULTATI

ESONERO II: 21 Dicembre 2011 ore 9.30 FAQ: Durata: 2 ore. Aula II. Portare un documento di validita' e una calcolatrice ( non si puo' usare quella del cellulare). Puo' partecipare all'esonero solo chi ha superato il primo. Non serve prenotarsi.

Testo del secondo esonero. RISULTATI

Studenti esonerati.

ESAMI:

Date degli esami: 16 Gennaio 2012, 30 Gennaio 2012, 13 Febbraio 2012. La prenotazione agli esami e' obbligatoria .

Diario delle Lezioni

26.09.2011 (4h): Presentazione del corso, libri di testo, programma, esami, esoneri, regole di base. Definizione di INSIEMI. Tre descrizioni per un insieme: elenco elementi, proprieta' caratterizzante, diagrammi di Venn. Unione, Intersezione, Complementare, Insieme delle Parti, Prodotto cartesiano. Proprieta' e leggi di De Morgan. Esempi ed Esercizi. Introduzione al linguaggio e simbolismo matematico: Quantificatori Ogni ed Esiste, inclusione, incluione propria, appartenenza, uguaglianza. Esempi ed Esercizi.

28.09.2011 (4h): LOGICA: Definizione di proposzione, congiunzione, disgiunzione e implicazioni. Tavole di Verita'. Equivalenza di proposizioni. Esempi ed Esercizi. FUNZIONI: Definizione di funzione, dominio e codominio. Funzioni equivalenti. Immagine e controimmagine di un sottoinsieme e Proprieta'. Funzioni iniettive. Esempi ed Esercizi.

03.10.2011 (4h): Ripasso. FUNZIONI: suriettive e biettive. Composizione di funzione e proprieta'. Inversa di funzioni biettive e proprieta'. Esempi ed Esercizi. Esercizi su funzioni.

05.10.2011 (4h): Cardinalita' di un insieme. Insiemi Equipotenti. Insiemi finiti. Cardinalita' minore o uguale. Se insiemi stessa cardinalita' finita, allora funzione e' iniettiva se e solo se suriettiva (con dim.) Insiemi infiniti, insiemi numerabili. Numerabilita' dell'insime degli interi Z (con dim). Potenza del continuo. Esempi. Principio di induzione completa e formulazioni equivalenti. Esempi e controesempi ed esercizi. Cardinalita' dell'insieme delle parti di un insieme finito (dim. usando il principio di induzione). Esempi ed Esercizi.

10.10.2011 (4h): SUCCESSIONI. Definizioni ed esempi. Simbolo di sommatoria e proprieta'. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi. Numeri di Fibonacci, definizione ricorsiva e come modellazione della popolazione di conigli. Formula ricorsiva e formula chiusa. Torri di Hanoi, definizione come gioco, formula ricorsiva e formula chiusa. Esercizi ed esempi (su funzioni, successioni e principio di induzione).

12.10.2011 (4h): Cardinalita' dell'unione di insiemi finiti. Caso generale di insiemi disgiunti. Regola della somma. Caso generale con intersezioni non vuote. Esempi ed applicazioni. Cardinalita' del prodotto di insiemi finiti. Regola del prodotto. Esempi ed applicazioni. COMBINATORIA: Disposizioni semplici di n oggetti di classe k (k minore o uguale ad n). Definizione, calcolo di D(n,k), esempi ed esercizi. D(n,k) calcola il numero di applicazioni iniettive da un insieme di cardinalita' k ad uno di cardinalita' n (con dim.). D(n,n)=n! come numero di ordinamenti di n oggetti. Permutazioni. D(n,n) calcola il numero di applicazioni biettive (con dim.). Esercizi ed Esempi. Combinazioni semplici di n oggetti di classe k (k minore o uguale ad n). Definizione e calcolo del coefficiente binomiale. Sottoinsiemi di cardinalita' k in un insieme di cardinalita' n. Proprieta'. Formula del binomio di Newton. Triangolo di Pascal o Tartaglia e legame con i coefficienti binomiali. Seconda dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando la formula di Newton. Esempi ed Esercizi.

17.10.2011 (4h): Ripasso: Disposizioni semplici di n oggetti di classe k e combinazioni semplici di n oggetti di classe k (k minore o uguale ad n). Caso con ripetizioni. Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Cardinalita' dell'insieme di applicazioni tra due insiemi finiti. Esempi e esercizi. Combinazioni con ripetizioni di n oggetti di classe k (k minore o uguale ad n). Funzione caratteristica di un sottoinsieme. Terza dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando le funzioni caratteristiche. Numero di applicazioni suriettive tra insiemi finiti. Esempi ed Esercizi. Correzione di esercizi.

17.10.2011. Ricevimento pomeridiano extra

19.10.2011 (4h): RELAZIONI. Definizioni di relazioni tra insiemi. Esempi. Relazione vuota, totale, associata ad una funzione. Relazione su un insieme, relazione identica. Proprieta' di una relazione: Riflessiva, Simmetrica, Antisimmetrica, Transitiva. Relazione di ordine parziale e insiemi parzialmente ordinati. Relazione di ordine totale e insiemi totalmente ordinati. Esempi ed Esercizi. Relazioni di equivalenza. Esempi ed Esercizi.

24.10.2011 (4h): Relazioni di equivalenza.Definizione di classe di equivalenza ed esempi. Teorema sulle proprieta' delle classi di equivalenza (con dimostrazione). Definizione di PARTIZIONE di un insieme; esempi. Teorema: ogni relazione di equivalenza definisce una partizione (con dimostrazione). Teorema: ogni partizione definisce una relazione di equivalenza (con dimostrazione). Insieme quiziente. Esempi ed Esercizi.

26.10.2011 (4h): NUMERI INTERI. Definizione di valore assoluto, di divosore e multiplo. Divisibilita' di ogni combinazione lineare. Teorema della divisione in Z: esistenza ed unicita' del quoziente e resto (dimostrazione dell'unicita' e dell'esistenza di quoziente e resto nel caso di numeri positivi). Esempi di divisioni con resto in tutti i casi. Definizione di un massimo comun divisore e definizione di MCD. Proprieta'. Esistenza del MCD e algoritmo di Euclide per la sua determinazione. Teorema di Bezout (con dimostrazione). Definizione di un minimo comune multiplo e di mcm. Proprieta'. Relazione di equivalenza della congruenza modulo n, classi resto e descrizione del quoziente. Esempi ed Esercizi.

31.10.2011. Ponte

2.11.2011 (4h): NUMERI PRIMI. Definizione di numeri primi. Teorema Fondamentale dell'aritmetica (con dimostrazione dell'esistenza): fattorizzazione in potenze di primi distinti. Applicazione della fattorazizzazione per trovare ivisori di un numero intero: scrittura esplicita e calcolo di quanto sono. Applicazione della fattorazizzazione per il calcolo del MCD. Teorema esistenza infiniti numeri primi (con dimostrazione). Crivello di Eratostene. Funzione di Eulero e proprieta'. Applicazione della fattorazizzazione per il calcolo della funzione di Eulero per ogni intero n. EQUAZIONI DIOFANTEE: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Teorema che descrive tutte e sole le soluzioni di una equazione diofantea (dimostrato solo che sono soluzioni). Esempi ed Esercizi. Prova di Esonero.

7.11.2011 (4h): CONGRUENZE modulo n >1. Ripasso della definizione della relazione di congruenza: relazione di equivalenza, descrizione classi resto, descrizione quoziente. Descrizione di alcune proprieta': somma, moltiplicazione, disione dei coefficienti, riduzione del modulo. Piccolo teorema di Fermat, con dimostrazione. Teorema di eulero Fermat (senza dimostrazione). Applicazione al calcolo di potenze modulo n. CONGRUENZE LINEARI: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Teorema che descrive tutte e sole le soluzioni di una congruenza lineare (dimostrato usando le equazzioni diofantee), descrizione delle soluzioni distinti modulo n. SISTEMI DI CONGRUENZE LINEARI: definizione ed esempi. Teorema riduzione dei coefficiente dell'incognita ad 1, nel caso di esistenza di soluzione per ogni congruenza. Teorema Cinese dei Resti: unicita' della soluzione. Esempi ed Esercizi.

9.11.2011. (4h) Metodi di Fattorizzazione: Metodo di Eratostene e Metodo di Fermat. Scrittura dei numeri in base n. Esempio in base 10,2 e 7. Criteri di divisibilita' per: 2,3,4,5,9,11,25. Sistema Crittografico RSA (R. Rivest, A. Shamir e L. Adleman): Definizione, crittografia a chiave pubblica. Accenno al probema della firma. Esercizi su: congruenze, potenze e congruenze, equazioni diofantee, congruenze lineari, sistemi di congruenze lineari.

9.11.2011. (2h) Esercitazione pomeridiana extra. Sistemi di congruenze, principio di induzione, funzioni, calcolo combinatorio, successioni ricorsive, MCD. Esercizi del 9 novembre.

14.11.2011. NO LEZIONE, per la settiamna di pausa degli esoneri

16.11.2011. (2h) Esonero, Aula II e Aula Magna. Portare un documento di validita' e una calcolatrice (non si puo' usare quella del cellulare).

21.11.2011. (4h) STRUTTRE ALGEBRICHE: Definizione di struttura algebrica, operazione, operazione associativa, lemento neutro, elemento inverso. MONOIDI: definizione, esempi, monoide delle parole, monoidi commutativi. GRUPPI: definizioni, esempi, gruppi abeliani. Legge di cancellazioni nei gruppi. Gruppi: scrittura moltiplicativa e scrittura additiva: potenze o multipli di un elemento. Relazioni di equivalenza compatibili con strutture algebriche: esempio della relazione di equivalenza su Z compatibile sia con la somma che con il prodotto. Gruppi (Z_n,+) e monoide commutativo (Z_n, .). TAbelle per i gruppi finiti. Esempi.

23.11.2011. (4h) SOTTOGRUPPI: definizioni, teorema di caratterizzazione deii sottogruppi (con dimostrazione). Esempi. Intersezione di sottogruppi e' un sottogruppo, l'unione in generale no. Ordine di un gruppo: definizione ed esempi, ordine di un sottogruppo. Teorema di Lagerange (senza dimostrazione). Sottogruppo ciclico generato da un elemento. Periodo di un elemento. Proprieta' delle potenze di un elemento in relazione al suo ordine. Gruppi ciclici finiti ed infiniti: definizione ed esempi. Proprieta' dei gruppi ciclici: sono abeliani, i sottogruppi sono ciclici, ordine degli elementi nei gruppi ciclici finiti, generatori. Esempi ed Esercizi

28.11.2011. (4h) GRUPPI CICLICI finiti: per ogni divisore hdell'ordine esiste un sottogruppo di ordine h. Esempi ed Esercizi. Monoide commutativo (Zn,.): definizione ed elementi invertibili. Gruppo abeliano: (Zp,.) con p primo. GRUPPO SIMMETRICO. Definizione di gruppo simmetrico, notazione degli elementi, e degli inversi e della composizione. Definizione di ciclo. Ogni ciclo corriponsde ad una permutazione. Ogni permutazione puo' scriversi come prodotto di cicli disgiunti. Definizione di trasposizione. Ogni ciclo e quindi ogni permutazione, puo' essere scritta come prodotto di trasposizioni. Permutazioni pari e dispari. Ordine di una permutazione. Esempi ed Esercizi.

28.11.2011. pomeriggio (4h) Esempi ed Esercizi. Gruppo somma diretta. Gruppo (Mat_nxm(R), +) delle matrici di ordine nxm a coefficienti reali.Gruppi finiti ciclici, ordine elementi e generatori. Esercizi sul gruppo simmetrico.

30.11.2011. No lezione

05.12.2011. (4h) ANELLI: Definizione di anello, di anello unitario, di anello commutativo unitario. Esempi (Z,+,.), (Q,+,.), (R,+,.), (Zn,+,.). Definizione di divisori dello zero e di elementi invertibili (o unitari). Esempi in (Z,+,.), (Q,+,.), (R,+,.), (Zn,+,.). Se un elemento e' invertibile allora non e' un divisore dello zero (con dimostrazione). Divisori dello zero ed invertibili in (Zn,+,.). Esempio di ANELLO dei POLINOMI a coefficienti in un anello commutativo unitario R: (R[x],+,.). CAMPI: definizione. Esempi: (Q,+,.), (R,+,.), (Zp,+,.) con p primo. Campo dei NUMERI COMPLESSI (C,+,.): definizione, dell 'insieme C=RxR e di . e +. Identificazione dei numeri reali con gli elementi (a,0). Definizione dell'unita' immaginaria i=(0,1). Definizione di Coniugato e di modulo di un numero complesso. Proprieta' del coniugato e del modulo. Esempi ed Esercizi.

07.12.2011. (4h) In ogni anello commutativo unitario finito, ogni elemento e' invertibile oppure un divisore dello zero (senza dimostrazione). Inverso nei numeri complessi. Esempi ed Esercizi. MATRICI: Riapsso della definizione di matrice e del gruppo abeliano (Mat_nxm(K), +), su un qualsiasi campo (K,+, .). Esempi. Definizione di matrice moltiplicabile. Definizione della matrice IDENTITA' e matrice TRASPOSTA. Definizione di PRODOTTO di MATRICI. Esempi ed esercizi. ANELLO delle MATRICI: (Mat_nxn(K), +, .) delle matrici di ordine nxn a coefficienti in un qualsiasi campo (K,+, .). Eempi di divisori dello zero nell'anello delle matrici. Definizione di COMPLEMENTO ALGEBRICO di un elemento di una matrice. Definizione di DETERMINANTE (di una MATRICE QUADRATA) con la regola di LAPLACE. Esempi ed Esercizi sul calcolo di determinanti. MATRICE INVERTIBILE: definizione di amtrice invertibile. Teorema: una matrice quadrata a coefficienti in un campo K e' invertibile se e solo se il determinante e' non nullo. Calcolo della MATRICE INVERSA, usando i complementi algebrici. Esempi ed Esercizi.

Alcuni esercizi sulla seconda parte esercizi (9 dicembre)

12.12.2011. GRAFI: definizione di grafo, esempi. Vertici adiacenti, lati incidenti. disegno di un grafo. Isomorfismo di grafi. Grado di un vertice. Formula che lega il numero dei lati ai gradi dei vertici (con dimostrazione)Numero di vertici dipari in un grafo. Grafi regolari. Definizione di grafo orientato, di multigrafo e di multigrafo orientato. Definizione di cammino e circuito (o ciclo). Grafo connesso. Grafo completo. Definizione di cammino euleriano, definizione di circuito euleriano. Teroema di esistenza di circuiti euleriani. Teorema di esistenza di cammini euleriani. Cammino hamiltoniano. Grafi bipariti. Esempi grafi bipartiti completi. Definizione di ALBERI. Teorema di caratterizzazione degli alberi. Esempi ed esercizi.

14.12.2011. Grafi PLANARI. Esempi grafi K5 e K3,3. Teoremi sui grafi planari. Definizione di faccia in un grafo planare. Formula che lega numero di lati, numero di vertici e facce. RETICOLI: definizione di reticolo (R,^,V). definizione di sottoreticolo. Esmepio di reticolo dell'insieme delle parti di un insieme finito. Teorema leggi di idempotenza (con dimostrazione). Teorema che lega unione e intersezione (con dimostrazione). Reticoli distributivi. Esistenza elemento neutro rispetto unione e intersezione. Complemento di un elemento. Teorema: nei reticoli distributivi con elementi neutri, se il complemento esiste e' unico (con dimostrazione). Definizione reticolo di BOOLE. Legame tra reticoli ed insimi parzialmente ordinati. Definizione massimo e minimo, estremo inferiore ed estremo superiore in un insieme parzialmente ordinato. Esempi: numeri interi e naturali, con la relazione di minore o uguale, numeri naturali non nulli e relazione di divisibilita', insieme dei divisori di un intero n, per ogni n>1. Diagrammi di Hasse di un insieme parzialmente ordinato. Teorema: ogni insieme parzialmente ordinato che ammette sup e inf e' un reticolo.

Altri esercizi del 16 dicembre 2011(simili ad una prova di esonero).

19.12.2011. RETICOLI: Ripasso sui reticoli. Teorema: ogni insieme parzialmente ordinato che ammette sup e inf e' un reticolo. Teorema: ogni reticolo e' un insieme parzialmente ordinato. Reticoli distributivi. Esempi di reticoli non distributivi: Reticolo trirettangolo M3, reticolo pentagonale N5. Definizione di isomorfismo di reticli. Teorema di caratterizzazione dei reticoli distributivi. Esercizi su: reticoli distributivi, reticoli di Boole, alberi, frafi, grafi planari e formula di Eulero, circuiti euleriani, grafi isomorfi, matrice e determinante, numeri complessi, gruppi di permutazione.

Stay hungry Stay foolish. S. Jobs