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

Priebeh letného semestra

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

skúška

sa skladá z dvoch častí:

  1. jeden písomný test (v pondelok 13.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



Turingov stroj

Alan Turing

Alan Turing (tiež) (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 s nekonečnou páskou - 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 na konci výpisu znamená, ž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.

Cvičenia

L.I.S.T.

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

    (stav, x)  ->  (y, >, stav)
    (stav, _)  ->  (z, =, end)
    
    prog = '''
    
    
    '''
    t = Turing(prog, ...)
    print(t.rob())
    

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


  1. Zisti, aké reťazce bude akceptovať nasledovný Turingov stroj:

    start q q > jedna
    jedna q q > dva
    dva q q > start
    jedna _ _ = stop
    

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


  1. Napíš pravidlá (program) pre Turingov stroj, ktorý bude akceptovať len takú postupnosť symbolov na páske, ktorá obsahuje len písmená {a, b, c}. Otestuj s rôznymi vstupnými reťazcami, napr.

    for retazec in 'abcb', 'ccccca', 'cba'*10, ...:
        t = Turing('''
        ...program...
        ''', retazec)
        print(retazec, t.rob(False))
    

  1. Na vstupnej páske je postupnosť znakov 'x'. Napíš program, ktorý akceptuje tento vstup len, ak obsahuje nepárny počet týchto znakov. Napr.

    >>> prog = '''
    ...program...
    '''
    >>> print(Turing(prog, 'xxxxx').rob(False))
    True
    >>> print(Turing(prog, 'xx' * 5).rob(False))
    False
    

  1. Program z úlohy (4) oprav tak, aby akceptoval len reťazce zložené z písmen {x, y}, v ktorých je nepárny počet znakov 'x' (na počte 'y' by nemalo záležať).

    >>> prog = '''
    ...program...
    '''
    >>> print(Turing(prog, 'xxxxx').rob(False))
    True
    >>> print(Turing(prog, 'yyy').rob(False))
    False
    >>> print(Turing(prog, 'yx' * 5).rob(False))
    True
    

  1. Na vstupnej páske je reťazec zložený len zo znakov 'e'. Napíš program, ktorý akceptuje len reťazce z písmen 'e', pričom na ich koniec pripíše jeden zo znakov {0, 1, 2} a to podľa zvyšku po delení 3 počtu 'e'. Napr.

    for pocet in 10, 9, 8, 7:
        t = Turing('''
        ...program...
        ''', 'e' * pocet)
        print(t.rob(False), t.paska.text())
    

    by mal vypísať:

    True eeeeeeeeee1
    True eeeeeeeee0
    True eeeeeeee2
    True eeeeeee1
    

  1. Otestuj Turingov stroj z prednášky, ktorý pripočítaval 1 k dvojkovému zápisu pre nejaké väčšie číslo, napr. takto:

    cislo = 555
    retazec = bin(cislo)[2:]
    t = Turing(...) #zavolaj Turingov stroj s daným reťazcom
    t.rob(False)
    vysledok = t.paska.text()
    print(cislo, retazec, vysledok, int(vysledok, 2))
    

    Uvedom si, že v premennej retazec je dvojkový zápis daného čísla cislo a v premennej vysledok by mal byť dvojkový zápis tohto čísla zväčšeného o 1.

    Skontroluj tento program aj pre iné čísla, napr. pre 2**20-1


  1. Ručne bez počítača preveď číslo 1000 do dvojkovej sústavy. Svoje riešenie skontroluj napr. pomocou:

    >>> int('...dvojkový zápis...', 2)
    

  1. Ručne zisti, aké číslo má dvojkový zápis 10101010. Ručne preveď toto číslo aj do 16-ovej sústavy. Môžeš to skontrolovať napr. takto:

    >>> int('10101010', 2)
    >>> int('šestnástkový zápis', 16)
    

  1. Navrhni Turingov stroj, ktorý zo vstupného reťazca 'matfyz' vytvorí na páske slovo 'python'. Pravidlá by mali mať jediný stav (okrem koncového). Otestuj napr.

    >>> t = Turing(prog, 'matfyz')
    >>> t.rob(False)
    True
    >>> t.paska.text()
    'python'
    

  1. Uprav pravidlá Turingovho stroja zo 7. ú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. Navrhni Turingov stroj, ktorý číslo v dvojkovej sústave vynásobí dvoma a pripočíta 1. Napr.

    >>> cislo = 27
    >>> t = Turing(prog, bin(cislo)[2:])
    >>> t.rob(False)
    True
    >>> int(t.paska.text(), 2)
    55
    

  1. Na páske je číslo zapísané v desiatkovej sústave. Navrhni Turingov stroj, ktorý toto číslo zvýši o 1. Napr.

    >>> cislo = 1299
    >>> t = Turing(prog, str(cislo))
    >>> t.rob(False)
    True
    >>> t.paska.text()
    '1300'
    

  1. Navrhni 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. Navrhni Turingov stroj, ktorý predpokladá, že na páske je postupnosť znakov 'x'. Po skončení práce stroja (metóda rob() vráti True) bude na páske celá táto postupnosť iksov skrátená na polovicu, napr.

    >>> t = Turing(prog, 'xxxx')
    >>> t.rob(False)
    True
    >>> t.paska.text()
    'xx'
    >>> t = Turing(prog, 'x' * 15)
    >>> t.rob(False)
    True
    >>> t.paska.text()
    'xxxxxxx'
    

  1. Čísla od 0 do 255 sú uložené v jednom bajte (8 bitov). Čísla do 65535 sú uložené v dvoch bajtoch (16 bitov). Napíš funkciu bajty(cislo), ktorá z daného čísla vráti postupnosť bajtov. Zrejme posledný bajt vypočítaš ako cislo % 256 a zvyšné bajty sú potom cislo // 256 - toto budeš opakovať, kým nebude cislo nula. Napr.

    >>> bajty(100)
    [100]
    >>> bajty(1000)
    [3, 232]
    >>> bajty(10000)
    [39, 16]
    >>> bajty(2 ** 16 - 1)
    [255, 255]
    >>> bajty(3 ** 33)
    [19, 191, 239, 166, 90, 187, 131]
    

  1. Každý bajt (číslo od 0 do 255) sa dá zapísať jedným dvojciferným číslom v 16-ovej sústave. Napíš funkciu do_hex(post), ktorá postupnosť bajtov zo (16) úlohy vypíše v 16-ovej sústave. Výsledok porovnaj so šestnástkovým výpisom pôvodného čísla. Napr.

    >>> do_hex(bajty(1000))
    03 e8
    >>> hex(1000)
    '0x3e8'
    >>> do_hex(bajty(3 ** 33))
    13 bf ef a6 5a bb 83
    >>> hex(3 ** 33)
    '0x13bfefa65abb83'
    


1. Domáce zadanie

L.I.S.T.

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, ako keby 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šovaný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 odovzdajte v súbore riesenie1.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é tri riadky tohto súboru budú obsahovať:

    # 1. zadanie: Turing
    # autor: Janko Hrasko
    # datum: 20.2.2019
    
  • 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 riesenie1.py pridať testovacie riadky, ktoré však 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)

Projekt riesenie1.py odovzdávajte na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 6. marca, kde ho môžete nechať otestovať. Testovač bude spúšťať vašu funkciu s rôznymi vstupmi. Odovzdať projekt aj ho testovať môžete ľubovoľný počet krát. Môžete zaň získať 10 bodov.