Zadání úloh školního kola 42. ročníku
P-I-1
Je dán řetězec délky N uložený v poli A (v jazyku Pascal
bychom to mohli vyjádřit deklarací
var A:array[1..N] of char).
Hodnota N je přitom tak veliká, že A zabírá skoro celou operační paměť.
Blok je souvislý podřetězec řetězce A začínající znakem s indexem z a
končící znakem s indexem k (1<=z<=k<=N), takovýto blok budeme označovat
A[z..k]. Bloky A[z1..k1] a A[z2..k2] se nepřekrývají, jestliže
k1<z2 nebo k2<z1. Například podřetězce A[4..5]=ak a
A[8..10]=abr jsou nepřekrývající se bloky řetězce A=abrakadabra.
Napište a zdůvodněte algoritmus, který vymění dva nepřekrývající se bloky
řetězce A, tj. pro zadané indexy z1<=k1<z2<=k2 přemění řetězec
A=A[1..z1-1]A[z1..k1]A[k1+1..z2-1]A[z2..k2]A[k2+1..N]
na řetězec
A'=A[1..z1-1]A[z2..k2]A[k1+1..z2-1]A[z1..k1]A[k2+1..N].
Například výměnou uvedených bloků v řetězci abrakadabra vznikne řetězec
abrabradaka.
Algoritmus smí použít jen konstantní pomocnou paměť (operační paměť je skoro
plná, nemusí se do ní vejít ani kopie menšího z bloků) a počet kroků algoritmu
by měl být úměrný N.
P-I-2
Průměr rovinného útvaru S je největší vzájemná vzdálenost mezi 2 body S:
diam(S)=max sqrt((x-x')2+(y-y')2)
přes všechny dvojice (x,y), (x',y') bodů z S.
Body X1=(x1,y1),...,
Xn(xn,yn) (n>=3) tvoří (v tomto
pořadí) vrcholy konvexního
n-úhelníka M v rovině. Napište a zdůvodněte algoritmus, který uřčí diam(m) -
průměr mnohoúhelníka M.
Poznámka: Existuje algoritmus s lineární časovou složitostí.
P-I-3
Multiplikativní složitost
Lineární algoritmus je algoritmus následujícího tvaru:
Vstup: x
1, x
2, ..., x
n (vstupní proměnné)
f
1:=g
1 op h
1
f
2:=g
2 op h
2
....
f
k:=g
k op h
k
Výstup: y
1, y
2, ..., y
m (výstupní proměnné)
přičemž pro každé i=1, ..., k je g
i, h
i prvkem
{x
1, ..., x
n} U {f
1, ..., f
i-1}
a op je jedna z operací +, -, * (sčítání, odčítání, násobení).
Složitost lineárního algoritmu je počet operací op, multiplikativní složitost
lineárního algoritmu je počet operací *.
Například následující lineární algoritmus:
Vstup: a, b, c, d
f1 := a * b
f2 := c * d
f3 := f1 - f2
Výstup: f3
počítá hodnotu výrazu ab-cd a má multiplikativní složitost 2.
Úlohy
- Najděte lineární algoritmus, který pro vstup x vypočítá hodnotu mnohočlenu
x+9x2+9x3+2x4 s nejmenší
možnou multiplikativní složitostí, své tvrzení
zdůvodněte (dokažte, že neexistuje lineární algoritmus řešící tuto úlohu s menší
multiplikativní složitostí).
- Dokažte, že hodnota výrazu ab-cd se nedá vypočítat lineárním algoritmem
s multiplikativní složitostí 1!
P-I-4
McCullochův stroj
McCullochův stroj slouží ke zpracování čísel. Má vstup a výstup; jestiže
na vstup dáme číslo, tj. konečnou neprázdnou posloupnost cifer 1, 2, ..., 9,
po konečném čase se na výstupu může (ale nemusí) objevit (obecně jiné) číslo -
odpověď stroje na vstupní číslo. V prvním případě (jestliže se odpověď objeví),
vstupní číslo se nazývá přijatelným. Odpověď stroje je vstupním číslem jednoznačně
určená:
- jestliže je vstupní číslo přijatelné, odpověď se objeví vždy a je vždy stejná.
- jestliže vstupní číslo není přijatelné, nikdy se neobjeví odpověď a stroj
se po konečném čase zastaví (tj. můžeme zjistit, že vstupní číslo není přijatelné).
Zavedeme si tato značení:
- Jak již bylo řečeno, čísla jsou pro nás kladná celá
čísla, jejichž desítkový zápis neobsahuje nulu.
- Jestliže X, Y jsou čísla, pak XY označuje jejich spojení: číslo, které dostaneme
napsáním zápisů čísel X, Y za sebou (v tomto pořadí). Např. pro X=53 a Y=728 je
XY=53728 a XYX=5372853. Číslo XX..X (k-krát) zapíšeme jako Xk.
- Zdvojením čísla X je číslo XX, tj. např. zdvojením čísla X=12345 je XX=1234512345.
- Říkáme, že číslo X vytváří číslo Y, jestliže X je přijatelné a po zadání X na
vstup stroje je odpovědí Y. Tento vztah budeme zkráceně zapisovat X->Y.
McCullochův stroj se řídí následujícími pravidly:
- Pravidlo P1: Pro libovolné číslo X, 2X2 je přijatelné a vytváří X (2X2->X).
- Pravidlo P2: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 7X vytváří Y2. Zkráceně: z X->Y plyne 7X->Y2.
- Pravidlo P3: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 5X vytváří
zdvojení čísla Y, tedy z X->Y plyne 5X->YY.
- Pravidlo P0: Číslo X je přijatelné pravě tehdy, když to vyplývá z pravidel
P1, P2, P3.
Například 2532->53 podle P1, 72532->532 podle P2, 572532->532532 podle P3,
ale 4253 není přijatelné podle P0.
Operační číslo je číslo složené z cifer 5, 7. Každé operační číslo M určuje
operaci M() v následujícím smyslu: z X->Y plyne MX->M(X). Např. 5 určuje
operaci zdvojení (5(Y)=YY), neboť z X->Y plyne 5X->YY. 75 určuje operaci
připsání 2 ke zdvojení (75(Y)=YY2), neboť z X->Y plyne 75X->YY2.
Úlohy
- Najděte číslo M, které vytváří samo sebe , tj. M->M !
- Existuje číslo N, které vytváří své zdvojení, tj. N->NN ?
- Existuje číslo P, které vytváří číslo P2, tj. P->P2 ?
- Existuje číslo Q, které vytváří číslo 6Q, tj. Q->6Q ?
- (McCullochův zákon) Dokažte, že pro každé číslo A existuje takové číslo X, že X vytváří AX, tj. X->AX !
- Existuje R tak, že R->R6 ?