Connexion
Statistiques
Nous avons 897 membres enregistrésL'utilisateur enregistré le plus récent est ExoSlashNos membres ont posté un total de 6295 messagesdans 683 sujets
Qui est en ligne ?
Il y a en tout 6 utilisateurs en ligne :: 0 Enregistré, 0 Invisible et 6 Invités :: 1 Moteur de recherche

Aucun

Voir toute la liste

Aimez notre page Facebook !
Les posteurs les plus actifs du mois
4 Messages - 25%
4 Messages - 25%
3 Messages - 19%
3 Messages - 19%
2 Messages - 13%
Les posteurs les plus actifs de la semaine
Publicité
Partagez
Voir le sujet précédentAller en basVoir le sujet suivant
Posteur Débutant
Posteur Débutant
Messages : 1
Voir le profil de l'utilisateur

Machine de Turing et problèmes NP Complets

le Dim 7 Fév - 19:01
Réputation du message : 100% (1 vote)
Bonjour à tous et à toutes !

Voilà j'ai un exercice à faire concernant la Machine de Turing et les problèmes NP.

J'ai quelques idées de réponses mais j'aimerais que vous m'aiguillez .

Machine de Turing :

1) On utilise la machine de Turing unaire ( l'alphabet est limité au bâton). Montrez que la fonction f : IN --> IN définie par f(n) = 2n est Turing calculable.

Alors pour celle - là je pense qu'il faille créer la liste d'instructions nécessaire et dire que par conséquent il existe un nombre (nombre de Godel) indexant cette liste d'instruction.

2) Même question avec l'alphabet binaire E = {0,1}

Alors là ... Je sais que l'alphabet n'importe peux. Faut - il dire qu'il existe une bijection entre ces deux alphabets ? Faut - il en faire la preuve ?

3) Calculez les fonctions de complexité dans les deux cas.

La complexité revient - elle à compter le nombre d'instruction pour f(n) = 2n en fonction de l'alphabet ? (qui doit contenir moins d'instruction, j'imagine , pour la seconde )


Problèmes NP.

1) Montrez que
Problème du cycle Hamiltonien
Problème du voyageur de commerce
sont deux problèmes de la classe NP

-> u___u comment démontrer ça ?
Solutions infinies non dénombrable ?


2) Montrez que le problème du cycle hamiltonien est un cas particulier du problème
du voyageur de commerce.

Bas le voyageur du commerce à la contrainte supplémentaire de trouver le cout minimum.
M'enfin bon je pense pas que ce soit une réponse valable.

3) Décrivez comment une machine de Turing pourrait transformer l'encodage d'une instance CH en encodage d'une instance VC ? Quelle en serait la complexité ?

-> Pas d'idée

4) Déduisez que si VC € P alors CH € P

-> Pas d'idée non plus


Je vous remercie encore d'y avoir passé du temps
Voir le sujet précédentRevenir en hautVoir le sujet suivant
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum