Matematica Discreta 2016/2017 (M-Z)

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

Inizio lezioni Martedi 27 Settembre 2016 Aula A, piano terra, Dipartimento di Informatica. Orario lezioni: Lunedi 8:30-10:30; Martedi 8:30-11:30; Giovedi 8:30-11:30. Fine lezioni Giovedi 23 Dicembre 2016.

Programma PROVVISORIO del corso

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

Ricevimento

Per i prossimi orari di Ricevimento studenti consultare la pagina esami.

Tutorato:

Dovrebbe essere attivo 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 2016/2017.

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 e comprendere prima di presentrasi agli esami.

    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/MD16MZ, 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

    • 27.09.2016 (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).
    • 29.09.2016 (+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. Esercizi di logica: Tabelle di verita' con tre proposizioni. Proposizioni logiche, vere, false e negazioni.
    • 03.10.2016 (+2h=8h): FUNZIONI: Definizione di funzione, insieme di partenza e insieme di arrivo. Funzioni coincidenti. Immagine. Controimmagine di un sottoinsieme. Funzione identita'. Funzioni costanti. Proprieta' di immagine e controimmagine rispetto unione e intersezione. Esempi ed Esercizi su logica e funzioni.
    • 04.10.2016 (+3h=11h): Ripasso definizione funzione. Funzioni iniettive, suriettive e biettive. Esempi ed esercizi su funzioni. Composizione di funzione e proprieta'. Esempi ed esercizi. Esercizi su inisiemi e di logica: Tabelle di verita' con tre proposizioni. Proposizioni logiche, vere, false e negazioni.
    • 06.10.2016 (+3h=14h): 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. Esempi ed esercizi.
    • 10.10.2016 (+2h=16h): Ripasso insiemi equipotenti e insiemi finiti. Propireta' insiemi finiti. Se insiemi stessa cardinalita' finita, allora funzione e' iniettiva se e solo se suriettiva. Cardinalita' minore o uguale. Insiemi infiniti, difinizioni equivalenti. Insiemi numerabili. Numerabilita' dell'insime degli interi Z. 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.
    • 11.10.2016 (+3h=19h): Esercizio su principio di induzione. SUCCESSIONI. Definizioni ed esempi. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi ed Esercizi. Esercizi ed esempi su funzioni.
    • 13.10.2016 (+4h=23h): Esercizio su formula chiusa di successioni ricorsive con principio di idnuzione seconda forma. Esempi ed Esercizi. Numeri di Fibonacci: definizione ricorsiva come modellazione della popolazione di conigli, formula ricorsiva e formula chiusa. Torri di Hanoi: definizione come gioco, formula ricorsiva e formula chiusa (con dimostrazione). Simbolo di sommatoria e proprieta'. Esercizio su principio di induzione. Cardinalita' dell'unione di insiemi finiti. Caso generale di insiemi disgiunti. Regola della somma. Caso generale con intersezioni non vuote per due insiemi: Principio di inclusione-esclusione (con dimostrazione per 2. Esempi. Enunciato Principio di inclusione-esclusione con 3 insiemi. Esercizi su funzioni. Esercizi su formula chiusa di successioni ricorsive con principio di idnuzione (un ora un piu' d'accordo con gli studenti)
    • 17.10.2016 (+2h=25h): Esercizio su principio di induzione con simbolo di sommatoria. Cardinalita' dell'unione di insiemi finiti: caso generale con intersezioni non vuote per due e tre insiemi (con dimostrazione per 2 e 3 insiemi). Esempi ed applicazioni. Cardinalita' del prodotto di insiemi finiti. 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. Caso 1) i) =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.
    • 18.10.2016 (+3h=28h): 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 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) i) 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. Funzione caratteristica di un sottoinsieme. Terza dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando le funzioni caratteristiche. Esercizi su principio di induzione
    • 20.10.2016 (+3h=31): Caso 2) ii) Scegliere k elementi con ripetizione in un insieme con n elementi, ordine non e' importante: Combinazioni con ripetizioni di n oggetti di classe k. Calcolo (senza dim). Esempi ed Esercizi. Esercizi su Combinatoria. RELAZIONI: Definizioni di relazione tra insiemi. Esempi. Relazione vuota, totale. Realazione associata ad una funzione. Relazione su un insieme, relazione identica. Esempi Esercizi su prima e seconda forma del principio di induzione.
    • 24.10.2016 (+2h=33): RELAZIONI. Relazione di ordine parziale: Riflessiva, Antisimmetrica, Transitiva. Insiemi parzialmente ordinati. Elementi confrontabili e insiemi totalmente ordinati. Esempi ed Esercizi. Relazioni di equivalenza: Riflessiva, Simmetrica, Transitiva. Esempi ed Esercizi.
    • 25.10.2016 (+3h=36): 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 combinatoria.
    • 27.10.2016 (+3h=39): NUMERI INTERI. Proprieta' dei numeri interi. Definizione di divisore e multiplo e proprieta'. Divisibilita' di ogni combinazione lineare (con dimostrazione). 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'. Esercizio su induzione con divisione. Esercizi su relazione di equivalenza con divisione.
    • 31 Ottobre e 01 Novembre no lezione, prossima lezione giovedi 4 Novembre. Coming Soon: Teorema: esistenza del MCD e algoritmo di Euclide per la sua determinazione e Identita' di Bezout .
    • 03.11.2016 (+3h=42): 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. NUMERI PRIMI. Definizione di numeri primi. Definizioni equivalenti (senza dimostrazione). Teorema Fondamentale dell'aritmetica: esiste unica fattorizzazione in potenze di primi distinti (dimostrato solo l'esistenza della fattorizzazione). Esempi. Esercizi su relazione di equivalenza con divisione e induzione.
    • 07.11.2016 (+2h=44): NUMERI PRIMI. Ripasso definizione ed esistenza fattorizzazione. Applicazione della fattorizzazione per trovare divisori positivi 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. EQUAZIONI DIOFANTEE: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Esempi.
    • 08.11.2016 (+3h=47): EQUAZIONI DIOFANTEE: 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. Esercizi su MCD, Equazioni diofantee.
    • 10.11.2016 (+3h=50): 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 (senza dim.). 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. 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), Esempi ed Esercizi.
    • 21.11.2016 (+2h=52): CONGRUENZE LINEARI: Ripasso, metodi di risoluzione. 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 solo dell'esistenza della soluzione). Esempi ed Esercizi.
    • 22.11.2016 (+3h=55): STRUTTURE 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. Esercizi su congruenze.
    • 24.11.2016 (+3h=58): Ripasso di struttura di Monoidi, elementi invertibili ed esempi. GRUPPI: definizioni, esempi, gruppi abeliani e non abeliani. Esempi. Relazioni di equivalenza compatibili con strutture algebriche. Teorema della struttura algebrica indotta sull'insieme quoziente (senza dimostrazione). Esempio fondamentale: relazione di congruenza modulo n (maggiore o uguale a 2) su Z compatibile con la somma : (Z_n,+). Esercizi su congruenze lineari, sistema di congruenze lineari.
    • 28.11.2016 (+2h=60): Ripasso Teorema della struttura algebrica indotta sull'insieme quoziente (senza dimostrazione). Esempio fondamentale: relazione di congruenza modulo n (maggiore o uguale a 2) su Z compatibile con il prodotto: (Z_n, .). Monoide commutativo (Z_n, .). SOTTOGRUPPI: definizioni, teorema di caratterizzazione dei sottogruppi (senza dimostrazione). Esempi. Ordine di un gruppo: definizione ed esempi, ordine di un sottogruppo. Teorema di Lagrange (senza dimostrazione). Sottogruppo ciclico generato da un elemento: insieme delle potenze (multiplo) di un elemento. Ordine o periodo di un elemento. Esempi.
    • 29.11.2016 (+3=63): Ripasso sottogruppo ciclico generato da un elemento e ordine di un elemento. Proprieta' delle potenze di un elemento in relazione al suo ordine. Esempi ed Esercizi. GRUPPI CICLICI finiti ed infiniti: definizione ed esempi. Proprieta' dei gruppi ciclici: sono abeliani, formula per l'ordine degli elementi nei gruppi ciclici finiti. Descrizione dei generatori. Esempi ed Esercizi. Esempi in (Z_n,+) ed Esercizi. Monoide commutativo (Zn,.): definizione e determinazione degli elementi invertibili. Gruppo abeliano: (Zp*,.) con p primo (con dimostrazione). Esempi ed Esercizi. Esercizi su strutture algebriche associative, commutative, esistenza elemento neutro.
    • 01.12.2016 (+3h=66): 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 (senza dim.). Divisori dello zero ed invertibili in (Zn,+,.). Esempi ed Esercizi. Esercizi su gruppi, generatori, e ordini degli elementi. Esercizi su strutture algebriche.
    • 05.12.2016 (+2h=68) Ripasso definizione di Anelli. definizione di CAMPO. Esempi. GRAFI: definizione di grafo, esempi. Disegno di un grafo. Vertici adiacenti, lati incidenti. Esempi. Definizione di grafo orientato, di multigrafo e di multigrafo orientato. Isomorfismo di grafi. Grado o Valenza di un vertice. Esempi. Teorema delle strette di mano: formula che lega il numero dei lati ai gradi dei vertici (con dimostrazione). Numero di vertici dispari in un grafo (con dimostrazione). Esempi ed Esercizi
    • 06.12.2016 (+3h=71): Esercizio su strutture algebriche. Esempio di gruppo non commutativo: GRUPPO SIMMETRICO o GRUPPO di PERMUTAZIONI. Definizione di gruppo simmetrico,. Notazione degli elementi, 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.
    • 12.12.2016 (+2h=73): GRAFI: Grafo completo ed esempi. Definizione di cammino e circuito (o ciclo). Grafo connesso. Definizione di cammino euleriano, definizione di circuito euleriano. Teorema di esistenza di circuiti euleriani (senza dim.) . Corollario di esistenza di cammini euleriani (senza dim.) . Definizone di cammino hamiltoniano. Esempi ed esercizi. Grafi bipariti. Teorema di caratterizzazione dei grafi bipartiti (senza dim.) Esempi: grafi bipartiti completi. Grafi PLANARI. Esempi grafi K5 e K3,3. Teoremi di Kuratowski di caratterizzazione dei grafi planari (senza dim.) . Definizione di ALBERI. Teorema di caratterizzazione degli alberi (senza dim.) . Esempi ed Esercizi su grafi e su alberi.
    • 13.12.2016 (+3h=76): RETICOLI: definizione di reticolo algebrico (R,^,V). Esempio di reticolo dell'insieme delle parti di un insieme finito. Proprieta': leggi di idempotenza e che lega V unione e ^ intersezione. Definizione: Reticoli distributivi, elemento neutro rispetto ad unione e intersezione. Complemento di un elemento. Esempio di reticolo dell'insieme delle parti di un insieme finito Teorema: nei reticoli distributivi con elementi neutri, se il complemento esiste e' unico (senza dim.). Definizione di reticolo di BOOLE. Esercizi su gruppo Simmetrico. 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.
    • 15.12.2016 (+3h=79): Legame tra reticoli ed insiemi parzialmente ordinati. Esempi: numeri naturali con la relazione di minore o uguale; insieme dei divisori di un intero n, con relazione di divisione. Diagrammi di Hasse di un insieme parzialmente ordinato finito. Definizione di estremo inferiore ed estremo superiore in un insieme parzialmente ordinato. Esempi. CAMPO 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,+, .). Definizione 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.
    • 19.12.2016 (+2h=81): Ripasso reticoli algebrici e reticoli ordinati. Teorema: ogni reticolo algebrico e' un insieme parzialmente ordinato che ammette sup e inf per ogni coppia di elementi. Teorema: ogni insieme parzialmente ordinato che ammette sup e inf per ogni coppia di elementi e' un reticolo algebrico. 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.
    • 20.12.2016 (+3h=84) MATRICI: 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.
    • 22.12.2016 (+2h=86): Esercizi di ricapitolazione sul corso. That's it.

    Stay hungry Stay foolish. S. Jobs