Objectifs

• Comprendre la structure et les opérations de base sur une liste.
• Savoir décrire un algorithme en langage naturel clair et le traduire en Python.
• Réaliser des algorithmes simples: somme, maximum, comptage, filtrage, tri élémentaire.

Définition et notation

Une liste est une collection ordonnée d'éléments. On note souvent une liste par exemple L = [a1, a2, a3, ..., an]. En Python, une liste s'écrit de la même manière: L = [1, 4, 7].

Indexation

Important: en langage naturel on peut compter à partir de 1. En Python, les indices commencent à 0. Ainsi L[0] est le premier élément, L[i] désigne l'élément d'indice i (0 ≤ i < len(L)).

Opérations courantes sur les listes

• Accès à un élément: L[i]
• Longueur: n = len(L) (nombre d'éléments)
• Parcours: examiner chaque élément dans l'ordre (for ou while)
• Ajout/suppression: append, insert, pop, remove (en Python)
• Concaténation et sous-listes: L[a:b] en Python

Principes pour rédiger un algorithme en langage naturel

• Définir précisément les entrées et la sortie.
• Donner les invariants (ce qui reste vrai à chaque étape importante).
• Utiliser des étapes numérotées, décrire l'initialisation, la boucle, et la terminaison.
• Éviter l'ambiguïté: préciser indices (0-based ou 1-based), sens du parcours, condition d'arrêt.

Exemples d'algorithmes en langage naturel

1) Somme des éléments d'une liste

Entrée: une liste de nombres L de taille n. Sortie: la somme S des éléments.

Algorithme:

1. Initialiser S ← 0 et i ← 0.
2. Tant que i < n: faire S ← S + L[i]; i ← i + 1.
3. Retourner S.

2) Recherche du maximum

Entrée: liste L non vide. Sortie: valeur maximale m.

1. Initialiser m ← L[0] et i ← 1.
2. Tant que i < n: si L[i] > m alors m ← L[i]; i ← i + 1.
3. Retourner m.

3) Compter les occurrences d'une valeur x

Entrée: liste L et valeur x. Sortie: compteur c.

1. Initialiser c ← 0 et i ← 0.
2. Tant que i < n: si L[i] = x alors c ← c + 1; i ← i + 1.
3. Retourner c.

4) Filtrer les éléments pairs

Entrée: liste L. Sortie: liste P contenant les éléments pairs dans le même ordre.

1. Initialiser P ← [] et i ← 0.
2. Tant que i < n: si L[i] est pair alors ajouter L[i] à P; i ← i + 1.
3. Retourner P.

Traduction en Python

Pour chaque algorithme, on traduit les étapes en instructions Python claires.

Somme

# Entrée: L liste de nombres
# Sortie: somme des éléments

def somme(L):
    S = 0
    for x in L:
        S += x
    return S

Maximum

# Entrée: L liste non vide
# Sortie: maximum

def maximum(L):
    m = L[0]
    for x in L[1:]:
        if x > m:
            m = x
    return m

Compter occurrences

# Entrée: L liste, x valeur
# Sortie: nombre d'occurrences de x

def compter(L, x):
    c = 0
    for y in L:
        if y == x:
            c += 1
    return c

Filtrer pairs

# Entrée: L liste d'entiers
# Sortie: liste des éléments pairs

def filtrer_pairs(L):
    P = []
    for x in L:
        if x % 2 == 0:
            P.append(x)
    return P

Tri élémentaire: tri par sélection (selection sort)

Idée: pour chaque position i de 0 à n-2, trouver le plus petit élément parmi les positions i..n-1 et l'échanger avec l'élément en i.

Algorithme en langage naturel

1. Pour i de 0 à n-2:
2.   min_index ← i
3.   Pour j de i+1 à n-1: si L[j] < L[min_index] alors min_index ← j
4.   Échanger L[i] et L[min_index] si min_index ≠ i
5. Fin pour

Implémentation Python

def tri_selection(L):
    n = len(L)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if L[j] < L[min_index]:
                min_index = j
        if min_index != i:
            L[i], L[min_index] = L[min_index], L[i]
    return L

Complexité: ce tri est en O(n²) en temps, utile pour comprendre le principe mais peu efficace pour de grandes listes.

Bonnes pratiques et remarques

• Tester vos algorithmes sur des listes vides, de taille 1, et des cas variés (déjà triée, inversée, avec doublons).
• Vérifier les indices (0-based en Python) pour éviter les erreurs hors bornes.
• Préférer les constructions pythonic (par exemple sum(L), max(L), compréhensions de liste) lorsque c'est permis, mais savoir écrire l'algorithme sous-jacent est essentiel.

Exercices rapides

1. Écrire en langage naturel puis en Python une fonction qui renvoie la moyenne des éléments d'une liste non vide.
2. Écrire une fonction qui supprime toutes les occurrences d'une valeur donnée dans une liste et renvoie la nouvelle liste.
3. Modifier le tri par sélection pour trier en ordre décroissant.