581336 Laskennan teoria (kevät 2006) Harjoitus 11 (25.28.4.)
Tehtävät 14 perustuvat vanhoihin tentteihin, joiden malliratkaisut löytyvät verkosta. Jos haluat, voit käyttää näitä malliratkaisuja apuna, mutta yritä kuitenkin ratkaista tehtävä ensin itse. Joka tapauk- sessa tehtävän merkitseminen tehdyksi edellyttää, että olet valmis selittämään ratkaisuehdotuksesi.
1. Mitä voit sanoa seuraavien ongelmien ratkeavuudesta ja laskennallisesta vaativuudesta? Perus- tele.
(a) Annettu: suuntaamaton verkko G = (V; E), jokaiselle kaarelle e 2 E paino w(e) Kysymys: mikä on kaarten kokonaispainoltaan pienin polku, joka käy verkon jo-
kaisessa solmussa tasan kerran ja palaa lähtöpisteeseensä (b) Annettu: jono (a1; : : : ; an) luonnollisia lukuja
Kysymys: onko olemassa osajoukko I f 1; : : : ; n g, jolleP
i2Iai= 3 (c) Annettu: Turingin kone M
Kysymys: voiko kielen L(M) tunnistaa äärellisellä automaatilla
2. Muotoile seuraavat kolme laskennallista ongelmaa formaaleina kielinä. Ilmoita kustakin ongel- masta, onko se ratkeava ja onko se osittain ratkeava. Perustele väitteesi. Voit kaikissa tapauksissa olettaa, että koneen M syöteaakkosto on = f a; b; c; d g ja merkkijonot tarkoittavat merkkijo- noja tässä aakkostossa.
(a) Annettu: Turingin kone M
Kysymys: hyväksyykö M kaikki korkeintaan 5 merkin mittaiset merkkijonot (b) Annettu: Turingin kone M
Kysymys: hyväksyykö M ainakin yhden yli 5 merkin mittaisen merkkijonon (c) Annettu: Turingin kone M
Kysymys: ovatko kaikki koneen M hyväksymät merkkijonot korkeintaan 5 mer- kin mittaisia
3. (a) Päteekö A pmA kaikilla A, ts. voidaanko mikä tahansa ongelma palauttaa polynomisesti itseensä? Perustele täsmällisesti käyttäen polynomisen palautuksen määritelmää.
(b) Seuraavassa on määritelty kolme laskennallista ongelmaa: toteutuvuusongelma SAT, Ha- miltonin kehä -ongelma HC ja polkuongelma PATH.
Toteutuvuusongelma SAT
Annettu: propositiologiikan kaava Kysymys: onko kaava toteutuva Hamiltonin kehä -ongelma HC
Annettu: suuntaamaton verkko G
Kysymys: onko verkossa G polku, joka käy tasan kerran jokaisessa sol- mussa ja palaa lähtöpisteeseensä
Polkuongelma PATH
Annettu: suuntaamaton verkko G = (V; E), kaksi solmua u 2 V , v 2 V Kysymys: onko verkossa G polku solmusta u solmuun v
Mitä tiedetään näiden ongelmien välisistä polynomisista palautuvuuksista, siis voi- daanko toteutuvuusongelma palauttaa polkuongelmaan, polkuongelma Hamiltonin kehä -ongelmaan jne.? Esitä lyhyet perustelut.
Käännä!
4. Tarkastellaan seuraavaa osumajoukko-ongelmaa (Hitting Set):
Annettu: perusjoukko X = f x1; : : : ; xng, luonnollinen luku k ja m osajoukkoa Ai X, i = 1; : : : ; m
Kysymys: onko olemassa sellainen joukko Y X, että jY j k ja Y \Ai 6= ; kaikilla i = 1; : : : ; m
Osoita, että osumajoukko-ongelma on NP-täydellinen. Voit pitää tunnettuna, että seuraava sol- mupeiteongelma (Vertex Cover) on NP-täydellinen:
Annettu: suuntaamaton verkko G = (V; E) ja luonnollinen luku k
Kysymys: onko olemassa sellainen solmujoukko U V , että jUj k ja jokaisella kaarella (u; v) 2 E ainakin toinen kaaren päätepiste kuuluu joukkoon U, ts. u 2 U tai v 2 U
5. Anna kurssista palautetta täyttämällä lomake osoitteessa
https://ilmo.cs.helsinki.fi/kurssit/servlet/Valinta
(linkki myös kurssin kotisivulla ja laitoksen etusivulla). Voit halutessasi vastata vasta kokeen jälkeen, mutta älä unohda vastata! Kaikki palaute on tervetullutta opettajille ja käydään huo- lellisesti lävitse. Kurssia Laskennan teoria ei nykymuodossaan enää tämän jälkeen luennoida, mutta nyt saatava palaute on hyödyllistä opetusohjelmaan tulevien uusien teoriakurssien laati- misessa.
2
