Supposons que soit un langage booléen, de chaînes finies sur . Soit le nombre de chaînes de de longueur . Pour une fonction des entiers positifs aux nombres réels positifs, a une densité supérieure si L n ≤ 2 n d ( n ) pour tout n suffisamment grand
Je recherche le texte intégral du résultat de la clique Moon and Moser 1965 On Cliques in Graphs (il existe des graphes avec un certain nombre de cliques maximales exponentielles en ). Le mur de paiement de mon université n'a pas accès au journal en question. (En fait, l' aperçu fournit les...
Je recherche des notes de cours disponibles en ligne ou d'autres ressources qui donnent une bonne introduction à la programmation parallèle, tout comme l'analogue parallèle des cours de base en informatique. Mon objectif est le suivant: alors que je suis en mesure de parler de division et de...
Existe-t-il un algorithme polynomial pour trouver, s'il en existe un, une araignée s'étendant sur un graphe donné ? Une araignée est un arbre avec au plus un nœud avec un degré supérieur à 2: je sais que diverses conditions de degré sur G (essentiellement, des degrés de nœud suffisamment grands)...
L'algorithme de Deutsch est un calcul quantique bien connu f(0)+f(1)mod2f(0)+f(1)mod2f(0) + f(1)\mod{2} avec une seule évaluation de fff . Si nous remplaçons +++ par ⋅⋅\cdot le problème semble devenir assez différent. Ma question est: existe-t-il un algorithme quantique calculant la valeur de...
Dans ma recherche d'articles de recherche sur les systèmes de types pour les langages impératifs, je ne trouve que des solutions pour un langage avec des références mutables mais sans véritables structures de contrôle impératif telles que des opérateurs composés, des boucles ou des conditionnelles....
Je suis assez familier avec la théorie derrière VC-Dimension, mais je regarde maintenant les progrès récents (10 dernières années) dans la théorie de l'apprentissage statistique: moyennes Rademacher (locales), Lemme de classe finie de Massart, Covering Numbers, Chaining, Dudley's Théorème,...
Soit un graphique avec des arêtes pondérées (positivement). Je veux définir le diagramme de Voronoi pour un ensemble de nœuds / sites S , associer à un nœud v ∈ S le sous-graphe R ( v ) de G induit par tous les nœuds strictement plus proche de v que de tout autre nœud en S , mesurant la longueur...
Quel est l'état de l'art sur la complexité des requêtes des formules 2-DNF d'apprentissage PAC appropriées avec des exemples de requêtes et sous une distribution uniforme ? Ou tout lien non trivial dessus? Parce que je ne connais pas du tout la théorie de l'apprentissage et que cette question est...
Quelle est la meilleure limite actuelle pour effectuer des requêtes de comptage de demi-espace sur un ensemble de points dimensionnels, exprimée sous la forme d'un compromis temps / espace. Selon l'article fondamental de Matousek de 1993 (Théorème 6.2, Recherche de plage avec des coupes...
Dans l'étude sur deux problèmes de théorie de l'information , Erdõs et Rényi donnent des limites inférieures sur le nombre minimum de pesées à faire pour déterminer le nombre de fausses pièces dans un ensemble de pièces.nnn Plus formellement: Les fausses pièces ont un poids plus petit que les...
JBV a suggéré de transformer certains commentaires en question, alors voici. Une autre question [1] pose sur les applications de l'informatique QM. Une réponse [2] était "simuler efficacement la mécanique quantique". Apparemment, cette idée remonte aux premiers écrits de Feynman sur le sujet; même...
Il y a quelques années, j'ai rencontré la règle de gauche suivante pour l'égalité dans le calcul séquentiel: s≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢Cs≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢C \frac{s \doteq t \leadsto \theta \qquad \theta(\Gamma) \vdash \theta(C)} {\Gamma, s \doteq t \vdash C} Ici, s≐t⇝θs≐t⇝θs \doteq t \leadsto \theta...
Soit un ensemble de bases mutuellement non biaisées (MUB) dans C n , c'est-à-dire que chaque B i est une base orthonormée et pour v ∈ B i , w ∈ B j , i ≠ j we avoir | ⟨ V | w ⟩ | = 1B= { B1, … , Bk}B={B1,…,Bk}\mathcal{B} = \{B_1, \dots, B_k\}CnCn\mathbb{C}^nBjeBiB_iv ∈ Bje, w ∈ Bj, i ≠...
Les représentations les plus simples pour les graphiques utilisent des matrices / listes d'adjacence, ce qui signifie que chaque nœud et bord est explicitement représenté. L'importance des représentations implicites pour les graphiques présentant de fortes régularités est reconnue depuis longtemps....
Soit . J'ai besoin de générer de simples graphiques G de circonférence g de telle sorte que l'ensemble de tous les g- cycles forme une couverture de double bord de G (c'est-à-dire que chaque bord est partagé par exactement deux g- cycles), et de telle sorte que l'intersection de deux g -cycles est...
Récemment, j'ai lu un nombre décent d'articles CoLT. Bien que je ne lutte pas avec les articles individuels (du moins pas plus que d'habitude avec les autres articles théoriques), je ne pense pas avoir une bonne compréhension du domaine dans son ensemble. Existe-t-il un texte standard, des sondages...
Je recherche des références sur la complexité du problème d' équilibrage des formules booléennes . En particulier, Savait-on que les formules booléennes pouvaient être équilibrées en ?AC0AC0\mathsf{AC^0} Existe-t-il une preuve simple de l'équilibrage de la formule booléenne en ?AC0AC0\mathsf{AC^0}...
J'écris ma thèse de master en CS et je travaille avec l'analyse d'alias. Ce qui m'intéresse, c'est l'analyse intraprocédurale, sensible aux flux et must-alias pour les langages de type Java. Je recherche des textes qui décrivent les bases de ce sujet de manière détaillée mais je n'ai pas pu trouver...
J'ai entendu parler d'un résultat de coloration approximative du graphique, mais je ne trouve pas la source. Le résultat est: Pour chaque constante il existe un suffisamment grand pour que la coloration d'un graphique colorable avec des couleurs soit NP-difficile.hhhkkkkkkh khkhk Quelqu'un...