Hladové algoritmy
Zalamování řádků v odstavci s lineární penalizací
Mějme text skládající se z r? slov, šírka /tého slova je w; pixelů. Chceme text vypsat do odstavce tak, aby byl zarovnán do bloku a na každém řádku byly co nejmenší mezery (mezery musí být minimálně 1 pixel). Maximální délka řádkuje m pixelů. Každému řádku kromě posledního je určena penalizace
kde / a j jsou indexy prvního a posledního slova na řádku. Cílem je minimalizovat součet penalizací všech řádků (kromě posledního).
► Na rozdíl od minulého demonstračního cvičení je tentokrát penalizace lineární místo kubické. Dokážeme v tomto případě najít hladový algoritmus?
Nezapomeňte: Nejdůležitější součástí hladového algoritmu je důkaz jeho korektnosti.
j
k=i
Hladové algoritmy
Optimální bezprefixové kódování
Kódovaní množiny symbolů Z je funkce code : Z —> {0,1}*. Kódovaní je bezprefixové, pokud žádný code(u) není prefixem code(v) pro žádná u ^ v. Dejme tomu, že známe četnosti všech symbolů v textu. Chceme najít takové bezprefixové kódování těchto symbolů, které bude minimalizovat celkovou délku zakódovaného textu.
► Jak souvisí bezprefixové kódování s binárními stromy?
Hladové algoritmy
Optimální bezprefixové kódování
Kódovaní množiny symbolů Z je funkce code : Z —> {0,1}*. Kódovaní je bezprefixové, pokud žádný code(u) není prefixem code(v) pro žádná u ^ v. Dejme tomu, že známe četnosti všech symbolů v textu. Chceme najít takové bezprefixové kódování těchto symbolů, které bude minimalizovat celkovou délku zakódovaného textu.
► Jak souvisí bezprefixové kódování s binárními stromy?
► Jaký tvar musí mít každý binární strom, který reprezentuje optimální bezprefixové kódování?
Hladové algoritmy
Optimální bezprefixové kódování
Kódovaní množiny symbolů Z je funkce code : Z —> {0,1}*. Kódovaní je bezprefixové, pokud žádný code(u) není prefixem code(v) pro žádná u ^ v. Dejme tomu, že známe četnosti všech symbolů v textu. Chceme najít takové bezprefixové kódování těchto symbolů, které bude minimalizovat celkovou délku zakódovaného textu.
► Jak souvisí bezprefixové kódování s binárními stromy?
► Jaký tvar musí mít každý binární strom, který reprezentuje optimální bezprefixové kódování?
► Má tento problém optimální substrukturu? Jak vypadají podproblémy?
Hladové algoritmy
Optimální bezprefixové kódování
Kódovaní množiny symbolů Z je funkce code : Z —> {0,1}*. Kódovaní je bezprefixové, pokud žádný code(u) není prefixem code(v) pro žádná u ^ v. Dejme tomu, že známe četnosti všech symbolů v textu. Chceme najít takové bezprefixové kódování těchto symbolů, které bude minimalizovat celkovou délku zakódovaného textu.
► Jak souvisí bezprefixové kódování s binárními stromy?
► Jaký tvar musí mít každý binární strom, který reprezentuje optimální bezprefixové kódování?
► Má tento problém optimální substrukturu? Jak vypadají podproblémy?
► Navrhněte hladový přístup a dokažte, že je korektní.
Hladové algoritmy
Protínání intervalů
Mějme množinu X (uzavřených) intervalů na číselné ose; intervaly mohou být různých délek a jsou zadány svými levými a pravými krajními body. O množině čísel X řekneme, že protíná množinu intervalů I, pokud každý interval z I obsahuje alespoň jedno číslo z X. Chceme najít minimální množinu X, která protíná I.
► Navrhněte hladový přístup a dokažte, že je korektní.
Hladové algoritmy
Barvení intervalů
Mějme opět množinu (uzavřených) intervalů Z. Nekonfliktní obarvení intervalů z I přiřadí každému intervalu barvu tak, že žádné dva intervaly se stejnou barvou nemají společný průnik. Chceme najít nekonfliktní obarvení s co nejmenším počtem barev.
► Navrhněte hladový přístup a dokažte, že je korektní.
Backtracking
Všechny /etice (variace s opakováním)
Mějme dána přirozená čísla n a k. Napište pseudokód (rekurzivního) algoritmu, který vypíše na výstup všechny /etice čísel z {1,2,n}.
Backtracking
Permutace
Mějme dáno přirozené číslo n. Máme napsat algoritmus, který vypíše všechny permutace čísel z {1, 2,n}.
► Jak můžeme využít algoritmus z minulého slajdu?
Backtracking
Problém n královen
Mějme dáno přirozené číslo n. Chceme umístit n šachových figur královen na šachovnici o rozměrech n x n tak, aby se žádné dvě z nich vzájemně neohrožovaly.
► Jak nám pomůže algoritmus z minulého slajdu?
Backtracking
Kombinace (bez opakování)
Mějme dána přirozená čísla n a k. Chceme vypsat všechny /cprvkové kombinace čísel z {1,2,n}, tj. všechny /cprvkové podmnožiny této množiny.
Backtracking
Klika
Mějme neorientovaný graf G — {V ^ E). Klikou v grafu nazveme každou podmnožinu K C V takovou, že podgraf indukovaný vrcholy z K je úplný.
► Mějme zadáno číslo k. Chceme zjistit, jestli G obsahuje kliku velikosti k. Jak můžeme modifikovat některý z dříve uvedených algoritmů?
Backtracking
Klika
Mějme neorientovaný graf G — {V ^ E). Klikou v grafu nazveme každou podmnožinu K C V takovou, že podgraf indukovaný vrcholy z K je úplný.
► Mějme zadáno číslo k. Chceme zjistit, jestli G obsahuje kliku velikosti k. Jak můžeme modifikovat některý z dříve uvedených algoritmů?
► Chceme zjistit, jakou největší kliku G obsahuje. Jak můžeme modifikovat předchozí algoritmus tak, abychom dostali co nejefektivnější řešení?