 |
Maria Rita CASALI
Professore Ordinario
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica
|
Insegnamento: Matematica discreta
Matematica (Offerta formativa 2021)
Obiettivi formativi
Il corso si propone di fornire agli studenti alcune nozioni matematiche fondamentali relative agli insiemi discreti, evidenziando le tecniche risolutive e dimostrative connesse con il loro studio.
Gli obiettivi specifici sono: lo studio e/o l'approfondimento delle nozioni relative a relazioni di equivalenza, numeri primi e problemi di fattorizzazione, aritmetica modulare, al fine di fornire le basi teoriche necessarie allo studio della criptografia; la conoscenza delle principali proprietà e tecniche risolutive delle relazioni ricorsive; la conoscenza degli elementi basilari della teoria dei grafi.
Prerequisiti
Nessuno.
Programma del corso
Complementi su insiemi e relazioni: cardinalità degli insiemi; insiemi equipotenti; insiemi discreti; il teorema di Cantor-Berstein; relazioni di equivalenza; classi di equivalenza; insieme quoziente; partizioni.
I numeri interi e la teoria della divisibilità: la divisione euclidea; il massimo comun divisore; identità di Bezout e algoritmo di Euclide; proprietà dei numeri coprimi e caratterizzazione dei numeri primi; il minimo comune multiplo; il teorema fondamentale dell'aritmetica; il metodo di fattorizzazione di Fermat; esistenza di infiniti numeri primi; risoluzione di equazioni diofantee lineari.
Aritmetica modulare: la congruenza modulo n; l'insieme delle classi resto e le sue operazioni; il piccolo teorema di Fermat. Congruenze lineari e sistemi di congruenze lineari; il teorema cinese del resto. La funzione di Eulero e il teorema di Eulero-Fermat. Il metodo di crittografia a chiave pubblica RSA. Codici rilevatori e/o correttori di errori.
Calcolo combinatorio: disposizioni, permutazioni e combinazioni; il principio della somma e del prodotto; il principio di inclusione/esclusione; la formula di Da Silva.
Relazioni ricorsive: formule chiuse; risoluzione di relazioni ricorsive lineari del primo ordine, omogenee e non omogenee; algoritmi del tipo "divide et impera"; equazione caratteristica di una relazione ricorsiva; risoluzione di relazioni ricorsive lineari omogenee del secondo ordine; estensione al caso dell'ordine superiore. I numeri di Fibonacci. Il problema della torre di Hanoi. Funzione generatrice di una successione.
Elementi di teoria dei grafi: grafi notevoli; isomorfismi di grafi; passeggiate, cammini, cicli, componenti connesse; matrici di incidenza; grado di un vertice e score di un grafo; grafi euleriani ed hamiltoniani; alberi ed alberi ricoprenti. Grafi planari; teorema di Kuratowski; formula di Eulero. Colorazioni e numero cromatico di un grafo. Polinomio cromatico; teorema di Whitney.
Metodi didattici
L'insegnamento consta di lezioni frontali (svolte anche attraverso l'ausilio di strumenti multimediali), con innestata attività di esercitazione, che permette l'applicazione immediata dei concetti e dei metodi teorici appresi.
Testi di riferimento
G.M.Piacentini Cattaneo, Algebra - un approccio algoritmico, Decibel Zanichelli (2001)
M.W.Baldoni-C.Ciliberto-G.M.Piacentini Cattaneo, Aritmetica, crittografia e codici, Springer (2006)
M.Barnabei - F.Bonetti, Matematica Discreta Elementare, Pitagora (1994)
R.L.Graham - D.E.Knuth - O.Patashnik, Matematica discreta, Hoepli, (1992)
N.L.Biggs, Discrete Mathematics, Oxford Science Publications (1998)
K.Rosen, Handbook of Discrete and Combinatorial Mathematics, Chapman & Hall (2000)
A.Facchini, Algebra e Matematica Discreta, Decibel Zanichelli (2000)
L.Giuzzi, Codici correttori, Springer (2006)
Verifica dell'apprendimento
L’esame consta di una prova scritta ed una prova orale, entrambe svolte senza l'ausilio di testi e/o appunti.
La prova scritta consiste di un test con 7 domande a risposta multipla, contenente sia quesiti teorici che esercizi, e di quattro esercizi a risposta aperta.
Per ogni domanda del test a risposta multipla sono fornite quattro possibili risposte, di cui una soltanto corretta. Il punteggio si ottiene calcolando 3 punti per ogni risposta corretta, -1 punti per ogni risposta errata e 0 punti per ogni domanda a cui non si è data risposta. Le domande a risposta aperta sono valutate con punteggio compreso tra 0 e 3 per ciascuna.
L’accesso all’orale attraverso la prova scritta d’esame è concesso - limitatamente all’a.a. di riferimento - se il voto è maggiore o uguale a 15.
Se si sostiene una prova orale con esito negativo, la validità dello scritto rimane limitata ad una sola ulteriore prova orale all’interno dell’a.a.: dopo due orali negativi, la prova scritta perde di validità.
La prova orale è volta alla verifica della conoscenza teorica degli argomenti in programma, con particolare attenzione all'aspetto della dimostrazione dei teoremi principali, che permette di testare l'uso corretto del formalismo matematico e del pensiero ipotetico deduttivo, e la capacità di utilizzo maturo delle conoscenze, anche in presenza di problemi concreti con ipotesi iniziali diverse.
Il voto finale è stabilito dall’esaminatore sulla base della prova orale, tenendo conto anche del voto dello scritto: dalla prova orale dipende comunque in modo preponderante il voto complessivo.
Risultati attesi
1. Conoscenza e comprensione
Tramite lezioni frontali e studio individuale, conoscenza di:
- cardinalità degli insiemi; proprietà degli insiemi discreti; esistenza di cardinalità superiori al numerabile
- relazioni di equivalenza e quozienti
- divisione euclidea; massimo comun divisore e teoremi relativi
- proprietà dei numeri coprimi e caratterizzazione dei numeri primi
- minimo comune multiplo e teoremi relativi
- relazione di congruenza modulo n, insieme delle classi resto modulo n e relative proprietà.
- congruenze lineari; sistemi di congruenze lineari e teorema cinese del resto.
- la funzione di Eulero, il teorema di Eulero-Fermat e le basi del metodo di crittografia a chiave pubblica RSA
- nozioni di calcolo combinatorio; principio di inclusione/esclusione
- relazioni ricorsive lineari e relativi metodi risolutivi
- grafi e loro proprietà
2. Capacità di applicare conoscenza e comprensione
Tramite le esercitazioni e il lavoro individuale, capacità di risolvere problemi ed esercizi relativi agli argomenti precedenti, e di applicarli in situazioni concrete.
3. Autonomia di giudizio
Attitudine ad un approccio metodologico che conduca a verificare tramite argomentazioni rigorose le affermazioni e i metodi presentati.
Capacità di autovalutazione delle proprie competenze ed abilità.
4. Abilità comunicative
Saper esporre in modo chiaro gli argomenti affrontati nel corso, formulando definizioni ed enunciati in modo adeguato e sapendone fornire dimostrazioni rigorose e dettagliate.
Capacità di affrontare in modo puntuale e coerente un confronto dialettico, argomentando con precisione.
5. Capacità di apprendimento.
Attitudine ad un approccio metodologico che conduca ad un miglioramento del metodo di studio con conseguente approfondimento della capacità di apprendere.
Acquisizione delle conoscenze di tipo matematico come proprio patrimonio, da poter utilizzare in qualsiasi altro momento del proprio percorso culturale.