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