Departamento de Informática (UM)

Laboratório de Algoritmia II

9696 [8504P1]

Licenciatura em Ciências da Computação [CCOM]

S4

Manuel Alcino Pereira Cunha

Objetivos

Esta unidade curricular ocorre no 2º semestre do 2º ano, tendo os alunos já aprendido diferentes linguagens de programação e obtido conhecimentos gerais de algoritmos e complexidade. Esta UC pretende complementar e solidificar estes conhecimentos, introduzindo diferentes estratégias genéricas de resolução algorítmica de problemas, ilustradas por uma série de problemas / puzzles clássicos que capturam a essência universal de cada estratégia. Pretende-se que após esta UC os alunos sejam capazes de rapidamente identificar e implementar a estratégia algorítmica mais adequada à resolução de um dado problema.

Programa

- Estratégias algorítmicas genéricas para resolução de problemas: pesquisa exaustiva, programação dinâmica, algoritmos de grafos, etc.
- Problemas / puzzles clássicos que podem ser resolvidos por cada uma dessas estratégias.
- Implementação eficiente dessas estratégias em linguagens de programação de alto nível (Python, C++, Haskell).

Bibliografia

Backhouse, R. (2011). Algorithmic Problem Solving. John Wiley and Sons.

Levitin, A., Levitin, M. (2012). Algorithmic Puzzles. Oxford University Press.

Arefin, A. S. (2006). Art of Programming Contest. Gyankosh Prokashoni.

Resultados da aprendizagem

- Reconhecer qual a estratégia algorítmica mais adequada à resolução de um determinado problema;
- Implementar essa estratégia de forma eficiente numa linguagem de programação de alto nível;
- Organizar o trabalho em grupo por forma a resolver um determinado problema num tempo limitado.
Pré-requisitos recomendados
- Programação Imperativa.
- Algoritmos e Complexidade.

Método de avaliação

A avaliação é feita em 5 torneios de programação ao longo do semestre, onde os alunos se organizam em grupos de 2 alunos para tentar resolver 2 problemas sobre uma determinada estratégia de resolução algorítmica, num período de tempo limitado. A nota final da UC é proporcional ao número de problemas resolvidos ao longo do semestre.

Funcionamento

Turno: PL 1; Docente: Manuel Alcino Pereira Cunha; Dep.: DI; Horas: 30.
Turno: PL 2; Docente: José Bernardo Santos Monteiro Vieira Barros; Dep.: DI; Horas: 30.