Algorithmique et complexité :¶
A faire vous même :
Lire la page Introduction à l'algorithmique proposée par David ROCHE puis répondre aux questions suivantes :
- A qui attribue-t-on les premiers algorithmes :
...
- Qu'est-ce qu'un algorithme ? Proposez une définition :
...
- Dans quel langage exprime-t-on un algorithme :
...
- Rechercher sur le Web ce qu'est un algorigramme ? Proposez des synonymes puis collez ci-dessous un lien hypertexte, une image d'un exemple d'algorigramme :
...
- Que devez vous faire si on vous demande d'implémenter un algorithme ?
...
- Qu'est-ce que la complexité d'un algorithme ?
...
- Quels types de complexité distingue-t-on pour un algorithme ?
...
- Comment mesure-t-on la complexité d'un algorithme ?
...
- A quoi correspond la complexité du pire des cas ?
...
A coder vous même :
Implémenter l'algorithme suivant dans une fonction en Python :¶
/!\ en Python le premier élément d'un tableau a pour indice 0
pseudocode
VARIABLE
t : tableau d'entiers
x : nombre entier
tr : booléen (VRAI ou FAUX)
i : nombre entier
DEBUT
tr ← FAUX
i ← 1
tant que i<=longueur(t) et que tr==FAUX:
si t[i]==x:
tr ← VRAI
fin si
i ← i+1
fin tant que
renvoyer la valeur de tr
FIN
def maFonction(t, x) :
tr = False
return tr
Vérifier le bon fonctionnement de votre fonction :¶
maFonction([5,8,15,53], 15)
maFonction([5,8,15,53], 12)
Puis mesurer le temps d'exécution de votre programme avec timeit :¶
%timeit maFonction([5,8,15,53], 15)
%timeit maFonction([5,8,15,53], 12)
%timeit maFonction([5,8,15,53], 5)
Est-ce que ces résultats sont logiques ? Expliquez pourquoi ?
...
Mesurez le temps d'exécution de votre programme pour des tableaux de plus grande dimension.
Est-ce que ces résultats vérifient l'ordre de grandeur de sa complexité ?
...
A faire vous même :
Écrivez un algorithme permettant de trouver le plus grand entier présent dans un tableau.
pseudocode
VARIABLE
t : tableau d'entiers
...
DEBUT
...
renvoyer ...
FIN
Vous ferez "tourner à la main" votre algorithme en utilisant le tableau t = [3,5,1,8,4,2].
Vous déterminerez ensuite la complexité de votre algorithme.
Enfin programmez une fonction Python correspondante à votre algorithme puis mesurez son temps d'exécution et vérifiez sa complexité...
A faire vous même :
Écrivez un algorithme permettant de calculer la moyenne de tous les entiers présents dans un tableau.
pseudocode
VARIABLE
t : tableau d'entiers
...
DEBUT
...
renvoyer ...
FIN
Vous ferez "tourner à la main" votre algorithme en utilisant le tableau t = [3,5,1,8,4,2].
Vous déterminerez ensuite la complexité de votre algorithme.
Enfin programmez une fonction Python correspondante à votre algorithme puis mesurez son temps d'exécution et vérifiez sa complexité...
Références aux programmes :¶
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Parcours séquentiel d’un tableau | Écrire un algorithme de recherche d’une occurrence sur des valeurs de type quelconque. Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne. |
On montre que le coût est linéaire. |
Dans jupyter :
%timeit ma_fonction()
ou
%%timeit
i,r = 0,1
n = 5
while i <= n:
i = i + 1
r = r*i
Afficher l'aide :
?timeit
Ce document, basé sur le travail de David ROCHE, est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.
Pour toute question, suggestion ou commentaire : eric.madec@ecmorlaix.fr