Corso di Laurea in Informatica
a.a 2015-2016 - primo semestre

Diario delle lezioni del corso - da 9 CFU - di

MATEMATICA DISCRETA

(elencate in ordine cronologico inverso)

Docente:   Fabio Gavarini

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  


                * * *                 * * *                 * * *                

QUARANTESIMA LEZIONE (soltanto ripasso e/o esercitazioni) - 22 Gennaio 2016:
    Simulazione di prova orale d'esame.
  FINE del CORSO  

TRENTANOVESIMA LEZIONE (soltanto ripasso e/o esercitazioni) - 20 Gennaio 2016:
    Ripasso ragionato dei seguenti argomenti:
      -   numeri interi: operazioni, ordine, valore assoluto, divisione con resto;
      -   numeri interi: elementi speciali, fattorizzazione, divisibilità, M.C.D. e m.c.m., algoritmo euclideo delle divisioni successive per il calcolo di M.C.D.(a,b);
      -   Teorema Fondamentale dell'Aritmetica: esistenza e unicità della fattorizzazione degli interi non nulli.
      -   congruenze tra interi, l'anello Z_n (interi modulo n);
      -   equazioni modulari, equazioni congruenziali, equazioni diofantee;
      -   elementi invertibili in Z_n, potenze in Z_n (generalità e Teorema di Eulero);
      -   sistemi di equazioni congruenziali.
    Esercizi sui sistemi di equazioni congruenziali.

TRENTOTTESIMA LEZIONE (soltanto ripasso e/o esercitazioni) - 18 Gennaio 2016:
    Ripasso ragionato dei seguenti argomenti:
      -   teoria degli insiemi, corrispondenze, funzioni, relazioni (e costruzioni associate);
      -   costruzione del sistema dei numeri naturali tramite gli Assiomi di Peano, il Principio di Induzione (nelle sue varie formulazioni), notazione in scrittura posizionale in base arbitraria;
      -   cardinalità di insiemi, insiemi infiniti (e loro caratterizzazione), insiemi numerabili, Primo e Secondo Teorema di Cantor.
    Esercizi sulla v-fattorizzazione in un reticolo.

TRENTASETTESIMA LEZIONE - 15 Gennaio 2016:
    Foglie in un multigrafo.
    Proposizione: Ogni foresta finita (in particolare, ogni albero finito) con almeno due vertici ha almeno due foglie.
    Teorema: Ogni albero è grafo bipartito (dimostrazione per induzione [debole o forte] nel caso finito e e dimostrazione tramite il "Lemma delle Strette di Mano" nel caso generale).
    Albero generatore di un multigrafo connesso, e foresta generatrice di un multigrafo (qualsiasi).
    Esistenza di un albero generatore per un multigrafo connesso (e di una foresta generatrice per un multigrafo qualsiasi); algoritmi di Kruskal ("per addizione" o "per sottrazione") per il calcolo di un albero generatore in un multigrafo connesso.
    Esempi di applicazione degli algoritmi di Kruskal.
  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

TRENTASEIESIMA LEZIONE - 13 Gennaio 2016:
    Alberi (non orientati), foreste: definizione ed esempi.
    Teorema (caratterizzazione degli alberi): Per un grafo G le seguenti proprietà sono equivalenti:
        (a) G è un albero;
        (b) G è aciclico, ma se si aggiunge un qualsiasi nuovo spigolo si ottiene un grafo ciclico;
        (c) G è connesso, ma se si toglie un qualsiasi spigolo si ottiene un sottografo sconnesso (in altre parole, ogni spigolo in G è un ponte);
        (c) per ogni scelta di vertici u e v in G esiste uno ed un solo percorso da u a v in G.
    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 |V|=n di vertici, le seguenti proprietà sono equivalenti:
          (a) G è un albero;   (b) G è aciclico e |E|=n-1 (=|V|-1);   (c) G è connesso e |E|=n-1 (=|V|-1).
      Bibliografia:   [L-L] Chapter 8, section 8 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 4

TRENTACINQUESIMA LEZIONE - 11 Gennaio 2016:
    Teorema di caratterizzazione dei multigrafi euleriani.
    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

TRENTAQUATTRESIMA LEZIONE - 8 Gennaio 2013:
    Cammini, precorsi, cicli (o "circuiti"), connessione in multigrafi e in multidigrafi. Componenti connesse in un multigrafo; multigrafi connessi, multidigrafi connessi.
    Proposizione: Ogni multigrafo finito è l'unione delle sue componenti connesse.
    Alberi, foreste. Ogni foresta è unione di alberi (le sue componenti connesse).
    Cammini euleriani; multigrafi e multidigrafi euleriani o semieuleriani. Relazione tra multi(di)grafi euleriani e semieuleriani.
    Teorema di caratterizzazione dei multidigrafi euleriani.
      Bibliografia:   [L-L] Chapter 8, sections 4 and 5 and 7; Chapter 9, section 3 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitoli 1 e 6

TRENTATREESIMA LEZIONE - 21 Dicembre 2015:
    Ogni grafo (semplice) completo con n vertici è regolare di grado n-1 .
    Digrafi "funzionali" (associati a corrispondenze); ogni digrafo funzionale è bipartito (e viceversa).
    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.
    Unione di multidigrafi, unione di multigrafi; la matrice di adiacenza di una unione di multidigrafi o di multigrafi è in forma "a blocchi".
      Bibliografia:   [L-L] Chapter 8, sections 7 and 11; Chapter 9, section 5 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 2

TRENTADUESIMA LEZIONE - 18 Dicembre 2015:
    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. Vertici isolati.
    Proprietà: Il grado (totale) di un vertice in un multidigrafo e il grado dello stesso vertice nel multigrafo soggiacente sono uguali.
    Grafi (semplici) regolari; grafi (semplici) completi.
    Multidigrafi bipartiti, multigrafi bipartiti.
      Bibliografia:   [L-L] Chapter 8, sections 1, 2, 3; Chapter 9, sections 1, 2, 3 - [Qua] Breve Introduzione alla Teoria dei Grafi, Capitolo 1

TRENTUNESIMA LEZIONE - 16 Dicembre 2015:
    Metodo di calcolo esplicito per funzioni ricorsive lineari omogenee a coefficienti costanti nei vari casi:
      - (1) il caso di grado 1;
      - (2) il caso di grado 2, con due radici distinte;
      - (3) il caso di grado 2, con una sola radice doppia (cioè due radici coincidenti).
    Esempi ed esercizi sul calcolo esplicito delle funzioni ricorsive omogenee a coefficienti costanti di grado 1 o di grado 2 (con radici reali).
      Bibliografia:   [G-P] file Equazioni alle differenze finite (cenni) - [L-L] Chapter 3, section 6; Chapter 6, sections 6, 7 and 8
      Videolezioni:   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.: la seconda è lo sviluppo consecutivo (senza transizione) della prima.

TRENTESIMA LEZIONE - 14 Dicembre 2015:
    Funzioni (o "successioni") ricorsive. Dati iniziali, equazione ricorsiva e grado (o "ordine") associati ad una funzione ricorsiva.
    Teorema di Ricorsione: Esistenza e unicità di una successione che soddisfi una data equazione ricorsiva e abbia dati iniziali preassegnati.
    Casi particolari di funzioni ricorsive: lineari, lineari omogenee, lineari a coefficienti costanti.
    Proposizione: L'insieme S delle successioni che sono soluzioni di un'equazione ricorsiva lineare omogenea di ordine k è chiuso per la somma e per il prodotto con uno scalare; inoltre, esistono k successioni a⁽¹⁾, ... , a^(k) in S tali che ogni successione in S si possa scrivere in modo unico come combinazione lineare delle successioni a⁽¹⁾, ... , a^(k) (senza dimostrazione).
    Strategia di calcolo di una funzione ricorsiva lineare omogenea: ricerca di una base dello spazio delle soluzioni dell'equazione ricorsiva associata, e successiva imposizione delle condizioni iniziali.
    Il caso lineare omegeneo a coefficienti costanti di grado 1.
    Bibliografia:   [G-P] file Equazioni alle differenze finite (cenni) - [L-L] Chapter 3, section 6; Chapter 6, sections 6 and 7
      Videolezioni:   Funzioni ricorsive 1 (funzioni ricorsive: generalità, casi particolari, esempi; Teorema di Ricorsione [di esistenza e unicità])   -   Funzioni ricorsive 2 (funzioni ricorsive lineari omogenee come spazio vettoriale; calcolo di una base, e di una successione specifica, per il caso a coefficienti costanti di grado 1)

VENTINOVESIMA LEZIONE - 11 Dicembre 2015:
    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

VENTOTTESIMA LEZIONE - 9 Dicembre 2015:
    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.
    Teorema: Ogni forma minimale di un polinomio booleano f è somma di implicanti primi di f in cui non si può scartare nessun addendo.
    Esempi di calcolo della F.N.D. di un polinomio booleano assegnato.
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9

VENTISETTESIMA LEZIONE - 4 Dicembre 2015:
    Prodotti, prodotti fondamentali, prodotti completi (in P_n); somme di prodotti (ridondanti, non ridondanti, complete); passaggio da un oggetto (prodotto o somma) non "buono" (fondamentale, o irridondante, o completo) ad uno "buono" equivalente.
    Forma Normale Disgiuntiva (=F.N.D.) di un polinomio booleano: esistenza e unicità. Dualizzazione: la forma normale congiuntiva di un polinomio booleano.
    Metodi operativi per il calcolo della F. N. D. di un polinomio booleano: (1) tramite "tavole di verità", (2) tramite manipolazioni successive.
    Corollario (del primo metodo): F_n(2) = P_n(2) , cioè tutte le funzioni booleani (in n variabili) sull'algebra di Boole 2 = {0,1} sono funzioni polinomiali.
      Bibliografia:   [G-P] file Funzioni booleane, paragrafo 3 - [L-L] Chapter 15, sections 7 and 8

VENTISEIESIMA LEZIONE - 2 Dicembre 2015:
    Esempi e controesempi per il Teorema di Stone (nel caso finito).
    Sottoalgebre di Boole; esempi e controesempi.
    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 indotte da un polinomio booleano.
    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])

VENTICINQUESIMA LEZIONE - 30 Novembre 2015:
    Anelli booleani: definizione, esempi, controesempi. Proprietà particolari in un anello booleano: il prodotto è commutativo, ogni elemento è uguale al suo opposto.
    Teorema di Equivalenza (Stone): Le nozioni di algebra di Boole e di anello booleano unitario sono equivalenti (senza dimostrazione, soltanto la definizione delle corrispondenze).
    Esempi di algebre di Boole: le funzioni a valori in un'algebra di Boole; prodotti di algebre di Boole; i prodotti 2ⁿ = {0,1}ⁿ.
    Controsempi: gli insiemi totalmente ordinati con più di due elementi non sono algebre di Boole.
    Morfismi e isomorfismi tra algebre di Boole, algebre di Boole isomorfe; proprietà dei morfismi e degli isomorfismi.   -   Esempio: la biiezione canonica da   P(X)   a   2^X = {0,1}^X   è un isomorfismo di algebre di Boole.
    Lemma: Una biiezione tra algebre di Boole è un isomorfismo di algebre di Boole se e soltanto è un isomorfismo di reticoli (senza dimostrazione).
    Teorema di Rappresentazione di Stone (caso finito): Ogni algebra di Boole finita è isomorfa all'insieme delle parti dell'insieme dei suoi atomi.
    Corollario: Ogni algebra di Boole finita è isomorfa all'insieme delle funzioni caratteristiche 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])

VENTIQUATTRESIMA LEZIONE - 27 Novembre 2015:
    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.
    Sottoreticoli di un reticolo. Morfismi e isomorfismi tra reticoli, reticoli isomorfi; proprietà dei morfismi e degli isomorfismi.
    Esempio 1: D_n è isomorfo al prodotto degli intervalli [0,e₁] , ... , [0,e_k] (con l'ordinamento prodotto) dove e₁ , ... , e₁ sono gli esponenti che compaiono in una fattorizzazione di n in in primi distinti.
    Esempio 2: D_r è isomorfo a D_s se e soltanto se r ed s hanno fattorizzazioni in primi distinti che coinvolgono gli stessi esponenti.
    Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N₅ o a M₅ (senza dimostrazione).
    Algebre di Boole, definite come: (1) reticoli distributivi (limitati) complementati; (2) insiemi con due operazioni, una endofunzione e due elementi speciali. Equivalenza delle due definizioni (idea della dimostrazione).
    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: i reticoli D_n per ogni n nella cui fattorizzazione in primi compaia almeno un esponente maggiore di 1 non sono algebre di Boole.
    Il Principio di Dualità per 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])

VENTITREESIMA LEZIONE - 25 Novembre 2015:
    Reticoli distributivi: definizione, esempi, controesempi, i casi N₅ e M₅.
    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.
    Proposizione: Ogni atomo è v-irriducibile.
    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.
    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)

VENTIDUESIMA LEZIONE - 23 Novembre 2015:
    Equivalenza delle due definizioni di reticolo (idea della dimostrazione).
    Costruzione di relazioni d'ordine: ordine tra funzioni, ordine prodotto, ordine lessicografico.
    Esempi e controesempi di reticoli.
    Insiemi ordinati limitati.   -   Proposizione: Ogni reticolo finito è limitato.
    Complementi in un reticolo limitato; reticoli complementati. Esempi e controesempi.
      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à)

VENTUNESIMA LEZIONE - 20 Novembre 2015:
    Relazioni d'ordine: ordin(ament)i totali, ordin(ament)i buoni. Relazione di copertura e diagramma di Hasse di un insieme ordinato. Sottoinsiemi ordinati, intervalli. Esempi.
    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.
    Reticoli: definizione come insiemi ordinati e definizione come insiemi con due operazioni binarie. Principio di Dualità per reticoli.
      Bibliografia:   [Cam] Capitolo I, paragrafo 1.3(B) - [G-P] file Relazioni - 2; file Reticoli, paragrafi 1 e 2 - [L-L] Chapter 14, sections 1, 2, 3, 5, 7 and 8
      Videolezioni:   Insiemi ordinati   (generalità, esempi, elementi speciali)   -   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)

VENTESIMA LEZIONE - 18 Novembre 2015:
    Il metodo crittografico R.S.A. (=Rivest-Shamir-Adleman) per la codifica e decodifica dei messaggi.
    Sistemi di equazioni congruenziali: discussione, sistemi equivalenti. Sistemi cinesi. 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, paragrafi 7, 8 e 9

DICIANNOVESIMA LEZIONE - 16 Novembre 2015:
    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: Le seguenti condizioni sono equivalenti:   (1) n è irriducibile (=primo);   (2) Z_n è un campo;   (3) Z_n è un dominio (cioè non ha divisori di zero).
    La funzione di Eulero: definizione, formula esplicita.
    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 della base invertibile (col Teoremadi Eulero) e caso generale.
    Esercizi 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

DICIOTTESIMA LEZIONE - 13 Novembre 2015:
    Descrizione delle classi di congruenza modulo n.
    Aritmetica modulare: compatibilità di somma e prodotto con ogni congruenza modulo n. Somma e prodotto in Z_n .
    Teorema: Z_n è un anello commutativo unitario (senza dimostrazione).
    Criteri di divisibilità in Z: strategia generale - calcolo di una classe in Z_n - esempi specifici.
    Equazioni congruenziali in Z: definizione, connessione con equazioni modulari in Z_n, connessione con equazioni diofantee in Z; criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni.
    Esempi espliciti di risoluzione di equazioni congruenziali e/o modulari.
      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

DICIASSETTESIMA LEZIONE - 11 Novembre 2015:
    Divisibilità tra un intero e un altro in termini delle loro fattorizzazioni in irriducibili.
    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. Descrizione dell'insieme quoziente 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

SEDICESIMA LEZIONE - 9 Novembre 2015:
    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. Elementi coprimi (o "primi tra loro").
    Esistenza del MCD in Z, e identità di Bézout per esso: calcolo con l'algoritmo euclideo delle divisioni successive. Esempi di calcolo esplicito.
    Tra i numeri interi, ogni irriducibile è primo.
    Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) 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 - [L-L] Chapter 11, sections 4, 5, 6, 7 - [PC] Capitolo 2, paragrafi 2 e 3

QUINDICESIMA LEZIONE - 6 Novembre 2015:
    Richiami sugli interi: operazioni, ordine, valore assoluto. Costruzione degli interi a partire dai naturali, come "naturali + i negativi": elementi, operazioni, ordine, valore assoluto (cenni).
    Il problema generale della fattorizzazione in un monoide: esempi e controesempi varî.
    Divisibilità. 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) non invertibili (dimostrazione dell'esistenza).
      Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Cam] Capitolo II, paragrafi 2 e 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 1, 2, 3, 5, 7 - [PC] Capitolo 2, paragrafi 1 e 3

QUATTORDICESIMA LEZIONE - 4 Novembre 2015:
    1^o Teorema di Cantor: L'unione disgiunta di una famiglia finita (non vuota) o numerabile di insiemi numerabili è numerabile  
    Corollario: L'unione di una famiglia finita numerabile di insiemi finiti o numerabili, di cui almeno uno sia numerabile, è numerabile  
    Applicazioni: gli insiemi Z, Q e NxN sono numerabili.
    2^o Teorema di Cantor: La cardinalità dell'insieme delle parti di un insieme è strettamente maggiore della cardinalità dell'insieme stesso.
    I numeri cardinali infiniti superiori "Aleph_n" (per ogni n in N); la cardinalità del continuo: |R| = |P(N)| .
    La relazione d'ordine tra numeri cardinali è un buon ordinamento. L'ipotesi del continuo generalizzata. Distribuzione (rispetto alla relazione d'ordine) dei numeri cardinali.
    Esercizi sui coefficienti binomiali.
      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 - 2 Novembre 2015:
    Equipotenza tra insiemi; l'equipotenza è riflessiva, simmetrica, transitiva. Cardinalità di un insieme, numeri cardinali. Insiemi finiti, infiniti numerabili o infiniti non numerabili.
    Relazione d'ordine tra numeri cardinali; Teorema di Schroeder-Bernstein (senza dimostrazione).
    Proprietà degli insiemi numerabili:
      - ogni insieme infinito contiene un sottoinsieme numerabile;
      - in un insieme numerabile, ogni sottoinsieme o è finito oppure è numerabile.
    Caratterizzazione degli insiemi infiniti: per un 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 - 30 Ottobre 2015:
    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; il triangolo di Pascal-Tartaglia;
      - calcolo del numero di partizioni di un insieme finito in sottoinsiemi con numero di elementi assegnato: coefficienti multinomiali;
    Applicazioni: la formula di Newton per lo sviluppo delle potenze di un binomio (in termini di coefficienti binomiali) o di un multinomio (in termini di coefficienti multinomiali).
      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

UNDICESIMA LEZIONE - 28 Ottobre 2015:
    Numerazione in base arbitraria. Scrittura posizionale (di un numero naturale) in base b (>1) arbitraria: esistenza e unicità.
    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 .
    Esercizi varî sulla scrittura posizionale in base arbitraria (determinazione della scrittura, conversione da una base ad un'altra, operazioni - somma, ecc. - in base fissata).
      Bibliografia:   [Cam] Capitolo II, paragrafo 2 - [G-P] file Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [PC] Capitolo 2, paragrafo 10
      Videolezione:   Numerazione (numerazione in base arbitraria / scrittura posizionale)

DECIMA LEZIONE - 26 Ottobre 2015:
    Dimostrazioni per induzione, dei vari tipi (debole, forte - base dell'induzione, passo induttivo - o con principio del minimo): idea, strategia operativa (base, passo induttivo).
    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.
    Esempi di dimostrazioni per induzione.
      Bibliografia:   [Cam] Capitolo II, paragrafo 1 - [G-P] file Induzione - [L-L] Chapter 1, section 8; Chapter 11, sections 3 and 4 - [PC] Capitolo 1, paragrafo 4
      Videolezioni:   Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo])   -   Divisione (divisione con resto tra numeri naturali)

NONA LEZIONE - 23 Ottobre 2015:
    Sistema dei numeri naturali (=S.N.N.): definizione tramite assiomi di Peano. Il Principio di Induzione Debole, o Semplice (=Pr.I.D./S.).
    Il problema della esistenza e unicità di un S.N.N. (cenni). Controesempi di S.N.N.
    Relazione d'ordine in un S.N.N. 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).
    Operazioni di somma e prodotto tra numeri naturali. L'insieme dei numeri naturali è un semianello (per somma e prodotto) in cui l'ordine è compatibile con le due operazioni (senza dimostrazione).
      Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Cam] Capitolo I, paragrafo 5 - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 1, paragrafo 4
      Videolezione:   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)

OTTAVA LEZIONE - 21 Ottobre 2015:
    Il sottoinsieme degli elementi invertibili in un monoide è un gruppo (per la stessa operazione). Il monoide libero A^* su un insieme A (=linguaggio sull'alfabeto A) con l'operazione di giustapposizione.
    Insiemi con due operazioni (binarie); casi speciali (semianelli, anelli, campi); esempi e controesempi.
    L'insieme delle parti (di un insieme) è un anello commutativo unitario - ma non un campo - per la differenza simmetrica e l'intersezione. Il campo con due elementi.
    Esempi di Z₅ - è un anello commutativo unitario, ed è un campo - e Z₆ - è un anello commutativo unitario, ma non un campo.
      Bibliografia:   [Cam] Capitolo I, paragrafo 4 - [G-P] file Gruppi, anelli, campi - [L-L] Appendix B - [PC] Capitolo 4, paragrafo 1
      Videolezione:   Operazioni 2 (insiemi con più operazioni)

SETTIMA LEZIONE - 19 Ottobre 2015:
    Decomposizione di funzioni. La decomposizione canonica di una funzione tramite l'insieme quoziente (modulo l'equivalenza associata alla funzione data) e l'immagine della funzione stessa.
    Esempi espliciti di decomposizione canonica di una funzione.
    Operazioni n-arie in un insieme. Gruppoidi. Proprietà speciali di operazioni binarie. Unicità di elemento neutro (se esiste) e di elemento inverso (se esiste) di un elemento dato.
    Semigruppi, monoidi, gruppi. Esempi e contro esempi di gruppoidi, semigruppi, monoidi, gruppi. L'insieme delle endofunzioni, risp. delle permutazioni, di un insieme è un monoide, risp. un gruppo, per la composizione.
      Bibliografia:   [Cam] Capitolo I, paragrafi 3 e 4 - [G-P] file Gruppi, anelli, campi - [L-L] Appendix B - [PC] Capitolo 5, paragrafi 1 e 2
      Videolezione:   Operazioni 1 (operazioni in un insieme; insiemi con una operazione)

SESTA LEZIONE - 16 Ottobre 2015:
    La congruenza modulo n tra numeri interi è una equivalenza.
    Classi di equivalenza; rappresentante di una classe di equivalenza; insieme quoziente, proiezione canonica.
    La relazione in X associata ad una partizione di X.
    La biiezione naturale tra l'insieme delle equivalenze in X e l'insieme delle partizioni di X.
      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)

QUINTA LEZIONE - 14 Ottobre 2015:
    Relazioni (binarie) in un insieme; interpretazione grafica di una relazione come "grafo orientato".
    Proprietà notevoli per una relazione: riflessività, simmetricità, antisimmetricità, transitività. Esempi e controesempi.
    Relazioni di preordine; relazioni d'ordine (parziale), relazioni d'ordine totale. Esempi e controesempi.
    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.
      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 - 12 Ottobre 2015:
    Caratterizzazione delle famiglie come funzioni.
    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 - 9 Ottobre 2015:
    Funzioni (o "applicazioni"): definizione, esempi, controesempi. Immagini e controimmagini. Restrizione di una funzione ad un sottoinsieme del dominio.
    Legame tra funzioni e corrispondenze: la "funzione canonica" associata ad una corrispondenza.
    Funzioni iniettive; funzioni suriettive; funzioni biiettive. Caratterizzazione della biiettività di una funzione tramite la corrispondenza inversa (deve essere a sua volta una funzione). Esempi e controesempi.
    Composizione di funzioni. La composizione di funzioni iniettive, risp. suriettive, è iniettiva, risp. suriettiva.
      Bibliografia:   [Cam] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3 - [PC] Capitolo 1, paragrafo 3
      Videolezioni:   Funzioni 1 (funzioni; iniettività, suriettività, biiettività)   -   Funzioni 2 (composizione di funzioni, funzioni invertibili)

SECONDA LEZIONE - 7 Ottobre 2015:
    Famiglie: definizione, comparazione con gli insiemi. Partizioni di un insieme.
    Prodotto cartesiano tra due o più insiemi.
    Corrispondenze tra insiemi: definizione, esempi. Immagine (tramite una corrispondenza data) di un sottoinsieme del dominio; controimmagine (tramite una corrispondenza data) di un sottoinsieme del codominio.
    Corrispondenza vuota, corrispondenza totale; corrispondenza identica.
    Corrispondenza complementare (o "opposta") e corrispondenza inversa di una corrispondenza data. Composizione - o "prodotto (operatorio)" - di due corrispondenze. Proprietà notevoli di inversione e composizione: associatività, esistenza di "elementi neutri", ecc. Potenze di una corrispondenza.
      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 - 5 Ottobre 2015:
    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.
    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.
      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)