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: 2022/2023 - 2S

Ativa?	Não
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	0	PE a partir do ano letivo de 2014	1	-	6	42	162
M:ENM	0	Plano de Estudos do M:Engenharia Matemática_2013-2014	1	-	6	42	162
			2

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 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: Métodos exatos; Pesquisa em árvore; Heurísticas e Metaheurísticas; Inaproximabilidade. Aplicações: 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.
- E - Computação quântica: visão quântica de algoritmos probabilísticos clássicos; estado quântico;  operações básicas sobre estados quânticos; modelo do circuito; algoritmo Deutch-Josza; dlgoritmo de Simon; transformada Quântica de Fourier; algoritmo de fatorização de Shor; algoritmo de pesquisa de Grover

======================================

Tópicos a abordar em 2022/2023:
A confirmar.  Poderão depender em parte do interesse e formação anterior dos estudantes inscritos. 

Provavelmente, (C) Alguns tópicos em Otimização combinatória (B) Algoritmos Geométricos e (E) Computação Quântica.

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)

Bibliografia Complementar

Ronald de Wolf; Quantum Computing Lecture Notes, 2021 (http://homepages.cwi.nl/~rdewolf/qcnotes.pdf)
Mark de Berg; Computational geometry. ISBN: 978-3-540-65620-3 hbk ((módulo B))
Joseph O.Rourke; Computational geometry in C. ISBN: 0-521-64976-5 ((módulo B))
Laurence A. Wolsey; Integer programming. ISBN: 9780471283669
Vijay V. Vazirani; Approximation algorithms. ISBN: 978-3-540-65367-7
Holger H. Hoos; Stochastic local search. ISBN: 978-1-55860-872-6

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	40,00
Exame	60,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

Projetos práticos (40%) - estudo de problemas e de alguns artigos relacionados, conceção e implementação, trabalho experimental e escrita de relatórios de síntese.

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

Poderão ser realizados testes para dispensa de exame final (a confirmar).

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).