index předchozí 1 2 3 4 5 6 7 následující

Cvičení šesté

Konstrukce tabel pro BPA

Tablo pro gama = delta se skláda z podtabel. Podtablo s kořenem Xalfa = Ybeta vytvoříme takto: Nechť k = min { |X| , |Y| }. Na Xalfa=Ybeta aplikujeme k-krát trojici pravidel (REC, SUM, PREFIX). Po k-aplikacích jsou některé listy reziduály, jeden z nich označíme jako vytčený a podle něj aplikujeme pravidlo SUB (případně SUBL,SUBR). Po aplikaci SUB zkontrolujeme každý list: Jestliže je úspěšný ukončili jsme rozvoj příslušné větve tabla, jestliže je neuspěšný je celé tablo neúspěšné. Není-li ani úspěšný ani neúspěšný, tak pro něj budujeme podtablo. Jestliže v průběhu tvorby podtabla se některý vrchol (nemusí to být list) ukáže být neúspěšným, končíme s celým výpočtem.

Kritéria úspěšnosti:
  1) alpha=alpha
  2) alpha=beta a na ceste od tohoto listu do korene celeho tabla
      se vyskytuje uzel se stejnym oznacenim alpha=beta
      a mezi nimi je alespon jednou pouzito pravidlo PREFIX

Kritéria neúspěšnosti:
  1) a.alpha=b.beta ,kde a je různé od b
  2) alpha=beta ,kde |alpha| je různá od |beta|

Poznámka: 1) Výše uvedená metoda funguje pouze pro NORMOVANÉ BPA !!!
          2) Poznamka o zapisu: XY = X.Y

========================= P R A V I D L A ================================
X.alpha = Y.beta
--------------------REC     kde X je definovano jako E a Y je definovano jako F
E.alpha = F.beta

a.alpha = a.beta
------------------PREFIX
   alpha = beta

(SUMA^m_i=1a_ialpha_i)alpha = (SUMAⁿ_j=1b_jbeta_j)beta
-------------------------------------------------------------------------------SUM
{a_ialpha_ialpha = b_f(i)beta_f(i) beta}^m_i=1 = {a_g(j)alpha_g(j)alpha = b_jbeta_j beta}ⁿ_j=1

kde f:{1,...,m} ---> {1,...,n} a g:{1,...,n} ---> {1,...,n}

alpha_ialpha = beta_ibeta
------------------------SUBL     kde alpha = gamma.beta je vytčený residuál
alpha_igamma = beta_i

alpha_ialpha = beta_ibeta
------------------------SUBR     kde gamma.alpha = beta je vytčený residuál
alpha_i = beta_igamma =============================================================================

1) Zkonstruujte důkaz PQQ = SU

  P = aPQQ + bRQQ + c
  Q = c
  R = bP
  S = aSU + bT + c
  T = bSU
  U = cV
  V = c

2) Zkonstruujte důkaz FX = A

  A = aBCX + aB
  B = aC
  C = aD
  D = bD + c
  F = a + aXC
  X = aY
  Y = aD

3) Dokažte AH vlnka AGF, EF not vlnka D, BA not vlnka DG

  A = aBC + aD + aEF
  B = b
  C = c
  D = bH + bC
  E = bG
  G = c
  F = bA
  H = cBA

4) Y = C

  X = aYX + b
  Y = bX
  A - aC + b
  C = bAA

5) X = A

  X = aXX + b + cY
  Y = aYX + b + cX
  A = aAA + b + cA

6) A = E

  A = aBC + aH
  B = b
  C = d + aDE
  D = bF
  F = c
  E = aC + aGH
  G =b
  H = d + aI
  I = bK
  K = cA

7) A = X

  X = d + aXX + bY + cZ
  Y = bX + aYY + cZ + d
  Z = bX
  A = d + aAA + bA + cB
  B = bA

8) AB = XYB

 A = aB + aC
 X = a + aZ
 B = aB + a
 Y = aY + a
 Z = bZ + bX
 C = bC + bA

9) FBI = AB

 A = aBCI + aB
 B = aC
 C = aD
 D = bD + c
 F = a + aIC
 I = aK
 K = aD