24. Úvodná prednáška v letnom semestri

24.1. Priebeh semestra

Pravidlá predmetu v letnom semestri sú skoro indentické so zimným semestrom. Rozdiely sú len tieto:

skúška

sa skladá z dvoch častí:

  1. jeden písomný test (v pondelok 22.5. o 14:00 v posluchárni A) - max. 40 bodov
  2. praktická skúška pri počítači (v skúškovom období) - max. 60 bodov

hodnotenie skúšky

spočítajú sa body z písomného testu, praktickej skúšky, príp. bodov za semestrálny projekt:

  • známka A 88 bodov
  • známka B 81 bodov
  • známka C 74 bodov
  • známka D 67 bodov
  • známka E 60 bodov
  • známka Fx menej ako 60 bodov

24.2. Turingov stroj

Alan Turing (1912-1954) sa považuje za zakladateľa modernej informatiky - rok 2012 sa na celom svete oslavoval ako Turingov rok.

Turingov stroj je veľmi zjednodušený model počítača, vďaka ktorému sa informatika dokáže zaoberať zložitosťou problémov - Turing ho publikoval v roku 1936 (keď mal 24 rokov).

Základná idea takéhoto stroja je nasledovná:

  • pracuje na nekonečnej páske - postupnosť políčok, na každom môže byť nejaký symbol (my si to zjednodušíme obyčajnými znakmi, t.j. jednoznakovými reťazcami) - táto páska je nekonečná oboma smermi
  • nad páskou sa pohybuje čítacia/zapisovacia hlava, ktorá vie prečítať symbol na páske a prepísať ho iným symbolom
  • samotný stroj (riadiaca jednotka) sa stále nachádza v jednom zo svojich stavov: na základe momentálneho stavu a prečítaného symbolu na páske sa riadiaca jednotka rozhoduje, čo bude robiť
  • na začiatku sa na políčkach pásky nachádzajú znaky nejakého vstupného reťazca (postupnosť symbolov), stroj sa nachádza v počiatočnom stave (stavy pomenujeme ľubovoľnými reťazcami znakov, napr. 's1' alebo 'end'), celý zvyšok nekonečnej pásky obsahuje prázdne symboly (my sa dohodneme, že to budeme označovať symbolom '_')
  • činnosť stroja (program) sa definuje špeciálnou dvojrozmernou tabuľkou, tzv. pravidlami
  • každé pravidlo je takáto pätica: (stav1, znak1, znak2, smer, stav2) a popisuje:
    • keď je stroj v stave stav1 a na páske (pod čítacou hlavou) je práve symbol znak1, tak ho stroj prepíše týmto novým symbolom znak2, posunie sa na páske podľa zadaného smeru smer o (-1, 0, 1) políčko a zmení svoj stav na stav2
    • napr. pravidlo (s0, a, b, >, s1) označuje: v stave 's0' so symbolom 'a' na páske ho zmení na 'b', posunie sa o jedno políčko vpravo a zmení svoj stav na 's1'
    • pre lepšiu čitateľnosť budeme smery na posúvanie hlavy označovať pomocou znakov '<' (vľavo), '>' (vpravo), '=' (bez posunu)
    • takéto pätice sa niekedy označujú aj v tomto tvare: (stav1, znak1) -> (znak2, smer, stav2), t.j. pre danú dvojicu stav a znak, sa zmení znak
  • program má väčšinou viac stavov, z ktorých niektoré sú špeciálne, tzv. koncové a majú takýto význam:
    • keď riadiaca jednotka prejde do koncového stavu, výpočet stroja sa zastaví a stroj oznámi, že akceptoval vstupné slovo, vtedy sa môžeme pozrieť na obsah pásky a táto informácia môže byť výsledkom výpočtu
  • stroj sa zastaví aj v prípade, že neexistuje pravidlo, pomocou ktorého by sa dalo pokračovať (stroj skončil v nekoncovom stave), vtedy
    • hovoríme, že stroj oznámil, že zamietol (neakceptoval) vstupné slovo
  • zrejme sa takýto stroj môže niekedy aj zacykliť a neskončí nikdy (pre informatikov je aj toto veľmi dôležitá informácia)

Na internete sa dá nájsť veľa rôznych zábavných stránok, ktoré sa venujú Turingovmu stroju, napr.

Zostavme náš prvý program pre Turingov stroj:

(0, a) -> (A, >, 0)
(0, _) -> (_, =, end)

Vidíme, že pre počiatočný stav sú tu dve pravidlá: buď je na páske symbol ‚a‘ alebo symbol ‚_‘, ktorý označuje prázdne políčko. Ak teda čítacia hlava má pod sebou na páske symbol ‚a‘, tak ho prepíše na symbol ‚A‘ a posunie hlavu na políčko vpravo. Riadiaca jednotka pritom stále ostáva v stave 0. Vďaka tomuto pravidlu sa postupne všetky písmená ‚a‘ nahradia ‚A‘. Ak sa pritom narazí na iný symbol, prvé pravidlo sa už nebude dať použiť a stroj sa pozrie, či nemá pre tento prípad iné pravidlo. Ak je na páske už len prázdny symbol, stroj sa zastaví a oznámi radostnú správu, že vstupné slovo akceptoval a vyrobil z neho nový reťazec. Ak ale bude na páske za postupnosťou ‚a‘ aj nejaké iné písmeno, stroj nenájde pravidlo, ktoré by mohol použiť a preto sa zastaví. Oznámi pritom správu, že takéto vstupné slovo zamietol.

Priebeh výpočtu pre vstupné slovo ‚aaa‘ by sme si mohli znázorniť napr. takto:

aaa
^ 0
Aaa
 ^ 0
AAa
  ^ 0
AAA_
   ^ 0
AAA_
   ^ end
True

True zmamená, že stroj sa úspešne zastavil v koncovom stave, teda stroj akceptoval vstupné slovo

Všimnite si, že v našej vizualizácii sa na páske automaticky objavujú prázdne symboly, keďže páska je nekonečná a okrem vstupného slova obsahuje práve tieto znaky.

Ak by sme zadali napr. slovo ‚aba‘, tak by výpočet prebiehal takto:

aba
^ 0
Aba
 ^ 0
False

False tu znamená, že stroj sa zastavil v inom ako koncovom stave, teda zamietol vstup

24.3. Cvičenie

  1. Pomocou programu Turing z prednášky otestujte tieto pravidlá

    (stav, x) -> (y, >, stav)
    (stav, _) -> (z, =, end)
prog = '''


'''
t = Turing(prog, ...)
print(t.rob())

Zvoľte takú vstupnú pásku, aby Turingov stroj akceptoval vstup (metóda rob() vráti True). Otostujte s rôzne veľkými páskami.

  1. Zistite, aké reťazce bude akceptovať nasledovný Turingov stroj:
start q q > jedna
jedna q q > dva
dva q q > start
jedna _ _ = stop

Nájdite aspoň 3 rôzne dlhé reťazce aspoň dĺžky 8, ktoré budú akceptované.

  1. Otestujte Turingov stroj z prednášky, ktorý pripočítaval 1 k dvojkovému zápisu pre nejaké väčšie číslo, napr. takto:
cislo = 1000000
retazec = ... #preveď cislo do dvojkovej sústavy (napr. funkciou bin())
t = Turing(...) #zavolaj Turingov stroj s daným reťazcom
t.rob()
vysledok = t.paska.text()
# skontroluj, či je výsledok o 1 viac ako pôvodné číslo
  • Otestujte ešte pre väčšie číslo, napr. 2**100-1. Metódu rob() nastavte tak, aby nerobila priebežný výpis.
  • Zistite, koľko pravidiel sa pritom vykonalo (metóda krok() bola úspešná) - zmodifikujte metódu rob() tak, aby zvyšovala počítadlo self.pocet
  1. Zistite, čo robí nasledovný Turingov stroj:
q00 a a > q10
q00 b b > q01
q10 a a > q00
q10 b b > q11
q01 a a > q11
q01 b b > q00
q01 _ _ = end
q11 a a > q01
q11 b b > q10

Nájdite reťazce dĺžky 5, 6, 7, 8, ktoré budú akceptované týmto Turingovým strojom

  1. Navrhnite Turingov stroj, ktorý zo vstupného reťazca 'matfyz' vytvorí na páske slovo 'python'. Pravidlá by mali mať jediný stav (okrem koncového). Otestujte napr.
>>> t = Turing(prog, 'matfyz')
>>> t.rob(False)
True
>>> t.paska.text()
'python'
  1. Upravte pravidlá Turingovho stroja z 3. úlohy tak, aby na páske vzniklo dvojkové číslo o 1 menšie. Napr.
>>> t = Turing(prog, '1000')
>>> t.rob(False)
True
>>> t.paska.text()
'111'
  1. Navrhinte Turingov stroj, ktorý predpokladá, že na páske je postupnosť znakov '1'. Po skončení práce stroja (metóda rob() vráti True) bude na páske celá táto postupnosť jednotiek skopírovaná za seba, napr.
>>> t = Turing(prog, '1111')
>>> t.rob(False)
True
>>> t.paska.text()
'1111_1111'
  1. Zapíšte pravidlá pre takýto Turingov stroj:
  • predpokladá, že na páske je len postupnosť '1', napr. '11111'
  • pred túto postupnosť (o jedno políčko vľavo) vloží znak '0', napr. '0 11111' - na páske budeme vytvárať dvojkové číslo ('0' pred prázdnym políčkom) z postupnosti '1' za prázdnym políčkom
  • teraz bude opakovať túto činnosť:
    • kým je postupnosť jednotiek neprázdna, tak
    • z nej odoberie poslednú jednotku
    • k dvojkovému číslu pripočíta 1 (algoritmom z 3. úlohy)

Na páske sa postupne budú objavovať tieto reťazce:

0 11111
1 1111
10 111
11 11
100 1
101

Na koniec vznikne dvojková reprezentácia čísla, ktoré bolo zapísané pomocou 1. Otestujte napr.

>>> t = Turing(prog, '1'*13)
>>> t.rob(False)
True
>>> t.paska.text()
'1101'

24.4. Domáce zadanie

Zapíšte metódy triedy Turing s týmito metódami:

class Turing:
    def __init__(self, program, obsah=''):
        self.prog = {}
        ...

    def restart(self, stav=None, obsah=None, n=None):
        # od noveho stavu (ak nie je None), s novou paskou (ak nie je None) a zavola rob()
        return False, 0

    def rob(self, n=None):
        return False, 0

    def text(self):
        return ''

Tento Turingov stroj by sa mal správať veľmi podobne, ako ten z prednášky, líšiť sa bude len v niekoľkých detailoch:

  • inicializácia __init__() má dva parametre program a počiatočný stav pásky, pričom program sa zadáva inak ako bolo v prednáške (uvádzame nižšie)
  • metódy restart() a rob() majú posledný parameter n, ktorý, ak je zadaný, určuje maximálny počet vykonávaných pravidiel, ak by sa mal tento počet presiahnuť, výpočet končí tak, akokeby neakceptoval vstup (Turingov stroj vtedy vykoná maximálne len n pravidiel, ale n+1-pravidlo už nie)
  • obe tieto metódy vrátia dvojicu: True/False a počet vykonaných pravidiel
  • metóda restart() môže mať tieto ďalšie 2 parametre, ktorým môžeme nastaviť počiatočný stav, resp. zmeniť obsah pásky (pri zmene obsahu sa pozícia na páske nastaví na 0), táto metóda okrem nastavovania stavu a pásky zavolá metódu rob()
  • množina koncových stavov je {'end', 'stop'}
  • metóda text() vráti momentálny stav pásky, ktorý je očistený od úvodných a záverečných prázdnych znakov '_'
  • v triede Turing môžete dodifinovať ďalšie metódy aj atribúty

Formát zadávaného programu pre Turingov stroj

Doteraz sme definovali Turingov stroj ako zoznam pravidiel, pričom každé z nich bolo päticou:

stav1 znak1 znak2 smer stav2

Napr.

s1 0 0 > s1
s1 1 1 > s1
s1 _ _ < s2

s2 1 0 < s2
s2 0 1 = end
s2 _ 1 = end

Tento istý Turingov stroj môžeme definovať aj takouto tabuľkou:

s1 s2
0 0 > s1 1=end
1 1 > s1 0 < s2
_ _ < s2 1=end

V tejto tabuľke sú v prvom riadku vymenované všetky stavy (okrem koncových), v prvom stĺpci sú všetky sledované symboly, pre ktoré existuje pravidlo. Každé vnútorné políčko tabuľky reprezentuje jedno pravidlo: stav1 z príslušného stĺpca a znak1 z príslušného riadka, samotné políčko obsahuje trojicu znak2 smer stav2. Ak pre nejakú dvojicu stav1, znak1 neexistuje pravidlo, tak na príslušnom mieste tabuľky je namiesto trojice reťazcov jeden znak '.'.

Niekedy sa takáto tabuľka môže trochu sprehľadniť tým, že sa môžu vynechať časti znak2, resp. stav2, ak sa zhodujú so znak1, resp. stav1. Predchádzajúca tabuľka by mohla vyzerať aj takto a popisovala by ten istý Turingov stroj:

s1 s2
0 > 1=end
1 > 0<
_ <s2 1=end

Všimnite si, že sme tu vynechali medzery v trojiciach vo vnútri tabuľky. Takúto tabuľku budeme do triedy Turing zadávať pri inicializácii, napr. takto:

prog = '''
    s1    s2
0    >    1=end
1    >    0<
_   <s2   1=end
'''
t = Turing(prog, '1011')

Uvedomte si, že ak má Turingov stroj n stavov (okrem koncových), tak prvý riadok súboru obsahuje n reťazcov - názvov stavov (prvý z nich bude štartový), ktoré sú navzájom oddelené aspoň jednou medzerou. Každý ďalší riadok (podľa počtu rôznych rozlišových znakov) obsahuje presne n+1 reťazcov navzájom oddelených aspoň jednou medzerou.

Ďalší príklad ukazuje tabuľku aj s políčkami bez pravidiel:

s1 s2 s3 s4 s5
a >s2 . . . .
h . >s3 . . .
o . . >s4 . .
j . . . >s5 .
_ . . . . =end

Obmedzenia

  • vaše riešenie odovzdavajte v súbore uloha1.py, pričom sa v ňom bude nachádzať len jedna definícia triedy Turing

  • atribút prog v triede Turing bude obsahovať asociatívne pole s pravidlami Turingovho stroja (vo formáte z prednášky)

  • prvé dva riadky tohto súboru budú obsahovať:

    # autor: Janko Hrasko
    # uloha: 1. domace zadanie Turing
    
  • zrejme ako autora uvediete svoje meno

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne testovacie print())

Testovanie

Keď budete spúšťať vaše riešenie na svojom počítači, môžete do súboru uloha1.py pridať testovacie riadky, ktoré ale testovač nebude vidieť, napr.:

if __name__ == '__main__':
    prog = '''
        s1    s2
    0    >    1=end
    1    >    0<
    _   <s2   1=end
    '''
    t = Turing(prog, '1011')
    print(t.prog)
    print(t.rob())
    print('vysledok =', t.text())
    print(t.restart('s1', '10102010'))

Tento test by vám mal vypísať:

{('s2', '_'): ('1', '=', 'end'), ('s1', '_'): ('_', '<', 's2'), ('s2', '1'): ('0', '<', 's2'),
('s1', '0'): ('0', '>', 's1'), ('s1', '1'): ('1', '>', 's1'), ('s2', '0'): ('1', '=', 'end')}
(True, 8)
vysledok = 1100
(False, 4)