Examen final Flashcards
Quels sont les deux types de metaheuristique
Trajectoire
Population
Quels sont les trois types de metaheuristique de trajectoire
Recherche Tabou
Voisinage Variable
Recuit simulé
Qu’est-ce qu’un schéma d’approximation ?
C’est un algorithme générique auquel on donne, en plus de l’exemplaire, l’epsilon désiré pour la garantie d’approximation relative.
Nommer les trois types d’algorithmes d’approximation?
C-abolue
Epsilon-Relative
Algorithme mixte
Qu’est-ce qu’un algorithme C-Absolue
Un algorithme ou la différence entre l’optimal est de plus ou moins C
Donc, - pour maximiser : V*-C <= V <= V* - pour minimiser : V* <= V <= V* + C
Qu’est-ce qu’un algorithme Epsilon-Relative
Un algorithme ou l’erreur est au plus epsilon
Pour Maximimser :
(1-epsilon)V* <= V <= V*
Pour minimiser :
V* <= V <= (1+epsilon)V*
Qu’est-ce qu’un algorithme d’Approximation mixte
Un mélange de C-Absolue et Espilon-Relative
Maximiser :
(1-epsilon)V-C <= V <= V
Miniser :
V* <= V <= (1+epsilon)V*+C
Qu’est-ce que l’effet Robin des bois?
Redistribuer l’effort d’un algorithme en ajoutant des probabilité. Par exemple, choisir un pivot au hasard
Quel est la formule pour calculer la probabilité d’un algorithme biaisé amplifié?
q = 1 - (1-p)^k
Quel est la formule pour calculer la probabilité d’un algorithme non biaisé amplifié?
La somme des probabilités des cas ou la réponse favorable est majoritaire
Expliquez la différence entre les classes de complexité NP et co-NP
La classe de complexité NP est l’ensemble des problèmes de décision dont on peut vérifier une réponse affirmative en un temps polynomial dans la taille de l’exemplaire. La classe de complexité co-NP est l’ensemble des problèmes de décision dont on peut vérifier une réponse négative en un temps polynomial dans la taille de l’exemplaire.
Existe-t-il des problèmes appartenant à la fois à P et à N P ? Justifiez.
Oui : tous les problèmes dans P peuvent être résolus en temps polynomial, donc on peut aussi vérifier une solution affirmative en temps polynomial ; ainsi ils
sont également dans NP. Il suffit aussi de répondre : bien sûr, puisque P ⊂ N P.
Qu’est-ce qu’un problème NP-complet ?
C’est un problème de décision appartenant à la classe NP et aussi difficile que n’importe quel autre membre de cette classe de complexité.
Est-ce que le Problème d’arrêt est indécidable à cause de la difficulté de retourner une réponse positive ou négative ? Expliquez.
Négative : si la réponse est “non”, on ne pourra jamais la retourner car notre exécution (simulation) d’un algorithme potentiel ne s’arrêtera pas.
Qu’entend-on par “cet algorithme a une consommation de ressource qui est pseudo-polynomiale” ?
Que sa complexité ne dépend pas seulement de la taille de l’exemplaire mais aussi de la magnitude des nombres en présence.
Le problème SAT est NP-complet ; quelle version restreinte de ce problème est par contre dans P?
2SAT, qui restreint chaque clause à contenir exactement 2 littéraux.
On acceptera aussi Horn-SAT.
Peut-on résoudre le problème du plus long chemin dans un graphe en adaptant l’algorithme de Dijkstra pour le problème du plus court chemin ? Si oui, dites
comment ; sinon, expliquez pourquoi.
Non. L’algorithme de Dijkstra est un algorithme glouton qui exploite la propriété de sous-structure optimale du problème du plus court chemin. Cette propriété
n’est pas vérifiée dans le problème du plus long chemin.
Définissez l’optimum local pour un problème de minimisation. Est-ce qu’on obtient le même optimum local si on applique l’algorithme d’amélioration locale en partant de deux solutions différentes ? (Vous pouvez donner votre réponse sous forme d’un dessin)
Soit V (s) le voisinage de la solution s. s est un optimum local pour un problème de minimisation si pour chaque s 0 ∈ V (s) on a f (s) ≤ f (s 0 ) où f est une fonction coût. Les voisinages de 2 solutions différentes sont différents ainsi, les 2 trajectoires empruntées par un algorithme d’amélioration locale ne seront pas nécessairement les mêmes.
Quelles sont les algorithmes de coloriage de graphe et leur complexité?
Heuristique constructif
- Algorithme vorace naïf -> O(n^2)
- Algorithme de DSATUR (plus contraignant en premier) -> O(n^2)
Décrivez les décisions de conception pour utiliser une heuristique d’amélioration locale.
- Conception d’une heuristique pour la construction de la solution initiale S
- Conception d’un voisinage V pour la solution S
- Décider du critère d’arrêt à chaque itération : Première solution améliorante ou la meilleure solution
Qu’est-ce qu’un Algorithme Monte Carlo
Un algorithme qui retourne une valeur qui n’est pas nécessairement correcte
Qu’est-ce qu’un Algorithme numérique probabiliste
Un algorithme qui un interval qui n’est pas nécessairement bonne
Qu’est-ce qu’un Algorithme Las Vegas?
Un algorithme qui retourne la bonne réponse. Cependant, il ne retourne pas toujours
Qu’est-ce qu’un Algorithme Sherwood
Un algorithme Las Vegas (qui retourne la réponse) mais qui retourne tout le temps.
Qu’est-ce qu’on entend par l’amplification de l’avantage stochastique ?
Il s’agit de relancer plusieurs fois un algorithme probabiliste Monte Carlo afin de réduire sa probabilité d’erreur. Cette amplification est beaucoup plus prononcée lorsque l’algorithme est biaisé.
Qu’est-ce qui distingue une métaheuristique à base de trajectoire d’une
métaheuristique à base de population ?
La première maintient une seule solution courante alors que la seconde en maintient un grand nombre.
Quelles opérations fait-on sur un algorithme génétique
Croisement et mutation
Définissez la classe P
C’est l’ensemble des problèmes de décision qu’on peut résoudre en temps polynomial dans la taille de l’exemplaire.
Quel note Christophe doit avoir dans son examen poour passe Algo?
14.5/35
Quel note Louis doit avoir dans son examen poour passe Algo?
13.5/35
Comment prouver qu’un problème NPC est au moins aussi difficile qu’un problème NP?
1 - montrer que le nouveau problème appartient à la classe NP, car c’est un problème de décision dont on peut vérifier une réponse affirmative en temps polynomial.
2 - Réduire la problème NPC en le nouveau problème. Si une solution du nouveau problème se trouve dans le problème NPC ceci veut dire que le nouveau problème est au moins aussi difficile que le NPC
Que peut-on déduire d’un problème A qui se réduit en un problème B?
B est au moins aussi difficile que A
A <= B
Qu’est-ce que l’algorithme Krukal
On ajoute toujours le plus petit arete à notre forest à condition qu’il ne forme pas de cycle.
Quel est la complexité de Kruskal?
theta(a log(n))
a = arete
Qu’est-ce que l’algorithme de Prim
On ajoute le plus petit arete à notre arbre à condition de ne pas former de cycle
Quel est la complexité de Prim
theta(n^2)
Les étapes pour créer un algorithme Glouton
1 - sélectionner un ensemble de candidats
2 - Élaborer une fonction de choix glouton
3 - Créer une fonction solution
4 - (optionnel) Créer une fonction illégale
Comment prouver l’optimalité d’une fonction Glouton
- Propriété de sous-structure optimale
- Propriété du choix Glouton
Que peut-on déduire d’une fonction gluton sur un matroïde?
Qu’il est optimal
Quand est-ce que l’on peut faire de la programmation dynamique?
Lorsque l’algorithme est optimal (principe de sous-strucutre optimale) ET des sous-strucutres de chevauche (répétitions)
Quelles sont les 5 étapes pour construire un algorithme dynamique
1- Définir le tableau 2- Définir la relation de récurrence 3- Établir les valeurs frontières 4- Remplir le tableau 5- Récupérer la solution
Qu’est-ce qu’un algorithme branch-and-bound?
À chaque noeud, je vérifie si le potentiel de continuer va battre mon maximum actuel avant de procéder
Qu’est-ce que P?
Classe de problèmes à complexité polynomial
Qu’est-ce que NP?
Classe de problèmes à complexité polynomial qui se répond à l’affirmatif
Qu’est-ce que Co-NP?
Classe de problèmes à complexité polynomial qui se répond au négatif
Qu’est-ce que le problème SAT
Le problème des booléans
Qu’est-ce qu’un schéma d’approximation pleinement polynomial?
Si O(p(n,1/epsilon))
