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.

Learning Goals

Discrete Mathematics is a rapidly growing and increasingly used area of mathematics, with many practical and relevant applications.Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers and statements in logic– do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets(sets that have the same cardinality as subsets of the natural numbers, including rational numbers but not real numbers). Because it is grounded in real-world problems, discrete mathematics it is often defined as an active branch of contemporary mathematics that is widely used in business and industry. Since many discrete math problems are simply stated and have few mathematical prerequisites, they are appropriate for students at all levels and of all abilities. The students will improve reasoning and problem-solving skills. The final examination is a written test given to students at the end of the annual course of study . The purpose of the test is to make a final review of the topics covered during the year and assessment of each student's knowledge of the subject.

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.

Teaching Methods

Methods of instruction: 1)Explaining, or lecturing by giving spoken explanations of the subject that is to be learned. Lecturing is often accompanied by visual aids to help students visualize an object or problem. 2)Demonstrating,e.g. teaching through examples or applications. For example, a demonstration may be used to prove a fact through a combination of visual evidence and associated reasoning.

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).

Prerequisites

The basic concepts and formulas of elementary algebra and analytic geometry.

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.

Assessment

The final examination is a written test given to students at the end of the annual course of study . The purpose of the test is to make a final review of the topics covered during the semester and assessment of each student's knowledge of the subject.

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.

Course Syllabus

Set Theory: Sets and subsets.The empty set.Proper subsets.Equality of sets.Venn diagrams.Operations on sets.Space, complement of a set. Power sets. Partitions of sets.Finite and infinite sets.Counting principle. Equipotent sets.Inclusion-exclusion principle.Properties of denumerable sets. Nondenumerable sets.Cardinal numbers.Cantor's theorem.Cartesian product.Relations.Equivalence relations.Equivalence classes.Quotient sets. Algebraic systems: Operations and semigroups. Monoids. Groups and subgroups. Rings. Zero divisors.Integral domains. Division rings. Fields. Quotient groups. Quotient rings. Sets of numbers and Modular Arithmetic: Principle of Mathematical Induction. Counting principle,factorial notation. Binomial coefficients. Permutations. Combinations. The binomial theorem. Bell numbers. Stifel's formulas. The set of the integers:Z. Divisibility. Prime factors and the Greatest Common Divisor. The Least Common Multiple. The division algorithm. Euclid's algorithm. The fundamental theorem of arithmetic. Congruences of integers. Congruences classes. The Galois fields:GF(p), p prime. Fermat theorem. Euler function. Euler theorem. RSA cryptosystem. Linear congruences. The chinese remainder theorem. Linear Algebra: Vector spaces. Subspaces. Linear indipendence. Basis and dimension. Linear transformations. Matrices. Matrix addition and scalar multiplication. Matrix multiplication. Transpose. Rank.Square matrices.Invertible matrices. Row reduction and echelon forms. Gaussian elimination. Elementary matrices. Symmetric matrices. Determinants. Determinant properties.The inverse of a matrix. Systems of linear equations. Rouchè -Capelli theorem. Cramer's rule.Eigenvalues and eigenvectors. The characteristic equation.