Naloge

Sklop 1: Turingovi stroji

  1. Tvorite, sprogramirajte v JFLAP in ocenite koliko korakov naredi Turingov stroj (TS) za jezik:

    • 0n1n0n

    • wxwR - palindrom kjer x ne nastopa v w

    • wwR - palindrom

    • a=b+c - jezik izrazov, kjer so a, b in c zapisani binarno ter mora veljati, da je vrednost a vsota b in c

Sklop 2: Računalnik in Turingovi stroji

  1. Osnovni TS, kot smo ga definirali, ima neskončen trak v obe smeri. Obstajajo pa tudi druge inačice TS, za katere pa se izkaže, da niso nič boljše. Za naslednje inačice TS opišite, kako simulirajo osnovni TS (namig: definirajte predvsem prhodno funkcijo):

    • TS, ki ima na traku dve ločeni sledi, v kateri vpisuje ločena in lahko različna znaka
    • TS, ki ima dve glavi in ne samo
    • TS, ki ima več trakov
    • TS, ki ima trak, ki je neskončen samo v eno stran
  2. Definirajte model računanja, ki bo popisal delovanje ALE (aritmetično logične enote) v procesorju.

Sklop 3: Nedeterminizem

  1. Za naslednje probleme zapišite dokazila:
    • problem potujočega trgovca (travelling salesmen problem): na zemljevidu imamo n mest, med katerimi so običajne evklidske razdalje. Ali obstaja rešitev, kjer bo trgovski potnik obiskal vse kraje a tako, da pri tem naredil največ k kilometrov.
    • problem (vozliščno) pokritja: v Butalah so odprli galerijo, ki sestoji v glavnem iz dolgih hodnikov, kamor so obesili slike. Hodniki se stikajo v sobah, kjer je lahko paznik, ki ima pregled na vse hodnike, ki vodijo do sobe. Butalski župan Štimani je zapovedal, da naj zaposlijo največ k ljudi, ki bodo pazili dragocene slike, a še vedno dovolj, da bo lahko vsak hodnik nadzoroval vsaj eden paznik.
    • problem klike: v socialnem omrežju se ljudje med seboj lahko poznajo ali pa ne - poznavanje je vzajemno. Kliko predstavlja skupina ljudi, kjer se vsi vzajemno poznajo. Recimo, da imamo n uporabnikov socialnega omrežja in nas zanima, ali je med njimi vsaj k takšnih, ki se vzajemno poznajo.

Sklop 4: Problemi s praktičnimi rešitvami

  1. Obstajata dve legendi o riževih zrnih in šahovnici (ena je tule http://britton.disted.camosun.bc.ca/jbchessgrain.htm). V obeh primerih pa zlagamo riževa zrna na šahovnico in sicer eno zrno na 1. polje, 2 na 3., 4 na tretje in tako vedno po še enkrat več na prejšnje polje. Koliko zrn je na zadnjem polju? Koliko zrn je skupaj na šahovnici?
  2. Poiščite podatek o velikosti in teži zrna ter izračunajte kako velika mora biti šahovnica - utemeljite rešitev ter koliko tehtajo vsa zrna riža.
  3. Poiščite 3 NP-polne probleme ter opišite, kje in kako nastopajo v vsakodnevnem življenju (primeri iz vprašanj v Sklopu 3 ne veljajo).
  4. Recimo, da imamo opis NTS S ter vhodno besedo w. Napišite/opišite postopek, ki bo z uporabo opisa preverl, če je beseda v jeziku TS S. (Namig: uporabite pojem stanja in vračanja.)

Sklop dodatek: (Ne)moč Turingovih strojev

  1. Poiščite še kakšne neizračunljive probleme ter jih opišite. Opišite, kje jih lahko srečamo v vsakodnevnem življenju.
  2. Kaj imajo skupnega Bertrand Russel, Kurt Gödel in Alan Turing?
  3. Kaj točno je počel David Hilbert in kako je povezan z zgornjimi tremi. Opišite povezanost.
Zadnja sprememba: Thursday, 8 May 2014, 20:36