zmena dijkstry na odpovidajici slozitost

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Odpovědět
vena

zmena dijkstry na odpovidajici slozitost

Příspěvek od vena »

A jsem tu zas: v zapiscich od Lenky i Anji je zmena dijkstry na slozitost O(nk + m) a posleze O((n+m)k) popsana velice stroze. Muze se prosim nekdo podelit o to, jak to chape on a nesetrit mistem :D ? Diky
Nahoru
df
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 5. 6. 2006 11:55

Re: zmena dijkstry na odpovidajici slozitost

Příspěvek od df »

je to priklad ze cviceni, melo by byt na wiki ( Dijkstra s omezenou váhovou funkcí),
prvni moznost byla tusim nejaky kruhovy pole spojacku

druha moznost pak nad tim kruhovym polem (delky k) postavit jeste haldicku binarni
Nahoru
Odpovědět

Zpět na „TIN062 Složitost I“