Corso di Laurea Triennale in   "Informatica"   Materiale didattico per il corso di   MATEMATICA DISCRETA     Docente:   Fabio Gavarini

---

Ultimo aggiornamento:   20 Agosto 2019   -   Fabio Gavarini

  PROGRAMMA del corso 2017-18   (versione definitiva)

  DIARIO del CORSO 2017-18   -   qui si illustra in dettaglio lo sviluppo del corso, lezione per lezione, man mano che è stato svolto.

ESAMI SCRITTI (testi & voti) del 2017-18:   18 Settembre 2018 (testo, testo & svolgimento , voti)   -   4 Settembre 2018 (testo, testo & svolgimento, voti)   -   3 Luglio 2018 (testo, testo & svolgimento, voti)   -   20 Giugno 2018 (testo, testo & svolgimento, voti)   -   19 Febbraio 2018 (testo, testo & svolgimento voti)   -   5 Febbraio 2018 (testo, voti)

                                       
  TESTI consigliati (contengono sostanzialmente tutto il materiale trattato nel programma, nonché numerosi esempi ed esercizi, inclusi esercizi svolti) :

• G. Campanella, Appunti di Algebra 1 & 2 - scaricabile da qui
• L. Geatti, G. Pareschi, Dispense - che trovate qui sotto
• S. Lipschutz, M. Lipson, Matematica discreta, Etas Libri, Milano, 1985   (in italiano)
• S. Lipschutz, M. Lipson, Discrete Mathematics, Third Edition, Schaum's Outlines, McGraw-Hill, 2007   (in inglese)
• G. M. Piacentini Cattaneo, Algebra, ed. Decibel - Zanichelli, Padova, 1996
• G. Quattrocchi, Breve Introduzione alla Teoria dei Grafi - scaricabile da qui

                                       
  DISPENSE (a cura di L. Geatti e G. Pareschi):     Alfabeto greco   -   Insiemi   -   Funzioni e cardinalità   -   Induzione   -   Relazioni - 1   -   Relazioni - 2   -   Aritmetica sugli interi, congruenze, Teorema Cinese del Resto   -   Aritmetica sugli interi, etc. (complementi)   -   Gruppi, anelli, campi   -   Reticoli   -   Algebre di Boole   -   Funzioni booleane   -   Forme minimali di una funzione polinomiale   -   Equazioni alle differenze finite (cenni)

                                       
  VIDEOLEZIONI (del prof. F. Gavarini)   -   in ordine progressivo di sviluppo del programma (da notare che non coprono tutto il programma):
      N.B.: in caso di problemi, si possono scaricare anche da questa pagina (per la quale il sottoscritto Fabio Gavarini non si assume alcuna responsabilità)

• Insiemi   (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)
• Corrispondenze   (corrispondenze tra insiemi e operazioni tra di esse)
• Funzioni 1   (funzioni; iniettività, suriettività, biiettività)
• Funzioni 2   (composizione di funzioni, funzioni invertibili)
• Funzioni caratteristiche   (funzioni caratteristiche in un insieme)
• Relazioni   (relazioni in un insieme: generalità, esempi)
• Equivalenze 1   (equivalenze e partizioni)
• Equivalenze 2   (equivalenze e funzioni)
• Operazioni 1   (operazioni in un insieme; insiemi con una operazione)
• Operazioni 2   (insiemi con più operazioni)
• Numeri naturali   (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)
• Induzione   (metodo di dimostrazione per induzione [semplice / forte / minimo])
• Divisione   (divisione con resto tra numeri naturali)
• Numerazione   (numerazione in base arbitraria / scrittura posizionale)
• Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
• Cardinalità 2   (Secondo Teorema di Cantor)   -   N.B.: è lo sviluppo consecutivo (senza transizione) di Cardinalità 1
• Insiemi ordinati   (generalità, esempi, elementi speciali)
• Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)
• Reticoli 2   (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)
• Reticoli 3   (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi)
• Algebre di Boole 1   (definizioni; esempi, controesempi; Teorema di Equivalenza [con anelli booleani unitari])
• Algebre di Boole 2   (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])
• Funzioni ricorsive 1   (funzioni [=successioni] ricorsive: generalità, casi particolari, esempi; Teorema di Ricorsione [di esistenza e unicità])
• Funzioni ricorsive 2   (funzioni [=successioni] ricorsive lineari omogenee come spazio vettoriale; calcolo di una base, e di una successione specifica, per il caso a coefficienti costanti di grado 1)
• Funzioni ricorsive 3.1   (risoluzione di equazioni ricorsive lineari omogenee a coefficienti costanti di grado 2: caso di due radici distinte o di una sola radice)
• Funzioni ricorsive 3.2   (risoluzione di equazioni ricorsive lineari omogenee a coefficienti costanti di grado 2: caso reale con due radici (distinte) complesse coniugate)   -   N.B.: è lo sviluppo consecutivo (senza transizione) di Funzioni ricorsive 3.1

                                       
  COMPITI d'ESAME di anni passati (per questo insegnamento e altri simili):

• Matematica Discreta:   14 Settembre 2016   -   1 Luglio 2016   -   17 Giugno 2016   -   16 Febbraio 2016   -   2 Febbraio 2016   -   12 Settembre 2013   -   12 Giugno 2013   -   22 Febbraio 2013   -   5 Febbraio 2013
• Algebra e Logica (CdL in "Ingegneria Informatica"):   22 Settembre 2017   -   5 Settembre 2017   -   18 Luglio 2017   -   5 Luglio 2017   -   21 Febbraio 2017   -   2 Febbraio 2017   -   18 Settembre 2015   -   4 Settembre 2015   -   15 Luglio 2015   -   3 Luglio 2015   -   23 Febbraio 2015   -   9 Febbraio 2015   -   18 Settembre 2014   -   2 Settembre 2014   -   16 Luglio 2014   -   4 Luglio 2014   -   18 Febbraio 2014   -   3 Febbraio 2014   -   13 Settembre 2013   -   5 Settembre 2013   -   19 Luglio 2013   -   5 Luglio 2013   -   14 Febbraio 2013   -   4 Febbraio 2013

                                       
  TEST di metà programma - 20 Dicembre 2017 ( testo , svolgimento)

  ESERCIZI (F. Gavarini):     Insiemi, Funzioni, Relazioni   -   Induzione, Scrittura posizionale (=numerazione in base arbitraria)   -   Scrittura posizionale, M.C.D., Equazioni diofantee   -   Equazioni diofantee, Congruenziali, Mdulari; Aritmetica modulare   -   Insiemi ordinati, Reticoli   -   Reticoli, Algebre di Boole   -   Funzioni ricorsive   -   Polinomi booleani

  ESERCIZI (L. Geatti & G. Pareschi):     Insiemi, operazioni sugli insiemi, funzioni   -   Cardinalità, principio di induzione   -   Relazioni, relazioni di equivalenza   -   Relazioni, relazioni d'ordine   -   M.C.D., algoritmo di Euclide, equazioni lineari a coefficienti interi   -   Congruenze e sistemi di congruenze   -   Somma e prodotto su Z_n, aritmetica modulare   -   Gruppi e applicazioni   -   Mix su insiemi, relazioni, aritmetica modulare   -   Reticoli   -   Algebre di Boole   -   Espressioni booleane   -   Equazioni alle differenze finite   -   Logica Matematica

  ESERCIZI SVOLTI (L. Geatti & G. Pareschi):     Insiemi, cardinalità, induzione, funzioni ricorsive (testo, soluzioni)   -   Relazioni (testo, soluzioni)   -   Aritmetica sugli interi, congruenze (testo, soluzioni)   -   Gruppi, anelli e campi (testo, soluzioni)   -   Reticoli (testo, soluzioni)   -   Algebre di Boole (testo, soluzioni)   -   Logica Matematica (testo, soluzioni)

  ESERCIZI del TUTORATO 2017-18 (F. Gaffi):   1 • Insiemi, Funzioni, Relazioni   -   2 • Relazioni di equivalenza, Principio di induzione   -   3 • Induzione, Scrittura posizionale, Coefficienti binomiali   -   4 • Scrittura posizionale, Coefficienti binomiali, M.C.D.   -   5 • Equazioni diofantee, Equazioni congruenziali, Aritmetica modulare   -   6 • Aritmetica modulare, Equazioni congruenziali, Sistemi di equazioni congruenziali   -   7 • Insiemi ordinati, Reticoli   -   8 • Reticoli, Algebre di Boole   -   9 • Polinomi booleani   -   10 • Multigrafi, Multidigrafi   -   11 • Multigrafi, Multidigrafi, Alberi

  ESERCIZI del TUTORATO 2015-16 (S. Fioravanti):   1 • Relazioni, insiemi   -   2 • Induzione, divisione in N   -   3 • Induzione, coefficienti binomiali, notazione posizionale   -   4 • Cardinalità, divisione in Z, M.C.D.   -   5 • Equazioni diofantee, equazioni congruenziali, aritmetica modulare   -   6 • Sistemi di equazioni congruenziali, aritmetica modulare, insiemi ordinati, reticoli   -   7 • Reticoli   -   8 • Polinomi booleani   -   9 • Successioni ricorsive, reticoli, algebre di Boole   -   10 • Multigrafi e multidigrafi   -   11 • Alberi

                                       
  ALTRO MATERIALE disponibile in rete (per gentile concessione degli autori):     pagina del corso 2014-15 (Geatti)   -   dispense (Campanella)   -   esercizi (Campanella)   -   dispense (Caranti)   -   Numeri naturali (D'Andrea)   -   Cardinalità (D'Andrea)   -   Numeri interi (D'Andrea)   -   Congruenze, aritmetica modulare (D'Andrea)   -   note su argomenti varî (Damiani)   -   lezioni, esercitazioni, prove di valutazione, ecc. (Fontana)   -   materiale relativo a corsi di Algebra e Logica (Gavarini)   -   Breve Introduzione alla Teoria dei Grafi (Quattrocchi)   -   esercitazioni, prove d'esame, ecc. (Tartarone)

  Modalità d'ESAME  

L'esame consiste in una prova scritta e una prova orale, entrambe obbligatorie;
condizione preliminare per essere ammessi alla prova orale è aver già superato una prova scritta (con un voto sufficiente, cioè almeno 18).
Si può sostenere la prova orale anche in un appello successivo o in una sessione successiva a quella in cui si sia superata la prova scritta.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
È possibile sostenere la prova scritta anche più di una volta: in tal caso, sarà considerato come rilevante il voto più alto ottenuto.
Se si sostiene una prova orale senza successo - perché respinti o ritirati - il voto con cui sia stata precedentemente superata la prova scritta
resta valido
per presentarsi di nuovo alla prova orale; in altre parole, si deve rifare soltanto la prova orale, e non anche la prova scritta.
È possibile sostenere nuovamente la prova orale anche nella stessa sessione.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
Per partecipare a ciascuna prova (scritta o orale), *è necessario prenotarsi*, nei giorni precedenti, attraverso il sito Delphi.
In occasione di ciascuna prova (scritta e/o orale) è necessario portare con sé un documento di riconoscimento e (se lo avete) il libretto universitario.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
Così come il corso è tenuto in italiano, le prove d'esame (scritte e orali) devono essere ugualmente compilate in italiano. In casi particolari - precisamente, per studenti Erasmus o comunque non di madrelingua italiana - lo studente sotto esame può chiedere al docente (prof. Gavarini) di autorizzarlo a svolgere le suddette prove, in alternativa, in inglese, in francese o in spagnolo.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
Durante le prove (scritte e/o orali) è vietato l'uso di libri, appunti, dispense, calcolatrici, telefoni cellulari, tavolette (=tablets), scaltròfoni (=smartphones) e/o quant'altro:
in breve, è vietato l'uso di qualsiasi strumento di archiviazione/ricezione/trasmissione/elaborazione di dati. Fanno ECCEZIONE a questa regola i casi particolari previsti dal regolamento d'ateneo (invalidità, dislessia, ecc.) e riconosciuti dall'apposito ufficio CARIS che verranno gestiti secondo le indicazioni prescritte dal suddetto ufficio: a tal fine, gli studenti interessati sono tenuti a rivolgersi all'ufficio CARIS prima di presentarsi all'esame.
Durante una prova scritta non è consentito uscire dall'aula - salvo emergenze e esigenze sanitarie - se non per consegnare il proprio compito (e dunque concludere la propria partecipazione alla prova scritta).
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
N.B.: nel caso di eventuali appelli straordinari, si applicano le stesse regole che per gli appelli ordinari.

Per studenti del vecchio ordinamento:
Gli studenti di un eventuale vecchio ordinamento che dovessero sostenere l'esame
secondo un programma ridotto o per un numero ridotto di CFU (cioè per meno di 9 CFU)
sono tenuti a comunicarlo in anticipo al professor Gavarini.