la recherche dichotomique
La recherche dichotomique (ou recherche binaire) est un algorithme de recherche qui permet de trouver la position d'une valeur cible dans un tableau trié.
MPSI, PCSI et la PTSI
MP, PSI et la TSI
Diviser pour régner
Premium
Diviser pour régner
tri rapide
tri fusion
Diviser pour régner : un paradigme algorithmique fondamental
Dans l'approche diviser pour régner, le problème en question est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment. Si nous continuons à diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement atteindre un stade où plus aucune division n'est possible.
MPSI, PCSI et la PTSI
MP, PSI et la TSI
Algorithmes Gloutons
Exercices langage c
Exercices python
algorithmes gloutons
Problème d'installation des étagères
Étant donné la longueur du mur L et des étagères de deux longueurs m et n, trouvez le nombre de chaque type d'étagère à utiliser et l'espace disponible restant dans la solution optimale, de sorte que l'espace vide soit minimal.
MPSI, PCSI et la PTSI
MP, PSI et la TSI
Algorithmes Gloutons
Premium
Exercices langage c
Exercices python
Tableaux
algorithmes gloutons
sac à dos
Problème du Sac à Dos fraction
Sac à dos fractionnaire Étant donné les poids et les valeurs de n articles, nous devons mettre ces articles dans un sac à dos de capacité C pour obtenir la valeur totale maximale dans le sac à dos.
Sous-ensemble de produits minimum d'un tableau
Étant donné un tableau a, nous devons trouver le produit minimum possible avec le sous-ensemble d'éléments présents dans le tableau. Le produit minimum peut être un seul élément aussi.
Problème de séquencement des tâches
Étant donné un ensemble de travaux pour lesquels chaque travail a une date limite et les bénéfices associés si le travail est terminé avant la date limite. Il est également indiqué que chaque travail prend une seule unité de temps, de sorte que le délai minimum possible pour tout travail est 1. Comment maximiser le profit total si un seul travail peut être planifié à la fois.
MP, PSI et la TSI
Algorithmes Gloutons
Problème de la sélection d'activités
Vous avez n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximal d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
MP, PSI et la TSI
Algorithmes Gloutons
Premium
algorithmes gloutons
Ordonnancement
Sélection d'activités
Introduction aux algorithmes gloutons
Un algorithme glouton (ou greedy algorithm en anglais) adopte une stratégie simple mais puissante : À chaque étape, il choisit le meilleur choix possible selon un critère local, sans jamais remettre en question les choix précédents. Autrement dit, l'algorithme avance pas à pas, en effectuant des choix immédiats qui semblent les plus avantageux sur le moment - d'où le terme "glouton" (celui qui "mange" tout de suite ce qui paraît le meilleur).
MP, PSI et la TSI
Les graphes
Programmation dynamique
Premium
plus cours chemin dans un graphe
Chemin
bellman-ford
Dijkstra
plus court chemin
Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Algorithme Floyd-Warshall
L'algorithme de Floyd-Warshall change de paradigme. Son objectif est de calculer simultanément les distances minimales pour tous les couples de sommets \((i,j)\). C'est un outil indispensable pour l'analyse de réseaux denses (où le nombre d'arêtes \(A\) est proche de \(S^2\)) et pour la détection de structures pathologiques comme les cycles de poids négatifs.
MP, PSI et la TSI
Les graphes
Programmation dynamique
Premium
graphe orienté
plus cours chemin dans un graphe
parcours des graphes
algorithmes de parcours
bellman-ford
Dijkstra
Algorithme de chemin le plus court de Bellman-Ford
L'algorithme de Bellman-Ford est un algorithme de calcul des plus courts chemins depuis une source unique dans un graphe pondéré. Développé par Richard Bellman et Lester Ford dans les années 1950, il constitue une alternative plus robuste mais moins efficace que l'algorithme de Dijkstra.
Algorithme de chemin le plus court de Dijkstra
L'algorithme a été conçu par Edsger W. Dijkstra en 1956 et publié en 1959. Dans sa lettre originale, il décrit sa découverte comme une solution "en 20 minutes" à un problème posé par un mathématicien non informaticien. La simplicité de sa formulation cache une profondeur conceptuelle qui en fait l'un des joyaux de l'algorithmique des graphes.
MP, PSI et la TSI
Les graphes
Premium
graphe orienté
graphe non orienté
plus cours chemin dans un graphe
algorithmes sur les graphes
parcours des graphes
DFS
BFS
algorithmes de parcours
Algorithmes de parcours d'un graphe
Le BFS explore un graphe par niveaux successifs, du plus proche au plus éloigné. Le DFS explore un graphe en s'enfonçant le plus loin possible le long d'un chemin avant de revenir en arrière (backtracking).