Description

Theory
1

Theory/Practice
3

Instructors

Ana Moura

Contents

P1. Mathematical Language and Logic (25%)
P1.1 Basics of Set Theory.
P1.2 Propositional Logic.
- Logical operators and properties;
- Propositional equivalence.
P1.3 Predicate logic. Quantifiers.
P1.4 Binary relations.
- Order relations;
- Equivalence relations.
P2. Graphs (30%)
P2.1 Basic concepts.
P2.2 Walks.
- Counting the number of walks;
- Eulerian trails. Fleury´s algorithm.
P2.3 Weighted graphs. Dijkstra?s algorithm.
P2.4 Minimum-cost spanning trees. Kruskal´s algorithm.
P3. Introduction to Proof Strategy (15%)
P3.1 Rules of inference.
P3.2 Mathematical induction.
P4. Analysis of Algorithms (30%)
P4.1 The concept.
P4.2 Complexity of algorithms.
- The asymptotic behaviour of functions: the notation big-O;
- Time complexity of some algorithms;
- Complexity classes.
P4.3 Complexity of problems.

Learning Outcomes

By the end of this course, the student must be able to:
CO1: Use mathematical logic to prove equivalence of propositions and validity of arguments;
CO2: Solve simple binary relations problems;
CO3: Use proof strategies, in particular, the induction method;
CO4: Apply some graph search algorithms to specific problems in the area of Engineering;
CO5: Describe the concept of efficiency of an algorithm;
CO6: Analyse and compare the time complexity of algorithms;
CO7: Apply the previous skills to specific problems in the engineering field.