9795525 - STRUTTURE DISCRETE O - Z

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.0 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 e domande più teoriche in cui sarà verificata la preparazione 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?