Estratégias Algorítmicas - Unidade Curricular - Universidade de Coimbra
Unidade Curricular / Estratégias Algorítmicas
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).
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.
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
Aprendizagem autónoma, aplicação dos conhecimentos teóricos na prática
As competências secundárias são:
Criatividade e adaptabilidade a novas situações.
▪ 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.
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