Jäsen : Käyttäjätunnus |Rekisteröinti |Tallennettu tieto
Etsi
Etsi ongelma [Muutos ]
Laskennallisen monimutkaisuuden teorian ja laskennan teorian mukaan etsintäongelma on tietojenkäsittelyn ongelma, jota edustaa binaarinen suhde. Jos R on binääriyhteys, niin että kenttä (R) ⊆ Γ ja T on Turingin kone, niin T laskee R: n, jos:

Jos x on sellainen, että on jonkinlainen y siten, että R (x, y), niin T hyväksyy x: n antamalla z: n siten, että R (x, z) (voi olla useita y ja T tarvitsee vain löytää yhden niistä)
Jos x on sellainen, että y: ssä ei ole sellaista, että R (x, y), niin T hylkää x: n

Intuitiivisesti ongelmana on rakenteen "y" löytäminen kohteesta "x". Sanotaan, että algoritmi ratkaisee ongelman, jos ainakin yksi vastaava rakenne on olemassa ja sitten syntyy yksi tämän rakenteen esiintyminen; muussa tapauksessa algoritmi pysähtyy sopivalla lähdöllä ("kohta ei löydy" tai vastaavaa viestiä).
Tällaiset ongelmat esiintyvät usein usein kaavion teorian yhteydessä, esimerkiksi silloin, kun etsitään kaavioita rakenteille, kuten täsmälliselle sovitukselle, napsautuksille, itsenäiselle joukolle jne., Kiinnostavia aiheita.
Huomaa, että osatoiminnon kaavio on binaarinen suhde, ja jos T laskee osittaisen toiminnon, on olemassa enintään yksi mahdollinen ulostulo.
Suhdetta R voidaan tarkastella etsintäongelmana, ja myös Turingin kone, joka laskee R: n, on myös sanottu ratkaisevan sen. Jokaisella hakupohjalla on vastaava päätösongelma, nimittäin


  
    
      
    
    L (R) = \ {x \ keski \ on yR (x, y) \}. \,}
  


Tämä määritelmä voidaan yleistää n-ary-suhteiksi käyttäen mitä tahansa sopivaa koodausta, joka sallii useita merkkijonoja pakattaviksi yhteen merkkijonoon (esimerkiksi listoimalla ne peräkkäisesti raja-arvolla).
1.Määritelmä
2.Tavoite
3.Hakutapa
[Lähetä Lisää Sisältö ]


Tekijänoikeus @2018 Lxjkh