Matfyz Wiki

Zkouska 3.2.

vexis at 2010-02-03 18:08:18

Zadani z dnesni pisemky:

  1. Aho-Corasick

  2. 2-aproximační algoritmus batohu, kdyz plati trojuhelnikova nerovnost

  3. najit vsechny pruseciky parabol ax<sup>2</sup> + bx + c = 0 kde a >0 (postup vpodstate stejny jako u usecek akorat pro poloviny parabol)

  4. pokryt vykousanou sachovnici dominovymi kostkami (prevedeme na problem perfektniho parovani -> pridame zdroj a stok a kapacity 1 -> najdeme maximalni tok)