Algorithmique et programmation Python en 1ère
Cours complet, points clés à retenir et exercices d'entraînement de algorithmique et programmation python pour les élèves de 1ère. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Variables, affectation et types de données en Python
- Notion de liste et manipulation (append, slicing, compréhension)
- Boucles imbriquées et complexité
- Recherche dans une liste : parcours séquentiel, dichotomie
- Algorithmes de tri : tri par sélection, tri par insertion
- Fonctions : définition, paramètres, valeur de retour
- Instruction assert et jeux de tests
Variables, affectation et types de données
Une variable est une boîte qui stocke une valeur (nombre, texte, etc.). L'affectation, c'est mettre une valeur dans cette boîte avec le symbole =. Le type de donnée indique ce qu'on stocke : entier (int), nombre décimal (float), texte (str), vrai/faux (bool).
Exemple
Quand tu crées un compte sur un réseau social, tu rentres ton nom (str), ton âge (int), ta taille (float). Chaque information est une variable avec son type.
À retenir : En Python, on écrit x = 5 pour affecter la valeur 5 à la variable x, et type(x) nous dit que c'est un int.
Notion de liste et manipulation
Une liste est une collection ordonnée d'éléments entre crochets. On peut ajouter des éléments avec append(), extraire une partie avec le slicing (notation [début:fin]), ou créer une liste rapidement avec la compréhension de liste.
Exemple
Ta playlist Spotify est une liste de chansons. Tu peux ajouter une chanson (append), écouter les chansons 3 à 7 (slicing), ou créer une liste des chansons de moins de 3 minutes (compréhension).
À retenir : Une liste se note [1, 2, 3], on accède à l'élément i par liste[i], et on ajoute avec liste.append(valeur).
Boucles imbriquées et complexité
Les boucles imbriquées sont des boucles dans des boucles. Elles permettent de traiter des structures complexes, mais elles ralentissent le programme. La complexité mesure combien d'opérations le programme fait : avec deux boucles imbriquées de n éléments, on fait environ $n^2$ opérations.
Exemple
Pour vérifier tous les matchs possibles entre 10 joueurs de tennis, tu dois comparer chaque joueur avec chaque autre : 10 × 10 = 100 comparaisons. C'est une complexité quadratique.
À retenir : Deux boucles imbriquées donnent une complexité en $O(n^2)$ : c'est lent pour les grandes listes.
Recherche séquentielle dans une liste
La recherche séquentielle parcourt la liste élément par élément jusqu'à trouver ce qu'on cherche. C'est simple mais lent pour les grandes listes : on peut faire jusqu'à n comparaisons.
Exemple
Tu cherches le numéro de téléphone d'un ami dans un annuaire papier : tu lis page par page jusqu'à le trouver. Si la liste n'est pas triée, c'est la seule méthode.
À retenir : La recherche séquentielle a une complexité en $O(n)$ : elle parcourt toute la liste dans le pire cas.
Recherche par dichotomie
La dichotomie est une recherche rapide dans une liste triée. On coupe la liste en deux, on compare avec le milieu, et on garde seulement la moitié pertinente. On répète jusqu'à trouver l'élément.
Exemple
Tu cherches un mot dans le dictionnaire : tu ouvres au milieu, tu vois si ton mot est avant ou après, tu jettes la moitié inutile, et tu recommences. Beaucoup plus rapide que de lire page par page.
À retenir : La dichotomie a une complexité en $O(\log n)$ : elle divise par 2 à chaque étape, donc elle est très rapide.
Tri par sélection
Le tri par sélection cherche le plus petit élément, le met au début, puis recommence avec le reste. C'est simple à comprendre mais pas très rapide.
Exemple
Pour ranger tes cartes Pokémon par numéro : tu cherches la carte 1, tu la mets devant, puis tu cherches la carte 2 parmi les restantes, etc.
À retenir : Le tri par sélection a une complexité en $O(n^2)$ : il faut chercher le minimum n fois.
Tri par insertion
Le tri par insertion prend chaque élément et l'insère à la bonne place dans la partie déjà triée. C'est comme ranger des cartes dans ta main : tu ajoutes chaque nouvelle carte au bon endroit.
Exemple
Tu reçois des cartes une par une au poker : tu les ranges dans ta main en mettant chaque nouvelle carte à sa place parmi celles que tu as déjà.
À retenir : Le tri par insertion a une complexité en $O(n^2)$ en moyenne, mais il est rapide si la liste est presque triée.
Fonctions : définition, paramètres, retour
Une fonction est un bloc de code réutilisable qu'on définit une fois avec def. Elle peut prendre des paramètres (entrées) et retourner une valeur (sortie) avec return.
Exemple
Une fonction calculatrice : tu définis une fonction addition(a, b) qui prend deux nombres et retourne leur somme. Tu peux l'utiliser autant de fois que tu veux.
À retenir : On écrit def nom_fonction(param1, param2): et return valeur pour définir et utiliser une fonction.
Instruction assert et jeux de tests
L'instruction assert vérifie qu'une condition est vraie. Si elle est fausse, le programme s'arrête avec un message d'erreur. C'est un outil pour tester que ta fonction fonctionne correctement.
Exemple
Tu écris une fonction qui calcule la moyenne. Tu testes : assert moyenne([10, 20]) == 15. Si le résultat n'est pas 15, tu sais qu'il y a un bug.
À retenir : assert condition permet de vérifier que ton code fonctionne : c'est un test automatique.
Les points clés
- Les variables stockent des données avec un type (int, str, float, bool) et on les modifie avec l'affectation =
- Les listes se manipulent avec append(), slicing [i:j], et compréhension [x for x in liste]
- La complexité mesure la vitesse : $O(n)$ pour séquentiel, $O(n^2)$ pour boucles imbriquées, $O(\log n)$ pour dichotomie
- La dichotomie est beaucoup plus rapide que la recherche séquentielle, mais la liste doit être triée
- Les tris par sélection et insertion sont en $O(n^2)$ : simples mais lents pour les grandes listes
- Les fonctions rendent le code réutilisable et lisible : toujours les utiliser pour éviter la répétition
- assert permet de tester automatiquement que ta fonction donne le bon résultat
L'essentiel
En algorithmique, il faut toujours penser à la complexité : une bonne stratégie (dichotomie, bon tri) peut rendre un programme 1000 fois plus rapide.
Exercices d'entraînement
Entraîne-toi sur ces exercices, puis fais-toi corriger pas à pas par le tuteur.
Exercice 1
Écris une fonction recherche_dichotomie(liste, cible) qui cherche cible dans une liste triée et retourne son index (ou -1 si absent). Teste avec assert recherche_dichotomie([1, 3, 5, 7, 9], 5) == 2.
Corrige cet exercice avec le tuteur →Exercice 2
Écris une fonction tri_insertion(liste) qui trie une liste en place par insertion. Teste avec assert tri_insertion([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5].
Corrige cet exercice avec le tuteur →