Oct 23, 2014
Mathematical methods, in particular those coming from combinatorics and logic, find applications in various areas of computer science. An area where such methods are often used is algorithm and data structure design. However, many important algorithmic problems are hard in the sense of computational complexity and it is unlikely that they can be efficiently solved in full generality. One of the approaches to cope with this is based on restricting the hardness by an appropriate parameterization, e.g., by restricting the structure of input data or the logic complexity of considered problems. The lecture will start with a demonstration how mathematical methods can be used to design an algorithm for a particular problem. The case study presented will be used to introduce concepts from the parameterized complexity and some of the basic results in this area. At the end of the lecture, we will give several general results that were proved using methods from combinatorics and logic. These results known as algorithms metatheorems guarantee the existence of efficient algorithms for a wide range of algorithmic problems.
Seminář se bude scházet vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí. Jeho program bude tvořen hodinovou přednáškou, po níž bude následovat časově neomezená diskuse. Základem přednášky by mělo být něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky budou standardně v angličtině. Formát semináře připravil přípravný výbor ve složení Roman Barták (MFF UK), Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT) Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.
Professional recording and live streaming, delivered globally.
Presentations on similar topic, category or speaker