Obiettivi Formativi

Una solida preparazione di matematica di base che fornisca gli strumenti di logica e i metodi risolutivi di problemi. La conoscenza di strutture algebriche che sono alla base dell'Informatica Teorica, strumenti necessari alla comprensione e alla formalizzazione e propedeutici agli insegnamenti avanzati degli anni successivi.

Metodi didattici

Le metodologie didattiche utilizzate consistono nello svolgimento di un'attività di lezioni teoriche e di esercitazioni mirate a verificare l'apprendimento dei concetti teorici svolti durante le lezioni. Sono anche previste presentazioni in Power Point inerenti agli argomenti del programma.

Prerequisiti

Algebra elementare. Nozioni di geometria analitica nel piano.

Verifiche dell'apprendimento

L'esame di Matematica Discreta consiste in una prova orale che prevede anche lo svolgimento di alcuni esercizi su tutti gli argomenti previsti dal programma per un punteggio massimo di 30/30. In tal modo: - si accertano le conoscenze acquisite dagli studenti su ogni singolo argomento del programma; - si verifica la capacità degli studenti ad applicare la teoria studiata a problemi.

Programma del Corso

Teoria degli insiemi: Insiemi, sottoinsiemi, uguaglianza tra insiemi. Operazioni tra insiemi: unione, intersezione, differenza. Insieme delle parti. Famiglie di insiemi; ricoprimenti e partizioni. Prodotto cartesiano. Cardinalità di un insieme: insiemi finiti ed infiniti e tecniche di enumerazione. Insiemi equipotenti. Il principio di inclusione-esclusione. Insiemi numerabili. Relazioni su un insieme. Relazioni di equivalenza, classi di equivalenza. Insieme quoziente. Legame tra le partizioni di un insieme A e le relazioni di equivalenza definite su A. Strutture algebriche. Gruppoidi. Semigruppi. Monoidi. Gruppi. Sottogruppi. Anelli. Domini d'integrità. Corpi. Campi. Aritmetica modulare. Il principio d'induzione matematica. Formule fondamentali del calcolo combinatorio. I numeri di Bell, formule di Stifel. I numeri interi. Operazioni in Z e loro proprietà. Divisione con resto in Z. Divisori, multipli, massimo comun divisore e minimo comune multiplo in Z. L'algoritmo euclideo delle divisioni successive. Identità di Bézout. Il Teorema Fondamentale dell'Aritmetica. Relazioni ricorsive. I numeri di Fibonacci. Congruenze e loro proprietà. L'anello Zn delle classi resto modulo n. Il campo di Galois GF(p) (p primo) delle classi resto modulo p. Il Piccolo Teorema di Fermat. La funzione di Eulero. Il Teorema di Eulero. Calcolo di potenze modulo n. Il sistema crittografico RSA. Equazioni diofantee e congruenze lineari. Il Teorema Cinese dei Resti.