DISCRETE MATHEMATICS
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2019/2020
- Teacher
- CINZIA BISI
- Credits
- 6
- Didactic period
- Primo Semestre
- SSD
- MAT/05
Training objectives
- Our aim is to bring the students to a good level of mathematical maturity.We will try to widen their cultural horizon without loosing sight of the applications.For these reasons we have chosen subjects of both theoretical and applicative importance.
The most important knowledges vested are :
1) first concepts in combinatorics, congruences and recursive rules;
2) Codes theory;
3) Graphs Theory.
4) first concepts in cryptography.
The principal skills are:
1) transalte a problem in mathematical language;
2) solve a problem in criptography and transmission of coded messages. Prerequisites
- Differential calculus,linear algebra.
Course programme
- (In the following programme we refer to the Notes of the Course.Proof's knowledge of a theorem is required only if explicitly written).
Part 0
Groups and finite fields.
Part 1
-Basic ArithmeticDefinition of divisor,of prime number and of composite number.The infinity of the prime numbers.Fundamental theorem of Arithmetic. Definition of greatest common divisor.
-CongruencesDefinition of congruence and basic properties.Cancellation law.Definition of complete system of residues.Proposition 4 (p.308),with proof.Eucidean algorithm and greatest common divisor.Linear congruences:theorem3 (p.311),with proof.Euler’s phi function.Definition of reduced system of residues:proposition 5 (p.317),with proof.The Euler-Fermat theorem,with proof.The order of a number n mod m:of this part,from p.319 to 324 ,only the definitions and the statements of theorems are required.R.S.A. cryptosystem,with proof.The discrete logarithm problem and the Diffie -Hellman problem.The definition of group.The running time of the Euclidean algorithm (in order to calculate the greatest common divisor of two numbers),with proof.The running time of modular exponentiation,with proof.The solution of linear congruences,with proof.-Codes 1) ( Here we refer to the notes entitled “ Teoria dei codici” ).Basic considerations.Definition of metric space.Definition of distance in Vn . Vn,d is a metric space,with proof.Definition of code. Definition of code that detecs (up to) e errors and corrects (up to) e errors.Theorem 1 (p.9),with proof.Theorem 2 (Hamming’s inequality),with proof.Definition of perfect code. 2) (Here we refer to the notes entitled “ La struttura di gruppo commutative di Vn,+)Vn,+ is a commutative group.Definition of linear code.Theorem 1 (only the statement is required).Theorem 2 ( Lagrange,only the statement is required).The fundamental parameters of linear codes.Practical usefulness of linear codes.Definition of weight of a word:theorem 3,with proof.Construction of linear codes by means of binary matrices (from p.11 to 188,you must know how to do it).Autocorrecting codes:theorem 4,with proof.The Hamming codes are perfect codes,with proof.
Part 2
-Recursion:Definition of recurrence relation; examples of recursively defined sequences.The Hanoi Towers example. Second-order linear homogeneous recurrence relations with constant coefficients. Derivation of a technique for solving these relations: the distinct-root case and the single-root case (with proofs). Higher-Order linear homogeneous (and non-homogeneous) recurrence relations with constant coefficients. The Catalan numbers. -Graphs and Trees:Graphs: definitions and basic properties.Basic terminology and examples of graphs. Special Graphs. The concept of degree of a vertex: undirected and directed graphs. The "shaken hands" theorem with proof. Definition of path and cycle in a graph. Connectedness of a graph. Matrix representations of graphs. Incidence matrices. Matrix moltiplication and counting walks of length N (theorem and proof). Isomorphic graphs. Planar graphs and the Euler Theorem (with proof). Graph coloring and chromatic number of a graph. Trees. Didactic methods
- For each argument of the course, there is a series of theoretical lessons, to which follow some exercises developed by the teacher at the blackboard. Students are also highly encouraged to go to the blackboard to solve some given problems.
Learning assessment procedures
- The exam consists of two parts:in the first one the student must solve problems and exercices,in the second one she/he should write down the proofs of fundamental theorems and results seen in the course.
The final valuation is the mean of the two partial valuations, the written exam and the oral exam.
Passing the final exam is the proof that knowledge and abilities outlined in the training objectives of the course have been achieved. Reference texts
- Reference texts for the lessons:
1) K. H. Rosen “Discrete Mathematics and its Applications” .
2) Teacher handouts in italian.
Complementary Readings:
3)N. Biggs “Discrete Mathematics” Oxford University Press.
