Tópicos Avançados em Algoritmos

Código:

CC4020

Sigla:

CC4020

Nível:

400

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

Ocorrência: 2020/2021 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/taa2021/
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	19	PE a partir do ano letivo de 2014	1	-	6	42	162
M:ENM	1	Plano de Estudos do M:Engenharia Matemática_2013-2014	1	-	6	42	162
			2
MI:ERS	1	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Reforçar conhecimentos de técnicas de concepção de algoritmos e análise da sua correção e complexidade.
Conhecer e aplicar métodos de resolução exata e aproximada para problemas difíceis.

Resultados de aprendizagem e competências

Conhecer alguns dos principais algoritmos e estruturas de dados para resolução de problemas específicos com utilidade prática.
Desenvolver capacidades para aferir a dificuldade computacional de problemas concretos e identificar problemas computacionalmente difíceis.

Modo de trabalho

Presencial

Programa

- Estruturas de Dados Avançadas
 . Árvores binárias de pesquisa (árvores AVL e Red-Black)
 . Estruturas de dados com auto-ajustamento (splay trees e análise amortizada)
 . Estruturas de dados probabilísticas (treaps, skip lists, bloom filters)
 . Estruturas de dados espaciais (quadtrees e variantes, kd-trees, range trees)
 . Estruturas de dados 1D (sparse tables, segment trees, fenwick trees)

- Problemas computacionais e suas soluções eficientes
 . LCA (Lowest Common Ancestor) eRMQ (Range Minimum Query)
 . String Matching (KMP, Boyer-Moore, Rabin-Karp)

- Técnicas Algorítmicas
 . Lazy Propagation
 . Fractional Cascading

- Heurísticas e Metaheurísticas
 . A classe de problemas NP-hard
 . Heurísticas e aproximabilidade para alguns poblemas
 . Metaheurísticas: construção e métodos para melhoria
 . Pesquisa tabu
 . Metaheurísticas baseadas em populações

- Algoritmos de pesquisa em árvore
 . Formulação de problemas de optimização
 . "Branch and bound" para problemas gerais de optimização inteira
 . Limites para problemas selecionados
 . Branch and bound condicionado ao tempo
 . Heurísticas e pesquisa com discrepância Limitada
 . Aprendizagem por reforço na pesquisa em árvore

Bibliografia Obrigatória

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 3rd ed, 2009)

Observações Bibliográficas

Alguns artigos científicos sugeridos (sobre tópicos específicos).

Métodos de ensino e atividades de aprendizagem

O conteúdo programático permite consolidar formação anterior e introduzir algumas técnicas e métodos de áreas específicas e importantes para resolução de problemas práticos, de forma exata ou aproximada.

Metodologias de ensino:  aulas teórico-práticas; desenvolvimento de projectos práticos em grupo, sua apresentação oral e escrita; exame final.

As aulas destinam-se à apresentação e explicação dos tópicos selecionados, introduzindo conceitos, resultados e algoritmos principais, tendo sempre subjacente a relação com um problema de interesse prático.

Os projeto práticos e homeworks permitirão aos estudantes aprofundar o conhecimento sobre um problema numa das áreas abordadas, podendo ter um caracter de iniciação à investigação, com enfoque numa vertente experimental. Propiciará algum trabalho autónomo de estudo, análise e reflexão crítica, e oportunidade de trabalho colaborativo, bem como a aplicação ou adaptação de técnicas e algoritmos dados.

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Trabalho prático ou de projeto	100,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Elaboração de relatório/dissertação/tese	10,00
Estudo autónomo	88,00
Frequência das aulas	42,00
Apresentação/discussão de um trabalho científico	2,00
Elaboração de projeto	20,00
Total:	162,00

Obtenção de frequência

Ter entregue os projectos práticos.

Fórmula de cálculo da classificação final

4 projetos/homeworks (cada um valendo 25%) - resolução de exercícios, estudo de problemas e de alguns artigos relacionados, conceção e implementação, trabalho experimental e escrita de relatório de síntese.

Observações

Necessário conhecimentos ministrados na u.c. de Desenho e Análise de Algoritmos (CC2001), ou u.c. equivalente, e, preferencialmente, também em Algoritmos (CC4010).