Parcours séquentiel d'un tableau
Algorithmique
Plan
Parcourir un tableau
Pour rappel voici les deux méthodes pour parcourir un tableau constitué d'une liste.
A partir des index:
for i in range(len(liste)):
print(liste[i])
en prenant directement l'élément de la liste...mais on ne connait pas son index:
for element in liste:
print(element)
Pour ranger des éléments on aura besoin de connaitre son emplacement donc son index, mais pour faire une moyenne il nous faut que la valeur et non son emplacement. On privilégie la méthode par élément lorsque c'est possible car plus lisible.
Notion de complexité
Le problème de la complexité temporelle (le temps mis par le programme) est fondamental en informatique. Sur un petit exercice contenant seulement 20 valeurs, les ranger dans l'ordre croissant sera très rapide quel que soit la méthode. Mais s'il faut répéter cela des milliers de fois ou que la taille de la liste est de 50000 valeurs, la qualité de l'algorithme est très importante. Entre l'algorithme le plus performant et le moins performant nous aurons un écart de 15 fois meilleur (dans le pire des cas) pour 20 valeurs et de 10640 fois pour 50000 valeurs!
Nous ne nous intéresserons pas à la complexité spatiale (la place occupée sur le disque pour traiter le problème), par défaut le mot complexité sous-entendra complexité temporelle.
Pour évaluer la complexité d'un algorithme on calcule le nombre d'étapes (comparaisons, calculs, affectations) nécessaires pour n données.
Par exemple, pour afficher toutes les valeurs d'un tableau, on lit chaque valeur une fois...il y a donc n étapes. On dit que l'algorithme est d'ordre n et on note O(n) selon la notation de Landau. Si je dois afficher la somme deux à deux, de tous les termes successifs avec un Algorithme qui lit une valeur et la suivante et effectue l'addition: cela fait 3 étapes à répéter n-1 fois. Le 3 ne dépend pas de n, la complexité est donc de l'ordre de 3(n-1)=3n-3. C'est linéaire (en fait affine si l'on pense fonction) à une constante près et en termes de complexité on va considérer que le -3 et le coefficient 3 ne sont pas importants. On dira encore que notre complexité est O(n). Une complexité en O(n) est dite linéaire.
Si le calcul d'une complexité nous amène à un ordre de 4n²+3n+1 on dira que la complexité est un O(n²). Une complexité d'ordre O(n²) est une complexité quadratique.
Une complexité de l'ordre O(nlog(n)) est dite quasi-linéaire.
On peut s'intéresser à la complexité d'un algorithme dans: le meilleur des cas, le cas moyen et le pire des cas.
Dans le cas du tri, on arrive à prouver mathématiquement la meilleure complexité atteignable.
Calculer la moyenne d'un tableau
Cet exemple est très simple et déjà fait en exercice. Je donne l'algorithme et vous laisse établir que la complexité est linéaire en donnant le nombre exact d'étapes pour n valeurs dans la liste.
➦ initialiser total à 0
➦ pour tous les éléments de la Liste
➦ additionner l'élément à total
➦ diviser le total par le nombre d'éléments
Recherche de maximum
Cet exemple est simple aussi et déjà fait en exercice. Je donne l'algorithme et vous laisse établir que la complexité est linéaire en donnant le nombre exact d'étapes pour n valeurs dans la liste. Calculer le nombre exact d'étapes dans le meilleur des cas. Est-ce que cela change la complexité?
➦ initialiser maximum à l'élément 0 de la liste
➦ pour tous les éléments de la Liste à partir du 2nd
➦ si l'élément est plus grand que maximum
➦ mettre maximum à la valeur de élément
➦ afficher maximum
Recherche d'une valeur
Cet exemple est simple aussi et déjà fait en exercice. Pour préciser l'exercice on va supposer que l'on veut un booléen qui indique si un élément est dans une liste.
Comparer le nombre d'étapes des algorithmes 1 et 2 dans le meilleur et le pire des cas.Etes-vous capable de donner le nombre moyen d'étapes? Est-ce que les trois complexités trouvées sont les mêmes?
## Algorithme 1
➦ Soit T la valeur à trouver
➦ initialiser trouve à Faux
➦ pour tous les éléments de la Liste
➦ si l'élément = T
➦trouve = Vrai
➦ afficher trouve
## Algorithme 2
➦ soit T la valeur à trouver
➦ soit L la longueur de la liste
➦ initialiser trouve à Faux
➦ initialiser i à 0
➦ tant que i < L et élément i de liste pas égal à T
➦ incrémenter i
➦ si i < L alors
➦ trouve=True
➦ affiche trouve
Exercices
- Ecrire le programme qui calcule la moyenne d'un tableau en utilisant l'algorithme ci-dessus
- Ecrire le programme qui calcule le maximum et le minimum et l'étendue d'un tableau en utilisant l'algorithme ci-dessus
- Ecrire les programmes de recherche de valeur avec les deux algorithmes. Faire afficher le nombre d'étapes exécutées et comparer à la complexité. A-t-on autant d'étapes que celles évaluées sur la complexité ?
- Les langages informatiques ont des fonctions qui calculent la moyenne, le min, le max etc...alors pourquoi apprendre à le faire soit même? Imaginons que l'on cherche le max mais en dessous d'une valeur seuil? Codez une fonction qui cherche le maximum d'une liste en ne tenant pas compte des valeurs supérieures ou égales à 10.
Une liste contient des listes de coordonnées dans l'espace (x,y,z). On cherche le point le plus bas! Réalisez ce codage.
Une liste contient des listes de coordonnées dans l'espace (x,y,z). On cherche si un point de la liste a une abscisse donnée, ou une ordonnée données ou une profondeur donnée. On peut coder cela en une seule fonction.
