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.


Workload (hours): 156
Contact Hours: 26

Assessment:
Continuous assessment is privileged: 2 or 3 digital written documents (e-folios) during the semester (40%) and a presence-based final exam (p-folio) in the end of the semester (60%). In due time, students can alternatively choose to perform one final presence-based exam (100%).


Comments:
No pre-requisites are required


Language(s) of Instruction: Portuguese.

Contact for virtual mobility students: Communication and International Relations Office – gcri@uab.pt