Matematica Discreta 2015/2016 (M-Z)

Corso di Laurea in Informatica, Corso B, M-Z

Inizio lezioni 1 Ottobre Aula A, piano terra, Dipartimento di Informatica. Orario lezioni: Lunedi 8:30-11:30; Martedi 9:30-11:30; Giovedi 8:30-11:30.

Fine lezioni Martedi 22 Dicembre 2015

Programma PROVVISORIO del corso

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

Tutorato:

E' stato attivato un servizio di tutoraggio per i corsi di Matematica ad Informatica. Per maggiori informazioni consultare la pagina web o contattare la Prof. Lanza.

Esami:

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', una penna e se serve una calcolatrice (non si puo' usare quella del cellulare). La durata della prova e' 2 ore. E' sconsigliata vivamente la partecipazione all' esame a chi non ha studiato (NON si viene a vedere come e' ne tantomeno a tentarlo).

Gli studenti degli anni precedenti (Canale M-Z) devono sostenere l'esame nelle modalita' e programma dell'anno 2015/2016 (che e' identico a quello dell'anno dell'anno 2014/2015.)

Gli studenti che hanno superato la prova e vogliono accettare il voto, devono farlo entro i termini stabiliti su Esse3. Chi non accetta il voto puo' ripetere la prova in uno qualsiasi degli appelli successivi, perdendo ovviamente la prova precedente (questo vale per chi non accetta il voto per proprio volere, per errore, per dimenticanza, perche' non sa usare Esse3, etc. ).

  • Regole e faq.
  • Leggere attentamente (versione aggiornata al 17 Dicembre 2015, con le regole per gli studenti trasferiti da altri corsi di laurea).

    Testi consigliati

    Per la preparazione al corso va bene un qualsiasi libro che ricopra gli argomenti trattati. Alcuni libri che contengono tali argomenti sono:

    G.M. Piacentini Cattaneo:"Matematica Discreta", ed. ZANICHELLI

    A. Facchini:"Algebra e Matematica Discreta", ed. ZANICHELLI

    M.G. Bianchi, A. Gillio: "Introduzione alla Matematica Discreta", ed. McGRAW-HILL

    L. Di Martino, M.C. Tamburini: "Appunti di Algebra", ed. CLU

  • Appunti.
  • Telegram

    E' stato attivato un canale su telegram https://telegram.me/MD15MZ, per facilitare e velocizzare la comunicazione di avvisi. Tutte le notizie verranno comunque pubblicate sulla pagina web del docente. Per iscriversi all'esame non si puo' usare telegram: LA PRENOTAZIONE E' OBBLIGATORIA mediante il sistema ESSE3 nei tempi stabiliti.

    Esercizi

    Diario delle Lezioni

    • 01.10.2015 (3h) : Presentazione del corso, orario lezioni, libri di testo, programma, esami, regole di base. Introduzione al linguaggio e simbolismo matematico: Quantificatori Ogni ed Esiste, Esiste ed unico. Teoria elementare degli INSIEMI. Tre descrizioni per un insieme: elenco elementi, proprieta' caratterizzante, Diagrammi di Venn. Inclusione, inclusione propria, appartenenza, uguaglianza. Esempi ed Esercizi. Unione, Intersezione, Complementare Proprieta' e leggi di De Morgan (con dimostrazione).
    • 05.10.2015 (+3h=6h) : Ripasso definizione di complementare e leggi di De Morgan (con dimostrazione). Insieme Differenza, Insieme delle Parti, Prodotto cartesiano. Esempi ed Esercizi. LOGICA: Definizione di proposizione, negazione, congiunzione, disgiunzione, implicazione, doppia implicazione. Equivalenza di proposizioni. Tavole di Verita'. Esempi ed Esercizi.
    • 06.10.2015 (+1h=7h): Esercizi su Tavole di Verita'. FUNZIONI: Definizione di funzione, insieme di partenza e insieme di arrivo. Funzioni coincidenti. Immagine. Esempi.
    • 08.10.2015 (+3h=10h): FUNZIONI: ripasso definizione funzione e di immagine. Funzione identita'. Funzioni costanti. Controimmagine di un sottoinsieme. Proprieta' di immagine e controimmagine rispetto unione e intersezione. Funzioni iniettive, suriettive e biettive. Esempi ed esercizi su funzioni. Esercizi di logica: Tabelle di verita' con tre proposizioni. Proposizioni logiche, vere, false e negazioni.
    • 12.10.2015 (+3h=13h): Composizione di funzione e proprieta'. Esempi ed esercizi. Dimostrazione che la composizioni di funzioni iniettive e' iniettiva, la composizioni di funzioni suriettive e' suriettiva, e che quindi la composizioni di funzioni biettive e' biettiva (con dimostrazioni). Funzione inversa di funzioni biettive e proprieta'. Determinazione della funzione inversa. Inversa della composizione di funzione, con dimostrazione. Esempi ed Esercizi. CARDINALITA': Cardinalita' di un insieme. Insiemi Equipotenti. Insiemi finiti. Cardinalita' minore o uguale. Insiemi infiniti, difinizioni equivalenti. Insiemi numerabili. Numerabilita' dell'insime degli interi Z (con dim).
    • 13.10.2015 (+3h=16h): Se insiemi stessa cardinalita' finita, allora funzione e' iniettiva se e solo se suriettiva (con dim.). PRINCIPIO di INDUZIONE: Principio di induzione e formulazioni equivalenti. Esempi e controesempi ed esercizi. Cardinalita' dell'insieme delle parti di un insieme finito (dim.1 usando il principio di induzione). Principio di induzione generalizzato. Esempi ed Esercizi su Proposizioni logiche, vere, false e negazioni, proprieta' della controiimagine, funzioni e inverse. [2h+1h ora di recupero della scorsa settimana].
    • 15.10.2015 (+3h=19h): 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.
    • 19.10.2015 (+3h=22): 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 per 2 e 3 insiemi). Esempi ed applicazioni. Cardinalita' del prodotto di insiemi finiti. Regola del prodotto. Esempi ed applicazioni. Introduzione a COMBINATORIA: Scegliere k elementi in un insieme con n elementi. Descrizione dei 4 casi: scelta di k elementi senza ripetizione (k minore o uguale ad n) ordine importante o no; scelta di k elementi con ripetizione ordine importante o no. Esempi. Esercizi su Funzioni iniettive, suriettive e biettive, inverse, composizioni e su principio di induzione.
    • Nei Martedi 20, 27 Ottobre e 3 Novembre, le lezioni inizieranno alle 8.45 per anticiparci delle ore e fare un ponte o finire prima.
    • 20.10.2015 (+3h=25): COMBINATORIA: Caso 1)=SENZA ripetizioni: 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. Formula di Newton. Seconda dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando la formula di Newton. Caso 2) CON ripetizioni. Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Cardinalita' dell'insieme di funzioni tra due insiemi finiti. Esempi e esercizi. Esercizi su principio di induzione. [D'accordo con gli studenti 2h+1h ora per anticiparci delle ore e fare un ponte o finire prima].
    • 22.10.2015 (+3h=28): Caso con ripetizioni. Scegliere k elementi con ripetizione in un insieme con n elementi. 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 (senza dim). Esempi ed Esercizi. RELAZIONI. Definizioni di relazione tra insiemi. Esempi. Relazione vuota, totale, associata ad una funzione. Relazione su un insieme, relazione identica. Esempi Esercizi su formula chiusa di una successione, prima e seconda forma del principio di induzione. Anagrammi, esercizi di combinatoria.
    • 26.10.2015 (+3h=31): RELAZIONI. 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. Definizione di classe di equivalenza ed esempi. Esempi ed Esercizi.
    • 27.10.2015 (+3h=34): Ripasso deifinizone relazioni di equivalenza e definizione di classe di equivalenza. Teorema sulle proprieta' delle classi di equivalenza (con dimostrazione). Esempi. Definizione di PARTIZIONE di un insieme; esempi. Teorema: ogni relazione di equivalenza definisce una partizione (senza dimostrazione). Teorema: ogni partizione definisce una relazione di equivalenza (senza dimostrazione). Insieme quoziente. Esempi ed Esercizi su relazioni di ordine, di equivalenza e insieme quoziente. Esercizi su principio di induzione e combinatoria.
    • 29.10.2015 (+3h=37): NUMERI INTERI. Proprieta' dei 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'. Teorema: esistenza del MCD e algoritmo di Euclide per la sua determinazione e Identita' di Bezout (con dimostrazione). Definizione di un minimo comune multiplo e di mcm. Proprieta'. Esempi ed Esercizi.
    • 02.11.2015 (+3h=40): NUMERI PRIMI. Definizione di numeri primi. Definizioni equivalenti (con dimostrazione). Teorema Fondamentale dell'aritmetica: unica fattorizzazione in potenze di primi distinti (dimostrato esistenza fattorizzazione). 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. Teorema esistenza infiniti numeri primi (con dimostrazione). Crivello di Eratostene per trovare numeri primi. Metodi di Fattorizzazione: Metodo di Eratostene e Metodo di Fermat.
    • 03.11.2015 (+3h=43): 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. Definizione della relazione di congruenza: relazione di equivalenza, descrizione classi resto, descrizione quoziente. Esempi. Esercizio su relazioni di equivalenza e su principio di induzione. [D'accordo con gli studenti 2h+1h ora per anticiparci delle ore e fare un ponte o finire prima].
    • Giovedi 5 Novembre no lezione per gli Stati Generali. Ricevimento straordinario 10:00-11:30.
    • 09.11.2015 (+3h=46): 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 pu' curiosi: un po' di storia del teorema e un link un po' meno matematico Definizione della funzione di Eulero. Teorema di Eulero Fermat (senza dimostrazione). Applicazione al calcolo di potenze modulo n. Esempi ed Esercizi. Scrittura dei numeri in base n. Esempio in base 10,2 e 8. Criteri di divisibilita' per: 2,3,5,9,4,25.
    • 10.11.2015 (+2h=48): CONGRUENZE LINEARI: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Teorema che descrive tutte e sole le soluzioni di una congruenza lineare (usando le equazioni diofantee), descrizione delle soluzioni non congruenti modulo n. Proprieta'. Esempi ed Esercizi.
    • 12.11.2015 (+3h=51): 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 solo dell'esistenza della soluzione). Esempi ed Esercizi. Esercizi su congruenze, e su potenze. Introduzione alla crittografia. Crittografia chiave pubblica e chiave privata. Sistema Crittografico RSA (R. Rivest, A. Shamir e L. Adleman): Definizione, crittografia a chiave pubblica ed esempi.
    • No lezione nella settimana 16-20 Novembre. Il ricevimento di Martedi 17 Novembre e' stato spostato a lunedi 16 Novembre 10:00- 11:30. Prossima lezione lunedi 23 Novembre: Strutture Algebriche.
    • 23.11.2015 (+3h=54): STRUTTRE ALGEBRICHE: Definizione di struttura algebrica, operazione, operazione associativa, elemento neutro. Esempi. MONOIDI: definizione, esempi, monoide delle parole. Definizione di operazione commutativa ed esempi. Monoidi commutativi e non commutativi. Definizione di elementi invertibili ed esempi.
    • Nei Martedi 24 Novembre, 1 Dicembre, 15 Dicembre le lezioni inizieranno alle 8.45 a causa delle ore perse per gli stati generali.
    • 24.11.2015: (+3h=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. Prodotto di potenze e potenza di potenze. 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 su strutture algebriche. [D'accordo con gli studenti 2h+1h ora per recuperare le ore perse durante gli stati generali].
    • 26.11.2015 (+3h=60) SOTTOGRUPPI: definizioni, teorema di caratterizzazione dei sottogruppi (senza dimostrazione). Esempi. Intersezione di sottogruppi e' un sottogruppo (con dimostrazione), l'unione in generale no. Esempi. Ordine di un gruppo: definizione ed esempi, ordine di un sottogruppo. Teorema di Lagrange (senza dimostrazione). Sottogruppo ciclico generato da un elemento. Ordine o periodo di un elemento. Proprieta' delle potenze di un elemento in relazione al suo ordine. Esempi ed Esercizi.
    • 30.11.2015 (+3=63): 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. Esempi in (Z_n,+) ed Esercizi. Proprieta' nei gruppi ciclici finiti: per ogni divisore h dell'ordine esiste un sottogruppo di ordine h. Esempi ed Esercizi. Monoide commutativo (Zn,.): definizione ed elementi invertibili. Gruppo abeliano: (Zp*,.) con p primo. Esempi ed Esercizi. Esercizi su strutture algebriche associative, commutative, esistenza elemento neutro, esistenza inverso.
    • 01.12.2015 (+3h=66): Esempio di gruppo non commutativo: GRUPPO SIMMETRICO o GRUPPO di PERMUTAZIONI. Definizione di gruppo simmetrico, notazione degli elementi, e degli inversi e della composizione. Esempi. Definizione di ciclo. Ogni ciclo corriponde ad una permutazione. Ogni permutazione puo' scriversi come ciclo o prodotto di cicli disgiunti. Definizione di trasposizione. Definizione di ordine di una permutazione. Ogni ciclo puo' essere scritto come prodotto di trasposizioni. Ogni permutazione puo' essere scritta come prodotto di trasposizioni. Permutazioni pari e dispari. Esempi ed Esercizi. [D'accordo con gli studenti 2h+1h ora per recuperare le ore perse durante gli stati generali].
    • 03.12.2015 (+3h=69): 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. Esempi in (Z,+,.), (Q,+,.), (R,+,.), (Zn,+,.). Se un elemento e' invertibile allora non e' un divisore dello zero (con dimostrazione). Negli anelli unitari finiti, ogni elemento o e' divisore dello zero o e' invertibile. Divisori dello zero ed invertibili in (Zn,+,.). Esempi ed Esercizi. Esercizi su divisori dello zero e su invertibili negli anelli. Calcolo dell'inverso. Esercizi su gruppi, generatori, sottogruppi e ordini degli elementi. Esercizio su gruppi di permutazioni, ordine, cicli, parita' e sottogruppo generato.
    • Prossima lezione, Giovedi 10 Dicembre. Prossimo Ricevimento Studenti: Giovedi 10 Dicembre ore 15:00-16:00.
    • 10.12.2015. (+3h=72) Campo dei NUMERI COMPLESSI (C,+,.): definizione, sull'insieme C=RxR e di . e + e verifica proprieta' di campo. Identificazione dei numeri reali con gli elementi (a,0). Definizione dell'unita' immaginaria i=(0,1). Forma algebrica dei numeri complessi. Definizione di coniugato di un numero e proprieta'. Definizione di modulo di un numero complesso e proprieta'. Forma algebrica dell'inverso. Esempi ed Esercizi. MATRICI: Definizione di matrice e dell'insieme Mat_nxm(K) delle matrici di ordine nxm a coefficienti in un qualsiasi campo (K,+, .). Esercizi su divisori dello zero e invertibili, sui gruppi ciclici, generatori e ordini, sui gruppi di permutazione.
    • 14.12.2015. (+3h=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,+, .), anello non commutativo unitario. Definizione di COMPLEMENTO ALGEBRICO di un elemento di una matrice. Definizione di DETERMINANTE (di una MATRICE QUADRATA). 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). Definizione e Calcolo della MATRICE INVERSA, usando i complementi algebrici. Esempi ed Esercizi.
    • 15.12.2015.(+3h=78) 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 o Valenza di un vertice. Teorema delle stette di mano: 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. Teorema di esistenza di circuiti euleriani. Teorema di esistenza di cammini euleriani. Definizone di cammino hamiltoniano. Esempi ed esercizi.[D'accordo con gli studenti 2h+1h ora per recuperare le ore perse durante gli stati generali]
    • 17.12.2015. (+3h=81) GRAFI: Grafi bipariti. Teorema di caratterizzazione deig rafi bipartiti (senza dim.) Esempi grafi bipartiti completi. Grafi PLANARI. Esempi grafi K5 e K3,3. Teoremi di Kuratowski di caratterizzazione dei grafi planari. Definizione di ALBERI. Teorema di caratterizzazione degli alberi. Esempi ed esercizi. Esercizi su grafi e su alberi. RETICOLI: definizione di reticolo algebrico (R,^,V). Esempio di reticolo dell'insieme delle parti di un insieme finito. Teorema sulle leggi di idempotenza (senza dimostrazione). Teorema che lega V unione e ^ intersezione (con dimostrazione). Definizione: Reticoli distributivi, elemento neutro rispetto ad unione e intersezione. Complemento di un elemento. Teorema: nei reticoli distributivi con elementi neutri, se il complemento esiste e' unico (senza dim.). Definizione di reticolo di BOOLE.
    • 21.12.2015. (+3h=84) Legame tra reticoli ed insiemi parzialmente ordinati. Definizione di massimo e minimo, estremo inferiore ed estremo superiore in un insieme parzialmente ordinato. Esempi: 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 finito. 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 ammette sup e inf per ogni coppia di elementi. Relazione ta minimo e massimo ed elementi neutri. Esempi.
    • Esercizi sui reticoli. 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. Esercizi sui grafi
    • 22.12.2015. (+2h=86) Esercizi sui reticoli, reticoli distributivi e reticoli dei divisori, sulle matrici, sui numeri complessi, sulle strutture algebriche, sulla combinatoria, sul teorema cinese dei resti, sul principio di induzione. THAT'S IT!
    • Primo appello fissato per il 12 gennaio 2016 Prenotazione obbligatoria su Esse 3 nei tempi richiesti.
    • Prima di presentarsi all'esame studiare attentamenete la pagina Regole e faq.

    Stay hungry Stay foolish. S. Jobs