Matematická olympiáda – kategorie P

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[z₁..k₁] a A[z₂..k₂] se nepřekrývají, jestliže k₁<z₂ nebo k₂<z₁. 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 z₁<=k₁<z₂<=k₂ přemění řetězec A=A[1..z₁-1]A[z₁..k₁]A[k₁+1..z₂-1]A[z₂..k₂]A[k₂+1..N] na řetězec A'=A[1..z₁-1]A[z₂..k₂]A[k₁+1..z₂-1]A[z₁..k₁]A[k₂+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')²+(y-y')²) přes všechny dvojice (x,y), (x',y') bodů z S.

Body X₁=(x₁,y₁),..., X_n(x_n,y_n) (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₁, x₂, ..., x_n (vstupní proměnné)
f₁:=g₁ op h₁
f₂:=g₂ op h₂
....
f_k:=g_k op h_k
Výstup: y₁, y₂, ..., y_m (výstupní proměnné)
přičemž pro každé i=1, ..., k je g_i, h_i prvkem {x₁, ..., x_n} U {f₁, ..., 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
f₁ := a * b
f₂ := c * d
f₃ := f₁ - f₂
Výstup: f₃
počítá hodnotu výrazu ab-cd a má multiplikativní složitost 2.

Úlohy

1. Najděte lineární algoritmus, který pro vstup x vypočítá hodnotu mnohočlenu x+9x²+9x³+2x⁴ 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í).
2. 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 X^k.
• 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

1. Najděte číslo M, které vytváří samo sebe , tj. M->M !
2. Existuje číslo N, které vytváří své zdvojení, tj. N->NN ?
3. Existuje číslo P, které vytváří číslo P2, tj. P->P2 ?
4. Existuje číslo Q, které vytváří číslo 6Q, tj. Q->6Q ?
5. (McCullochův zákon) Dokažte, že pro každé číslo A existuje takové číslo X, že X vytváří AX, tj. X->AX !
6. Existuje R tak, že R->R6 ?