Estratégias Algorítmicas

Conhecimentos de Base Recomendados

Conhecimentos básicos de algoritmia, teoria da computação, paradigmas de programação procedimental e orientado a objetos, estruturas de dados e matemática (unidades curriculares de Introdução à Programação e Resolução de Problemas, Algoritmos e Estruturas de Dados, Princípios de Programação Procedimental, Programação Orientada a Objetos, Teoria da Computação e Estruturas Discretas).

Métodos de Ensino

Aulas teóricas:exposição da matéria pelo docente, à discussão de exemplos, à apresentação dos problemas a resolver durante o semestre, e à resolução de problemas de menor complexidade em grupo. As práticas laboratoriais destinam-se a apoiar a resolução dos problemas propostos e de exercícios sobre tópicos de paradigmas algorítmicos, para acompanhamento do projeto e para a defesa oral.Avaliação: 1) Provas escritas e individuais de conhecimento; 2) Provas de programação em grupo; 3) Projetos de programação em grupo; 4) Defesa oral, individual, das classificações. O sistema Mooshak como ferramenta de validação automática nas provas e no projeto de programação. Os casos de teste dos problemas propostos são gerados para testar diversos cenários. Esta abordagem permite ao estudante refinar a sua implementação de modo a torná-la correta e mais eficiente de acordo com a pontuação obtida. O exame permite recuperar unicamente a classificação obtida nas provas escritas de conhecimento.

Resultados de Aprendizagem

Reforçar a capacidade de resolução de problemas através do estudo de paradigmas algorítmicos e da sua aplicação a problemas de diversos domínios. Partindo da descrição verbal de um problema concreto, o estudante deverá ser capaz de, tanto individualmente como em grupo:

• Compreender o problema e relacioná-lo com outros problemas já conhecidos
• Identificar paradigmas algorítmicos adequados à sua resolução
• Conceber algoritmos específicos para a resolução do problema
• Implementar as soluções algorítmicas encontradas de forma modular, recorrendo a estruturas de dados adequadas
• Compreender os limites inerentes à complexidade dos algoritmos implementados

As competências principais desenvolvidas são:

• Análise e síntese, resolução de problemas
• Raciocínio crítico
• Aprendizagem autónoma, aplicação dos conhecimentos teóricos na prática

As competências secundárias são:

• Capacidade de decisão
• Competência em trabalho em grupo

Criatividade e adaptabilidade a novas situações.

Estágio(s)

Não

Programa

1. Introdução  

▪       Modelação e resolução de problemas

▪       Complexidade computacional

2. Paradigmas algorítmicos

▪       Procura recursiva

▪       Backtracking

▪       Programação dinâmica

▪      Procura gulosa

▪       Branch-and-bound

3. Casos de aplicação

▪       Grafos

▪       Redes de fluxo

▪       Geometria computacional

4. (opcional) Outros problemas como por exemplo: numéricos, de emparelhamento, de análise lexical e sintática, de bioinformática, de criptografia, etc.

Docente(s) responsável(eis)

Luís Filipe dos Santos Coelho Paquete

Métodos de Avaliação

Avaliação
Projecto: 20.0%
Exame: 40.0%
Frequência: 40.0%

Bibliografia

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed., 2009.
• S.Skiena and M.Revilla, Progamming Challenges, 2003.
• D. Knuth, The Art of Computer Programming.

• J. Kleinberg, and E. Tardos, Algorithm Design, 2005
• R. Sedgewick and K. Wayne, Algorithms, 4rd ed, 2011

B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner (eds),  Algorithms Unplugged, 2011