Cours de Algorithmique et programmation – Licence 1

Un algorithme est une suite finie et non ambiguë d'instructions qui résout un problème. Ce chapitre introduit les variables, les types de données, l'affectation, les entrées-sorties, la structure conditionnelle (si … alors … sinon) et les boucles (pour, tant que). Chaque notion est écrite en pseudo-code puis en Python, avec la trace d'exécution comme outil de vérification. Les exemples…

5 chapitres · exercices corrigés et quiz dans l'application

Programme : les chapitres

Chapitre à lire gratuitement : Variables et structures de contrôle

1. Algorithme, pseudo-code et programme

Définition : un algorithme est une suite finie d'instructions, exécutables mécaniquement, qui transforme des données d'entrée en un résultat. Il doit être non ambigu, terminer en un nombre fini d'étapes et produire un résultat correct.

Le pseudo-code est une écriture indépendante du langage, utilisée pour concevoir et expliquer. Un programme est la traduction d'un algorithme dans un langage comme Python. Nous écrivons chaque exemple dans les deux notations.

Méthode : avant d'écrire, on précise l'entrée, la sortie et l'idée de la solution ; on teste ensuite sur de petits exemples.

2. Variables, types et affectation

Une variable est un emplacement mémoire désigné par un nom, qui contient une valeur. Types usuels : entier (int), réel (float), booléen (bool), chaîne de caractères (str).

Affectation : en pseudo-code on écrit x ← 5 ; en Python x = 5. Elle évalue le membre de droite puis range le résultat dans la variable. L'instruction x ← x + 1 est donc légitime : elle augmente x de 1.

Opérateurs en Python : + − * / (division réelle), // (quotient entier), % (reste), ** (puissance). Comparaisons : ==, !=, <, <=, >, >=. Opérateurs logiques : and, or, not.

Exemple : 17 // 5 vaut 3, 17 % 5 vaut 2, et 17 == 5 * 3 + 2 est vrai.

Attention : = affecte, == compare. Écrire x = 5 dans une condition est une erreur classique.

3. Entrées-sorties

Pseudo-code : Lire n ; Écrire n.

Python : n = int(input('n = ')) lit un entier ; print(n) affiche.

La fonction input renvoie toujours une chaîne : il faut la convertir avec int ou float avant de calculer.

Exemple : calcul de l'aire d'un rectangle.

Lire L, l

aire ← L × l

Écrire aire

4. Structure conditionnelle

Pseudo-code :

Si condition alors

instructions

Sinon

autres instructions

Fin si

Python :

if condition:

instructions

elif autre_condition:

instructions

else:

instructions

L'indentation fait partie de la syntaxe de Python : elle délimite les blocs.

Exemple : mention selon la moyenne m.

if m >= 16: mention = 'très bien'

elif m >= 14: mention = 'bien'

elif m >= 12: mention = 'assez bien'

elif m >= 10: mention = 'passable'

else: mention = 'ajourné'

Les conditions sont évaluées dans l'ordre ; on place donc le test le plus restrictif en premier.

5. Boucles

Boucle pour (nombre d'itérations connu) :

Pseudo-code : Pour i de 1 à n faire … Fin pour

Python : for i in range(1, n + 1): … (range(1, n + 1) parcourt 1, 2, …, n).

Exemple : somme S = 1 + 2 + … + n.

S = 0

for i in range(1, n + 1):

S = S + i

Pour n = 100, on obtient 5 050, ce qui confirme la formule n(n + 1)/2.

Boucle tant que (nombre d'itérations inconnu) :

Pseudo-code : Tant que condition faire … Fin tant que

Python : while condition: …

La condition est testée avant chaque tour. Si elle ne devient jamais fausse, la boucle ne termine pas : on cherche un variant, quantité entière qui diminue strictement à chaque tour.

Exemple : algorithme d'Euclide pour le PGCD.

while b != 0:

a, b = b, a % b

Pour (252, 105) : (105, 42), puis (42, 21), puis (21, 0). Le PGCD est 21.

6. Trace d'exécution et invariant

La trace consiste à dresser un tableau des valeurs des variables après chaque tour. C'est la méthode de base pour comprendre et déboguer.

Un invariant de boucle est une propriété vraie avant et après chaque tour. Dans le calcul de S, après le tour i, S vaut 1 + 2 + … + i. À la sortie, i = n et S est la somme voulue.

Exemple de terminaison : pour la suite de Collatz (n pair devient n // 2, impair devient 3n + 1), on s'arrête quand n = 1. À partir de 6, il faut 8 étapes ; à partir de 27, il en faut 111. La terminaison est observée mais n'est pas démontrée en général.

7. Bonnes pratiques et pièges

• Initialiser toutes les variables avant de les utiliser, notamment les compteurs et les sommes.
• Éviter les boucles infinies : modifier dans le corps la variable testée par le while.
• Choisir des noms explicites (somme, compteur) plutôt que a, b, c.
• Tester les cas limites : n = 0, n = 1, valeur négative.
• Commenter les parties non évidentes avec # en Python.