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