Subject: Discrete Mathematics

Scientific Area:

Mathematics

80 Hours

Number of ECTS:

7,5 ECTS

Language:

Portuguese

# Overall objectives:

1 - Develop modeling, abstraction, calculus and deduction capabilities.
2 - Introduction (or revision) of the basic elementary mathematics that is the basis of the computing foundations and of the analysis of the efficiency of algorithms.

# Syllabus:

1 - Informal introduction to the logical connectives and quantifiers.
2 - Sets: power set, major operations on sets, unions and intersections of generalized sets; sets, "bags" ("multiset") and sequences (lists); Cartesian product of sets.
3 - Relations: n-relations and binary relations; equivalence relations and quotient set; order relations and related concepts, partially and totally ordered sets, well order and well-founded relations.
4 - Functions: (partial) functions and applications, composition of functions, operations and algebraic structures, families of elements of E indexed by I; applications Injective, surjective and bijective and some results.
5 - The problem of the cardinality of a set: equipotent sets, finite and infinite sets, countable and numerable sets; fundamental results and some useful criteria for demonstrating that a set is countable or not (illustration of the diagonal method).
6 - Structures (sets with structure ") and morphisms between structures: the essential idea; morphisms and isomorphisms between relational structures; morphisms and isomorphisms between algebraic structures.
7 - Inductively defined sets and proofs by induction (finite, structural and well-founded).
8 - Sums and series.
9 - Recurrence relations.
10 - Applications in the analysis of the efficiency of algorithms and key notations for describing the behavior (growth) of asymptotic functions.

# Literature/Sources:

R.A. Brualdi , 1999 , Introductory Combinatorics , Prentice Hall
J. Campos Ferreira , 2001 , Elementos de Lógica Matemática e Teoria dos Conjuntos , Dep. de Matemática, Instituto Superior Técnico (ww
R.L. Graham, D.E. Knuth e O. Patashnik , 1994 , Concrete Mathematics , Addison-Wesley
A.J.F. Oliveira , 1982 , Teoria de Conjuntos - Intuitiva e Axiomática (ZFC) , Livraria Escolar Editora
Carmo, J.M.C.L.M. , 2005 , Noções Básicas para a Matemática do Discreto , Universidade da Madeira

# Assesssment methods and criteria:

Classification Type: Quantitativa (0-20)

Evaluation Methodology:
Oral and written presentation of the syllabus contents of the curricular unit. Realization of two frequencies (with a weight of 50% each) to be individually resolved during the normal season. In this way, the student can, throughout the semester, evaluate their performance and change strategies if necessary. At the time of appeal, students can recover the grade of one of the frequencies or, alternatively, the complete exam, that is, they can recover the entire subject.