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.
1. Combinatorics 2. Number theory 3. Recurrences 4. Graph theory
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.
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.
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.
E-learning.
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%).
