| Finále soutěže ACM | PDF(75KB) PNG |
| Tento příspěvek je věnován úlohám, které se vyskytly na světovém finále soutěže ACM-ICPC konaném v marockém městě Marrákéš od 15. do 20. května 2015. Při řešení několika z nich bylo užitečné využít matematické znalosti a odhalit zajímavé zákonitosti. Přesně na ty úlohy se podíváme a pokusíme se je vyřešit. |
| Zdroj: sborník | Autor: Filip Hlásek | Datum: 2016 Hojsova Stráž |
| Komunikace přes nezabezpečený kanál | PDF(45KB) PNG |
| Tento text je volným pokračováním mého příspěvku 100 vězňů a žárovka. Budeme uvažovat dva subjekty, které se snaží tajně si předat zprávu. Všechna jejich komunikace je sice odposlouchávána, ale naštěstí jsou informace doručeny v neporušeném stavu. |
| Zdroj: sborník | Autor: Filip Hlásek | Datum: 2015 Sklené |
| Konečné projektívne roviny a latinské štvorce | PDF(84KB) PNG |
| V tejto prednáške sa zoznámime s konceptom konečných projektívnych rovín a latinských štvorcov a ukážeme si, ako tieto objekty navzájom súvisia. V druhej časti prednášky si predstavíme ich aplikáciu pri takzvaných samoopravných kódoch. Tieto kódy sa využívajú pri prenose informácií menej spoľahlivým spôsobom, kde môže dochádzať k zmene niektorých z prenášaných znakov. |
| Zdroj: sborník | Autor: Peter „πtr“ Korcsok | Datum: 2012 Domašov |
| Lineární programování a aproximační algoritmy | PDF(82KB) PNG |
| Příspěvek se věnuje dvěma informatickým tématům, lineárnímu programování a aproximačním algoritmům, jejichž výsledky se často používají v praxi. Přestože je lineární programování důležité především pro informatiky, jedná se o matematický problém. Aproximační algoritmy jsou často založené právě na lineárním programování, a proto na sebe tato dvě témata navazují. Přestože aproximační algoritmy jsou tématem nesporně informatickým, často bývá obtížnější dokázat, že daný algoritmus je skutečně aproximační, než algoritmus vymyslet. |
| Zdroj: sborník | Autor: Štěpán Šimsa | Datum: 2016 Hojsova Stráž |
| Minimální kostry | PDF(90KB) PNG |
| Cílem příspěvku je seznámit s tématem minimálních koster, konkrétně s teoretickými základy, algoritmy a jejich analýzou. |
| Zdroj: sborník | Autor: Štěpán Šimsa | Datum: 2017 Meziměstí |
| MOP | PDF(48KB) PNG |
| I když MO-P znamená Matematická olympiáda, kategorie programování, k jejímu (úspěšnému) řešení není třeba umět programovat. Každé kolo je alespoň z části teoretické, přičemž teoretické úlohy jsou rozhodně blíže úlohám z matematické olympiády než nějaké práci s počítačem. Na přednášce si ukážeme, jak se dostat do celostátka MO-P jen s minimem práce. |
| Zdroj: sborník | Autor: Matěj Konečný | Datum: 2015 Sklené |
| Redundantní číselné soustavy pro pokročilé | PDF(74KB) PNG |
| Problém, jak zapisovat čísla, se táhne s lidstvem od nepaměti. Dnes známý poziční zápis, kdy stejný symbol (např. „5“) použitý na různých místech umožňuje zapsat jednou pět, jednou padesát, byl podmíněn vynálezem symbolu „0“ pro „nic“. Každému je jasné, že úloha vynásobení čísel 42 a 27 zapsaných v desítkové soustavě je jednodušší, než násobení XLII a XXVII zapsaných římským způsobem. Přesto se desítkový zápis prosadil v Evropě až ve 13. století. I dnes má smysl číselné soustavy zkoumat. Jejich renesance přišla s nástupem procesorů – důvodem byla potřeba vyvinout algoritmus pro paralelní sčítání. |
| Zdroj: sborník | Autor: Jakub „Roman“ Klemsa | Datum: 2012 Domašov |
| Relace, operace a splnitelnost podmínek | PDF(60KB) PNG |
| V informatice lidi často zajímá, zda je možné najít řešení nějaké úlohy inteligentněji než tupým zkoušením všech možností (přesněji zda existuje polynomiální algoritmus). Zde se budeme obecně věnovat úlohám typu "dají se zvolit za x1,..., xn čísla z dané konečné množiny tak, aby byly splněny všechny předepsané podmínky?" Přitom pro studium jednoduchosti podmínek (relací) se ukáže praktické studovat operace, které jsou s nimi "kompatibilní". |
| Zdroj: sborník | Autor: Mirek Olšák | Datum: 2015 Staré Město |
| Složitost | PDF(71KB) PNG |
| Příspěvek popisuje dva základní koncepty teoretické informatiky, Turingovy stroje a složitost. Kromě definic důležitých pojmů uvádí také několik souvisejících tvrzení, vět a cvičení. |
| Zdroj: sborník | Autor: Filip Hlásek | Datum: 2015 Staré Město |
| Sto vězňů a žárovka | PDF(89KB) PNG |
| Příspěvek se zamýšlí nad známým komunikačním problémem, kde se agenti (vězni) pomocí jednoduchého média (žárovky) a lokálních změn systému (přepnutí žárovky) snaží předat globální informaci týkající se jich všech. Na první pohled je až neuvěřitelné, že lze úlohu vůbec vyřešit. Když vězeň vidí svítící žárovku, neví, kdo ji rozsvítil; pokud se rozhodne zhasnutou žárovku rozsvítit, neví zase, kdo ji poté uvidí svítit. Přesto ukážeme, že pomocí takto jednoduchého komunikačního prostředku lze navrhnout protokol k přenosu mnoha informací. |
| Zdroj: sborník | Autor: Filip Hlásek | Datum: 2014 Zásada |
| Toky v sítích, Hallova věta | PDF(83KB) PNG |
| Cílem přednášky je seznámit se základními definicemi a poznatky týkajících se toků v sítích a problému hledání maximálního toku. Další část přednášky se zabývá párováním a důkazem Hallovy věty pomocí aplikace poznatků o tocích. |
| Zdroj: sborník | Autor: Vít "Vejtek" Musil | Datum: 2010 Domaslav |
