Self-assessment quiz

# Comment un problème est-il défini en informatique ? - [x] Comme une fonction d’un domaine vers un codomaine > ✅ Un problème peut être représenté comme une fonction qui associe des entrées (domaine) à des sorties (codomaine). - [ ] Comme une série d’étapes pour résoudre une tâche spécifique > ❌ Cela décrit un algorithme, pas un problème. Un problème est la fonction abstraite que l’algorithme résout. - [ ] Comme un arbre de décision > ❌ Un arbre de décision est un modèle spécifique utilisé pour la classification ou la prise de décision, pas une définition générale d’un problème. - [x] Comme une fonction qui peut être partielle ou totale > ✅ Les problèmes peuvent être partiels (définis pour certaines entrées) ou totaux (définis pour toutes les entrées du domaine). - [ ] Comme un ensemble de contraintes > ❌ Bien que les contraintes puissent définir des problèmes spécifiques, elles ne constituent pas la définition générale d’un problème. # Qu’est-ce qu’un problème de décision ? - [x] Un problème avec un codomaine booléen > ✅ Un problème de décision associe des entrées à un codomaine booléen, retournant `true` ou `false` comme solution. - [ ] Un problème avec plusieurs solutions possibles > ❌ Cela décrit un problème de recherche, pas un problème de décision. - [ ] Un problème qui ne peut pas être résolu par un algorithme > ❌ Les problèmes de décision peuvent souvent être résolus par des algorithmes, à condition qu’ils soient bien définis. - [x] Un problème qui répond par oui ou non à une question > ✅ Les problèmes de décision sont conçus pour répondre à des questions binaires (oui/non). - [ ] Un problème avec un domaine infini > ❌ Bien que les problèmes de décision puissent avoir des domaines infinis, ce n’est pas une caractéristique déterminante. # Qu’est-ce qui distingue un problème de recherche d’un problème de décision ? - [x] Un problème de recherche peut avoir plusieurs solutions > ✅ Les problèmes de recherche permettent plusieurs solutions possibles, contrairement aux problèmes de décision qui retournent une seule valeur booléenne. - [ ] Un problème de recherche a toujours exactement une solution > ❌ Les problèmes de recherche peuvent avoir une, plusieurs ou aucune solution, selon l’entrée. - [ ] Un problème de décision est toujours plus difficile à calculer qu’un problème de recherche > ❌ Cela dépend du problème spécifique ; les problèmes de décision ne sont pas intrinsèquement plus difficiles ou plus faciles que les problèmes de recherche. - [x] Un problème de recherche peut être défini à l’aide de relations plutôt que de fonctions > ✅ Les problèmes de recherche sont souvent définis par des relations, car ils peuvent produire des ensembles de solutions plutôt qu’une seule sortie. - [ ] Les problèmes de recherche ne peuvent pas être résolus par des algorithmes > ❌ Les problèmes de recherche peuvent souvent être résolus algorithmiquement, bien que trouver toutes les solutions ne soit pas toujours faisable en temps fini. # Qu’est-ce qu’un problème d’optimisation ? - [x] Un raffinement d’un problème de recherche où la meilleure solution est souhaitée > ✅ Les problèmes d’optimisation visent à trouver la meilleure solution selon une fonction de coût. - [ ] Un problème avec des sorties booléennes > ❌ Les sorties booléennes caractérisent les problèmes de décision, pas les problèmes d’optimisation. - [x] Un problème défini par une fonction de coût > ✅ Les problèmes d’optimisation utilisent une fonction de coût pour évaluer et identifier la meilleure solution parmi plusieurs. - [ ] Un problème qui a toujours une solution unique > ❌ Les problèmes d’optimisation peuvent avoir plusieurs solutions optimales selon la fonction de coût et les contraintes. - [x] Un problème où les solutions sont évaluées pour minimiser ou maximiser une valeur > ✅ Les problèmes d’optimisation consistent à minimiser ou maximiser une valeur basée sur une fonction de coût donnée. # Quel est le but d’une fonction de coût dans les problèmes d’optimisation ? - [x] Évaluer la qualité d’une solution > ✅ La fonction de coût attribue une valeur à chaque solution, permettant à l’algorithme d’évaluer sa qualité. - [ ] Déterminer si un problème n’a pas de solution > ❌ La fonction de coût évalue les solutions, pas l’existence d’une solution. - [x] Trouver la meilleure solution parmi les solutions possibles > ✅ La fonction de coût aide à identifier la solution optimale en comparant les valeurs de toutes les solutions possibles. - [ ] Simplifier le problème en un problème de décision > ❌ La fonction de coût ne simplifie pas le problème mais aide à affiner la recherche d’une solution optimale. - [x] Minimiser ou maximiser une valeur spécifique dans le problème > ✅ Les problèmes d’optimisation visent à minimiser ou maximiser la fonction de coût pour déterminer la meilleure solution.

# Quelles sont les trois étapes principales de la stratégie diviser pour régner ? 1. [x] Diviser, Conquérir, Combiner > ✅ Diviser pour régner consiste à diviser le problème en sous-problèmes plus petits, les résoudre indépendamment, puis combiner leurs solutions. 1. [ ] Diviser, Résoudre, Itérer > ❌ Les étapes correctes sont diviser, conquérir et combiner, pas "résoudre" ou "itérer". 1. [ ] Diviser, Conquérir, Répéter > ❌ Bien que la répétition puisse avoir lieu, la troisième étape est "combiner", pas "répéter". # Quelle inefficacité peut survenir dans les implémentations récursives de diviser pour régner ? - [x] Calculs redondants dus à des sous-problèmes qui se chevauchent > ✅ Les sous-problèmes qui se chevauchent peuvent entraîner la répétition des mêmes calculs, ce qui cause une inefficacité. - [ ] Le besoin de réécrire le problème récursivement > ❌ Le problème est les calculs redondants, pas la nécessité de réécrire le problème. - [x] Complexité temporelle exponentielle dans certains cas > ✅ Sans optimisation, la récursion diviser pour régner peut conduire à une complexité temporelle exponentielle. - [ ] Difficulté à combiner les solutions des sous-problèmes > ❌ Bien que la combinaison puisse être complexe, l’inefficacité principale vient des calculs redondants. - [ ] Les problèmes doivent toujours être divisés de manière égale > ❌ La taille des sous-problèmes peut varier ; la division égale n’est pas une exigence stricte. # Comment la mémoïsation améliore-t-elle les algorithmes récursifs ? - [x] En stockant et réutilisant les résultats des sous-problèmes déjà calculés > ✅ La mémoïsation évite les calculs redondants en mettant en cache les résultats des sous-problèmes résolus. - [ ] En exécutant tous les sous-problèmes simultanément > ❌ La mémoïsation ne consiste pas à exécuter en parallèle, mais à mettre en cache les résultats pour éviter la recomputation. - [x] En réduisant la complexité temporelle des sous-problèmes qui se chevauchent > ✅ La mémoïsation réduit la complexité temporelle en empêchant la recomputation des sous-problèmes qui se chevauchent. - [ ] En réduisant la complexité spatiale des appels récursifs > ❌ La mémoïsation augmente souvent la complexité spatiale à cause du stockage des résultats. - [ ] En éliminant le besoin de récursion > ❌ La mémoïsation fonctionne avec la récursion ; elle ne l’élimine pas. # Qu’est-ce qui distingue la programmation dynamique de la mémoïsation ? - [x] La programmation dynamique résout les problèmes de manière ascendante (bottom-up) > ✅ La programmation dynamique traite les sous-problèmes de façon itérative, en commençant par les plus petits, plutôt que récursivement. - [ ] La programmation dynamique utilise toujours moins de mémoire > ❌ La programmation dynamique peut utiliser plus de mémoire selon le problème et l’implémentation. - [x] La programmation dynamique évite la récursion en itérant sur les sous-problèmes > ✅ Contrairement à la mémoïsation, la programmation dynamique évite la récursion en résolvant les sous-problèmes de manière itérative. - [ ] La mémoïsation est plus rapide que la programmation dynamique > ❌ L’efficacité de la mémoïsation et de la programmation dynamique dépend du problème, mais la programmation dynamique a souvent un léger avantage pour les problèmes itératifs. - [x] La programmation dynamique utilise une table pré-calculée pour les solutions des sous-problèmes > ✅ La programmation dynamique utilise une table pour stocker et consulter les solutions des sous-problèmes de manière structurée. # Quel est le principal avantage de la programmation dynamique ? - [x] Elle garantit que chaque sous-problème est résolu une seule fois > ✅ La programmation dynamique évite de recalculer les sous-problèmes, assurant l’efficacité en les résolvant une seule fois. - [ ] Elle garantit une complexité temporelle constante pour tous les problèmes > ❌ La programmation dynamique ne garantit pas une complexité constante ; son efficacité dépend du problème. - [x] Elle réduit la complexité temporelle par rapport à la récursion naïve > ✅ La programmation dynamique réduit significativement la complexité temporelle en évitant les calculs redondants. - [ ] Elle ne nécessite pas de mémoire supplémentaire > ❌ La programmation dynamique nécessite souvent de la mémoire supplémentaire pour stocker les solutions dans une table. - [ ] Elle élimine le besoin de dépendances entre sous-problèmes > ❌ La programmation dynamique repose explicitement sur la résolution structurée des dépendances entre sous-problèmes. # Qu’est-ce que le graphe des sous-problèmes en programmation dynamique ? - [x] Un graphe orienté acyclique montrant les dépendances entre sous-problèmes > ✅ Le graphe des sous-problèmes représente les dépendances, avec des arêtes indiquant quels sous-problèmes sont nécessaires pour en résoudre d’autres. - [ ] Un arbre qui répète les mêmes sous-problèmes > ❌ Le graphe des sous-problèmes évite la répétition en fusionnant les nœuds avec les mêmes étiquettes. - [x] Une version compactée de l’arbre d’appels récursifs > ✅ Le graphe des sous-problèmes est une représentation compacte qui évite les nœuds redondants en fusionnant les sous-problèmes dupliqués. - [ ] Une structure qui garantit une complexité temporelle linéaire > ❌ Bien que le graphe des sous-problèmes favorise l’efficacité, la complexité temporelle dépend du nombre de nœuds et d’arêtes. - [ ] Un graphe qui élimine les dépendances entre sous-problèmes > ❌ Le graphe des sous-problèmes montre explicitement les dépendances pour guider le processus de résolution.

# Quelle est la caractéristique clé de la programmation dynamique dans les problèmes d’optimisation ? - [x] Elle évite la recomputation en stockant les résultats intermédiaires > ✅ La programmation dynamique utilise la mémoïsation ou la tabulation pour stocker les résultats intermédiaires et éviter les calculs redondants. - [ ] Elle utilise le hasard pour explorer plusieurs solutions > ❌ La programmation dynamique est déterministe et ne repose pas sur le hasard. - [x] Elle décompose les problèmes en sous-problèmes qui se chevauchent > ✅ La programmation dynamique est efficace pour les problèmes avec des sous-problèmes qui se chevauchent et peuvent être résolus récursivement. - [ ] Elle garantit une complexité temporelle constante pour tous les problèmes > ❌ La complexité temporelle dépend de la taille et de la structure du problème, elle n’est pas constante pour tous les problèmes. - [ ] Elle produit toujours des solutions approximatives > ❌ La programmation dynamique vise à trouver des solutions exactes, pas des approximations. # Que signifie "structure optimale" dans le contexte de la programmation dynamique ? - [x] La solution optimale peut être construite à partir des solutions de ses sous-problèmes > ✅ La structure optimale signifie que la solution du problème entier peut être composée des solutions des sous-problèmes plus petits. - [ ] Chaque sous-problème doit avoir la même taille > ❌ Les sous-problèmes peuvent varier en taille ; l’essentiel est que leurs solutions se combinent pour résoudre le problème global. - [ ] Le problème doit toujours être divisé en deux parties > ❌ La programmation dynamique ne requiert pas que le problème soit divisé en exactement deux parties ; cela dépend de la structure du problème. - [x] La solution d’un sous-problème n’affecte pas les autres sous-problèmes > ✅ Les sous-problèmes en programmation dynamique sont indépendants, ce qui rend leurs solutions réutilisables. - [ ] L’algorithme s’exécute en temps logarithmique > ❌ La structure optimale ne garantit pas une complexité en temps logarithmique. # Quelle est l’approche gloutonne pour résoudre des problèmes ? - [x] Faire des choix localement optimaux à chaque étape > ✅ L’approche gloutonne choisit la meilleure option à chaque étape, visant un optimum global. - [ ] Explorer toutes les solutions possibles de manière exhaustive > ❌ Cela décrit les méthodes par force brute, pas les algorithmes gloutons. - [x] Prioriser la simplicité et l’efficacité plutôt que l’optimalité garantie > ✅ Les algorithmes gloutons sont efficaces et simples mais ne garantissent pas toujours la solution optimale. - [ ] S’assurer que tous les sous-problèmes sont résolus avant de combiner les solutions > ❌ Cette approche décrit la programmation dynamique, pas les algorithmes gloutons. - [x] Fournir parfois des solutions exactes selon la structure du problème > ✅ Les algorithmes gloutons peuvent produire des solutions exactes pour les problèmes qui possèdent la propriété du choix glouton. # Quel est le principal inconvénient de l’approche gloutonne ? - [x] Elle peut manquer l’optimum global > ✅ Les algorithmes gloutons se concentrent sur des décisions locales et peuvent négliger de meilleures solutions globales. - [ ] Elle nécessite toujours plus de ressources computationnelles que la programmation dynamique > ❌ Les algorithmes gloutons sont généralement plus économes en ressources que la programmation dynamique. - [x] Elle suppose que les optima locaux conduisent à des optima globaux > ✅ Les algorithmes gloutons supposent que les choix localement optimaux conduisent à des solutions globalement optimales, ce qui n’est pas toujours vrai. - [ ] Elle ne peut pas gérer les problèmes d’optimisation > ❌ Les algorithmes gloutons peuvent résoudre des problèmes d’optimisation, mais leur efficacité dépend de la structure du problème. - [ ] Elle nécessite des sous-problèmes qui se chevauchent > ❌ Les sous-problèmes qui se chevauchent sont une caractéristique de la programmation dynamique, pas des algorithmes gloutons.