Subject: MATEMATICA DISCRETA (A.A. 2020/2021)
Unit Matematica discreta
Advanced Theoretical Studies (lesson)
The course intends providing students with a number of fundamental mathematical notions relating to discrete sets, highlighting the resolutive and demonstrative methods relating to their study.
Specific goals are: the study and/or detailed examination of notions relating to equivalence relations, prime numbers and factoring problems, modular arithmetic, in order to provide the theoretical bases needed to study cryptography; knowledge of the main properties and resolutive methods of recursive relations; knowledge of the basic aspects of the graph theory.
Sets and relations
Cardinality of sets. Sets with the same power. Finite and infinite sets. Discrete sets. Countable sets. The cardinality of continuum. Comparison of cardinalities: Cantor-Berstein theorem. Equivalence relations. Equivalence classes. Quotient sets. Partitions.
Integer numbers and the theory of divisibility
The Euclidean division. The greatest common divisor: definition, existence and uniqueness. The Euclidean algorithm and computation of the GCD. Properties of the co-prime numbers and characterisation of prime numbers. The least common multiple. Solution of diophantine linear equations. The unique factorization theorem. Existence of infinite prime numbers.
Congruence relation modulus a positive integer n. The set of the remainder classes mod. n and its operations. The Chinese theorem of the remainder. Linear congruences. The Euler function and the Euler-Fermat theorem. Public key cryptography methods RSA. Error corrector codes.
Simple and repeating dispositions; permutations; simple and repeating combinations; permutations on a multiset. Sum and Product Principle. Inclusion/exclusion principle. Da Silva formula.
Recursion: recursive definitions and recursive algorithms. Closed formulas. Homogenous and non-homogeneous linear recursion relations. Solution of the first-order linear recursive relations. "Divide et impera" type algorithms. Characteristic equation of a recursive relation. Solution of second-order linear homogeneous relations. Fibonacci numbers. The Hanoi tower problem. Some elements of generating functions.
Elements of graph theory
Special graphs. Graph isomorphisms. Walks; paths; cycles. Connected components. The incidence matrix. Degree of a vertex and graph score. Eulerian and Hamiltonian graphs. Trees and recovering trees. Colourings and chromatic number of a graph; Chromatic polynomial; Whitney theorem.
The teaching method consists of lectures (also carried out via multimedia tools), mixed with exercise activity, which allows to immediately apply concepts and theoretical methods.
The exam consists of a written and an oral examination. The written examination consists of a multiple choice test, containing both theoretical questions and exercises, and four open-ended exercises. Aim of the oral test is to verify the theoretical knowledge of the subjects, with particular attention to the proof of the main theorems, which allows to test the correct use of mathematical formalism and the hypothetical deductive thinking, and the ability to use knowledge, also in the presence of concrete problems with different starting hypoteses.
Through lectures and individual study, knowledge of:
- cardinality; properties of discrete sets; existence of cardinality greater than countable
- equivalence relations and quotients
- euclidean division; greatest common divisor and related results
- Properties of coprime numbers and characterization of prime numbers
- Least common multiple and related results
- congruence relation mod. n and related notions and results
- Linear congruences; systems of linear congruences and the Chinese Remainder Theorem
- Euler function, Euler-Fermat's theorem and the basis of the encryption method RSA
- Notions of combinatorics; principle of inclusion/exclusion
- Linear recursive relations and their solution methods
- Graphs and their properties.
Through classroom exercises and individual work, ability to solve problems and exercises concerning the above subjects, and to apply them in concrete situations.
Attitude towards a methodological approach that leads to verify claims and methods through rigorous arguments.
Ability to self-assessment of their skills and abilities.
Ability to deal with a dialectical discourse in a timely and consistent way, arguing with precision.
Lasting acquisition of mathematical knowledge to be used at any time of their cultural journey.
Attitude towards a methodological approach that leads to an improvement in the method of study in order to deepen learning capacity.
G.M.Piacentini Cattaneo, Algebra - un approccio algoritmico, Decibel Zanichelli (2001)
M.W.Baldoni-C.Ciliberto-G.M.Piacentini Cattaneo, Aritmetica, crittografia e codici, Springer (2006)
M.Barnabei - F.Bonetti, Matematica Discreta Elementare, Pitagora (1994)
R.L.Graham - D.E.Knuth - O.Patashnik, Matematica discreta, Hoepli, (1992)
N.L.Biggs, Discrete Mathematics, Oxford Science Publications (1998)
K.Rosen, Handbook of Discrete and Combinatorial Mathematics, Chapman & Hall (2000)
A.Facchini, Algebra e Matematica Discreta, Decibel Zanichelli (2000)
L.Giuzzi, Codici correttori, Springer (2006)