Complexité d’un algorithme : La complexité d’un algorithme mesure le nombre d’opérations élémentaires qu’il effectue en fonction de la taille de l’entrée, notée n. Elle permet d’évaluer l’efficacité de l’algorithme en termes de temps de traitement.
Notation de Landau (O) : La notation O, ou notation asymptotique, sert à classer les algorithmes selon leur comportement lorsque n tend vers l’infini. Elle indique la limite supérieure du nombre d’opérations en fonction de n, en ignorant les constantes et termes de moindre ordre.
Complexité constante O(1) : Un algorithme a une complexité constante si le nombre d’opérations ne dépend pas de n. Il effectue un nombre fixe d’opérations, quel que soit la taille de l’entrée.
Complexité linéaire O(n) : La complexité est linéaire lorsque le nombre d’opérations croît proportionnellement à n. L’algorithme doit parcourir ou traiter chaque élément de l’entrée une seule fois.
Complexité logarithmique O(ln(n)) : La complexité logarithmique indique que le nombre d’opérations croît en fonction du logarithme de n. Elle est typique des algorithmes qui divisent l’espace de recherche à chaque étape, comme la recherche dichotomique.
Complexité quadratique O(n²) : La complexité est quadratique si le nombre d’opérations croît proportionnellement au carré de n. Elle apparaît souvent dans des algorithmes avec des boucles imbriquées sur la même donnée.
La complexité d’un algorithme permet de mesurer le nombre d’opérations élémentaires en fonction de la taille de l’entrée n. Elle influence directement le temps d’exécution, avec des classes allant de O(1) (constante) à des comportements exponentiels. La notation O permet de classer ces comportements selon leur croissance asymptotique, facilitant la comparaison entre algorithmes. La complexité peut être évaluée analytiquement, par une étude formelle du code, ou expérimentalement, par des tests sur des jeux de données. Un algorithme efficace est celui qui minimise à la fois le temps de traitement et l’espace mémoire utilisé, surtout pour de grandes valeurs de n.
Comprendre la classification des complexités permet d’anticiper la performance des algorithmes et de choisir la meilleure approche selon la taille des données. La notation O offre un cadre pour comparer leur efficacité asymptotique.
Algorithme glouton : Un algorithme qui, à chaque étape, fait un choix optimal localement dans l’espoir d’obtenir une solution globale optimale. Il repose sur la stratégie de sélection immédiate du meilleur choix possible sans revenir en arrière.
Choix optimum local : La décision prise à une étape donnée qui maximise ou minimise une certaine valeur selon le problème, sans considération directe des étapes futures.
Solution optimale globale : La meilleure solution possible pour l’ensemble du problème, qui minimise ou maximise la critère défini, et qui est atteinte par l’algorithme glouton sous certaines conditions.
Système monétaire canonique : Un système de pièces de monnaie pour lequel l’algorithme glouton donne toujours la solution optimale pour le rendu de monnaie.
Preuve d’optimalité gloutonne : Une démonstration qui établit que l’algorithme glouton produit une solution optimale, notamment par raisonnement par l’absurde et échange d’intervalles.
Un algorithme glouton procède en faisant, à chaque étape, un choix localement optimal, dans l’espoir que cette stratégie mène à une solution globale optimale. Cependant, cette garantie n’est pas systématique : les algorithmes gloutons ne garantissent pas toujours la solution optimale dans tous les cas. Par exemple, dans le problème du rendu de monnaie, si le système de pièces est canonique, l’algorithme glouton fournit toujours la solution optimale. La preuve d’optimalité pour certains problèmes, comme le planning d’occupation, repose sur un raisonnement par l’absurde et un échange d’intervalles, montrant que toute solution non optimale peut être améliorée par des échanges. Enfin, ces algorithmes sont efficaces pour certains problèmes spécifiques, notamment le rendu de monnaie canonique et le planning d’occupation, où ils permettent de résoudre rapidement des instances complexes.
Les algorithmes gloutons exploitent des choix locaux simples pour résoudre efficacement certains problèmes, mais leur optimalité doit être justifiée par une preuve spécifique, car ils ne garantissent pas toujours la solution globale optimale.
Système monétaire : Ensemble de pièces de monnaie avec des valeurs spécifiques, permettant de constituer une somme donnée. La solution optimale consiste à rendre la somme avec le moins de pièces possibles, c’est-à-dire en minimisant la somme des quantités de pièces utilisées.
Pièces de monnaie : Unités monétaires physiques, chacune ayant une valeur fixe. Par exemple, dans un système donné, des pièces de 1 €, 2 €, 5 €, 10 € et 20 € sont disponibles.
Algorithme glouton pour rendu : Méthode qui, à chaque étape, choisit la plus grande pièce possible sans dépasser la somme restante. Il continue ainsi jusqu’à ce que la somme soit entièrement rendue.
Algorithme naïf récursif : Approche exhaustive qui explore toutes les combinaisons possibles de pièces pour rendre la somme. Il garantit de trouver la solution optimale en comparant toutes les solutions possibles.
Solution optimale de rendu : La combinaison de pièces qui permet de rendre la somme demandée avec le nombre minimal de pièces, c’est-à-dire la solution qui minimise la somme des quantités utilisées.
Le rendu de monnaie vise à minimiser le nombre de pièces utilisées pour constituer une somme donnée. L’algorithme glouton fonctionne en sélectionnant, à chaque étape, la pièce de plus grande valeur qui ne dépasse pas la montant restant. Par exemple, pour rendre 57 €, avec des pièces de 1 €, 2 €, 5 €, 10 € et 20 €, la solution optimale est : 2 pièces de 20 €, 1 de 10 €, 1 de 5 €, 1 de 2 € (total 5 pièces). La solution est optimale si la somme de toutes les pièces utilisées est minimale.
Un système monétaire est dit canonique si l’algorithme glouton donne toujours la solution optimale pour toutes les sommes possibles. Dans ce cas, la structure des pièces garantit la fiabilité de la méthode glouton.
Cependant, certains systèmes monétaires ne sont pas canoniques. Par exemple, dans l’ancien système britannique, l’algorithme glouton appliqué à 49 pence ne donne pas toujours la meilleure solution, ce qui montre que le système n’est pas canonique. La méthode naïve récursive, quant à elle, explore toutes les combinaisons pour garantir la solution optimale, mais au prix d’un coût computationnel plus élevé.
Le rendu de monnaie illustre comment un algorithme glouton simple peut être efficace ou non selon la structure des pièces disponibles. Lorsqu’il ne garantit pas la solution optimale, une approche exhaustive est nécessaire pour assurer la meilleure réponse.
Planning d’occupation : Organisation des intervalles de temps réservés pour des conférences ou activités, visant à maximiser leur nombre sans chevauchement.
Intervalle de conférence : Période de temps délimitée par une heure de début et une heure de fin, correspondant à la durée d’une conférence. La fin doit être postérieure au début.
Critère de sélection glouton : Règle utilisée par l’algorithme pour choisir quel intervalle ajouter au planning. Ici, il s’agit de sélectionner l’intervalle qui se termine le plus tôt parmi ceux compatibles avec le planning en cours.
Preuve d’optimalité du planning : Argument démontrant que la solution obtenue par l’algorithme glouton est la meilleure possible, notamment par raisonnement par échange et contradiction.
Conflit d’intervalles : Situation où deux intervalles se chevauchent, rendant incompatible leur présence simultanée dans le planning. La sélection doit alors faire un choix pour éviter ces conflits.
Le but est de maximiser le nombre de conférences sans chevauchement. Pour cela, il est préférable de choisir le conférencier qui termine le plus tôt, afin d’optimiser l’espace disponible pour les conférences suivantes. L’algorithme glouton sélectionne donc, parmi les intervalles compatibles, celui qui se termine le plus tôt. Cette méthode garantit une sélection efficace, car elle laisse le maximum de place pour accueillir d’autres conférenciers. La preuve d’optimalité repose sur un raisonnement par échange et contradiction : si une solution optimale différente existe, on peut échanger certains intervalles pour obtenir une solution au moins aussi bonne, ce qui confirme que la solution gloutonne est optimale. Lorsqu’un conflit d’intervalles survient, il faut faire des choix pour éviter la superposition, en privilégiant l’intervalle qui respecte le critère de sélection.
Le planning d’occupation montre comment un critère de sélection judicieux dans un algorithme glouton garantit une solution optimale dans un problème d’ordonnancement.
Dichotomie
La dichotomie, du grec διχοτομία, signifie division en deux parties. Elle désigne une méthode qui consiste à diviser un intervalle en deux pour localiser une solution ou une racine d’une fonction.
Méthode dichotomique
Il s’agit d’une stratégie "diviser pour régner" appliquée à la recherche d’un zéro d’une fonction continue. Elle consiste à réduire progressivement un intervalle jusqu’à atteindre une précision souhaitée, en utilisant la division en deux pour éliminer la moitié de l’intervalle à chaque étape.
Fonction continue et monotone
Une fonction continue sur un intervalle [a, b] est une fonction sans interruption. Elle est monotone si elle est soit toujours croissante, soit toujours décroissante sur cet intervalle. La méthode s’applique à une fonction continue et monotone, garantissant l’existence d’un zéro dans l’intervalle si f(a) et f(b) ont des signes opposés.
Théorème des valeurs intermédiaires
Ce théorème stipule que si une fonction continue f est définie sur [a, b] et que f(a) et f(b) ont des signes opposés, alors il existe au moins un point c dans (a, b) tel que f(c) = 0. Il garantit l’existence d’une racine dans l’intervalle.
Intervalle de recherche
C’est l’intervalle initial [a, b] dans lequel on cherche à localiser la racine. La méthode consiste à le réduire en divisant cet intervalle en deux à chaque étape, en conservant la partie où le signe de la fonction change.
La dichotomie est une approche systématique et rigoureuse pour isoler une racine, combinant principes mathématiques et algorithmique, en divisant l’intervalle en deux à chaque étape jusqu’à atteindre la précision souhaitée.
Recherche dichotomique : Méthode de recherche qui localise un zéro d’une fonction en divisant l’intervalle selon le signe de la fonction, jusqu’à obtenir une précision souhaitée. Elle repose sur la propriété que si f(g) et f(d) ont des signes opposés, alors il existe une racine entre g et d.
Zéro d’une fonction : Point x où f(x) = 0. La recherche dichotomique vise à trouver ce point en utilisant la continuité et la monotonie de la fonction.
Principe de la méthode dichotomique : Diviser l’intervalle en deux parts en utilisant le point médian, puis sélectionner la sous-partie où le signe de la fonction change, jusqu’à ce que la longueur de l’intervalle soit inférieure à la précision désirée.
Coût de la recherche dichotomique : Logarithmique en fonction de la précision ε, exprimé par kmax = −(log2 ε ab + 1). Le nombre d’itérations nécessaire pour atteindre cette précision est proportionnel à ce logarithme.
Preuve de convergence : La preuve garantit que l’intervalle se réduit à chaque étape, grâce à la propriété que la longueur de l’intervalle diminue d’au moins un facteur 1/2 à chaque itération, assurant ainsi la convergence vers la racine.
La recherche dichotomique localise un zéro en divisant l’intervalle selon le signe de la fonction. À chaque étape, on calcule le point médian m = (g + d)/2. Si f(m) = 0, la racine est trouvée. Sinon, on choisit la sous-intervalle où le signe de f change : si f(g) ⋅ f(m) < 0, on remplace d par m ; si f(d) ⋅ f(m) < 0, on remplace g par m. La méthode converge grâce à la continuité et la monotonie de la fonction, qui garantissent que la racine se trouve dans l’intervalle réduit. Le coût est logarithmique en fonction de la précision ε, avec un nombre d’itérations kmax = −(log2 ε ab + 1). La preuve repose sur le fait que l’intervalle se réduit d’au moins un facteur 1/2 à chaque étape, et que la longueur de l’intervalle devient inférieure à ε après un nombre fini d’itérations. Des tests supplémentaires peuvent renforcer la robustesse de l’algorithme.
La recherche dichotomique est une méthode efficace et rigoureuse pour localiser un zéro d’une fonction, combinant un coût maîtrisé grâce à sa complexité logarithmique et une convergence assurée par la propriété de réduction progressive de l’intervalle.
Recherche dans tableau trié : Technique qui exploite la structure ordonnée d’un tableau pour localiser efficacement une valeur cible en divisant l’espace de recherche à chaque étape.
Tableau trié : Tableau dont les éléments sont organisés selon un ordre croissant ou décroissant, permettant d’appliquer des méthodes de recherche optimisées.
Principe de la recherche dichotomique : Méthode qui consiste à comparer la valeur cible au milieu du tableau pour réduire l’intervalle de recherche de moitié à chaque étape, jusqu’à trouver la valeur ou épuiser l’espace.
Algorithme de recherche dichotomique : Procédé systématique utilisant la division répétée de l’intervalle de recherche en deux, en comparant la valeur cible avec l’élément central, jusqu’à localisation ou élimination.
Complexité logarithmique : La recherche dans un tableau trié via la dichotomie a une complexité en O(ln(n)), ce qui signifie que le nombre d’opérations croît logarithmiquement avec la taille du tableau.
La recherche dans un tableau trié utilise la dichotomie pour diviser l’espace de recherche. Elle fonctionne en comparant la valeur cible au milieu du tableau, ce qui permet de réduire l’intervalle de recherche de moitié à chaque étape. Cette méthode est beaucoup plus efficace qu’une recherche linéaire, avec une complexité logarithmique O(ln(n)). La preuve de cette efficacité montre que si la valeur existe dans le tableau, l’algorithme la trouve en un nombre d’étapes proportionnel à ln(n). Cependant, cette méthode nécessite que le tableau soit préalablement trié pour fonctionner correctement.
La recherche dichotomique dans un tableau trié illustre un algorithme efficace exploitant la structure ordonnée des données, permettant de réduire considérablement le nombre d’opérations nécessaires pour localiser une valeur.
| Critère | Algorithme glouton | Approche naïve (récursive) |
|---|---|---|
| Stratégie | Choix local immédiat (ex : pièce la plus grande, intervalle le plus tôt) | Exploration exhaustive de toutes les solutions possibles |
| Garantie d’optimalité | Oui, si problème ou système est canonique (ex : rendu de monnaie canonique) | Oui, garantit toujours la solution optimale |
| Complexité | Faible, souvent linéaire ou logarithmique selon le problème | Élevée, exponentielle dans le pire cas |
| Exemple typique | Rendu de monnaie dans un système canonique | Rendu de monnaie dans un système non canonique, recherche exhaustive |
| Utilisation principale | Résolution rapide de problèmes spécifiques | Recherche de solution optimale sans contrainte de temps |
Testez vos connaissances sur Maîtrise des algorithmes gloutons et dichotomie avec 7 questions à choix multiples avec corrections détaillées.
1. Quelle est la cause principale de la rapidité de convergence de la recherche dichotomique ?
2. Selon le texte, à quel moment la stratégie de sélection du plus tôt dans le planning d’occupation a été démontrée comme optimale ?
Mémorisez les concepts clés de Maîtrise des algorithmes gloutons et dichotomie avec 14 flashcards interactives.
Complexité algorithme — définition ?
Mesure du nombre d'opérations en fonction de n.
Notation O — rôle ?
Classe et compare la croissance asymptotique.
Complexité constante O(1) — description ?
Opérations fixes, indépendantes de n.
Bases de données
Bases de données
Programmation
Programmation
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches