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

Paradigme glouton — objectif ?

Construire une solution en choisissant localement optimal.

Diviser-pour-régner — principe ?

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

Programmation dynamique — propriété clé ?

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

Force brute — méthode ?

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

Stratégie gloutonne — propriété du choix ?

Choix local optimal, pas toujours globalement optimal.

Mémoïsation — rôle ?

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

Tabulation — rôle ?

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

Diviser pour mieux régner — analyse ?

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

Force brute — limite ?

Complexité exponentielle, impraticable pour grandes instances.

Retour sur trace — mécanisme ?

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

Heuristiques — rôle ?

Guider la recherche sans garantie d’optimalité.

Métaheuristiques — définition ?

Algorithmes généraux pour optimisation approximative.

Comparaison paradigmes — optimalité ?

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

Dijkstra — complexité ?

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

Sac à dos fractionnaire — stratégie ?

Prendre objets selon ratio valeur/poids, solution optimale.

Sac à dos 0-1 — approche ?

Utiliser programmation dynamique pour optimalité.

Fibonacci naïf — complexité ?

Exponentielle, beaucoup de recalculs.

Fibonacci DP — avantage ?

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

Validation DaariNova — principe ?

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

Force brute — limite pratique ?

Intractable pour instances de taille moyenne ou grande.

Glouton — condition d’optimalité ?

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

Programmation dynamique — avantage ?

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

Dijkstra — principe ?

Fixer distances minimales en élargissant le plus proche sommet.

Heuristique du plus proche voisin — application ?

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