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