Algoritmos

Código:

CC4010

Sigla:

CC4010

Nível:

400

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2021/2022 - 1S

Ativa?	Sim
Página Web:	https://www.dcc.fc.up.pt/~apt/Aulas/ALGO2122.html
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
M:CC	37	PE a partir do ano letivo de 2014	1	-	6	42	162

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

- Fundamentos 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
- Fundamentos da teoria da complexidade computacional e problemas NP-completos
- Introdução aos algoritmos de aproximação e algoritmos parametrizados
- Aplicações e alguns algoritmos clássicos  (exemplos: algoritmos em grafos; deteção de ocorrências de strings; algoritmos geométricos)

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; trabalhos de casa (podendo incluir exercícios e leitura de artigos) e apresentação oral pelos estudantes; teste intermédio escrito  (obrigatório) 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 e artigos 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	20,00
Prova oral	5,00
Trabalho prático ou de projeto	5,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

• (Tc) Exercícios (com apresentação oral) 10%


• (Ti) Teste intermédio 20% (durante o semestre).


• (E) Exame final: 70% (pode ser substituído por Tf)


•  (Tf) Dependendo da evolução da pandemia por Covid'19, poderá ser realizado um teste facultativo (em Dezembro) para dispensa de exame final. Necessário Tf >= 8.

Classificação da época normal: C = max(E,Tf)*0.7+ Ti*0.2 + Tc*0.1 >= 9.5

Classificação da época de recurso: C = max(E*0.7+Ti*0.2+Tc*0.1,E*0.9+Tc*0.1) >= 9.5

Necessário E >= 8.

Melhoria de classificação

Por exame final (na época de recurso)