Corso di Laurea in Informatica
a.a 2017-2018 - primo semestre

Diario delle lezioni del corso - da 9 CFU - di

MATEMATICA DISCRETA

(elencate in ordine cronologico inverso)

DOCENTE:   Fabio Gavarini

Codocente:   Ilaria Damiani   -   Tutore: Francesco Gaffi

ORARIO

Lunedì 11:00-13:00   -   Mercoledì 9:00-11:00   -   Venerdì 9:00-11:00

PROGRAMMA
  (versione definitiva)  


BIBLIOGRAFIA:
[AaVv] - Autori Varî, Materiale vario disponibile in rete   (per gentile concessione degli autori)
[Cam] - G. Campanella, Appunti di Algebra 1   (per gentile concessione dell'autore)
[G-P] - L. Geatti, G. Pareschi, Appunti varî   (per gentile concessione degli autori)
[L-L] - S. Lipschutz, M. Lipson, Discrete Mathematics, Third Edition, Schaum's Outlines, McGraw-Hill, 2007
[PC] - G. M. Piacentini Cattaneo, Algebra - un approccio algoritmico, ed. Decibel/Zanichelli, Padova, 1996
[Qua] - G. Quattrocchi, Breve Introduzione alla Teoria dei Grafi   (per gentile concessione dell'autore)

  Materiale didattico vario (dispense, videolezioni, esercizi, compiti d'esame, ecc. ecc.) utile per questo corso  


                * * *                 * * *                 * * *                

QUARANTATREESIMA LEZIONE (prof.ssa Damiani) - 26 Gennaio 2018:
    Esercizi sugli alberi, costruzione di alberi ricoprenti, ecc. ecc.
    Esercizi su iniettività e suriettività di funzioni.
  FINE del CORSO  
      Bibliografia:   [L-L] Chapter 8, sections 5 and 8 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 4, Capitolo 6

QUARANTADUESIMA LEZIONE - 24 Gennaio 2018:
    Teorema: Ogni albero è un (multi)grafo bipartito.
    Albero ricoprente di un multigrafo connesso.
    Esistenza di alberi ricoprenti per un multigrafo connesso: algoritmi di Kruskal ("per addizione" o "per sottrazione") per il calcolo di un albero ricoprente in un multigrafo connesso.
    Esempi di applicazione degli algoritmi di Kruskal per la costruzione di alberi ricoprenti.
  FINE del PROGRAMMA (seguono solo ripasso e/o esercitazioni)
      Bibliografia:   [L-L] Chapter 8, section 8 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 4

QUARANTUNESIMA LEZIONE - 22 Gennaio 2018:
    Alberi (non orientati), foreste: definizione, esempi e controesempi.   -   Nota: ogni foresta è somma di alberi (le sue componenti connesse).
    Esercizio un multigrafo G è una foresta <=> ogni spigolo di G è un ponte.
    Teorema (caratterizzazione degli alberi): Per ogni multigrafo G, le seguenti proprietà sono equivalenti:
        (a) G è un albero;
        (b) G è aciclico, e aggiungendo a G un qualunque nuovo spigolo si forma un ciclo;
        (c) presi due vertici qualunque in G, esiste uno e un solo percorso dall'uno all'altro (in G);
        (d) G è connesso, e togliendo da G un qualunque spigolo si ottiene un sottomultigrafo sconnesso (cioè ogni spigolo di G è un ponte).
    Descrizione esplicita di tutti gli alberi con al più 6 vertici.
    Teorema (caratterizzazione degli alberi finiti): Per un multigrafo G:=(V,E) con un numero finito di vertici, le seguenti proprietà sono equivalenti:
          (a) G è un albero;   (b) G è aciclico e |E| = |V| - 1;   (c) G è connesso e |E| = |V| - 1.
    Foglie (o "vertici pendenti") in un multigrafo.   -   Teorema: Ogni albero finito con almeno due vertici possiede almeno due foglie.
      Bibliografia:   [L-L] Chapter 8, section 8 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 4

QUARANTESIMA LEZIONE (prof.ssa Damiani) - 19 Gennaio 2018:
    Esercizi sui polinomi booleani: calcolo di forme normali disgiuntive, forme minimiali, implicanti primi, ecc. ecc.
    Esercizi sui multigrafi e multidigrafi: cammini, cammini euleriani, calcolo del numero di cammini tramite le potenze (per il prodotto righe per colonne) della matrice di adiacenza, ecc. ecc.
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3; file Forme minimali di una funzione polinomiale - [L-L] Chapter 8, section 5; Chapter 15, sections 9 and 11 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 6

TRENTANOVESIMA LEZIONE - 17 Gennaio 2018:
    Relazione tra multi(di)grafi euleriani e semieuleriani.
    Teorema di caratterizzazione dei multidigrafi e multigrafi semieuleriani.
    L'Algoritmo di Fleury per il calcolo di un cammino euleriano (cenni).
    L'Algoritmo di Hierholzer per il calcolo di un cammino euleriano (cenni).
    Esercizi ed esempi sui grafi euleriani o semieuleriani; applicazioni dell'algoritmo di Fleury e dell'algoritmo di Hierholzer.
      Bibliografia:   [L-L] Chapter 8, section 5 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 6

TRENTOTTESIMA LEZIONE - 15 Gennaio 2018:
    Unione di multidigrafi, unione di multigrafi.
    Esercizi: (a) la matrice di adiacenza di una unione di multidigrafi o di multigrafi è in forma "a blocchi";
        (b) ogni multigrafo è l'unione delle sue componenti connesse.
    Cammini euleriani; multigrafi e multidigrafi euleriani o semieuleriani.
    Teorema (caratterizzazione dei multigrafi euleriani): Per ogni multigrafo connesso e finito G le seguenti proprietà sono equivalenti:
        (a) G è euleriano;
        (b) ogni vertice di G ha grado pari;
        (c) esiste una partizione dell'insieme degli spigoli di G in circuiti.
    Teorema (caratterizzazione dei multidigrafi euleriani): Per ogni multidigrafo fortemente connesso e finito G le seguenti proprietà sono equivalenti:
        (a) G è euleriano;
        (b) ogni vertice di G ha grado uscente e grado entrante uguali;
        (c) esiste una partizione dell'insieme degli archi di G in circuiti (orientati).
      Bibliografia:   [L-L] Chapter 8, sections 4 and 5; Chapter 9, sections 3 and 5 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitoli 2 e 6

TRENTASETTESIMA LEZIONE - 12 Gennaio 2018:
    Vertici isolati in un multigrafo. Sorgenti e pozzi in un multidigrafo.
    Teorema ("Lemma delle Strette di Mano"):
        (1) In ogni multigrafo finito, la somma dei gradi di tutti i vertici è uguale al doppio del numero degli spigoli del multigrafo.
        (2) In ogni multidigrafo finito, la somma dei gradi entranti di tutti i vertici e la somma dei gradi uscenti di tutti i vertici sono uguali al numero degli archi del multidigrafo.
    La matrice di adiacenza (di un multidigrafo o di un multigrafo): definizione, esempi. Ricostruzione di un multidigrafo, o di un multigrafo, dalla sua matrice di adiacenza.
    Proprietà di un multidigrafo o di un multigrafo che possono esser lette dalla sua matrice di adiacenza.
    Cammini, percorsi, cicli (o "circuiti"), connessione in multigrafi e in multidigrafi. Componenti connesse in un multigrafo; multigrafi connessi, multidigrafi connessi.
      Bibliografia:   [L-L] Chapter 8, sections 4 and 11; Chapter 9, sections 3 and 5 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitoli 1 e 2

TRENTASEIESIMA LEZIONE (prof.ssa Damiani) - 10 Gennaio 2018:
    Esercizi sui polinomi booleani: calcolo di forme normali disgiuntive, forme minimiali, implicanti primi, ecc. ecc.
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 9 and 11

TRENTACINQUESIMA LEZIONE - 8 Gennaio 2018:
    Grafi, digrafi, multigrafi, multidigrafi: definizione, descrizione. Il multigrafo soggiacente ad un multidigrafo. Esempi.
    Sottomultigrafi, sottomultidigrafi: definizione, descrizione, esempi.
    Grado entrante, grado uscente, grado (totale) di un vertice in un multidigrafo. Grado di un vertice in un multigrafo.
    Proprietà: Il grado (totale) di un vertice in un multidigrafo e il grado dello stesso vertice nel multigrafo soggiacente sono uguali.
    Proprietà: un grafo completo con n vertici è regolare di grado n e ha esattamente n(n - 1)/2 spigoli.
    Grafi semplici; grafi (semplici) regolari; grafi (semplici) completi.
    Multidigrafi bipartiti, multigrafi bipartiti; corrispondenza tra grafi bipartiti e corrispondenze.
      Bibliografia:   [L-L] Chapter 8, sections 1, 2, 3 and 7; Chapter 9, sections 1, 2, 3 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 1

TRENTAQUATTRESIMA LEZIONE (prof.ssa Damiani) - 22 Dicembre 2017:
    L'insieme delle parti (di un insieme dato) come reticolo.
    Morfismi e isomorfismi di reticoli: esempi e controesempi varî.
    L'ordine prodotto e l'ordine lessicografico: nel prodotto cartesiano di due insiemi ordinati: generalità ed esempi specifici.
    Calcolo di elementi speciali in (sotto)insiemi ordinati: atomi, elementi v-irriducibili, sup e inf di elementi assegnati.
    Calcolo di v-fattorizzazioni di un elemento in un reticolo; esempi di non unicità.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1.3(B) - [G-P] files Reticoli e Relazioni - 2 - [L-L] Chapter 14
      Videolezione:   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)

TRENTATREESIMA LEZIONE - 20 Dicembre 2017:
    Proposizione: F_n(2) = P_n(2) , cioè tutte le funzioni booleani (in n variabili) sull'algebra di Boole 2 = {0,1} sono funzioni polinomiali.
    Il consenso di due prodotti in P_n. Il Metodo del Consenso: algoritmo di calcolo della somma di tutti gli implicanti primi di un polinomio booleano.
    Teorema: Dopo un numero finito di passi l'algoritmo del Metodo del Consenso si arresta, e fornisce come risultato finale la somma di tutti gli implicanti primi del polinomio booleano di partenza (senza dimostrazione).
    Strategia di calcolo di una forma minimale di un polinomio booleano.
    Esempi di calcolo della forma normale disgiuntiva e di una forma minimale per un polinomio booleano.
      Bibliografia:   [G-P] file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9

TRENTADUESIMA LEZIONE - 18 Dicembre 2017:
    Tavola di verità di un polinomio booleano (cenni).
    Misura di complessità di una somma di prodotti; relazione di "maggior semplicità" tra somme di prodotti (in P_n). Definizione di forma minimale (=f.m.) di un polinomio booleano; esistenza (e non unicità, in generale) di forme minimali.
    La relazione di "implicazione" tra polinomi booleani. Collegamento tra la relazione di implicazione e quella di equivalenza per polinomi booleani.
    Gli implicanti primi di un polinomio booleano.
    Lemma: In una somma di polinomi booleani, ogni addendo implica la somma stessa.
    Proposizione: Ogni somma di prodotti è equivalente alla somma di tutti i suoi implicanti primi (senza dimostrazione).
    Teorema: Ogni forma minimale di un polinomio booleano f è somma di implicanti primi di f in cui non si può scartare nessun addendo.
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 9 and 11

TRENTUNESIMA LEZIONE - 15 Dicembre 2017:
    Prodotti, prodotti fondamentali, prodotti completi (in P_n). Somme di prodotti (=:s.d.p.), s.d.p. ridondanti, s.d.p. non ridondanti.
    Teorema: Ogni polinomio P è equivalente a una s.d.p. fondamentali completi non ridondante, detta Forma Normale Disgiuntiva (=F.N.D.) di P, che è unica a meno dell'ordine dei prodotti (nella somma) e dell'ordine dei fattori (in ciascun prodotto).
    Dualizzazione: la forma normale congiuntiva di un polinomio booleano (cenni).
    Calcolo della F. N. D. di un polinomio booleano tramite manipolazioni successive o tramite "tavole di verità".
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3 - [L-L] Chapter 15, sections 7 and 8

TRENTESIMA LEZIONE - 13 Dicembre 2017:
    Corollario: Ogni algebra di Boole finita è isomorfa all'insieme delle funzioni caratteristiche dell'insieme dei suoi atomi.
    Esempi, controesempi e conseguenze del Teorema di Rappresentazione di Stone (nel caso finito).
    L'algebra di Boole delle parti finite o cofinite di N.
    Sottoalgebre di Boole; esempi e controesempi. L'algebra di Boole delle parti finite o cofinite di N è una sottoalgebra di Boole di P(N).
    Teorema di Rappresentazione di Stone (caso generale): Ogni algebra di Boole è isomorfa ad una sottoalgebra di Boole dell'insieme delle parti di un opportuno insieme (senza dimostrazione).
    L'insieme F_n(B) delle funzioni booleane in n variabili su un'algebra di Boole B; struttura di algebra di Boole. L'insieme P_n dei polinomi booleani in n variabili; funzioni booleane indotte da un polinomio booleano. L'insieme P_n(B) delle funzioni polinomiali su B in n variabili.
    Proposizione: P_n(B) è sottoalgebra di Boole di F_n(B).
    Equivalenza tra polinomi booleani (quando inducono la stessa funzione booleana su 2).
    Teorema: Due polinomi booleani inducono la stessa funzione booleana su qualsiasi algebra di Boole se e soltanto se sono equivalenti.
      Bibliografia:   [G-P] file Algebre di Boole; file Funzioni booleane, paragrafi 1 e 2 - [L-L] Chapter 15, sections 2, 6, 7 and 8
      Videolezione:   Algebre di Boole 2   (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])

VENTINOVESIMA LEZIONE (prof.ssa Damiani) - 11 Dicembre 2017:
    Insiemi ordinati, sottoinsiemi ordinati (in un insieme ordinato).
    Prodotto cartesiano di due insiemi ordinati: l'ordine prodotto e l'ordine lessicografico.
    Elementi speciali in (sotto)insiemi ordinati; minimo, massimo, estremo inferiore, estremo superiore di un (sotto)insieme ordinato.
    Reticoli: esempi e controesempi varî. L'isomorfismo di reticoli tra P(X) e 2^X.
    Sottoreticoli in un reticolo: esempi e controesempi varî.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1.3(B) - [G-P] file Relazioni - 2 - [L-L] Chapter 14, sections 1, 2, 3, 5 and 8
      Videolezione:   Insiemi ordinati   (generalità, esempi, elementi speciali)   -   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)   -   Reticoli 3   (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi)

VENTOTTESIMA LEZIONE - 6 Dicembre 2017:
    Equivalenza delle due definizioni di algebra di Boole (idea della dimostrazione).
    Il Principio di Dualità per algebre di Boole.
    Esempi di algebre di Boole:
      (1) le funzioni a valori in un'algebra di Boole (risp. in un reticolo) formano un'algebra di Boole (risp. un reticolo);  
      (2) l'algebra di Boole 2 = {0,1} ;
      (3) l'insieme 2^X delle funzioni caratteristiche su un insieme X   un'algebra di Boole.
    Controsempi: gli insiemi totalmente ordinati con più di due elementi non sono algebre di Boole.
    Anelli booleani: definizione, esempi, controesempi.
    Teorema di Equivalenza (Stone): Le nozioni di algebra di Boole e di anello booleano unitario sono equivalenti (senza dimostrazione, soltanto la definizione delle corrispondenze).
    Isomorfismi tra algebre di Boole, algebre di Boole isomorfe; proprietà degli isomorfismi; la relazione "è isomorfa a" tra algebre di Boole è un'equivalenza.
        • Lemma: Una biiezione tra algebre di Boole è un isomorfismo di algebre di Boole se e soltanto è un isomorfismo di reticoli (senza dimostrazione).
        • Esempio/Esercizio: la biiezione canonica da   P(X)   a   2^X = {0,1}^X   è un isomorfismo di algebre di Boole.
    Teorema di Rappresentazione di Stone (caso finito): Ogni algebra di Boole finita è isomorfa all'insieme delle parti dell'insieme dei suoi atomi.
      Bibliografia:   [G-P] file Algebre di Boole - [L-L] Chapter 15, sections 1 to 6
      Videolezioni:   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])

VENTISETTESIMA LEZIONE - 4 Dicembre 2017:
    Proposizione: In un reticolo finito unicamente complementato, ogni elemento v-irriducibile diverso dal minimo è un atomo.
    Teorema di v-Fattorizzazione Unica (in atomi) per reticoli finiti distributivi complementati.
    Isomorfismi tra reticoli, reticoli isomorfi; proprietà degli isomorfismi e della relazione di "essere isomorfi".
    NOTA: un reticolo L è isomorfo a un reticolo L' se e soltanto se il diagramma di Hasse di L ha la stessa forma di quello di L'.
    Esempio: D_r è isomorfo a D_s se e soltanto se gli esponenti dei primi che compaiono nella fattorizzazione di r in potenze di primi distinti sono gli stessi (salvo che per l'ordine) che nell'analoga fattorizzazione di s.
    Sottoreticoli di un reticolo; esempi e controesempi di sottoreticoli.
    Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N₅ o a M₅ (senza dimostrazione, soltanto l'idea).
    Algebre di Boole, definite come: (1) reticoli distributivi (limitati) complementati; (2) insiemi con due operazioni, una endofunzione e due elementi speciali.
    Esempi di algebre di Boole: l'insieme delle parti P(X); i reticoli D_n per ogni n nella cui fattorizzazione in primi tutti gli esponenti siano al più 1.
    Controsempi di algebre di Boole: i reticoli D_n per ogni n nella cui fattorizzazione in primi compaia almeno un esponente maggiore di 1 non sono algebre di Boole.
      Bibliografia:   [G-P] file Reticoli, paragrafi 6 e 7; file Algebre di Boole - [L-L] Chapter 15, sections 1 to 5
      Videolezioni:   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])

VENTISEIESIMA LEZIONE - 1 Dicembre 2017:
    Reticoli distributivi: definizione, esempi, controesempi - i reticoli N₅ e M₅ sono non distributivi.
    Proposizione: In un reticolo distributivo, il complemento - se esiste - è unico, e valgono le Leggi di De Morgan per il complemento di inf(x,y) e di sup(x,y).
    Elementi v-riducibili o v-irriducibili; atomi.
    Caratterizzazione degli elementi v-irriducibili in un reticolo finito: sono quelli che coprono al più un elemento (senza dimostrazione).
    Proposizione: Ogni atomo è v-irriducibile (senza dimostrazione).
    Teorema: In un reticolo finito, ogni elemento ha una v-fattorizzazione non ridondante in fattori v-irriducibili.
    La v-fattorizzazione non ridondante in fattori v-irriducibili nei reticoli P(X) e D_n.
    Proposizione: In un reticolo distributivo, un'eventuale v-fattorizzazione non ridondante in fattori v-irriducibili è unica (a meno dell'ordine dei fattori).
    Teorema di v-Fattorizzazione Unica (in v-irriducibili) per reticoli finiti distributivi.
      Bibliografia:   [G-P] file Reticoli, paragrafi da 3 a 5 - [L-L] Chapter 14, sections 10 and 11
      Videolezione:   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)   -   Reticoli 2   (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)

VENTICINQUESIMA LEZIONE (prof.ssa Damiani) - 29 Novembre 2017:
    Sistemi di equazioni congruenziali in forma generale.
    Calcolo di potenze in anelli del tipo Z_n .
    Criteri di divisibilità.
      Bibliografia:   [Cam] Capitolo II, paragrafi 5 e 6 - [G-P] files Aritmetica sugli interi, congruenze, Teorema Cinese del Resto, Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, section 9 - [PC] Capitolo 2, paragrafi 6, 7 e 8

VENTIQUATTRESIMA LEZIONE - 27 Novembre 2017:
    Reticoli: definizione come insiemi ordinati e definizione come insiemi con due operazioni binarie.
    Equivalenza delle due definizioni di reticolo (idea della dimostrazione).
    Principio di Dualità per reticoli. Esempi e controesempi di reticoli.
    Proposizione: Ogni reticolo finito è limitato.
    Complementi in un reticolo limitato; reticoli complementati. Esempi e controesempi; il caso dei reticoli N₅ e M₅, il caso dei reticoli D_n.
      Bibliografia:   [G-P] file Reticoli, paragrafi da 1 a 3 - [L-L] Chapter 14, sections 8, 9 and 11
      Videolezione:   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)

VENTITREESIMA LEZIONE - 24 Novembre 2017:
    Relazioni d'ordine: ordin(ament)i totali, ordin(ament)i buoni. Esercizio ogni ordinamento buono è anche totale.
    Sottoinsiemi ordinati (in un insieme ordinato); intervalli in un insieme ordinato.
    Relazione di copertura e diagramma di Hasse di un insieme ordinato.
    Principio di Dualità per insiemi ordinati.
    Elementi minimali (risp. massimali), minimo min(E') - risp. massimo max(E') - per un sottoinsieme E' in un insieme ordinato E; unicità di min(E') - risp. di max(E') - se esiste.
    Minoranti - risp. maggioranti - estremo inferiore inf(E') - risp. estremo superiore sup(E') - per un sottoinsieme E' in un insieme ordinato E; unicità di inf(E') - risp. di sup(E') - se esiste. Sottoinsiemi limitati (superiormente/inferiormente) in un insieme ordinato.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1.3(B) - [G-P] file Relazioni - 2 - [L-L] Chapter 14, sections 1, 2, 3, 5 and 7
      Videolezione:   Insiemi ordinati   (generalità, esempi, elementi speciali)

VENTIDUESIMA LEZIONE (prof.ssa Damiani) - 22 Novembre 2017:
    Sistemi di equazioni congruenziali: discussione, sistemi equivalenti. Sistemi in forma cinese. Risoluzione di un sistema - tramite il Teorema Cinese del Resto (senza dimostrazione), se possibile, o tramite sostituzioni successive.
    Esempi espliciti di discussione e risoluzione di sistemi di equazioni congruenziali (tramite l'uno o l'altro metodo).
      Bibliografia:   [Cam] Capitolo II, paragrafo 5 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 9 - [PC] Capitolo 2, paragrafo 7

VENTUNESIMA LEZIONE - 20 Novembre 2017:
    Criterio di esistenza di soluzioni per equazioni modulari, metodo di calcolo di una soluzione, descrizione dell'insieme (completo) di tutte soluzioni.
    Elementi invertibili in Z_n; criterio di invertibilità, calcolo dell'inverso mediante risoluzione di una equazione congruenziale.
    Il gruppo moltiplicativo U(Z_n) degli elementi invertibili di Z_n; descrizione esplicita.   -   Caso speciale: Z_n è un campo <=> n è irriducibile (=primo).
    La funzione φ di Eulero: definizione, formula esplicita. U(Z_n) ha esattamente φ(n) elementi.
    Ripetitività delle potenze in Z_n: generalità.
    Il Piccolo Teorema di Fermat, il Teorema di Eulero (senza dimostrazione).
    Algoritmo di riduzione di un esponente: caso generale, caso speciale (quando la base invertibile - col Teorema di Eulero).
    Esempi espliciti sul calcolo di potenze in Z_n.
      Bibliografia:   [Cam] Capitolo II, paragrafi 5 e 6 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 8 and 9 - [PC] Capitolo 2, paragrafi 6, 7 e 8

VENTESIMA LEZIONE - 17 Novembre 2017:
    Criteri di divisibilità in Z: strategia generale - calcolo di una classe in Z_n - ed esempi specifici.
    Equazioni congruenziali in Z, equazioni modulari in Z_n: definizione, connessione tra equazioni congruenziali, equazioni modulari ed equazioni diofantee (in ZxZ).
    Criterio di esistenza di soluzioni per equazioni congruenziali, metodo di calcolo di una soluzione, descrizione dell'insieme (completo) di tutte soluzioni.
    Equazioni diofantee equivalenti, equazioni congruenziali equivalenti. Semplificazioni di equazioni diofantee o congruenziali.
      Bibliografia:   [Cam] Capitolo II, paragrafi 4 e 5 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 8 and 9 - [PC] Capitolo 2, paragrafi 6 e 7

DICIANNOVESIMA LEZIONE (prof.ssa Damiani) - 15 Novembre 2017:
    M.C.D. e m.c.m. tra interi; identità di Bézout per il M.C.D..
    Operazioni tra interi modulari (cioè in Z_n).
      Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4; file Congruenze, aritmetica modulare(D'Andrea), paragrafi 1 e 2 - [Cam] Capitolo II, paragrafi 3 e 4 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 8 - [PC] Capitolo 2, paragrafi 3 e 6

DICIOTTESIMA LEZIONE - 13 Novembre 2017:
    L'espressione unica di un intero non nullo come prodotto di un invertibile (un segno) e di potenze di irriducibili prefissati.
    Divisibilità tra un intero e un altro in termini delle loro fattorizzazioni in irriducibili (come sopra).
    Esistenza e forma esplicita di MCD(a,b) e di mcm(a,b) in termini di fattorizzazioni di a e di b ; la relazione MCD(a,b) mcm(a,b) = a b ; calcolo di mcm(a,b) tramite il calcolo di MCD(a,b) .
    Equazioni diofantee: definizione, criterio di esistenza di soluzioni, algoritmo per il calcolo esplicito di una soluzione. Esempi espliciti.
    Congruenze modulo n in Z (richiami). Ogni congruenza è una equivalenza: se n=0 è l'identità, se n=1 è la relazione totale. Le congruenze modulo +n e modulo -n coincidono.
    Descrizione delle classi di congruenza modulo n e dell'insieme quoziente Z_n .
    Compatibilità di somma e prodotto con ogni congruenza modulo n (esercizio). Definizione di somma e prodotto in Z_n .
    Teorema (senza dimostrazione):   (a) Z_n è un anello commutativo unitario.
      (b) Per ogni n>1, le seguenti condizioni sono equivalenti:   (b.1) Z_n è un dominio;   (b.2) Z_n è un campo;   (b.3) n è primo;   (b.4) n è irriducibile.
      Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4; file Congruenze, aritmetica modulare(D'Andrea), paragrafi 1 e 2 - [Cam] Capitolo II, paragrafi 3 e 4 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 8 - [PC] Capitolo 2, paragrafi 3 e 6

DICIASSETTESIMA LEZIONE - 10 Novembre 2017:
    Teorema di Euclide: Esistono infiniti numeri interi irriducibili.
    Divisione con resto tra numeri interi: esistenza e unicità di quoziente e resto (positivo).
    Massimo comun divisore (=M.C.D.) e minimo comun multiplo (=m.c.m.) di due numeri interi. Numeri interi coprimi (o "primi tra loro").
    Esistenza del MCD in Z, e identità di Bézout per esso: procedura di calcolo con l'algoritmo euclideo delle divisioni successive.
    Proposizione: Tra i numeri interi, ogni irriducibile è primo.
    Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi non nulli e non invertibili (dimostrazione dell'unicità).
      Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Cam] Capitolo II, paragrafi 1, 2 e 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 4, 5, 6, 7 - [PC] Capitolo 2, paragrafi 2 e 3

SEDICESIMA LEZIONE - 8 Novembre 2017:
    Costruzione dei numeri interi a partire dai numeri naturali, come "naturali + i negativi": elementi, operazioni, ordine, valore assoluto (cenni).
    Anelli, domini, campi: definizione, esempi e controesempi.
    L'insieme dei numeri interi, con le operazioni di somma e prodotto, è un anello commutativo unitario, che è un dominio ma non un campo.
    Il problema generale della fattorizzazione: esempi e controesempi varî.
    Divisibilità tra interi. Elementi invertibili, elementi associati. Elementi riducibili, elementi irriducibili, elementi primi.
    Lemma: Ogni primo è irriducibile.
    Fattorizzazioni banali, fattorizzazioni "ottimali" (=in fattori irriducibili); fattorizzazioni equivalenti.
    Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi non nulli e non invertibili (dimostrazione dell'esistenza).
      Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Cam] Capitolo I, paragrafo 4; Capitolo II, paragrafi 2 e 3 - [G-P] files Gruppi, anelli, campi, Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Appendix B, Chapter 11, sections 1, 2, 3, 5, 7 - [PC] Capitolo 2, paragrafi 1 e 3; Capitolo 4, paragrafo 1
      Videolezioni:   Operazioni 1 (operazioni in un insieme; insiemi con una operazione)   -   Operazioni 2 (insiemi con più operazioni)

QUINDICESIMA LEZIONE (prof.ssa Damiani) - 6 Novembre 2017:
    La funzione (ricorsiva) fattoriale f(n) = n!
    Elementi di calcolo combinatorio:
      - calcolo del numero di funzioni da un insieme finito ad un altro ("disposizioni" - o "prelievi", o "campionamenti" - con ripetizioni);
      - calcolo del numero di funzioni iniettive da un insieme finito ad un altro ("disposizioni" - o "prelievi", o "campionamenti" - senza ripetizioni);
      - calcolo del numero di biiezioni tra due insieme finiti con n elementi (è n!); il numero di permutazioni di un insieme con n elementi è n! ;
      - calcolo del numero dei sottoinsiemi con k elementi in un insieme con n elementi ("combinazioni di k elementi scelti tra n"): coefficienti binomiali;
      - proprietà notevoli dei coefficienti binomiali: casi speciali, il triangolo di Pascal-Tartaglia;
    Applicazioni: la formula di Newton per lo sviluppo delle potenze di un binomio in termini di coefficienti binomiali.
      Bibliografia:   [Cam] Capitolo I, paragrafo 2 - [L-L] Chapter 5, sections 1 to 5; Chapter 6, sections 1 to 3 - [PC] Capitolo 1, paragrafo 6

QUATTORDICESIMA LEZIONE - 3 Novembre 2017:
    Proposizione: L'insieme NxN è numerabile.
    1^o Teorema di Cantor: L'unione di una famiglia finita (non vuota) o numerabile di insiemi finiti o numerabili, di cui almeno uno sia numerabile, è a sua volta numerabile.  
    Corollario: Gli insiemi Z e Q sono numerabili.
    2^o Teorema di Cantor: La cardinalità dell'insieme delle parti P(X) e la cardinalità dell'insieme delle funzioni caratteristiche 2^X di un insieme X è strettamente maggiore della cardinalità di X.
    I numeri cardinali infiniti superiori "Aleph_n" (per ogni n in N). La cardinalità del continuo: |R| = |P(N)| .
    L'ipotesi del continuo generalizzata. Distribuzione (rispetto alla relazione d'ordine) dei numeri cardinali.
      Bibliografia:   [AaVv] file Cardinalità (D'Andrea) - [Cam] Capitolo I, paragrafo 6 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7 - [PC] Capitolo 1, paragrafo 5
      Videolezioni:   Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)   -   Cardinalità 2   (Secondo Teorema di Cantor)

TREDICESIMA LEZIONE - 30 Ottobre 2017:
    Equipotenza tra insiemi; l'equipotenza è riflessiva, simmetrica, transitiva. Cardinalità di un insieme, numeri cardinali. Insiemi finiti, insiemi infiniti; insiemi (infiniti) numerabili.
    Relazione d'ordine tra numeri cardinali. Teorema di Schroeder-Bernstein (senza dimostrazione della antisimmetria).
    Proprietà degli insiemi numerabili: (a) Ogni insieme infinito contiene un sottoinsieme numerabile; (b) in un insieme numerabile, ogni sottoinsieme o è finito oppure è numerabile.
    Corollario: La cardinalità del numerabile è maggiore di ogni cardinale finito, ed è minore o uguale ad ogni cardinale infinito.
    Caratterizzazione degli insiemi infiniti: Per ogni insieme X le seguenti proprietà sono equivalenti:
      - X è infinito,
      - esiste una funzione iniettiva dall'insieme dei numeri naturali ad X,
      - esiste un sottoinsieme proprio di X che è equipotente ad X stesso.
      Bibliografia:   [AaVv] file Cardinalità (D'Andrea) - [Cam] Capitolo I, paragrafo 6 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7 - [PC] Capitolo 1, paragrafo 5
      Videolezione:   Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)

DODICESIMA LEZIONE - 27 Ottobre 2017:
    Divisione con resto tra numeri naturali; dimostrazione per induzione in tre modi diversi: col Pr.I.D., col Pr.I.F. e col Pr.M.
    Numerazione in base arbitraria: esistenza e unicità della scrittura posizionale (di un numero naturale) in base b (>1) arbitraria.
    La procedura operativa per il calcolo della scrittura posizionale di un numero naturale in una base data.
    I numeri descrivibili con al più T cifre nella scrittura posizionale in base b sono tutti quelli da 0 fino a   b^T - 1 .
    Gli algoritmi di calcolo in notazione posizionale per la somma e il prodotto in base arbitraria (cenni).
    Esempi espliciti di scrittura posizionale in base arbitraria.
      Bibliografia:   [Cam] Capitolo II, paragrafi 1 e 2 - [G-P] file Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [L-L] Chapter 11, section 4 - [PC] Capitolo 1, paragrafo 4; Capitolo 2, paragrafo 10
      Videolezioni:   Induzione (metodo di dimostrazione per induzione [debole / forte / minimo])   -   Divisione (divisione con resto tra numeri naturali)   -   Numerazione (numerazione in base arbitraria / scrittura posizionale)

UNDICESIMA LEZIONE - 25 Ottobre 2017:
    Definizione delle operazioni di somma e prodotto tra numeri naturali. Proprietà notevoli di somma, prodotto e relazione d'ordine in un S.N.N. (senza dimostrazione).
    Formulazioni alternative del Principio di Induzione: il Principio di Induzione Debole (=Pr.I.D.), il Principio di Induzione Forte (=Pr.I.F.), il Principio del Minimo (=Pr.M.). L'equivalenza tra Pr.I.D., Pr.I.F. e Pr. M. (senza dimostrazione).
    Dimostrazioni per induzione, dei vari tipi (debole, forte - base dell'induzione, passo induttivo - o con principio del minimo): idea, strategia operativa (base, passo induttivo).
    Esempi di dimostrazioni per induzione.
      Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Cam] Capitolo I, paragrafo 5 - [G-P] file Induzione - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 1, paragrafo 4
      Videolezioni:   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)   -   Induzione (metodo di dimostrazione per induzione [debole / forte / minimo])

DECIMA LEZIONE (prof.ssa Damiani) - 23 Ottobre 2017:
    Esercizi, esempi e controesempi su relazioni di equivalenza, classi di equivalenza, partizioni, relazioni di preordine, ecc.

NONA LEZIONE - 20 Ottobre 2017:
    Proposizione: La famiglia delle classi di equivalenza in un insieme X è una partizione di X.
    La relazione in X associata ad una partizione di X.
    Proposizione: La relazione in un insieme X associata ad una partizione di X è un'equivalenza.
    In un insieme X, le costruzioni della partizione in classi (per una equivalenza data) e della equivalenza associata (ad una partizione data) sono inverse l'una dell'altra.
    Sistema dei Numeri Naturali (=S.N.N.): definizione tramite assiomi di Peano.
    Il problema della esistenza e unicità di un S.N.N. (cenni). Controesempi di S.N.N.
    Definizione di una relazione d'ordine in un S.N.N.
      Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Cam] Capitolo I, paragrafi 3 e 5 - [PC] Capitolo 1, paragrafi 2 e 4
      Videolezioni:   Equivalenze 1 (equivalenze e partizioni)   -   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)

OTTAVA LEZIONE (prof.ssa Damiani) - 18 Ottobre 2017:
    Esercizi, esempi e controesempi su funzioni, relazioni, relazioni d'equivalenza - in particolare, la congruenza modulo n nell'insieme Z dei numeri interi - relazioni d'ordine, ecc.

SETTIMA LEZIONE - 16 Ottobre 2017:
    Partizioni di un insieme: definizione, esempi, controesempi.
    Classi di equivalenza; rappresentante di una classe di equivalenza. Insieme quoziente e proiezione canonica per una equivalenza.
    Per l'equivalenza in X associata ad una funzione f con dominio X, la classe di equivalenza di un elemento è la controimmagine della sua immagine per la funzione f.
    Collegamento tra il rapporto tra due elementi e il rapporto tra le corrispondenti classi di equivalenza.
    Ogni rappresentante di una classe di equivalenza determina univocamente la classe stessa.
      Bibliografia:   [Cam] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
      Videolezioni:   Equivalenze 1 (equivalenze e partizioni)   -   Equivalenze 2 (equivalenze e funzioni)

SESTA LEZIONE (prof.ssa Damiani) - 13 Ottobre 2017:
    Esercizi, esempi e controesempi su insiemi, sottoinsiemi, corrispondenze, funzioni, ecc.

QUINTA LEZIONE - 11 Ottobre 2017:
    Famiglie (di oggetti in un insieme), definite come funzioni.
    Relazioni (binarie) in un insieme; descrizione grafica di una relazione come "grafo orientato".
    Proprietà notevoli per una relazione: riflessività, transitività, simmetricità, antisimmetricità. Esempi e controesempi.
    Relazioni di preordine; relazioni d'ordine, relazioni di equivalenza: definizione, esempi.
    La relazione in X associata ad una funzione f da X a Y è una equivalenza. Generalizzazione: la relazione in X controimmagine, per una funzione f da X a Y, di una relazione in Y, è riflessiva, risp. simmetrica, risp. transitiva, se tale è la relazione iniziale in Y (cenni).
      Bibliografia:   [Cam] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
      Videolezioni:   Relazioni (relazioni in un insieme: generalità, esempi)   -   Equivalenze 1 (equivalenze e partizioni)

QUARTA LEZIONE - 9 Ottobre 2017:
    Legame tra funzioni e corrispondenze: la "funzione canonica" associata ad una corrispondenza.
    Esercizio: (a) la composizione di funzioni iniettive, risp. suriettive, è iniettiva, risp. suriettiva;
            (b) se la composizione di due funzioni è iniettiva, risp. suriettiva, allora la prima funzione è iniettiva, risp. la seconda funzione è suriettiva.
    Funzioni invertibili: definizione; caratterizzazione in termini intrinseci (biiettività) e in termini della corrispondenza inversa (dev'essere a sua volta una funzione).
    Funzioni caratteristiche in un insieme. Biiezione naturale tra l'insieme delle parti di un insieme A e l'insieme delle funzioni caratteristiche in A.
      Bibliografia:   [Cam] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3 - [PC] Capitolo 1, paragrafo 3
      Videolezioni:   Funzioni 2 (composizione di funzioni, funzioni invertibili)   -   Funzioni caratteristiche (funzioni caratteristiche in un insieme)

TERZA LEZIONE - 6 Ottobre 2017:
    Composizione - o "prodotto (operatorio)" - di due corrispondenze. Proprietà notevoli di inversione e composizione: associatività, le identità sono "elementi neutri", ecc. Potenze di una corrispondenza.
    Funzioni (o "applicazioni"): definizione, esempi, controesempi; immagini e controimmagini. Restrizione di una funzione ad un sottoinsieme del dominio.
    La composizione di due funzioni è (a sua volta) una funzione.
    Funzioni iniettive; funzioni suriettive; funzioni biiettive. Esempi e controesempi.
    Caratterizzazione della biiettività: una funzione è biiettiva se e soltanto se la sua corrispondenza inversa è (a sua volta) una funzione.
      Bibliografia:   [Cam] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapters 2, 3 - [PC] Capitolo 1, paragrafo 3
      Videolezioni:   Corrispondenze (corrispondenze tra insiemi e operazioni tra di esse)   -   Funzioni 1 (funzioni; iniettività, suriettività, biiettività)   -   Funzioni 2 (composizione di funzioni, funzioni invertibili)

SECONDA LEZIONE - 4 Ottobre 2017:
    Prodotto cartesiano tra due o più insiemi.
    Proprietà notevoli delle operazioni tra insiemi:
      - (1) associatività e commutatività di intersezione, unione e differenza simmetrica;
      - (2) elementi speciali;
      - (3) distributività, leggi di De Morgan.
    Corrispondenze tra insiemi: definizione, esempi. Immagine di un sottoinsieme del dominio, controimmagine di un sottoinsieme del codominio (per una corrispondenza data).
    Corrispondenza vuota, corrispondenza totale; corrispondenza identica.
    Corrispondenza complementare (o "opposta") e corrispondenza inversa di una corrispondenza data.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
      Videolezione:   Corrispondenze (corrispondenze tra insiemi e operazioni tra di esse)

  PRIMA LEZIONE - 2 Ottobre 2017:
    Considerazioni generali sul corso, modalità d'esame, ecc.
    Insiemi: definizione (naturale, o "ingenua"), descrizioni possibili; appartenenza e non appartenenza di elementi.
    Sottoinsiemi, sovrainsiemi. Inclusione tra insiemi; inclusione stretta. L'uguaglianza tra insiemi come doppia inclusione. L'insieme vuoto. L'insieme delle parti di un insieme.
    Operazioni tra insiemi: intersezione, unione, differenza, complementare, differenza simmetrica.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1 - [G-P] file Insiemi - [L-L] Chapter 1 - [PC] Capitolo 1, paragrafo 1
      Videolezione:   Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)