STRUTTURE DISCRETE A - L

Conoscenza e capacità di comprensione (knowledge and understanding): Lo studente acquisirà le nozioni di base delle strutture matematiche discrete che sono alla base dell’informatica, e che servono per interpretare e descriverne i problemi.

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente acquisirà le competenze necessarie per affrontare ed analizzare da un punto di vista teorico le problematiche tipiche dell’informatica ed in particolare dell’algoritmica, risolvendo problemi classici in cui è richiesta l’applicazione di tecniche standard.

Autonomia di giudizio (making judgements): lo studente sarà in grado di elaborare autonomamente soluzioni ai principali problemi oggetto del corso scegliendo la strategia più conveniente sulla base dei risultati appresi.

Abilità comunicative (communication skills): lo studente acquisirà le necessarie abilità comunicative ed il linguaggio specifico della matematica discreta, e del suo uso in informatica.

Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente il metodo di studio, la forma mentis e il rigore logico che gli saranno necessari per poter affrontare e risolvere autonomamente nuove problematiche che dovessero sorgere durante la sua attività lavorativa come informatico.

Lezioni frontali per un totale di 48 ore.

Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

È essenziale avere buona conoscenza degli elementi di base dell'Aritmetica e dell'Algebra Elementare,

Le risorse principali messe a disposizione dello studente sono le lezioni frontali e quindi la frequenza è fortemente consigliata.

Il corso, per un totale di 6CFU, è suddiviso in 4 parti di diversa ampiezza, come sotto delineato. Ognuna delle parti si conclude con uno o più casi studio di particolare importanza.

Parte I: Insiemi e Relazioni (1.5 CFU):

Introduzione alla Logica Proposizionale e agli operatori di base.

Il concetto di insieme e le proprietà di base. Insiemi ed operazioni tra di essi. Dimostrazione diretta. Esercizi su Insiemi

Famiglie di insiemi. Insieme prodotto. Paradossi.

Relazioni binarie e funzioni. Relazioni di Equivalenza. Relazioni d’ordine, Rappresentazione di insiemi finiti
Esercizi e Problemi su Relazioni e Famiglie di Insiemi. Il Problema del "Hitting Set"

Caso Studio: Famiglie di insiemi chiuse e la congettura Union-Closed

Parte II: Fondamenti di Teoria dei Numeri e metodologie di dimostrazione (1.5 CFU):

Numeri Interi

Introduzione e operazioni sui numeri interi. Principio di Induzione. Divisione tra interi. Divisibilità

MCD ed Algoritmo di Euclide. Numeri Primi e Coprimi. Criteri di divisibilità. Problemi ed Esercizi

Aritmetica Modulare

Congruenze. Proprietà delle congruenze. Invarianza rispetto a somma e prodotto: conseguenze ed esercizi

Funzione φ di Eulero

Definizione e formula generale. Il Teorema di Eulero. Esempi ed esercizi

Applicazioni dell’Aritmetica modulare

La prova del 9. Codici ISBN e Carte di Credito. Cifrari monoalfabetici a trasposizione

Teoria dei numeri e problemi aperti

Numeri primi di Mersenne e numeri perfetti. Numeri primi gemelli. La congettura di Goldbach

CASO STUDIO: Il problema 3x + 1 (Congettura di Collatz)

Parte III: Calcolo Combinatorio e Probabilità Discrete (1 CFU):

Calcolo Combinatorio

Introduzione. Disposizioni e combinazioni. Permutazioni e Combinazioni. Teorema Binomiale. Il triangolo di Pascal. Combinazioni con ripetizione.
Esercizi. Principio dei cassetti (Pigeonhole principle)

Probabilità Discrete

Introduzione. Formalizzazione Matematica. Assiomi e Proprietà. La regola di Bayes. Problemi d’urna.
Esercizi. Variabili casuali. Problemi ed esercizi

Caso Studio: Il paradosso di Monty Hall, giochi e paradossi probabilistici.

Parte IV: Grafi e Alberi (2.0 CFU):

1

Introduzione alla Teoria dei Grafi

Introduzione: strette di mano e passeggiate su ponti. Definizioni di base.
Gradi di un nodo. Classi particolari di grafi: Grafi regolari, Grafi completi, Grafi Bipartiti.

Sottografi, Isomorfismi e Omeomorfismi: Definizione di sottografo, Isomorfismi, Omeomorfismi.

Percorsi, cammini e cicli. Grafi connessi. Rappresentazione di un grafo. Numero di percorsi tra nodi. Grafi Euleriani ed Hamiltoniani. Grafi pesati.

Il problema del commesso viaggiatore. Grafi planari. Colorazione di un grafo.
Alberi: definizioni fondamentali e classi particolari di alberi.

CASI STUDIO:Problemi combinatori su grafi.

Nessun testo di riferimento specifico. Il docente fornirà agli studenti i lucidi del corso e quant'altro materiale necessario e sufficiente per completare ed approfondire gli argomenti discussi a lezione.

L'esame prevede un test scritto, in cui allo studente sarà chiesto di risolvere alcuni esercizi ed una prova orale, riservata agli studenti che hanno ottenuto la sufficienza nel test scritto, in cui sarà verificata la preparazione teorica dello studente sugli argomenti (definizioni e proprietà formali) trattati a lezione.

La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

1. Qual è il numero massimo di archi che un grafo bipartito con un totale di 10 vertici può avere?

2. Un grafo planare connesso con 6 vertici e 7 archi, quante facce contiene?

3. La seguente congruenza è vera o falsa: 11⁵ ≡ 1(mod 7)

4. In un’urna ci sono 5 palline bianche e 10 palline rosse. Estraiamo due palline. Qual è la probabilità che nell’urna siano rimaste solo 3 palline bianche?