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