Příklady

Trumpetista řadí noty

2018-09-17T10:39:39+02:00

Představte si, že stejně jako ostatní členové kapely si máte najít daných 40 skladeb z neseřazené složky asi 200. Tak začnete hledat první skladbu, dáte ji stranou, potom od začátku zase druhou skladbu, dokud nemáte všech 40, na tom přece nic není. Nebo by to snad šlo udělat nějak líp?

V popsané situaci se Roger Dannenberg, trumpetista, zachoval spíš jako informatik. Odhadl, že množství těch papírů stojí za rychlou úvahu. Zatímco všichni ostatní začali postupně procházet složku a po jedné hledat a vybírat skladby, Dannenberg se rozhodl nejprve složku s dvěma sty skladbami seřadit.

Abychom mohli jeho přístup s ostatními porovnat, potřebujeme nějakou “měrnou jednotku”. Pro zjednodušení budeme počítat, kolikrát je potřeba vzít do ruky papír se skladbou a porovnat její název s nějakým jiným (nebo stejným). Když se řadí chytře, je potřeba řádově nanejvýš N·log2(N) takových porovnání. Parametr N je počet řazených věcí, v našem případě velikost složky, takže 200. Můžeme tedy odhadnout 200·8 = 1600 porovnání (200 je někde mezi 128 a 256, logaritmus 200 je mezi 7 a 8). To je docela hodně, a skutečně, on pořád ještě řadil, zatímco ostatní byli zpola hotovi a podivovali se jeho počínání.

Teprve v seřazené složce pak Dannenberg hledal konkrétní skladby. Jako informatik to opět dělal optimálně, takže každou skladbu jistě našel nejpozději na osmé podívání (porovnání). Skladeb hledal 40, využil tedy přinejhorším 40·8 = 320 porovnání. Celkově pak pro celý úkol 1600+320 = 1920 porovnání.

Ostatní hledali v neseřazené složce a museli proto kontrolovat každý jeden list, dokud skladbu po průměrně 100 porovnáních nenašli. Celkově tak potřebovali 40·100 = 4000 porovnání. Trumpetista Dannenberg skončil pohodlně jako první.

Uvedné výpočty jsou samozřejmě jen odhady. Možná sami odhalíte, co všechno jsme zjednodušili a zanedbali. Dostatečně ale ilustrují, jaký rozdíl způsobí snaha o efektivní postup podpořená základními znalostmi. Dannenberg navíc téměř jistě nic takového nepočítal, využil prostě zkušenost a intuici. Kdyby bylo not k vyhledání víc, rozdíl by byl ještě větší.

Teď když už jsou všechny skladby nalezeny, máme víc času se v klidu zamyslet. Nemohli bychom postupovat ještě lépe? Předchozí odhady ukázaly, jakou sílu má počet skladeb ve složce. Co kdybychom zkusili minimalizovat počet průchodů touto složkou? Ideálně tak, abychom na každou skladbu “sáhli” pouze jednou? Postup hledání by se tak obrátil: pro každou skladbu ve složce bychom kontrolovali, jestli patří mezi hledané. Takový postup není vůbec intuitivní, ale podívejme se, jak obstojí vůči předchozím.

Abychom si hledání usnadnili, předem bychom seřadili seznam hledaných skladeb (za 40·log240 kroků, odhadněme jako 240). Jedna kontrola v takto seřazeném seznamu si pak vyžádá nanejvýš 6 kroků. Celkem bychom tedy dostali 240+200·6 = 1440 kroků, aspoň takhle v teorii tedy jaště lepší postup, než použil náš trumpetista-informatik.

Nakonec si povšimněme, že v popsané situaci nejde bezmyšlenkovitě použít postupy známé z informatiky. Informatici umí dobře vyhledávat a řadit posloupnosti čísel v pracovní paměti. Jenom když dobře rozumí tomu, proč a jak ty osvědčené algoritmy fungují, mohou je přizpůsobit zcela jiným podmínkám - např. jinému fungování pracovní paměti člověka a tomu, že má dvě ruce.

Dan Lessner, blog Učíme informatiku

Hledání dárců ledvin

2018-09-18T10:39:39+02:00

Tisíce lidí potřebují každoročně dárce ledvin. Ochotný dárce z rodiny ale není vždy kompatibilní. Proto má smysl hledat vzájemné kombinace dárců a příjemců. Řešení, které není nejlepší, nebo které je nalezeno pozdě, přitom znamená, že zemře někdo, kdo zemřít nemusel.

Zapojení informatického myšlení na straně organizátorů dárcovského systému vedlo k rozpoznání problému a posouzení jeho řešitelnosti: teoreticky by mělo být možné řetězec transplantací sestavit. Může například nastat situace, kdy bratři Dijkstrovi ani sestry Hopperovy nemají kompatibilní ledviny. Jsou ovšem kompatibilní křížem: Zdravý pan Dijkstra může darovat ledvinu nemocné paní Hopper a naopak.

Následná spolupráce s informatiky vedla ke kvalitativnímu zlepšení situace. V praxi se daří nacházet řetězce ještě delší, a to mnohem rychleji, než kdyby se měly hledat ručně. Nejde přitom až tak o výpočetní sílu stroje. Podstatné je, že se podařilo najít efektivní algoritmus.

Řetězové transplantace již několik let probíhají i v ČR. Detailní informace najdete na stránkách Center for Computational Thinking.

Dan Lessner, blog Učíme informatiku

Každodenní použití

2018-09-18T11:39:39+02:00

Balení školní brašny je předběžné načítání (nebo spíš nakládání) do pracovního úložiště. Organizace jogurtů v lednici podle data spotřeby je prioritní fronta. Telefonní linka fungující i při výpadku proudu ukazuje redundanci a nezávislost selhání v návrhu. Některé příklady jsou tak jednoduché, že kvůli nim opravdu není třeba studovat informatiku.

Podobně jednoduchým příkladem je pipeline v jídelně. Nikoho snad ani nenapadne neseřadit „nějak rozumně“ výdej táců, příborů, polévky, jednoho z hlavních jídel, ovoce, sklenic a nápojů, aby strávníci mohli postupovat pěkně v řadě a nevráželi do sebe. Čas od času ovšem narazíme na situaci ekvivalentní, mimo známý jídelnový kontext — a organizace se změní v chaos.

Nebo jiný příklad: znáte někoho, kdo potřeboval změnit uspořádání zásuvek v komodě? A přehazoval jejich obsah, nebo prostě zaměnil celé zásuvky? Když si s přáteli v řadě podáváte polínka na topení (nebo knížky), abyste je efektivně přestěhovali, ovšem přátel přibývá, kdy už se vyplatí vytvořit další, paralelní řadu?

Tyto triviální příklady ukazují, že se informatické principy najdou i v doslova každodenním životě. Čím je situace jednodušší, tím spíše ji zdárně vyřešíme i bez znalosti informatiky. Podobně i hmotnost cihly z úlohy „cihla váží kilo a půl cihly" zjistíme bez znalosti rovnic. Vybíráte si k zaplacení nákupu opravdu nejvhodnější pokladnu, nebo jen tak odhadujete? A z pohledu obchodníka: naplníte regál intuitivně, nebo přijdete s robustnějším řešením? A co teprve organizace skladu? Čím je řešený problém rozsáhlejší, tím více se vyplatí chytrá řešení.

Dan Lessner, blog Učíme informatiku

Svatební hostina

2018-11-23T13:06:03+01:00

Přípravy na svatební hostinu vrcholí. Všude přibývají ozdoby, květiny přesně podle přání toho, pro koho je to důležité, a konečně dorazila i krabice s pěkné vyvedenými jmenovkami pro hosty. Spolu se zasedacím pořádkem, aby bylo jasné, jak jmenovky rozmístit k velikému stolu. Ovšem čas běží, a běda, pokud tento nejdůležitější den nebude perfektní. Jak si poradíte?

Nabízí se docela hodně možností:

Vezmu krabici, obcházím stůl, pro každé místo dohledávám jmenovku
Beru jmenovky po jedné, každou najdu v zasedacím pořádku a donesu na místo.
- Jméno v zasedacím pořádku po nalezení škrtnu. Nebo raději až po umístění jmenovky, kdybych třeba zapomněl, kam jdu.
- Po cestě už můžu hledat místo další jmenovky.
Zkusím rozdělit práci mezi několik pomocníků… jenže jak? Mají si vzít několik jmenovek? Nebudou do sebe vrážet? Mají si vzít na starost nějakou část stolu? Mám více kopií zasedacího pořádku?
Práci si nejprve připravím: jmenovky si rozmístím na samotný zasedací pořádek, aniž by bylo třeba někam chodit. Potom je v daném pořadí sesbírám a na jeden průchod kolem stolu rozmístím. Nebo ten úkol už snadno zadám pomocníkům.

Informatika neříká, co je obecně nejlepší postup pro rozmístění jmenovek. Asi jste sami poznali, že optimální postup závisí na mnoha okolnostech (Máme pomocníky? Kolik? Jak schopných? Kolik je jmenovek, jak je velký stůl, popř. kolik jich je a jak rozmístěných? Kolik jmenovek se mi vejde ruky? Na jak velkém papíru je zasedací pořádek?). Situace je navíc ztížena tím, že čas běží i během rozmýšlení postupu. V jeden okamžik je tedy třeba začít. Potřebujeme rozpoznat, který postup je už dostatečně dobrý (nejspíš to ale nebude ten, který nás napadne jako první). Právě pro rozhodnutí naznačená v tomhle článku je informatické myšlení jako stvořené.

Stejně jako pro přípravu samotného zasedacího pořádku, aby spolu seděli pokud možno ti, kteří mohou, a v žádném případě ne ti, kteří nemohou. To je zase úplně jiné dobrodružství.

Dan Lessner, blog Učíme informatiku