• Ei tuloksia

581336 Laskennan teoria (syksy 2003) Harjoitus 5 (18.21.11.2003)

N/A
N/A
Info
Lataa
Protected

Academic year: 2022

Jaa "581336 Laskennan teoria (syksy 2003) Harjoitus 5 (18.21.11.2003)"

Copied!
1
0
0

Ladataan.... (näytä koko teksti nyt)

Lataa nyt ( 1 sivua )

Kokoteksti

(1)

581336 Laskennan teoria (syksy 2003) Harjoitus 5 (18.21.11.2003)

1. Todista rekursiivisten palautusten transitiivisuusominaisuus Jos A≤mB jaB≤mC niinA≤mC.

2. Todista luennoilla esitettyyn Postin vastaavuusongelman ratkeamattomuuteen liittyvä aputulos MPCP≤mPCP.

3. Tarkastellaan seuraavaa päätösongelmaa:

Annettu: Turingin koneetM1jaM2, luonnollinen luku n Kysymys: onko|L(M1)∩L(M2)| ≥n

Osoita, että ongelma on osittain ratkeava muttei ratkeava. Voit käyttää hyväksi edellisen har- joituskerran tuloksia.

4. Olisi ilmeisen hyödyllistä, jos ohjelmasta voitaisiin jo käännösvaiheessa todeta, johtaako se jollain syötteellä nollalla jakamiseen. Perustele, miksi tällaista tarkastusta ei voi tehdä niin, että se aina varmasti toimisi.

5. Tarkastellaan ongelmaa, siirtääkö annettu Turingin kone annetulla syötteellä koskaan nauha- päätään vasemmalle. Muotoile ongelma formaalina kielenä. Osoita, että se on ratkeava.

6. Anna esimerkki ei-rekursiivisesta kielestäB, jolleB ≤mB. (Vihje: Harjoitus 3, tehtävä 5)

Viittaukset

Lataa nyt ( PDF - 1 sivua - 48.10 KB )

LIITTYVÄT TIEDOSTOT

581336 Laskennan teoria (kevät 2006) Harjoitus 7, ratkaisuja

Koska algoritmi voi tuottaa minkä tahansa osajoukon A, se löytää myös tällaisen osajoukon, jos sellainen on olemassa.. Toisaalta algoritmi ei hyväksy syötettä, ellei se löydä

581336 Laskennan teoria (kevät 2006) Harjoitus 8, ratkaisuja

Sanomme, että palautusfunktion syötteitä ovat muotoa hG; ki olevat merkkijonot, ja tulos- teita muotoa hG 1 ; G 2 i olevat merkkijonot... Polynomisen laskenta-ajan takaa se,

581336 Laskennan teoria (kevät 2006) Harjoitus 9, ratkaisuja

Kysymyksessä on pa- lautus solmupeiteongelmasta joukkopeiteongelmaan, sillä solmujoukko U on solmupeite jos ja vain jos joukkoon U kuuluu vähintään toinen pää jokaisesta

581336 Laskennan teoria (kevät 2006) Harjoitus 10 (11.12.4. ja 21.4.)

Yleisluontoinen vihje: Koska NP on luokka päätösongelmia ja funktion f laskeminen on etsintä- ongelma, sinun pitää palauttaa f jonoksi päätösongelmia samaan tapaan kuin

581336 Laskennan teoria (kevät 2006) Harjoitus 10, ratkaisuja

Lisäksi koska kolmikoiden väliset kaaret yhdistävät ainoastaan lähtösolmuja tulosolmuihin, täytyy syklissä peräkkäiset kolmikot ja siten kaikki kolmikot käydä läpi

581336 Laskennan teoria (kevät 2006) Harjoitus 11 (25.28.4.)

Kurssia Laskennan teoria ei nykymuodossaan enää tämän jälkeen luennoida, mutta nyt saatava palaute on hyödyllistä opetusohjelmaan tulevien uusien teoriakurssien laati-

581336 Laskennan teoria (kevät 2006) Harjoitus 11, ratkaisuja

kaikki tarvittavat kaaret ovat olemassa) ja laskemalla kutakin laillista läpikäyntijärjestystä vastaavien kaarten kokonaispaino. Ongelma on siis ratkeava, ja näin ollen myös

581336-0 Laskennan teoria

Usein ajatellaan, ett¨ a polynomisessa ajassa ratkeavat ongelmat ovat. ”k¨ ayt¨ ann¨ oss¨