DISCRETE MATHEMATICS
Code: 21082
ECTS: 6
Departament: Department of Sciences and Technology
Field of Study: Mathematics
Keywords:
1. Combinatorics
2. Number theory
3. Recurrences
4. Graph theory
Teacher:
Maria João Oliveira
Área Científica: Mathematics.
E-mail: oliveira@uab.pt

Course Description:
In this curricular unit are introduced the basic concepts and techniques of enumerative combinatorial, elementary theory of numbers and linear recursions. This course ends with a brief introduction to graph theory and some of its applications.

Competences:
At the end of this course students are expected to able to:
Understand the basic notions and techniques of combinatorics;
Understand the basic notions and techniques of elementary number theory
Solve linear recursions;
Understand the basic notions and techniques of graph theory.

Contents:
Introduction to combinatorics: basic countings problems; the pigeonhole principle, the inclusion-exclusion principle; arrangements, permutations and combinations; the binomial theorem and the Pascal triangle; properties of the binomial coefficients.
Elementary number theory: divisibility, divisibility algorithm, maximum common divisor, Euclides algorithm, minimum common divisor; prime numbers, the fundamental theorem of arithmetic; congruence relation for integer numbers and modular arithmetic; applications to coding and criptography.
Introduction to linear recurrences: Fibonacci numbers; linear recurrence relations.
Graphs: Basic properties of non-direct graphs; connectedness; paths and cycles; Eulerian and Hamiltonian paths; trees; coloring of vertexes of a graph; planar graphs; Euler theorem.

Bibliography:
Course materials will be provided online

Complementary Bibliography:
C. André; F. Ferreira, Matemática Finita, Universidade Aberta, 2000. ISBN: 972-674-305-2.
D. M. Cardoso; J. Szymanski; M. Rostami, Matemática Discreta: Combinatória, Teoria de Grafos e Algoritmos, Escolar Editora, 2008. ISBN: 978-972-592-237-8.
N. L. Biggs, Discrete Mathematics, Oxford University Press, 2nd Ed. 2007.

Format:
E-learning.