Electronics Engineering

Lesson 1 and 2: A brief introduction to the problems and methods of Discrete Mathematics. Natural Numbers. Induction principle. Well-ordering principle. Greatest common divisor and Bézout identity. Fundamental theorem of arithmetic. There exist infinitely many prime numbers: Euclid’s proof. Perfect numbers. Mersenne numbers. (1.1-1.3 Appunti) Exercises. Lesson 3: Euclid proof can be adapted to show that there exist infinitely many prime numbers of the form 4n+3. But it cannot be adapted to show that there are infinitely many prime numbers of the form 4n+1. Why? (V. Appunti p.6) Proof that the series of the reciprocal of primes diverges, from which we deduce, again, that there are infinitely many prime numbers. Definition of a continued fraction and some simple computation to write fractions as continued fractions. Infinite continued fractions. The case of [1;1,1,1,1,1,…]. (Appunti 1.4,1.5) Exercises. Lessons 4 and 5: Continued fractions and Euclid’s algorithm of successive divisions. Convergent as the best rational approximation with a small denominator. Recursive method to quickly compute the value of a continued fraction. Case of the golden section and the Fibonacci sequence. Exercises. Definition of the congruence relation. Quotient set of remainder modulo n. Addition and multiplication tables for Z6 and Z7. Zero divisors. Invertible elements in Zn. Abelian group structure and ring structure in Zn. Field structure in Zn, when n is prime. Properties of congruences. How to simplify a congruence. Lemma on the power of a binomial modulo a prime number. (Appunti 1.6 ) Exercises Lesson 6: Divisibility criteria. Fermat small theorem and its proof. Solution of linear congruences. Solvability criterion. Method of solution. (Appunti 1.7) Exercises Lesson 7,8: Exercises on solutions of linear congruences. Systems of congruences: Chinese remainder theorem. Representation of an integer as a “vector” of its congruences classes. Reduction to the case of coprime moduli. Definition of the Euler φ function. Property of the function φ. Formula for the function φ based on the factorization of n. Introduction to the notion of Group. Dihedral group of the symmetries of an equilateral triangle. Simbols used and computations with dihedral groups. (Appunti 1.7,1.8 ) Exercises Lesson 9: Definition of a group. Several examples. Dihedral groups and symmetric groups. Order of a group. Order of an element. Definition of cyclic group. Examples. Generators of a cyclic group. Subgroups. A subgroup of a cyclic group is cyclic. Group of the n-th roots of 1. (Appunti 2.1, 2.2) Exercises Lessons 10,11: Lagrange Theorem: proof and some corollaries. A group having prime order p is necessarily cyclic. If G is a group of finite order n, then gn=e, for all g in G. Proof of Fermat’s small theorem as a consequence of Lagrange’s theorem. Euler’s theorem, also a consequence of Lagrange’s theorem. Homomorphisms. Kernel, image of a homomorphism. Injectivity and surjectivity of a homomorphism. Group isomorphism. Classification theorem of cyclic groups. A special example of a ring: S. (Appunti 2.3, 2.4) Exercises Lezione 12: Ring and field notions. Polynomial ring. The ring F[x] is Euclidean if F is a field. Division among polynomials. Irreducibile polynomials. Irreducibility of x4+1 as a polynomial with coefficients in Z3. Introduction to the classification of finite fields (Galois fields). (Appunti 2.5) Exercises Lessons 13,14: Characteristic of a field. Fundamental subfield. Classification theorem of finite fields. Construction of a finite field using irreducible polynomials. Primitive elements. (Appunti 2.6) Introduction to cryptography. Definition of a cryptosystem. Classical cryptosystems: affine cryptosystems. Monoalphabetic and polyalphabetic cryptosystems. Hill’s cipher. Vigénère’s cipher. (Appunti 3.1) Exercises Lezione 15: Cryptoanalys of a Vigénère cipher. Kasiski’s test. Friedman’s coincidence index. Public Key cryptography. RSA method. Exercises. Lessons 16,17: RSA method. Diffie-Hellman protocol for key exchange. Signature authentication. [Appunti 3.2, 3.3, 3.4] Exercises. Lesson 18: Exercises. Review. Fermat factorization method. Exercises. Lessons 19, 20: Written exercitation. Lezione 21: Introduction to Code theory. Correcting and detecting codes. Hamming distance. Minimum distance of a code. Equivalence of two codes. The main problem of code theory. [Appunti 4.1, 4.2, 4.3] Lessons 22, 23: Spheres in Fqn. Hamming inequality. Perfect codes. Some examples and properties of A2(n,d). Linear codes. Equivalence of linear codes. Hamming code of type [7,4,3] starting from Fano plane. Hamming code is perfect. [Appunti 4.3, 4.4] Lesson 24: Minimum distance and minimum weight. Generator matrix of a linear code. Generator matrices of equivalent codes. Elementary row and (some) column operations. Generator matrix in standard form. Every matrix can be put in standard form. Definition of inner product in Fqn. Isotropic vectors. Orthogonal complement of a code: dual code. [Appunti 4.5, 4.6] Exercises. Lesson 25: Parity check matrix H of a code. Standard form of H. Examples. Syndrome of a vector. Syndrome of a coset. Syndrome decoding. [Appunti 4.6, 4.7] Lessons 26, 27: Hamming codes, 1-corrector and perfect. Introduction to combinatorics. Some examples of combinatorial problems. Walks on lattices. Fibonacci numbers and some of their properties. Binet’s Formula. Generating functions. [Appunti 4.8, 5.1, 5.2] Exercises. Lesson 28: Solutions of homogeneous linear recurrence relations. Formal series, convolution product. [Appunti 5.3, 5.4] Exercises. Lesson 29: Catalan number sequence. Quadratic recurrence. Generating function for Catalan numbers. Closed formula for the n-th Catalan number. Triangulations of convex di polygons. Integer partitions. Generating function of integer partitions. Money changing problem. [Appunti 5.5, 6.1] Exercises. Lessons 30, 31: Euler’s theorem on partitions in odd part and distinct parts. Binomial Coefficients: some identities. Vandermonde convolution identity: an analytic proof and a combinatorial proof. Definition of graph and of a simple graph. Some special graphs: complete graphs, hypercubes, bipartite graphs. The problem of the Konigsberg bridges. Euler theorem on Eulerian paths. Adjacency matrix of a graph. [Appunti, 7.1, 7.3, 8.1,8.2,8.3, 8.6] Esercizi. Lessons 32, 33: Hamiltonian circuits.Dirac and Ore theorems. Bipartite graphs and matchings. Coloring of graphs and applications. Handshaking lemma. Exercitation.

Besides the usual high-school matematics that includes elementary geometry, algebra (polynomials, equations, inequalities) and trigonometry, the successful student must know the content of the fundamental notions studied in the course of Geometry Syllabus: http://www.dmmm.uniroma1.it/~stefano.capparelli/didattica/Geometria%2016-17/Diario%20delle%20lezioni%2016-17.htm as well as a good working knowledge of the content of a first course in mathematical analysis: http://www.sbai.uniroma1.it/~daniela.sforza/analisi_17-18/DIARIO_A1_17-18.pdf

If a student follows lectures regularly then itis enough to study on my class notes Lectures on Discrete Math, Esculapio ed. 2025, (Italian Version: Lezioni di Matematica Discreta (Esculapio ed. 2025).

The course is presented via traditional classroom lectures containing a suitable amount of motivation and new material, as well as the necessary examples and exercises. Both new material and exercises are presented together.

Attendance is optional

The final written examination will require the solving of a suitable number of exercises concerning material studied in class, but it will also have some problems aimed at testing the problem solving capability of the student.

a. Baldoni, Ciliberto, Piacentini Cattaneo: Aritmetica, Crittografia e Codici, Springer 2006 b. Biggs, Discrete Mathematics, Oxford, 2002 c. Brualdi, Introductory Combinatorics, Prentice Hall, 1999. d. Cerasoli, Eugeni, Protasi, Elementi di Matematica Discreta, Zanichelli 1988 e. Knuth, The art of Computer Programming, Vol. I Addison Wesley, 1997 f. Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley 1988 g. Schroeder, Number Theory in Science and Communication, Springer 2009

The course is presented via traditional classroom lectures containing a suitable amount of motivation and new material, as well as the necessary examples and exercises. Both new material and exercises are presented together.

Lesson 1 and 2: A brief introduction to the problems and methods of Discrete Mathematics. Natural Numbers. Induction principle. Well-ordering principle. Greatest common divisor and Bézout identity. Fundamental theorem of arithmetic. There exist infinitely many prime numbers: Euclid’s proof. Perfect numbers. Mersenne numbers. (1.1-1.3 Appunti) Exercises. Lesson 3: Euclid proof can be adapted to show that there exist infinitely many prime numbers of the form 4n+3. But it cannot be adapted to show that there are infinitely many prime numbers of the form 4n+1. Why? (V. Appunti p.6) Proof that the series of the reciprocal of primes diverges, from which we deduce, again, that there are infinitely many prime numbers. Definition of a continued fraction and some simple computation to write fractions as continued fractions. Infinite continued fractions. The case of [1;1,1,1,1,1,…]. (Appunti 1.4,1.5) Exercises. Lessons 4 and 5: Continued fractions and Euclid’s algorithm of successive divisions. Convergent as the best rational approximation with a small denominator. Recursive method to quickly compute the value of a continued fraction. Case of the golden section and the Fibonacci sequence. Exercises. Definition of the congruence relation. Quotient set of remainder modulo n. Addition and multiplication tables for Z6 and Z7. Zero divisors. Invertible elements in Zn. Abelian group structure and ring structure in Zn. Field structure in Zn, when n is prime. Properties of congruences. How to simplify a congruence. Lemma on the power of a binomial modulo a prime number. (Appunti 1.6 ) Exercises Lesson 6: Divisibility criteria. Fermat small theorem and its proof. Solution of linear congruences. Solvability criterion. Method of solution. (Appunti 1.7) Exercises Lesson 7,8: Exercises on solutions of linear congruences. Systems of congruences: Chinese remainder theorem. Representation of an integer as a “vector” of its congruences classes. Reduction to the case of coprime moduli. Definition of the Euler φ function. Property of the function φ. Formula for the function φ based on the factorization of n. Introduction to the notion of Group. Dihedral group of the symmetries of an equilateral triangle. Simbols used and computations with dihedral groups. (Appunti 1.7,1.8 ) Exercises Lesson 9: Definition of a group. Several examples. Dihedral groups and symmetric groups. Order of a group. Order of an element. Definition of cyclic group. Examples. Generators of a cyclic group. Subgroups. A subgroup of a cyclic group is cyclic. Group of the n-th roots of 1. (Appunti 2.1, 2.2) Exercises Lessons 10,11: Lagrange Theorem: proof and some corollaries. A group having prime order p is necessarily cyclic. If G is a group of finite order n, then gn=e, for all g in G. Proof of Fermat’s small theorem as a consequence of Lagrange’s theorem. Euler’s theorem, also a consequence of Lagrange’s theorem. Homomorphisms. Kernel, image of a homomorphism. Injectivity and surjectivity of a homomorphism. Group isomorphism. Classification theorem of cyclic groups. A special example of a ring: S. (Appunti 2.3, 2.4) Exercises Lezione 12: Ring and field notions. Polynomial ring. The ring F[x] is Euclidean if F is a field. Division among polynomials. Irreducibile polynomials. Irreducibility of x4+1 as a polynomial with coefficients in Z3. Introduction to the classification of finite fields (Galois fields). (Appunti 2.5) Exercises Lessons 13,14: Characteristic of a field. Fundamental subfield. Classification theorem of finite fields. Construction of a finite field using irreducible polynomials. Primitive elements. (Appunti 2.6) Introduction to cryptography. Definition of a cryptosystem. Classical cryptosystems: affine cryptosystems. Monoalphabetic and polyalphabetic cryptosystems. Hill’s cipher. Vigénère’s cipher. (Appunti 3.1) Exercises Lezione 15: Cryptoanalys of a Vigénère cipher. Kasiski’s test. Friedman’s coincidence index. Public Key cryptography. RSA method. Exercises. Lessons 16,17: RSA method. Diffie-Hellman protocol for key exchange. Signature authentication. [Appunti 3.2, 3.3, 3.4] Exercises. Lesson 18: Exercises. Review. Fermat factorization method. Exercises. Lessons 19, 20: Written exercitation. Lezione 21: Introduction to Code theory. Correcting and detecting codes. Hamming distance. Minimum distance of a code. Equivalence of two codes. The main problem of code theory. [Appunti 4.1, 4.2, 4.3] Lessons 22, 23: Spheres in Fqn. Hamming inequality. Perfect codes. Some examples and properties of A2(n,d). Linear codes. Equivalence of linear codes. Hamming code of type [7,4,3] starting from Fano plane. Hamming code is perfect. [Appunti 4.3, 4.4] Lesson 24: Minimum distance and minimum weight. Generator matrix of a linear code. Generator matrices of equivalent codes. Elementary row and (some) column operations. Generator matrix in standard form. Every matrix can be put in standard form. Definition of inner product in Fqn. Isotropic vectors. Orthogonal complement of a code: dual code. [Appunti 4.5, 4.6] Exercises. Lesson 25: Parity check matrix H of a code. Standard form of H. Examples. Syndrome of a vector. Syndrome of a coset. Syndrome decoding. [Appunti 4.6, 4.7] Lessons 26, 27: Hamming codes, 1-corrector and perfect. Introduction to combinatorics. Some examples of combinatorial problems. Walks on lattices. Fibonacci numbers and some of their properties. Binet’s Formula. Generating functions. [Appunti 4.8, 5.1, 5.2] Exercises. Lesson 28: Solutions of homogeneous linear recurrence relations. Formal series, convolution product. [Appunti 5.3, 5.4] Exercises. Lesson 29: Catalan number sequence. Quadratic recurrence. Generating function for Catalan numbers. Closed formula for the n-th Catalan number. Triangulations of convex di polygons. Integer partitions. Generating function of integer partitions. Money changing problem. [Appunti 5.5, 6.1] Exercises. Lessons 30, 31: Euler’s theorem on partitions in odd part and distinct parts. Binomial Coefficients: some identities. Vandermonde convolution identity: an analytic proof and a combinatorial proof. Definition of graph and of a simple graph. Some special graphs: complete graphs, hypercubes, bipartite graphs. The problem of the Konigsberg bridges. Euler theorem on Eulerian paths. Adjacency matrix of a graph. [Appunti, 7.1, 7.3, 8.1,8.2,8.3, 8.6] Esercizi. Lessons 32, 33: Hamiltonian circuits.Dirac and Ore theorems. Bipartite graphs and matchings. Coloring of graphs and applications. Handshaking lemma. Exercitation.

Besides the usual high-school matematics that includes elementary geometry, algebra (polynomials, equations, inequalities) and trigonometry, the successful student must know the content of the fundamental notions studied in the course of Geometry Syllabus: http://www.dmmm.uniroma1.it/~stefano.capparelli/didattica/Geometria%2016-17/Diario%20delle%20lezioni%2016-17.htm as well as a good working knowledge of the content of a first course in mathematical analysis: http://www.sbai.uniroma1.it/~daniela.sforza/analisi_17-18/DIARIO_A1_17-18.pdf

If a student follows lectures regularly then itis enough to study on my class notes Lectures on Discrete Math, Esculapio ed. 2025, (Italian Version: Lezioni di Matematica Discreta (Esculapio ed. 2025).

The course is presented via traditional classroom lectures containing a suitable amount of motivation and new material, as well as the necessary examples and exercises. Both new material and exercises are presented together.

Attendance is optional

The final written examination will require the solving of a suitable number of exercises concerning material studied in class, but it will also have some problems aimed at testing the problem solving capability of the student.

a. Baldoni, Ciliberto, Piacentini Cattaneo: Aritmetica, Crittografia e Codici, Springer 2006 b. Biggs, Discrete Mathematics, Oxford, 2002 c. Brualdi, Introductory Combinatorics, Prentice Hall, 1999. d. Cerasoli, Eugeni, Protasi, Elementi di Matematica Discreta, Zanichelli 1988 e. Knuth, The art of Computer Programming, Vol. I Addison Wesley, 1997 f. Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley 1988 g. Schroeder, Number Theory in Science and Communication, Springer 2009

The course is presented via traditional classroom lectures containing a suitable amount of motivation and new material, as well as the necessary examples and exercises. Both new material and exercises are presented together.