Témata

Témata jsou hlavním obsahem časopisu M&M. Obvykle představují složitější a obecnější problémy než samostatné úlohy. Navíc je v jejich zadání vždy prostor pro tvůrčí rozšíření. Za pěkný článek k tématu lze získat třeba i 20 bodů, určitě se tedy vyplatí se tématy zabývat.

Jak řešit téma?

Letos jsme pro tebe připravili tato témata:

Téma 1: Krotitelé světla

Laser je přístroj, který dokáže vytvořit světelný svazek natolik koncentrovaný, že ho lze využít k mechanickým úkonům, např. řezání skla. My s ním sice v této úloze přímo pracovat nebudeme, pokusíme se však jeho vlastnostem přiblížit za pomoci nám dostupných jednodušších mechanismů – odrazu a lomu světla. Naším cílem bude ovládnout světlo a donutit ho vytvořit v prostoru oblast s výrazně vyšší intenzitou.

Nejjednodušším přístrojem, který má tuto schopnost, je optická čočka, která zalamuje rovnoběžné paprsky blízké optické ose do jediného bodu (ohniska). Je možné celý výkon koncentrovaný v tomto bodě následně nasměrovat do libovolně tenkého paprsku? Jestliže ne, proč?

Je možné zařídit, aby bylo do ohniska lámáno víc paprsků? Navrhněte uspořádání (stačí ve 2D), při kterém je do ohniska, případně do jediného paprsku, koncentrováno co nejvíce světla z okolí. Můžete uvažovat rovnoměrné osvětlení, nebo naopak předpokládat, že světlo přichází primárně z jednoho konkrétního směru.

Nemusíte se při tom ani držet čočky, zkuste nalézt jiný předmět s podobnými vlastnostmi. Jaký tvar by musel mít povrch objektu, aby lámal do ohniska všechny rovnoběžné paprsky bez ohledu na jejich vzdálenost od optické osy? Popřípadě zkuste nalézt takový předmět, který v sobě udrží paprsek co nejdéle. Může existovat takový předmět, v němž by jednou vlétnuvší paprsek už zůstal?

K výpočtu dráhy každého paprsku využijte zákony odrazu a lomu, můžete uvažovat paraxiální aproximaci (tj. $\sin \alpha =\alpha =\mathop {\mathrm{tg}}\alpha $ pro malé $\alpha $), nebo se od ní naopak odchýlit a přemýšlet obecněji. Můžete využít i více různých materiálů s různými indexy lomu. Vítány jsou také jakékoli experimentální realizace vámi vytvořených schémat.

Evžen

Stejně


Téma 2: Mapování DNA

Využívat a ohýbat přírodu pro své záměry se lidé snaží snad už celé věky. Ale až v posledních desetiletích se nám dostaly do rukou nástroje, kterými dokážeme manipulovat s těmi nejzákladnějšími stavebními kameny života – s DNA. Díky nim dokážeme uměle vytvářet nové organismy nebo třeba velmi přesně předpovídat, jaké zdravotní problémy by toho kterého člověka mohly potkat.

Ale k tomu, abychom mohli DNA upravovat pro naše záměry, je třeba vědět, kde se v ní co nachází. Dnes asi nejjednodušší možností je DNA prostě nasekvenovat – tedy určit jak přesně jdou jednotlivé báze v dané DNA za sebou – a vše vyčíst z řetízku bází. My se ale podíváme na metodu, která nám toho sice o DNA řekne méně, ale zase je mnohem jednodušší. A to na restrikční mapování.

Restrikční mapování je založené na použití tzv. restrikčních enzymů. To jsou molekuly, které dokážou DNA „rozstřihnout“ v těch místech, která obsahují nějakou konkrétní posloupnost bází (např. enzym EcoRI rozstřihne posloupnost bází GAATTC). Nejdřív tedy DNA pomocí nějakého restrikčního enzymu rozstříháme na kratší kusy – fragmenty. Následně pomocí elektroforézy změříme délky a počty fragmentů a z těchto informací chceme sestavit restrikční mapu. To je seznam míst v DNA, ve kterých stříhá daný enzym (restrikčních míst). Pokud máme DNA dlouhou 20000 bází a získáme fragmenty délky 8000, 7000 a 5000 bází, pak restrikční mapa může např. říkat, že enzym stříhá v místě vzdáleném 7000 bází od začátku sekvence a v místě vzdáleném 15000 bází od začátku sekvence.

Z příkladu už je vidět, že jen z délek a počtu fragmentů restrikční mapu nesestavíme – není jasné, jak fragmenty uspořádat. V praxi se proto používají enzymy dva. Nejdřív DNA naštěpíme prvním, pak druhým a pak oběma současně – to nám znemožňuje uspořádat fragmenty úplně libovolně. Stačí to? Zkuste najít netriviální protipříklad dokazující, že ani v tomto případě nemusí být restrikční mapa jednoznačná. Dá se s tím nějak vypořádat? Zkuste vymyslet jiné metody, jak najít restrikční mapu DNA (pro jeden, nebo pro více restrikčních enzymů).

Jak ale vlastně z fragmentů sestavíme restrikční mapu? Inu, pořídíme si na to nějaký program! Zkuste vymyslet algoritmus, který dostane délky a počty fragmentů a sestaví z nich restrikční mapu. Můžete použít variantu se dvěma enzymy z předchozího odstavce (které se říká Double Digest Problem), nebo nějakou vlastní „stříhací“ metodu. Pokud umíte programovat, můžete svůj algoritmus i naprogramovat a podívat se, jak funguje. K tomu se vám může hodit online nástroj1, kterým si můžete nastříhat DNA nebo rovnou vyrobit restrikční mapu. Pokud byste si chtěli nastříhat nějakou reálnou DNA, můžete využít online databázi DNA2. Nenechte se zastrašit lehce komplikovaným rozhraním obou stránek, časem se na https://mam.mff.cuni.cz/zadani/temata/ objeví návod, jak je používat.

Pokud se s algoritmy a programováním moc nekamarádíte, můžete se zkusit zaměřit na experimentální část mapování. Jak vůbec takové restrikční enzymy fungují a jak poznají, kde mají stříhat? Na jakém principu funguje měření délek fragmentů? Dokážeme nějak poznat, kolik je fragmentů dané délky? A jak přesné ono měření vůbec je? Dá se s nepřesnostmi případně nějak vypořádat?

Napadla-li vás nějaká otázka, která zde nezazněla, nebojte se nad ní zamyslet a něco k ní poslat. Stejně tak se nebojte napsat, pokud potřebujete pomoci třeba se získáním nějakých zdrojů, ke kterým se nemůžete dostat, nebo máte nějaký dotaz.

O(N)dra


1) http://www.restrictionmapper.org/

2) https://www.ncbi.nlm.nih.gov/nucleotide/

Stejně


Téma 3: Mafie jako výpočetní model

Za sedmero horami a sedmero řekami v jednom odlehlém městečku byla mafie. Jak taková mafie vypadá? Skládá se z mafiánů. Žádný mafián samozřejmě z bezpečnostních důvodů nezná všechny ostatní mafiány – každý jich zná jen konstantně mnoho a s těmi si dopisuje. Každý den ráno pošle všem svým známým mafiánům dopis. (Každá dvojice známých mafiánů si tedy každý den pošle dva dopisy – v každém směru jeden.) Všechny dopisy se do večera doručí. Mohli bychom tedy říci, že celá mafie má strukturu souvislého grafu1. Vrcholy odpovídají mafiánům a hrany reprezentují to, zda si daná dvojice dopisuje.

Mafiáni by nyní chtěli zjistit něco o tom, jak ta jejich mafie vypadá – třeba kolik jich je. Jediný způsob, jak něco takového zjistit, je pomocí mafiánů, co se znají a posílají si dopisy. Nejdříve mafiánský boss na předem domluveném místě vylepí algoritmus, který bude popisovat, jak si mají mafiáni posílat dopisy, aby hledanou informaci zjistili. Každý den si pak známí mafiáni mohou vyměnit zprávu. Cílem je, aby na konci každý mafián věděl informaci, na kterou se snažili přijít.

Vymyslete grafové vlastnosti nebo problémy, které by mafiáni mohli řešit, nebo zkuste vyřešit jeden z problémů zmíněných v další části. Určete složitost vašeho algoritmu. Jde nám především o počet dnů, za který v nejhorším případě algoritmus skončí, a součet délek všech zpráv, které si mafiáni vymění. Jak se na každého správného mafiána sluší, má neomezený výpočetní výkon, takže časovou složitost v běžném slova smyslu uvažovat nemusíte. Složitosti můžete vyjadřovat v závislosti na počtu mafiánů, průměru grafu mafie (největší vzdálenost mezi dvojicí mafiánů), nebo si můžete vymyslet svůj vlastní parametr. Složitosti určujte asymptoticky2.

Inspirovat se můžete následujícími problémy:

  • Zjistěte velikost mafie, tedy počet mafiánů, kteří v ní jsou.

  • Mafiáni by chtěli co nejvíce omezit počet dopisů, které pošlou. Rozhodli se proto, že si spolu někteří mafiáni přestanou dopisovat. Najděte co nejvíce dvojic, které si spolu mohou přestat dopisovat tak, aby stále mezi libovolnou dvojicí mafiánů existovala cesta.

  • Mafiáni by chtěli zjistit, jaký je celkový majetek mafie (vyjádřeno v místní měně). Žádný z mafiánů při tom nechce, aby některý jiný mafián zjistil hodnotu jeho majetku.

  • Čas od času potřebuje nějaký mafián o něčem informovat všechny ostatní. To se dělá tak, že předá zprávu všem, se kterými si dopisuje. Každý další mafián pak zprávu přepošle ostatním mafiánům, se kterými si dopisuje (ale jen při prvním přijetí dané zprávy). Zjistěte, jak nejdéle může trvat, než se zpráva dostane ke všem mafiánům.

  • Mafiáni by chtěli vědět, kolik nejméně z nich by muselo být zatknuto, aby se mafie „rozpadla“. Tedy aby pak existovali dva mafiáni, mezi kterými nebude existovat cesta vedoucí pouze přes nezatčené mafiány. Jinými slovy chceme spočítat největší k takové, že graf mafie je k-souvislý. Toto by mohlo být zajímavé už pro k=2. (Věřím, že tento problém je poměrně těžký a možná ani nemá efektivní řešení.)

Kuba


1) Pokud nevíte, co se myslí grafem, doporučujeme přečíst si prvních pár odstavců grafové kuchařky zde: https://ksp.mff.cuni.cz/kucharky/grafy

2) Pokud nevíte, co se tím myslí, doporučujeme přečíst odstavec asymptotická složitost v programátorské kuchařce o složitosti: https://ksp.mff.cuni.cz/kucharky/slozitost/

Stejně