Жадные алгоритмы аппроксимации: различия между версиями

Жадные алгоритмы аппроксимации (посмотреть исходный код)

95 байт добавлено , 23 апреля 2015

м

4430

правок

@@ Строка 72: / Строка 72: @@
 <math>f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>\le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>= f(C) - f(C \cap D)</math>.
+Если функция f является монотонно возрастающей, то <math>A \subseteq B \;</math> влечет <math>f(A) \le f(B)</math>. Следовательно, для <math>x \in B \;</math>,
+<math>\Delta_x f(A) \ge 0 = \Delta_x f(B)</math>.
-Если функция f является монотонно возрастающей, то для ACB f(A) < f(B). Следовательно, для x 2 B,
-A)xf{A) > 0 = Axf(B) :
 Напротив, если Axf(A) > Axf(B) для любого x 2 B и А С B, тогда для любых x и A, Axf(A) > Axf(AU{x}) = 0, то есть f(A) < /(A U xg). Пусть B - A = fx 1..: ; xk g. Тогда
 f(A) </(AU