Introduzione ai temi e alle tecniche della Matematica Discreta.

Oltre ad una panoramica di diversi tipi di problemi, uno degli scopi principali del corso è quello di  far esercitare anche una abilità di "problem solving", in cui si richiede una qualche creatività nell'applicazione degli strumenti della Matematica Discreta. Infine il corso si propone di sviluppare la capacità dello studente di presentare un’argomentazione corretta.

 

Tra i vari punti essenziali del corso ci sono dunque:  il ragionamento matematico rigoroso; l'abilità di contare oggetti di vario tipo (analisi combinatoria); lo studio di strutture matematiche discrete: insiemi, permutazioni, relazioni, numeri interi, grafi; lo studio di strutture algebriche quali i gruppi, anelli e campi.

Nello specifico, un programma di massima del corso è il seguente:

Numeri interi. Numeri primi. Numeri di Fibonacci. Il teorema fondamentale dell'Aritmetica e alcune sue conseguenze. La funzione di Eulero. La congruenza modulo n . Sistemi di congruenze. Il teorema cinese dei resti. Gruppi. Gruppi ciclici. Gruppi finiti. Il teorema di Lagrange. Il teorema di Cauchy. Il piccolo teorema di Fermat. Il teorema di Eulero. Anelli e campi. Campi finiti. Polinomi, matrici e spazi vettoriali su un campo finito. Elementi di crittocrafia classica e a chiave pubblica. Funzioni aritmetiche unidirezionali. Il  metodo di Diffie e Hellman. Il protocollo RSA. Introduzione ai codici lineari. Teoria delle partizioni di interi. Funzioni generatrici, trasformata zeta. Successioni definite per ricorrenza. Polinomi ortogonali. Identita' soddisfatte da coefficienti binomiali. Formula di convoluzione di Vandermonde. Alcuni risultati generali sugli insiemi finiti.  Cenni  alla teoria di Ramsey.

 Grafi finiti. Grafi connessi. Alberi. Il teorema di Cayley. Grafi piani. La formula di Eulero. Il teorema di Kuratowski. Grafi euleriani. Grafi hamiltoniani. La matrice di adiacenza di un grafo finito e le sue potenze. Il polinomio caratteristico di un grafo. Autovalori di un grafo.