CoursNumérique et sciences informatiques · tle
Comment résoudre efficacement des problèmes complexes ? La spécialité NSI de terminale approfondit l'algorithmique avec de grandes stratégies : diviser pour régner, les algorithmes gloutons et les graphes.
Le cours
« Diviser pour régner » est une stratégie qui consiste à découper un problème en sous-problèmes plus petits, à les résoudre séparément, puis à combiner les solutions. Cette approche permet de résoudre efficacement de nombreux problèmes (comme certains tris).
Diviser pour régner découpe le problème en sous-problèmes.
Un tri rapide découpe la liste en parties plus petites, qu'il trie séparément.
Un algorithme glouton construit une solution étape par étape, en faisant à chaque fois le choix qui semble le meilleur sur le moment. C'est simple et souvent rapide, mais cela ne donne pas toujours la solution optimale. Les gloutons sont efficaces dans certains cas.
Un glouton fait le meilleur choix immédiat à chaque étape.
Pour rendre la monnaie, un glouton choisit à chaque fois la plus grande pièce possible.
Un graphe est une structure faite de sommets reliés par des arêtes. Il modélise de nombreuses situations : réseaux (routes, internet, réseaux sociaux), liens entre éléments. Les graphes sont un outil puissant pour représenter et étudier des relations.
Un graphe modélise des éléments et leurs relations.
Un réseau social peut se modéliser par un graphe : les personnes sont les sommets, les liens les arêtes.
On peut parcourir un graphe pour explorer ses sommets, chercher un chemin entre deux points, ou trouver le plus court chemin. Ces algorithmes sur les graphes sont essentiels dans de nombreuses applications (itinéraires, réseaux, recommandations).
Parcourir un graphe permet de trouver des chemins.
Trouver le plus court chemin entre deux villes est un problème de parcours de graphe.
Ce qu'il faut absolument retenir
Vérifie ta compréhension
Exercice 1En quoi consiste la stratégie « diviser pour régner » ?
« Diviser pour régner » découpe un problème en sous-problèmes plus petits, les résout séparément, puis combine les solutions.
Exercice 2Comment fonctionne un algorithme glouton ?
Un algorithme glouton construit une solution en faisant à chaque étape le choix qui semble le meilleur sur le moment.
Exercice 3Qu'est-ce qu'un graphe ?
Un graphe est une structure faite de sommets reliés par des arêtes, qui modélise des éléments et leurs relations.
Exercice 4Un algorithme glouton donne toujours la solution optimale.
Faux : un glouton est simple et souvent rapide, mais le meilleur choix immédiat ne mène pas toujours à la solution optimale.
Exercice 5Donne un exemple de situation que l'on peut modéliser par un graphe.
Un réseau social peut être modélisé par un graphe : chaque personne est un sommet, et chaque lien d'amitié est une arête reliant deux sommets. De même, un réseau routier peut être un graphe (les villes sont les sommets, les routes les arêtes), ce qui permet par exemple de chercher le plus court chemin entre deux villes. Les graphes servent à représenter des éléments et leurs relations.