Je me demande s'il y a des problèmes durs qui sont "polynomiaux" dans le cas moyen. Je pense qu'il y a deux façons d'interpréter cela?NPNPNP Si , peut-il y avoir un algorithme résolvant un problème dur avec un temps d'exécution amorti (cas moyen) de pour une constante ?P≠NPP≠NPP \neq...
Sera-t-il nécessaire de changer les définitions de la sécurité si nous avons des ordinateurs quantiques? Quelles constructions cryptographiques vont casser? Connaissez-vous une enquête ou un article qui explique ce qui sera nécessaire pour
En raison de la nature de la question, je dois inclure beaucoup d'informations de base (parce que ma question est: comment puis-je restreindre cela?) Cela dit, cela peut être résumé (à ma connaissance) comme: Quelles méthodes existent pour trouver des optimums locaux sur des espaces de recherche...
L'algorithme de Brzozowski peut être étendu aux automates de Moore mais sa complexité temporelle est exponentielle en général. Existe-t-il un autre algorithme pour minimiser les automates Moore? Quels sont les temps d'exécution de ces algorithmes, le cas
Je ne connais pas la terminologie correcte pour poser cette question, donc je vais la décrire avec beaucoup de mots à la place, supportez-moi. Contexte , juste pour que nous soyons sur la même longueur d'onde: les programmes contiennent souvent des caches - un compromis temps / mémoire. Une erreur...
Je ne sais pas si cette question appartient ici et je m'en excuse sinon. Ce que je cherche à faire est de développer une manière programmatique dans laquelle je peux déterminer de manière probabiliste si une chaîne donnée "appartient" dans un sac de chaînes. Par exemple, si j'ai un sac de 10 000...
Je suis à la recherche d'un algorithme d'appariement rapide de chaînes k-mismatch. Étant donné une chaîne de motif P de longueur m et une chaîne de texte T de longueur n, j'ai besoin d'un algorithme rapide (temps linéaire) pour trouver toutes les positions où P correspond à une sous-chaîne de T...
Existe-t-il des langages de programmation (ou logique) qui peuvent implémenter (ou exprimer) une fonction si et seulement si est une fonction bijective calculable? ff:N→Nf:N→Nf:\mathbb{N}\to
Issu du POV de quelqu'un qui envisage de poursuivre un doctorat en informatique. J'ai du mal à décider sur quoi je concentrerais mes recherches lorsque je ferai mon doctorat. Voir aussi cette question sur academia.SE . Je pense donc que lire / se tenir au courant des recherches en cours et des...
Il existe un éventail parfois vertigineux de symboles utilisés dans les documents mathématiques et CS. Pourtant, beaucoup supposent une familiarité de base qui semble rarement enseignée au même endroit. Je cherche un dictionnaire quelque chose comme le suivant, en particulier du point de vue CS. Il...
Je recherche des ressources pour débuter avec l'analyse de programme . Le seul livre que j'ai trouvé sur le sujet est le livre Nielson & Nielson . En dehors de cela, il semble qu'il n'y ait que des livres de "compilateur" où "l'analyse de programme" serait un chapitre, ou quelque chose du...
Dans la programmation de type dépendant, il existe deux façons principales de décomposer les données et d'effectuer la récursivité: Correspondance de modèle dépendante : les définitions de fonction sont données sous forme de clauses multiples. L'unification garantit que tous les cas omis sont...
Je m'intéresse aux procédures de partage équitable des terres (c.-à-d. Partage sans envie, ou au moins partage proportionnel). Contrairement au problème bien étudié de division des gâteaux, la division des terres est bidimensionnelle, c'est-à-dire que les préférences des utilisateurs peuvent varier...
Un graphe est en corde s'il n'a pas de cycles induits de longueur ou plus. Un arbre de clique de est un arbre dont les sommets de l'arbre sont les cliques maximales de . Une arête en correspond à un séparateur minimal. Le nombre d'arbres cliques distincts peut être exponentiel dans le nombre de...
Je me demande, existe-t-il une méthode d'analyse automatique de l'exécution qui fonctionne au moins sur un sous-ensemble pertinent d'algorithmes (algorithmes pouvant être analysés)? Je googlé « Analyse de l' algorithme automatique » qui m'a donné ce mais il est MATHY aussi. Je veux juste un exemple...
Considérez les programmes linéaires D u a l : → c ≤ → y T APr i m a l :A x⃗ ≤ b⃗ max c⃗ TX⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} D u a l :c⃗ ≤ y⃗ TUNEmin...
Nous avons eu plusieurs questions sur la relation entre les réductions Cook et Karp . Il est clair que les réductions de Cook (réductions de Turing à temps polynomial) ne définissent pas la même notion de complétude NP que les réductions de Karp (réductions de plusieurs à un temps polynomial), qui...
La question est à peu près dans le titre. Y a-t-il jamais un moment où une langue peut être acceptée par un DFA minimal avec états, mais , l'inversion de , peut être acceptée par un DFA avec états, où ?LLLL R L m m < nnnnLRLRL^RLLLmmmm <
Je veux fournir des preuves pour des parties d'un programme Haskell que j'écris dans le cadre de ma thèse. Jusqu'à présent cependant, je n'ai pas réussi à trouver un bon ouvrage de référence. Le livre d'introduction de Graham Hutton, Programming in Haskell ( Google Books ) - que j'ai lu tout en...
Je décris une approche de l'isomorphisme graphique qui a probablement des faux positifs, et je suis curieux de savoir s'il existe de la littérature indiquant que cela ne fonctionne pas. Étant donné deux matrices d'adjacence , une méthode certes naïve de vérification de l'isomorphisme consiste à...