Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithme > Examen final > Flashcards

Examen final Flashcards

1
Q

Quels sont les deux types de metaheuristique

A

Trajectoire

Population

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Quels sont les trois types de metaheuristique de trajectoire

A

Recherche Tabou
Voisinage Variable
Recuit simulé

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Nommer les trois types d’algorithmes d’approximation?

A

C-abolue
Epsilon-Relative
Algorithme mixte

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Qu’est-ce qu’un algorithme C-Absolue

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Qu’est-ce qu’un algorithme Epsilon-Relative

A

Un algorithme ou l’erreur est au plus epsilon

Pour Maximimser :
(1-epsilon)V* <= V <= V*
Pour minimiser :
V* <= V <= (1+epsilon)V*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Qu’est-ce qu’un algorithme d’Approximation mixte

A

Un mélange de C-Absolue et Espilon-Relative

Maximiser :
(1-epsilon)V-C <= V <= V
Miniser :
V* <= V <= (1+epsilon)V*+C

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Qu’est-ce que l’effet Robin des bois?

A

Redistribuer l’effort d’un algorithme en ajoutant des probabilité. Par exemple, choisir un pivot au hasard

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Quel est la formule pour calculer la probabilité d’un algorithme biaisé amplifié?

A

q = 1 - (1-p)^k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Quel est la formule pour calculer la probabilité d’un algorithme non biaisé amplifié?

A

La somme des probabilités des cas ou la réponse favorable est majoritaire

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Expliquez la différence entre les classes de complexité NP et co-NP

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Existe-t-il des problèmes appartenant à la fois à P et à N P ? Justifiez.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Qu’est-ce qu’un problème NP-complet ?

A

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é.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Qu’entend-on par “cet algorithme a une consommation de ressource qui est pseudo-polynomiale” ?

A

Que sa complexité ne dépend pas seulement de la taille de l’exemplaire mais aussi de la magnitude des nombres en présence.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Le problème SAT est NP-complet ; quelle version restreinte de ce problème est par contre dans P?

A

2SAT, qui restreint chaque clause à contenir exactement 2 littéraux.
On acceptera aussi Horn-SAT.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Quelles sont les algorithmes de coloriage de graphe et leur complexité?

A

Heuristique constructif

  • Algorithme vorace naïf -> O(n^2)
  • Algorithme de DSATUR (plus contraignant en premier) -> O(n^2)
20
Q

Décrivez les décisions de conception pour utiliser une heuristique d’amélioration locale.

A
  1. Conception d’une heuristique pour la construction de la solution initiale S
  2. Conception d’un voisinage V pour la solution S
  3. Décider du critère d’arrêt à chaque itération : Première solution améliorante ou la meilleure solution
21
Q

Qu’est-ce qu’un Algorithme Monte Carlo

A

Un algorithme qui retourne une valeur qui n’est pas nécessairement correcte

22
Q

Qu’est-ce qu’un Algorithme numérique probabiliste

A

Un algorithme qui un interval qui n’est pas nécessairement bonne

23
Q

Qu’est-ce qu’un Algorithme Las Vegas?

A

Un algorithme qui retourne la bonne réponse. Cependant, il ne retourne pas toujours

24
Q

Qu’est-ce qu’un Algorithme Sherwood

A

Un algorithme Las Vegas (qui retourne la réponse) mais qui retourne tout le temps.

25
Q

Qu’est-ce qu’on entend par l’amplification de l’avantage stochastique ?

A

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é.

26
Q

Qu’est-ce qui distingue une métaheuristique à base de trajectoire d’une
métaheuristique à base de population ?

A

La première maintient une seule solution courante alors que la seconde en maintient un grand nombre.

27
Q

Quelles opérations fait-on sur un algorithme génétique

A

Croisement et mutation

28
Q

Définissez la classe P

A

C’est l’ensemble des problèmes de décision qu’on peut résoudre en temps polynomial dans la taille de l’exemplaire.

29
Q

Quel note Christophe doit avoir dans son examen poour passe Algo?

A

14.5/35

30
Q

Quel note Louis doit avoir dans son examen poour passe Algo?

A

13.5/35

31
Q

Comment prouver qu’un problème NPC est au moins aussi difficile qu’un problème NP?

A

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

32
Q

Que peut-on déduire d’un problème A qui se réduit en un problème B?

A

B est au moins aussi difficile que A

A <= B

33
Q

Qu’est-ce que l’algorithme Krukal

A

On ajoute toujours le plus petit arete à notre forest à condition qu’il ne forme pas de cycle.

34
Q

Quel est la complexité de Kruskal?

A

theta(a log(n))

a = arete

35
Q

Qu’est-ce que l’algorithme de Prim

A

On ajoute le plus petit arete à notre arbre à condition de ne pas former de cycle

36
Q

Quel est la complexité de Prim

A

theta(n^2)

37
Q

Les étapes pour créer un algorithme Glouton

A

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

38
Q

Comment prouver l’optimalité d’une fonction Glouton

A
  • Propriété de sous-structure optimale

- Propriété du choix Glouton

39
Q

Que peut-on déduire d’une fonction gluton sur un matroïde?

A

Qu’il est optimal

40
Q

Quand est-ce que l’on peut faire de la programmation dynamique?

A

Lorsque l’algorithme est optimal (principe de sous-strucutre optimale) ET des sous-strucutres de chevauche (répétitions)

41
Q

Quelles sont les 5 étapes pour construire un algorithme dynamique

A 
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
42
Q

Qu’est-ce qu’un algorithme branch-and-bound?

A

À chaque noeud, je vérifie si le potentiel de continuer va battre mon maximum actuel avant de procéder

43
Q

Qu’est-ce que P?

A

Classe de problèmes à complexité polynomial

44
Q

Qu’est-ce que NP?

A

Classe de problèmes à complexité polynomial qui se répond à l’affirmatif

45
Q

Qu’est-ce que Co-NP?

A

Classe de problèmes à complexité polynomial qui se répond au négatif

46
Q

Qu’est-ce que le problème SAT

A

Le problème des booléans

47
Q

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

A

Si O(p(n,1/epsilon))

Algorithme (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions