Algoritmos
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2018/2019 - 1S
Ciclos de Estudo/Cursos
Língua de trabalho
Inglês
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 a 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
- Fundamentos de provas de correção e de análise assintótica
- Dividir-para-conquistar e resolução de recorrências
- Análise amortizada
- Análise probabilística e algoritmos aleatorizados
- Ordenação e seleção lineares
- Algoritmos ávidos/gulosos e programação dinâmica
- Algoritmos para deteção de ocorrências de strings
- 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
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/)
Steven Halim and Felix Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (https://sites.google.com/site/stevenhalim/)
Métodos de ensino e atividades de aprendizagem
Aulas teórico-práticas; trabalhos de casa escritos e individuais; trabalhos de casa para apresentação oral em grupo; 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 trabalhos de casa escritos destinam-se à aplicação dos conceitos na prática, permitindo consolidar o conhecimento adquirido. Os trabalhos de casa orais complementam os escritos e permitem introduzir problemas mais abertos, onde as respostas não são triviais, fomentando a discussão interativa das ferramentas intelectuais usadas com recurso ao quadro para a explicação das ideias usadas.
O exame final, 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 |
Prova oral |
15,00 |
Trabalho escrito |
15,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Apresentação/discussão de um trabalho científico |
|
Estudo autónomo |
|
Frequência das aulas |
|
Trabalho escrito |
|
Total: |
0,00 |
Obtenção de frequência
Entregar no mínimo um trabalho de casa escrito e apresentar no mínimo um trabalho de casa oral.
Fórmula de cálculo da classificação final
- (H) Trabalho de casa escrito + oral: 2 trabalhos de casa escritos para serem resolvidos individualmente e submetidos electronicamente + 2 trabalhos de casa para serem apresentados oralmente. O peso de H na nota final é de 30%.
- (E) Exame final: 70% da nota final
- (T) Testes: dois testes, T1 e T2, vão ser oferecidos durante o semestre (um a meio, outro perto do final). Os alunos podem usá-los para obterem dispensa do exame final. T = 0.5*T1 + 0.5*T2
Classificação da época normal: C = max(E,T)*0.7 + H*0.3 >= 9.5
Classificação da época de recurso: C = E*0.7 + H*0.3 >= 9.5