Zadání práce

V zadání byste měli napsat dvě základní věci.

Jaký problém budete studovat.
Co se zvoleným problémem budete dělat.

Popis problému

S vedoucím práce jste se již domluvili na problému, který chcete studovat a už byste na něm chtěli pracovat, ale stejně je nutné nejprve problém napsat. Sepsání problému před započetím práce slouží k tomu, abyste si s vedoucím ujasnili, že jste se spolu správně na konzultaci pochopili. Dále je užitečný pro vedoucího (a někdy i pro studenta), aby si mohl rychle připomenout, kterou přesnou variantu problému máte studovat, zejména když vedoucí má více studentů a někteří se rozhodnou celé léto se věnovat jiným aktivitám. Nakonec stejně bude nutné popis problému napsat do textové části práci, tak proč jej nenapsat hned.

Přesné popsání problému bývá pro studenty nelehký úkol a neexistuje něj universální postup. Začněme jednou základní radou: snažte se při popisu používat nástroje, které jste slyšeli na přednáškách nebo četli v odborné literatuře.

V naprosté většině problémů se vyskytuje nějaká množina, ať už se jedná skupinu lidí, měst, dní, přednášek, aut nebo dinosaurů. Zaveďte tedy jedno písmenko pro každou množinu, kterou budete používat.
Jednotlivé prvky množiny nejspíše mají nějaké vlastnosti, tak je vhodné každou vlastnost označit písmenkem. Například můžete napsat, že každý člověk c z množiny lidí L má výšku h_c, váhu w_c a barvu očí b_c z množiny všech barev B.
Pokud řešíte nějaký přepravní problém, tak je dobré popis začít tím, že máte graf, u kterého popíšete, co jsou vrcholy a co hrany. Opět nějakým písmenkem označíte graf, jiným množinu vrcholů a dalším množinu hran. Dalšími pismenky označíte různé parametry pro vrcholy a hrany (například délka nebo kapacita hrany, pozice vrcholu). Pojem graf se vám může hodit nejen u hledání nejkratší cesty nebo maximálního toku, ale i při analýze počítačové sítě nebo vztahů mezi lidmi.
Podobně můžete zavést matici vzdáleností bydlišť všech dětí do všech škol.

Takto byste měli popsat vstup vašeho problému. Při pojmenovávání a značení různých objektů je vhodné se držet zvyklostí v daném oboru, protože to čtenářům velmi zjednodušuje porozumění textu. Proto si přečtěte pár článků o podobných problémech a zbytečně nevymýšlejte nové názvy.

Poté je nutné popsat, co je řešením vašeho problému.

Při řešení problému batohu hledáte podmnožinu N z množiny všech prvků M. Můžete též použít charakteristický vektor x, kde x_i je rovno 1, jestliže i z M je vybrán a jinak je rovno 0. Záleží jen na vás, co se vám bude v dalším textu hodit.
Při hledání Hamiltonovské kružnice hledáte permutaci všech vrcholů.
V úloze maximálního toků hledáte vektor f, který pro každou hranu e z E určuje velikost toku f_e.

Dále je popíšete, jaké podmínky musí splňovat přípustné řešení. Například v problému batohu nesmíme překročit kapacitu, při hledání toku zachovat kapacity a Kirchhoffův zákon a při hledání perfektního párování musí nalezená podmnožina hran pokrýt každý vrchol právě jednou. Tyto podmínky je možné popsat slovy nebo matematickými formulacemi. V nejsrozumitelnějším textu je napsáno obojí.

Nakonec ještě uvedete, jakým způsobem zjišťujete, které je lepší než jiné. Nejčastější postup je napsat cílovou funkci nebo fitness, který každé řešení ohodnotí jedním reálným číslem (ve vícekriteriální optimalizaci vektorem). Jiným postupem je popsat, jak porovnat dvě řešení (například lexikografické uspořádání).

Proč je nutné problém popsat tak přesně?

Většina studentů má pocit, že se vyjadřují naprosto přesně. Toto je bohužel pravda, dokud svůj text nedají přečíst někomu jinému. V matematických textech není důležité, aby jej šlo pochopit tak, jak zamýšlel autor, ale aby jej nešlo pochopit jinak. Nepřesnost zadání úloh je často důvodem, proč studenti (a někdy i vyučující) nemají rádi kombinatoriku a pravděpodobnost na střední škole. Má-li například spočítat počet různých výběrů k objektů z n možných, tak je důležité, jestli

jsou objekty rozlišitelné nebo jsou stejné
při rozlišitelnosti objektů máme z každého typu jen jeden exemplář nebo máme více stejných exemplářů
záleží na pořadí výběru nebo nebo ne

Pokud se tyto drobné rozdíly ztratí v jazykové formulaci, tak čtenář nemusí autora pochopit a o práci ztratit zájem.

Pěkný příklad záludnosti nepřesných matematických formulací ukazuje Bertrandův paradox, který se ptá, jaká je očekávaná délka náhodné tětivy kružnice. Bertrand již v roce 1889 ukázal tři možné řešení této otázky v závislosti na pravděpodobnostním prostoru, ze kterého je tětiva vybrána.

Přínos práce

Po popsání problému, který budete studovat, napíšete, co s ním budete dělat. Připadá vám zjevné, že jej přeci budete řešit? To je samozřejmé, ale není jasné, jakými metodami jej budete řešit, a co dalšího s problémem budete dělat.

Nyní nejspíš nevíte, jaké algoritmy budou na problém dobře fungovat. Ale zjistit, jak je který algoritmus dobrý, je cílem práce. Zamyslete se nad tím, kterými algoritmy má smysl problém řešit, a vyzkoušíte je.

Kromě implementace algoritmu můžete v závislosti na konkrétním problému potřebovat vyřešit další věci.

Získání testovacích dat

Algoritmy je nutné spustit na nějakých datech. Jak je získat záleží na konkrétním problému. Na některé problému můžete najít standardní, často používané datasety. U některých problémů je nutné dataset vytvořit samostatně. Též je možné část dat vzít z datasetu a zbytek si vytvořit.

Testovací data je možné vytvořit celá náhodným generátorem nebo využít dostupná data.

Pokud řešíte dopravní problém, tak si můžete z Open Street Map stáhnout silniční síť nějaké oblasti.
Můžete se podívat na data, který dává k dispozici magistrát Prahy.
Mendeley: Repositář otevřených vědeckých dat.
Google dataset search: Vyhledávač dat pro testování.
Kaggle: Různé datasetu, vědecké soutěže a příklady řešení problémů zejména ve strojovém učení.

Simulátor a fitness

V kombinatorických úlohách (například problém batohu nebo obchodního cestujícího) je naprogramování výpočtu fitness funkce triviální. Ale při optimalizaci řízení výtahového systému budete potřebovat jeho simulátor. K návrhu mostu budete potřebovat analyzovat nosní konstrukci. Při vytváření efektivnějšího křídla letadla se neobejdete bez výpočtu dynamiky plynů.

Vizualizace

K odladění programu se velmi hodí vědět, jak vypadá vstup, výstup a řešení průběžných mezivýpočtů, abyste věděli, co program dělá. K vizualizaci můžete využít různé nástroje. Nejspíš jste si hned představili klasické GUI, které například při řízení výtahů postupně zobrazuje, kde je který výtah, kam jede a koho veze. Ale to není jediná cesta. Mnohem jednodušší je vstup nebo výstup exportovat do vhodného formátu, který vám šikovný program pěkně zobrazí, a celou vizualizaci tak můžete mít na pár desítek řádků kódu.

Pokud pracujete s grafy, tak se vám může hodit jazyk dot, ve kterém vypíšete vrcholy a hrany s potřebnými vlastnostmi, a Graphviz vám jej zobrazí.
K zobrazení měst, zastávek, silniční sítě a dalších geografických dat můžete jednotlivé objekty exportovat jako body, úsečky nebo lomené čáry do formátu GeoJSON, který můžete zobrazit například v programu QGIS nebo ve webovém prohlížeči.

Můžu použít existující knihovny nebo musím vše napsat sám?

Záleží na vás, co se chcete naučit a vyzkoušet si. Cílem práce může být implementace simulátoru výtahu i s přehlednou vizualizací, na kterém strávíte celý rok, a poté vyzkoušíte jednoduchý algoritmus na jeho řízení. Nebo si simulátor stáhnete a implementujete několik zajímavějších řídících algoritmů. Volba je na vás, ale musíte předem říct a napsat, jaké budou vaše cíle, co v práci uděláte a na co použijete existující nástroje. Vedoucí práce podle vašich návrhů zváží, jestli rozsah práce je přiměřený. Pokud použijete existující simulátor a k řízení jen testovací data nasypete do scikit-learn, tak práce bude v rozsahu jednoho domácího úkolu na strojové učení. Pokud byste si chtěli simulátor i neuronovou síť napsat sami, tak to v bakalářské práci nestihnete.