Abstrakt
Teorie diskrepance zkoumá nepravidelnosti rozložení. Typická otázka zní: k danému “komplikovanému” rozložení najít "jednoduché", které jej dobře aproximuje.
Ukazuje se, že mnohé otázky teorie složitosti se dají zredukovat na problémy tohoto typu. Tím pádem by mohlo by teoretická informatika mohla využít složité matematické nástroje teorie diskrepance.
Ukážeme několik převratných výsledků získaných pomocí “diskrepančních metod”. Upravené 2. vydání.