Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF6133  Gr. 01
Titre : Algorithmes géométriques
Session : Automne 2016  Horaire et local
Professeur : Czyzowicz, Jurek
1. Description du cours paraissant à l'annuaire :

Objectifs

Permettre aux étudiants de perfectionner leurs connaissances sur les algorithmes traitant les données géométriques et leurs applications.

Contenu

Types de données géométriques. Graphes géométriques. Graphes de disques unitaires. Arrangements. Grilles. Arbres quaternaires. Recherche géométrique et localisation de points. Intersections. Triangulations et trapézoïdations. Enveloppes convexes. Diagrammes de Voronoï et triangulations Delauney. Algorithmes d’exploration et planification de trajectoires.
2. Objectifs spécifiques du cours :
Introduire les étudiants aux spécificités des algorithmes traitant les données géométriques. Introduire les étudiants aux spécificités et à la complexité des problèmes et les algorithmes géométrique. Illustrer par les exemples d’applications.
3. Stratégies pédagogiques :
  • Cours magistraux
  • Recherche dirigée dans des sujets spécialisés
  • Écriture et présentation d'un rapport
4. Heures de disponibilité ou modalités pour rendez-vous :
Jeudi 15h00 - 17h00.
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1    Primitives géométriques. Complexités des données géométriques. Solutions informatiques des problèmes géométriques de base. 12 sept. 2016 
2    Problèmes géométriques de base (suite). Recherche géométrique. Localisation de points. 19 sept. 2016 
3    Requêtes orthogonales en bases de données. Graphes géométriques. 26 sept. 2016 
4    Graphes de visibilité. Problèmes de la supervision de galléries d'arts. Triangulations et trapézoïdations. 03 oct. 2016 
5    Semaine d'étude. 10 oct. 2016 
6    Planification de trajectoires de robots. 17 oct. 2016 
7    Enveloppes convexes. 24 oct. 2016 
8    Examen intra. 31 oct. 2016 
9    Intersection de segments. Droites de balayage. 07 nov. 2016 
10    Diagrammes de Voronoï. 14 nov. 2016 
11    Triangulations de Delauney. 21 nov. 2016 
12    Grilles. Arbres quaternaires. Applications choisies. 28 nov. 2016 
13    Présentations des étudiants. 05 déc. 2016 
14    Révision. 12 déc. 2016 
15    Examen final. 19 déc. 2016 
6. Évaluation du cours :
  • Présentations d'étudiants :15 %
  • Examen intra : 40 %
  • Examen final : 45 %
7. Politiques départementales et institutionnelles :
8. Principales références :
  1. Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. Computational Geometry. Algorithms and Applications. 3rd Edition, 2008.
  2. Preparata, F.P., M.I. Shamos: Computational Geometry. An Introduction. Springer 1993.
9. Page Web du cours :
http://moodle.uqo.ca/course/view.php?id=9078