Examens corriges

Examen final et corrigé d'analyse et conception d'algorithmes

Introduction à l'examen final d'analyse et conception d'algorithmes

Cet article propose une analyse détaillée du sujet d'examen final de la session d'automne 2004 pour le cours d'analyse et conception d'algorithmes. Ce document d'évaluation académique comporte l'ensemble des questions posées aux étudiants ainsi que les corrigés officiels détaillés. Il constitue un support de travail précieux pour appréhender les exigences méthodologiques et théoriques attendues dans le cadre de cet enseignement supérieur.

Présentation générale du document

Le document officiel émane de l'École Polytechnique de Montréal, rattaché au département de génie informatique. Il s'adresse aux étudiants inscrits au cours portant sur la matière algorithmique avancée. D'une durée initiale de deux heures et demie, l'examen rassemble six grandes questions notées sur un total de vingt points, couvrant un large spectre de notions fondamentales en informatique théorique et en optimisation.

Contenu thématique et questions abordées

Les exercices et questions théoriques de l'épreuve parcourent plusieurs grands thèmes structurants de la discipline :

  • La complexité algorithmique et les notations asymptotiques, avec une distinction claire entre les bornes supérieures et inférieures.
  • L'analyse de structures de graphes et de leurs propriétés, incluant les arbres de recouvrement minimum.
  • Les algorithmes voraces et leur application à des problèmes d'optimisation de parcours ou d'autonomie.
  • La méthode de résolution par séparation et évaluation, plus communément appelée branch-and-bound.
  • La programmation dynamique et la résolution de problèmes par sous-structures optimales, illustrée par un problème de gestion de location de bicyclettes le long d'un parcours de course.
  • Les algorithmes probabilistes, en particulier l'analyse du comportement des algorithmes de Monte Carlo et la amplification de leur fiabilité par répétition.

Méthodes d'évaluation et types d'exercices

Le questionnaire alterne habilement entre des questions de validation conceptuelle par Vrai ou Faux, des questions de cours demandant d'expliquer brièvement des concepts fondamentaux, et des exercices pratiques approfondis. Par exemple, l'optimisation par séparation et évaluation exige de tracer l'arbre de recherche et de calculer les bornes pour maximiser un profit d'affectation d'objets à des acheteurs. De même, l'approche par programmation dynamique demande de formaliser mathématiquement une relation de récurrence pour un coût minimal de transport.

Utilisation recommandée pour les révisions

L'utilisation optimale de ce sujet corrigé consiste à s'exercer en conditions réelles, en tentant de résoudre chaque problème avant de consulter la solution détaillée fournie. L'analyse des corrigés permet de comprendre la rigueur exigée dans la rédaction des démonstrations et dans la formalisation des algorithmes. C'est également un excellent moyen de repérer les pièges classiques liés aux heuristiques locales, aux complexités algorithmiques ou à l'interprétation des probabilités de succès des méthodes de Monte Carlo.

Questions fréquentes

Quel est l'établissement qui propose cet examen ?

Ce document provient de l'École Polytechnique de Montréal, au sein du département de génie informatique.

À quel niveau d'études s'adresse ce sujet ?

Il s'adresse aux étudiants de niveau universitaire suivant un cours d'analyse et conception d'algorithmes d'une valeur de 3 crédits.

Quels sont les principaux paradigmes algorithmiques abordés dans l'épreuve ?

L'examen aborde les algorithmes voraces, la programmation dynamique, la méthode branch-and-bound, ainsi que les approches probabilistes de type Monte Carlo.

Testez vos connaissances

Question 1

Que mesure la notation asymptotique O() dans l'analyse des algorithmes ?

  1. Une borne inférieure sur la consommation de ressources
  2. Une borne supérieure sur la consommation de ressources
  3. Le temps exact d'exécution en secondes
  4. La quantité moyenne de mémoire utilisée par un ordinateur spécifique

Réponse correcte : Une borne supérieure sur la consommation de ressources

Explication : La notation O() exprime une borne supérieure sur l'utilisation des ressources informatiques telles que le temps ou l'espace en fonction de la taille de l'entrée.

Question 2

Quelle est la caractéristique fondamentale qui différencie la programmation dynamique de la technique diviser-pour-régner selon le document ?

  1. L'une utilise des graphes et l'autre des arbres
  2. La programmation dynamique procède de bas en haut, tandis que diviser-pour-régner procède de haut en bas
  3. L'une utilise des probabilités et l'autre est entièrement déterministe
  4. La programmation dynamique est toujours plus rapide

Réponse correcte : La programmation dynamique procède de bas en haut, tandis que diviser-pour-régner procède de haut en bas

Explication : Bien que les deux techniques reposent sur des relations de récurrence, la programmation dynamique construit la solution de bas en haut contrairement à l'approche diviser-pour-régner.

Question 3

Qu'est-ce qu'un algorithme Monte Carlo dit 'vrai-biaisé' pour un problème de décision ?

  1. Il est toujours exact lorsque la réponse est Vrai
  2. Il donne toujours une réponse aléatoire
  3. Il ne commet jamais d'erreur lorsque la réponse est Faux
  4. Il est plus lent que les autres algorithmes

Réponse correcte : Il est toujours exact lorsque la réponse est Vrai

Explication : Un algorithme vrai-biaisé garantit une exactitude absolue lorsque la solution attendue est Vrai, pouvant en revanche présenter un taux d'erreur lorsque la solution est Faux.





Télécharger Examen final et corrigé d'analyse et conception d'algorithmes pdf