calcul asymptotyque

Question 1

Quelles propriétés possède un algorithme? (5)

Answer 1

–doit être correct;
– doit être composé d’un ensemble
d’opérations concrètes;
– ne doit pas avoir d’ambigüité dans les
opérations;
– doit être composé d’un nombre fini d’étapes;
– doit terminer.

Question 2

V ou F

Il ne peut y avoir qu’un seul algorithme pour résoudre un problème donné?

Answer 2

F

Question 3

Quelles sont les spécification d’un organigramme? (2)

Answer 3

– Exprime un algorithme en utilisant un ensemble de
figures géométriques décrivant les différentes étapes de
l’algorithme.
– Cette représentation n’est presque plus utilisée.

Question 4

Quelles sont les spécification d’un pseudocode? (2)

Answer 4

– Mélange d’instructions de type « langage de
programmation » et de langage naturel
(français,anglais,…)
– Notation utilisée dans ce cours:
• Structures de contrôle : pour, tant que, si
• Assignation est représentée par un =
• Égalité représentée par ==

Question 5

Quelles sont les spécification d’un programme? (3)

Answer 5

– Dépend du langage de programmation
– Dépend des choix d’implémentation
– Est souvent optimisé, donc plus difficile à
comprendre

Question 6

Quelles sont les spécification d’un algorithme? (4)

Answer 6

Algorithme
– Ne contient aucun détail d’implémentation
– Ne contient pas de vérification des variables
d’entrées
– Indépendant du contexte d’implémentation (OS,
langage)
– Plus facile à comprendre

Question 7

Quelle est l’utilité d’un algorithme? (5)

Answer 7

Permet de prouver l’exactitude d’une solution
Permet de déterminer les détails d’implémentation
Permet d’estimer le temps de réponse et la mémoire
de travail utilisée
Permet de séparer le problème en plusieurs sousproblèmes
Fait office de documentation

Question 8

Pourquoi voudrait-on choisir l’algorithme le plus efficace? (2)

Answer 8

– Au point de vue de la vitesse d’exécution

– De la quantité de mémoire de travail utilisé

Question 9

Qu’est qui entre en ligne de compte pour un algorithme?

Answer 9

La simplicité

Question 10

Le temps d’exécution varie grandement d’un
ordinateur à un autre et même d’une exécution à
l’autre. Quel facteurs peuvent influencé le
temps d’exécution d’un algorithme? (3)

Answer 10

• Le type d’architecture de la machine
• L’implémentation
• Le multitâche

Question 11

Algorithme(T[1..n])

1. d = ∞
2. pour i = 1 à n
3. pour j = 1 à n
4. si i ≠ j et |T[i] – T[j]| < d
5. d = |T[i] – T[j]|
6. retourner d

Que fait cet algorithme?
Combien de fois chaque ligne est exécutée?

Answer 11

pour réponse voir dia 25 à 28 du cours 1

Question 12

quels sont les avantage et désavantage de l’Analyse détaillée de l’algorithme et de l’Analyse asymptotiquement du
comportement de l’algorithme lorsque le(s)
paramètre(s) de l’algorithme tend(ent) vers
l’infini

Answer 12

Analyse détaillée d’un algorithme:
– Avantage :Très précise
– Désavantage : Long à calculer

Analyser asymptotiquement
– Avantage: Facile à calculer
– Désavantage: Moins précis

Question 13

Que détermine la notation O et quel est sa définition formelle?

Answer 13

Détermine une borne supérieure

f(n) = O(g(n)) s’il existe deux constantes positives
n0 et c tel que f(n) <= cg(n) pour tout n>n0

Question 14

VOIR DIA 32?

Answer 14

IMPORTANT??

Question 15

Que cherche-t-on avec une Analyse d’un algorithme?

Answer 15

Cherche une fonction simple qui décrit le comportement de l’algorithme dans le pire cas.
– Exemples : O(n), O(n2), O(lg n)

Question 16

L’analyse est simplifiée selon quelles règles ?

Answer 16

– Les constantes sont éliminées

– Seul le monôme avec le degré le plus élevé est conservé

Question 17

Que détermine la notation omega et quel est sa définition formelle?

Answer 17

Détermine une borne inférieure
Définition formelle : f(n) = omega(g(n)) s’il existe deux constantes positives n0 et c tel
que cg(n) <= f(n) pour tout n>n0

Question 18

voir dia 38

Answer 18

Important?

Question 19

Que détermine la notation -0 avec barre a l’intérieur et quel est sa définition formelle?

Answer 19

Relation d’équivalence
Définition formelle : f(n) = Q(g(n)) s’il existe trois constantes positives n0,c1 et
c2 tel que c1g(n) <= f(n) <= c2g(n) pour tout n>n0

Question 20

voir dia 41

Answer 20

important?

Question 21

Qu’est-ce qu’un baromètre?

Answer 21

C’est une instruction qui s’exécute au moins autant de fois que chacune
des autres.

Question 22

Comment fonctionne un baromètre? (3)

Answer 22

– Sélectionne un ensemble d’instructions significatives B={b1…bk}
– Détermine le nombre d’exécutions de chacun des baromètres dans B
– Temps total est la somme du nombre d’exécutions de chaque baromètre

Question 23

Comment choisir l’ensemble B? (3)

Answer 23

– Mettre systématiquement certains types
d’instructions(boucles,conditions,etc.)
– Estimer leurs nombres d’exécution maxima et minima selon que l’on
calcule le meilleur ou le pire cas.
– Simplifier B en gardant seulement les instructions qui s’exécutent le plus
souvent.

Question 24

Quelle est la Sélection des instructions des Baromètre&:

Answer 24

Mettre dans B les instructions suivantes.
1. points d’entrée des fonctions.
2. boucles tant que.
3. conditionnels si.
4. une instruction au moins dans chaque bloc.
• bloc = ensemble d’instructions de même
indentation qui s’exécutent le même nombre de
fois.

voir exemple dia 47

Question 25

Combien d’algorithme de tri sont vue et nomme les?

Answer 25

3
Tri à bulle
Tri par sélection
Tri par insertion

Question 26

Dans le pire des cas et avec le même nombre de données à trier, est-ce que le temps d’exécution sera identique?

Answer 26

Je ne sais pas la réponse mais toi tu devrais

Question 27

Quel est l’ordre de cet algorithme?
Algorithme(T[1..n])
1. sum = 0
2. x = 1
3. tant que i < n
4. sum = sum+T[x]
5. x = x*2
6. retourner sum

Answer 27

Je ne sais pas la réponse mais toi tu devrais

Question 28

Sais- tu Déterminer expérimentalement la relation asymptotique entre deux fonctions?

Answer 28

2 fonctions inconnues f(n) et g(n).
– Fonctions positives non décroissantes.
– Arguments positifs.
On a un échantillon des valeurs de f(n) et de
g(n) pour plusieurs points n = {n1, n2…..}.
– On peut avoir plusieurs valeurs de f(n) et g(n)
pour le même n.
Tracer un graphe f(n) vs g(n). (voir dia 56)

Question 29

Voir dia 58

Answer 29

Important je crois que c’est un résumé!!!

Question 30

Supposons que nous avons un tableau de n+1
éléments. Ce tableau contient tous les nombres
de 1 à n. Donc, il y a un nombre qui revient
deux fois.
Donner un algorithme qui permet de trouver le
doublon en inspectant chaque case une seule
fois et qui est O(1) pour l’espace mémoire
utilisée.

Answer 30

tu dois savoir la réponse moi je sais pas!