Discrete mathematics is the branch of mathematics with a more direct relationship with the theory of computation; In fact, its great development in the last century is due in large part to the onset of computer science.
The course introduces several interrelated subjects - logic, arithmetic, combinatorics and graph theory -, which are the basis of discrete mathematics. The presentation of the topics will emphasize the algorithmic and computational aspects.
Teachers
Person in charge
Anna De Mier Vinué (
)
Others
Guillem Perarnau Llobet (
)
Marc Noy Serrano (
)
Tassio Naia Dos (
)
Xavier Povill Clarós (
)
Weekly hours
Theory
3
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
7.5
Competences
Technical Competences
Technical competencies
CE1 - Skillfully use mathematical concepts and methods that underlie the problems of science and data engineering.
Transversal Competences
Transversals
CT5 - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
CT6 [Avaluable] - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
Basic
CB1 - That students have demonstrated to possess and understand knowledge in an area of ??study that starts from the base of general secondary education, and is usually found at a level that, although supported by advanced textbooks, also includes some aspects that imply Knowledge from the vanguard of their field of study.
Generic Technical Competences
Generic
CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.
Objectives
To know the language of mathematical logic
Related competences:
CE1,
CT6,
CB1,
To understand basic arithmetic of integers and polynomials, specially the computational aspects
Related competences:
CE1,
CG5,
To know the basic results of enumerative combinatorics
Related competences:
CE1,
CG5,
To know the basics of graph theory, with emphasis on algorithmic problems
Related competences:
CE1,
CT5,
CG5,
Contents
Sets and proofs
The language of set theory. Demonstrations in mathematics. The induction method.
Propositional and predicate calculus
Boolean formulas. Assignment and truth tables. Satisfiability. First-order logic.
Arithmetics of integers and polynomials
Divisibility of integers. Maximum common divisor. Congruences Divisibility and congruence of polynomials. Roots and factorization.
Basic enumeration and recurrences
Permutations, sets, and multisets. Binomial numbers. The principle of inclusion and exclusion. Recurrence equations. Resolution of linear recurrence equations.
Graphs and trees
Basic concepts of graph theory. Distances and connectivity. Walks and graph exploring . Trees and spanning trees. Colouring. Planarity.
In the theory classes the subject is exposed, complementing it with examples and applications. in the problem sessions we'll discuss problems from a list, encouraging the active participation of students.
Evaluation methodology
There will be a midterm exam (EP) about the first half of the course and a final exam (EF) about the second half. Optionally, on the day of the final exam it will be possible to resit the midterm exam (REC). If this exam is submitted, it will replace the grade EF.
The final grade is computed as follows:
-If the resit exam is not submitted, the final grade will be NF=0.5·EP+0.5·EF.
-If the resit exam is submitted, the final grade will be NF=0.5·REC+0.5·EF.
There will be a re-evaluation exam (REAV) for those students with NF<5. In this case, the final grade for the course will be max(NF, REAV).