Donatella Iacono

Matematica Discreta 2024/2025 (A-L)

Corso di Laurea in Informatica, Corso A-L

Inizio lezioni: Ottobre 2024.

Inizio lezioni 2 Ottobre 2024: Aula 4, primo piano, Palazzo delle Aule. Orario lezioni: Lunedi 8:30-11:00, Mercoledi 8:30-10:10, Giovedi 8:30-11:00.

Ricevimento

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

Esami:

La prenotazione agli appelli È OBBLIGATORIA mediante il sistema ESSE3 nei tempi stabiliti. NON si accettano prenotazioni via mail, netantomeno prenotazioni dopo i termini stabiliti. Portare obbligatoriamente un documento di validità, una penna e se serve una calcolatrice (non si può usare quella del cellulare). La durata della prova è 2 ore. È sconsigliata vivamente la partecipazione all' esame a chi non ha studiato (NON si viene a vedere come è ne tantomeno a tentarlo). 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 può 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, perché non sa usare Esse3, etc. ).

Pagina web degli Esami

Leggere attentamente e comprendere prima di presentarsi agli esami le Regole e faq.

Programma A.A. 2024/2025

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

M.G. Bianchi, A. Gillio: "Introduzione alla Matematica Discreta", ed. McGRAW-HILL

K. H. Rosen, "Discrete Mathematics and Its Applications", McGraw-Hill Editore, Settima Edizione (2012) (in Inglese).

Appunti, a cura di D.Iacono .

Note ed Esercizi svolti di Logica e Insiemi a cura di D.Iacono e V.C. Nardozza.

È stato attivato un canale su telegram https://t.me/MD24AL, per facilitare e velocizzare la comunicazione di avvisi. Tutte le notizie verranno comunque pubblicate sulla pagina web del docente.

Esercizi

Esercizi di recupero su prodotti e potenze.(su prodotti, potenze, frazioni)
Esercizi 7 Ottobre 2024.(alcuni visti a lezione, su insiemi e logica)
Esercizi 9 Ottobre 2024.(alcuni visti a lezione, su logica e funzioni)
Esercizi 10 Ottobre 2024.(alcuni visti a lezione, su logica e funzioni)
Esercizi 14 Ottobre 2024.(alcuni visti a lezione, su funzioni)
Esercizi 16 Ottobre 2024.(alcuni visti a lezione, su funzioni)
Esercizi 17 Ottobre 2024.(alcuni visti a lezione, su funzioni e principio di induzione)
Esercizi 21 Ottobre 2024.(alcuni visti a lezione, su principio di induzione)
Esercizi 24 Ottobre 2024.(alcuni visti a lezione, su principio di induzione e combinatoria)
Esercizi 28 Ottobre 2024.(alcuni visti a lezione, su combinatoria)
Esercizi 28 Ottobre 2024.(alcuni visti a lezione, di riepilogo)
Esercizi 30 Ottobre 2024.(alcuni visti a lezione, su relazioni di ordine)
Esercizi 4 Novembre 2024.(alcuni visti a lezione, su relazioni di equivalenza)[Nei primi 5 esercizi le relazioni sono quelle del foglio del 30 Ottobre]
Esercizi 6 Novembre 2024.(alcuni visti a lezione, su relazioni di equivalenza)[I primi 2 esercizi sono gli stessi del foglio del 4 Novembre scritti con il simbolo di divisione.]
Esercizi 7 Novembre 2024.(alcuni visti a lezione, su divisione e MCD)

Esercizi di riepilogo sulla prima parte del corso (In alcune tracce c'e' un esercizio sui sistemi di congruenze lineari e/o sulle equazioni diofantee che non va svolto, impareremo a svolgerlo dopo la pausa esoneri) Per simulare una prova basta scegliere una traccia, svolgerla in 2 ore usando solo penna e calcolatrice.

Prova di autovalutazione 11 Novembre 2024 Aula A e B, piano terra, Dipartimento di Informatica. Per simulare una prova basta svolgerla in 2 ore usando solo penna e calcolatrice.
Esercizi 18 Novembre 2024.(alcuni visti a lezione, su equazioni diofantee)
Esercizi 20 Novembre 2024.(alcuni visti a lezione, su congruenze)

All'appello del 12 Gennaio 2016, uno studente mi ha fatto giustamente notare che nel titolo manca una i....dal 2011: tutta colpa del copia e incolla! Anche se perseverare è diabolico.... lasciamo questo errore come segno di riconoscimento per esercizi e tracce.

Diario delle Lezioni

02.10.2024 (2h) : Presentazione del corso, orario lezioni, libri di testo, programma, esami, regole e faq. Teoria elementare degli INSIEMI. Esempi. Simbolo di appartenenza. Tre descrizioni per un insieme: elenco elementi, proprietà caratterizzante, Diagrammi di Venn. Inclusione. Esempi.
03.10.2024 (+3=5h) Ripasso appartenenza e inclusione. Inclusione propria, uguaglianza. Esempi. Introduzione al linguaggio e simbolismo matematico: Quantificatori Ogni ed Esiste. Esiste ed è unico. Esempi. Unione, Intersezione. Proprietà. Esempi. Esempi: operazione di somma e prodotto negli insiemi numerici: Commutatività, associatività, esistenza 0 e 1. Definizione di complementare ed esempi. Leggi di De Morgan (con dimostrazione). Insieme Differenza ed esempi. Prodotto cartesiano ed esempi. Insieme delle Parti. Esempi ed Esercizi. LOGICA: Definizione di proposizione. Esempi.
07.10.2024 (+3=8h) Esercizi su legge di De Morgan. LOGICA: Proposizione, negazione, congiunzione, disgiunzione, implicazione. Tavole di Verità. Esempi ed Esercizi. Esercizi di logica: Tabelle di verità, proposizioni logiche, vere, false e negazioni. Doppia implicazione. Tavole di Verità. Esempi ed Esercizi. Equivalenza di proposizioni. Esempi ed Esercizi. Esercizi di logica: Tabelle di verità con tre proposizioni. Equivalenza di proposizioni. Significato Teorema.
09.10.2024 (+2=10h) Esercizi: Proposizioni logiche, vere, false e negazioni. Tabelle di verità con tre proposizioni. FUNZIONI: Definizione di funzione, insieme di partenza e insieme di arrivo. Esempi. Funzioni uguali. Funzioni costanti. Esempi. Funzione identità. Esempi. Immagine di una funzione e di un sottoinsieme. Esempi. Controimmagine di un sottoinsieme. Esempi ed Esercizi su immagini e controimmagine.
10.10.2024 (+3=13h) Esercizi: Proposizioni logiche, vere, false e negazioni. Tabelle di verità con tre proposizioni. Esercizi su immagine e controimmagine. Proprietà di immagine e controimmagine rispetto unione e intersezione. Esercizio su immagine di intersezione di sottoinsiemi. Grafico di una funzione. Esempi. Funzioni iniettive, definizione ed esempi. Funzioni suriettive, definizione ed esempi.
14.10.2024 (+3=16h) Esercizi: Proposizioni logiche, vere, false e negazioni. Tabelle di verità con tre proposizioni. Esercizi su funzioni:controimmagine dell'unione è l'unione delle controimmagini. Ripasso funzioni iniettive e suriettive. Funzioni biettive, definizione ed esempi. Esercizi su funzioni, iniettive, suriettive, biettive. Composizione di funzione e proprietà. Esempi ed esercizi su composizione di funzioni. Esercizio: dimostrazione che la composizioni di funzioni iniettive è iniettiva. Esercizo su funzioni, iniettive, suriettive, biettive, composizioni.
16.10.2024 (+2h=18h): Ripasso composizione di funzioni. Esercizio: dimostrazione che la composizioni di funzioni suriettive è suriettiva. Funzione inversa di funzioni biettive. Proprietà: inversa della composizione di funzione, funzione inversa della funzione identità, funzione inversa della funzione inversa (senza dim). Determinazione della funzione inversa. Esempi ed Esercizi. Esercizi su funzioni: iniettive, suriettive, biettive, inversa, composizione. CARDINALITÀ: Cardinalità di un insieme. Insiemi Equipotenti (o con stessa cardinalita`). Insiemi finiti e proprieta`. Esempi.
17.10.2024 (+3h=21h): Ripasso Insiemi finiti e proprieta`. Insiemi infiniti, definizioni equivalenti. Esempi. PRINCIPIO di INDUZIONE: Principio di induzione e formulazioni equivalenti. Esempi e controesempi ed esercizi sul principio di induzione. Enunciato PRINCIPIO di INDUZIONE generalizzato. Teorema: Cardinalità dell'insieme delle parti di un insieme finito (dim.1 usando il principio di induzione). Esercizio su funzioni: iniettive, suriettive, biettive, inversa, composizione.
21.10.2024 (+3h=24h): Esercizio su principio di induzione. SUCCESSIONI. Definizione di successione ed esempi. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi ed Esercizi. Esercizi su formula chiusa di successioni ricorsive e numeri fattoriali. 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).
23.10.2024 (+2h=26h): Esercizio su formula chiusa di successioni ricorsive. Simbolo di sommatoria e proprietà. Esercizi vari su principio di induzione con simbolo di sommatoria. Cardinalità dell'unione di insiemi finiti. Caso generale di insiemi disgiunti. Cardinalità dell'unione di insiemi finiti: Principio di inclusione-esclusione caso con intersezioni non vuote per due insiemi (con dimostrazione).
24.10.2024 (+3h=29h): Esercizio su formula chiusa di successioni ricorsive. Esercizi vari su principio di induzione con simbolo di sommatoria. Ripasso inclusione-esclusione caso con intersezioni non vuote per due insiemi. Esercizio. Principio di inclusione-esclusione caso con intersezioni non vuote per tre insiemi (con dimostrazione). Cardinalita' del prodotto di insiemi finiti. Esempi. 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) a) =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 cardinalità k ad uno di cardinalità n (con dim.). Esempi. D(n,n)=n! come numero di ordinamenti di n oggetti (permutazioni). D(n,n) calcola il numero di applicazioni biettive tra insiemi di cardinalità n. Esempio. Caso 1) b) =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 cardinalità k in un insieme di cardinalità n. Esempi. Proprieta'. Triangolo di Tartaglia e legame con i coefficienti binomiali. Formula del binomio di Newton (senza dim.).
28.10.2024 (+3h=32h): Ripasso Scegliere k elementi in un insieme con n elementi 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) e Caso 1) ii) =SENZA ripetizioni ordine non importante: Combinazioni semplici di n oggetti di classe k (k minore o uguale ad n). Esercizio su formula coefficiente binomiale per n+1. Seconda dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando la formula di Newton (con dim.). Esercizi ed Esempi. Caso 2) = CON ripetizioni. Caso 2) a) =con ripetizioni ordine importante: Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Esempi ed Esercizi. Numero di funzioni tra due insiemi finiti. Esempi. Caso 2) b) =con ripetizioni ordine non importante: Combinazioni con ripetizioni di n oggetti di classe k. Calcolo (senza dim). Esempi ed Esercizi. RELAZIONI: Definizioni di relazione su un insieme. Esempi. Relazione vuota, totale, identità.
28.10.2024 (+2h=34h): Esercitazione 11:30 Aula VIII: Esercizi vari su logica. Esercizi su funzioni, iniettive, suriettive, biettive, composizioni. Esercizi su formula chiusa di successioni ricorsive. Esercizi vari su principio di induzione con simbolo di sommatoria.
30.10.2024 (+2h=36h): Esercizi vari su combinatoria su disposizioni e combinazioni. Relazione di ordine parziale: Riflessiva, Antisimmetrica, Transitiva. Esempi. Insiemi parzialmente ordinati e insiemi totalmente ordinati. Esempi. Esercizi su relazioni di ordine.
4.11.2024 (+3h=39h): Esercizio su relazione di ordine. Relazioni di equivalenza: Riflessiva, Simmetrica, Transitiva. Esempi. Definizione di classe di equivalenza. Esempi ed Esercizi su relazioni di ordine e di equivalenza. Esempio Importante: a-b multiplo di n. Teorema sulle proprieta' delle classi di equivalenza (senza dimostrazione). Definizione di PARTIZIONE di un insieme. Teorema: le cassi di equivalenza definiscono una partizione e viceversa (senza dimostrazione). Esercizio su relazioni di ordine e di equivalenza e classi.
6.11.2024 (+2h=41h): Ripasso definizione di classe di equivalenza. Teorema sulle proprieta' delle classi di equivalenza Definizione di insieme quoziente. Esempi. Esercizi su relazioni di equivalenza, classi di equivalenza. NUMERI INTERI. Definizione di divisore e multiplo. Proprietà ed esempi. Teorema della combinazione lineare: divisibilità di ogni combinazione lineare (con dimostrazione). Esercizio su relazione di equivalenza con divisione.
7.11.2024 (+3h=44h): Ripasso definizione di divisore e multiplo. Ripasso Teorema della combinazione lineare. Esercizio su induzione con divisione. Teorema della divisione in Z: esistenza ed unicità del quoziente e resto (senza dimostrazione). Esempi di divisioni con resto in tutti i casi (positivi e negativi). Definizione di un massimo comun divisore e definizione di MCD. Proprietà di MCD. Esempi. Definizione di un minimo comune multiplo e di mcm. Teorema: esistenza del MCD e algoritmo di Euclide per la sua determinazione e Identità di Bezout (con dimostrazione). Esempi ed Esercizi. Esercizio su relazione di equivalenza con divisione.
PAUSA ESONERI: 11-15 NOVEMBRE (no lezioni).
Il giorno 11 Novembre, ore 11:30, prova di autovalutazione Aula A e B, piano terra, Dipartimento di Informatica.
18.11.2024 (+3h=47h):Ripasso definizione del MCD e Identità di Bezout. Esercizio. EQUAZIONI DIOFANTEE: Definizione ed Esempi. Teorema di esistenza della soluzione (con dim.). Teorema che descrive tutte e sole le soluzioni di una equazione diofantea (visto solo che sono soluzioni). (Il nome è dovuto a Diofanto, per i più curiosi). Esempi ed Esercizi. Esercizi su equazioni diofantee. NUMERI PRIMI. Definizione di numeri primi. Definizioni equivalenti (senza dimostrazione) e proprietà. 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 di un numero: scrittura esplicita e calcolo di quanti sono i divisori. Applicazione della fattorizzazione per il calcolo del MCD. Esempi.
20.11.2024 (+2h=49h): Ripasso regole dell'esame: per altri dubbi leggere le faq. Esercizio su induzione con divisione. Esercizi su equazioni diofantee. Ripasso definizione numeri primi. Teorema esistenza infiniti numeri primi (con dimostrazione). Crivello di Eratostene per trovare numeri primi e metodo di fattorizzazione. CONGRUENZE modulo n >1. Ripasso della definizione della relazione di congruenza: relazione di equivalenza. Descrizione relazione, classi di equivalenza. Esempi.

DONATELLA IACONO