Algorithmique et programmation en 1ère
Cours complet, points clés à retenir et exercices d'entraînement de algorithmique et programmation pour les élèves de 1ère. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Parcours séquentiel d'un tableau, recherche dichotomique
- Algorithmes de tri : tri par sélection, tri par insertion
- Algorithmes gloutons (rendu de monnaie)
- k plus proches voisins (kNN) : principe et applications
- Notion de complexité algorithmique (intro)
Parcours séquentiel d'un tableau
C'est parcourir tous les éléments d'un tableau un par un, du premier au dernier, pour effectuer une action sur chacun. On utilise généralement une boucle for ou while.
Exemple
Vérifier tous les devoirs d'une classe pour voir qui a rendu son travail : tu regardes chaque nom dans la liste, l'un après l'autre.
À retenir : Le parcours séquentiel examine chaque élément exactement une fois, dans l'ordre.
Recherche dichotomique
Méthode rapide pour trouver un élément dans un tableau trié en divisant l'espace de recherche par deux à chaque étape. On compare avec l'élément du milieu et on élimine la moitié inutile.
Exemple
Chercher un mot dans un dictionnaire : au lieu de lire page par page, tu ouvres au milieu, tu vois si le mot est avant ou après, et tu recommences dans la bonne moitié.
À retenir : La recherche dichotomique est beaucoup plus rapide qu'une recherche linéaire sur un tableau trié.
Tri par sélection
Algorithme de tri qui fonctionne en trouvant le plus petit élément, en le plaçant au début, puis en répétant l'opération sur le reste du tableau.
Exemple
Ranger tes cartes à jouer : tu cherches la plus petite, tu la mets à gauche, puis tu cherches la plus petite parmi les restantes, et ainsi de suite.
À retenir : Le tri par sélection fait plusieurs passages et place chaque élément à sa bonne position définitive.
Tri par insertion
Algorithme de tri qui construit le tableau trié élément par élément en insérant chaque nouvel élément à sa bonne place parmi les éléments déjà triés.
Exemple
Ranger des cartes à jouer en main : tu prends une carte, tu la places au bon endroit parmi celles que tu tiens déjà triées.
À retenir : Le tri par insertion est efficace pour les petits tableaux et les données presque triées.
Algorithmes gloutons
Stratégie qui fait le meilleur choix à chaque étape sans revenir en arrière, en espérant obtenir une bonne solution globale. On prend toujours ce qui semble optimal maintenant.
Exemple
Rendre la monnaie avec le moins de pièces : tu utilises d'abord les plus grandes pièces possibles, puis les plus petites. Tu ne reviens jamais en arrière.
À retenir : Un algorithme glouton est rapide mais ne garantit pas toujours la meilleure solution possible.
Algorithme des k plus proches voisins
Méthode de classification qui prédit la catégorie d'un élément en regardant les k éléments les plus proches de lui dans les données connues et en prenant la catégorie la plus fréquente.
Exemple
Prédire le genre d'un film : tu regardes les 5 films les plus similaires à celui-ci et tu comptes combien sont des comédies, drames, etc. Tu choisis la catégorie la plus fréquente.
À retenir : L'algorithme k-NN est simple mais nécessite de calculer les distances avec tous les éléments connus.
Spécification et tests avec assert
Spécifier un programme c'est écrire clairement ce qu'il doit faire. Les assertions sont des vérifications qui s'arrêtent si une condition n'est pas respectée, utiles pour tester.
Exemple
Avant d'écrire une fonction qui calcule la moyenne, tu dis : elle prend une liste de nombres et retourne un nombre. Tu ajoutes assert pour vérifier que le résultat est correct.
À retenir : Les assertions aident à détecter les erreurs rapidement pendant le développement.
Modularité : fonctions et modules
Diviser un programme en petites parties indépendantes (fonctions, modules) qui font chacune une tâche précise. Cela rend le code plus lisible, réutilisable et facile à tester.
Exemple
Au lieu d'écrire un gros programme pour gérer un jeu, tu crées une fonction pour afficher le plateau, une pour vérifier les coups valides, une pour calculer le score.
À retenir : La modularité rend le code plus facile à comprendre, maintenir et déboguer.
Bibliothèques et imports
Une bibliothèque est un ensemble de fonctions et outils déjà programmés qu'on peut utiliser dans son code. On les importe avec import ou from...import.
Exemple
Au lieu de programmer toi-même comment calculer une racine carrée, tu utilises la bibliothèque math avec math.sqrt().
À retenir : Les bibliothèques évitent de réinventer la roue et offrent des outils testés et optimisés.
Les points clés
- Le parcours séquentiel est la base : on examine chaque élément une fois
- La recherche dichotomique est rapide mais demande un tableau trié
- Les tris par sélection et insertion ont des complexités différentes selon les données
- Les algorithmes gloutons sont rapides mais ne donnent pas toujours la solution optimale
- Les assertions permettent de vérifier que le code fonctionne correctement
- La modularité (fonctions, modules) rend le code maintenable et réutilisable
L'essentiel
Bien choisir son algorithme selon le problème : un algorithme rapide mais glouton peut être moins bon qu'un algorithme plus lent mais optimal, et toujours tester avec des assertions.
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_max(tableau)` qui parcourt séquentiellement un tableau et retourne l'indice de l'élément maximum. Teste ta fonction avec l'assertion suivante : `assert recherche_max([3, 7, 2, 9, 1]) == 3`
Corrige cet exercice avec le tuteur →Exercice 2
Implémente l'algorithme de tri par insertion pour trier un tableau en ordre croissant. Explique le principe en 3-4 lignes, puis fournis le code avec des assertions de test.
Corrige cet exercice avec le tuteur →