final

Question 1

Nommes des métaheuristiques pour échapper à un optimum local

Answer 1

métaheuristique à base de trajectoire:
–recherche avec tabou : on se déplace toujours vers le meilleur voisin (même s’il est plus mauvais) mais on interdit le retour à une solution déjà visitée pendant un
certain nombre d’itérations.
–recuit simulé : on choisit un voisin au hasard et on se déplace vers lui même s’il dégrade la qualité de la solution (mais avec une faible probabilité). Au fur et à mesures des itérations, cette probabilité diminue
–recherche à voisinage variable : plusieurs types de voisinages sont utilisés ; lorsqu’on
atteint un minimum local dans un, on passe à un autre voisinage

métaheuristique à base de population: (on a pas une seule solution courante, mais bien plusieurs solutions)
–algorithmes génétiques: on a un bassin de population que l’on croise, modifie, combine, etc

Question 2

Quels sont les trois types d’algorithmes possibles ?

Answer 2

• exact: solution optimale
• d’approximation : solution que est garantie ‘être au plus à une distance donnée de la meilleure solution (ex à 25%)
  heuristiques: solution sans aucune garantie de sa qualité

Question 3

Quels sont les trois ordres possibles pour parcourir un arbre

Answer 3

en ordre: sud
post-ordre: est
pré-ordre: ouest

Question 4

Quelle est la différence entre Kruskal et Prim ?

Answer 4

Kruskal : pour faire un arbre couvrant de poid minimum, prend la plus petite arrête possible, peu importe elle est où dans le graphe, mais sans créer de cycle
Prim : pour faire un arbre couvrant de poid minimum, prend la plus petite arrête qui touche à une autre arrete deja dans l’arbre de recouvrement, mais sans créer de cycle

Question 5

Qu’est-ce qu’un algorithme probabiliste ?

Answer 5

Un algorithme qui utilise le hasard pour faire des choix aléatoire

Question 6

Nommer des types d’algorithmes probabilistes

et leur differences

Answer 6

termine correct

• numerique probabiliste X
• monte carlo X
• las vegas X
• sherwood X X

Question 7

Qu’est-ce que la classe de complexité P ?

Answer 7

problèmes de decision quon peut resoudre en un temps polynomial dans la taille de lexemplaire

Question 8

Qu’est-ce que la classe de complexité NP ?

Answer 8

problèmes de decision dont on peut vérifier une reponse affirmative en un temps polynomial dans la taille de lexemplaire

Question 9

Qu’est-ce que la classe de complexité NPC ?

Answer 9

probleme qui appartient à NP et qui est aussi difficile que chacune des problemes dans NP

Question 10

Qu’est-ce que la classe de complexité Pspace ?

Answer 10

probleme de decision quont peut resoudre en utilisant une quantité despace memoire qui est polynomaile dans a taille de l’exemplaire

Question 11

Qu’est-ce que la classe de complexité logspace ?

Answer 11

probleme de decision quont peut resoudre en utilisant une quantité despace memoire qui est logarithmique dans a taille de l’exemplaire

Question 12

Vrai ou faux ?
P⊂NP
P⊂NPC
NPC⊂P
P⊂Pspace

Answer 12

vrai
faux
faux
vrai

Question 13

SAT est dans quelle classe de complexité?
et 2SAT ?
et 3SAT ?

Answer 13

NPC
P
NPC

Question 14

Quels sont les algorithmes d’approximation possibles ? et les décrire

Answer 14

c-absolue. calcule une solution de valeur V dont l’erreur absolue par rapport à la valeur V⋆
optimale est au plus c :
V⋆ − c ≤ V ≤ V⋆ si on maximise
V⋆ ≤ V ≤ V⋆ + c si on minimise

e-relative. calcule une solution de valeur V dont l’erreur relative par rapport à la valeur V⋆ optimale est au plus e :
(1 − e)V⋆ ≤ V ≤ V⋆ si on maximise
V⋆ ≤ V ≤ (1 + e)V⋆ si on minimise

mixte. calcule une solution de valeur V dont l’erreur par rapport à la valeur V⋆ optimale s’exprime à la fois de manière absolue et relative :
(1 − e)V⋆ − c ≤ V ≤ V⋆ si on maximise
V⋆ ≤ V ≤ (1 + e)V⋆ + c si on minimise

Question 15

Qu’est-ce qu’un schéma d’approximation ?

Answer 15

c’est un algorithme auquel on fournit, en plus de l’exemplaire, l’e désiré pour l’algorithme d’approximation e-relative à résoudre.
On dira que le schéma d’approximation est pleinement polynomial s’il prend un temps dans O(p(n, 1/e))

Question 16

l’algorithme de Djikstra est-il un algorithme de programmation dynamique, glouton ou probabiliste ?

Answer 16

algorithme glouton

Question 17

Nommez un algorithme probabiliste du type Sherwood vu en cours. Quel est l’avantage de cet algorithme par rapport à un algorithme déterministe

Answer 17

Tri de Hoare “quicksort” avec choix de pivot uniformément au hasard.
Donne une complexité O(n lg n) espérée peu importe l’exemplaire

Question 18

pourquoi les algorithmes Sherwood sont-ils nommés ainsi ?

Answer 18

Sherwood est la forêt où vit robin des bois.
Comme robin qui distribuait la richesse des très riches aux plus pauvres, les algorithmes Sherwood redistribuent l’inefficacité de certains exemplaires (pire cas) à tous le monde

Question 19

Quel algorithme est le meilleur entre Prim et Kruskal?

Answer 19

ca dépend. Si le graphe est épars (peu d’arretes) on choisira kruskal (O(nlogn))
mais si le graphe est dense, on préférera Prim (O(n^2))

Question 20

Expliquez le patron de conception d’algorithme “vorace”

Answer 20

Algorithme itératif qui bâtit progressivement une solution en ajoutant à
chaque étape un élément parmi un ensemble de candidats, choisi selon un critère
localement optimal. Il ne revient jamais sur ses décisions

Question 21

Expliquez comment décider, en appliquant un parcours de graphe, si un graphe non orienté contient un cycle

Answer 21

En effectuant une fouille en largeur ou en profondeur, si on atteint un sommet déjà visité alors il y a un cycle.

dans une fep, il y a un cycle s’il y a des arretes arrieres
dans une fel, il y a un cycle s’il y a des arretes latérales

Question 22

Quelle est la différence entre diviser pour régner et la programmation dynamique ?

Answer 22

Les algorithmes diviser pour régner procèdent de haut en bas (“top down”) alors que les algorithmes de programmation dynamique procèdent de bas en haut (“bottom up”).
Ou encore, les premiers sont utilisés lorsqu’il n’y a pas de chevauchement des sous-exemplaires à traiter alors que les seconds le sont lorsqu’il y a justement chevauchement

Question 23

Qu’est-ce que le principe d’optimalité ?

Answer 23

La solution optimale d’un exemplaire est la combinaison des solutions optimales de certains de ses sous-exemplaires.

Question 24

Nommez et expliquez un problème indécidable

Answer 24

Le problème d’arrêt. Si la réponse est “non”, on ne pourra jamais la retourner car notre exécution d’un algorithme potentiel ne s’arrêtera pas.

Question 25

avantages et désavantages des algorithmes gloutons

Answer 25

avantages: facile à concevoir et implémenter rapides désavantages: confiné aux problèmes d'optimisation pas nécessairement optimal et pourrait même ne pas retourner de solution du tout

Question 26

Qu'est-ce qu'un graphe connexe ?

Answer 26

Un graphe est connexe si tous ces sommets ont un chemin entre un.

Question 27

Donnez une définition de la programmation dynamique

Answer 27

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-exemplaire, puis à résoudre les sous-problèmes en stockant les résultats intermédiaires

Question 28

Quand pouvons nous utiliser le patron de programmation dynamique ?

Answer 28

Il doit y avoir un chevauchement des sous-exemplaires. (souhaitable) Il faut qu'il y ait des sous-structure optimale (principe d'optimalité) (nécessaire)

Question 29

Donnez un exemple de problème auquel ne s'applique pas le principe d'optimalité.

Answer 29

Plus court chemin simple avec des arrêtes de longueur possiblement négative (on ne pourrait donc pas utiliser la programmation dynamique pour résoudre ce problème) Calcul du plus long chemin simple (meme chose)

Question 30

Qu'est-ce qu'un algorithme pseudo-polynomial?

Answer 30

C'est quand la consommation de l'algorithme dépend de la magnitude des nombres en entrée

Question 31

Quelles sont les étapes pour utiliser la programmation dynamique ?

Answer 31

1) définition du tableau 2) définition de la relation de récurence 3) établissement des valeurs frontières 4) remplissage du tableau selon l'ordre de la récurence 5) récupération de la solution

Question 32

différence entre fouille en largeur et fouille en profondeur ?

Answer 32

une fouille en largeur utilise une file tandis qu'une fouille en profondeur utilise une pile

Question 33

Lors de fouilles en profondeur ou en largeur, comment s'apelle les autres arrêtes de l'arbre qui ne font pas partie du chemin de la fouille ?

Answer 33

pour la fouille en profondeur : arrete arrières | pour la fouille en largeur : arrete latérale

Question 34

Comment savoir si un graphe est connexe ?

Answer 34

En effectuant une fouille en largeur ou en profondeur, s'il n'y a qu'un seul arbre généré, alors le graphe est connexe

Question 35

Qu'est-ce qu'un couplage ?

Answer 35

un couplage dans un graphe est un sous ensemble de ses arrêtes qui ne partagent aucuns sommets

Question 36

Qu'est-ce qu'un chemin augmentant ?

Answer 36

étant donnée un certain couplage C dans un graphe, un chemin augmentant relie deux sommets non couplé et est composé en alternance d'arretes faisant et ne faisant pas partie de C

Question 37

Quelle est la différence entre un graphe implicite et explicite ?

Answer 37

Un graphe implicite est trop grand pour qu'on puisse le représenter entièrement en mémoire. On n'en manipule qu'une petite partie à la fois

Question 38

Qu'est-ce que l'algorithme DSATUR ? (Brélaz)

Answer 38

C'est un algo pour le problème de coloriage de graphe dont l'idée est de s'occuper d'abord des sommets les plus contraints L'heuristique DSATUR donne la solution optimale sur un graphe biparti ; par contre, elle ne donne pas de garantie en général sur la qualité de la solution obtenue

Question 39

Donnez une définition pour les heuristiques d'amélioration locale

Answer 39

À partir d'une solution initiale s0 , appliquer une sucession de modifications locales afinn d'arriver à une meilleure solution st après t itérations

Question 40

Nommez des voisinages possibles et les expliquer

Answer 40

voisinage ré-affectation : on change l'affectation d'un seul élément de la solution. La taille de ce voisinage est dans Θ(nm) voisinage échange : on échange l'affectation de deux élément de la solution. La taille de ce voisinage est dans Θ(n^2) voisinage k-échange: on échange l'affectation de k éléments de la solution. La taille de ce voisinage est dans O(n^k)

Question 41

pourquoi dans la métaheuristique de recherche tabou, on met la solution dans un ensemble T dite Tabou ?

Answer 41

Pour empêcher de revenir à une solution visitée récemment. Parce que le voisinage est symétrique. Je suis le voisin de mon voisin. On ne veut pas revenir à la solution qu'on vient d'échapper, on interdit la modification inverse.

Question 42

Quelle est la différence entre le problème du sac à dos et le problème de mise en boite ?

Answer 42

Dans le problème du sac à dos, les objets ont un poids ET une valeur. Il faut -choisir- les objets qui rentrent dans le sac et maximiser la valeur du sac Dans le problème de mise en boite, il faut mettre -tous- les objets qu'on possède dans des boites en minimisant le nombre de boite utilisées OU on a plusieurs objets de poids wi et k boites de poid W, on veut savoir le plus grand nombre d'objets quon peut y mettre

Question 43

Nommez des algorithmes gloutons pour résoudre le problème de mise en boite (ou il faut mettre tous les objets qu'on a en minimisant le nombre de boites)

Answer 43

- Fist-Fit-Decreasing : on prend les objets les plus lourd en premier, et on les met dans la premiere boite disponible - Best-Fit-Decreasing: On prend les objets les plus lourd en premier, et on les met dans la boite qui minimisera la place restante après avoir mis l'objet

Question 44

Qu'est-ce qu'un algorithme de Monte Carlo p-correct?

Answer 44

Un algo monte carlo est p-correct si la probabiblité qu'il retourne la bonne réponse est d'au moins p, et ce peu importe l'exemplaire

Question 45

Qu'est-ce qu'un algorithme de Monte Carlo biaisé ?

Answer 45

Un algo monte carlo est biaisé si au moins une des réponse retournée en sortie est correcte.

Question 46

Si la probabilité de succès (terminaison) d'un algorithme de Las Vegas est p, le nombre espéré de relance pour obtenir une réponse est de combien ? Et quelle est la formule pour calculer le temps espéré pour chacune des répétition ?

Answer 46

1/p Ttot = (1/p - 1)Te + Ts où Ts et Te sont respectivement le temps d'exécution espéré en cas de succès et d'échec

Question 47

Nommez une facon de calculer l'effort de calcul associé à un programme de graphe (par exemple le problème des n-reines)

Answer 47

On peut mesurer l'effort de calcul par le nombre de noeuds explorés dans l'arbre de recherche

Question 48

Quel est le principe de l'amplification de l'avantage stochastique ? et formules

Answer 48

C'est d'augmenter la probabilité de retourner une réponse correcte en répétant des appels indépendants à un algorithme Monte Carlo avec k répétitions d'un algorithme p-correct biaisé on aura un algorithme q-correct où q = 1 − (1 − p)^k avec k répétitions d'un algorithme p-correct NON biaisé on aura un algorithme q-correct où q = (voir photo**)

Question 49

pourquoi l'amplification de l'avantage stochastique est inutile lorsqu'on tire à pile ou face ?

Answer 49

Parce que la probabilité de succès est de 1/2. | L'amplification aux algorithmes non biaisés peux seulement être utilisé si p > 1/2

Question 50

Qu'est-ce que la réduction de problème de A vers B ?

Answer 50

Transformation d'un exemplaire de A pour un exemplaire de B tel que B répondrait oui si et seulement si A répondrait oui

Question 51

Expliquez l’avantage du patron d’algorithme "backtracking" par rapport à générer-puis-tester.

Answer 51

Le premier évite une énumération explicite de toutes les solutions potentielles en interrompant la génération d’une solution partielle dès qu’on détecte qu’il est impossible de la compléter en une solution valide. On élimine ainsi d’un seul coup de nombreuses solutions

Question 52

comment on s’y prend pour démontrer qu’un problème de décision est N P-complet ?

Answer 52

Par réduction de problème pour un problème π : 1. Montrer que π ∈ NP. 2. Choisir π' ∈ NPC. 3. Concevoir une transformation f qui fait correspondre à chaque exemplaire de π' un exemplaire de π. 4. Montrer que f se calcule en temps polynomial dans la taille d’un exemplaire de π' 5. Montrer l’équivalence : réponse positive ssi réponse positive