Nuova ricerca

Maria Rita CASALI

Professore Ordinario
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

Insegnamento: Matematica Discreta

Artificial intelligence engineering (D.M.270/04) (Offerta formativa 2023)

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.

Per un ulteriore approfondimento degli obiettivi formativi, si rimanda alla lettura dei Risultati di apprendimento attesi

Prerequisiti

Elementi di base di teoria degli insiemi, di logica e di algebra lineare.

Programma del corso

[0.5 cfu] 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.

[1 cfu] 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.

[1 cfu] 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.

[0.5 cfu] Calcolo combinatorio: disposizioni, permutazioni e combinazioni; il principio della somma e del prodotto; il principio di inclusione/esclusione; la formula di Da Silva.

[1.5 cfu] 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.

[1.5 cfu] 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.

La scansione dei contenuti per CFU è da intendere come indicativa. Essa può infatti subire modifiche nel corso dell’insegnamento alla luce dei riscontri e della partecipazione degli studenti.

Metodi didattici

L'insegnamento consta di lezioni frontali (svolte in lingua italiana, anche attraverso l'ausilio di strumenti multimediali), con innestata attività di esercitazione, che permette l'applicazione immediata dei concetti e dei metodi teorici appresi.
Gli studenti lavoratori possono usufruire del materiale didattico presente su Moodle, ed in particolare di videolezioni di anni precedenti.

Testi di riferimento

Testi per approfondimento:
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)

Materiale didattico a cura del docente verrà reso disponibile su piattaforma moodle (moodle.unimore.it).

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.

Per gli studenti della LM Matematica (per i quali alcuni contenuti del programma sono già compresi in insegnamenti precedenti), è richiesta durante la prova orale la presentazione di un approfondimento su un argomento concordato con il docente.

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.

Per la attribuzione del voto si considera:
- conoscenza basilare degli argomenti e capacità parziale di applicare la conoscenza: voto minimo (18/30)
- conoscenza piena degli argomenti e capacità ottima di applicare la conoscenza: voto massimo (30/30 e lode)
- graduazione dei voti intermedi in base al raggiungimento dei risultati di apprendimento attesi, compresi quelli trasversali dimostrati durante la prova d’esame.

Risultati attesi

1. Conoscenza e capacità di 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.