- 1. La théorie de la complexité informatique est une branche de l'informatique théorique qui se concentre sur la classification des problèmes informatiques en fonction de leur difficulté inhérente et de la quantité de ressources nécessaires, telles que le temps et l'espace. Elle permet de comprendre l'efficacité des algorithmes, d'analyser la faisabilité de la résolution de problèmes sur différents types de machines et de déterminer les limites de la puissance de calcul. En étudiant la théorie de la complexité informatique, les chercheurs cherchent à explorer les limites de l'informatique et à identifier les capacités et les limites des ordinateurs dans la résolution de divers types de problèmes.
Sur quoi porte la théorie de la complexité informatique ?
A) Conception de matériel informatique
B) Aspects psychologiques de l'interaction homme-machine
C) Analyser les ressources nécessaires pour résoudre les problèmes de calcul
D) Développement de nouveaux langages de programmation
- 2. Quelle est la notation couramment utilisée pour indiquer la complexité des algorithmes ?
A) Code binaire
B) Lettres grecques
C) Notation du grand O
D) Chiffres romains
- 3. Quelle classe de complexité contient les problèmes de décision qui sont efficacement vérifiables ?
A) NP
B) BPP
C) EXP
D) PSPACE
- 4. Quelle classe de complexité est utilisée pour classer les problèmes qui peuvent être résolus par un ordinateur quantique en un temps polynomial ?
A) PSPACE
B) NP-complet
C) BQP
D) EXPSPACE
- 5. Quel est l'objectif principal de la théorie de la complexité informatique ?
A) Construire des superordinateurs
B) Classer les problèmes informatiques en fonction de leur difficulté inhérente
C) Pour générer des nombres aléatoires
D) Créer des ordinateurs plus rapides
- 6. Quel est le lien entre le théorème de Cook-Levin et la théorie de la complexité informatique ?
A) NP-complétude
B) Algorithmes quantiques
C) Problème P vs NP
D) Calculs parallèles
- 7. Que signifie "EXP" dans la théorie de la complexité informatique ?
A) Élargi
B) Temps exponentiel
C) Expert
D) Exploratoire
- 8. Quelle est la classe de complexité qui représente les problèmes les plus difficiles dans NP ?
A) NP-complet
B) BPP
C) P
D) EXPTIME
|