Tölvumál - 01.04.1983, Qupperneq 8

8
Ljóst er að takraarka 'þarf svör enn frekar. Skilgreinum
>ví:
annars
Skýringar:
S = Einhver tölfræðileg spurning.
C = Skilyrði sem afmarkar hóp.
N = Fjöldi lína í töflunni.
K = Lágmarksfjöldi sem þarf að afmarkast af
skilyrðlnu C t.þ.a. spurningu sé svarað.
N-K = Hámarksfjöldi sem skilyrði má afmarka
t.l>.a. spurningu sé svarað.
Athugum nú hvort við getum komist að hlutum sem á að
halda leyndum í einhverju gagnasafni. Takmarkanir á svörum
eru eins og getlð er að ofan og l<K<=N/2 . Við vitum (eftir
einhverjum leiðum) að einstaklingur I ákvarðast einkvæmt af
skilyröinu C. Vlð viljum komast að því hvort hann uppfyllir
einnig skilyrði a. Nú er FJÖLDI( C AND a ) < = FJÖLDI (C) =1<K
þ.a. við getum ekki notað aðferöina sem við notuðum áöur.
SPORHUNDAR.
Hér hefur J. Schlörer aðferð sem getur komið að notum
(heimild 2) . Ef við getum brotið C niöur í tvo hluta þ>á
getur verið að við getum fundið út FJÖLDI( C AND a ) með "því
að spyrja tveggja spurninga sem hafa að geyma brotin úr C.
Hugsum okkur að hægt sé að brjóta C, sem við teljum að
einkenni I einkvæmt, niður í C=( A AND B ) þ.a. svör fáist
við spurnlngunum FJÖLDI( A AND ( NOT B )) og FJÖLDI(A).
Þ.e.a.s við viljum að eftirfarandi gildi:
K<=FJÖLDI( A AND ( NOT B ))<=FJÖLDI(A)<=N-K
Jafnan T=( A AND ( NOT B )) er kölluð sporhundur (tracker)
v.þ.a. hún gerir okkur kleyft að þefa uppi ýmis leyndarmál
um I.