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