Nahoru:

Knihovna: Informatická témata

Podkategorie v této kategorii:

Články v této kategorii:

Finále soutěže ACMPDF(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íkAutor: Filip HlásekDatum: 2016 Hojsova Stráž
Komunikace přes nezabezpečený kanálPDF(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íkAutor: Filip HlásekDatum: 2015 Sklené
Konečné projektívne roviny a latinské štvorcePDF(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íkAutor: Peter „πtr“ KorcsokDatum: 2012 Domašov
Lineární programování a aproximační algoritmyPDF(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íkAutor: Štěpán ŠimsaDatum: 2016 Hojsova Stráž
Minimální kostryPDF(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íkAutor: Štěpán ŠimsaDatum: 2017 Meziměstí
MOPPDF(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íkAutor: 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íkAutor: Jakub „Roman“ KlemsaDatum: 2012 Domašov
Relace, operace a splnitelnost podmínekPDF(99KB) 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íkAutor: Mirek OlšákDatum: 2015 Staré Město
SložitostPDF(104KB) 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íkAutor: Filip HlásekDatum: 2015 Staré Město
Sto vězňů a žárovkaPDF(109KB) 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íkAutor: Filip HlásekDatum: 2014 Zásada
Toky v sítích, Hallova větaPDF(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íkAutor: Vít "Vejtek" MusilDatum: 2010 Domaslav

Kontakt

email mks (zavináč) mff.cuni.cz
pošta Korespondenční seminář
KAM MFF UK
Malostranské náměstí 25
118 00   Praha 1

Organizátoři

mff

Matematický korespondenční seminář je organizovaný studenty Matematicko-fyzikální fakulty UK pod záštitou Informatického ústavu UK a Oddělení pro vnější vztahy a propagaci UK.

Partneři

pix