6 ECTS; 1º Ano, 2º Semestre, 28,0 T + 28,0 TP + 5,0 OT , Cód. 814354.
Lecturer
- Maria Manuela Morgado Fernandes Oliveira (1)(2)
(1) Lead Professor
(2) Teaching Professor
Prerequisites
Not applicable.
Objectives
Successful completion of this course will enable the student to:
a) Understand the fundamental concepts of finite mathematics and binary relations.
b) Apply equivalence and order relations in the modeling of computational problems.
c) Understand and apply basic concepts of number theory, including divisibility and modular arithmetic.
d) Analyze sequences and recurrence relations in the context of algorithms.
e) Use the principle of mathematical induction to prove properties of algorithms and recursive structures.
f) Understand and apply fundamental concepts of graph theory, including connectivity, planarity, coloring, and trees, in solving problems in
computer science and artificial intelligence
Program
1. Finite Mathematics
Set Theory: concepts and notation; finite and infinite sets; operations; Cartesian product.
Binary Relations: definition and properties; equivalence and order relations; partitions.
2. Number Theory
Divisibility: concepts; factorization; GCD and LCM; Euclidean algorithm.
Congruences: modular arithmetic; properties and operations.
3. Sequences and Induction
Sequences: definition; recurrence sequences.
Recurrence: relations; complexity analysis.
Mathematical Induction: principle; simple and strong induction; applications to algorithms and recursive structures.
4. Graphs
Terminology: simple, directed, weighted graphs.
Connectivity: connected graphs; paths and cycles; Eulerian and Hamiltonian graphs.
Planarity and Coloring: planar graphs; Eulers formula; coloring and chromatic number.
Trees: definition and properties; rooted, binary, and minimum spanning trees.
Evaluation Methodology
Assessment by frequency: two written works, two classroom presentations and three written tests, all classified from 0 to 20 points. A student
is exempt from the exam if he/she submitted both works, made the presentations, had a classification higher than 4 points in each test and
the sum of 50% of the average of the works and presentations and 50% of the average of the tests is equal to or greater than 10 values.
Assessment by exam: a written test, graded from 0 to 20 points, on the entire subject. The student is approved if he obtains at least 10 points in the exam.
A student who obtains a classification higher than 17 may have to take an extraordinary assessment. If the student does not do so, they will be awarded 17 points.
Bibliography
- Fortney, J. (2021). Discrete Mathematics for Computer Science: An Example-Based Introduction. London ; New York;: Taylor & Francis Ltd
- ORegan,, . (2021). Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications.. Cham, Suíça: Springer
- Rosen, K. (2011). Discrete Mathematics and Its Applications, 7ª edição. New York: McGraw-Hill Education,
Teaching Method
1.Theoretical classes: the fundamental principles are conveyed, and their applications are described and illustrated.
2.Theoreticalpractical classes: solving exercises that explore and apply the concepts.
3.Group discussion.
4.Use of software.
Software used in class
GeoGebra, SageMath, Wolfram Alpha, and Python within a Jupyter Notebook environmente.
