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