MATEMATICA DISCRETA
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2019/2020
- Docente
- CINZIA BISI
- Crediti formativi
- 6
- Periodo didattico
- Primo Semestre
- SSD
- MAT/05
Obiettivi formativi
- Il nostro scopo è quello di portare gli studenti ad un buon livello di maturità matematica, cercando, nello stesso tempo, di ampliare notevolmente il loro orizzonte culturale, senza perdere di vista le applicazioni. Per questi motivi abbiamo cercato di scegliere argomenti di grande importanza sia teorica che applicativa.
Le princiali conoscenze acquisite sono:
1) rudimenti di combinatorica, congruenze e ricorsività;
2) teoria dei codici;
3) teoria dei grafi.
4) le basi di crittografia.
Le principali abilita' sono:
1) tradurre un problema in linguaggio matematico;
2) risolvere un problema di crittografia e di trasmissione cifrata di messaggi. Prerequisiti
- Analisi Matematica 1 e 2, Algebra Lineare.
Contenuti del corso
- Parte 0.
Strutture Algebriche Fondamentali (Gruppi e Campi Finiti).
Parte 1 (Teoria dei Numeri con applicazioni crittografiche):Congruenze e loro proprietà. Il Teorema di Eulero-Fermat. L'algoritmo della divisione euclidea e dell'esponenziazione modulare: loro “running-time”. Il crittosistema R.S.A. e quello di El Gamal. Schemi di firme digitali.Parte 2 (Teoria dei Codici):Considerazioni di base. Definizione di Spazio Metrico. La distanza in V^n (=insieme delle n-ple di cifre binarie). Definizione generale di codice, di codice che scopre (fino) a e errori e che corregge (fino) a e errori. I parametri fondamentali che caratterizzano i codici: lunghezza delle parole, numero delle parole e loro minima distanza. Stima di Hamming. Definizione di codice perfetto .Codici Lineari. La struttura di gruppo di (V^n, +). Definizione di codice lineare . Costruzione di codici lineari mediante matrici binarie. Vantaggi dei codici lineari. Correzione degli errori nei codici lineari. Codici di Hamming. Parte 3 (Ricorsività):Che cosa e'' una legge ricorsiva. La soluzione non e'' unica ma dipende dai dati iniziali. L'esempio delle Torri di Hanoi. Ricorsione lineare omogenea di grado k=1,2,… . Esempi di ricorsione lineare non omogenea e come si risolve passando all'omogenea associata. I due teoremi che danno la formula risolutiva della ricorsività lineare omogenea di grado 2, caso delle due radici coincidenti e caso delle due radici distinte. I numeri di Catalan come esempio di ricorsione non lineare.Parte 4 (Grafi):Definizione ed esempi di Grafo, Multigrafo, Pseudografo, con o senza orientazione, e loro differenze. Il grado di un vertice di un grafo con o senza orientazione. Teorema della Stretta di Mano di un grafo con o senza orientazione, con dimostrazione. Il grafo bipartito ed il grafo bipartito completo. Definizione ed esempi di sottografo e di sottografo indotto da un sottoinsieme di vertici. Matrice d'incidenza di un grafo. Isomorfismo tra grafi ed Automorfismo di un grafo. Quando due grafi sono isomorfi in termini delle loro matrici di incidenza. Cammini di lunghezza n tra due vertici di un grafo. Grafo connesso. Distanza tra vertici di un grafo e diametro di un grafo. Legame tra la potenza r-esima della matrice di incidenza ed il numero di cammini di lunghezza r tra due vertici. Grafi planari. Teorema di Eulero. Colorazione di grafi e numero cromatico. Teorema dei 4 colori. Metodi didattici
- Per ogni argomento del corso, ad una serie di lezioni teoriche seguono delle esercitazioni che il docente svolge in classe agli studenti. Nell' ambito delle esercitazioni, gli studenti sono anche chiamati alla lavagna a svolgere esercizi nell'ottica di capire se hanno afferrato i principali concetti.
Modalità di verifica dell'apprendimento
- Lo studente deve necessariamente superare una prova scritta ed una prova orale, ovvero deve sapere risolvere esercizi rappresentativi degli argomenti svolti durante il corso e deve sapere ricostruire dimostrazioni e spiegare i concetti fondamentali visti a lezione.Il voto finale e' la media del due voti parziali della prova scritta e di quella orale.
Il superamento dell'esame è prova di aver acquisito le conoscenze e le abilità specificate negli obiettivi formativi dell'insegnamento. Testi di riferimento
- Testi di riferimento del corso:
1)K. H. Rosen “Discrete Mathematics and its Applications” .
2)Dispense del Corso in italiano.
Testo consigliato per approfondimenti:
3) N. Biggs “Discrete Mathematics” Oxford University Press.
