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.

Learning Goals

A solid preparation of basic mathematics that provides logical tools and troubleshooting methods. Knowledge of algebraic structures, the basis of theoretical computing; necessary tools for understanding the advanced teachings of the following years.

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.

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. Nozioni di geometria analitica nel piano.

Prerequisites

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

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.

Assessment

The final examination is an oral exam - a set of questions and exercises evaluating skills and knowledge. The purpose of the exam is to make a final review of the topics covered during the semester and assessment of each student's knowledge of the subject. ​​​​​​​The final grade is expressed out of thirty.

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.

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 set. Indexed families of 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. The fundamental Theorem on equivalence relations. 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. Recurrence relations. The Fibonacci sequence. 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. Bézout identity. 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.