Obiettivi Formativi

Questo corso è inteso a sviluppare nello studente la comprensione delle idee matematiche , a maturare l'attitudine al pensiero astratto e a far conoscere quelle strutture algebriche che sono alla base dell’Informatica Teorica. In tal modo lo studente avra’ piena conoscenza dei fondamenti logico-matematici dell’Informatica , dei fondamenti algoritmici e della matematica computazionale. Si vuole inoltre enfatizzare l'importanza di una corretta notazione matematica nel ragionamento scientifico. Lo studente aumenterà la sua conoscenza matematica, sviluppando la sua capacità nel linguaggio matematico. Competenze acquisite: Alla fine del corso lo studente acquisirà competenze di base nell'ambito della Matematica Discreta , come specificato nel programma del corso. Acquisirà esperienza ed abilità nell'affrontare problemi di carattere combinatorio, aritmetico e logico, nel risolvere problemi numerici direttamente o impostando algoritmi da implementare su macchine; sarà in grado di sviluppare semplici dimostrazioni per via diretta, per assurdo e/o per induzione e a manipolare espressioni logiche. Metodi di accertamento L’esame finale di Matematica Discreta consiste in una prova scritta . Il compito si articola in una serie di 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. Fra il primo e il secondo semestre si svolge una prova in itinere: essa consiste in una prova scritta avente per oggetto solo gli argomenti svolti nel primo semestre. Dopo la fine del corso, ogni studente che avrà superato la prova in itinere sosterrà una prova d’esame scritta avente per oggetto solo gli argomenti svolti nel secondo semestre, con una valutazione globale espressa da un voto in trentesimi, che terrà conto anche della valutazione della prova in itinere. Gli studenti che non avranno superato la prova in itinere , o non avranno potuto partecipare alla stessa prova, potranno sostenere l’esame finale consistente in una prova scritta avente per oggetto gli argomenti svolti nel primo e secondo semestre in tutti gli appelli previsti dopo la fine del corso.

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 argomenti del programma.

Prerequisiti

Algebra elementare (ad es: potenze, radici, logaritmi, esponenziali e loro proprietà; prodotti notevoli, risoluzione di equazioni e disequazioni di primo e secondo grado). Nozioni di geometria analitica nel piano (ad es:riferimento cartesiano, diagrammi di retta, circonferenza).

Verifiche dell'apprendimento

L’esame di Matematica Discreta consiste in una prova scritta . Il compito si articola in una serie di 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. Fra il primo e il secondo semestre si svolge una prova in itinere: essa consiste in una prova scritta avente per oggetto solo gli argomenti svolti nel primo semestre. Dopo la fine del corso, ogni studente che avrà superato la prova in itinere sosterrà una prova d’esame scritta avente per oggetto solo gli argomenti svolti nel secondo semestre, con una valutazione globale espressa da un voto in trentesimi, che terrà conto anche della valutazione della prova in itinere. Gli studenti che non avranno superato la prova in itinere , o non avranno potuto partecipare alla stessa prova, potranno sostenere l’esame finale consistente in una prova scritta avente per oggetto gli argomenti svolti nel primo e secondo semestre in tutti gli appelli previsti dopo la fine del corso.

Programma del Corso

Teoria degli insiemi: Insiemi, sottoinsiemi, uguaglianza tra insiemi. Operazioni tra insiemi: unione, intersezione, differenza, differenza simmetrica; proprietà delle operazioni tra insiemi. Insieme delle parti, complementare di un sottoinsieme, leggi di De Morgan. Famiglie di insiemi; ricoprimenti e partizioni. Prodotto cartesiano, corrispondenze tra insiemi. Cardinalità o potenza di un insieme : insiemi finiti ed infiniti e tecniche di enumerazione. Insiemi equipotenti. Il principio di inclusione-esclusione. Insiemi numerabili. La potenza del numerabile è minore di quella del continuo. Ogni insieme ha potenza minore di quella dell’insieme delle sue parti. Relazioni su un insieme. Relazioni di equivalenza, classi di equivalenza e proprietà. Insieme quoziente rispetto ad una relazione di equivalenza. Legame tra le partizioni di un insieme A e le relazioni di equivalenza definite su A. Strutture algebriche: Leggi di composizione. Leggi associative e commutative. Elemento neutro. Gruppoidi. Semigruppi. Monoidi. Gruppi. Sottogruppi. Anelli . Divisori dello zero. Domini d’integrità. Corpi . Campi. Gruppi quozienti . Anelli quozienti. Insiemi numerici e Aritmetica modulare: I numeri naturali. Il principio d’induzione matematica. Formule fondamentali del calcolo combinatorio:permutazioni , disposizioni , combinazioni, numeri di Bell, formula del binomio, formule di Stifel. I numeri interi. Operazioni in Z e loro proprietà. Divisibilità in Z . Elementi invertibili ed elementi associati. Elementi primi ed elementi irriducibili in Z. Divisione con resto in Z . Divisori , multipli , massimo comun divisore e minimo comune multiplo in Z . Proprietà del M.C.D. e del m.c.m.. L’algoritmo euclideo delle divisioni successive per la ricerca del M.C.D.. Identità di Bezout. Fattorizzazione in Z. Il Teorema Fondamentale dell’Aritmetica. Infinita’ dei numeri primi. Relazioni ricorsive. I numeri di Fibonacci ed alcune proprietà. Congruenze e loro proprietà . L’anello Zn delle classi resto modulo n. Elementi invertibili in Zn . Il campo GF(p) ( p primo) delle classi resto modulo p. Il Piccolo Teorema di Fermat e conseguenze. La funzione di Eulero. Il Teorema di Eulero. Calcolo di potenze modulo n. Il sistema crittografico RSA. Equazioni diofantee e congruenze lineari. Risoluzioni di congruenze lineari. Il Teorema Cinese dei Resti. Algebra lineare: Generalità sugli spazi vettoriali. Intersezioni e somme di sottospazi . Vettori linearmente indipendenti e dipendenti. Generatori e basi di uno spazio vettoriale. Applicazioni lineari. Generalità sulle matrici. Somma di matrici. Moltiplicazione di uno scalare per una matrice. Prodotto di matrici righe per colonne. Anello delle matrici quadrate. Matrici diagonali, matrici triangolari, simmetriche ed antisimmetriche e loro proprietà. Rango di una matrice. Matrici ridotte. Trasformazioni elementari sulle righe o colonne di una matrice. Riduzioni di matrici. Matrici echelon o a scalini. Matrici triangolari superiori ed inferiori. Metodo di eliminazione di Gauss. Generalità sui sistemi lineari. Riduzione di sistemi lineari. Sistemi lineari equivalenti. Risoluzione dei sistemi lineari con il metodo di riduzione. Teorema di Rouche’ Capelli. Sistemi lineari omogenei. Soluzioni di un sistema lineare omogeneo. Determinante di una matrice. Proprietà dei determinanti. Minori e complementi algebrici di una matrice . Autovalori e autovettori. Teorema di Laplace. Teorema di Binet. Matrici invertibili e proprietà. Calcolo della matrice inversa. Teorema di Cramer per i sistemi lineari.