Algoritmos
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2024/2025 - 1S 
Ciclos de Estudo/Cursos
Docência - Responsabilidades
Língua de trabalho
Português - Suitable for English-speaking students
Objetivos
Esta UC é dedicada ao desenho de algoritmos para problemas computacionais, e como raciocinar de forma clara sobre a sua correção e tempo de execução. O principal objectivo é dotar os alunos das ferramentas intelectuais necessárias para que sejam capazes de desenhar e analisar os seus próprios algoritmos para problemas que precisem de resolver no futuro.
Resultados de aprendizagem e competências
Os alunos deverão ser capazes de compreender a relação entre o desenho de algoritmos, a prova da sua correcção e a análise da sua complexidade. Deverão aprender técnicas gerais úteis na implementação de novos algoritmos e conhecer alguns dos principais algoritmos nalguns domínios específicos. Os alunos irão também obter experiência prática na aplicação de algoritmos genéricos a problemas concretos.
Modo de trabalho
Presencial
Programa
- Correção de algoritmos
- Complexidade: análise de melhores e piores casos
- Fundamentos de análise assimptótica
- Análise de casos médio e algoritmos probabilísticos
- Análise de algoritmos recursivos
- Análise amortizada
- Estruturas de dados - coleções e dicionários
- Fundamentos da teoria da complexidade computacional e problemas NP-completos
Bibliografia Obrigatória
Cormen Thomas H. 070;
Introduction to algorithms. ISBN: 9780262033848 hbk
Bibliografia Complementar
Skiena Steven S.;
The algorithm design manual. ISBN: 978-1-84800-069-8
Steven Halim and Felix Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (https://sites.google.com/site/stevenhalim/)
Sedgewick Robert;
Algorithms. ISBN: 0-201-06673-4
Jon Kleinberg and Éva Tardos; Algorithm Design, 2005. ISBN: 978-0321295354 (http://www.cs.princeton.edu/~wayne/kleinberg-tardos/)
Armando Matos; Tópicos Avançados em Algoritmos, DCC/FCUP, 2008 (Alguns Apontamentos (http://www.dcc.fc.up.pt/~acm/aulas/aa/t1.pdf))
Ana Paula Tomás; Desenho e Análise de Algoritmos – Alguns Apontamentos, DCC/FCUP, 2013 ((Revisões de DAA: http://www.dcc.fc.up.pt/~apt/aulas/DAA/1314/ApontamentosDAA.pdf))
Métodos de ensino e atividades de aprendizagem
Aulas teórico-práticas; teste intermédio escrito e teste para dispensa de exame final; exame final.
As aulas misturam exposição de matéria (introduzindo conceitos, resultados e algoritmos principais) com discussão interativa da sua aplicação na resolução de problemas reais.
Os exercícios destinam-se à aplicação dos conceitos na prática, permitindo consolidar o conhecimento adquirido.
O exame final (e testes escritos), sem consulta, destina-se à avaliação global dos conhecimentos adquiridos.
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Designação |
Peso (%) |
Exame |
70,00 |
Teste |
30,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Estudo autónomo |
120,00 |
Frequência das aulas |
42,00 |
Total: |
162,00 |
Obtenção de frequência
Todos os estudantes serão admitidos a exame.
Fórmula de cálculo da classificação final
- (Ti) Teste intermédio 30% (durante o semestre).
- (Tf) Teste final: 70% (durante a época normal).
- (ER) Exame (duante a época de recurso).
Classificação da época normal: C = Ti*0.3+ Tf*0.7 (>= 9.5)
Classificação da época de recurso: C = ER (>= 9.5)
Necessário Ti >= 6 e Tf >= 6.
Provas e trabalhos especiais
- Data do Teste Intermédio: início de Nov (durante a 1ª aula).
Avaliação especial (TE, DA, ...)
É semelhante à avaliação dos alunos regulares.
Melhoria de classificação
Por exame final, apenas na época de recurso.