Geometria Computacional › 47604

Objectivos e competências (objectives)

O objectivo desta disciplina é desenvolver algoritmos e estruturas de dados eficientes que serão aplicados na resolução de problemas de optimização em termos de objectos geométricos elementares.

 

 

Domínio do funcionamento de sistemas dedutivos, modelação e representação de conhecimento, programação em Prolog, capacidade de utilizar as ferramentas da Matemática na programação, programação numa linguagem funcional.

Algoritmos geométricos: localização de pontos em polígonos e poliedros.

Determinação de invólucros convexos.

Problemas de proximidade: O problema do par mais próximo.

Triangulação de polígonos simples.

Teorema da Galeria de Arte e Variantes.

Diagramas de Voronoi e Triangulação de Delaunay.

A avaliação desta disciplina enquadra-se no regime de avaliação da UA, sendo dada a possibilidade dos alunos optarem pela avaliação contínua ou pela avaliação final. A avaliação contínua desta disciplina compreende os seguintes elementos: (a) Apresentação e crítica de um artigo científico da área (b) Dois mini-testes (b1 e b2) de curta duração (60 – 75 minutos) A componente (a) terá um peso de 30% e a componente (b) de 70% (b1 = 30% e b2 = 40%). Aprovação na Disciplina (regime de avaliação periódica): Serão aprovados na disciplina os alunos que obedeçam às seguintes condições: 1. Obtenham um mínimo de 9,5 valores no somatório das notas dos três elementos de avaliação e; 2. Obtenham um mínimo de 30% na nota de cada um dos três elementos de avaliação. Regras importantes: - Todos os alunos que se submeterem ao primeiro mini-teste (b1) ficam sujeitos ao regime de avaliação contínua, não podendo desistir dele no presente ano lectivo. - Os alunos que optarem pelo método de avaliação contínua, caso não tenham aproveitamento, não serão admitidos a exame de época normal, podendo contudo ir à época de recurso. - Os alunos que optarem pelo método de avaliação final deverão realizar a componente de apresentação e crítica dum artigo científico da área. Neste caso, no exame final (época normal) serão avaliados todos os temas abordados durante o semestre lectivo e terá um peso de 70% na classificação final da disciplina. - Os alunos em regime de trabalhador-estudante poderão (com prévia coordenação com o docente da disciplina) realizar a apresentação e crítica dum artigo científico da área em horário extra-aulas. - Todos os alunos têm sempre acesso à época de recurso. - O exame de recurso substituirá todas as componentes de avaliação da disciplina e portanto terá um peso de 100% na classificação final da disciplina. Neste exame serão avaliados todos os temas abordados durante o semestre lectivo.

- Exposição do material teórico e teórico práticos nas aulas teóricas da disciplina. - Exposição e discussão dos conceitos fundamentais relacionados com os métodos e técnicas algorítmicas de problemas geométricos. - Os alunos deverão participar nesta exposição mediante a elaboração e apresentação de críticas a artigos científicos da área. - Haverá acesso a um web site da disciplina onde será disponibilizado o material das aulas para facilitar o seu acompanhamento.

Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985.

Bibliografia principal

 

1.      M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational Geometry, Algorithms and Applications, Springer Verlag, 1997 (second edition, 2000).

2.      F.P. Preparata and M.I. Shamos: Computational Geometry: An Introduction, Texts and Monographs in Computer Science,Springer-Verlag,New York, 1985.

3.       J. O""Rourke: Computational Geometry in C, Cambridge University Press,Cambridge, 1994 (second edition, 1998).

4.       J.–R. Sack and J. Urrutia (editors): Handbook of Computational Geometry, Elsevier Science, 2000.