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