Matematica Discreta 2017/2018 (M-Z)

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

Inizio lezioni 26 Settembre 2017 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 21 Dicembre 2017.

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.

Corsi di Recupero

E' stato attivato Corso di recupero in Matematica.

Seconda prova di autovalutazione:

Giovedi 11 Gennaio ore 9:00-11:00, Aula A, piano terra, Dipartimento di Informatica.

Prova di autovalutazione:

Martedi 14 Novembre, Aula B, I piano, Dipartimento di Informatica, 15:00-17:00. (Esercizi di riepilogo sulla prima parte svolti per simulare un esame,non vengono corretti e non si prendono le presenze)

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 2017/2018.

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

    • 26.09.2017 (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.
    • 28.09.2018 (+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.
    • 02.10.2017 (+2h=8h): FUNZIONI: Definizione di funzione, insieme di partenza e insieme di arrivo. Funzioni uguali. Immagine di una funzione e di un sottoisnieme. Controimmagine di un sottoinsieme. Funzione identita'.Esempi. Esercizi su logica.
    • 03.10.2017 (+3h=11h): Ripasso funzioni, immagini e controimmagini. Esempi. Funzioni costanti. Proprieta' di immagine e controimmagine rispetto unione e intersezione. Funzioni iniettive, suriettive e biettive. Esempi ed esercizi su funzioni. Esempi ed Esercizi su logica: tabelle di verita' con tre proposizioni, proposizioni logiche, vere, false e negazioni.
    • 05.10.2017 (+3h=14h): Ripasso definizione funzioni biettive. Esercizi. 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': Insiemi Equipotenti. Esempi. Esercizi su logica: Proposizioni logiche, vere, false e negazioni.
    • 09.10.2017 (+2h=16h): CARDINALITA': Cardinalita' di un insieme. Insiemi Equipotenti. Insiemi finiti. Esempi ed esercizi. Propireta' insiemi finiti. Se insiemi stessa cardinalita' finita, allora funzione e' iniettiva se e solo se suriettiva (senza dim.). Cardinalita' minore o uguale. Insiemi infiniti, difinizioni equivalenti. PRINCIPIO di INDUZIONE: Principio di induzione. Esempi. Cardinalita' dell'insieme delle parti di un insieme finito (dim.1 usando il principio di induzione).
    • 10.10.2017 (+3h=19h): PRINCIPIO di INDUZIONE: Principio di induzione e formulazioni equivalenti. Esempi e controesempi ed esercizi. SUCCESSIONI. Definizioni ed esempi. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi ed Esercizi. Esercizio su formula chiusa di successioni ricorsive con principio di induzione seconda forma. Esercizi ed esempi su funzioni.
    • 12.10.2017 (+3h=22h): Numeri di Fibonacci: definizione ricorsiva come modellazione della popolazione di conigli, formula ricorsiva e formula chiusa (senza dim.). 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. Cardinalita' dell'unione di insiemi finiti: Principio di inclusione-esclusione caso con intersezioni non vuote per due e tre insiemi (con dimostrazione). Cardinalita' del prodotto di insiemi finiti. Esempi. Esercizi su formula chiusa di successioni ricorsive con principio di induzione. Esercizi su principio di induzione con simbolo di sommatoria.
    • 16.10.2017 (+2h=24h): 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/ ordine non importante; scelta di k elementi con ripetizione ordine importante/ ordine non importante. Caso 1) =SENZA ripetizioni. Caso 1) i) =SENZA ripetizioni ordine importante: 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. Caso 1) ii) =SENZA ripetizioni ordine non importante: 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.
    • 17.10.2017 (+3h=27h): Caso 2) i) CON ripetizioni. Caso 2) i) =con ripetizioni ordine importante: Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Cardinalita' dell'insieme di funzioni tra due insiemi finiti. Esempi ed Esercizi. Caso 2) ii) =con ripetizioni ordine non importante: Combinazioni con ripetizioni di n oggetti di classe k. Calcolo (senza dim). Esempi ed Esercizi. Esercizi su Combinatoria. Esercizi su principio di induzione, su coefficiente binomiale e su formule chiuse.
    • 19.10.2017 (+3h=30): RELAZIONI: Definizioni di relazione tra insiemi. Esempi. Relazione vuota, totale. Realazione associata ad una funzione. Relazione su un insieme, relazione identica. Relazione di ordine parziale: Riflessiva, Antisimmetrica, Transitiva. Insiemi parzialmente ordinati. Elementi confrontabili e insiemi totalmente ordinati. Esempi ed Esercizi. Esercizi su combinatoria ed esercizi sul principio di induzione.
    • 23.10.2017 (+2h=32): Relazioni di equivalenza: Riflessiva, Simmetrica, Transitiva. Esempi ed Esercizi su relazioni di ordine e di equivalenza. Definizione di classe di equivalenza. Esercizi su relazioni di equivalenza e classi. Esempio a-b multiplo di n.
    • 24.10.2017 (+3h=35): Ripasso definizione di classe di equivalenza. Teorema sulle proprieta' delle classi di equivalenza (con dimostrazione). Esempi. Definizione di PARTIZIONE di un insieme: le cassi di equivalenza definiscono una partizione (senza dimostrazione). Insieme quoziente. Esempi ed Esercizi su relazioni di ordine, di equivalenza e insieme quoziente. Esercizi su logica.
    • 26.10.2017 (+3h=38): NUMERI INTERI. Proprieta' dei numeri interi. Definizione di divisore e multiplo. 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'. Definizione di un minimo comune multiplo e di mcm. Esercizio su induzione con divisione. Esercizi su relazione di equivalenza con divisione.
    • 30.10.2017 (+2h=40): Teorema: esistenza del MCD e algoritmo di Euclide per la sua determinazione e Identita' di Bezout (con dimostrazione). Esempi ed Esercizi. NUMERI PRIMI. Definizione di numeri primi. Definizioni equivalenti (senza dimostrazione). Esercizi su combinatoria.
    • 31.10.2017 (+3h=43): Ripasso definizione numeri primi. Teorema Fondamentale dell'aritmetica: esiste unica fattorizzazione in potenze di primi distinti (dimostrato solo l'esistenza della fattorizzazione). Esempi. Applicazione della fattorizzazione per trovare divisori positivi di un numero: 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. Esercizi su MCD e Identita' di Bezout. Esercizi su funzioni.
    • 02.11.2017 (+3h=46): EQUAZIONI DIOFANTEE: Teorema di esistenza della soluzione (con dim.). 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 principio di induzione.
    • 06.11.2017 (+2h=48): 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.
    • 07.11.2017 (+3h=51): Esercizio su congruenze modulo p primo. 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. Scrittura dei numeri in base n. Esempio in base 10 e 8. Criteri di divisibilita' per: 2,3,5,9,4.
    • 9.11.2017 (+3h=54): 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 sistema di 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.
    • 15.11.2017: Prova di Autovalutazione
    • Prossima Lezione 20.11.2017: STRUTTURE ALGEBRICHE
    • 20.11.2017 (+2h=56): STRUTTURE ALGEBRICHE: Definizione di struttura algebrica, operazione, operazione associativa, elemento neutro. Esempi. MONOIDI: definizione, esempi, monoide delle parole. Definizione di operazione commutativa ed esempi. Esercizi su strutture algebriche.
    • 21.11.2017 (+3h=59): Ripasso di struttura di Monoidi. Monoidi commutativi e non commutativi. Definizione di 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,+). Esempio fondamentale: relazione di congruenza modulo n (maggiore o uguale a 2) su Z compatibile con il prodotto: (Z_n, .). Monoide commutativo (Z_n, .). Esercizio su principio di induzione. Esercizi su strutture algebriche associative, commutative, esistenza elemento neutro, invertibili.
    • Le lezioni del 23,27 e 28 Novembre sono sospese per le prove di accesso di Area Medica. Prossima Lezione 30.11.2017: Sottogruppi.
    • 30.11.2017 (+3h=62): 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. Proprieta' delle potenze (multiplo) di un elemento in relazione al suo ordine (senza dim.). Esempi ed Esercizi. Esercizio su strutture algebriche associative, commutative, esistenza elemento neutro, invertibili.
    • 04.12.2017 (+2=64): GRUPPI CICLICI 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 (con dimostrazione). Gruppo abeliano: (Zp*,.) con p primo (con dimostrazione). Esempi ed Esercizi su gruppi ciclici, generatori, ordini di elementi.
    • 05.12.2017 (+3h=67): 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.
    • 07.12.2017 (+3h=70): 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,+,.). Teorema: 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 su divisori dello zero e su invertibili negli anelli. Calcolo dell'inverso. Definizione di CAMPO. Esempi. Esercizio su gruppi di permutazioni, ordine, cicli, parita' e sottogruppo generato. Esercizio su gruppi, generatori e ordini degli elementi. Esercizio su strutture algebriche associative, commutative, esistenza elemento neutro, invertibili.
    • 11.12.2017. (+2h=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 complesso e proprieta'. Definizione di modulo di un numero complesso e proprieta'. Forma algebrica dell'inverso. Esempi ed Esercizi. Esercizi su divisori dello zero e invertibili e sui gruppi di permutazione.
    • 12.12.2017. (+3h=75) MATRICI: Definizione di matrice e dell'insieme Mat_nxm(K) delle matrici di ordine nxm a coefficienti in un qualsiasi campo (K,+, .). Matrici quadrate Mat_n(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. 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_n(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.
    • 14.12.2017. (+3h=78) Esercizi su: Matrici, numeri complessi, gruppi ciclici, divisori dello zero e invertibili in un anello, gruppi di permutazione, strutture algebriche.
    • 18.12.2017 (+2h=80) 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 sull'esistenza dei grafi. Grafo regolare, grafo completo ed esempi.
    • 19.12.2017 (+3h=83): GRAFI: Definizione di cammino e circuito (o ciclo). Grafo connesso. Distanza tra vertici. Definizione di cammino euleriano, definizione di circuito euleriano. Teorema di esistenza di circuiti euleriani (senza dim.) . Teorema 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.
    • 21.12.2017 (+3h=86): Esercizi di ricapitolazione sul corso. Esercizi su: grafi, alberi, matrici, combinatoria, teorema cinese dei resti, relazioni. That's it!.
    • Giovedi 11 Gennaio pre 9:00-11:00 prova di autovalutazione, Aula A piano terra.

    Stay hungry Stay foolish. S. Jobs