Sedmé setkání Pražského informatického semináře proběhne 23. října 2014 od 16 hod. v posluchárně KN:E-107, FEL ČVUT, Karlovo nám.13, Praha 2.
Přednášku na téma Matematika a rychlé algoritmy přednese prof. Daniel Kráľ.
Anotace: Metody z kombinatoriky, logiky a dalších oborů matematiky nacházejí stále více aplikací v různých oblastech informatiky. Jednou z oblastí, kde se matematické metody často využívají, je návrh efektivních algoritmů a datových struktur. Nicméně řada důležitých algoritmických problémů je těžká z hlediska výpočetní složitosti a proto je nepravděpodobné, že by je bylo možné efektivně vyřešit v plné obecnosti. Jeden z přístupů k řešení takových problémů je založen na omezení jejich těžkosti vhodnou parametrizací, např. omezením struktury vstupních dat nebo logickou složitostí uvažovaných typů problémů.
V úvodu přednášky předvedeme využití matematických metod v návrhu algoritmu pro vybraný konkrétní problém. Tohoto příkladu využijeme k zavedení pojmů, které se vyskytují v oblasti parametrizované složitosti, a představíme základní výsledky z této oblasti. Na závěr zmíníme několik obecných výsledků založených na poznatcích z kombinatoriky a logiky, které zaručují existenci efektivních algoritmů a které se souhrnně označují jako algoritmické metavěty.
Žádné komentáře:
Okomentovat