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.
Testez vos connaissances avec un QCM de 12 questions sur Introduction à la Complexité Algorithmique.
1. Qu'est-ce que le modèle de calcul WORD-RAM dans l'analyse de la complexité algorithmique?
2. Quel auteur ou référence précise est associé à la définition de la complexité en temps dans le modèle WORD-RAM mentionné dans le contenu ?
Révisez le cours complet dans la fiche de révision de Introduction à la Complexité Algorithmique.
Voir la fiche →Intelligence Artificielle
Bases de données
Bases de données
Bases de données
Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards