"Мимимизация выпуклых функций"
Решите задачку. В семье два ребенка. Известно, что один из них — мальчик, родившийся во вторник. Какая вероятность, что второй ребенок — девочка?
Безысходность. Минимизация недифференцируемой невыпуклой кусочно-линейной функции, где вычисление градиента любого линейного куска — решение NP-сложной задачи. Жизнь — боль.
<rkit> Понимаю. Это ты не понимаешь, что тьюринг-полнота не требует бесконечной ленты.
Есть предикат f(A, B, C), определяющий, можно ли вокруг точек A, B, C на плоскости описать окружность заданного радиуса r.
Оказывается, у предиката f нет мажоритарного полиморфизма четвертого порядка.
Для меня это очень важный результат, ведь я особенно много думал над этой задачей 4 месяца назад, когда во всю пылал кризис в моей личной жизни.
Забавно, как только мне казалось, что ответ к задаче положительный, у меня возникала эйфория, а вместе с ней и уверенность, что я все исправлю.
Когда же я находил ошибку в своих рассуждениях и у меня появлялись хорошие аргументы в пользу отрицательного ответа, меня бросало в отчаяние и приходило чувство безысходности.
Вышло так, что мои отношения окончательно разрушились до того, как я нашел ответ.
Теперь я знаю, что они были обречены, ведь у такого предиката нет мажоритарного полифморфизма четвертого порядка =)
Оказывается, у предиката f нет мажоритарного полиморфизма четвертого порядка.
Для меня это очень важный результат, ведь я особенно много думал над этой задачей 4 месяца назад, когда во всю пылал кризис в моей личной жизни.
Забавно, как только мне казалось, что ответ к задаче положительный, у меня возникала эйфория, а вместе с ней и уверенность, что я все исправлю.
Когда же я находил ошибку в своих рассуждениях и у меня появлялись хорошие аргументы в пользу отрицательного ответа, меня бросало в отчаяние и приходило чувство безысходности.
Вышло так, что мои отношения окончательно разрушились до того, как я нашел ответ.
Теперь я знаю, что они были обречены, ведь у такого предиката нет мажоритарного полифморфизма четвертого порядка =)
Пишу тут, чтобы не забыть.
Для конечного полукольца (+,) с идемпотентными + и следующие два утверждения эквивалентны:
1) Закон поглощения: a+a*b = a для любых a и b.
2) Единица равна сумме всех элементов полукольца
Для конечного полукольца (+,) с идемпотентными + и следующие два утверждения эквивалентны:
1) Закон поглощения: a+a*b = a для любых a и b.
2) Единица равна сумме всех элементов полукольца
Есть функция g(0) = 1, g(1) = 2, g(2) = 4, ..., g(i+1) = 2^g(i).
И обратная ей функция f(k) = g^-1(k).
Как называется функция g или лучше функция f?
Если есть какая-то функция O(f) с хорошим названием, то тоже очень даже подойдет.
И обратная ей функция f(k) = g^-1(k).
Как называется функция g или лучше функция f?
Если есть какая-то функция O(f) с хорошим названием, то тоже очень даже подойдет.
В доказательстве центральной предельной теоремы по ссылке:
nsu.ru
Утверждается, что справедливо nsu.ru
исходя из справедливости замечательного предела.
Я понимаю, почему (1 — t^2/(2n)) -> exp[i-t^2/2]
Но вот как не крути, а (1 — t^2/(2n) + o(t^2/n)) -> exp[i-t^2/2] + o(t^2)
И от этого самого o(t^2) избавиться у меня не выходит.
nsu.ru
Утверждается, что справедливо nsu.ru
исходя из справедливости замечательного предела.
Я понимаю, почему (1 — t^2/(2n)) -> exp[i-t^2/2]
Но вот как не крути, а (1 — t^2/(2n) + o(t^2/n)) -> exp[i-t^2/2] + o(t^2)
И от этого самого o(t^2) избавиться у меня не выходит.
Как решить такое дифференциальное уравнение второго порядка?
y''y = c
y''y = c
Какие еще есть интересные полукольца с идемпотентными + и *, кроме (V,&), (min, max), (max, min) и (объединение, пересечение)?
Есть некоторая выпуклая дифференцируемая функция f(x), где x — элемент R^n.
В любой точке x мы можем вычислить случайный вектор g(x) такой, что математическое ожидание g(x) равно градиенту в точке x: M[g(x)] = grad f(x).
xm — минимум функции f.
рассмотрим процесс x_{i+1} = 1/i*g(x_i) + x_i
Вопрос 1: стремится ли вероятность того, что |x_n-xm|<epsilon к единице?
Вопрос 2: тот же вопрос, но f — не дифференцируемая, а M[g(x)] — субградиент f(x)
В любой точке x мы можем вычислить случайный вектор g(x) такой, что математическое ожидание g(x) равно градиенту в точке x: M[g(x)] = grad f(x).
xm — минимум функции f.
рассмотрим процесс x_{i+1} = 1/i*g(x_i) + x_i
Вопрос 1: стремится ли вероятность того, что |x_n-xm|<epsilon к единице?
Вопрос 2: тот же вопрос, но f — не дифференцируемая, а M[g(x)] — субградиент f(x)
У меня ступор.
Как доказать, что
min_x max_y xAy = max_y min_x xAy
где A — матрица,
x и y — вектора принадлежащие выпуклым множествам
?
Как доказать, что
min_x max_y xAy = max_y min_x xAy
где A — матрица,
x и y — вектора принадлежащие выпуклым множествам
?
посоветуйте литературу по #P-полноте задач и по #P (sharp P, number P) вообще.
Подскажите хорошие книги по линейному программированию.
А то я где бы не читал о, например, симплекс методе, ничего не понимал, пока сам не начал его придумывать.
А то я где бы не читал о, например, симплекс методе, ничего не понимал, пока сам не начал его придумывать.
Субмодулярная псевдобулевая функция двух переменных в своей приведенной форме не содержит нелинейных слогаемых с положительными коэффициентам.
Справедливо ли это для функций большего числа переменных?
Справедливо ли это для функций большего числа переменных?
Есть n-мерный гиперкуб с длиной ребра 1. Множество вершин гиперкуба разделили на два подмножества так, что их выпуклые оболочки не пересекаются. Вопрос: какое минимальное расстояние может быть между выпуклыми оболочками?