Matematické Fórum

Dobry den, mam problem popsany nize a chtel bych Vas snazne poprosit o pomoc s dukazem mat. indukci.

Název problému: Výběr aktivit
Vstup: množina konečně mnoha aktivit {1, 2, . . . , n} s pevně určenými časovými
intervaly (s1, f1), (s2, f2), . . . , (sn, fn), kde (∀i, 1 ≤ i ≤ n) : si < fi
Výstup: množina obsahující největší možný počet vzájemně kompatibilních aktivit (tj. aktivit s vzájemně se nepřekrývajícími intervaly)

Jak dokazat tento pseudoalgoritmus?
Výběr-Aktivit(n, s, f)
 předp., že poč. časy jsou již v poli s a konc. časy v poli f
 dále předp. f[1] ≤ f[2] ≤ . . . f[n], kde n představuje počet aktivit
A ← {1}; j ← 1
for i ← 2 to n
do if s[i] ≥ f[j]
then A ← A ∪ {i}; j ← i
return A
V uvedeném případě je důkaz faktu, že hltavý přístup skutečně vede k opti-
málnímu řešení, celkem snadný. (Indukcí podle počtu aktivit n.)

Mockrat dekuji, Honza