Flashcard: Introduction à la Complexité Algorithmique — 24 carte

Algorithme — définition ?

Procédure précise pour résoudre un problème.

Spécification d’un algorithme — rôle ?

Définir formellement paramètres, sortie, commentaires.

Déclaration de variable — fonction ?

Réserve mémoire pour une donnée.

Instruction élémentaire — exemple ?

Affectation ou test en temps constant.

Test conditionnel — but ?

Prendre une décision selon une condition.

Boucle itérative — utilité ?

Répéter des instructions jusqu’à une condition.

Complexité en temps — mesure ?

Nombre d’opérations en fonction de n.

Complexité en espace — concerne ?

Mémoire utilisée par l’algorithme.

Modèle WORD-RAM — caractéristique ?

Opérations en temps constant.

Notation de Landau — O — rôle ?

Borne supérieure asymptotique.

Notation de Landau — Ω — rôle ?

Borne inférieure asymptotique.

Notation de Landau — Θ — rôle ?

Croissance asymptotique exacte.

Croissance logarithmique — exemple ?

Algorithme de recherche binaire.

Croissance exponentielle — exemple ?

Algorithme naïf de puissance, O(2^n).

Limite d’une fonction — définition ?

Valeur vers laquelle elle tend quand x approche a.

Limite à l’infini — rôle ?

Comparer la croissance asymptotique.

Fonction linéaire — notation ?

O(n), croissance proportionnelle à n.

Fonction logarithmique — croissance ?

Très lente, O(log n).

Complexité classique — exemple ?

O(1), O(n), O(log n).

Preuve d’invariant — objectif ?

Valider la correction d’un algorithme.

Preuve par récurrence — étape clé ?

Montrer la propriété pour n=base et n→n+1.

Algorithme diviser pour régner — principe ?

Diviser, résoudre, combiner récursivement.

Appels récursifs — croissance ?

Proportionnelle à log n dans division par 2.

Algorithme itératif — caractéristique ?

Répétition par boucle, invariant pour correction.