Laboratórios de Programação Avançada

Conhecimentos de Base Recomendados

Conhecimentos básicos de algoritmia, 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, Estruturas Discretas).

Métodos de Ensino

As aulas teóricas destinam-se à 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 individual pelos estudantes dos problemas propostos, para acompanhamento do projeto e para a defesa oral.

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:
1) Análise e síntese, resolução de problemas
2) Raciocínio crítico
3 )Aprendizagem autónoma, aplicação dos conhecimentos teóricos na prática

As competências secundárias são:
1) Capacidade de decisão
2) Competência em trabalho em grupo
3) Criatividade e adaptabilidade a novas situações.

Estágio(s)

Não

Programa

1. Introdução  
   1. Modelação e resolução de problemas
   2. Complexidade computacional
   3. Paradigmas algorítmicos
      1. Procura recursiva
      2. Backtracking
      3. Programação dinâmica
      4. Procura gulosa
      5. Branch-and-bound
      6. Casos de aplicação
         1. Grafos
         2. Redes de fluxo
         3. Geometria computacional

(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
1) Resolução individual do problema; 2) Provas a realizar em grupo; 3) Projeto; 4) Defesa oral, individual, das classificações.: 100.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.
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani,  Algorithms (draft)
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