Course: 2023/2024

Discrete Mathematics

(15971)

Requirements (Subjects that are assumed to be known)

Calculus (First year / First semester)
Linear Algebra (First year / First semester)

Learning outcomes:
RA1.2. Knowledge and understanding of engineering disciplines underlying their specialisation, at a level necessary to achieve the other programme outcomes, including some awareness at their Forefront.
RA1.3. Awareness of the wider multidisciplinary context of engineering.
RA7.1. Ability to communicate effectively information, ideas, problems and solutions with engineering community and society at large.
Basic and general competences:
CB1. Students have demonstrated possession and understanding of knowledge in an area of study that builds on the foundation of general secondary education, and is usually at a level that, while relying on advanced textbooks, also includes some aspects that involve knowledge from the cutting edge of their field of study.
CGB3. Ability to understand and master the basic concepts of discrete mathematics, logic, algorithmic and computational complexity, and their application to the resolution of engineering problems.
CGO12. Knowledge and application of basic elements of economics and human resources management, organisation and planning of projects, as well as legislation, regulation and standardisation in the field of computer projects, in accordance with the knowledge acquired.
Objectives:
1. To know and apply sets, algebraic structures, and binary relations.
2. To set out and solve combinatorial problems by using basic counting methods, or more advanced ones like recurrences and generating functions.
3. To know and apply graph theory to real-life problems.

Skills and learning outcomes

Description of contents: programme

1. Elementary set theory. Definitions. Set operations and their algebraic properties. Subsets. Power set. Cartesian product. Functions. Functions types.
2. Elementary combinatorics. Set cardinality. Elementary counting techniques. Binomial coefficients.
3. Advanced combinatorics. Recurrence relations. Generating functions.
4. Introduction to graph theory. Generalities. Adjacency matrix. Graph isomorphism. Walks on graphs. Graph connectivity. Trees. Planar graphs. Euler formula
5. Graph-theoretic algorithms. Weighted graphs. Directed graphs. Minimum-weight spanning tree. Shortest-distance path between two vertices. Proper colorings of graphs. Eulerian and Hamiltonian graphs. Combinatorial problems in graphtheory: proper colorings, matchings, etc.
6. Equivalence relations and their application to modular arithmetic. Binary relations. Equivalence relations and partitions. Equivalence classes. Quotient set. Integer and modular arithmetic. Diophantine equations. Euler theorem.
6. Order relations and mathematical induction. Partially ordered sets. Hasse diagrams. Extremal elements. Totally ordered sets. Well-ordered sets and mathematical induction. Lexicographic order. Topological order.
7. Lattices. Bounded, modular, and distributive lattices. Complementary lattices. Boolean algebras.

Learning activities and methodology

* Theoretical-practical classes: 2 ECTS. Concepts and knowledge to be acquired are presented in these sessions. Students are provided with lecture notes and can find basic reference bibliography to facilitate class understanding and posterior personal work. Exercises are solved by students for self-assessment and achievement of necessary skill. During the practical sessions, students are presented with exercises that are discussed and solved.
* Individual and group work: 2.5 ECTS. Students' personal work.
* Continuous assessments. 1 ECTS. Knowledge, skills and abilities, gradually acquired, are globally assessed. They serve as self-assessment of progress to adapt learning strategies if necessary.
* Tutoring sessions. Sessions to clarify theoretical or practical issues encountered by students on an individual or in-group basis.
* Final exam: 0.5 ECTS. Knowledge, skills and abilities acquired over the course of the academic semester are globally assessed.

Assessment System

- % end-of-term-examination 60
- % of continuous assessment (assigments, laboratory, practicals...) 40

Basic Bibliography

- F. García Merayo. Matemática Discreta. Paraninfo. 2015
- J. Matousek and J. Nesetril. Invitation to Discrete Mathematics. Oxford. 2004
- K.H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill. 7th edition, 2012

Additional Bibliography

- N.L. Biggs. Discrete Mathematics. Oxford University Press. 2002
- R.P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. 2003

The course syllabus may change due academic events or other reasons.