calcul asymptotyque Flashcards
Quelles propriétés possède un algorithme? (5)
–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.
V ou F
Il ne peut y avoir qu’un seul algorithme pour résoudre un problème donné?
F
Quelles sont les spécification d’un organigramme? (2)
– 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.
Quelles sont les spécification d’un pseudocode? (2)
– 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 ==
Quelles sont les spécification d’un programme? (3)
– Dépend du langage de programmation
– Dépend des choix d’implémentation
– Est souvent optimisé, donc plus difficile à
comprendre
Quelles sont les spécification d’un algorithme? (4)
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
Quelle est l’utilité d’un algorithme? (5)
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
Pourquoi voudrait-on choisir l’algorithme le plus efficace? (2)
– Au point de vue de la vitesse d’exécution
– De la quantité de mémoire de travail utilisé
Qu’est qui entre en ligne de compte pour un algorithme?
La simplicité
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)
- Le type d’architecture de la machine
- L’implémentation
- Le multitâche
Algorithme(T[1..n])
- d = ∞
- pour i = 1 à n
- pour j = 1 à n
- si i ≠ j et |T[i] – T[j]| < d
- d = |T[i] – T[j]|
- retourner d
Que fait cet algorithme?
Combien de fois chaque ligne est exécutée?
pour réponse voir dia 25 à 28 du cours 1
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
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
Que détermine la notation O et quel est sa définition formelle?
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
VOIR DIA 32?
IMPORTANT??
Que cherche-t-on avec une Analyse d’un algorithme?
Cherche une fonction simple qui décrit le comportement de l’algorithme dans le pire cas.
– Exemples : O(n), O(n2), O(lg n)
L’analyse est simplifiée selon quelles règles ?
– Les constantes sont éliminées
– Seul le monôme avec le degré le plus élevé est conservé
Que détermine la notation omega et quel est sa définition formelle?
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
voir dia 38
Important?
Que détermine la notation -0 avec barre a l’intérieur et quel est sa définition formelle?
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
voir dia 41
important?
Qu’est-ce qu’un baromètre?
C’est une instruction qui s’exécute au moins autant de fois que chacune
des autres.
Comment fonctionne un baromètre? (3)
– 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
Comment choisir l’ensemble B? (3)
– 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.
Quelle est la Sélection des instructions des Baromètre&:
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
Combien d’algorithme de tri sont vue et nomme les?
3
Tri à bulle
Tri par sélection
Tri par insertion
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?
Je ne sais pas la réponse mais toi tu devrais
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
Je ne sais pas la réponse mais toi tu devrais
Sais- tu Déterminer expérimentalement la relation asymptotique entre deux fonctions?
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)
Voir dia 58
Important je crois que c’est un résumé!!!
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.
tu dois savoir la réponse moi je sais pas!
