Miško naujienos (2014)
Taškai: 12
Tolimojoje Bebrijoje laikraščio „Miško naujienos“ žinutės rašomos tik raidėmis A, B ir C. Trys korektoriai skaito žinutes iš kairės į dešinę ir ieško tam tikrų raidžių sekų.
- Jaunesnysis korektorius ieško sekų ABC. Radęs tokią seką pakeičia į BC ir tekstą skaito vėl nuo pradžių. Kai tokių sekų neberanda, tekstą persiunčia vyresniajam korektoriui.
- Vyresnysis korektorius ieško sekų BC. Radęs tokią seką pakeičia į B ir tekstą grąžina jaunesniajam korektoriui. Kai tokių sekų neberanda, tekstą persiunčia vyriausiajai korektorei.
- Vyriausioji korektorė ieško sekų BB. Radusi tokią seką, pakeičia į B ir tekstą grąžina jaunesniajam korektoriui. Kai tokių sekų neberanda, straipsnio koregavimas baigtas.
Duotos keturios žinutės:
A. AAABCB
B. ABCABC
C. ABABCB
D. ABCCCC
Atlikus korektūrą tris iš šių žinučių sudarys vienintelė raidė B, tačiau vieną – ne. Kuri žinutė negali sutrumpėti iki raidės B?
Aprašytasis koregavimo procesas – tai Markovo algoritmas. Kaip ir Tiuringo mašina, Markovo algoritmai formalizuoja algoritmo aprašymo procesą. Viskam, kas gali būti suskaičiuojama kompiuteriu, galima taikyti kurį nors iš Markovo algoritmų ir atvirkščiai.
Teisingas atsakymas – C.
AAABCB→AABCB→ABCB→BCB→BB→B
ABCABC→BCABC→BCBC→BBC→BB→B
ABABCB→ABBCB→ABBB→ABB→AB
ABCCCC→BCCCC→BCCC→BCC→BC→B