Написал код, который реализует алгоритм Форда-Фалкерсона и генерирует по шагам Ваш пример, можно посмотреть тут github.com/Malkovsky/interactive-visualization/blob/master/examples/ford-fulkerson.ipynb
Если хочется посмотреть и потыкать, но не хочется мучаться с установкой, можно онлайн в биндере (в репе есть ссылка), но возможно придется подождать сборку докер-образа
Метод, который упомянут в статье — «взять переменную, выразить из одного из уравнений и подставить в другие». Метод Гаусса — приведение к треугольному виду.
UPD. Технически это наверно эквивалентно, но я первый раз вижу, чтобы это подавалось с такой стороны
Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц
С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
Но ни новый алгоритм, ни другие математические достижения последнего полувека никак не повлияли на практически применимые способы решения систем уравнений: Google и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.
Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Все мы учили в школе алгоритм исключения неизвестных по одной
К тому же, в вещественных числах вычисление логарифма не зависит от аргумента
Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
Сотрите, у меня было два основных тезиса
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
Диагонализация матрицы из статьи
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
Видимо вы имеете в виду Формулу Бине, которая также опирается на возведение в степень, и если эту операцию мы считаем O(1), то и представленный алгоритм тоже O(1), но вообще это некорректно.
Интересный момент, вполне возможно, что там имелось в виду (last-first) + (middle-first)log(middle-first), так как видимо предполагается, что элементы от [first, middle) должны быть отсортированы. В соседнем же nth_element уже сложность линейная (с стандартной execution policy).
Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону — это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.
Эта фраза относилась к проблеме рендеринга latex формул (последний пример), а так разумеется основная цель — это подготовка материалов, в том числе и обучающих. Я веду курс лекций в СПбГУ/ВШЭ, хочу перевести его в такой формат
Есть более точный анализ сортировки вставками основанный на инверсиях. Инверсия в перестановке — это такая пара элементов, что больший из них стоит раньше. Единственная перестановка с нулевым количеством инверсий — это тождественная, она же является единственной отсортированной. Утверждается, что если сортировка вставками делает своп, то число инверсий уменьшается ровно на единицу. Отсюда количество свопов — это количество инверсий. Количество сравнений — это количества свопов плюс не больше, чем n холостых проверок, после которых срабатывает break.
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
или в некоторых местах открытую область (не выпуклую область)
Хотя бы один пример можете привести?
Алгоритмы линейной оптимизации начинают с некоторой вершины и следуют по прямой, заданной соответствующим уравнением, до следующей ближайшей точки пересечения (вершины)
Это называется Симплекс-метод, обоснование которого опирается на то, что набор линейных равенств и неравенств всегда задает выпуклый многогранник.
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. В любом случае это какие-то азы приведения задачи к нужному виду (канонической или стандартной форме).
По поводу остального — вы приводите поверхностные выводы, понять которые без деталей невозможно. Я не понимаю, про какие «необходимые условия и структуры данных» и «формализацию нелинейности» вы говорите.
github.com/Malkovsky/interactive-visualization/blob/master/examples/ford-fulkerson.ipynb
Если хочется посмотреть и потыкать, но не хочется мучаться с установкой, можно онлайн в биндере (в репе есть ссылка), но возможно придется подождать сборку докер-образа
UPD. Технически это наверно эквивалентно, но я первый раз вижу, чтобы это подавалось с такой стороны
С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Это между прочим именной метод
Я в своё время использовал hyperopt (кажется TPE), из коробки вполне работал, интересно узнать лучше ли у вас получилось.
Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
Про сам алгоритм можно прочитать например здесь
Одноко реальные попытки применить этот метод на практике провалились. Много историй об этом можно найти в… Вот только одна из них: используя работы Канторовича по оптимальному раскрою кусков заданной формы из прямоугольного листа, инженеры и экономисты фабрики, производившей стальные изделия, смогли значительно увеличить выпуск продукции. Однако они столкнулись с неожиданными неприятными последствиями. Во-первых, как результат, план на следующий год увеличился (для системы социалистического планирования было обычно требовать некоторого прироста производства продукции автоматически каждый год), но теперь уже у фабрики больше не было резервов, чтобы выполнить новый увеличенный план. Во-вторых, у каждого предприятия был план сбора металлолома, очевидно, что в результате применения оптимальной стратегии раскроя, количество отходов стали уменьшилось, и этот план выполнить не удалось. Руководство фабрики получило партийный выговор и, как следствие, отказалось от дальнейшего сотрудничества с математиками.
Для этого в матане тоже есть термин)
Опорная гиперплоскость
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
Это называется Симплекс-метод, обоснование которого опирается на то, что набор линейных равенств и неравенств всегда задает выпуклый многогранник.
2. Ну это точно никакая не проблема, если у вас задача в духе cx->min, Ax<=b, x>=h, то последнее ограничения можно просто добавить к Ax<=b. Ну или можно сделать замену y=x-h, тогда исходная задача переписывается в виде cy->min, Ay<=b+Ah, y>=0. В любом случае это какие-то азы приведения задачи к нужному виду (канонической или стандартной форме).
По поводу остального — вы приводите поверхностные выводы, понять которые без деталей невозможно. Я не понимаю, про какие «необходимые условия и структуры данных» и «формализацию нелинейности» вы говорите.