37 documents tagués avec "algorithms"

Plus courts chemins depuis une source avec arêtes négatives et détection des cycles négatifs accessibles.

Plus courts chemins depuis une source avec des poids d’arêtes non négatifs.

Programmation dynamique pour les plus courts chemins entre toutes les paires et la détection des cycles de poids négatif.

Forêts couvrantes minimums obtenues par tri des arêtes et union d'ensembles disjoints.

Construction progressive d'un arbre couvrant minimum par l'arête admissible la plus légère d'une coupe.

Une carte pour analyser les algorithmes, reconnaître les schémas de conception et choisir une famille de résolution adaptée.

Une carte orientée problèmes pour choisir entre parcours, plus courts chemins et arbres couvrants minimums.

Une carte de décision pour la recherche, les données ordonnées et le parcours de graphes.

Une carte de décision pour le tri par comparaison, la stabilité, l’adaptativité et les compromis mémoire.

Des algorithmes de choix local organisés autour des preuves à fournir et des contre-exemples.

La propriété de la coupe relie les choix d'arêtes sûrs de Prim et de Kruskal.

Codes préfixes binaires optimaux pour des fréquences de symboles connues.

Analyse du pic de mémoire occupé par l'entrée, la sortie, l'état auxiliaire et la récursion.

Analyse asymptotique du temps d'exécution avec mesures d'entrée, modèles et hypothèses de cas explicites.

Sous-problèmes récursifs indépendants, coûts de combinaison et analyse par récurrence.

Une petite récurrence pour illustrer les sous-problèmes répétés et la compression de l'état.

Une lecture des plus courts chemins par les récurrences, reliée aux algorithmes propres aux graphes.

Planifier des tâches unitaires dans leur dernier créneau admissible afin de maximiser le profit.

Parcours de graphe par couches et plus courts chemins en nombre d’arêtes.

Parcours de graphe fondé sur une pile, structure parentale et garanties propres à DFS.

Énumération position par position avec élagage des symétries dues aux valeurs répétées.

Programmation dynamique d'alignement de séquences et compromis entre longueur et reconstruction.

Programmation dynamique indexée par la capacité et sens des mises à jour unidimensionnelles.

Une méthode centrée sur l'état pour les problèmes dont les sous-problèmes peuvent être réutilisés.

Recherche de frontière dans des données triées à accès aléatoire ou sur des prédicats monotones.

Recherche séquentielle sans hypothèse d’ordre ni prétraitement.

Recherche en profondeur dans les décisions, avec état réversible et élagage sûr.

Sélection par densité lorsque les objets sont continûment divisibles.

Ordonnancement d'un nombre maximal d'intervalles selon leur heure de fin la plus précoce.

Une recherche 0/1 précise pour la somme de sous-ensemble et les limites de son élagage.

Distinguer la preuve d’existence, la construction explicite et l’exécution pratique d’une stratégie dans un jeu fini, avec les limites du vol de stratégie et de l’élagage.

Tri par échanges adjacents, son invariant et son rôle pratique limité.

Tri stable par division pour régner, au temps prévisible et à l’espace de travail linéaire sur tableau.

Tri stable adaptatif pour les intervalles petits ou presque ordonnés.

Tri par sélection du minimum, au coût de comparaison fixe et avec peu d’échanges.

Tri en place avec un tas binaire et une borne au pire cas en n-log-n.

Tri par partition, risque du pivot, traitement des doublons et discipline de pile.