Nutnou a postačující podmínkou k získání zápočtu z předmětu Teorie grafů je vypracování semestrální práce.  
Student si může podle svých preferencí vybrat tyto typy práce:

A: prezentace některé kapitoly teorie grafů, která nebyla probrána na standardních přednáškách, nebo
B: implementace některého z algoritmů, které byly probrány, nebo
C: vlastní téma.

Možná témata prací najdete na zvláštní stránce.

Formální požadavky společné pro všechny typy prací

• Práce musí být napsaná nebo prezentovaná česky nebo slovensky.
• Pokud máte opravdu velké problémy s češtinou, můžeme se individuálně domluvit na vypracování v angličtině.
• Odevzdané materiály budou jednom z v následujících formátů:
  • textové materiály (doprovodný text k prezentaci, programová dokumentace a pod.) ve formátu PDF,
  • zdrojový kód programu/funkce v nativním formátu příslušného jazyka (pro Matlab m-file, pro C/C++ soubor C, CPP nebo C++, případně H, pro Python PY, atd.),
  • případné zvlášť přiložené obrázky ve formátu PDF nebo PNG,
  • prezentace nejraději v PDF, nebude-li to možné, pak PPT,
  • bude-li vhodné data zkomprimovat, pak použijte formát ZIP nebo GZ.
  • Nebudu otvírat, číst, rozbalovat, dešifrovat a otravovat se s žádnými docx, rar, ani s miliónem dalších formátů.

Jak má vypadat semestrální práce typu A - prezentace

Předmětem semestrální práce tohoto typu je nastudování a zpracování některé kapitoly teorie grafů, která nebyla probrána na standardních přednáškách.

Prezentace bude zahrnovat

• zasazení tématu do kontextu předmětu (na kterou kapitolu navazuje nebo s ní souvisí); pokud jde o vzdálenější téma, které s dosud probranými nesouvisí, teno bod odpadá,
• motivaci (k čemu je to dobré nebo proč je to zajímavé),
• teoretický úvod - musí být věcně správný a matematicky korektní, složitější důkazy nemusejí být uvedeny,
• jedná-li se o úlohu teorie grafů, pak přesná formulace této úlohy, případně jejích variant,
• jedná-li se o úlohu teorie grafů, pak přístupy k jejímu řešení, popřípadě obtížnost, algoritmus a pod.,
• pokud se o úlohu teorie grafů nejedná (nějaké popisné téma), postupujte podle toho, co si téma žádá,
• nějaký příklad (nebo příklady),
• cokoliv zajímavého, na co narazíte.

Student bude práci prezentovat na semináři (osobně nebo on-line). Můžete mít připravený text prezentace, který budete promítat, je možné použít i tabuli nebo obojí kombinovat. Pokud chcete mluvit spatra, připravíte si písemně zpracované téma prezentace v odpovídajícím rozsahu. Prezentace musí být srozumitelná, jasná a konzistentní a bude trvat přibližně 30-40 minut. Případné animace, příklady z praxe a jiné atrakce jsou vítány.

Student kromě toho dodá vyučujícímu

• připravenou prezentaci, kterou promítal na semináři, nebo
• písemně zpracované téma prezentace v odpovídajícím rozsahu.

Jak má vypadat semestrální práce typu B - algoritmus

Semestrální práce, která implementuje daný algoritmus, musí obsahovat tyto náležitosti:

• Program, proceduru nebo funkci, která provádí požadovaný algoritmus. Při použití Matlabu to znamená jednu m-funkci, která může využívat volání dalších pomocných m-funkcí. (Budete-li používat C/C++, napište i program main, který bude danou funkci volat, případně makefile a cokoliv bude potřeba.) (Při použití jiného programovacího jazyka postupujte analogicky - je nutné dodat kompletní funkční řešení.) Tento kus software musí fungovat a produkovat správné výsledky. Měl by mít také přiměřenou štábní kulturu. Zdrojový kód musí být přiměřeně zdokumentovaný, tj. minimálně stručný popis jeho funkce (co to dělá), specifikaci vstupů a výstupu, okomentované významy hlavních proměnných, jméno autora atd.
• Doprovodnou dokumentaci, která obsahuje
  • Úvodní část
    • jméno autora, téma práce,
    • zadání práce - tj. co jakou úlohu má program řešit,
    • použitý algoritmus - stačí název algoritmu, který se probíral v předmětu Y1TG nebo 17TGA s případným  upřesněním jeho varianty a popisem modifikací, nebo odkaz na literaturu a stučný popis algoritmu. Pokud algoritmus vynaleznete sami, je zapotřebí jej popsat podrobně a případně dokázat jeho správnost.
  • Část týkající se samotné implementace
    • přesný a jednoznačný popis vstupu, a to jak formálně (formát vstupních dat), tak sémanticky (co vstupní data reprezentují a jaký typ grafu funkce požaduje)
    • přesný a jednoznačný popis výstupu,
    • výpis samotné funkce (případně použitých pomocných funkcí)
    • způsob volání funkce/programu
    • popis omezení funkce/programu - tj. požadavky na další vlastnosti vstupu (např. velikost dat, souvislost grafu, nezápornost ohodnocení, ...) a popis toho, co funkce/program nedělá, i když by někdo očekával, že to dělat má. (To neznamená, že by například funkce na hledání minimální kostry našla prostě nějakou kostru, vy jste napsali do dokumentace, že minimální kostru nehledá a byli jste z obliga. Jedná se o záležitosti, které v rámci dělby práce mezi částmi kódu obvykle dělá někdo jiný - například výpisy, kontrola správnosti vstupních dat a podobně.)
  • Protokol o testování
    • několik (3-5) testovacích příkladů menšího rozsahu (do 10 vrcholů).
      Dobře zvolené příklady testují, jestli funkce opravdu dělá, co má, a co slibuje její popis. Nejsou úplně triviální a zahrnují všechny neobvyklé, vyjímečné a krajní případy, které vás napadnou. Například nesouvislý graf, neexistence hledaného objektu (cesty, párování, ...), existence více hledaných objektů, divný požadavek (najdi cestu z vrcholu v do vrcholu v), ...
    • ke každému příkladu bude uvedeno zadání (obrázek grafu; stačí nakreslený od ruky), vstupní data (tj. popis grafu, který je vstupem pro program), výpis výsledku a zhodnocení, jestli je výsledek v pořádku.
  • Ukázku použití.
    Nějaký hezký příklad, na kterém lze ukázat, jak je váš prográmek šikovný a co všechno umí. Rozhodně by měl být trochu větší, než testovací příklady (15 - 25 vrcholů); záleží na tom, jaký typ úlohy řešíte. Graf by měl být co nejobecnější, jaký vaše funkce zvládne - pokud například umíte najít nějakou cestu v ohodnoceném grafu, který obsahuje cykly záporné délky, pak nemá smysl demonstrovat vaše umění na acyklickém grafu s nezáporně ohodnocenými hranami.
  • Závěr - pokud zjistíte něco zajímavého, napište to sem. Můžete také napsat, jak by se dal program vylepšit a jestli byste to zvládli. Jinak stačí zkonstatovat, že program funguje.
• Výsledky ukázkového příkladu.

Aby se vám dokumentace snáze psala, podívejte se na vzorovou práci.