Discrete Structures

Recommended Prerequisites

Secondary School Mathematics

Teaching Methods

Classes are of theoretical and theoretical-practical type. The teaching methods in the theoretical classes are predominantly expository. In the practical classes, problems will be solved under the guidance of the teacher.

The strong interaction between concepts and their practical application must be discussed, giving as much as possible a central role in the visualization and analysis of particular situations before making a progressive abstraction of the concepts.

When possible,

Learning Outcomes

A discrete mathematics course has several objectives. Students should learn a particular set of mathematical facts and how to apply them, but more importantly, learn how to think mathematically. To achieve these goals, the course emphasizes mathematical reasoning and different ways to approach and solve problems.
One will discuss topics ranging from logic to algebra, probability theory and graph theory, through a linkage between theory and practice: whenever possible we will try to complement theory with the exploration and experimentation of the computational math concepts.

The course aims at developing the following instrumental skills: analysis and synthesis, organization and planning, oral and written communication, problem-solving skills and computational ability. On the personal and systemic levels it also allows to develop self-learning skills and independent thinking. The transformation of concepts into working tools will be achieved by encouraging personal work.

Work Placement(s)

No

Syllabus

1. Basics.
1.1. How to reason? Propositional logic.
1.2. Mathematical reasoning, induction and recursion.
1.3. Algorithms and complexity.
2. Graph Theory.
2.1. Graphs.
2.2. Trees.
3. The integers. Cryptography.
4. Counting.
4.1. Basic techniques and discrete probability.
4.2. Advanced Techniques.

Head Lecturer(s)

Jorge Manuel Senos da Fonseca Picado

Assessment Methods

Assessment
There are two types of grading: during the semester and by final exam. The first includes tests or/and one or more mid-term exams and may include presentations, as well as the solving of problems proposed in the form of homework sets. The later consists of a single exam at the end of the semester. - Problem solving [0-50%] - Tests [0-50%] - Midterm exams [0-100%] - Exam [0-100%]: 100.0%

Bibliography

Jorge Picado, Estruturas Discretas: textos de apoio, DMUC, 2008.
Kenneth Rosen, Discrete Mathematics and its Applications, MacGraw-Hill, 5a Edição, 2002.
James Hein, Discrete Structures, Logic and Computability, Portland State University, 2002.
Jon Barwise e John Etchemendy, Language, Proof and Logic, CSLI Publications, 1999.
Carlos André e Fernando Ferreira, Matemática Finita, Universidade Aberta, 2000.