Qualification and title awarded – Licenciatura in Computer Science, Licenciado

Regime: S1

2 hours/week - lectures. 2 hours/week – examples classes.

Programa:

Syntax and semantics of classical propositional logic; conjunctive and disjunctive normal forms; natural deduction for classical propositional logic; soundness and completeness theorems. Syntax, Tarski semantics and natural deduction for classical first-order logic. Introduction to intuitionistic propositional logic: Kripke semantics; natural deduction; Godel's interpretation into classical logic.

Métodos de Avaliação:

Periodic assessment (2 written tests) or written final exam.

Pré-requisitos:

Elementary notions of set theory.

Resultados de Aprendizagem:

On successfully completing the course the student should be able to:

Bibliografia:

1. Logic and structure, van Dalen, Springer
2. Language, Proof and Logic, Barwise and Etchemendy, CSLI Publications

Docentes:

Carla Albertina Carvalhinho da Silva Mendes

Regime: S2

2 hours/week - lectures. 1 hours/week – examples classes. 2 hours/week – lab. Session.

Programa:

Propositional logic:  Sequent Calculus, Tableaux, Resolution, Davis-Putnam; BDDs.

First-order Logic: Sequent Calculus; Prenex/Herbrand/Skolen normal forms; Propositional resolution in LPO; Unification; Resolution (first order). Horn clauses and SLD resolution.

Curry-Howard analogy: Term annotations in natural-deduction proof systems; proof equality and normalization; pure typed lambda-calculus and the Curry-Howard analogy.

Logic Programming:  Prolog language; inference and backtracking; Cut predicate; second-order predicates; generate-and-test strategy.

Métodos de Avaliação:

Written exam.

Pré-requisitos:

Elementary notions of Discrete Mathematics and Logic.

Resultados de Aprendizagem:

Exploit efficient methods for validity checking of propositional formulas.

Justify/apply the resolution mechanism as a mean to establish the inconsistency of a first-order theory.

Take advantage of logic programming in (medium-sized) problem solving.

Bibliografia:

Proof Theory and Automated Deduction. Jean Goubault-Larrecq & Ian Mackie , Kluwer Academic Publishers, 1997.

From Logic to Logic Programming. Kees Doets, MIT Press, 1994.

Proofs and Types. Jean-Yves Girard & Yves Lafont & Paul Taylor, Cambridge University Press, 1990.

Docentes:

José Carlos Bacelar Almeida.

Regime: S2

2 hours/week of theorectical lectures; 1 hour/week theorectical-practical and 2 hours/week of practical work.

Programa: Language Processing Introduction: interpreters and compilers; Language processor architecture: lexical analysis, syntactic analysis and semantic analysis; Language and Grammar Comcept; Kinds of Languages and Grammars: Chomsky hierarchy. Regular Languages and Lexical Analysis: concept; Regular language specification with regular expressions; Regular Languages Recognition: automaton concept; Regular Expression to Finite State Automaton Conversion; flex as an automaton generator. Non-regular Languages and Syntactic Analysis: Context Free Grammars and Languages; Parser structure; Top-Down Parsing and LL(1) invariant; LL(1) conflicts and their resolution; Top-Down Parsing; Bottom-UP Parsing: LR(0) automaton, shift/reduce and reduce/reduce conflicts; SLR(1) automaton; LALR(1) automaton; yacc as a Bottom-UP parser generator. Semantic Analysis: abstract syntax tree; concrete grammar and abstract grammar; Intermediate representation.

Métodos de Avaliação:

60% (written mark) + 40% (Lab Project)

Pré-requisitos:

Imperative Programming

Resultados de Aprendizagem:

The student will be able to develop new domain specific languages and associated tools. He will also be able to develop front-ends and back-ends to other software applications.

Basically he will be able to specify and program any transformation from a textual forma tinto another format.

Bibliografia:

Aho , Sethi , Ullman , Compiler Principles, Techniques and Tools , Addison-Wesley , 1986 .

R. G. Crespo , Processadores de Linguagens: da concepção à implementação , IST-Press , 1998 .Pittman , Peters , The Art of Compiler Design: theory and pratice , Prentice-Hall , 1992 .

Docentes:

José Carlos Ramalho

José João Almeida

Regime: S2

Lectures (2h/week), Tutorial(1h/week), Laboratory(2h/week).

Programa:

The Object Oriented Programming Paradigm: Data abstraction and modularity. Objects: structure and behaviour. Messages. Classes, hierarchy and inheritance. Inheritance versus Composition. Abstract Classes. The substitution principle. Dynamic binding. Polymorphism.

Métodos de Avaliação:

Final exam (55%) and group project(45%).

Pré-requisitos:

Previous knowledge of programming and data structures.

Resultados de Aprendizagem:

a) Understand the fundamental concepts of OOP (Objects, Classes, Inheritance, Polymorphism);
b) Understand how OOP concepts map into JAVA constructs;
c) Understand techniques for large scale programming;
d) Design the classes and interfaces needed to implement a given software problem (modelling);
e) Develop medium scale type safe, generic and extensible Java applications.

Bibliografia:

JAVA5 e Programação por Objectos, F. Mário Martins, Editora FCA, Setembro de 2006. - An Introduction to Object Oriented Programming, T. Budd, Addison-Wesley, 2nd Edition, 1997. - Java in a Nutshell, D. Flanagan, O´Reilly & Associates, 3th. Edition, 1999. - Core Java, G. Cornell, C. Horstmann, Prentice-Hall, 1996.

Docentes:

Regime: S2

Lectures, practical exercises.

Programa:

Introduction to operating systems and systems programming. Process management and inter-process communication. Memory management, file systems and device management. Case studies.

Métodos de Avaliação:

Written examinations.

Pré-requisitos:

None.

1. To understand the role of the operating system.

Bibliografia:

Docentes:

Regime: S2

Lectures, Tutorials and Lab Classes.

Theory and lab classes
Programa:

Combinators and equational laws for Functional Programming.

An introduction to theory and method in programming. Reasoning about programs. Compositionality. Program combinators. Programming packages and software components. * Functional programming: motivation and historical background. The Haskell language and libraries. * Function composition. Abstraction and isomorphism. Introduction to the Hindley-Milner type system. Basic data/function combinators and properties (universal, reflection, fusion, absorption, cancellation, functorhood). Algebra of a datatype. Exchange law. McCarthys conditional. * An introduction to inductive regular datatypes. Functor algebras and the «cata-ana-hilo» triology. Polinomial recursion patterns. Case study: sorting algorithms. * Rules for encoding Haskell data definitions in the C programming language. Expressiveness and compatcness of a programming language. * Parametric polymorphism. Generic programming. Type functors. Introduction to polytypism. * Functional programming using monads. `Input/output'. Exceptions. Monad laws.

Written examination and practical assignment.

Individual exam papers + lab assignments
Pré-requisitos:

Basic knowledge of functional programming concepts and data-structures.

Functional Programming
Resultados de Aprendizagem:

To be able to establish simple equational reasonings about functional programs.

This course teaches a constructive method for functional programming based on a selected library of combinators and associated calculus. This introduces students to the Algebra of Programming and pointfree reasoning, as well as to polytypism and genericity.

J.N. Oliveira, An Introduction to Pointfree Programming, DIUM 1999.

[Bir98] R. Bird. Introduction to Functional Programming Using Haskell . Series in Computer Science. Prentice-Hall International, 2nd edition, 1998. C. A. R. Hoare, series editor. [Hu00] P. Hudak. The Haskell School of Expression - Learning Functional Programming Through Multimedia . Cambridge University Press, 1st edition, 2000. ISBN 0-521-64408-9. [Ol99a] J.N. Oliveira. An Introduction to Pointfree Programming. 37p., Departamento de Informática, Universidade do Minho, 1999. [Ol99b] J.N. Oliveira. Recursion in the Pointfree Style. 33p., Departamento de Informática, Universidade do Minho, 1999. [Ol01a] J.N. Oliveira. A Quick Look at Monads, 2001. Departamento de Informática, Universidade do Minho. Chapter of book in preparation. [VB00] J.M. Valença and J.B. Barros. Fundamentos da Computação II: Programação funcional. Universidade Aberta, 2000. ISBN 972-674-318-4, 234 p.

Olga Maria Pacheco

Regime: S1

2 hours/week - lectures; 2 hours/week - aulas tutorials.

Programa:

Turing machines and computable functions. Partial recursive functions. Church’s thesis. Recursive and recursively enumerable languages.

Decidability and semi-decidability. Recursive and recursively enumerable sets. Complexity classes P and NP. NP-complete problems.

Métodos de Avaliação:

Final exam. Individual project during the semester.

Periodic assessment (two written tests) / Written final exam.

Pré-requisitos:

None.

Resultados de Aprendizagem:

To understand the concepts of Turing machine and partial recursive function and to describe in these models computational solutions for simple problems.
To know some of the evidence for Church’s thesis and to recognize its importance.
To apply universal functions in computability arguments and to explain the main ideas underlying the construction of these functions.
To give proofs of undecidability in Computability Theory.
To relate the concepts of decidability and semi-decidability.
To understand the concept of NP-complete problem and to know some examples of this kind of problem.

Bibliografia:

J. Hopcroft e J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
N. Cutland, Computability, Cambridge, 1994.

M. Davis, Computability and Unsolvability, McGraw Hill, 1982.

Docentes:
José Carlos Cruz da Costa
José Carlos Soares Espírito Santo

Regime: S1

Lectures and practical classes.

Programa:

Concurrent systems modeling, concurrency in shared-memory systems (mutual exclusion, deadlocks, semaphores, monitors), concurrency in message-passing systems (channels and ports, synchronous and asynchronous systems, client-server, faults).

Métodos de Avaliação:

Written exam and programming assignment.

Pré-requisitos: None.
Resultados de Aprendizagem:

Model concurrent systems.

Bibliografia:

Principles of Concurrent and Distributed Programming: Algorithms and Models, M. Ben-Ari, Prentice-Hall, 2006;

Java Concurrency in Practice, Brian Goetz, Tim Peierls, Joshua Bloch, Addison Wesley, 2006

Programming Erlang, Joe Armstrong, OReilly, 2007
Docentes:
Paulo Sérgio Soares Almeida

Regime: S1.  

Regime: S1

Theoretical and practical classes.

Programa:

Affine and euclidian spaces. Geometrical tranformations. Curves and surfaces.

Métodos de Avaliação:

Individual resolution of exercises and written examination.

Pré-requisitos:

Basics notions of linear algebra.

Resultados de Aprendizagem:

By the end of the course the student should be able to:

- solve incidence and metric problems;

-identify simple geometrical transformations and analise their properties;

- describe differential structures on simples curves and surfaces;

- apply basics notions of projective geometry to solve practical problems.

Bibliografia:

• 
  “Geometry and its Applications”, W. Meyer, Harcout Academic Press (1999);
  
• 
  “Mathematics for 3D Game Programming and Computer Graphics”, E. Lengyel, Charles River Media (2002);
  

Regime: S1

Lectures (2 hours/week) and problem solving sessions in a computing lab, with MATLAB (3 hours/week) The problems to be solved are proposed to the students with 1 or 2 weeks in advance.

Programa:

Numerical errors and stability of algorithms. Polynomial interpolation. Numerical quadrature (Newton Cotes’ methods). Non-linear equations. Simultaneous linear equations (direct methods only).

Métodos de Avaliação:

Problem solving in the computing lab during the semester (about every two weeks).

Pré-requisitos:

Linear Algebra, functions of several variables, programming skills.

Resultados de Aprendizagem:

1. To analyse, in simple cases, the numerical erros produced in floating point arithmetic. – 2. To solve problems using methods on polynomial interpolation, numerical quadrature, non-linear equations, simultaneous linear equations. – 3. To evaluate algorithms in terms of their efficiency and numerical stability. – 4. To develop MATLAB codes for the studied methods. – 5. To select MATLAB’s routines to solve problems and discuss the results obtained. -6. To explain the numerical errors in the results in terms of the conditioning of the problem and the stability of the algorithm used.

Bibliografia:

1-Cálculo Científico com Matlab e Octave, A. Quarteroni, F. Saleri, Springer-Verlag Itália, 2006; 2-Métodos Numéricos, Heitor Pina, McGraw-Hill de Portugal, 1995.

Docentes:

Rui Ralha

Regime: S2

Theoretical a practical classes.

Programa:

Primitive roots and indexes, application to the study of some kinds of congruences. Distribution of primes, prime number theorem. Primality and pseudo-primality testing. Algoritms for prime numbers generation. The RSA cypher. Quadradic residues, quadratic reciprocity law. Rational fractions, Pell's equations. Factorization algoritms (Fermat, Pollard, via continued fractions, etc.). Representation of integers as a sum of squares. Gaussian integers and primes.

Métodos de Avaliação:

Written examination.

Pré-requisitos:

Basic number theory as in Discrete Mathematics.

Resultados de Aprendizagem:

Study some kinds of non-linear congruences.

Bibliografia:

David M. Burton, Elementary Number, Wm. C. Brown, 1989.
Kenneth Rosen, Elementary Number Theory and its applications, Longman, 2000.
Song Y. Yan, Number Theory for Computing, Springer, 2002.

Docentes:

Regime: S2