Comment puis-je prouver que la conversion de CNF en DNF est NP-difficile? Je ne demande pas de réponse, juste quelques suggestions sur la façon de le
Le raffinement de partition est une technique dans laquelle vous commencez avec un ensemble fini d'objets et divisez progressivement l'ensemble. Certains problèmes, comme la minimisation DFA, peuvent être résolus en utilisant le raffinement de partition assez efficacement. Je ne connais pas...
Dans mon cours de théorie de l'informatique, beaucoup de nos problèmes impliquent l'utilisation de l'induction sur la longueur de la chaîne d'entrée pour prouver les déclarations sur les automates finis. Je comprends l'induction mathématique, mais lorsque les cordes entrent en jeu, je suis vraiment...
Considérons une représentation en virgule fixe qui peut être considérée comme un cas dégénéré d'un nombre flottant. Il est tout à fait possible d'utiliser le complément à 2 pour les nombres négatifs. Mais pourquoi un bit de signe est-il nécessaire pour les nombres à virgule flottante, les bits de...
Tous les automates finis non déterministes peuvent être transformés en automates finis déterministes équivalents. Cependant, un automate fini déterministe ne permet qu'une seule flèche par symbole pointant à partir d'un état. Par conséquent, ses États devraient être membres de l'ensemble des États...
C'est peut-être assez simple, mais j'ai du mal à obtenir cette réduction. Je veux réduire la somme des sous-ensembles à la partition, mais pour le moment je ne vois pas la relation! Est-il possible de réduire ce problème en utilisant une réduction Levin? Si vous ne comprenez pas, écrivez pour...
J'ai commandé quelques feuilles de cuir à partir desquelles j'aimerais construire des balles de jonglage en cousant des bords ensemble. J'utilise les solides platoniciens pour la forme des boules. Je peux numériser les feuilles de cuir et générer un polygone qui se rapproche de la forme de la...
Je dois trouver un cycle négatif dans un graphique pondéré dirigé. Je sais comment fonctionne l'algorithme de Bellman Ford et qu'il me dit s'il y a un cycle négatif atteignable. Mais il ne le nomme pas explicitement. Comment puis-je obtenir le chemin réel du cycle?v 1 , v 2 , … v k , v...
Est-il possible que et la cardinalité de soit la même que la cardinalité de ? Ou signifie-t-il que et doivent avoir des cardinalités différentes?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =
J'ai entendu dire que la génération de nombres aléatoires dans les ordinateurs n'est pas vraiment aléatoire, mais il n'y a pas d'algorithme efficace pour le détecter. Comment peut-il être
De nombreux algorithmes de flux max que je vois couramment implémentés, l'algorithme de Dinic, le réétiquetage push et d'autres, peuvent voir leur coût asymptotique en temps amélioré grâce à l'utilisation d' arbres dynamiques (également appelés arbres coupés de liens). Push relabel s'exécute en ou...
Le théorème maître est un bel outil pour résoudre certains types de récurrences . Cependant, nous masquons souvent une partie intégrante lors de son application. Par exemple, lors de l'analyse de Mergesort, nous sommes heureusement passés de T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad...
Souvent, si les complexités ont des constantes telles que 3n, nous négligeons cette constante et disons O (n) et non O (3n). Je n'arrive pas à comprendre comment pouvons-nous négliger ce triple changement? Une chose varie 3 fois plus rapidement qu'une autre! Pourquoi négligeons-nous ce fait?...
Dans la conception du compilateur, pourquoi la récursion gauche devrait-elle être éliminée dans les grammaires? Je lis que c'est parce que cela peut provoquer une récursion infinie, mais n'est-ce pas également vrai pour une grammaire récursive
Existe-t-il une méthode générale pour résoudre la récurrence du formulaire: T(n)=T(n−nc)+T(nc)+f(n)T(n)=T(n−nc)+T(nc)+f(n)T(n) = T(n-n^c) + T(n^c) + f(n) pour c<1c<1c < 1 , ou plus généralement T(n)=T(n−g(n))+T(r(n))+f(n)T(n)=T(n−g(n))+T(r(n))+f(n)T(n) = T(n-g(n)) + T(r(n)) + f(n) où...
Ceci est inspiré d'une question d'entrevue . On nous donne un tableau d'entiers et devons déterminer s'il existe des distincts tels que i < j < kune1, … , Unna1,…,ana_1, \dots, a_ni < j < ki<j<ki \lt j \lt k unek- unj= aj- unjeak−aj=aj−aia_k - a_j = a_j - a_i k - j = j - ik−j=j−ik...
Wikipedia indique que le problème de la somme des sous-ensembles consiste à trouver un sous-ensemble d'un multiset donné d'entiers, dont la somme est nulle. De plus, il déclare qu'il revient à trouver un sous-ensemble avec la somme sss pour tout sss donné . Je pense donc que comme ils sont...
Les langages sans contexte ne sont pas fermés sous complément, nous le savons. Pour autant que je sache, les langages sans contexte qui sont un sous-ensemble de pour certaines lettres sont fermés sous complément (!?) a , ba∗b∗a∗b∗a^*b^*a,ba,ba,b Voici mon argument. Chaque langue CF a une image...
Le tri Radix est théoriquement très rapide lorsque vous savez que les clés sont dans une certaine plage limitée, disons valeurs dans la plage [ 0 … n k - 1 ] par exemple. Si k < lg n, vous venez de convertir les valeurs en base n, ce qui prend du temps Θ ( n ) , effectuez un tri radix en base n...
J'interagis souvent avec des gens qui veulent demander un algorithme pour un problème de calcul (ou sa complexité), mais ils ne l'expriment pas de manière rigoureuse pour nous (les informaticiens) à comprendre. Les renvoyer à des livres comme CLRS n'est pas utile parce que les exemples là-bas ont...