Tópicos Avançados em Algoritmos
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2020/2021 - 2S
Ciclos de Estudo/Cursos
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).