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 :

Muhammad Ibn Mūsā al-Khuwārizmī

• Qu'est-ce qu'un algorithme ? Proposez une définition :

C'est une procédure de calcul bien définie qui prend en entrée une valeur ou un ensemble de valeur, et qui donne en sortie une valeur ou un ensemble de valeur.

• Dans quel langage exprime-t-on un algorithme :

On utilise un langage dit "langage naturel" ("tant que", "si"...)

• 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 :

C'est une représentation graphique normalisée utilisée pour analyser ou décoder un problème.

- logigramme¶

• https://signoret-col.spip.ac-rouen.fr/spip.php?article924 -

• Que devez vous faire si on vous demande d'implémenter un algorithme ?

On doit écrire une version exécutable sur une machine à l'aide d'un langage de programmation

• Qu'est-ce que la complexité d'un algorithme ?

C'est le nombre d'opérations élementaires qu'il doit effectuer pour mener a bien un calcul

• Quels types de complexité distingue-t-on pour un algorithme ?

Il y a la complexité spatiale et la complexité temporelle

• Comment mesure-t-on la complexité d'un algorithme ?

On mesure alors la complexité en temps d'un algorithme

• A quoi correspond la complexité du pire des cas ?

Elle mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles.

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

In [2]:

def maFonction(t, x) :
    tr = False
    i = 1
    while i <= len(t) and tr == False :
        if t[i]== x :
            tr = True
        else :
            i = i+1
            break
    return tr

def maFonction(t, x) : tr = False i = 1 while i <= len(t) and tr == False : if t[i]== x : tr = True else : i = i+1 break return tr

Vérifier le bon fonctionnement de votre fonction :¶

In [3]:

maFonction([5,8,15,53], 15)

maFonction([5,8,15,53], 15)

Out[3]:

False

In [4]:

maFonction([5,8,15,53], 12)

maFonction([5,8,15,53], 12)

Out[4]:

False

Puis mesurer le temps d'exécution de votre programme avec timeit :¶

In [6]:

%timeit maFonction([5,8,15,53], 15)

%timeit maFonction([5,8,15,53], 15)

426 ns ± 0.363 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [7]:

%timeit maFonction([5,8,15,53], 12)

%timeit maFonction([5,8,15,53], 12)

433 ns ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [8]:

%timeit maFonction([5,8,15,53], 5)

%timeit maFonction([5,8,15,53], 5)

427 ns ± 2.63 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Est-ce que ces résultats sont logiques ? Expliquez pourquoi ?

Non, ils ne sont pas logiques car le resultat ne depend pas du dernier nombre.

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

Oui, car cela prend plus de temps a s'executer.

In [9]:

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78], 5)

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78], 5)

478 ns ± 0.171 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [10]:

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78, 500, 87, 25, 14, 35,74], 5)

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78, 500, 87, 25, 14, 35,74], 5)

534 ns ± 14.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [11]:

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78, 7888888, 25, 35], 5)

%timeit maFonction([5,8,15,53, 69, 57, 24, 35, 78, 7888888, 25, 35], 5)

497 ns ± 0.14 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

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
i ← len(t)
tant que i < i+1:
    si i > i+1

    fin si
        i > i+1
renvoyer la valeur max de i
FIN

...



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

In [1]:

t = [3,5,1,8,4,2]
def fonction(t) :
    max=t[0]
    longueur= len(t)
    for i in range(longueur):
        if t[i] >= max:
            max=t[i]
    return max
fonction(t)

t = [3,5,1,8,4,2] def fonction(t) : max=t[0] longueur= len(t) for i in range(longueur): if t[i] >= max: max=t[i] return max fonction(t)

Out[1]:

8

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
total : 0
longeur : t

DEBUT

pour i tant que longueur :
total : total + t[i]
renvoyer total / longueur
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é

votre algorithme.

Enfin programmez une fonction Python correspondante à votre algorithme puis mesurez son temps d'exécution et vérifiez sa complexité...

In [26]:

t = [3,5,1,8,4,2]
def ma_fonction(m):
    total= 0
    longueur=len(t)
    for i in range(longueur):
        total= total + t[i]
    return total / longueur
ma_fonction(t)

t = [3,5,1,8,4,2] def ma_fonction(m): total= 0 longueur=len(t) for i in range(longueur): total= total + t[i] return total / longueur ma_fonction(t)

Out[26]:

3.8333333333333335

---

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.

Ressources :¶

Pour mesurer un temps d'exécution, Python dispose d'une bibliothèque dédiée : timeit

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 :

In [12]:

?timeit

?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

In [ ]: