• Как оптимизировали экономику СССР и что из этого вышло
    +4
    Из статьи Поляк Б. Т. История математического программирования в СССР: анализ феномена

    Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
  • Быстрый поиск касательных и пересечений у выпуклых многоугольников
    +1
    Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону — это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.

    Для этого в матане тоже есть термин)
    Опорная гиперплоскость
  • Мой топ IT книг из прошлого века, актуальных до сих пор
    +8
    Книги Таненбаума.
  • Интерактивная визуализация алгоритмов на базе Jupyter
    +1
    Эта фраза относилась к проблеме рендеринга latex формул (последний пример), а так разумеется основная цель — это подготовка материалов, в том числе и обучающих. Я веду курс лекций в СПбГУ/ВШЭ, хочу перевести его в такой формат
  • Сортировка вставками
    0
    Есть более точный анализ сортировки вставками основанный на инверсиях. Инверсия в перестановке — это такая пара элементов, что больший из них стоит раньше. Единственная перестановка с нулевым количеством инверсий — это тождественная, она же является единственной отсортированной. Утверждается, что если сортировка вставками делает своп, то число инверсий уменьшается ровно на единицу. Отсюда количество свопов — это количество инверсий. Количество сравнений — это количества свопов плюс не больше, чем n холостых проверок, после которых срабатывает break.

    Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны

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

    Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
  • Кластерный метод решения транспортной задачи
    0
    или в некоторых местах открытую область (не выпуклую область)
    Хотя бы один пример можете привести?
    Алгоритмы линейной оптимизации начинают с некоторой вершины и следуют по прямой, заданной соответствующим уравнением, до следующей ближайшей точки пересечения (вершины)
    Это называется Симплекс-метод, обоснование которого опирается на то, что набор линейных равенств и неравенств всегда задает выпуклый многогранник.
  • Кластерный метод решения транспортной задачи
    0
    1. Предполагаю, что вы имеете в виду следующий пример: есть два треугольника с вершинами (0, 0), (2, 0), (0, 2) и (1, 1), (1, 0), (0, 1) соответственно; наша область — это пересечение первого треугольника и дополнения второго. Такая область действительно невыпукла, как и дополнение второго треугольника. Дополнение треугольника невозможно получить набором линейных неравенств.
    2. Ну это точно никакая не проблема, если у вас задача в духе cx->min, Ax<=b, x>=h, то последнее ограничения можно просто добавить к Ax<=b. Ну или можно сделать замену y=x-h, тогда исходная задача переписывается в виде cy->min, Ay<=b+Ah, y>=0. В любом случае это какие-то азы приведения задачи к нужному виду (канонической или стандартной форме).

    По поводу остального — вы приводите поверхностные выводы, понять которые без деталей невозможно. Я не понимаю, про какие «необходимые условия и структуры данных» и «формализацию нелинейности» вы говорите.
  • Кластерный метод решения транспортной задачи
    0
    1. Для решения задачи использовалась WolframMathematica. Она «умеет» многое.
    Зачем же вы ограничиваете себя линейным программированием тогда?
    2. Добиваюсь преодоления проблем, обозначенных вначале.
    Должен признать, я вообще не понял вторую и третью проблемы, слишком мало контекста.
    3. Устойчивость в задаче линейного программирования — это получение одинакового результата вне зависимости от начальной точки и метода обхода вершин (по тексту было уточнено).

    5. Проблема и условия устойчивости. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование (1998).

    Посмотрел в книге, там под устойчивостью подразумевается совершенно другое — как изменится решение, если мы немного поменяем параметры задачи. Вообще обычно это называется «Sensitivity analysis».
    4. Почему любая система линейных уравнений и неравенств должна порождать выпуклую область?
    Потому что пересечение выпуклых множеств выпукло
    Линейное программирование не покрывает большинство потребностей в бизнесе (я такое не писал — видно по ссылке). Более того, оно не соответствует сути большинства задач, подразумевающих наличие нелинейности.

    Ну так используйте нелинейное!
    Нельзя правильно использовать результат, который непонятно как получен. Получая «оптимальное» решение неким стандартным методом, вы, на самом деле, не знаете, что получили.
    Тут то в чем проблема? Если переменные задачи не имеют интерпретацию вида «купить у поставщика АА такой объем угля», «перевезти из пункта А в пункт Б столько то угля», то это не проблема математического метода, это проблема моделирования.
  • Кластерный метод решения транспортной задачи
    0
    Оптимизация в бизнесе в подавляющем числе случаев связана с применением метода линейного программирования.

    Линейное программирование покрывает большой пласт задач, но не точно не большинство потребностей бизнеса. Как минимум можно посмотреть на стандартные пакеты для оптимизации и что они умеют. Вот например Gurobi поддерживает линейное, квадратичное и смешанное программирование. Вообще в науке линейное программирование сейчас подпадает под более широкий класс задач выпуклой оптимизации — для них работает тот же эффективный метод внутренней точки, собственно это помогло бы с вашей первой проблемой. Если хотите попробовать как-то применять выпуклую оптимизацию на практике, советую посмотреть на cvxpy/cvxopt. Отдельно стоит выделить оптимизационные пакеты для машинного обучения (tensorflow, pytorch,… ), они вообще работают с произвольными функциями, но без ограничений. Они заточены под другой пласт задач, но тоже более чем используются на практике.

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

    В теории решения экстремальных задач имеется теорема об устойчивости решения задач линейного программирования. Согласно ей решение устойчиво только при условии выпуклости области определения задачи. При большом количестве переменных и неравенств установить, выпукла ли область определения задачи, не представляется возможным. При этом вероятность не выпуклости велика.

    Что вы понимаете под устойчивостью? В задаче линейного программирования ограничения всегда задают выпуклое множество.
  • Немецкое качество по доступной цене
    0
  • Нейросеть — обучение без учителя. Метод Policy Gradient
    0
    Среда выдает Агенту только вознаграждение по результатам его действий, Среда никак своей наградой Агента не обучает и не говорит ему правильно он поступает или нет.

    Среда обучает агента и говорит ему, поступает ли он правильно или нет, ровно тем, что дает ему вознаграждение по результатам его действий.

    Как обычные задачи обучения с учителем, так и задачи обучения с подкреплением решаются с помощью минимизации некоторого функции потерь. Ключевая разница — в более традиционных задачах, таких как классификация, даны «правильные ответы», и в качестве функции потерь используется какое-то расстояние (среднеквадратиченое отклонение, кросс энтропия) между выходами модели и правильными ответами, так как мы знаем функцию расстояния, то можем её продифференцировать. В обучении с подкреплением функция потерь задана извне, поэтому мы не можем её продифференцировать, в этом и заключается ключевая особенность задач обучения с подкреплением.
  • Нейросеть — обучение без учителя. Метод Policy Gradient
    0
    У OpenAI есть целая подборка, наверно самая классическая задача из этой серии — это задача обратного маятника
  • Нейросеть — обучение без учителя. Метод Policy Gradient
    0
    Хотя, может я и не прав
  • Нейросеть — обучение без учителя. Метод Policy Gradient
    +3
    Таким образом так же обобщая все вышесказанное, мы приходим к выводу, что алгоритмом обучения без учителя мы называем такие алгоритмы, где нет явных указания для алгоритма как ему поступать, а есть только общая оценка всех его действий в процессе решения задачи.

    Не надо свою субъективную классификацию методов выдавать за общепринятую. А в общепринятой обучение без учителя — это не когда вы даете только «общую оценку» действий, а когда вы никакой оценки не даете. Обучение с подкреплением (reinforcement learning) — это вполне себе обучение с учителем.
  • Немецкое качество по доступной цене
    0
    Спасибо, когда писал уже купил тот, что изначально хотел, доволен как слон. С wifi уже обнаружил, что фильмы в высоком качестве не посмотреть, правда задержи в 2-5 секунд не обнаружил, только артефакты изображения и просадку битрейта. Возможно попробую этот SVP 4, спасибо за наводку. Быть может можете что-нибудь посоветовать про всякие chromecast и подобное?
  • Немецкое качество по доступной цене
    0
    Увидел, большое спасибо! Посмотрел еще на сайте Люфтганзы, буду теперь знать, куда смотреть.
  • Немецкое качество по доступной цене
    +1
    Не совсем понял, что Вы имеете в виду. Яндекс маркет сам по себе ничего не продает (или я не прав?), а только агрегирует данные, в общем то та же реклама, но, судя по всему, сделанная с большей ответственностью.

    Или Вы имеете в виду то, что Яндекс большой и разнообразный, директом и маркетом там занимаются разные команды, которые возможно даже никогда друг с другом не общались?
  • Немецкое качество по доступной цене
    0
    Про такое не знал. А это только в *.de? И где его можно посмотреть, если он есть?
  • Немецкое качество по доступной цене
    +5
    Вот никогда в жизни не кликал на рекламу, а тут решил попробовать, почему бы и нет? Не могу сказать, что получилось плохо — получил новый для себя опыт.
  • Мир и еще n миров, или математика для гуманитария
    +1
    Мне лично очень приятно, что Вы пришли к выводам о том, что математика существует не только для того, чтобы вас не обманывали со сдачей в магазине. Но все-таки у Вас банально не хватает компетенции для того, чтобы адекватно рассказывать о том, зачем нужна математика: понимать что-то и уметь объяснять это другим — задачи совершенно разного уровня. С этим кстати успешно справляется Алексей Савватеев
  • Квадратура круга: наглядное доказательство
    0
    Ну и что от того, что не сглаживается? В определении через правильные многоугольники тоже не сглаживается, углов становится все больше и больше, но в пределе почему-то другая величина.
  • Квадратура круга: наглядное доказательство
    +1
    Полагаю этот комментарий будет также заминусован, но добавлю
    Вы можете обратить внимание, что не все Ваши комментарии заминусованы. Анализируйте, делайте выводы.
  • Квадратура круга: наглядное доказательство
    0
    Более канонический пример — доказательство, что пи=4. И парадокс этот только с помощью евклидовой геометрии и интуиции не разрешить. А вот дифференциальное/интегральное исчисление явно дает непротиворечивое определение длины произвольной кривой, в рамках которого описанная в доказательстве схема к этой самой длине не имеет никакого отношения. Короче говоря
    Мат. анализ не зря придумывали

  • Разбираем EM-algorithm на маленькие кирпичики
    +2
    Как говорится, «Вы там сговорились, что ли?», буквально на днях на хабре статья про ЕМ была.

    Для ЕМ алгоритма есть очень хороший и простой пример — метод к средних. Он не использует вероятностную трактовку, но в целом имеет схожую структуру.

    Вообще, ЕМ алгоритм — это довольно общая штука. Представьте, что вы как-то разметили данные и обучили на этом некоторую статистическую модель. В некоторых ситуациях может так получиться, что если вы этой же моделью разметите обучающую выборку, а потом переучите модель на новой разметке, то модель станет лучше. В общем то, зациклив эту процедуру и получается ЕМ алгоритм, кластеризацией он не ограничен. Я вот довольно много работаю со скрытыми марковскими цепями, там есть хороший аналог — алгоритм Баума-Велша.

    А так, мне кажется, что мануал хороший!

    P. S. У вас там кажется пару раз $j$ встречается, видимо забыли $inline$ написать. На мой взгляд в заглавной картинке ну уж очень мерзким шрифтом формулы написаны
  • EM-алгоритм для кластеризации
    0
    Хабр не рендерит букву с двумя индексами, если в выражении есть знак суммы (я писал всё в Chrome). Также я хотел везде написать _{i=1}, а не просто i внизу знака суммы, но это тоже не работает, как показал предпросмотр. Наверно, стоит обратиться в поддержку.

    Вот одна из моих статей на хабре, где есть "_{i=1}", пробовал открывать в хроме — вроде бы все отображается. По поводу двух индексов не понял, в чем проблема. Вы уверены, что вы корректное TeX выражение использовали?
  • EM-алгоритм для кластеризации
    0
    Честно говоря, мне кажется, что структура статьи очень плохая. Прочитав раздел «Идея Решения» создается ощущение, что вы описываете не ЕМ алгоритм, а один его шаг.

    Зашел на википедию, увидел там описание алгоритма ничуть не хуже, чем у Вас, да еще и с анимированным примером. В чем преимущество вашей статьи?

    По формулам: у вас где-то g_{ij}, а где-то g(ij). Предположу, что это одни и те же величины, та как g(ij) не определяется… обычно в математических формулах так не делают и используют одинаковый стиль обозначений (в данном случае индексирования), чтобы лишний раз не путать читателя.
  • Замощение доминошками
    0
    Ничего страшного, бывает
  • Замощение доминошками
    +1
    Да, fig можно отрисовать/сохранить. Но в моем случае дело немного в другом: если бы мне нужно было просто отрисовать фигуру, то достаточно было бы просто написать там `plt.show()`, но у меня была цель еще и как-то проанимировать алгоритмы, для этого я сохранял fig в список и потом анимировал его с помощью ipywidgets.
  • Замощение доминошками
    +1
    Я про такую задачу мало что знаю, попробуйте посмотреть вот эту статью
  • Замощение доминошками
    +1
    Ровно это объяснение я даю в самом начале под спойлером, во второй конфигурации 16 белых и 16 черных клеток
  • Генерация предсказуемых случайных последовательностей: другой подход к пермутациям
    +1
    Вы уже раза 3 написали, что Фишер-Йетс не подходит (к слову большое спасибо, я знал этот алгоритм, но не знал, что он именной), но совершенно непонятно почему. Исходя из той задачи и того исходного решения, которое вы описали, создается ощущение, что подходит абсолютно любой алгоритм равномерной генерации перестановок. Все, что нужно сделать — это запомнить seed.
  • Топологическая сортировка
    0
    Хмм… скорее всего это ровно то, что рассказывается в статье, уверен, что это фольклор. Тарьян вообще кучу всего придумал, наиболее близкое по теме — это скорее всего алгоритм нахождения компонент сильной связности, если применить его к ациклическому графу, то он сделает на нем топологическую сортировку, а потом обнаружит, что все компоненты состоят из одной вершины.
  • Машинный перевод. От Холодной войны до наших дней
    +1
    Очевидным недостатком данной модели является также то, что для подготовки корпуса, в котором сделано выравнивание, требуются очень значительные усилия, профессиональные переводчики должны не просто перевести текст, но и указать, какое слово является переводом какого.

    А как же автоматическое выравнивание? Собственно решение от IBM
  • Генерируем тексты песен цепями Маркова
    +2
    Нет, сама по себе библиотека дает прекрасный результат.

    Вы вообще на него смотрели? Сгенерированной фраза
    «Но на тебе я ставлю точку, это точно, Вот мое тебе «пока». Я говорю тебе в ответ: Что еще тут непонятно?»
    покрывается (с переходом на слове «тебе»)
    «Но на тебе я ставлю точку, это точно, Вот мое тебе «пока». Я говорю тебе»
    и
    «тебе в ответ: Что еще тут непонятно?»
    которые присутствует в обучающем тексте.

    Результат очень слабый. Если хотите использовать марковские цепи для генерации текста, то хотя бы разберитесь в том, как работают нграмные языковые модели, но вообще вроде как не секрет, что нейронные сети сейчас вне конкуренции на подобных задачах
  • MVP проекта CoVirus — онлайн карта заражения коронавирусом или «красная кнопка» в твоей руке
    +2
    С начала февраля мониторю страничку от John Hopkins University
    Новостей там нет, но в плане интерактивной карты она точно более информативна
    Вышел на неё, кажется, по хабру
  • Нормализация текста в задачах распознавания речи
    +3
    Читать разумеется удобней, но тут предполагается текста для обучения систем распознавания речи, а там как раз предпочтительней, чтобы текст в точности соответствовал тому, что было произнесено, без сокращение и прочего
  • Просто о простых числах (быстрый инкрементный метод вычисления простых чисел)
    0
    «для каждого очередного… помечает кратные ему» это как минимум вложенный цикл, это не похоже на O(1)

    Внутренний цикл действительно не O(1), при нахождении простого k внутренний цикл делает (n-k*k)/k итераций. Вероятность, что число k является протым — это k/ln(k). Дальше немного базового матана и вы получаете оценку для базового решета Эратосфена O(n loglog(n)).

    Есть более оптимальная реализация со сложностью O(n), о ней даже в прошлом году писали на хабре

    P. S. alez13 Вы потратили время на изложения своего потока мыслей не удосужившись до это сделать минимальные действию по изучению вопроса (поискать в гугл, ну или на хотя бы на хабре). Это основная причина, почему вашу статью приняли в штыки.
  • Kaboom: необычный сапёр
    +5
    Хмм, а почему в случае отсутствие безопасных клеток сделать так, что любая открытая небезопасная клетка не взрывалась?
  • Теория антиряда
    0
    Если вы пишите статью, предполагая, что читать её будете только вы сами, но при этом выставляете на общее обозрение некоторому сообществу, то отрицательная оценка этой статьи — закономерный результат.
    В интернете нет ни одного форума, участники которого были бы заинтересованы в получении результатов совместной научно-теоретической деятельности

    Зачем же вы тогда тратите свое время на то, чтобы писать что-то на форуме в интернете?
    поэтому мне нет смысла соблюдать эти формальности
    Для людей, которые профессионально занимаются наукой (да и не только), эти формальности позволяют быстрей и эффективней находить полезную для них информацию.
  • Теория антиряда
    0
    Хотелось бы всё-таки рассчитывать на минимум компетенции участников обсуждения

    В таком случае вам стоит освоить минимальную компетенцию автора публикации: из первого абзаца должно быть понятно, какова цель этой публикации, о чем она. Без этого условия публикацию не будут читать, какой бы прорывной и гениальной она не была (и это действует не только на хабре).