4.2- Algorithme : instruction répétition/itération 4.

2- Algorithme : instruction répétition/itération

(TD2)
Boucle while (itération) – Syntaxe Python Instructions répétitions : boucle while
Boucle de base Voir TD2 notebook
# initialisation nécessaire
while condition :
bloc_a_repeter_avec_modification_de_la_condition

# on entre dans la boucle si la condition est évaluée à Vrai

# on sort quand la condition passe à Faux
# si elle est à Faux dès le départ, on ne rentre pas dans la boucle
# si elle ne change jamais on a une boucle infinie

# ATTENTION : les variables qui interviennent dans la condition quelles soient simples ou
complexes doivent être initialisées avant et modifiées pendant l’exécution des
instructions du bloc

10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 53 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 54

4.2- Algorithme : instruction répétition/itération 5- Algorithme : structures de données

Instructions répétitions : boucle do … while - Que faire si on veut suivre une trajectoire carrée en faisant varier la
Non implémenté directement en python contrairement au langage C dimension du côté en fonction d’une liste de valeurs : 1, 2, 3 … mètres ?
On peut écrire du code qui a le même comportement. Que fait ce code python ? - il faut disposer de la liste des valeurs
- soit la liste peut être obtenue avec une itération
code = "163903" else : print("erreur")
nb_tentatives = 0 POUR D de VAL1 à VAL2 PAS P
if code != essai_code and nb_tentatives > 3:
while True : print("échec") les valeurs successives de D peuvent être considérées comme les
essai_code = input( "Saisie du code ? :") break;
nb_tentatives = nb_tentatives+1
différentes valeurs à prendre en compte
if code == essai_code: - soit la liste est fournie en entrée
print("code bon")
break; lue au clavier ou dans un fichier ou bien calculée
è il faut pouvoir traiter des collections de données
11/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 55 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 56
5.1- Structures de données : TABLEAU 5.1- Structures de données : TABLEAU
Premier type de collection de données : le TABLEAU Lien entre TABLEAU et boucle POUR
Définition algorithmique : ensemble de données de même type (homogène) Indice chaque élément du tableau (ou ‘case’) est désignée par le nom du
tableau et son indice. Exemple :TAB[1]
Déclaration d’un tableau
grâce à une boucle POUR, on peut appliquer le même traitement à
allocation d’un espace mémoire d’une certaine taille tous les éléments du tableau
à pour stocker un nombre MAXIMUM d’éléments
et d’un certain type POUR I de 1 à 6 FAIRE # I prend successivement les valeurs 1, 2, …6
LIRE(TAB[I]); # et permet de parcourir tout le tableau
à tous les éléments sont du même type (ont la même taille) et sont
considérés comme des variables « agglomérées » accessibles via un Fin POUR
indice
1 2 3 4 5 6 1 2 3 4 5 6
19 25 7 -4 9 0
TAB : Tableau[1..6] entiers;
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 57 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 58

5.1- Structures de données : TABLEAU 5.1- Structures de données : TABLEAU

Lien entre TABLEAU et boucle TANT QUE Que faut-il savoir d’autre sur les TABLEAUX ?
On peut également faire le même traitement avec une boucle TANT QUE … MAIS il ATTENTION : un tableau peut ne pas être complètement rempli !!!
faut : - initialiser la variable qui va servir d’indice,
à si on ne sait pas a priori combien il contiendra d’éléments
- gérer son incrémentation
à il faut garder la trace du remplissage avec une variable dédiée
- vérifier la condition pour continuer ou arrêter le traitement
à la valeur maximale ne pourra pas excéder la TAILLE max
I = 1 ; # initialisation
TANT QUE (I <= 6) FAIRE # arrêt quand I sera = à 7 Bonnes pratiques : certains langages ne contrôlent pas cela, c’est donc à la charge de la
LIRE(TAB[I]); # et permet de traiter un élément personne qui programme de vérifier qu’il n’y a pas de dépassement
I = I + 1; # incrémentation … va modifier la condition dans le code qui a été écrit
Fin TANT QUE Suivant les langages le premier indice commence à 0 et non à 1, suivant le cas donc il ne
faut pas dépasser TAILLE-1 ou TAILLE
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 59 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 60
5.1- Structures de données : TABLEAU 5.1- Structures de données : TABLEAU
Algorithme : Gestion du remplissage potentiellement incomplet d’un tableau
# Déclarations Quelles sont les différentes étapes de cet algo ? Exercice
TAB : Tableau[1..6] entier;
nb_elements, indice, reponse : entier; Détailler les valeurs des variables, contenu du Donner une nouvelle version (version 6) de l’algorithme pour une succession de
continuer_ok : booleen; tableau et le résultat pour l’exécution suivante trajectoires carrées (5 maximum) de côté variables. Les valeurs des côtés à prendre en
Début compte seront lues au clavier avant de tracer l’ensemble des trajectoires.
continuer_ok ß Vrai; indice ß 1; Donner les éléments du tableau un à un
ECRIRE(‘’Donner les éléments du tableau un à un ’’); 15 On tiendra compte du fait que la commande avancer peut-être déclinée en
TANT QUE (continuer_ok and indice <= 6) FAIRE Voulez-vous continuer (O/N) ?: O
LIRE(TAB[indice]); 12 avancer(distance)
indice = indice + 1; Voulez-vous continuer (O/N) ?: O avec distance = nombre de mètres a faire en ligne droite
ECRIRE(’’Voulez-vous continuer (O/N) ?: ’’ ); 1
LIRE(reponse); Voulez-vous continuer (O/N) ?: N avancer(1) est équivalent à avancer dans les algos précédents
SI reponse = ‘N’ ALORS continuer_ok = Faux …
Fin TANT QUE
Initialisation : le robot est orienté dans la première direction à prendre. Le point de
nb_elements = indice – 1; Modifier l’algo pour écrire le contenu du tableau à départ de chaque trajectoire est toujours le même.
ECRIRE(’’le tableau compte ‘’, nb_elements, ‘’ éléments); l’écran
Fin
10/09/2023
Ecrire une autre version de cette partie
UPSSITECH - SRI - Algorithmique et Programmation 61 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 64

5.1- Structures de données : TABLEAU 5.1- Structures de données : TABLEAU

Que faut-il savoir d’autre sur les TABLEAUX ? Que faut-il savoir d’autre sur les TABLEAUX ?
Un tableau peut avoir plusieurs dimensions. Un tableau a un type donné d’éléments
- valeurs numériques
• Une dimension permet de représenter un vecteur de TAILLE éléments
TAB vecteur[1..5] : entier; # ou TAB vecteur[5] : entier; entiers, réels, …: 0, 0.0, -15, -1.5, 25, 25.56

- valeurs alphanumériques
• Deux dimensions correspondent à la représentation de type matrice (au sens mathématique) ou plus
largement à un tableau de tableaux, tout dépend du type des éléments. caractères, chaines de caractères : 'a' , '0', "exemple"
TAB matrice[3,4] : entier; # ou TAB matrice[3][4] : entier; - valeurs structurées
TAB matrice[3,4] : entier; # ou TAB matrice[3][4] : entier;
tableaux, structures, types définis (structures de données avancées)
• On peut bien sûr avoir plus de 2 dimensions pour représenter des structures plus complexes comme
des tableaux multidimensionnels : tenseurs (au sens mathématique) ou tableaux de tableaux de [0,15,45,32]
tableaux,… { "Dupond", "Marcel", 21 }
TAB tenseur[3,4,3] : entier; # ou TAB tenseur[3][4][3] : entier; …
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 67 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 68
5.1- Structures de données : TABLEAU 5.1- Structures de données : TABLEAU
Que faut-il savoir d’autre sur les TABLEAUX ? Que faut-il savoir d’autre sur les TABLEAUX ?
i Attention : la gestion des tableaux est complètement différente entre le langage C et le
Tableau à 1 dimension indice i à élément T[i] langage PYTHON
j
indice ligne i indice colonne j
En C c’est une application stricte de la définition algorithmique
Tableau à 2 dimensions
i à élément T[i][j] - il n’y a pas de type tableau prédéfini
- une TAILLE_MAX doit être spécifiée lors de la déclaration (allocation statique)
Tableau à 3 dimensions - pas moyen de connaître la taille exacte sauf si c’est une chaîne de caractères

indice ligne i k - il ne faut pas la dépasser, mais aucun contrôle n’est fait à source d’erreur à l’exécution L
i
indice colonne j - l’intervalle des indices va de 0 à TAILLE_MAX-1
indice profondeur k
- les éléments sont de même type, on affiche/traite un tableau élément par élément
à élément T[i][j][k]
j
- …. (cf. cours programmation impérative)
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 69 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 70

5.1- Structures de données : TABLEAU 5.1.1- Tableaux en python via le type list
Que faut-il savoir d’autre sur les TABLEAUX ? Que faut-il savoir sur le type list ?

En PYTHON plusieurs options - les éléments sont repérés par un indice allant de 0 à longueur – 1
- l’indice est spécifié entre []
cela peut être représenté par un type prédéfini list plus générique
- l’utilisation d’indices invalides provoque la levée d’une exception (cf slide …)
et plus puissant. ma_liste2 = [13, 24, 35, 46, 57] # liste de 5 entiers
- le nombre d’éléments est déterminé en fonction de la valeur affectée ma_liste2[k] à k doit être compris entre 0 et len(ma_liste2)-1
ma_liste1 = [] # liste vide - l’élément d’indice i désigné par TAB[i] est le i+1ème élément de la liste
ma_liste2 = [13, 24, 35, 46, 57] # liste de 5 entiers
ma_liste3 = ['a', 'e', 'i', 'o', 'u', 'y'] # liste de 6 caractères

- il est accessible avec la fonction len()

len(ma_liste1) ? len(ma_liste2) ? len(ma_liste3) ?

10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 71 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 72
5.1.1- Tableaux en python via le type list 5.1.1- Tableaux en python via le type list
Que faut-il savoir d’autre sur le type list ? Que faut-il savoir d’autre sur le type list ?
c’est plus large qu’un simple tableau au sens algorithmique !!!
Mais c’est plus large que cela !!!
- il y a un contrôle sur le dépassement de la longueur de la liste J
- on peut tester l’appartenance d’une valeur à une liste avec l’opérateur in
au lieu de la rechercher élément par élément (comme en C) - on peut augmenter la taille d’une liste en lui ajoutant des éléments avec append
15 in TAB à renvoie un booléen (Vrai ou Faux) lst1 = [] # longueur de 0 = liste vide
for i in range(1,11):
- on peut aussi regrouper des éléments de types différents (éléments hétérogènes) [Link](i ** 2)
ma_liste4 = [1,1,2001, "Dupond", "Marc", "12345678"] # à chaque ajout on augmente la longueur de 1
# et on stocke la valeur de i au carré
print(lst1, len(lst1))
QUESTION : A quels éléments correspondent :
ma_liste4[0] ? ma_liste4[5] ? ma_liste4[7] ? QUESTION : Quelle est la valeur de la liste à l’issue de ce traitement ?
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 73 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 74

5.1.1- Tableaux en python via le type list 5.1.1- Tableaux en python via le type list
Que faut-il savoir d’autre sur le type list ? Structure de données de type list – syntaxe PYTHON
c’est plus large qu’un simple tableau au sens algorithmique !!! # Liste vide ma_liste = [] Question :
Quel est selon vous
Attention : # Ajout d’un élément en ma_liste.append(15) le résultat obtenu ?
fin de liste avec append print(ma_liste, len(ma_liste))
- le type list est une classe (cf. programmation orientée objet au S6)
- il y a des fonctions spécifiques dédiées appelées méthodes qui s’appliquent # Suppression d’un ma_liste = [5, 10, 15, 20]
élément suivant l’indice ma_liste.append(25)
directement à une instance de la classe (appelée objet) fourni avec pop : par print(ma_liste, len(ma_liste))
[Link](arguments) défaut dernier élément
sinon élément d’indice nb_out = [Link]()
à c’est le cas de append donné print(nb_out, len(ma_liste))
Nom_objet_list.append(valeur_a_ajouter)
nb_out = [Link](0)
print(nb_out, len(ma_liste))
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 75 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 76
5.1.1- Tableaux en python via le type list 5.1.1- Tableaux en python via le type list (TD3)
Structure de données de type list – syntaxe PYTHON Structure de données de type list – en python
# Suppression d’un élément nb_out = ma_liste.remove(15)
Question : Voir TD3 notebook
donné avec remove print(ma_liste, len(ma_liste)) Quel est selon vous
le résultat obtenu ?
# concaténation de deux ma_liste = ma_liste + [5, 15, 25]
listes avec + print(ma_liste, len(ma_liste))

# duplication de la liste ma_liste = ma_liste * 2

avec * print(ma_liste, len(ma_liste))

QUESTION : pour obtenir la liste [20, 40, 10, 30, 50 ] que faudrait-il faire ?

11/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 77 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 80

5.1.1- Tableaux en python via le type list 5.1.1- Tableaux en python via le type list
Que faut-il savoir d’autre sur le type list ? Que faut-il savoir d’autre sur le type list ?
c’est plus large qu’un simple tableau au sens algorithmique !!! c’est plus large qu’un simple tableau au sens algorithmique !!!
- une liste peut elle-même contenir des listes - une liste de liste de même taille permet de représenter un
ma_liste = [ 15, [1, 2, 3], 35, 45, [4, 5, 6, 7]] tableau à 2 dimensions (matrice 2D)
ma_liste = [ [1, 2, 3],[4, 5, 6], [7,8,9]]
ma_liste[0] ? ma_liste[3] ?
ma_liste[1] ? ma_liste[4] ? ma_liste[0] ? ma_liste[3] ?
ma_liste[2] ? ma_liste[5] ? ma_liste[1] ? ma_liste[1][1] ?
ma_liste[1][0] ? ma_liste[4][2] ? ma_liste[2] ? ma_liste[2][0] ?
ma_liste[2][1] ? ma_liste[4][4] ? ma_liste[0][0]? ma_liste[1][3] ?
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 81 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 82
5.1.1- Tableaux en python via le type list 5.1.1- Tableaux en python via le type list
Que faut-il savoir d’autre sur le type list ? Que faut-il savoir d’autre sur le type list ?
- on peut accéder à une sous liste à partir des infos suivantes c’est plus large qu’un simple tableau au sens algorithmique !!!
[d : f : p] avec d indice de début de la sous liste - cela peut aussi s’appliquer à des listes de données de types différents
f indice de fin non inclus ma_liste = [1,1,2001, ‘Dupond’, ‘Marc’, ‘12345678’]
p pas éventuel (1 par défaut)
ma_liste = [ 10, 15, 20, 25, 30, 35, 40] ma_liste[0:3] ? ma_liste[3:5] ?
ma_liste[0:len(ma_liste):2]) ? ma_liste[3:4] ?
ma_liste[1:6:2] ? ma_liste[0:3] ? ma_liste[::-1] ? ma_liste[::-3] ?
ma_liste[0:len(ma_liste):2] ? ma_liste[3:4] ?
ma_liste[::-1] ? ma_liste[::-2] è on sort de la définition algorithmique d’un tableau
10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 83 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 84

5.1.2- Tableaux en python via le type array 5.1.2- Tableaux en python via le type array
Que faut-il encore savoir d’autre sur les TABLEAUX ? Que faut-il savoir sur le type array de numpy ?

En PYTHON plusieurs options

import numpy as np # définition d’un alias np
cela peut être aussi être représenté par le type array si on importe la
bibliothèque numpy (non défini sinon) tableau = [Link]([1,2,3,4,5,6,7,8,9])
print(type(tableau))
à bibliothèque dédiée au calcul scientifique (logique, mathématique) sur les tableaux
print(tableau, id(tableau) )
représentant des vecteurs, des matrices, des tenseurs, …
indice = int(input())
à bien plus efficace dans ce cas que la manipulation du type list print(tableau[indice])

à permet le calcul vectoriel, matriciel et opérations d’algèbre linéaire

10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 85 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 86
5.1.2- Tableaux en python via le type array 5.1.2- Tableaux en python via le type array
Que faut-il savoir sur le type array de numpy ? Que faut-il savoir d’autre sur le type array de numpy ?
import numpy as np # définition d’un alias np

vecteur_zero = [Link](5)
… print(type(vecteur_zero), vecteur_zero, id(vecteur_zero))
print(tableau * 2) print([Link](vecteur_zero))

print(tableau, id(tableau)) print(vecteur_zero[0], type(vecteur_zero[0]))

tableau = tableau * 2

print(tableau, id(tableau))

10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 88 13/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 90

5.1.2- Tableaux en python via le type array 5.1.2- Tableaux en python via le type array
Que faut-il savoir d’autre sur le type array de numpy ? Que faut-il savoir d’autre sur le type array de numpy ?
import numpy as np # définition d’un alias np import numpy as np # définition d’un alias np

… matrice_identite = [Link](4)

vecteur_un = [Link](8) print(type(matrice_identite), matrice_identite, id(matrice_identite))

print(type(vecteur_un), vecteur_un, id(vecteur_un))
taille = [Link](vecteur_un) taille = [Link](matrice_identite)
print(taille, vecteur_un[taille-1], type(vecteur_un[taille-1])) ligne, colonne = [Link](matrice_identite)

print(ligne, colonne, matrice_identite[ligne-1][colonne-1], ‘\n’,

type(matrice_identite[ligne-1][colonne-1]))

13/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 92 10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 96
5.1.2- Tableaux en python via le type array
Que faut-il savoir d’autre sur le type array de numpy ?

Voir les TP …

10/09/2023 UPSSITECH - SRI - Algorithmique et Programmation 98