Chapitre1AACQuiz

La classe des problèmes pour lesquels il existe un algorithme qui peut trouver une solution en un temps polynomial. La durée d'exécution de l'algorithme ne dépasse jamais un multiple de n^c pour des entrées suffisamment grandes.

Les problèmes de la classe P sont considérés comme "facilement résolvables" car des algorithmes peuvent traiter des entrées de taille raisonnable en un temps acceptable.

Un algorithme dont le temps d'exécution est borné par un polynôme en fonction de la taille de l'entrée. Exemple : O(n^2), O(n^3).

Un problème peut être solutionné par un algorithme polynomial. Par exemple, le tri à bulles.

Un algorithme qui trie les éléments d'un tableau en les comparant deux à deux et en les échangeant si nécessaires.

Consister à parcourir un tableau et à comparer l'élément en cours avec l'élément suivant. Si les éléments sont dans le mauvais ordre, ils sont échangés.

Un algorithme de tri qui divise le tableau en deux sous-tableaux, trie chacun des sous-tableaux, puis combine les deux sous-tableaux triés en un seul tableau trié.

Un algorithme de tri qui choisit un pivot dans le tableau, partitionne le tableau en deux sous-tableaux et trie récursivement les deux sous-tableaux.

La gestion de la mémoire est un concept important en informatique, consistant à gérer l'allocation, la libération et l'organisation de la mémoire utilisée par les programmes. Les algorithmes n'abordent généralement pas ce concept car ils se concentrent sur la résolution de problèmes logiques, tandis que la gestion de la mémoire est un aspect lié à l'implémentation et à l'exécution.

Un algorithme doit être traduit en code source pour pouvoir être exécuté sur un ordinateur. Cela implique de choisir un langage de programmation et de convertir les étapes de l'algorithme en instructions compréhensibles par la machine.

Les tests et le débogage sont essentiels pour garantir que le code implémentant un algorithme fonctionne correctement. Ils permettent de détecter et de corriger les erreurs (bugs) qui peuvent se produire dans le code.

L'allocation dynamique de mémoire permet aux programmes de demander de la mémoire au moment de l'exécution, selon leurs besoins, plutôt que de devoir spécifier une quantité fixe à l'avance. Cela offre une flexibilité et une gestion optimisée de la mémoire.

La libération de mémoire, également appelée désallocation, est le processus de retour de la mémoire précédemment allouée au système d'exploitation une fois qu'elle n'est plus nécessaire. Cela empêche les fuites de mémoire et permet une utilisation efficace de la mémoire.

Les pointeurs sont des variables qui stockent des adresses mémoire. Ils permettent aux programmes d'accéder directement à des données dans la mémoire, ce qui offre un contrôle fin sur la gestion de la mémoire.

La gestion des pointeurs est cruciale pour une programmation efficace et sécurisée. Elle implique de manipuler les pointeurs correctement pour éviter les erreurs courantes comme les déréférencements de pointeurs nulls ou les accès mémoire non autorisés.

Un problème NP-complet est un problème pour lequel il est difficile de trouver une solution mais facile de vérifier si une solution candidate est correcte.

Un algorithme non déterministe peut tester simultanément plusieurs solutions candidates, ce qui est plus efficace que de tester chaque solution de manière séquentielle.

Tous les problèmes de la classe P sont aussi des problèmes de la classe NP, ce qui signifie que si un problème peut être résolu rapidement, il peut aussi être vérifié rapidement.

Le processus de vérification est essentiel pour rendre les problèmes NP-complets plus faciles à utiliser dans des applications pratiques.

Les algorithmes non déterministes peuvent masquer la complexité inhérente aux problèmes NP-complets en vérifiant plusieurs solutions candidate en même temps.

La difficulté de prouver qu'un problème de NP n'appartient pas à P témoigne du défi posé par l'étude de la complexité computationnelle.

La question de savoir si P=NP est l'un des problèmes les plus fondamentaux en informatique théorique. Si P=NP, tous les problèmes vérifiables en temps polynomial pourraient être résolus en temps polynomial. Si P≠NP, il existe des problèmes dont la verification est plus facile que la résolution.

Déterminer si une formule booléenne peut être satisfaite par une certaine attribution de valeurs de vérité pour ses variables.

Étant donné un graphe, déterminer s'il existe un sous-ensemble de k sommets tels que chaque paire de sommets dans ce sous-ensemble soit connectée par une arête.

Trouver le chemin le plus court pour visiter un ensemble de villes et revenir à la ville d'origine.

La classe NP est un ensemble de problèmes où l'on peut vérifier une solution en temps polynomial.

La classe NP est un ensemble de problèmes dont la résolution peut être vérifiée en temps polynomial.

La classe NP (Nondeterministic Polynomial time) en théorie de la complexité computationnelle regroupe les problèmes pour lesquels, une fois qu'une solution potentielle est proposée, on peut vérifier cette solution en un temps polynomial par rapport à la taille de l'entrée.

Un problème appartient à NP s'il existe une machine de Turing non déterministe qui accepte une entrée x en temps polynomial, où cette acceptation dépend de la présence d'une 'preuve' ou d'un 'certificat' y qui peut être vérifié en temps polynomial.

Le processus de vérifier si une solution potentielle satisfait les critères ou contraintes du problème. Cette vérification doit être effectuée par une machine de Turing déterministe en temps polynomial.

Représente une instance du problème que l'on souhaite résoudre, par exemple les nombres à additionner dans un problème d'addition.

Représente une 'preuve' ou un 'certificat' qui permet de vérifier si la solution x est correcte. Par exemple, dans un problème de coloration de graphe, le certificat pourrait être la coloration elle-même.

V (x, y) est une fonction qui vérifie si la solution x est correcte en utilisant le certificat y. Cette vérification doit être effectuée en temps polynomial.

La taille de l'entrée x. Par exemple, pour un problème d'addition, la taille de l'entrée serait le nombre de chiffres dans les nombres à additionner.

Un polynôme p qui représente la limite supérieure du temps de l'algorithme de vérification V en fonction de la taille de l'entrée x.

Une réduction polynomiale entre deux problèmes, notée B ≤ p A, signifie qu'un algorithme efficace pour résoudre A implique automatiquement un algorithme efficace pour résoudre B.

Un problème NP-difficile est un problème auquel tout problème dans NP peut être réduit en temps polynomial.

Si B ≤ p A et A est NP-difficile, alors B est également NP-difficile. Cela signifie que B est 'au moins aussi difficile à résoudre' que A.

Une méthode efficace pour résoudre A peut être utilisée pour résoudre B par le biais de la réduction.

La réduction polynomiale permet de classer les problèmes en fonction de leur difficulté relative.

La transformation d'une instance de B en une instance équivalente de A doit être effectuée en temps polynomial.

La réduction consiste à transformer une instance du problème B en une instance équivalente du problème A.

La réduction polynomiale est un outil puissant pour comprendre les hiérarchies de complexité et identifier des problèmes équivalents en termes de difficulté.

Signup and view all the flashcards