CONNEXION
  • RetourJeux
    • Tests
    • Soluces
    • Previews
    • Sorties
    • Hit Parade
    • Les + attendus
    • Tous les Jeux
  • RetourActu
    • Culture Geek
    • Astuces
    • Réalité Virtuelle
    • Rétrogaming
    • Toutes les actus
  • RetourHigh-Tech
    • Actus JVTECH
    • Bons plans
    • Tutoriels
    • Tests produits High-Tech
    • Guides d'achat High-Tech
    • JVTECH
  • RetourVidéos
    • A la une
    • Gaming Live
    • Vidéos Tests
    • Vidéos Previews
    • Gameplay
    • Trailers
    • Chroniques
    • Replay Web TV
    • Toutes les vidéos
  • RetourForums
    • Hardware PC
    • PS5
    • Switch
    • Xbox Series
    • Overwatch 2
    • FUT 23
    • League of Legends
    • Genshin Impact
    • Tous les Forums
  • PC
  • PS5
  • Xbox Series
  • PS4
  • One
  • Switch
  • Wii U
  • iOS
  • Android
  • MMO
  • RPG
  • FPS
En ce moment Genshin Impact Valhalla Breath of the wild Animal Crossing GTA 5 Red dead 2
Etoile Abonnement RSS

Sujet : informatique, P NP oracle

DébutPage précedente
1
Page suivantePage suivante
Soldier76Homo Soldier76Homo
MP
Niveau 10
13 avril 2019 à 21:58:27

https://www.noelshack.com/2019-15-6-1555185416-20190413-213125.jpg

bonjour alors voila je sais pas quoi repondre aux deux dernieres questions, ni l'inclusion 1, 2 et 4...

pouvez vous m'aider svp :-( ?

Niverolle Niverolle
MP
Niveau 10
13 avril 2019 à 23:56:14

Pour les inclusions :
1. NP inclus dans NPSPACE puisque chaque étape de calcul écrit au plus une case mémoire, ça marche avec ou sans oracles on s'en fiche
2. QSAT est dans PSPACE, tu peux remplacer chaque appel à l'oracle par le vrai algo QSAT, et au total t'es encore dans NPSPACE.
4. Utilise le fait que QSAT est PSPACE-complet

Pour la (4), t'as juste à suivre l'indication. Regarde ce que fait M_i0 sur l'entrée 1^i0, et compare à la définition de B_i0.
- Si M_i0 accepte 1^i0 alors [...] (contradiction)
- et si M_i0 rejette 1^i0 alors [...] (contradiction aussi)

Pour la (5) je vois pas

Soldier76Homo Soldier76Homo
MP
Niveau 10
15 avril 2019 à 15:09:08

merci mon bro

Fuligule Fuligule
MP
Niveau 10
15 avril 2019 à 16:23:53

En fait pour la question (5) il faut juste remarquer qu'à la question 3 on avait en fait card(U Xj) < 2^(i-1). Du coup, soit Bi est vide, soit Bi contient au moins la moitié des mots de {0,1}^i.
Du coup à chaque fois que tu testes un mot de {0,1}^i au hasard, si Bi est non-vide, t'as une proba >1/2 de tomber sur un mot de Bi. Tu répètes ça 10 fois et t'auras une proba <1/1000 de te planter.

Soldier76Homo Soldier76Homo
MP
Niveau 10
15 avril 2019 à 22:46:10

Le 13 avril 2019 à 23:56:14 Niverolle a écrit :
Pour les inclusions :
1. NP inclus dans NPSPACE puisque chaque étape de calcul écrit au plus une case mémoire, ça marche avec ou sans oracles on s'en fiche
2. QSAT est dans PSPACE, tu peux remplacer chaque appel à l'oracle par le vrai algo QSAT, et au total t'es encore dans NPSPACE.
4. Utilise le fait que QSAT est PSPACE-complet

Pour la (4), t'as juste à suivre l'indication. Regarde ce que fait M_i0 sur l'entrée 1^i0, et compare à la définition de B_i0.
- Si M_i0 accepte 1^i0 alors [...] (contradiction)
- et si M_i0 rejette 1^i0 alors [...] (contradiction aussi)

Pour la (5) je vois pas

du coup j'ai :

Si M_io accepte 1^i0 alors il existe un m tel que 1^|m| appartient à B_io(barre) et m appartient à B_io or B_io est vide donc contradiction

et elle est en complexité < 2^n/4 car si M_io accepte alors elle accepte avant le timeout

Soldier76Homo Soldier76Homo
MP
Niveau 10
15 avril 2019 à 22:49:11

Le 15 avril 2019 à 16:23:53 Fuligule a écrit :
En fait pour la question (5) il faut juste remarquer qu'à la question 3 on avait en fait card(U Xj) < 2^(i-1). Du coup, soit Bi est vide, soit Bi contient au moins la moitié des mots de {0,1}^i.
Du coup à chaque fois que tu testes un mot de {0,1}^i au hasard, si Bi est non-vide, t'as une proba >1/2 de tomber sur un mot de Bi. Tu répètes ça 10 fois et t'auras une proba <1/1000 de te planter.

je vois pas d ou tu tiens 2^(i-1)

Fuligule Fuligule
MP
Niveau 10
15 avril 2019 à 23:09:11

et elle est en complexité < 2^n/4 car si M_io accepte alors elle accepte avant le timeout

c'est le contraire, dans la question 4 tu supposes que M_i0 accepte en complexité 2^m/4, c'est ça qui te permet de dire que soit elle accepte, soit elle rejette (elle ne peut pas timeout)

je vois pas d ou tu tiens 2^(i-1)

Somme de 0 à i de 2^j/4 = 2^(i+1)/4 = 2^(i-1)

Soldier76Homo Soldier76Homo
MP
Niveau 10
15 avril 2019 à 23:33:29

c'est le contraire, dans la question 4 tu supposes que M_i0 accepte en complexité 2^m/4, c'est ça qui te permet de dire que soit elle accepte, soit elle rejette (elle ne peut pas timeout)

oui dans l autre sens, le reste est correct?

Somme de 0 à i de 2^j/4 = 2^(i+1)/4 = 2^(i-1)

bien vu ca venait de la 1ere affirmation. je pensais que t'as fait un typo sur la 2e.

Fuligule Fuligule
MP
Niveau 10
15 avril 2019 à 23:36:55

Oui c'est OK pour la contradiction. Il faut faire pareil pour M_i0 rejette 1^i0

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 13:40:01

jy suis pas arrivé mais ya vraiment besoin? si on fait pour 1 cas ca suffit pour dire qu'elle ne calcule pas la bonne chose

Fuligule Fuligule
MP
Niveau 10
16 avril 2019 à 14:14:08

Ben non ça suffit pas, pour l'instant tu as juste montré qu'elle ne pouvait pas accepter le mot 1^i0 mais rien ne te dit que ce mot devrait être accepté.

Il te reste soit a prouver 1^i0 doit être accepté (càd, que B_i0 est non vide), soit à supposer que la machine refuse 1^i0 et aboutir à une contradiction. Dans les deux cas l'argument sera le même (en particulier il faut utiliser la question 3)

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 14:18:04

ok je vais essayer ce soir

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 14:22:08

juste par curiosité tu as déja vu ce sujet :hap: ?

Fuligule Fuligule
MP
Niveau 10
16 avril 2019 à 14:35:13

Non mais c'est un argument diagonal classique

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 15:31:33

ok

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 22:35:25

donc dans l autre sens :

Si M io ne reconnait pas 1 io, ca veut dire qu'il nexiste pas de mot m de longueur io tel que m appartient à Bio or Bio n'est pas vide

et la on a deux contradiction et cest bon?

Fuligule Fuligule
MP
Niveau 10
16 avril 2019 à 22:43:18

Oui

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 22:50:36

super merci fuligule

Soldier76Homo Soldier76Homo
MP
Niveau 10
16 avril 2019 à 23:08:51

si ca tinteresse je peux scanner le reste de l'examen, cest des reductions depuis sat vers des problemes

DébutPage précedente
1
Page suivantePage suivante
Répondre
Prévisu
?
Victime de harcèlement en ligne : comment réagir ?
Infos 0 connecté(s)

Gestion du forum

Modérateurs : HypoBowling
Contacter les modérateurs - Règles du forum

Sujets à ne pas manquer

La vidéo du moment