How Approximate Algorithms Work

Written by

Jiří Skála

University of West Bohemia

Seminar in Czech
April 15, 2009 at 9:30
University of West Bohemia, UK417

Download

presentation slides (742kB PDF)

Abstract

(download in PDF)

Už jste asi zjistili, že ne všechny problémy jdou vyřešit lehce. Některé jsou složité ze své podstaty, jako například NP problémy, a není pro ně znám efektivní algoritmus. Existují ale i jednoduché úlohy, jako třeba řazení, které mohou představovat problém. Máme-li dat velmi mnoho nebo potřebujeme-li výsledek extrémně rychle, běžné algoritmy na to nestačí.

Avšak ne vždy potřebujeme přesný výsledek. Často nám postačí i přibližné řešení ? takové, které dávají přibližné algoritmy.

V nadcházející přednášce si povíme, co je to přibližný algoritmus a jak se liší od obyčejné heuristiky. Uvidíme, že přibližné algoritmy nejsou jen hračkou grafových teoretiků, ale že mají i praktické uplatnění. Následně se podrobněji podíváme na dvě konkrétní úlohy ? přibližné řazení a triangulace s minimální vahou.