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: 2014/2015 - 2S

Ativa?	Sim
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	11	PE a partir do ano letivo de 2014	1	-	6	42	162
MI:ERS	2	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

UC organizada em quatro módulos temáticos, de que serão escolhidos tópicos para apresentação.
- A - Algoritmos em grafos e redes: Caminhos; Fluxo máximo e de custo mínimo; Emparelhamentos (cardinal máximo; pesados; com preferências); Morfismos de grafos (descoberta de motifs); Redes de mundo pequeno.
- B - Algoritmos geométricos: Primitivas; Varrimento planar; Invólucro convexo; Interseções de decomposições planares; Triangulação; Visibilidade e Galeria de Arte; Arranjos e dualidade; Localização de pontos; Diagramas de Voronoi e triangulações de Delaunay; Procura num domínio.
- C - Otimização combinatória: Caixeiro viajante (TSP); Escalonamento; Localização de serviços; Encaminhamento de veículos; Empacotamento e corte; Cobertura (incluindo de conjuntos); Contagem (aproximada) e Amostragem.
- D - Estruturas de dados avançadas: Estruturas com auto-ajustamento; temporais; modelos para "cache"; sucintas. Estruturas para problemas geométricos.


Tópicos a serem abordados em 2014/2015:
 B - Varrimento planar. Invólucro convexo em 2D. Decomposição de polígonos, triangulação e problemas de vigilância (Galeria de Arte). Interseção de segmentos. Proximidade:  par de pontos mais próximos; diagramas de Voronoi e triangulação de Delaunay para conjuntos finitos.
 C - Algoritmos de aproximação para problemas de optimização NP-hard (ex, cobertura por vértices, cobertura de conjuntos, TSP  métrico e euclideano). Vigilância óptima de polígonos com guardas em vértices  (MVG): algoritmos exatos e heurísticas. Inaproximabilidade (casos MVG, e TSP genérico).
 A - Introdução aos problemas de emparelhamento com preferências em grafos bipartidos; redes complexas, suas propriedades (ex: mundo pequeno e "power laws") e modelos de geração (ex, Erdős–Rényi, Watts–Strogatz e Barabási–Albert); isomorfismos de grafos e subgrafos; descoberta de comunidades (ex, modularidade); padrões em redes (ex, "motifs" e "graphlets").
 D - Estruturas para problemas geométricos: listas de arestas duplamente ligadas (DCEL) para decomposições planares; estruturas de dados com auto-ajustamento (ex, red-black trees e splay trees); pesquisa em intervalos (ex, quadtrees, kd-trees, segment trees e fenwick trees); filas de prioridade (ex, binomial heaps e pairing heaps); estruturas de dados probabilísticas (ex, skip lists, treaps e bloom filters).

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)
Berg Mark de 070; Computational geometry. ISBN: 978-3-540-65620-3 hbk ( Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, "Computational Geometry: Algorithms and Applications", 3rd Edition, Springer-Verlag, 2008 (or 2nd Edition). )
O.Rourke Joseph; Computational geometry in C. ISBN: 0-521-64976-5 (J.O'Rourke. Computational Geometry in C. 2nd edition, Cambridge University Press, 2001)

Bibliografia Complementar

Vazirani Vijay V.; Approximation algorithms. ISBN: 9783540653677 (Vijay V. Vazirani. Approximation Algorithms. Springer, 2001)
Garey Michael R.; Computers and intractability. ISBN: 0-7167-1045-5 (M.R.Garey, D.S.Johnson. Computers and Intractability: a guide to the theory of NP-completeness, W.H. Freeman, 1979)
J. Kleinberg, E. Tardos.; Algorithm Design., Addison-Wesley, 2005. ISBN: 978-0321295354 ((Cap 11, algoritmos de aproximação) materiais disponíveis em http://www.cs.princeton.edu/~wayne/kleinberg-tardos/))
S. Halim and F. Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (PDF da 1ª versão disponível online: https://sites.google.com/site/stevenhalim/)

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. Os tópicos admitem um tratamento independente permitindo ao docente efetuar uma seleção mais diversificada ou mais focada numa área. As áreas e tópicos do programa estão relacionados com trabalho de investigação passado ou em curso no Departamento.

Metodologias de ensino:  aulas teórico-práticas; desenvolvimento de projecto prático em grupo, sua apresentação oral e escrita; exame final (sem consulta).

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

O projeto prático permitirá 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.

O exame final destina-se à avaliação global de conhecimentos genéricos sobre a matéria lecionada uma vez que a especificidade do tema do projeto prático poderá não permitir uma avaliação suficientemente abrangente e mais individualizada.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	60,00
Trabalho laboratorial	40,00
Total:	100,00

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

Projeto prático (40%-60%) - estudo do problema e de alguns artigos relacionados, conceção e implementação, trabalho experimental e escrita de relatório de síntese.

Exame final (60%-40%) - sem consulta (necessário classificação mínima de 9.5 em 20 no exame).

Dependendo da qualidade do projeto prático desenvolvido, a ponderação da sua classificação na nota final pode ser de até 60%.