Здравствуйте.
Булева ф-я f(x1...xk) задана вектором своих значений (битвектором длины 2^k)).
Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
Как проверить на монотонность? (т.е. "неубываемость"?)

U>Здравствуйте.
U>Булева ф-я f(x1...xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. "неубываемость"?)

Для действительной функции двух и более переменных нет понятия монотонность.
Что такое монотонность для булевой функции нескольких переменных, это ещё более загадка.
думаю нужна переформулировка задачи.

Здравствуйте, Аноним, Вы писали:

U>>Здравствуйте.
U>>Булева ф-я f(x1...xk) задана вектором своих значений (битвектором длины 2^k)).
U>>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>>Как проверить на монотонность? (т.е. "неубываемость"?)

А>Для действительной функции двух и более переменных нет понятия монотонность.
А>Что такое монотонность для булевой функции нескольких переменных, это ещё более загадка.
А>думаю нужна переформулировка задачи.

а. оказывается есть монотонность для булевой:
http://ru.wikipedia.org/wiki/Булева_функция
это если в дизъюнктивной нормальной форме нет отрицаний переменных.
Но непонятно, это ли имелось ввиду . так как слово неубываемость тут вроде не к месту.

U>Булева ф-я f(x1...xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. "неубываемость"?)

По одному проходу для каждой переменной (при этом максимизируется "локальность" обращений к массиву).
Что-то вроде:

bool is_monotonic(const std::vector<bool>& vec)
{
  size_t shift = vec.size();
  if ((shift - 1) & shift) {
    // vector size is NOT a power of 2, bailing out
    return false;
  }
  while ((shift /= 2) > 0) {
    size_t i = 0;
    while (i < vec.size()) {
      for (size_t j = shift; j--; ++i)
        if (vec[i] > vec[i + shift]) {
          // monotonicity is violated
          return false;
        }
      }
      i += shift;
    }
  }
  return true;
}

Здравствуйте, ultrator, Вы писали:

U>Булева ф-я f(x1...xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. "неубываемость"?)

Решение за O(2^k * k)

Функция монотонна, когда выполняется условие
f(xxx0xxx) <= f(xxx1xxx)
То есть, если для каждого вектора X мы получим множество векторов {X'} таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X)<=f(X')...
Беда в том, что для O=000...0 множество таких векторов — это все остальные.
Что делать?

А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).
Ибо,

Например, k=3.
Проверив, что
f(000)<=f(100),
f(000)<=f(010),
f(000)<=f(001),
затем
f(100)<=f(110) — из этого следует, что f(000)<=f(100)<=f(110)
f(100)<=f(101) — из этого f(000)<=f(101)
и ещё позже
f(010)<=f(011) — из этого f(000)<=f(011)
f(110)<=f(111) — из этого f(000)<=f(111)

То есть, по индукции мы охватим всё множество.

Интересно, можно ли быстрее?

К>А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).
К>Например, k=3.
К>Проверив, что
К>f(000)<=f(100),
К>f(000)<=f(010),
К>f(000)<=f(001),


код выше именно это и делает. Только порядок циклов у него другой -- если сгруппировать эти сравнения так как выше, то доступ в массив будет не очень локален/линеен, поэтому нужно делать по проходу на каждую переменную.
То есть порядок проверок такой:
проход 1
f(000)<=f(100)
f(001)<=f(101)
f(010)<=f(110)
f(011)<=f(111)
проход 2
f(000)<=f(010)
f(001)<=f(011)
f(100)<=f(110)
f(101)<=f(111)
проход 3
f(000)<=f(001)
f(010)<=f(011)
f(100)<=f(101)
f(110)<=f(111)

Здравствуйте, Кодт, Вы писали:

К>Функция монотонна, когда выполняется условие
К>f(xxx0xxx) <= f(xxx1xxx)
К>То есть, если для каждого вектора X мы получим множество векторов {X'} таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X)<=f(X')...
К>Беда в том, что для O=000...0 множество таких векторов — это все остальные.
К>Что делать?

К>А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).


Спасибо. Так и делал.
Потом заметил ещё вот что:

вектор f "монотонен" <=> "монотонны" левый и правый полувекторы, и правый >= левого.

На основе этого можно сделать алгоритм, который будет в несколько раз быстрее, но всё равно с O(2^k * k), т.е. не принципиально лучше.

К>Интересно, можно ли быстрее?

Мне тоже...

Здравствуйте, Аноним, Вы писали:

К>>Интересно, можно ли быстрее?
А>Мне тоже...

Можно посчитать теоретическую оценку.
k-арная функция отображается на 2^k-арный вектор.
Всего k-арных функций — N(k) = 2^(2^k).
Из них, монотонных функций... это числа Дедекинда
M(k) ≈ 2^C(k,k/2)

Из этого следует... следует из этого... Чёрт, всё позабыл!