Discrete Mathematics

Discrete Mathematics

Cod: 21082

Department: DCET

Department: DCET

ECTS: 6

Scientific area: Mathematics

Scientific area: Mathematics

Total working hours: 156

Total contact time: 26

Total contact time: 26

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

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.

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.

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.

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.

No pre-requisites are required