Self-assessment quiz

# Qu’est-ce que la complexité algorithmique ? - [ ] Une mesure du temps d’exécution d’un algorithme > ❌ L'algorithmique de complexité mesure non seulement le temps d'exécution, mais aussi l'espace mémoire utilisé par un algorithme. - [ ] Une mesure de l’espace mémoire utilisé par un algorithme > ❌ L'algorithmique de complexité prend en compte à la fois l'espace mémoire et le temps d'exécution de l'algorithme. - [x] Une mesure du temps d’exécution et de la mémoire utilisée par un algorithme > ✅ La complexité algorithmique mesure à la fois le temps d'exécution et l'espace mémoire nécessaire à un algorithme. - [ ] Une mesure de la complexité d’un algorithme > ❌ La complexité algorithmique ne mesure pas la difficulté de compréhension de l'algorithme, mais bien les ressources qu'il consomme. # Qu’est-ce qui nous intéresse généralement quand on étudie la complexité algorithmique ? - [ ] L’analyse moyenne > ❌ L'analyse moyenne peut être utile, mais on se concentre souvent sur le pire des cas pour garantir la performance de l'algorithme dans toutes les situations. - [ ] L’analyse pessimiste > ❌ Bien que proche, le terme correct est "worst-case analysis" en anglais pour désigner l'analyse du pire des cas. - [x] L’analyse du pire des cas > ✅ L'analyse du pire des cas est utilisée pour s'assurer qu'un algorithme fonctionnera dans des délais raisonnables, même dans les situations les plus défavorables. # Laquelle des notations suivantes correspond aux algorithmes linéaires et logarithmiques ? 1. [ ] $O(N)$ > ❌ O(N) représente une complexité linéaire, sans le composant logarithmique. 1. [x] $O(N \cdot log(N))$ > ✅ O(N \cdot log(N)) représente une complexité linéaire logarithmique, souvent rencontrée dans des algorithmes comme le tri rapide. 1. [ ] $O(N^2)$ > ❌ O(N^2) représente une complexité quadratique, où le temps d'exécution augmente en fonction du carré de N. # Quel type d’algorithme a une complexité de la forme $O(N^p)$ ? 1. [ ] Algorithmes logarithmiques > ❌ Les algorithmes logarithmiques ont une complexité de type O(log(N)). 1. [ ] Algorithmes linéaires > ❌ Les algorithmes linéaires ont une complexité de type O(N). 1. [x] Algorithmes polynomiaux > ✅ Les algorithmes de type polynomial ont une complexité de la forme O(N^p), où p est une constante. # Qu’est-ce qui cause le grand nombre de calculs dans un algorithme ? - [x] Le nombre de boucles > ✅ Les boucles augmentent le nombre de calculs en répétant des opérations, ce qui impacte directement la complexité de l'algorithme. - [ ] Le nombre de variables > ❌ Le nombre de variables n'affecte pas directement le nombre de calculs d'un algorithme, sauf si ces variables sont utilisées dans des opérations coûteuses. - [ ] Le nombre de fonctions > ❌ Le nombre de fonctions n'affecte pas le nombre de calculs, bien que certaines fonctions puissent inclure des boucles ou des appels récursifs. # Chercher l’existence d’un élément spécifique dans une liste est un exemple de quel type de complexité ? - [ ] Complexité logarithmique > ❌ Une recherche dans une liste non triée nécessite de parcourir chaque élément, ce qui est linéaire, et non logarithmique. - [x] Complexité linéaire > ✅ Une recherche dans une liste non triée a une complexité linéaire O(N) car il faut potentiellement examiner chaque élément. - [ ] Complexité constante > ❌ Une recherche avec complexité constante O(1) n'est possible que dans des structures permettant un accès direct, comme un tableau indexé. - [ ] Complexité quadratique > ❌ La recherche linéaire n'implique pas de double boucle, donc elle n'a pas une complexité quadratique.

# Qu’est-ce qu’un arbre binaire de recherche (BST) ? - [x] Une structure arborescente qui place les valeurs plus petites à gauche et les valeurs plus grandes à droite > ✅ Dans un BST, le sous-arbre gauche de chaque nœud contient des valeurs inférieures au nœud, tandis que le sous-arbre droit contient des valeurs supérieures. - [ ] Un arbre où chaque nœud a exactement deux enfants > ❌ Dans un BST, les nœuds peuvent avoir zéro, un ou deux enfants ; la structure dépend des valeurs insérées. - [x] Une structure de données qui maintient un ordre entre les nœuds > ✅ Les BST maintiennent une structure ordonnée, ce qui rend les opérations comme la recherche et l’insertion efficaces. - [ ] Un arbre utilisé uniquement pour stocker des nombres > ❌ Un BST peut stocker n’importe quelle donnée ordonnable, pas seulement des nombres. - [ ] Une structure sans cycles ni connexions entre les nœuds > ❌ Bien que les BST soient acycliques, ils sont connectés par des relations parent-enfant. # Quels sont les principaux avantages d’utiliser un BST ? - [x] Recherche efficace grâce à sa structure ordonnée > ✅ La structure ordonnée d’un BST permet une recherche efficace, avec une complexité en temps de O(h), où h est la hauteur. - [ ] Accès aux éléments en temps constant > ❌ Le temps d’accès dans un BST dépend de la hauteur de l’arbre, pas constant comme dans un tableau. - [x] Insertion efficace tout en maintenant l’ordre > ✅ L’insertion dans un BST est efficace et préserve la structure ordonnée de l’arbre. - [ ] Structure garantie équilibrée > ❌ Les BST ne sont pas nécessairement équilibrés ; sans équilibrage, ils peuvent se dégrader en structures linéaires. - [x] Supporte des opérations comme trouver les valeurs minimum et maximum efficacement > ✅ Grâce à sa structure, un BST permet un accès rapide aux valeurs minimum et maximum en parcourant à gauche ou à droite. # Comment trouve-t-on la valeur minimale dans un BST ? - [x] En suivant les enfants gauche depuis la racine > ✅ Dans un BST, la valeur minimale se trouve en allant à gauche jusqu’à atteindre un nœud sans enfant gauche. - [ ] En suivant les enfants droite depuis la racine > ❌ Suivre les enfants droite permet de trouver la valeur maximale, pas la minimale. - [ ] En vérifiant chaque nœud de l’arbre > ❌ La structure ordonnée permet de trouver le minimum sans vérifier tous les nœuds. - [x] Cela a une complexité en temps de O(h), où h est la hauteur de l’arbre > ✅ Trouver le minimum prend un temps O(h) car il suffit de parcourir un seul côté de l’arbre. - [ ] En équilibrant d’abord l’arbre > ❌ L’équilibrage n’est pas nécessaire pour trouver le minimum dans un BST. # Quelle est l’importance de la hauteur d’un BST pour ses performances ? - [x] La hauteur affecte l’efficacité des opérations de recherche, insertion et suppression > ✅ La hauteur d’un BST détermine la complexité temporelle des opérations comme la recherche, l’insertion et la suppression, rendant la hauteur équilibrée cruciale. - [ ] La hauteur doit toujours être égale au nombre de nœuds > ❌ La hauteur d’un BST n’est pas toujours égale au nombre de nœuds ; elle dépend de l’ordre d’insertion et de l’équilibre de l’arbre. - [x] Une hauteur plus petite rend l’arbre plus efficace > ✅ Une hauteur plus faible signifie moins de nœuds à parcourir, ce qui améliore l’efficacité des opérations. - [ ] La hauteur n’impacte pas les performances > ❌ La hauteur impacte significativement les performances ; un arbre plus haut signifie des chemins de recherche et d’insertion plus longs. - [ ] Un BST de hauteur 0 est idéal pour toutes les opérations > ❌ Un BST de hauteur 0 ne contient que la racine et n’offre pas de structure significative pour des données plus volumineuses. # Qu’est-ce que la rotation d’arbre dans le contexte des BST ? - [x] Une méthode pour équilibrer l’arbre et réduire sa hauteur > ✅ Les rotations d’arbre ajustent la structure d’un BST pour maintenir l’équilibre et réduire sa hauteur. - [ ] Un processus pour supprimer des nœuds de l’arbre > ❌ La rotation d’arbre ne supprime pas de nœuds ; elle les réarrange pour maintenir l’équilibre. - [x] Un moyen de conserver la propriété BST intacte après restructuration > ✅ Les rotations d’arbre ajustent la structure tout en préservant la propriété BST. - [ ] Une technique utilisée uniquement dans les arbres binaires déséquilibrés > ❌ La rotation d’arbre est aussi appliquée dans les BST équilibrés pour maintenir la hauteur après insertions et suppressions. - [ ] Un remplacement du rééquilibrage de l’arbre > ❌ La rotation d’arbre est une étape du processus de rééquilibrage, pas un remplacement. # Qu’est-ce qu’un BST équilibré ? - [x] Un arbre où les sous-arbres gauche et droit de chaque nœud diffèrent en hauteur d’au plus 1 > ✅ Un BST équilibré garantit qu’aucun sous-arbre n’est significativement plus haut que l’autre, optimisant les performances. - [ ] Un arbre où tous les éléments sont d’un seul côté > ❌ Un arbre avec tous les éléments d’un seul côté est déséquilibré, ressemblant à une liste chaînée. - [x] Un arbre qui maintient des temps efficaces pour la recherche, l’insertion et la suppression > ✅ Un BST équilibré offre des temps d’opération efficaces grâce à sa hauteur optimale. - [ ] Un arbre avec un seul nœud > ❌ Un arbre à nœud unique est trivialement équilibré mais ne représente pas le concept d’équilibre pour des arbres plus grands. - [x] Un arbre qui peut utiliser des rotations pour maintenir sa structure > ✅ Les BST équilibrés, comme les arbres AVL ou Rouge-Noir, utilisent souvent des rotations pour maintenir l’équilibre après insertions ou suppressions.

# Qu’est-ce qu’un algorithme randomisé ? - [x] Un algorithme qui utilise le hasard pour prendre des décisions > ✅ Les algorithmes randomisés utilisent des choix aléatoires dans leur logique, ce qui peut entraîner des résultats ou performances variables sur la même entrée. - [ ] Un algorithme qui garantit le même résultat à chaque exécution > ❌ Les algorithmes randomisés peuvent produire des résultats différents à chaque exécution en raison de l’utilisation du hasard. - [ ] Un algorithme avec un temps d’exécution fixe > ❌ Le temps d’exécution d’un algorithme randomisé peut varier selon ses choix aléatoires. - [x] Un algorithme qui peut parfois donner des solutions approximatives > ✅ Les algorithmes randomisés peuvent offrir des garanties probabilistes plutôt que des solutions exactes. - [ ] Un algorithme qui ne fonctionne qu’avec des données numériques > ❌ Les algorithmes randomisés peuvent s’appliquer à divers types de données, pas seulement numériques. # Quelle est la principale caractéristique d’un algorithme Monte-Carlo ? - [x] Il fournit des résultats corrects avec une haute probabilité mais pas toujours > ✅ Les algorithmes Monte-Carlo ont une forte probabilité de produire des résultats corrects mais peuvent parfois donner des résultats incorrects. - [ ] Il produit toujours un résultat correct > ❌ Les algorithmes Monte-Carlo ne garantissent pas la correction à chaque exécution ; ils l’obtiennent seulement avec une haute probabilité. - [x] Il a un temps d’exécution prévisible > ✅ Les algorithmes Monte-Carlo ont généralement des temps d’exécution prévisibles car ils sont optimisés pour la rapidité plutôt que la précision. - [ ] Il s’arrête dès qu’il rencontre une erreur > ❌ Les algorithmes Monte-Carlo sont conçus pour continuer à fonctionner, même avec des variations potentielles de précision. - [ ] Il n’utilise pas le hasard > ❌ Les algorithmes Monte-Carlo reposent sur le hasard pour prendre des décisions dans leur processus. # Quel est le principal avantage d’utiliser un algorithme Las-Vegas ? - [x] Il produit toujours le résultat correct > ✅ Les algorithmes Las-Vegas garantissent le résultat correct, mais leurs performances peuvent varier. - [ ] Il fournit des résultats approximatifs pour gagner du temps > ❌ Les algorithmes Las-Vegas privilégient la correction et ne compromettent pas en fournissant des résultats approximatifs. - [x] Il peut s’exécuter en temps polynomial attendu > ✅ Les algorithmes Las-Vegas s’exécutent typiquement en temps polynomial attendu, bien que le temps exact puisse varier. - [ ] Il s’exécute sans besoin de nombres aléatoires > ❌ Les algorithmes Las-Vegas utilisent le hasard pour potentiellement améliorer leurs performances tout en assurant la correction. - [ ] Il garantit un temps d’exécution fixe > ❌ Le temps d’exécution des algorithmes Las-Vegas peut varier à cause de leur nature aléatoire, mais ils produisent toujours le résultat correct. # Pourquoi utilise-t-on couramment des nombres pseudo-aléatoires dans les algorithmes randomisés ? - [x] Les vrais nombres aléatoires sont difficiles à générer > ✅ Générer une vraie aléa est difficile, donc on utilise souvent des nombres pseudo-aléatoires à la place. - [ ] Les nombres pseudo-aléatoires sont toujours uniformément distribués > ❌ Les nombres pseudo-aléatoires ne sont pas toujours parfaitement uniformes, mais ils suffisent pour la plupart des applications. - [x] Ils offrent un compromis entre rapidité et portabilité > ✅ Les générateurs de nombres pseudo-aléatoires sont conçus pour être efficaces et compatibles sur différents systèmes. - [ ] Ils sont continus plutôt que discrets > ❌ Les nombres pseudo-aléatoires sont typiquement discrets ; générer des valeurs continues nécessite un traitement supplémentaire. - [x] Ils permettent des séquences reproductibles pour les tests > ✅ Les générateurs de nombres pseudo-aléatoires produisent des séquences répétables, utiles pour les tests et le débogage. # Quelles sont deux propriétés clés d’un bon générateur de nombres aléatoires ? - [x] Uniformité > ✅ L’uniformité garantit que chaque valeur possible a une chance égale d’être générée. - [ ] Prédictibilité > ❌ Un bon générateur de nombres aléatoires doit être imprévisible, pas prévisible. - [x] Indépendance > ✅ L’indépendance signifie que les nombres générés ne dépendent pas les uns des autres, maintenant le caractère aléatoire de la séquence. - [ ] Complexité > ❌ La complexité n’est pas une qualité souhaitable pour les générateurs de nombres aléatoires, la simplicité améliore l’efficacité et la portabilité. - [ ] Déterminisme > ❌ Le déterminisme n’est pas une caractéristique de l’aléa idéal ; les générateurs pseudo-aléatoires sont déterministes, mais le vrai hasard ne l’est pas.