Открыть список
Как стать автором
Обновить

Комментарии 11

Спасибо, что выбираете для своего блога качественный контент, а не кликбейт!

Спасибо! мы стараемся :)
К счастью, на каждую страницу в интернете ведут совсем немного входящих ссылок — не миллиард и даже не миллион. На популярную статью в Википедии могут ссылаться десятки тысяч страниц, на эту статью на Хабре — хорошо если десятки. Иными словами, почти все коэффициенты в системе уравнений интернета — нули. Каждый ненулевой коэффициент подвергнется O(N) умножениям при подстановке содержащего его уравнения во все остальные.


Значит ли это, что в предельном случае (нереально огромного числа ссылок на ресурс) случайно наткнуться на него в Интернете будет быстрее, чем его нагуглить??

Предельный случай это если на каждой странице в интернете будет ссылка. Но тогда вероятность будет d*1/L(p), где d это вероятность того, что юзер кликнет по ссылке, L(p) это количество ссылок на странице p. То есть сильно меньше единицы.
Стопроцентная вероятность будет только если каждая страница в интернете будет содержать только одну ссылку, и это будет ссылка на страницу р. При этом должна отсутствовать возможность закрыть браузер или набрать другой адрес.

Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц

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

Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Все мы учили в школе алгоритм исключения неизвестных по одной
Это между прочим именной метод

У вас ссылка на метод решения системы неравенств. Если говорить, про уравнения, то это метод Гаусса

Метод, который упомянут в статье — «взять переменную, выразить из одного из уравнений и подставить в другие». Метод Гаусса — приведение к треугольному виду.

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

В посте ровно это и написано: «Для системы уравнений с их алгоритм находит точное решение за операций, опережая степень асимптотической сложности умножения матриц на 0.04.»

Это между прочим именной метод

У нас в школе, когда его учат, точно не упоминают ни Гаусса, ни Фурье, ни Моцкина.
Может быть, в англоязычных школах кого-то из них упоминают, но сомневаюсь.
Может они по дереву проходят начиная со страниц с нулевым числом входящих ссылок. Таким образом можно делать перерасчёт только в сегментах с изменёнными входными данными. В мире САПР тоже была дилемма система или дерево, все выбрали дерево оставив систему только для простейшей двухмерной геометрии.
Это не дерево: циклы из ссылок встречаются практически на каждом сайте.

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

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
Местоположение
Россия
Сайт
macloud.ru
Численность
11–30 человек
Дата регистрации
Представитель
Mikhail

Блог на Хабре