La complexité spatiale de la reconnaissance des palindromes Watson-Crick

J'ai le problème algorithmique suivant:

Déterminer l'espace Turing complexité de reconnaître les chaînes d'ADN qui sont des palindromes Watson-Crick.

Les palindromes Watson-Crick sont des chaînes dont le complément inversé est la chaîne d'origine. Le complément est défini par lettre, inspiré de l'ADN: A est le complément de T et C est le complément de G. Un exemple simple pour un palindrome WC est ACGT.

J'ai trouvé deux façons de résoudre ce problème.

L'un nécessite un espace . $\mathcal{O}(n)$

Une fois que la machine a fini de lire l'entrée. La bande d'entrée doit être copiée sur la bande de travail dans l'ordre inverse.
La machine lira ensuite les bandes d'entrée et de travail à partir de la gauche et comparera chaque entrée pour vérifier que la cellule dans la bande de travail est le complément de la cellule dans l'entrée. Cela nécessite un espace . $\mathcal{O}(n)$

L'autre nécessite un espace $\mathcal{O}(\log n)$ .

Lors de la lecture de l'entrée. Comptez le nombre d'entrées sur la bande d'entrée.
Lorsque la lecture de la bande d'entrée est terminée
- copier le complément de la lettre sur la bande de travail
- copiez la lettre L à la fin de la bande de travail
(Point de boucle) Si le compteur = 0, effacez la bande de travail et écrivez oui, puis arrêtez
Si la bande d'entrée indique L
- Déplacer la tête d'entrée vers la gauche du nombre de fois indiqué par le compteur (nécessite un deuxième compteur)
Si la bande d'entrée indique R
- Déplacer la tête d'entrée vers la droite du nombre de fois indiqué par le compteur (nécessite un deuxième compteur)
Si la cellule qui contient la valeur sur la bande de travail correspond à la cellule actuelle sur la bande d'entrée
- décrémenter le compteur de deux
- Déplacez-en un vers la gauche ou la droite selon que R ou L est sur la bande de travail respectivement
- copier le complément de L ou R sur la bande de travail à la place du L ou R actuel
- continue la boucle
Si les valeurs ne correspondent pas, effacez la bande de travail et écrivez non, puis arrêtez

Cela revient à environ espace pour stocker les deux compteurs, le complément actuel et la valeur L ou R. $2\log n+2$

Mon problème

Le premier nécessite à la fois du temps et de l'espace linéaires. La seconde nécessite temps et espace. On m'a donné le problème de la citation et j'ai proposé ces deux approches, mais je ne sais pas laquelle choisir. J'ai juste besoin de donner la complexité spatiale du problème. $\frac{n^2}{2}$ $\log n$

La raison pour laquelle je suis confus

J'aurais tendance à dire que la seconde est la meilleure option car elle est meilleure en termes de temps, mais cette réponse ne vient que de ma chance et de l'élaboration d'un algorithme. Il semble que si je veux donner la complexité spatiale de quelque chose, il ne faudrait pas de chance pour trouver le bon algorithme. Suis-je en train de manquer quelque chose? Dois-je même trouver une solution au problème pour répondre à la complexité de l'espace?

algorithms algorithm-analysis turing-machines space-complexity justausr
la source

Je pense que la question serait encore meilleure si vous donniez un pseudocode pour les algorithmes. Recherchez ici de l'aide sur le formatage.

Raphael

Réponses:

Avertissement : L'algorithme suivant n'utilise pas le modèle standard pour la complexité de l'espace sublinéaire (voir WP: DSPACE ), car il écrit sur la bande d'entrée. De plus, l'ensemble des palindromes (Watson-Crick) n'est pas dans . Néanmoins, c'est une solution sur place à de nombreuses fins pratiques (par exemple, si chaque lettre est un en C). $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$ char

Pour montrer qu'un problème a une complexité d'espace spécifique, il faut généralement trouver un algorithme qui a cette complexité d'espace. Cela peut nécessiter des essais et des erreurs, mais une meilleure approche consiste à avoir une bonne compréhension du problème que vous regardez et une bonne expérience des algorithmes et de la complexité.

Pour cet exemple particulier, il existe un troisième algorithme qui ne nécessite aucun espace supplémentaire et nécessite une complexité temporelle . Cet algorithme serait à espace constant. $O(n^2)$

Astuce: pourquoi utiliser de l'espace supplémentaire, quand vous pouvez utiliser l'espace occupé par l'entrée?

Astuce: zippez dans la chaîne en vérifiant un caractère à la fois - utilisez l'état de la machine de Turing pour vous souvenir du caractère que vous vérifiez et effacez les caractères que vous avez déjà vérifiés.

Dave Clarke
la source

c'est ce que fait mon deuxième algorithme. Pour aller et venir sur une chaîne, vous avez besoin de compteurs. Pour une entrée de longueur, vous avez besoin d'un espace log n pour stocker le compteur. À moins que je ne comprenne mal, mais il semble que vous ne pouviez pas faire des allers-retours sur la chaîne sans garder une trace de la partie qui a été comparée

justausr

Pourquoi avez-vous besoin de stocker un comptoir?

Dave Clarke

Si j'atteins la fin de l'entrée et qu'elle fait 10 caractères. Je dois revenir en arrière de 10 caractères et enregistrer le dernier caractère de l'entrée. Une fois arrivé au début, je compare et copie le deuxième caractère et je me déplace vers la droite 7 fois et vérifie que le deuxième caractère correspond au 9ème. Comment puis-je savoir que c'est 7 fois, sauf si je l'ai suivi?

justausr

La tête ne peut se trouver qu'à un seul endroit sur la bande à la fois, mais l'état de la MT peut se souvenir de ce que la tête a vu, et on peut marquer la bande avec d'autres caractères pour indiquer quelles parties de la bande ont déjà été visitées ( dans certaines phases de l'algorithme).

Dave Clarke

Je ne vois pas ce que tu veux dire. Si vous effacez ou marquez les caractères dans le flux d'entrée (avec la même marque), vous pouvez facilement déterminer quand vous avez fini de traiter la chaîne d'entrée car vous manquez de chaîne d'entrée.

Dave Clarke

La façon dont la question est posée, vous devriez trouver une limite supérieure et une limite inférieure sur la complexité de l'espace.

La première partie se fait généralement en présentant un algorithme pour votre problème, mais une réduction à un autre problème bien étudié fonctionnerait également (et produirait indirectement un algorithme aussi). Puisque vous ne considérez pas une complexité combinée (temps et espace), seul l'espace compte, même si le temps augmente. Vous avez donc trouvé une limite supérieure de . $\mathcal{O}(\log n)$

La deuxième partie est généralement beaucoup plus délicate, mais vous pouvez facilement montrer qu'un espace constant n'est pas suffisant, car cela rendrait votre langue régulière. En utilisant le lemme de pompage avec, disons , où est le nombre de pompage supposé fera l'affaire. Cela laisse encore un grand écart entre et . $a^lb^{2l}a^l$ $l$ $\omega(1)$ $\mathcal{O}(\log n)$

J'ai trouvé un exercice (voir exercice 6) qui donne quelques indices. Si j'interprète correctement leur indice, essayez de prouver qu'il existe de nombreuses classes d'équivalence différentes de la relation Myhill-Nerode pour chaque taille d'entrée. Ceci est similaire à l'argument selon lequel vous ne pouvez pas distinguer plus de chaînes de longueur (où est votre alphabet de bande et votre complexité d'espace). Cela vous donnera une limite inférieure de . $c\cdot\Gamma^{s(n)}$ $n$ $\Gamma$ $s(n)$ $\Omega(\log n)$

Notez que vous n'avez pas besoin de vous soucier du complément de lettres car cette opération est triviale, donc tout ce qui fonctionne pour les palindromes ordinaires peut être modifié avec quelques états supplémentaires pour résoudre votre problème.

frafl
la source

Il est extrêmement probable que le compromis temps-espace classique pour les palindromes se vérifie également dans votre cas. Ce résultat indique qu'une machine de Turing reconnaissant des palindromes dans l'espace doit prendre du temps , c'est-à-dire Dans votre cas, le premier algorithme a et le second a . On peut également montrer que la limite inférieure de l'espace est . Je n'ai pas pu trouver quelle est la meilleure borne supérieure - c'est-à-dire s'il existe un algorithme utilisant l'espace et le temps logarithmique , ou en général, pour quelles valeurs de $S$ $\Omega(n^2/S)$

Time \times Space = Ω (n^{2}) .

$\textrm{Time} \times \textrm{Space} = \Omega(n^2).$

T S = Θ (n^{2})

$TS = \Theta(n^2)$

T S = Θ (n^{2} \log n)

$TS = \Theta(n^2\log n)$

Ω (\log n)

$\Omega(\log n)$

O (n^{2} / \log n)

$O(n^2/\log n)$

S

$S$ pouvons-nous atteindre le temps . Comme exercice, vous pouvez essayer de trouver d'autres algorithmes hybrides interpolant vos deux algorithmes.

Ω (n^{2} / S)

$\Omega(n^2/S)$

Yuval Filmus
la source