STRUTTURE DISCRETE A - L

Anno accademico 2020/2021 - 1° anno - Curriculum Elaborazione Dati e Applicazioni e Curriculum Sistemi e Applicazioni
Docente: Vincenzo CUTELLO
Crediti: 6
SSD: INF/01 - Informatica
Organizzazione didattica: 150 ore d'impegno totale, 102 di studio individuale, 24 di lezione frontale, 24 di esercitazione
Semestre:

Obiettivi formativi

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.


Modalità di svolgimento dell'insegnamento

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.


Prerequisiti richiesti

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


Frequenza lezioni

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


Contenuti del corso

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.

 


Testi di riferimento

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.



Programmazione del corso

 ArgomentiRiferimenti testi
1Introduzione alla Logica Proposizionale e agli operatori di base Lucidi delle lezioni 
2Insiemi e Relazioni: Il concetto di insieme e le proprietà di base. Insiemi ed operazioni tra di essi. Dimostrazione diretta. Esercizi su InsiemiLucidi delle lezioni 
3Famiglie di insiemi. Insieme prodotto. Paradossi.Lucidi delle lezioni 
4Relazioni binarie e funzioni. Relazioni di Equivalenza. Relazioni d’ordine, Rappresentazione di insiemi finiti Esercizi e Problemi su Relazioni e Famiglie di Insiemi. Lucidi delle lezioni 
5CASO STUDIO: Famiglie di insiemi chiuse e la congettura Union-ClosedLucidi delle lezioni 
6Numeri Interi Introduzione e operazioni sui numeri interi. Principio di Induzione. Divisione tra interi. DivisibilitàLucidi delle lezioni 
7MCD ed Algoritmo di Euclide. Numeri Primi e Coprimi. Criteri di divisibilità. Problemi ed EserciziLucidi delle lezioni 
8Aritmetica Modulare Congruenze. Proprietà delle congruenze. Invarianza rispetto a somma e prodotto: conseguenze ed eserciziLucidi delle lezioni 
9Funzione φ di Eulero Definizione e formula generale. Il Teorema di Eulero. Esempi ed eserciziLucidi delle lezioni 
10Applicazioni dell’Aritmetica modulare La prova del 9. Codici ISBN e Carte di Credito. Cifrari monoalfabetici a trasposizioneLucidi delle lezioni 
11Teoria dei numeri e problemi aperti Numeri primi di Mersenne e numeri perfetti. Numeri primi gemelli. La congettura di GoldbachLucidi delle lezioni 
12CASO STUDIO: Il problema 3x + 1 (Congettura di Collatz)Lucidi delle lezioni 
13Calcolo Combinatorio e Probabilità Discrete: Disposizioni e combinazioni. Permutazioni e Combinazioni. Teorema Binomiale. Lucidi delle lezioni 
14Il triangolo di Pascal. Combinazioni con ripetizione. Esercizi. Principio dei cassetti (Pigeonhole principle)Lucidi delle lezioni 
15Probabilità discreta. Formalizzazione Matematica. Assiomi e Proprietà. La regola di Bayes. Problemi d’urna. Esercizi. Variabili casuali. Problemi ed eserciziLucidi delle lezioni 
16CASO STUDIO: Il paradosso di Monty Hall, giochi e paradossi probabilistici.Lucidi delle lezioni 
17Grafi e Alberi: Introduzione: strette di mano e passeggiate su ponti. Definizioni di base.Lucidi delle lezioni 
18Gradi di un nodo. Classi particolari di grafi: Grafi regolari, Grafi completi, Grafi Bipartiti.Lucidi delle lezioni 
19Sottografi, Isomorfismi e Omeomorfismi: Definizione di sottografo, Isomorfismi, Omeomorfismi.Lucidi delle lezioni 
20Percorsi, cammini e cicli. Grafi connessi. Rappresentazione di un grafo. Numero di percorsi tra nodi. Grafi Euleriani ed Hamiltoniani. Grafi pesati.Lucidi delle lezioni 
21Il problema del commesso viaggiatore. Grafi planari. Colorazione di un grafo.Lucidi delle lezioni 
22Alberi: definizioni fondamentali e classi particolari di alberi.Lucidi delle lezioni 
23CASI STUDIO:Problemi combinatori su grafi.Lucidi delle lezioni 

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

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.


Esempi di domande e/o esercizi frequenti

  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: 115 ≡ 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?