Есть мнение, что все формулы/теоремы, названные в честь известных математиков, изобретены далеко не ими, например с Гауссом подобная история. Забавно, что конкретно по тематике статьи есть обратный пример: известно, что первые варианты БПФ придумал именно он.
Ничего не мешает. Посыл в другом: я занимаюсь R&D и мы постоянно экспериментируем с разными методами, ошибки так или иначе случаются и их комбинации иногда приводят к очень странным узлам.
Градиентный спуск всегда сходится из любой начальной точки (если сходится)
Как-то очень странно вы написали. Возможно вы имели в виду, что как для градиентного спуска, так и для метода Ньютона гарантии сходимости есть только в случае выпуклости функции, но методу Ньютона дополнительно нужно еще достаточно близкое начальное приближение. Посыл был в том, что методы применялись в ситуациях, в которых теоретических гарантий в принципе нет. На текущий момент самое распространённое применение градиентного спуска - обучение нейросетей, где также нет никаких теоретических гарантий.
Мне кажется, что поиск гораздо лучше аналогия со словарём, отсортированным в лексикографическом порядке. Вот вы хотите найти какое-то слово:
Если вы открываете словарь посередине и смотрите на первую букву пытаясь понять, должно ли ваше слово быть во второй половине или первой, а потом повторяете несколько раз - это бинарный поиск.
Возможно вы филолог и знаете, что слов на букву "а" больше, чем на букву "ы", а может даже знаете априорное распределение для первых, ну или просто осознаёте, что слово на букву "э" будет скорее в конце, чем в начала и смотрите не в середину, а куда-то еще основываясь на априорных знаниях, это интерполяционный поиск.
Возможно это ваш словарь и вы заранее сделали в нём закладки на начало каждой буквы, а может даже и на первые две буквы. Найдя таким образом нужный раздел вы совершили поразрядную сортировку.
Так или иначе в какой-то момент находите нужную страницу и какой-то слово, которое достаточно близко к искомому и уже просто пробегаетесь подряд назад или вперед -- это линейный поиск
Чего многие не осознают, так это то, что на самом деле и практические поисковые алгоритмы гораздо сильнее схожи с человеческим, чем кажется. Например использование интерполяционного поиска на больших массивах сильно уменьшает количество кэш промахов по сравнению с бинарным, а на маленьких массивах линейный поиск может быть заметно лучше других за счет параллельной обработки (на уровне регистров/конвеера).
Случай отсутствия ограничений (теорема Ферма): если градиент не 0, то чуть-чуть идём в противоположном ему направлении -- линейна часть функции уменьшится, а значит при достаточно малом размере шага и сама функция уменьшается. Значит в точки минимума градиент обязан быть нулём.
Случай ограничений в виде равенств (метод множителей Лагранжа): ограничения задают некоторую поверхность/многообразие в пространстве. Попытаемся применить логику из предыдущего пункта, не должно существовать направления вдоль поверхности, движение по которому изменяло бы линейную часть функции. Геометрически это означает, что градиент функции обязан быть ортогонален поверхности.
Случай ограничений в виде неравенств, точка внутри (условия ККТ): если у нас есть ограничение, выполняющееся строго, то его можно просто выкинуть, на локальные свойства оно никак не повлияет, работает логика из первого пункта
Случай ограничений в виде неравенств, точка на границе (условия ККТ): наконец самый сложный случай, в целом схож с 2, но теперь у нас не только граница, но и внутренняя область. Качественная разница в том, что в одну сторону от границы мы можем перемещаться, а в другую нет. Из-за этого для гарантии минимума градиент должен быть не просто ортогонален границе, но и указывать вовне.
Условия неотрицательности -- соответствуют последнему пункту, условие дополняющей нежёсткости -- это неявный разбор случаев 3 и 4. Если убрать функцию g, отвечающую за неравенства, то останется пункт 2.
Недавно открыл для себя quarto, книгу в формате бумажной печати не пробовал на нём писать, но например со стандартной IEEE в две колонки легко справляется, есть примеры онлайн книг. Под капотом Jupyter+pandoc+latex
как оптимально распределить товары со складов по магазинам, учитывая пропускную способность дорог? Или как эффективно распределить вычислительную нагрузку между серверами?
Алгоритм Диница + capacity scaling даёт , U - максимальная пропускная способность.Вроде как есть варианты сделать . В любом случае интереснее кто быстрее номинально, а не асимптотически. Лет 10 назад когда плотно изучал вопрос хороши были как раз Диница и Preflow, последний как раз был хорош благодаря двум эвристикам (max height и global relabeling), благодаря которым становился очень быстр. У Эндрю Гольдберга в личной библиотеке были реализации обоих и вроде как они были сопоставимы по скорости. К сожалению эта библиотека скорее всего канула в лету. Префлоу я недавно видел в лимоне, в networkx реализованы оба, можно попробовать замерить, но учитывая что они там на питоне реализованы это будет очень условно. На алгоритм Бойкова-Колмогорова можно обратить внимание, он по асимптотике не очень, но вроде как зарекомендовал себя на практике для выделения границ в изображении.
P. S. @csharpminor0 алгоритм Диница не для начинающих ...
И тем не менее используемая в питоне сортировка тоже названа именем автора. Прогнал код на случайных данных, действительно вызовов компаратора меньше, чем у std::sort.
Мне тоже приятно в случае если это несколько строчек с переменными +- одинакового размера. Но вот если это начинает разрастаться, то могут появиться интересные эффекты:
Коммиты, удаляющие кучу пробелов, среди которых нужно искать реальные изменения
Код, напоминающий книжное оглавление, где на глаз уже не так очевидно к какому слову слева относится вот это число справа.
О чем кстати в книге вроде как и написано. В общем как обычно, не стоит а) вырывать тезисы из контекста б) слепо следовать правилам и предполагать, что другие так будут делать
Есть например октонионы, но кажется, что практическая их польза заметно меньше кватернионов.
Есть мнение, что все формулы/теоремы, названные в честь известных математиков, изобретены далеко не ими, например с Гауссом подобная история. Забавно, что конкретно по тематике статьи есть обратный пример: известно, что первые варианты БПФ придумал именно он.
Ничего не мешает. Посыл в другом: я занимаюсь R&D и мы постоянно экспериментируем с разными методами, ошибки так или иначе случаются и их комбинации иногда приводят к очень странным узлам.
Как-то очень странно вы написали. Возможно вы имели в виду, что как для градиентного спуска, так и для метода Ньютона гарантии сходимости есть только в случае выпуклости функции, но методу Ньютона дополнительно нужно еще достаточно близкое начальное приближение. Посыл был в том, что методы применялись в ситуациях, в которых теоретических гарантий в принципе нет. На текущий момент самое распространённое применение градиентного спуска - обучение нейросетей, где также нет никаких теоретических гарантий.
Вспомнил, что есть Freshman's dream, которая иногда возникает в конечных полях
Мне кажется, что поиск гораздо лучше аналогия со словарём, отсортированным в лексикографическом порядке. Вот вы хотите найти какое-то слово:
Если вы открываете словарь посередине и смотрите на первую букву пытаясь понять, должно ли ваше слово быть во второй половине или первой, а потом повторяете несколько раз - это бинарный поиск.
Возможно вы филолог и знаете, что слов на букву "а" больше, чем на букву "ы", а может даже знаете априорное распределение для первых, ну или просто осознаёте, что слово на букву "э" будет скорее в конце, чем в начала и смотрите не в середину, а куда-то еще основываясь на априорных знаниях, это интерполяционный поиск.
Возможно это ваш словарь и вы заранее сделали в нём закладки на начало каждой буквы, а может даже и на первые две буквы. Найдя таким образом нужный раздел вы совершили поразрядную сортировку.
Так или иначе в какой-то момент находите нужную страницу и какой-то слово, которое достаточно близко к искомому и уже просто пробегаетесь подряд назад или вперед -- это линейный поиск
Чего многие не осознают, так это то, что на самом деле и практические поисковые алгоритмы гораздо сильнее схожи с человеческим, чем кажется. Например использование интерполяционного поиска на больших массивах сильно уменьшает количество кэш промахов по сравнению с бинарным, а на маленьких массивах линейный поиск может быть заметно лучше других за счет параллельной обработки (на уровне регистров/конвеера).
Ждём когда master theorem переименуют в main theorem и тогда её смело можно добавлять к этому списку.
Если позволите, вот мои 5 копеек.
Слева направо, сверху вниз
Случай отсутствия ограничений (теорема Ферма): если градиент не 0, то чуть-чуть идём в противоположном ему направлении -- линейна часть функции уменьшится, а значит при достаточно малом размере шага и сама функция уменьшается. Значит в точки минимума градиент обязан быть нулём.
Случай ограничений в виде равенств (метод множителей Лагранжа): ограничения задают некоторую поверхность/многообразие в пространстве. Попытаемся применить логику из предыдущего пункта, не должно существовать направления вдоль поверхности, движение по которому изменяло бы линейную часть функции. Геометрически это означает, что градиент функции обязан быть ортогонален поверхности.
Случай ограничений в виде неравенств, точка внутри (условия ККТ): если у нас есть ограничение, выполняющееся строго, то его можно просто выкинуть, на локальные свойства оно никак не повлияет, работает логика из первого пункта
Случай ограничений в виде неравенств, точка на границе (условия ККТ): наконец самый сложный случай, в целом схож с 2, но теперь у нас не только граница, но и внутренняя область. Качественная разница в том, что в одну сторону от границы мы можем перемещаться, а в другую нет. Из-за этого для гарантии минимума градиент должен быть не просто ортогонален границе, но и указывать вовне.
Условия неотрицательности -- соответствуют последнему пункту, условие дополняющей нежёсткости -- это неявный разбор случаев 3 и 4. Если убрать функцию g, отвечающую за неравенства, то останется пункт 2.
6600 можно просто разбить молотком. Вы лучше расскажите, что под капотом 3310.
Недавно открыл для себя quarto, книгу в формате бумажной печати не пробовал на нём писать, но например со стандартной IEEE в две колонки легко справляется, есть примеры онлайн книг. Под капотом Jupyter+pandoc+latex
Редкий анекдот, про который я был уверен, что
Человек на земле был дворником.
Шерлок Холмс заключил, что они в России, потому что только тут математики работают дворниками.
Неужели до сих пор гибрид/стс + нграмные языковые являются наиболее предпочтительными вариантами для продакшена ASR?
Есть ссылки где применяются?
Если сложность не важна, почему для начинающих Вы решили рассказывать алгоритм Диницы, а не алгоритм Форда-Фалкерсона?
Алгоритм Диница + capacity scaling даёт
, U - максимальная пропускная способность.Вроде как есть варианты сделать 
. В любом случае интереснее кто быстрее номинально, а не асимптотически. Лет 10 назад когда плотно изучал вопрос хороши были как раз Диница и Preflow, последний как раз был хорош благодаря двум эвристикам (max height и global relabeling), благодаря которым становился очень быстр. У Эндрю Гольдберга в личной библиотеке были реализации обоих и вроде как они были сопоставимы по скорости. К сожалению эта библиотека скорее всего канула в лету. Префлоу я недавно видел в лимоне, в networkx реализованы оба, можно попробовать замерить, но учитывая что они там на питоне реализованы это будет очень условно. На алгоритм Бойкова-Колмогорова можно обратить внимание, он по асимптотике не очень, но вроде как зарекомендовал себя на практике для выделения границ в изображении.
P. S. @csharpminor0 алгоритм Диница не для начинающих ...
Про DCT поправил. Про паддинг я вроде бы не писал, сам как раз работаю с полями
где паддинг проблематичный, а БПФ уметь делать очень хочется.
И тем не менее используемая в питоне сортировка тоже названа именем автора. Прогнал код на случайных данных, действительно вызовов компаратора меньше, чем у std::sort.
Хмм
\color{red}{asdasd} ->
\color{blue}{asdasd} ->
\color{green}{asdasd} ->
Хмм, ну как будто все замеры перемешались. Может выложите код на гитхаб? Ну или хотя бы замените скриншоты кода текстом.
Мне тоже приятно в случае если это несколько строчек с переменными +- одинакового размера. Но вот если это начинает разрастаться, то могут появиться интересные эффекты:
Коммиты, удаляющие кучу пробелов, среди которых нужно искать реальные изменения
Код, напоминающий книжное оглавление, где на глаз уже не так очевидно к какому слову слева относится вот это число справа.
О чем кстати в книге вроде как и написано. В общем как обычно, не стоит а) вырывать тезисы из контекста б) слепо следовать правилам и предполагать, что другие так будут делать