Algorithmique
Cette partie du programme introduit les principes de conception, d’analyse et d’optimisation des algorithmes, en abordant les structures de contrôle, la décomposition en sous-problèmes, la complexité, ainsi que des méthodes classiques de programmation et de résolution de problèmes.
Complexité linéaire et quadratique
Lorsqu'on cherche à résoudre un problème par un algorithme, il est essentiel de mesurer l'efficacité de celui-ci. La complexité permet d'estimer les ressources nécessaires (temps, mémoire) en fonction de la taille des données à traiter.
Protéger les variables constantes
Lorsqu'on récupère des données, par exemple depuis un fichier CSV, il est essentiel de protéger les variables qui doivent rester inchangées. Nous allons voir quelques bonnes pratiques simples pour éviter les erreurs involontaires.
Le jeu de la vie
Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.
Invariant de boucle
Quand on programme une boucle, il est souvent utile de pouvoir raisonner sur ce qui ne change pas pendant son exécution. C’est ce qu’on appelle un invariant de boucle.
Tri par sélection
Le tri par sélection est un algorithme de tri simple qui fonctionne en sélectionnant l'élément le plus petit (ou le plus grand) d'une liste et en le plaçant à la bonne position. Il est souvent utilisé pour illustrer les concepts de base des algorithmes de tri.