M.G. Piacentini Cattaneo:
Matematica Discreta e Applicazioni - Zanichelli
Obiettivi Formativi
Acquisizione delle conoscenze fondamentali di aritmetica, combinatoria, teoria dei grafi e logica. Capacita' di sviluppare ragionamenti e dimostrazioni in modo rigoroso.
Prerequisiti
Sono sufficienti le nozioni base di matematica e logica, che fanno parte dei programmi di ogni scuola media superiore.
Metodi Didattici
Lezioni frontali
Modalità di verifica apprendimento
Esame scritto e orale.
L'esame scritto prevede la verifica della capacita' di applicare le nozioni acquisite durante il corso, nella soluzione di esercizi. Nell'esame orale lo studente dovra' mostrare di aver acquisito i concetti e compreso le dimostrazioni svolte a lezione.
Esame scritto: è un compito scritto con esercizi sugli argomenti svolti durante il corso. Il voto è in trentesimi e l'esame scritto è superato con una votazione di almeno 18/30.
Una parte dello scritto può essere sostenuta durante le prove intermedie di febbraio. In tal caso durante l'appello lo studente deve svolgere un esame scritto ridotto, riguardante solo gli argomenti della seconda parte del corso.
Esame orale: si svolge nello stesso appello dello scritto ed è una interrogazione sulla teoria svolta durante il corso.
Durante la prova orale puo' essere anche richiesto lo svolgimento di alcuni semplici esercizi, al fine di verificare la corretta applicazione della teoria.
Programma del corso
Elementi di teoria degli insiemi; operazioni fra insiemi. Funzioni e relazioni. Relazioni di equivalenza. Induzione. Successioni definite per ricorrenza. Numeri interi: massimo comun divisore, algoritmo euclideo, divisibilita'. Numeri primi. Equazoni diofantee. Calcolo combinatorio elementare: disposizioni, combinazioni, permutazioni; principio di inclusione-esclusione. Aritmetica modulare; teorema di Fermat, funzione di Eulero, teorema cinese dei resti. Sistema crittografico RSA. Criteri di irriduciblita' per polinomi a coefficienti interi e razionali. Strutture algebriche: gruppi, anelli e campi. Gruppo simmetrico. Campi finiti. Relazioni di ordine; insiemi parzialmente ordinati e reticoli. Algebre di Boole. Teoria dei grafi: cammini, alberi, grafi orientati e non orientati. Grafi euleriani e grafi hamiltoniani. Grafi planari. Grafi bipartiti. Colorabilita' di grafi. Applicazioni. Teorema di Hall e teorema di Koenig.Connettivita'; teorema di Menger. Reti e flussi. Elementi di logica matematica: il linguaggio della logica proposizionale, l’algoritmo di Davis- Putnam, linguaggi della logica dei predicati, skolemizzazione, deduzioni per via automatica.