Flashcards : Paradigmes algorithmiques et stratégies efficaces — 24 cartes

Construire une solution en choisissant localement optimal.

Décomposer en sous-problèmes, résoudre, puis combiner.

Sous-structure optimale et sous-problèmes chevauchants.

Tester toutes les possibilités jusqu’à la solution.

Choix local optimal, pas toujours globalement optimal.

Stocker résultats pour éviter recalculs en top-down.

Remplir un tableau de façon itérative pour résoudre.

Décomposition en sous-problèmes indépendants, complexité typique O(n log n).

Complexité exponentielle, impraticable pour grandes instances.

Explorer arbre, revenir en arrière si branche non optimale.

Guider la recherche sans garantie d’optimalité.

Algorithmes généraux pour optimisation approximative.

Force brute garantie, glouton conditionnelle, DP garantie si propriété du sous-problème.

O((V + E) log V) avec tas, dépend du graphe.

Prendre objets selon ratio valeur/poids, solution optimale.

Utiliser programmation dynamique pour optimalité.

Exponentielle, beaucoup de recalculs.

Réduction de la complexité à O(n) en évitant recalculs.

Identifier propriété du choix et sous-structure pour garantir optimalité.

Intractable pour instances de taille moyenne ou grande.

Propriété du choix glouton vérifiée et sous-structure optimale.

Solution efficace pour problèmes avec sous-structure et chevauchement.

Fixer distances minimales en élargissant le plus proche sommet.

TSP, choisit la ville la plus proche non visitée.