Prerequisites
None.
Objectives
Develop rigorous mathematical reasoning. Master the mathematical concepts and tools for algorithm and procedure analysis, focusing both on correctness and efficiency.
Program
Mathematical induction. Elementar number theory. Euclides and Saunderson algorithms. Fermat's little theorem. Chinese remainder theorem. Polynomials. Discrete Fourier Transform (DFT) and its efficient computation (FFT). Applications to RSA cryptography. Closed forms of infinite sums. Generating functions. Solution of finite difference linear equations. Graphs, subgraphs, cycles and circuits. Digraphs and networks. Planar graphs. Graph coloring. Deterministic and non-deterministic finite automata; regular languages, regular expressions and regular grammars. Pushdown automata. Context-free languages and grammars. Pumping lemmas. Programme correction. Hoare's calculus of partial and total correction of imperative programmes. Total correction of search and sorting algorithms.
Evaluation Methodology
Exam/tests, possibly with minimum grade, complemented with continuous evaluation components.
Cross-Competence Component
The UC allows the development of transversal competences on Critical Thinking, Creativity and Problem Solving Strategies, in class, in autonomous work and in the several evaluation components. The percentage of the final grade associated with these competences should be around 15%.
Laboratorial Component
Not applicable.
Programming and Computing Component
Not applicable.
More information at: https://fenix.tecnico.ulisboa.pt/cursos/lerc/disciplina-curricular/845953938490003
