Student World

Jistě se to dá provádět nějakým lepším způsobem, než provádět test každého jednotlivého odběru…

***pravidelné páteční „přetištění“ staršího článku

***texto text je úryvkem z knihy
Dennis E. Shasha
Kybernetické hlavolamy Dr. Ecca
Mladá fronta, Praha 2006

Další úryvek z knihy: Drobné pro Mudžikistán
http://www.businessworld.cz/bw.nsf/ID/41AD0935D6C7485BC125716200533BF3/

Měl na sobě sportovní sako a kravatu, ale kolem krku mu visel stetoskop. Dr. Max Jacobs si nás několik sekund prohlížel. „Doufám, že nejste choulostivá, mladá dámo,“ řekl Lianě. „Bude řeč o krvi.“
„Lidské nebo mločí?“ zeptala se ho Liana s úšklebkem.
Dr. Jacobs se usmál.
„Jsi pohotová,“ řekl. „Bude se ti to hodit při řešení problému, který před tebe, Dr. Ecca a profesora chci postavit. Asi víte, že hepatitis C je velmi devastující nemoc, jež se dá přežít pomocí transfuze krve. Test na hepatitis C se nazývá ELISA. Není však dostatečně spolehlivý, protože občas ukáže nemoc tam, kde není, a naopak. Vedle něho existuje nákladná, ale zato poměrně přesná technika založená na PCR. Je natolik přesná, že když vezmeme kapku krve z 50 tisíc půllitrových odběrů, z nichž je jediný kontaminován hepatitidou C, dokážeme kontaminaci zjistit.
Naše centrum dostává takových dávek 100 tisíc denně. Přibližně 1% z nich je touto nemocí kontaminováno. Rádi bychom našli způsob, jak zjistit, které dávky to jsou, ale s použitím nanejvýše 20 tisíc testů. Každý test však trvá dvě hodiny a my potřebujeme rozhodnout o osudu každé dávky nanejvýš za čtyři hodiny. Dokážete nám pomoci?“
„Jak musíme být přesní?“ zeptala se Liana. „Mám na mysli jak moc vám záleží na tom, abyste se špatnou krví nevyhodili také dobrou.“
„Ty máš zajištěnou budoucnost u ministerstva zdravotnictví,“ odpověděl jí Jacobs s úsměvem. „Pro začátek předpokládejme, že nesmíte vyřadit více než dvě dobré dávky na každou skutečně špatnou.“
„Zkusme nejdříve případ, kdy každá dávka může být otestována na hepatitis C jediným testem, tedy za dvě hodiny, než rozhodneme o jejím osudu,“ navrhl Ecco.

Rada pro kybernetické učně: Než budete číst dále, podívejte se jestli dokážete nalézt metodu s méně než 35 tisíci testy, která nemá za následek vyřazení více než dvou tisíc dávek dobré krve, za předpokladu, že v sadě je 1000 dávek špatných. O všech dávkách musí být rozhodnuto přibližně za 2 hodiny.

„To je dobrý nápad, strýčku,“ pochválila ho Liana. „Dobrá. Protože máme tisíc špatných dávek a tudíž můžeme udělat dva tisíce chyb, rozdělíme všechny dávky na 33.333 skupin po třech a zbude nám jedna skupina o jedné dávce. Všechny dávky v každé skupině vyzkoušíme najednou. Jedna tisícovka skupin bude mít špatnou dávku, a my každou takovou skupinu prostě vyhodíme.“

1. Úloha pro kybernetické učně: V situaci, kdy jsou na celý test dovoleny jen čtyři hodiny, přičemž na 100 tisíc dávek připadá jen jeden tisíc špatných a můžeme vyřadit dva tisíce dobrých dávek jako špatné, dokázala Liana provést úkol s méně než 12 tisíci testy. Jak zdatní jste vy?

„A co když nejsou povoleny žádné omyly?“

2. Úloha pro kybernetické učně: Liana dokázala vyřešit případ, kdy nejsou povoleny žádné omyly, při 20 tisících testů. Dokážete to také?

„Máme tak na vybranou jestli zahazovat úplně zdravou krev, nebo dělat tolik testů,“ řekl nevesele Dr. Jacobs. „Dejme tomu, že by se naše předběžné vyšetření před testem trochu zdokonalilo, takže bychom mohli zajistit, že bude kontaminována pouze jediná dávka. Jaký nejmenší počet testů provedených za dvě hodiny byste potřebovali, abyste nemuseli vyřadit žádnou dobrou krev?“

3. Úloha pro kybernetické učně: Liana to dokázala se 17 testy, ale pro každý jsou nutné vzorky z mnoha dávek. Jak jste na tom vy?

„Přesně jedna špatná dávka nedává smysl. Co kdyby jich místo toho byl jen nějaký malý počet, řekněme nanejvýše 10, a vy stejně nechcete o žádnou zdravou krev přijít?

4. Úloha pro kybernetické učně: Pro tuto situaci neměla Liana žádnou zaručenou metodu, jak úkol vyřešit za dvě hodiny. Dokonce i pro 4 hodiny vyžadovalo její nejlepší řešení v nejnepříznivějším případě až 1900 testů. Potom metodu zlepšila na 733 a nakonec na 714 testů. Dokážete to ještě líp?

Dr. Jacobs si vše zaznamenával nečitelnou doktorskou čmáranicí. Zapsal si dokonce i Lianino poslední řešení. „Máte chytrou neteř, Ecco. Gratuluji,“ řekl. Složil svůj papír do kapsy, podal nám ruku a spokojeně odešel.

***texto text je úryvkem z knihy

Dennis E. Shasha
Kybernetické hlavolamy Dr. Ecca
36 hlavolamů pro hackery a ostatní matematické detektivy
objednávka viz
http://www.bookcafe.cz/product_info.php/info/p723_kyberneticke-hlavolamy-dr–ecca.html

***

Řešení

Mějte na paměti, že úloha se dá řešit mnoha různými způsoby. Pro případ se čtyřhodinovým omezením jsou významné následující dva postupy.
Připomeňme si, že v základní verzi úlohy bylo 100 tisíc dávek krve, z níž část mohla být kontaminována hepatitidou C. K dispozici je dvouhodinový test PCR, který může zjistit dokonce i velice malá množství hepatitidy, takže je možné smíchat dohromady po kapce krve z každé dávky a hepatitis může být i v této směsi zjištěna.

1. V první verzi úlohy, kdy je špatných dávek jeden tisíc, přičemž spolu s nimi smí být vyřazeny i dva tisíce dobrých, a k dispozici máme 4 hodiny, si počínáme následovně:

a. Rozdělte 100 tisíc dávek do 5882 skupin o 17 dávkách, takže vám na poslední skupinu zbude pouze 6 dávek.
b. Proveďte současně 5883 testů všech skupin. V nejhorším případě jich bude 999 špatných. Kdyby jich bylo právě tisíc, pak by to znamenalo, že v každé skupině je právě jedna špatná dávka. Která to je, se zjistí dalším testováním uvnitř těchto skupin. Očíslujme si jejich členy od 0 do 16, ale ve dvojkové soustavě. Nejnižší pořadí by tedy bylo 00000, nejvyšší 10000. Nyní namícháme novou sadu směsí krve tak, že v každé směsi je po jedné kapce pouze z 16 dávek s tím, že v první směsi nebude zastoupena dávka s číslem 16 (odpovídá nule na místě s nejvyšším dvojkovým řádem, tedy číslu 0xxxx, kde x značí nulu nebo jedničku) ve druhé bude nula na druhém místě zleva atd., takže vznikne celkem pět takových sad o 16 dávkách, z nichž právě jedna je špatná. Dejme tomu, že to je třeba dávka číslo 6, tedy 00110. Jak se snadno přesvědčíme, prozradí se přítomnost této špatné dávky špatným výsledkem testu s nulou na třetím a na čtvrtém místě zleva při výše uvedeném číslování. Totéž provedeme současně u všech uvažovaných skupin, kterých je 1000 a potom provedeme během dalších dvou hodin 5 krát 1000 = 5000 dalších testů, z nichž 1000 je se špatným výsledkem.
c. V případě, kdy bude počet pozitivních testů roven 999, je počet potenciálně špatných dávek roven 999 x 17 = 16 983. Rozdělíme je na 5661 skupin po třech dávkách a otestujeme každou skupinu jako celek. Všechny dávky ze špatných skupin pak vyřadíme. Celkový počet testů je 5883 + 5661 = 11 544.
Tento postup, který navrhl Magne Oestlyngen, byl až dosud nejčistší a nejstručnější.

2. Pokud se nesmí spolu se špatnými vyřadit žádné dobré dávky, pak si můžeme být jisti, že jsme nalezli následující odpověď s 20 000 testy. Všech 100 000 dávek rozdělíme na 10 000 skupin po deseti. V nejnepříznivějším případě bude mít 1000 skupin špatné dávky, takže otestujeme všech těchto 10 000 dávek. Jestliže je špatných skupin méně, budeme dělat testů rovněž méně.

3. Provedeme očíslování všech dávek ve dvojkové soustavě, k čemuž potřebujeme 17 bitů. Dále otestujeme směs malých vzorků dávek s pořadovými čísly majícími na nejvyšším řádovém místě 1, a výsledek testu zapišme jako jedničku nebo nulu podle toho, je-li směs kontaminována nebo ne. Je to budoucí bit adresy hledané kontaminované dávky. Potom učiníme totéž se směsí vzorků dávek s jedničkou na druhém nejvyšším bitu pořadového čísla a výsledek stejným způsobem dosadíme za další bit adresy, a tak dále celkem pro všech 17 bitů. Adresa kontaminované dávky je pak dána jako dvojkové číslo sestavené z výsledků celkem 17 testů, jež mohou být prováděny současně, takže úloha je splněna za dvě hodiny.

4. Následuje metoda, jak nalézt až 10 špatných dávek během méně než 2000 testů za 4 hodiny. Otestujte 1000 skupin po sto dávkách. Jestliže je 10 směsí špatných, pak víme, že je jedna dávka v každé skupině a provedeme binární hledání jako v předešlém případě. Jinak otestujeme dávku po dávce 9 nebo méně skupin, což vyžaduje o něco méně než 900 dalších testů.
Dá se to však udělat lépe, jak ukázal Dennis Yelle. Uspořádejte všech 100 000 dávek do velké téměř čtvercové matice o 316 řádcích a 317 sloupcích. 172 zbývajících pozic může být vyplněno prázdnými místy. Za první dvě hodiny proveďte 633 testů následujícím způsobem: Proveďte 316 testů, kdy každý test využívá každý vzorek v jednom z 316 řádků. Všimněte si přitom, že 316 x 317 > 100 000. Jestliže buď 10 řádků nebo sloupců dopadne špatně, je jedna špatná dávka v každém z nich a my můžeme opět použít binární postup vyžadující pouze 40 dalších testů. Nejhorší případ pak je, že 9 řádků a 9 sloupců je špatných, takže je potřeba celkem 81 dalších testů. To dohromady dává 633 + 81 = 714 testů. K tomuto řešení přispěli Eliah Pau, Ng Weng Leong a Tomas Rokicki.

Nápady a poznámky

K této úloze mě inspirovala návštěva transfúzní stanice. Vždycky tam odebírají zvláštní zkumavku ke zkoušce, zda je vaše krev dostatečně způsobilá k uložení jako krevní konzerva. Přemýšlel jsem, jak krev testují, když vědí, že většina krve je dobrá. Jistě se to dá provádět nějakým lepším způsobem, než provádět test každého jednotlivého odběru. Nevěděl jsem ani, že o téže věci již přede mnou přemýšlel jeden matematicky založený voják, když mu při vstupu do armády testovali krev na syfilis. Vypracoval metodu a dokonce o tom vznikla literatura. V každém případě se nápady některých čtenářů zdají být nové a mohou přispět v každé situaci, kdy je testování nezbytné. Můj kolega Mike Goodrich z John Hopkins věří, že pravděpodobnostní algoritmy (při nichž se k rozhodování uvnitř programu používají náhodná čísla) mohou vést k mnohem lepším výsledkům, než je dosud známo. Tato otázka je stále otevřena.

autor