Algoritmos Geométricos

Código:

CC443

Sigla:

CC443

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

Ocorrência: 2013/2014 - 2S

Ativa?	Não
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/ALGOGEO/1314
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos

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 do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
MI:ERS	0	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5

Língua de trabalho

Português

Objetivos

Introdução à Geometria Computacional com enfâse no estudo de algoritmos clássicos para resolução de problemas com aplicações relevantes em Computação Gráfica, Robótica, Desenho Assistido por Computador, Sistemas de Informação Geográfica, Biologia Molecular e Análise de Dados.

Resultados de aprendizagem e competências

Conhecer e saber implementar algoritmos e estruturas de dados eficientes para resolução de problemas geométricos no plano. Capacidade de os adaptar para resolução de problemas afins.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Requer conhecimentos de desenho e análise de algoritmos e experiência de programação (em C, C++, JAVA ou Python).

Programa

Conceitos e ferramentas básicas em Geometria Computacional. Técnicas de varrimento do plano. Algoritmos para determinação do invólucro convexo de um conjunto de pontos. Algoritmos para decomposição de polígonos: partição de polígonos ortogonais em rectângulos alinhados, triangulação de polígonos monótonos e triangulação de polígonos genéricos. Noções de visibilidade no plano: introdução ao problema da Galeria de Arte e variantes. Algoritmos para identificar as intersecções dos segmentos de recta de um conjunto. Decomposições planares: algoritmo para determinar a sobreposição de duas decomposições e sua aplicação para obter a intersecção, união e diferença de duas decomposições planares (temáticas). Algoritmo para determinação do arranjo de um conjunto de rectas complanares (teorema da zona e complexidade do arranjo). Algoritmos para localização de pontos em regiões rectangulares. Problemas de proximidade. Diagrama de Voronoi e triangulação de Delaunay de um conjunto de pontos no plano: algoritmos para sua determinação e propriedades. Estruturas de dados para problemas geométricos. Aplicações.

Bibliografia Obrigatória

000075502. 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)
000074637. ISBN: 0-521-64976-5 (Joseph O'Rourke, "Computational geometry in C" , 2nd ed. Cambridge University Press, 2001)

Bibliografia Complementar

000097672. ISBN: 9780444825377 (J.R Sack and J. Urrutia, "Handbook of Computational Geometry", Elsevier Sci. Publishers, Amsterdam, 2000.)
000097671. ISBN: 9781584883012 (Jacob E. Goodman, Joseph O'Rourke (Eds), "Handbook of discrete and computational geometry" CRC Press, 1991.)
000102107. ISBN: 9780262033848 hbk (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, "Introduction to Algorithms (Second Edition)", MIT Press, 2001.)
000000083. ISBN: 978-0-387-96131-6 New York : hbk (Franco P. Preparata, Michael Ian Shamos, "Computational Geometry: an Introduction", Springer-Verlag 1985.)

Observações Bibliográficas

Bibliografia complementar: Alguns artigos científicos a indicar.

Ligações externas:

- GCAL - Computational Geometry Algorithms Library (CGAL Open Source Project) http://www.cgal.org/

Métodos de ensino e atividades de aprendizagem

Aulas teóricas: exposição da matéria, acompanhada de discussão de alguns casos de estudo.

Aulas práticas: aulas laboratoriais para  desenvolvimento do Projeto Prático.

Apresentação escrita e oral dos projetos pelos estudantes.

Avaliação de conhecimentos.

 

Classificação: 35% projeto prático -- estudo e implementação de um algoritmo para resolução de um problema (tópico a definir pelo docente). 65% exame final (questões de índole teórica sobre a matéria lecionada).

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	65,00
Participação presencial	0,00
Trabalho laboratorial	35,00
Total:	100,00

Obtenção de frequência

Perde a frequência o estudante que não estiver presente a pelo menos 75% das aulas práticas previstas (cf. regulamento FCUP).

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

35% Projecto Prático (Implementação + Relatório)

65% Exame Final (é exigida a nota mínima de 9.5 valores para aprovação à disciplina)

Avaliação especial (TE, DA, ...)

Idêntica à dos restantes alunos.