A) Aspects psychologiques de l'interaction homme-machine B) Conception de matériel informatique C) Analyser les ressources nécessaires pour résoudre les problèmes de calcul D) Développement de nouveaux langages de programmation
A) Code binaire B) Notation du grand O C) Lettres grecques D) Chiffres romains
A) PSPACE B) EXP C) NP D) BPP
A) PSPACE B) NP-complet C) BQP D) EXPSPACE
A) Créer des ordinateurs plus rapides B) Construire des superordinateurs C) Classer les problèmes informatiques en fonction de leur difficulté inhérente D) Pour générer des nombres aléatoires
A) Calculs parallèles B) Problème P vs NP C) NP-complétude D) Algorithmes quantiques
A) Temps exponentiel B) Élargi C) Exploratoire D) Expert
A) BPP B) NP-complet C) EXPTIME D) P
A) Un problème matériel dans les ordinateurs. B) Une équation mathématique qui ne peut pas être résolue. C) Une question théorique insoluble. D) Une tâche résolue par un ordinateur en utilisant un algorithme.
A) L'ensemble de toutes les lettres minuscules B) L'ensemble des caractères ASCII C) L'alphabet hexadécimal D) L'alphabet binaire {0, 1}
A) Aucun codage n'est nécessaire B) Un choix concret de codage des entrées C) Codage utilisant le langage naturel D) Utilisation exclusive de la notation décimale
A) Déterminer le nombre de nœuds dans un graphe. B) Trouver le chemin le plus court dans un graphe. C) Calculer le flux maximal dans un réseau. D) Déterminer si un graphe donné est connexe ou non.
A) Vérifier si un graphe est bipartite. B) Le problème du voyageur de commerce. C) Déterminer si un nombre est premier. D) Déterminer si deux graphes sont isomorphes.
A) Mots B) Caractères C) Bits D) Octets
A) Un dispositif pour manipuler des objets physiques. B) Une technologie informatique pratique. C) Une forme primitive de matériel informatique. D) Un modèle théorique pour le calcul général.
A) La thèse de Church-Turing. B) Les théorèmes d'incomplétude de Gödel. C) Le théorème P versus NP. D) Le théorème de Cook-Levin.
A) Machine de Turing quantique. B) Machine de Turing déterministe. C) Machine de Turing non déterministe. D) Machine de Turing probabiliste.
A) Ils utilisent des bits aléatoires pour les calculs. B) Ils sont limités à un temps polynomial. C) Ils fonctionnent de manière déterministe. D) Ils nécessitent une réalisation physique.
A) Axiomes de complétude de Turing B) Théorème de Cook-Levin C) Axiomes de complexité de Blum D) Axiomes liés à la complexité P vs NP
A) Complexité de l'intrication quantique B) Complexité des arbres de décision C) Complexité de la communication D) Complexité des circuits
A) Complexité de communication B) Complexité de circuit C) Complexité temporelle D) Complexité spatiale
A) Théorème de hiérarchie des complexités spatiales B) Théorème de Savitch C) Théorème de hiérarchie des complexités temporelles D) Théorème de Cook-Levin
A) Calculs en temps réel B) Ensembles élémentaires C) Mesures de complexité D) Automates à mémoire linéaire
A) 1956 B) 1971 C) 1955 D) 1960
A) BPP B) RP C) QMA D) AC
A) Downey, Rod; Fellows, Michael B) Papadimitriou, Christos; Sipser, Michael C) Wuppuluri, Shyam; Doria, Francisco A. D) Cook, Stephen; Fortnow, Lance
A) NC B) RP C) BPP D) #P
A) FP B) EXPTIME C) PSPACE D) NP
A) 21 B) 10 C) 30 D) 15
A) Machines à états finis. B) Traitement numérique du signal. C) Algorithmes probabilistes. D) Systèmes dynamiques continus et équations différentielles.
A) Sanjeev Arora; Boaz Barak B) Christos Papadimitriou C) Oded Goldreich D) Michael R. Garey; David S. Johnson
A) Théorème de Cook-Levin B) Théorème de la hiérarchie temporelle C) Problème P vs NP D) Théorème de Savitch
A) EXPTIME B) NP C) TOUTES D) P
A) co-P ne serait pas égal à co-NP B) co-P serait égal à co-NP C) P ne serait pas égal à NP D) NP ne serait pas égal à co-NP
A) John Myhill B) Raymond Smullyan C) Hisao Yamada D) Boris Trakhtenbrot
A) PH B) PP C) MA D) BQP
A) Arora, Sanjeev ; Barak, Boaz B) Downey, Rod ; Fellows, Michael C) Wuppuluri, Shyam ; Doria, Francisco A. D) Garey, Michael R. ; Johnson, David S.
A) Cook, Stephen B) Mertens, Stephan C) Fortnow, Lance ; Homer, Steven D) Khalil, Hatem ; Ulery, Dana
A) « Fonction de signalisation » B) « Machine de Turing » C) « Complexité computationnelle » D) « Temps polynomial »
A) Fonctions continues. B) États quantiques. C) Expressions booléennes. D) Graphes discrets.
A) PP B) co-NP C) NP D) BQP
A) Sanjeev Arora ; Boaz Barak B) Christos Papadimitriou C) Michael R. Garey ; David S. Johnson D) Oded Goldreich
A) QMA B) NC C) AC D) BPP
A) Analyse amortie B) Complexité dans le cas moyen C) Complexité dans le cas le plus défavorable D) Complexité dans le cas optimal
A) PP B) NC C) NL D) L
A) 1965 B) 1950 C) 1945 D) 1936
A) Juris Hartmanis B) Gabriel Lamé C) Alan Turing D) Richard E. Stearns
A) Réduction en temps exponentiel. B) Réduction en temps polynomial. C) Réduction en temps linéaire. D) Réduction en temps logarithmique.
A) 1971 B) 1972 C) 1965 D) 1967
A) Hisao Yamada B) Boris Trakhtenbrot C) Raymond Smullyan D) John Myhill
A) QMA B) BPP C) IP D) NC
A) Edmonds B) Juris Hartmanis C) Leonid Levin D) Gabriel Lamé
A) Sanjeev Arora B) Michael Sipser C) Christos Papadimitriou D) Boaz Barak |