Matematická olympiáda – kategorie P

Zadání úloh domácí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: x1, x2, ..., xn (vstupní proměnné)
f1:=g1 op h1
f2:=g2 op h2
....
fk:=gk op hk
Výstup: y1, y2, ..., ym (výstupní proměnné)
přičemž pro každé i=1, ..., k je gi, hi prvkem {x1, ..., xn} U {f1, ..., fi-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

  1. 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í).
  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á:

Zavedeme si tato značení: McCullochův stroj se řídí následujícími pravidly: 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 ?