Algebra and Geometry
No prerequisites needed.
Knowledge and understanding
The course aims to provide basic knowledge of elementary topics of discrete mathematics, such as sets, functions, equivalence relations, and algebraic structures, and of linear algebra and linear systems and matrices, as well as hints of analytic geometry. Such knowledge, that is part of the cultural baggage of a student of a scientific degree, is intended to improve the attitude towards the abstraction and the symbolic representation. The course will place side by side the more theoretical and methodological aspects of mathematics, with the more technical aspects that allow the resolution of exercises that make mathematics a useful tool for various application areas.
During the course, emphasis will be given to examples related to computer applications and especially algorithmic. In particular, we emphasize aspects related to the understanding of the properties of natural numbers such as recursion and induction. An important part of the course will be devoted to solving exercises, always emphasizing that in order to solve an exercise, the total understanding of the topic is needed.
Making judgments and communication skills
The expected learning outcomes include not only knowledge of the terms and technical results, but also the ability to deal with a mathematical argumentation, getting able to distinguish premises and conclusions. In this perspective, the technical language of the student will have to expand in order to express abstract mathematical concepts.
Evaluation procedure
The exam consists of a written test centered on the resolution of the exercises related to the topics covered in the course, followed by an oral exam in which, in addition to possibly supplement and correct the exercises of the written test, the student must show the proper understanding of the course content, through the exposure of demonstrations of two theorems (chosen by the student) studied in the course. To gain access to the oral examination the student must pass the written test. The oral exam can also be given in a session different from the written test. Examples of past written tests can be found at the e-learning web page.
The assignment of the final grade will be determined by an overall evaluation of the written test and the oral exam.
In the middle and at the end of the course the student can give written tests “in itenere”, which (if passed both) shall serve as the written part of the examination and allow access to the oral exam.
• Theorems and methods of proof: implication, proofs by contradiction. Quantifiers and negation. Induction principle, examples and exercises. (4h)
• Sets, elements of a set, inclusion, subsets, power set of a set, cardinality of a finite set, Venn diagrams. Operations between sets: union, intersection and complement. Pairs and Cartesian product. Counting the elements of finite sets. (4h)
• Relationships, binary relations, properties. Equivalence relations, equivalence classes, quotient set. Partitions, fundamental theorem of equivalence relations. Order relations, examples: divisibility of integer numbers, prefixes, inclusions between sets. Not comparable elements. Maximum and minimum. Infimum and supremum. (6h)
• Functions, domain and range, image and preimage. Injective, surjective and biettive functions. Inverse of a bijective function. Composition of functions. (4h)
• Elements of combinatorics: permutations with repetition, factorial, binomial coefficient. Arrangements and combinations, counting functions and injective functions. (6h)
• Euclidean algorithm for computing gcd, prime numbers, fundamental theorem of arithmetic (with proof), the theorem on the existence of infinitely many primes (with proof). (4h)
• Binary and n-ary systems. Relation of congruence modulo n. Solving linear congruences. Set of classes modulo n. (6h)
• Operations on a set, commutativity and associativity, neutral element and invertible elements. Invertible elements in Zm, Euler function. (4h)
• Monoids and groups. Numerical and not numerical examples (monoid of words, the permutation group). Definition of subgroup. Example of the group of square matrices of order 2, with determinant different from zero. Subgroups, equivalence relation determined by a subgroup, right side, Lagrange's theorem. (4h)
• Rings, examples (ring of integers modulo n ring of matrices over R, ring of polynomials). Fields, examples (the field of real, complex field). (4h)
• Matrices over a field, operations between matrices. Determinant and rank (method of Laplace and Sarrus, Kronecker method for rank). Inverse of a matrix. Reduction in triangular shape. (4h)
• Systems of linear equations (homogeneous and non-homogeneous): Gauss-Jordan method. Rouchè-Capelli theorem, Cramer theorem. (8h)
• Definition and examples of vector space. Subspaces. Linearly independent set. Subspaces. Solution space of a homogeneous system. Basis and dimension of a vector space. Dimension of a subspace. (4h)
• Linear matrix associated with a linear map. Kernel and image of a linear map. Rank-nullity theorem. (6h)
• Eigenvalues and eigenvectors, geometric and algebraic multiplicity of an eigenvalue, bases formed by eigenvectors. (4h)
• Introduzione alla Matematica Discreta, di M Bianchi e A. Gillio, McGraw-Hill.
• Elementi di Matematica Discreta e Algebra Lineare di F. Dalla Volta e M. Rigoli, Pearson Education, 2007.
Exercises on the E-learning web-site