Matematica Discreta 2013/2014

Per le informazioni sugli esami, tracce e risultati, consultare anche la pagina esami

Inizio lezioni 24 Febbraio 2014, orario 9.30-13.15. Fine lezioni 21 Maggio 2014.

Programma PROVVISORIO del corso

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

Il corso di Matematica discreta, 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.

ESAMI: Tracce e Risultati

La prenotazione agli appelli E' OBBLIGATORIA mediante il sistema ESSE3 nei tempi stabiliti, non si accettano prenotazioni via mail, ne tantomeno prenotazioni dopo i termini stabiliti. Portare obbligatoriamente un documento di validita' e una calcolatrice (non si puo' usare quella del cellulare). E' sconsigliata vivamente la partecipazione all' esame a chi non ha studiato (NON si viene a vedere come e' ne tantomeno a tentarlo).

ESONERO: 14 Aprile ore 10:00; Tracce Esonero 14 Aprile 2014; Risultati primo esonero 2014.

La prenotazione all'esonero E' OBBLIGATORIA mediante il sistema ESSE3 nei tempi stabiliti (tra il 17 Marzo e il 6 Aprile ), non si accettano prenotazioni via mail, ne tantomeno prenotazioni dopo i termini stabiliti. Portare OBBLIGATORIAMENTE un documento di validita' e se serve una calcolatrice (non si puo' usare quella del cellulare). Puo' partecipare all'esonero SOLO chi ha studiato ed e' regolarmente iscritto e in regola con le tasse universitarie. E' sconsigliata vivamente la partecipazione all' esonero a chi non sta seguendo il corso o non ha studiato (NON si viene a vedere come e' ne tantomeno a tentarlo, tanto i testi saranno poi disponibili su internet).

FAQ: Durata: 2 ore. ISCRIZIONE OBBLIGATORIA e PORTARE OBBLIGATORIAMENTE un documento di identita' e una penna e se occorre una calcolatrice (non si puo' usare quella del cellulare). L'esonero si supera con la votazione di 18/30. Al secondo esonero potra' partecipare solo chi ha superato il primo. Se uno studente supera il primo esonero e non supera il secondo esonero o non si presenta al secondo esonero, allora rinuncia alla possibilita' di superare l'esame con gli esoneri ovvero deve fare tutto l'esame.

ESONERO II: 28 Maggio ore 9:30; Tracce Esonero 28 Maggio 2014; Risultati secondo esonero 2014 e regole per gli studenti esonerati.

PORTARE OBBLIGATORIAMENTE un documento di identita' e una penna e se occorre una calcolatrice (non si puo' usare quella del cellulare). L'esonero si supera con la votazione di 18/30. Puo' partecipare solo chi ha superato il primo. Se uno studente supera il primo esonero e non supera il secondo esonero o non si presenta al secondo esonero, allora rinuncia alla possibilita' di superare l'esame con gli esoneri ovvero deve fare tutto l'esame.

TUTOR

Per l'esame di Matematica Discreta e' stato nominato un tutor, in carica fino a novembre, che e' disponibile per fare ricevimento via skype. L'orario provvisorio e' il Mercoledi dalle 16:30 alle 19. Per avere maggiori informazioni su come contattare il tutor (e.g., utente skype) contattatemi. Orario Provvisorio (aggiornato il 22 Maggio). Orario di Agosto, Settembre, Ottobre e Novembre.

Esercizi

Diario delle Lezioni

  • 24.02.2014 (1h) : Presentazione del corso, orario lezioni, libri di testo, programma, esami, esoneri, regole di base.
  • 26.02.2014 (+4h=5h): Teoria elementare degli INSIEMI. Tre descrizioni per un insieme: elenco elementi, proprieta' caratterizzante, diagrammi di Venn. Unione, Intersezione, Complementare, Insieme delle Parti, cartesiano. Proprieta' e leggi di De Morgan (con dimostrazione). Esempi ed Esercizi. Introduzione al linguaggio e simbolismo matematico: Quantificatori Ogni ed Esiste, inclusione, inclusione propria, appartenenza, uguaglianza. Esempi ed Esercizi. Prodotto cartesiano. Esempi ed Esercizi. LOGICA: Definizione di proposizione, negazione, congiunzione, disgiunzione e implicazioni. Tavole di Verita'. Equivalenza di proposizioni. Esempi ed Esercizi.
  • 03.03.2014 (+4h=9h): FUNZIONI: Definizione di funzione, dominio e codominio. Funzioni coincidenti. Funzioni identita'. Immagine e controimmagine di un sottoinsieme. Esempi ed Esercizi. Funzioni iniettive suriettive e biettive. Composizione di funzione e proprieta'. Esempi ed esercizi.
  • 05.03.2014 (+4h=13h): Funzione inversa di funzioni biettive e proprieta'. Esempi ed Esercizi. CARDINALITA': 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). PRINCIPIO di INDUZIONE: 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). Principio di induzione generalizzato. Esempi ed Esercizi.
  • 10.03.2014 (+4h=17): SUCCESSIONI. Definizioni ed esempi. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi ed Esercizi. Numeri di Fibonacci: definizione ricorsiva come modellazione della popolazione di conigli, formula ricorsiva e formula chiusa (con dimostrazione). Torri di Hanoi: definizione come gioco, formula ricorsiva e formula chiusa (con dimostrazione). Simbolo di sommatoria e proprieta'. Esercizi ed esempi su principio di induzione. Esercizi di logica: Tabelle di verita' con tre proposizioni. Proposizioni logiche, vere, false e negazioni.
  • 12.03.2014 (+4h=21): Cardinalita' dell'unione di insiemi finiti. Caso generale di insiemi disgiunti. Regola della somma. Caso generale con intersezioni non vuote per due e tre insiemi: Principio di inclusione-esclusione con dimostrazione). 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 tra insiemi di cardinalita' n (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'. 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.
  • 12.03.2014 (+2h=23) Dimostrazione leggi di de Morgan, e proprieta della controiimagine. Esercizi su funzioni: iniettivita', suriettivita', controimmagini, immagini, biettivita', inversa, composizione. Esercizi su principio di induzione.
  • 17.03.2014 (+4h=27): Ripasso: Regola della somma; Principio inclusione esclusione; regola del prodotto; 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. Funzione caratteristica di un sottoinsieme. Terza dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando le funzioni caratteristiche. Combinazioni con ripetizioni di n oggetti di classe k. Calcolo e dimostrazione. Esempi ed Esercizi. Correzione di esercizi su combinatoria, formula chiusa di successioni definite per ricorrenza e principio di induzione.
  • 19.03.2014 (+4h=31): RELAZIONI. Definizioni di relazione 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. Elementi confrontabili e insiemi totalmente ordinati. Esempi ed Esercizi. Relazioni di equivalenza. Esempi ed Esercizi. Esercizi su combinatoria, anagrammi e funzioni.
  • 24.03.2014 Inaugurazione anno accademico. No lezione.
  • 26.04.2014 (+4h=35): 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 quoziente. Esempi ed Esercizi. Proprieta' dei numeri interi. Esercizi su relazioni di equivalenza, combinatoria e principio di induzione.
  • 31.03.2014 (+4h=39): NUMERI INTERI. Definizione di divisore e multiplo e proprieta'. Divisibilita' di ogni combinazione lineare. Teorema della divisione in Z: esistenza ed unicita' del quoziente e resto (senza dimostrazione). 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. Identita' di Bezout (con dimostrazione). Definizione di un minimo comune multiplo e di mcm. Proprieta'. Esempi ed Esercizi. NUMERI PRIMI. Definizione di numeri primi. Teorema Fondamentale dell'aritmetica: fattorizzazione in potenze di primi distinti. Applicazione della fattorizzazione per trovare divisori di un numero intero: scrittura esplicita e calcolo di quanti sono i divisori. Applicazione della fattorizzazione per il calcolo del MCD.
  • 31.03.2014 (+2h=41): Esercizio su principio di iduzione seconda forma generalizzato: ovvero dimostrazione dell'esistenza della fattorizzazione del Teorema Fondamentale dell'aritmetica. Esercizio su relazioni di equivalenza: Relazione di equivalenza della congruenza modulo n, classi resto e descrizione del quoziente. Esercizi su relazione di ordine, su massimo comun divisore ed identita' di Bezout e su logica.
  • 02.04.2012 (+4h=45):Teorema esistenza infiniti numeri primi (con dimostrazione). Crivello di Eratostene. Metodi di Fattorizzazione: Metodo di Eratostene e Metodo di Fermat. EQUAZIONI DIOFANTEE: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Teorema che descrive tutte e sole le soluzioni di una equazione diofantea (visto solo che sono soluzioni). Esempi ed Esercizi. 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, divisione dei coefficienti, riduzione del modulo. Piccolo teorema di Fermat, con dimostrazione. Teorema di Fermat (enunciato). Per i pou' curiosi: un po' di storia del teorema e un link un po' meno matematico
  • 07.04.2014 (+4h=49): Definizione della funzione di Eulero. 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 equazioni diofantee), descrizione delle soluzioni distinti modulo n. Esempi ed Esercizi. SISTEMI DI CONGRUENZE LINEARI: definizione ed esempi. Teorema riduzione dei coefficiente dell'incognita ad 1, nel caso di esistenza di soluzione per ogni congruenza (con dimostrazione). Teorema Cinese dei Resti: esistenza ed unicita' della soluzione modulo N (dimostrazione dell'esistenza). Esempi ed Esercizi. Scrittura dei numeri in base n. Esempio in base 10,2 e 7. Criteri di divisibilita' per: 2,3,4,5,9,11,25.
  • 07.04.2014 (+2h=51): Esercitazione su Teorema cinese dei resti, congruenze lineari, equazione diofantea, relazione dei equivalenza, calcolo combinatorio.
  • 09.04.2014 No lezione, pausa di riflessione per permettere agli studenti la preparazione all'esonero.
  • 14.04.2014: Esonero: puo' partecipare solo chi e' nella Lista degli iscritti PORTARE OBBLIGATORIAMENTE un documento di identita' e una penna e se occorre una calcolatrice (non si puo' usare quella del cellulare). Tracce Esonero 14 Aprile 2014; Risultati primo esonero 2014. .

  • 28.04.2014 (+3h=54) Sistema Crittografico RSA (R. Rivest, A. Shamir e L. Adleman): Definizione, crittografia a chiave pubblica. STRUTTRE ALGEBRICHE: Definizione di struttura algebrica, operazione, operazione associativa, operazione commutativa elemento neutro, elemento inverso. Esempi di ogni definizione. MONOIDI: definizione, esempi, monoide delle parole, monoidi commutativi e non commutativi, esempi.
  • 30.04.2014: (+3=57) GRUPPI: definizioni, esempi, gruppi abeliani e non abeliani. Legge di cancellazioni nei gruppi con dimostrazione. Gruppi: scrittura moltiplicativa e scrittura additiva: potenze o multipli di un elemento. Relazioni di equivalenza compatibili con strutture algebriche. Teorema della struttura algebrica indotta sull'insieme quoziente (senza dimostrazione). Esempi fondamentali: relazione di congruenza modulo n (maggiore o uguale a 2) 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 e Esercizi.
  • 05.05.2014: (+4=61) SOTTOGRUPPI: definizioni, teorema di caratterizzazione dei 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 Lagrange (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. Esempii in (Z_n,+). Proprieta' nei gruppi ciclici finiti: per ogni divisore h dell'ordine esiste un sottogruppo di ordine h. Esempi ed Esercizi.
  • 05.05.2014: (+2=63) Esercizi su strutture algebriche associative, commutative, esistenza elemento neutro, esistenza inverso.
  • 07.05.2014. (+4h=67) Monoide commutativo (Zn,.): definizione ed elementi invertibili. Gruppo abeliano: (Zp,.) con p primo. Esempi ed Esercizi. GRUPPO SIMMETRICO. Definizione di gruppo simmetrico, notazione degli elementi, e degli inversi e della composizione. Definizione di ciclo. Ogni ciclo corriponde 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.
  • 12.05.2014. (+4h=71) 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,+,.). CAMPI: definizione (K,+,.). Esempi: (Q,+,.), (R,+,.), (Zp,+,.) con p primo. Esempio di ANELLO dei POLINOMI a coefficienti in un campo: (K[x],+,.). 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). Forma algebrica dei numeri complessi. Definizione di coniugato e di modulo di un numero complesso. Forma algebrica dell'inverso. Proprieta' del coniugato e del modulo. Esempi ed Esercizi. Esercizi sui gruppi ciclici.
  • 14.05.2014. (+4h=75) MATRICI: Definizione di matrice e del gruppo abeliano (Mat_nxm(K), +) delle matrici di ordine nxm a coefficienti in un qualsiasi campo (K,+, .). Esempi di matrici ed esempi di somma. Definizione della matrice IDENTITA' e di matrice TRASPOSTA. Prodotto Matrice per uno scalare. Definizione di matrici moltiplicabili. Definizione di PRODOTTO di MATRICI. Esempi ed esercizi. ANELLO delle MATRICI: (Mat_nxn(K), +, .) delle matrici quadrate di ordine n a coefficienti in un qualsiasi campo (K,+, .). Esempi di divisori dello zero nell'anello delle matrici (e quindi non e' un campo). 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 matrice invertibile. Teorema: una matrice quadrata a coefficienti in un campo K e' invertibile se e solo se il determinante e' non nullo (senza dimostrazione). Calcolo della MATRICE INVERSA, usando i complementi algebrici. Esempi ed Esercizi. Esercizi su gruppi di permutazione.
  • 19.05.2014.(+4h=79) GRAFI: definizione di grafo, esempi. Definizione di grafo orientato, di multigrafo e di multigrafo orientato. 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 dispari in un grafo (con dimostrazione). Definizione di cammino e circuito (o ciclo). Grafo connesso. Definizione di distanza tra vertici in un grafo connesso. Grafo completo. Definizione di cammino euleriano, definizione di circuito euleriano. definizione di grafo euleriano. Teorema di esistenza di circuiti euleriani. Teorema di esistenza di cammini euleriani. Definizone di cammino hamiltoniano. Grafi bipariti. Esempi grafi bipartiti completi. Definizione di ALBERI. Teorema di caratterizzazione degli alberi. Grafi PLANARI. Esempi grafi K5 e K3,3. Teoremi sui grafi planari. Esempi ed esercizi.
  • 19.05.2014. (+3h=82) Esercitazione su grafi, matrici, numeri complessi, gruppi di permutazione, strutture algebriche. Sistema di congruenze, principio di induzione.
  • 21.05.2014. (+4h=86) RETICOLI: definizione di reticolo algebrico (R,^,V). Definizione di sottoreticolo. Esempio di reticolo dell'insieme delle parti di un insieme finito. Teorema sulle leggi di idempotenza (con dimostrazione). Teorema che lega V unione e ^ intersezione (con dimostrazione). Reticoli distributivi. Esistenza elemento neutro rispetto ad unione e intersezione. Complemento di un elemento. Teorema: nei reticoli distributivi con elementi neutri, se il complemento esiste e' unico (con dimostrazione). Definizione di reticolo di BOOLE. Legame tra reticoli ed insiemi parzialmente ordinati. Definizione di 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 per ogni coppia di elementi e' un reticolo algebrico. Teorema: ogni reticolo algebrico e' un insieme parzialmente ordinato che amemtte sup e inf per ogni coppia di elementi. Relazione ta minimo e massimo ed elementi neutri. Esempi di reticoli non distributivi: Reticolo trirettangolo M3, reticolo pentagonale N5. Teorema di caratterizzazione dei reticoli distributivi. Esercizi su: reticoli distributivi, reticoli di Boole, complementi di un elemento, reticoli dei divisori. THAT'S IT!
  • 28.05.2014. Secondo Esonero ore 9:30: Al secondo esonero potra' partecipare solo chi ha superato il primo. Se uno studente supera il primo esonero e non supera il secondo esonero o non si presenta al secondo esonero, allora rinuncia alla possibilita' di superare l'esame con gli esoneri ovvero deve fare tutto l'esame.

Stay hungry Stay foolish. S. Jobs