Новости — Алгоритм 2013
Официальные результаты финального раунда доступны по ссылке:
Мы поздравляем tourist, eatmore и peter50216 с первым, вторым и третьим местом в финальном раунде!
Чтобы узнать больше о том, как прошел финальный раунд Яндекс.Алгоритма 2013 следите за новостями.
Текстовая трансляция финального раунда:
Сегодня в 14:00 начнется финальный раунд Яндекс.Алгоритма. Все участники уже прибыли в Санкт-Петербург, заглянули во дворец и немного прогулялись по городу.
Прошло уже 15 минут, но до сих пор ещё нет ни одного сабмита! А между тем, участникам предложено шесть задач всего на 100 минут.
14:18: KADR сделал первый сабмит втёмную по задаче B!
14:19: А за ним и dmitrymatov, первая сдача задачи в открытую. Тоже B.
14:20: eatmore отправил B втёмную, попав на второе место в турнирной таблице, а s-quark сделал неудачную посылку по задаче A. Наконец-то ребята проснулись. 🙂
14:23: yeputons, сабмит по B втёмную. По секретной информации, mikhailOK работает над E, Petr пишет F, но большинство решают A и B.
14:25: tourist, сабмит по B втёмную. Кажется, что ребята идут в ва-банк, рассчитывая получить минимум штрафного времени. Ну что ж, тем интереснее будет разморозка. 😉
14:26: Mimino совершил неудачный сабмит в открытую по задаче A. Пока что A не поддалась ещё никому.
14:31: RAVEman отправил втёмную B, а между тем у Mimino вторая неудачная попытка по A.
14:32: А вот и Petr! Неожиданный сабмит втёмную по F и первое место в турнирной таблице!
14:33: watashi сделал сабмит в открытую по B и — неудача. Пока что китайские участники идут не очень удачно, но всё впереди!
14:34: Также втёмную отправили задачу B vepifanov и Jedi_Knight.
14:36: ilyakor в открытую сдал B. Теперь определилась первая десятка соревнования. А между тем, до конца контеста остался всего один час.
14:38: peter50216, сабмит втёмную по B.
14:39: Mimino сделал уже четыре неудачных посылки по A! Жюри считает, что участников ждёт ещё несложная задача D, которая пока ещё никем не открыта (не прочитана?) 😉
14:42: Petr уверенно закрепляет успех сабмитом втёмную по B! Уже две задачи!
14:44: s-quark, watashi и Kenny_HORROR отправили B и поднялись в таблице.
14:47: Многие участники, воодушевившись примером Petr, пытаются решать сложную задачу F. Прошла почти половина контеста, на первом месте Petr с двумя задачами (B и F), за ним 2–14 места с одной задачей B.
14:50: tourist отправляет втёмную задачу F и вырывается на второе место!
14:51: А вот и первый сабмит по задаче D от ainu77! К сожалению, неудачный.
14:53: По задачам C и E нет ни одной посылки, по A и D пока не было успешных, B выглядит наиболее простой и решаемой, ну а что происходит на самом деле с F? 🙂
14:54: А вот и сразу два сабмита втёмную по D от eatmore и ainu77! eatmore теперь разделяет 2–3 места с tourist, ainu77 четвёртый.
14:57: RAVEman отправил задачу F и… eatmore поднимается на первое место! Вот это правила! =)
15:00: watashi сдаёт в открытую F и поднимается на пятое место! В отличие от других лидеров, у watashi задачи B и F гарантированно решены.
Где это видано, Где это слыхано, RAVEman сабмитит, а eatmore растёт! 😀
15:04: Сабмит втёмную по F от s-quark.
15:05: KADR и peter50216 отправили F втёмную. Кажется, что сабмиты втёмную — это де-факто стандарт нашего финала! =)
15:06: romanandreev сдаёт в открытую D, это первый сабмит romanandreev и первая гарантированная сдача D!
15:07: mikhailOK отправил втёмную F.
15:08: А вот и tourist! Третья задача втёмную — на этот раз D — и первое место!
15:11: Всего пятеро ребят пока не справились ни с одной задачей. tourist, eatmore и Petr составили тройку лидеров.
15:13: michal.forisek сдаёт в открытую D. Остаётся 25 минут до конца.
15:14: winger сдал в открытую сложную задачу A и переместился на 9-ое место!
15:15: Согласно мнению Павла Кунявского, все задачи достаточно неприятны. 😀
15:17: eatmore закрепляется на втором месте, отправляя втёмную задачу F и проигрывая всего 9 минут штрафного времени tourist.
15:21: s-quark отправил втёмную задачу D и вышел на третье место!
15:23: Niyaz Nigmatullin сдаёт задачу B в открытую. Все участники из России справились хотя бы с одной задачей.
15:25: winger сдаёт F втёмную и поднимается на четвёртое место. Напомним, что это единственный участник, справившийся с задачей A.
15:27: peter50216 отправляет задачу D втёмную и поднимается на четвёртое место.
15:31: Petr дебажит C, tourist решает A. А между тем, остаётся меньше десяти минут до конца!
15:35: Меньше пяти минут до финиша, в таблице никаких изменений. Может это затишье перед бурей?..
15:37: Petr отправляет C втёмную и выходит на первое место за три минуты до конца, выигрывая у tourist всего одну минуту штрафного времени!
15:39 Настойчивый Mimino делает уже 12-ую неудачную попытку по задаче A. 🙂
15:40 Соревнование окончено!
contest.yandex.ru
Разбор квалификационного раунда Яндекс.Алгоритм 2017 — Алгоритм 2017
Этот раунд был подготовлен разработчиками минского офиса Яндекса.
Рассмотрим решение, которое работает с квадратичной асимптотикой. Для этого будем действовать в соответствии с условием задачи: заведем счетчик последней закрытой задачи, будем проходить по списку задач от начала до конца, увеличивая счетчик, когда проходим через элемент массива задач, соответствующий следующей задаче. Из-за достаточно больших ограничений это решение не укладывается по времени.
Рассмотрим, в каком случае, мы уже не найдем никакой подходящей задачи до конца списка. Оказывается, только в том случае, когда после закрытия задачи с номером x следующая задача с номером (x+1) расположена ближе к началу списка. Следовательно, для решения задачи нужно по каждому номеру задачи узнать ее позицию в списке задач, а затем подсчитать количество различных номеров x таких, что позиция задачи с номером (x+1) меньше, чем позиция задачи с номером x.
К найденному количеству нужно добавить первый проход по списку задач. Итоговая трудоемкость алгоритма .
Задача “Междугороднее общение” не содержит особой алгоритмической идеи, поэтому нужно аккуратно реализовать описанное в условии задачи поведение системы бронирования.
Мы можем зафиксировать число от 0 до 23 (час, в который будем проверять возможность организации встречи). После этого в каждом из городов нужно проверить наличие свободной переговорки.
Отметим, что при больших ограничениях сохранить свободную переговорку для каждой пары (город, час) следовало бы до обработки запросов. Это позволило бы всегда отвечать на запрос за время пропорциональное количеству городов, а не суммарному количеству переговорок.
Для этой задачи можно придумать несколько различных подходов к решению задачи, рассмотрим два из них.
Первое решение основано на подсчете количества раз, сколько раз тест с номером x будет запущен. В исходной системе каждой тест запускается один раз, а в новой системе 2d(x), где d(x) расстояние от корневого тест до теста с номером x. Это утверждение несложно доказывается методом математический индукции, также заметить этот факт можно было внимательно изучив описание тестовых примеров из условия. Для подсчете d(x) достаточно обойти дерево любым обходом.
Второй метод решения основан на динамическом программировании. Пусть T(x) равно суммарному времени работы теста с номером x, т.е. времени работы тестов, от которых он зависит, и времени проверки ax. Запишем соотношение:
Для вычисления ответа T(1) также достаточно одного обхода дерева (в данном случае DFS).
Трудоемкость решения задачи .
Сразу следует рассмотреть такую задачу: на какое количество слагаемых можно разбить число n, если все слагаемые должны быть степенями двойки с целыми неотрицательными степенями. Покажем, что для любого целого k от popcount(n) до n это возможно (где popcount(n) это количество установленных бит в двоичной записи n).
Очевидно, что нельзя использовать меньшее чем popcount(n) число слагаемых, и большее n. Если у нас есть разложение в x слагаемых (x < n), то среди них есть слагаемое 2t с положительной степенью t. Его мы можем заменить на два слагаемых 2t-1, получив разложение с (x+1) слагаемым. Разложение из popcount(n) слагаемых строится из двоичного представления числа.
Для решения задачи будет перебирать длину последовательности k (k ≥ 1), пока не найдем подходящее. Как показано выше, нужно найти минимальное k, что popcount(kn) ≤ k, а после этого построить требуемое разложение. Для ограничений задачи k не превосходит 60 (60 ⋅ (250 — 1) < 260 — 1 = 20 + 21 + … + 259).
Требуется чтобы в графе соединений не было мостов, следовательно степень всех вершин не менее двух. А так как сумма степеней всех вершин равна 2 ⋅ n + 2, то у нас возможны два случая:
- есть одна вершина степени 4;
- есть две вершины степени 3.
Рассмотрим первый случай. Граф представляет собой объединение двух циклов длины (m + 1) и (n — m) с общей вершиной. В этом случае нам нужно выбрать какие вершины попадут в первый цикл (остальные попадут во второй), и в каком порядке вершины окажутся на этих циклах. Общая формула имеет следующий вид
Рассмотрим второй случай. В графе есть две вершины степени три, которые соединены между собой цепочками ребер, на которых расположены все остальные (n-2) вершины. Сразу обратим внимание, что соединение с нулем дополнительных вершин (ребро) может быть только одно. Пусть на соединениях расположены a, b и c вершины (a ≤ b ≤ c). Рассмотрим несколько случаев:
- 0 ≤ a < b < c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
- 0 < a = b < c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
- 0 ≤ a < b = c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
- 0 < a = b = c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) .
Собирая все формулы вместе, получаем итоговый результат.
Для решения этой задачи обратимся к строковой терминологии. Бордером строки s называется какая строка y, что x начинается и заканчивается на y.
Тогда в задаче нам для каждого префикса исходного текста нужно найти максимальный по длине бордер, которых имеет еще хотя бы одно дополнительное вхождение. Для этого можно найти все бордеры префикса, и в порядке убывания длин найти найти первый, который имеет дополнительное вхождение.
Для поиска всех бордеров можно использовать префикс-функцию. Дополнительно вспомнив, что — длина максимального бордера, а длины всех бордеров префикса длины i можно перечислить, пройдя по последовательности и т.д.
Следующий интересный факт: у бордера длины всегда есть не менее трех вхождений: первое начинается в начале строки, второе заканчивает в позиции i, а третье заканчивается в позиции .
Следовательно, для полного решения задачи нам осталось научиться проверять, есть ли дополнительное вхождение максимального по длине бордера (длины ). Чтобы такое вхождение было, должна найтись позиция j (j < i), в которой . Для быстрой проверки такого неравенства достаточно хранить префиксный максимум значений префикс-функции.
Трудоемкость решения задачи линейная от длины текста.
contest.yandex.ru
Поисковые алгоритмы Яндекса
В этой статье вы найдете наиболее полную подборку информации обо всех алгоритмах поисковой системы Яндекс, а также ссылки на официальные источники этих данных.
Поисковый алгоритм — это определенная математическая формула, по которой поисковая система вычисляет, как именно должны ранжироваться сайты в поисковой выдаче. Как правило, большинство алгоритмов затрагивали либо ссылочные факторы, либо текстовый контент.
Непот фильтр — 2005 год
Вес внешних ссылок с сайтов, которые занимаются линкоторговлей, перестает учитываться.
Новая формула ранжирования — 2007 год
Теперь алгоритм зависим от запросов. Он по разному ранжирует однословные и многословные запросы. Это первый поисковый апдейт Яндекса, который был официально анонсирован Садовским на https://searchengines.guru/showthread.php?t=149644
Алгоритм Родео — 07.08.2007
Появление новой формулы ранжирования для запросов из одного слова. Теперь в выдаче по таким запросам преимущество отдается главным страницам.
Восьмерка SP 1
Снижение веса ссылок с главных страниц ресурсов. После этого апдейта вебмастера начинают покупать ссылки с внутренних страниц.
Гости из прошлого — 5 февраля 2008
Теперь ссылки с сайтов, которые находятся под Непот фильтром, получают минимальный вес, который стремится в нулю. Это означает, что теперь нельзя определять площадки, которые находятся под санкциями, с помощью меток в анкорах. Обсуждение этого фильтра началось с обсуждения на серче. https://searchengines.guru/showthread.php?t=201743
Крупный ссылочный апдейт — 18 марта 2008 года
Теперь ссылки с главных страниц полностью теряют свой вес. Большинство сайтов, которые держались в выдаче с помощью таких ссылок, полностью выпали из ТОП-10. Ссылки с внутренних страниц все еще работают.
Иноязычные документы — 4 апреля 2008 года
https://yandex.ru/blog/webmaster/535
Теперь в выдаче появляются иноязычные документы. Причина в том, что Яндекс теперь ведет поиск и по зарубежным сайтам.
Магадан — 16 мая 2008 года
https://yandex.ru/blog/webmaster/839
Первый именной поисковый алгоритм Яндекса. Теперь появилась выдача по информационным запросам. Также, Яндекс научился расшифровывать аббревиатуры и транслитерацию.
Магадан 2.0 — 2 июля 2008
https://yandex.ru/blog/webmaster/1062
С этим апдейтом Яндекс научился определять и ранжировать коммерческие запросы. Теперь очень важен фактор уникальности текстов, а возраст сайта уже не играет большой роли для ранжирования.
Изменения в алгоритме тИЦ — 28 августа 2008
https://yandex.ru/blog/webmaster/1439
Апдейт коснулся сайтов, которые накручивают тИЦ с помощью специальных алгоритмов. Их значение тИЦ резко снизилось до показателей от 0 до 10.
Находка — 11 сентября 2008
https://yandex.ru/blog/webmaster/1622
Зафиксировано значительное увеличение внутренних страниц. Теперь в выдаче по высокочастотным и среднечастотным запросам присутствуют не только главные страницы, но и внутренние. Морфологические изменения, в частотности, по запросам в единственном и множественном числе — разная выдача. В выдаче по коммерческим запросам можно встретить информационные страницы.
Арзамас (Анадырь) — 8 апреля 2009
https://yandex.ru/blog/webmaster/3255
Появление региональной выдачи. В Яндекс.Вебмастере появилась возможность привязки сайта к конкретному региону. При ранжировании запросов с неоднозначным значением в выдачу подмешиваются различные результаты.
Понижение страниц с popunder-баннерами — 30 апреля 2009
https://yandex.ru/blog/webmaster/3772
Яндекс объявил войну popunder рекламе из-за того, что она мешает пользователям, теперь такие сайты ранжируются ниже.
Арзамас 1.1 — 24 июня 2009
https://yandex.ru/blog/webmaster/4610
Улучшена формула регионального ранжирования для всех регионов, исключая Москву, Санкт-Петербург и Екатеринбург.
Страницы с clickunder ранжируются ниже — 11 августа 2009
https://yandex.ru/blog/webmaster/4967
Значительное понижение страниц с такой рекламой в поисковой выдаче.
Арзамас 1.2 — 20 августа 2009
https://yandex.ru/blog/webmaster/5055
Появление классификации геозависимости запросов. Теперь запросы делятся на геозависимые и геонезависимые.
АГС 17
https://www.searchengines.ru/008057.html
Фильтр, направленный на искоренение некачественного контента. Под него попадают сайты, которые содержат неуникальный, или мусорный контент. Симптомы — в индексе остается всего несколько страниц, а чаще всего только главная страница.
Снежинск — 17 ноября 2009
https://yandex.ru/blog/webmaster/5869
Первое применение алгоритма машинного обучения Матрикснет. В разы увеличено количество учитываемых при ранжировании параметров, благодаря чему качество поиска было серьезно улучшено.
АГС-30 — 18 декабря 2009
https://yandex.ru/blog/webmaster/6456
Улучшенная версия алгоритма АГС-17. Количество учитываемых в ранжировании параметров значительно увеличено, теперь учитывается около 100 факторов. Сайты с неактуальным контентом оказались под угрозой получения санкций.
Поиск Яндекса в каждом городе — 22 декабря 2009
https://yandex.ru/blog/webmaster/6895
Локальное ранжирование теперь работает не только для 19 крупнейших регионов, как это было ранее, а для 1250 городов по всей России.
21. Портяночный фильтр — 20 января 2010
Этот алгоритм является предшественником фильтра «Ты спамный». Накладывается за большие и длинные тексты, переспамленные ключевыми словами. Как правило, фильтр накладывался на страницу, содержащую «портянку» из текста.
Снежинск 1.1 — 10 марта 2010
https://yandex.ru/blog/webmaster/7465
Улучшена формула ранжирования по геонезависимым запросам для пользователей России.
Обнинск — 13 сентября 2010
https://yandex.ru/blog/webmaster/8403
Улучшено ранжирование по геозависимым запросам. Значительно увеличена формула ранжирования, почти в 2,5 раза. Такое внимание к ранжированию геозависимых запросов обусловлено тем, что они составляют почти 70% от всех запросов.
Улучшение определения авторства — 2 ноября 2010
https://yandex.ru/blog/webmaster/9118
Предпочтение в ранжировании теперь отдается авторским публикациям. Страницы с чужими текстами теперь ранжируются ниже.
Краснодар (Технология Спектр) — 15 декабря 2010
https://yandex.ru/blog/webmaster/9477
Алгоритм на основе пользовательской истории формирует нужные ответы на неоднозначные запросы. В основе этой технологии лежит статистика поисковых запросов по более чем 60-ти тематикам. Например, под поисковым запросом «Пушкин» может подразумеваться город или всем известный русский поэт. Алгоритм автоматически определяет, какой именно результат желает увидеть пользователь.
Более подробно про технологию вы сможете прочитать в статье нашего блога https://labrika.ru/blog/spektr
Обновление алгоритма ранжирования по геозависимым запросам — 17 декабря 2010
https://webmaster.yandex.ru/blog/9559
Преимущества в ранжировании по регионам получают местные сайты. Привязка сайта к конкретному региону становится более важна для продвижения по нему.
Фильтр за накрутку поведенческих факторов — 23 мая 2011
https://yandex.ru/blog/webmaster/10399
Яндекс объявляет войну программам накрутки, которые эмулируют действия пользователей на сайте. Позиции сайтов, на которых была замечена накрутка, были существенно понижены.
Рейкьявик — 17 августа 2011
https://yandex.ru/blog/company/38489
Каждый пользователь получает информацию в выдаче в соответствии со своими языковыми предпочтениями. В поиске по англоязычным запросам отображаются и страницы на русском языке, но если пользователь регулярно открывает англоязычные сайты, соответственно, они будут чаще отображаться в поиске. Алгоритм самообучаемый, поэтому, если меняются языковые предпочтения пользователя, то вместе с ними меняется и поисковая выдача.
Ты спамный — 13 сентября 2011
https://webmaster.yandex.ru/blog/11464
Обновление портяночного фильтра. Под угрозой оказались страницы с большим количеством текста, перенасыщенным ключевыми словами, также нежелательно, чтобы на странице было много выделений курсивом и жирным шрифтом. Тексты должны быть для людей, а не для роботов. Также, стали учитываться поведенческие факторы пользователей — под фильтр попадают только страницы с низким ПФ.
Яндекс начинает учитывать юзабилити сайтов — 5 октября 2011
https://yandex.ru/blog/webmaster/11888
Приоритет отдается сайтам с удобной структурой и навигацией. Сайты, которые неудобны для пользователей и имеют плохие поведенческие факторы, ранжируются ниже. Также, проблемы будут у сайтов, на которых рекламные баннеры мешают просмотру контента.
Новая формула ранжирования для коммерческих сайтов — 23 ноября 2011
https://yandex.ru/blog/webmaster/12443
При ранжировании сайтов учитываются дополнительные параметры, такие как наличие цен, разнообразие ассортимента продукции, различные возможности оплаты и доставки, доверие к компании и пользовательский интерфейс. Изначально, алгоритм применялся только к Московскому региону, но потом стал учитываться и в других регионах России.
Калининград (персональный поиск) — 12 декабря 2012
https://yandex.ru/company/press_releases/2012/1212/
Яндекс запускает персональный поиск, теперь при запросе пользователя учитывается история его предыдущих запросов, на основе которых формируются предполагаемые интересы пользователя. Например, при запросе «гарри поттер», пользователю, который любит читать, поисковая система, в первую очередь, покажет информацию о книге, а не о фильме или компьютерной игре.
Персональные подсказки для зарегистрированных пользователей — 7 февраля 2012
https://yandex.ru/blog/company/43447
При введении запроса в поисковую строку появляются не только популярные запросы, но и те запросы, которые пользователь уже вводил ранее.
Региональный поиск в Яндекс.Картинки — 16 февраля 2012
https://yandex.ru/blog/company/43792
Теперь по одному и тому же запросу пользователи из России, Беларуси, Украины и Казахстана могут видеть разные изображения, а именно, те, которые будут больше соответствовать их стране или региону.
Сайты с обманными pop-up элементами ранжируются ниже — 15 мая 2012
https://yandex.ru/blog/webmaster/13533
Ресурсы, которые содержат уведомления, обманывающие пользователей, теперь имеют меньший приоритет при ранжировании.
Дублин — 30 мая 2013
https://yandex.ru/company/press_releases/2013/0530/
https://yandex.ru/blog/company/66549
Теперь Яндекс учитывает не только персональные интересы пользователей, но и сиюминутные, и дает тот ответ, который хочет увидеть пользователь именно сейчас.
АГС-40 — 6 ноября 2013
https://yandex.ru/blog/webmaster/16272
Обновление всем известного алгоритма включило в себя дополнительные показатели, по которым поисковая машина определяет низкое качество сайта. Санкции, по-прежнему, накладываются автоматически.
Анонс алгоритма бессылочного ранжирования — 5 декабря 2013
https://yandex.ru/blog/webmaster/16843
Яндекс начинает вводить формулу ранжирования, которая не будет учитывать ссылки по коммерческим запросам.
Отмена учета ссылок в ранжировании коммерческих запросов — 12 марта 2014
https://yandex.ru/blog/webmaster/18092
Сначала алгоритм затронул только Московский регион и такие тематики как, например, недвижимость, туризм, электроника и бытовая техника.
Изменения в ранжировании страниц с шокирующей рекламой — 20 марта 2014
https://yandex.ru/blog/webmaster/18326
Страницы с отвлекающей рекламой (эротические баннеры, неприятные изображения и т. д.) стали ранжироваться ниже. Была отмечена положительная тенденция после внедрения изменений — количество страниц с шокирующей рекламой снизилось на 30%.
Изменения в работе алгоритма АГС — 15 апреля 2014
https://yandex.ru/blog/webmaster/18552
Очередное обновление алгоритма, задача которого бороться с некачественными сайтами. Теперь, вместо исключения страниц некачественного ресурса из поиска, у него будет обнуляться тИЦ .
Острова — 5 июня 2014
https://yandex.ru/blog/company/80704
Новый дизайн результатов поисковой выдачи. Позже Яндекс признал эксперимент неудачным и от данного нововведения пришлось отказаться.
Изменения в ранжировании страниц с назойливой рекламой — 22 сентября 2014
https://yandex.ru/blog/webmaster/19327
Очередное совершенствование алгоритма, направленного на борьбу с отвлекающей рекламой.
Пессимизация за накрутку поведенческих факторов — 1 декабря 2014
Под санкции попали сайты, которые накручивали переходы из поиска, а также ресурсы, которые использовали клики по покупным ссылкам, чтобы увеличить передаваемый ими вес.
Амстердам — 1 апреля 2015
В правой части результатов выдачи появляется информационный блок, в котором содержатся данные об объекте поиска.
Минусинск — 15 мая 2015
https://yandex.ru/blog/webmaster/20337
Сайты, которые используют для продвижения SEO-ссылки, теперь ранжируются ниже. Такие ограничения могут существенно снизить трафик из поисковых систем на несколько месяцев. Чтобы избежать неприятностей, Яндекс рекомендует полностью отказаться от SEO-ссылок и развивать web-ресурс.
https://yandex.ru/support/webmaster/yandex-indexing/algorithm-minusinsk.xml — все об алгоритме
Пессимизация за продажу ссылок с сайтов — 8 сентября 2015
https://yandex.ru/blog/webmaster/20960
Яндекс продолжает войну с методами продвижения, которые обманывают алгоритмы поисковой системы. Теперь за размещение SEO-ссылок на страницах сайт может попасть под пессимизацию — независимо от его качества. Как правило, ограничения в ранжировании сопровождаются обнулением тИЦ.
Многорукий бандит Яндекса — 14 сентября 2015
https://yandex.ru/blog/webmaster/20999
В ТОП-10 поисковой выдачи периодически подмешиваются новые страницы, которые еще не собрали нужного количества статистических данных для оценки поведенческих факторов. Это сделано для того, чтобы более молодые сайты могли конкурировать со старыми, надежно закрепившимися в поисковой выдаче. Возраст сайта уже не так важен для продвижения.
Опасные сайты — 2 октября 2015
https://yandex.ru/blog/webmaster/21119
https://yandex.ru/company/press_releases/2009/0526/ — об опасных сайтах. Теперь опасные сайты не только помечаются специальными предупреждениями в поисковой выдаче, но и ранжируются ниже.
Ссылки опять учитываются — 3 ноября 2015
На одной из лекций для вебмастеров от Яндекс сообщили, что ссылочное ранжирование опять работает для ряда тематик по Московскому региону.
Сайты с кликджекингом ранжируются ниже — 30 декабря 2015
https://yandex.ru/blog/webmaster/21745
Кликджекинг — это механизм обмана на сайтах, он связан с размещением на сайте невидимых элементов, с которыми пользователь взаимодействует, не подозревая об этом, при этом совершаются какие-либо действия. Такие сайты теперь ранжируются ниже.
Владивосток (Оптимизация для мобильных — теперь фактор ранжирования) — 2 февраля 2016
https://yandex.ru/blog/webmaster/optimizatsiya-dlya-mobilnykh-teper-faktor-ranzhirovaniya
Удобство использования сайта на мобильных устройствах становится фактором ранжирования. Теперь адаптивный дизайн или мобильная версия положительно учитываются при ранжировании ресурса.
Обновление алгоритма расчета тИЦ — 9 июня 2016
https://yandex.ru/blog/webmaster/obnovleniya-algoritma-rasch-ta-tits
Серьезным изменениям подверглись механизмы очистки ссылочного сигнала. Многие устаревшие показатели были исключены из алгоритма расчета.
Новый алгоритм Палех — 3 ноября 2016
https://yandex.ru/blog/webmaster/novyy-algoritm-palekh
https://habr.com/company/yandex/blog/314222/ — подробный разбор алгоритма.
Яндекс начал применять нейронные сети для поиска по смыслу. Новый алгоритм позволяет отвечать на сложные запросы, состоящие из большого количества слов и умеет находить документы не по словам, содержащимся в тексте, а по смыслу запроса и заголовка.
Алгоритм Баден-Баден 16 июня 2017
https://yandex.ru/blog/webmaster/baden-baden-novyy-algoritm-opredeleniya-pereoptimizirovannykh-tekstov
https://labrika.ru/blog/keis_po_vihodu_is_baden-baden — кейс по выводу сайта из-под фильтра Баден-Баден.
Обновление алгоритма, который определяет переоптимизированные тексты. Яндекс решил коренным образом бороться с SEO-текстами. Под этот фильтр массово начали попадать web-ресурсы, содержащие некачественные тексты с большим количеством ключевых слов. Попадание под фильтр сопровождается уведомлением в Яндекс.Вебмастер в разделе «Безопасность и нарушения». Сайты, попавшие в пессимизацию, резко теряют позиции в поисковой выдаче, а следовательно и трафик.
Алгоритм Королев — 22 августа 2017
https://yandex.ru/blog/webmaster/yandeks-predstavil-novyy-algoritm-korolev
Очень серьезное обновление поисковой системы. Мероприятие по запуску алгоритма было ярким и масштабным. Обновление в своей основе содержит алгоритм «Палех», но теперь нейронная сеть анализирует не только заголовок, но и всю страницу целиком. Это огромный шаг в сторону поиска по смыслу. Большое значение стала играть скрытая семантика — слова, которые относятся к одной и той же смысловой подгруппе и помогающие поисковой системе определить тематику страницы. Наше исследование на тему скрытой семантики вы можете прочитать — тут.
Запуск Турбо-страниц — 22 ноября 2017
https://yandex.ru/blog/webmaster/turbo-stranitsy-otkryty-dlya-vsekh
Появление в поисковой выдаче страниц, которые значительно ускоряют загрузку контента на мобильных устройствах. Пользователи моментально получают нужный контент и не уходят с ресурса из-за долгой загрузки. Создать турбо-страницы можно на любом сайте.
Фильтрация агрессивной рекламы — 5 февраля 2018
https://webmaster.yandex.ru/blog/s-5-fevralya-yandeks-brauzer-nachinaet-filtrovat-reklamu-razdrazhayuschikh-formatov
https://yandex.ru/support/webmaster/diagnosis/annoying-ads.html?utm_source=wmblog&utm_campaign=browser5
С первой недели февраля 2018 г. Яндекс прекращает использование на своих площадках раздражающих форматов рекламы, которые противоречат рекомендациям ассоциации IAB Russia. А также фильтрует такую рекламу в Яндекс Браузере. Проверить наличие на сайте раздражающей рекламы можно в разделе «Диагностика» Яндекс Вебмастера.
Борьба с некачественными турбо-страницами — 20 февраля 2018
https://webmaster.yandex.ru/blog/turbo-stranitsy-opyt-pervykh-trekh-mesyatsev
Яндекс объявляет о том, что с 5 марта 2018 г. некачественные турбо-страницы, содержимое которых не соответствует оригинальной версии, не будут появляться в Поиске, Дзене и Новостях. Их заменят оригинальными страницами сайта. Соответствующее предупреждение будет отображаться в Вебмастере.
Обновление алгоритма, определяющего влияние рекламы на удобство использования сайта — 24 апреля 2018
https://webmaster.yandex.ru/blog/o-reklame-kotoraya-vvodit-v-zabluzhdenie
Произошло обновление алгоритма, который используется для распознавания на сайте нарушения «Малополезный контент, некорректная реклама, спам». При наличии данного нарушения все страницы сайта могут ранжироваться ниже. Информация о нем отображается в Яндекс.Вебмастере в разделе «Диагностика» — «Безопасность и нарушения».
В результате обновления улучшилось определение страниц с рекламой, вводящей пользователей в заблуждение и мешающей навигации по сайту (например, маскирующейся под элементы интерфейса сайта).
Усиление внимания качеству ресурса — 1 июня 2018
https://webmaster.yandex.ru/blog/bolshe-vnimaniya-kachestvu
Яндекс заявил о внесении в основную метрику изменений с целью усиления учёта качества и оформления контента, удобства навигации по сайту, уместности и корректности рекламы.
Обновление алгоритма поиска в Яндекс.Картах — 3 августа 2018
https://webmaster.yandex.ru/blog/blyuda-v-poiske-po-kartam
Теперь посетители могут искать не только сами организации, но и товары из их прайс-листа. Обновление началось с поиска блюд из меню, загруженных в Яндекс.Справочник в формате XLSX.
Замена тИЦ на ИКС — 22 августа 2018
https://webmaster.yandex.ru/blog/yandeks-zamenyaet-tits-na-iks-novyy-pokazatel-kachestva-sayta
Яндекс перестает рассчитывать и отображать тематический индекс цитирования (тИЦ), определявший авторитетность ресурса по количеству и качеству ссылок на него. Его заменяет новый показатель — индекс качества сайта (ИКС). Под качеством сайта теперь в первую очередь понимается его востребованность аудиторией, способность удовлетворить запросы пользователей.
Усиление защиты пользователей от криптоджекинга — 21 сентября 2018
https://webmaster.yandex.ru/blog/yandeks-usilivaet-zaschitu-polzovateley-ot-kriptodzhekinga
Сайты, тайно использующие устройства пользователей для майнинга криптовалют, могут ранжироваться ниже в поисковой выдаче. При переходе на них пользователям будет выдаваться предупреждение. Владельцы сайтов, на которых будут обнаружены скрипты криптоджекинга, получат уведомление в сервисе Яндекс.Вебмастер в разделе «Безопасность и нарушения».
Обновленный поиск Андромеда — 19 ноября 2018
https://yandex.ru/blog/company/bolshoe-obnovlenie-poiska
Масштабное обновление поиска, содержащее более тысячи улучшений. Основные направления:
- увеличение количества быстрых ответов, которые можно получить прямо в выдаче;
- обновление формулы ранжирования — большее значение приобрели удобство для пользователей, наличие постоянной аудитории, полезного и ненавязчивого контента;
- возможность в один клик сохранять понравившиеся находки (ссылки, картинки, видео и т. д.) на сервисе Яндекс.Коллекции.
Обновление ИКС — 25 декабря 2018
https://webmaster.yandex.ru/blog/obnovlennyy-iks
Внесены коррективы в алгоритм расчета индекса качества сайта (ИКС) — в новой версии ИКС не присваивается сайтам, которые больше не содержат контента, а также при недостаточном количестве данных о сайте.
Защита пользователей от навязчивых оповещений — 10 января 2019
https://webmaster.yandex.ru/blog/zaschischaem-polzovateley-ot-navyazchivykh-opovescheniy
Сайты, которые вынуждают пользователя подписаться на рекламные оповещения, в результатах поиска ранжируются ниже и помечаются предупреждением об опасности.
HTTPS рассматривается как один из признаков качественного сайта — 21 февраля 2019
https://webmaster.yandex.ru/blog/https-kak-znak-kachestva-sayta
Яндекс объявляет использование защищенного протокола HTTPS одним из признаков безопасности сайта, который может быть учтен при ранжировании.
labrika.ru
Хронология алгоритмов Яндекса
Методика Яндекса по определению релевантности контента запросам пользователей претерпела многочисленные изменения со времени появления компании в 1997 году. Постоянно разрабатывались новые, усовершенствованные формулы ранжирования, но общественности эта внутренняя работа стала видна только с 2007 года. Тогда же алгоритмам стали присваиваться названия. Главные особенности каждого из них мы рассмотрим в краткой хронологии за последние десять лет.
«Версия 7» (02.07.07)
Обновлённый алгоритм с повышенным числом факторов был анонсирован только на специализированном форуме для вебмастеров.
«Версия 8» (20.12.07) и «Восьмерка SP1» (17.01.08)
Авторитетные сайты стали пользоваться преимуществом в ранжировании, появился фильтр для борьбы с накруткой ссылочных факторов.
«Магадан» (16.05.08) и «Магадан 2.0» (02.07.08)
Первые «именные» алгоритмы. Сначала увеличилось количество классификаторов веб-страниц и ссылок, модернизировалась база аббревиатур, в два раза возросло число факторов ранжирования, смягчилась фильтрация отбора документов, затем появились новые факторы для проверки уникальности контента и классификаторы коммерческих и геозапросов.
«Находка» (11.09.08)
Новый алгоритм стал учитывать стоп-слова в запросах. Также расширились словари Яндекса вследствие автообработки «оболочки» текста, модернизировалось машинное обучение.
«Арзамас»/«Анадырь» (10.04.09)
Самым важным нововведением стала зависимость характера выдачи от региона местонахождения пользователя, задавшего поисковый запрос. Также произошло снятие омонимии, улучшилась обработка многословных запросов. Впоследствии алгоритм получил несколько органических продолжений:
- «Арзамас 1.1» (24.06.09)– доработана формула для ряда регионов России;
- «Арзамас 1.2» (20.08.09)– стала учитываться геозависимость запросов;
- «Арзамас+16» (31.08.09) – дополнение 16-ю регионами для геозависимых запросов;
- «Арзамас 1.5» (23.09.09)– улучшенная общая формула для геонезависимых запросов и региональных запросов, где не применяется локализованный рейтинг;
- «Арзамас 1.5 SP1» (28.09.09)– заработала дополненная формула регионального поиска.
«Снежинск» (17.11.09)
Алгоритм был поставлен на платформу самообучающейся системы MatrixNet. Было добавлено несколько тысяч новых параметров ранжирования, проработана локальная выдача для девятнадцати российских регионов.
«Конаково» (22.12.09) и «Конаково 1.1» (10.03.10)
На 1250 российских городов расширилась база регионального ранжирования, затем обновилась формула для геонезависимых запросов. В выдаче хорошо поднялись некоммерческие информационные ресурсы.
«Обнинск» (13.09.10)
Алгоритм с перенастроенной формулой, повышенной производительностью, улучшенной обработкой геонезависимых запросов, ограниченным влиянием на рейтинг искусственных ссылок.
«Краснодар» (15.12.10)
В основу алгоритма была заложена поисковая технология «Спектр», которая помогла более чётко распознавать различные значения слов в запросах пользователей и разнообразить выдачу. Также улучшилась локализация геозависимых запросов.
«Рейкьявик» (17.08.11)
Алгоритм стал учитывать языковые предпочтения пользователей, выдавать два варианта ответов – с исправленной опечаткой в запросе и неизменный, и заложил основы персонализированной выдачи.
«Калининград» (12.12.12)
Произошла глобальная персонализация выдачи: возникли поисковые подсказки, избранные сайты стали выдаваться как наиболее релевантные. В продвижении сайтов стали комплексно учитываться множество факторов: качество контента и ссылочного профиля, юзабилити сайта, социальные сигналы и других.
«Дублин» (30.05.13)
Продолжалась и совершенствовалась персонализация поиска. Система стала подстраиваться под интересы пользователя прямо в процессе текущей поисковой сессии.
«Без ссылок» (12.03.14)
Было отменено несколько ссылочных факторов ранжирования по ряду коммерческих запросов в Москве (в сфере недвижимости, туризма, электроники и бытовой техники).
«Острова» (05.06.14)
Произошло обновление дизайна поисковой выдачи с помощью интерактивных ответов прямо на странице с результатами поиска. Позже этот эксперимент признали неудачным и свернули.
«Объектный ответ» (01.04.15)
Изменился внешний вид страницы с результатами поиска. Справа от результатов Яндекс стал показывать карточку запрашиваемого объекта с основной информацией, а также классифицировал в базу множество объектов поиска.
«Минусинск» (15.05.15)
Алгоритм понизил в рейтинге сайты с избытком искусственных ссылок в ссылочном профиле. В работах по продвижению Яндекс рекомендовал уделить внимание качеству контента и проработанности дизайна сайта.
«Многорукие бандиты Яндекса» (14.09.15 ± 3 месяца)
«Бандиты» рандомизировали поисковую выдачу, добавив в неё «молодые» ресурсы. Рандомизация проводилась для выявления дополнительных поведенческих особенностей.
«Владивосток» (02.02.16)
Алгоритм стал учитывать адаптированность сайта к мобильным устройствам. Более высокий рейтинг стали получать ресурсы, наиболее приспособленные для мобильного просмотра.
«Палех» (02.11.16)
С помощью нейронных сетей поиск стал производиться не формально по словам, а по смыслу запроса и Title, т.е. заголовку страницы. Целью этого алгоритма стал качественный поиск по редким запросам (например, заданный в естественном разговорном формате).
«Баден-Баден» (23.03.17)
Алгоритм с рядом дополнительных факторов, отвечающих за определение переоптимизированного контента и понижающий его ранжирование в выдаче.
«Королёв» (22.08.17)
Логическое продолжение «Палеха». С помощью технологии искусственного интеллекта алгоритм научился сопоставлять интенты на сайте и смысл запроса. В отличие от своего предшественника, «Королёв» анализировал не только Title, но и весь контент страницы.
«Андромеда» (19.11.18)
Новейший алгоритм с рядом нововведений, большая часть которых относится к отображению на странице выдачи различных колдунщиков и Яндекс-сервисов. Улучшены функции «быстрых ответов», появились метки на страницах («Популярный сайт», «Выбор пользователей» и т.п.). В основе «Андромеды» – новая метрика качества поиска Proxima. Она нацелена на максимально быстрый поиск релевантного ответа прямо в поисковой выдаче и учитывает множество аспектов: вероятность решения поставленной пользователем задачи на конкретной странице; лояльность пользователей; баланс релевантного и рекламного контента; индекс попарного сравнения сайта с аналогами. Proxima быстро обучается на основе разнообразных запросов, и качество ранжирования также растёт.
www.iseo.ru
Алгоритмы Яндекса — новые и старые, хронология за 2007-2017 года
Привет уважаемые читатели seoslim.ru! Тем, кто интересуется SEO и пытается развивать сайты правильно будет полезно узнать обо всех алгоритмах Яндекса, чтобы лучше понимать по каким критериям поисковая машина их ранжирует.
На протяжении всего времени Yandex постоянно вносит правки в работу алгоритмов: используются нейронные сети, устраняются ошибки, дорабатывается функционал, появляются новые фильтры и так далее.
Делается всё, чтобы выдача максимально точно отвечала на запросы пользователя.
По приведенным ссылкам вы узнаете о истории развитии компании, принципах работы поисковой машины и всех известных фильтрах.
В этой статье предлагаю всем освежить память и восстановить хронологию, дабы посмотреть, как происходила эволюция поисковых алгоритмов ранжирования Яндекса за период 2007 — 2017 годов.
Далее о каждом из них более подробно.
История алгоритмов Яндекса
«Безымянный или Версия 7» (июль 2007) — первый алгоритм, о котором было объявлено публике, цель которого улучшить релевантность выдачи.
Анонс на searchengines.guru
«8 SP1» (январь 2008) — после обновления в ТОП стали попадать старые авторитетные сайты, а ссылки стали товаром.
«Магадан» (май 2008) — запуск новой версии поиска, теперь поисковая программа могла решать ряд задач:
- Количество факторов ранжирования было удвоено.
- Алгоритмы могу быстро находить релевантные страницы, не дожидаясь обработки всех документов.
- Яндекс научился понимать слова, написанные транслитом и аббревиатуры.
- В выдаче стали отображаться сайты, не смотря на опечатки, которые исправляются автоматически.
- Расширение базы в несколько миллиардов страниц.
Анонс на yandex.ru/blog/
«Находка» (сентябрь 2008) — упор был сделан на изменения факторов ранжирования.
- Новый поход к машинному обучения.
- Учёт стоп-слов.
- Произошло расширение словарей Яндекса.
Анонс на yandex.ru/blog/
«Анадырь-Арзамас» (апрель 2009) — нововведения сильно пошатнули ТОП-выдачу.
Теперь молодым сайтам стало еще сложнее продвигаться, так как Яшка не могу определить их региональную принадлежность.
- Внедрение алгоритма «снятие омонимии», теперь Яндекс научился лучше понимать русский язык.
- Стал учитываться регион пользователя, и выдача менялась в зависимости от него.
- Был создан классификатор гео-зависимости запросов, когда в зависимости от запроса мог учитываться регион пользователя.
Релиз в yandex.ru/blog/
«Снежинск» (ноябрь 2009) — изменен подход к построению ранжирования, что позволило еще больше улучшить качество поиска.
- Появились фильтры АГС.
- Тестирование самообучающейся системы MatrixNet.
- Запуск дополнительных региональных факторов.
- Ухудшено ранжирование страниц с портянками текста.
- Первые места в выдаче отдаются первоисточнику, копипаст ранжируется хуже.
Анонс на yandex.ru/blog/webmaster/
«Конаково» (декабрь 2009) — был обновлением предыдущего алгоритма Снежинск.
- Появление новых операторов в поиске (*, / и др.).
- Расширение базы регионального ранжирования (добавлено 1250 городов России).
Релиз на yandex.ru/blog/webmaster/
«Обнинск» (сентябрь 2010) — запуск нового алгоритма, цель которого улучшить ранжирование по гео-независимым запросам.
- Снижено влияние seo-ссылок на поиск.
- Увеличен объем формулы ранжирования, который достиг 280 МБ.
- Расширение словаря транслитерации.
- Появилось понятие автор контента.
Подробнее в yandex.ru/blog/
«Краснодар» (декабрь 2010) — основой данного алгоритма стала технология «Спектр», которая могла отвечать на неточные запросы пользователей, благодаря разбавленным ответам из 60-ти категорий.
- Яндекс проиндексировал социальную сеть Вконтакте.
- Запросам стала присваиваться категория.
- Обновлено ранжирование по геозависимым запросам.
- Появились расширенные сниппеты.
Источник yandex.ru/blog/
«Рейкьявик» (август 2011) — теперь поиск стал персонализированным, то есть для каждого отображалась своя выдача.
- Появление колдунщиков, что позволило производить расчёты прямо в поиске.
- Обновлен алгоритм поисковых подсказок для новостных ресурсов.
- Тестирование программы «Оригинальные тексты».
Анонс запуска на yandex.ru/blog/company/
«Калининград» (декабрь 2012) — глобальная персонализация поисковой выдачи для запросов и подсказок.
- Обновление поисковых подсказок.
- Продвигать сайты теперь надо комплексно, теперь для Яндекса важны: ссылки, ключевые слова, дизайн, контент, юзабилити, соц. сигналы и другие факторы.
Источник yandex.ru/blog/
«Дублин» (май 2013) — следствие обновление предыдущего алгоритма Калининград.
Теперь персонализированный поиск мог реагировать на сиюминутные запросы пользователя.
Если раньше Яндекс обновлял данные об интересах пользователей раз в сутки, то теперь Яшка стал анализировать текущую поисковую сессию.
Подробнее на yandex.ru/company/
«Острова» (июль 2013) — запуск новой островной выдачи и сервисов.
Предполагалось, что пользователь будет решать свои вопросы прямо в выдаче без перехода на сайт с помощью интерактивных блоков, например, купить билет в кино или на самолёт, заказать столик в кафе и др.
Подробнее в yandex.ru/blog/company/
«Объектный ответ» (апрель 2015) — после запуска данной технологии в поиске справа, появилась карточка с общей информацией о предмете запроса. Подобное решение имеется и у Google.
Пример смотрите на yandex.ru/company/
«Минусинск» (май 2015) — цель этого алгоритма занижение позиций сайтов в выдаче, которые для продвижения используют SEO-ссылок в ссылочном профиле.
Яндекс рекомендуют вебмастерам больше уделять внимание улучшению сервисов на сайте, контенту и дизайну.
Подробнее yandex.ru/blog/webmaster/
«Владивосток» (февраль 2016) — новый алгоритм нацелен на учёт факторов мобилопригодности сайтов. Теперь в мобильном поиске будет большее значение отводиться сайтам, адаптированным под мобильный интернет.
Особенности алгоритма на yandex.ru/blog/
«Палех» (ноябрь 2016) — благодаря новому алгоритму Яндекс научился отвечать на сложные запросы пользователей.
Впервые в поиске стал использоваться искусственный интеллект, который с помощью нейронных сетей может понимать запросы пользователей не по словам, а по смыслу.
Подробно про работу алгоритма yandex.ru/blog/
«Баден-Баден» (март 2017) — алгоритм, который направлен на борьбу с переоптимизированными страницами. Если на сайте будут найдены подобные тексты, то позиции таких страниц или всего сайта в выдаче будут ухудшены.
Подобные нарушения отображаются в Яндекс.Вебмастере, раздел «Диагностика» — «Безопасность и нарушения».
Анонс алгоритма в yandex.ru/blog/webmaster/
«Королёв» (август 2017) — запуск новой версии поисковой выдачи или продолжение алгоритма Палех. Благодаря нейронной сети, Яндекс может наиболее точно давать ответы на сложные и многословные запросы.
Искусственный интеллект собирает данные на основе оценок пользователей, поисковой статистики, асессоров и толокеров.
Подробнее читайте на yandex.ru/blog/webmaster/
На этом все, с выходом нового алгоритма статья будет дополняться, так что добавьте ее в закладки, чтобы быть в курсе последний нововведений Яндекса.
seoslim.ru
Алгоритмы и структуры данных поиска. Лекции и курсы от Яндекса
Сегодня мы завершаем новогоднюю серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».В этом курсе рассматриваются базовые алгоритмы и структуры данных, включая хешировани, сложность и модели вычислений, деревья поиска, B-деревья, задачи геометрического поиска, динамическую связность в графах и другое.
Мы учли то, о чём нас просили в комментариях к прошлым курсам — теперь при желании можно не только смотреть/скачивать лекции по отдельности, но и загрузить всё разом в виде открытой папки на Яндекс.Диске. Кстати — в предыдущих постах тоже появились такие же апдейты (вот ссылки для удобства: «машинное обучение», «дискретный анализ и теория вероятностей», «параллельные и распределённые вычисления»).
Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.
Полный курс в виде папки на Яндекс.Диске
Лекция 1. Сложность и модели вычислений. Анализ учетных стоимостей (начало)
Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
Лекция 2. Анализ учетных стоимостей (окончание)
Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.
Лекция 3. Функции быстрой сортировки и сортировки слиянием
Понятие о методе «разделяй и властвуй». Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. K-way Merge-Sort для работы во внешней памяти. Сортировка слиянием без использования дополнительной памяти. Общая схема алгоритма Quick-Sort. Два варианта реализации Partition. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Элиминация хвостовой рекурсии. Задача об оптимальном дереве слияний. Коды Хаффмана. Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск «от края» (galloping).
Лекция 4. Порядковые статистики. Кучи (начало)
Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort.
Лекция 5. Кучи (начало). Хэширование (начало)
k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.
Лекция 6. Хэширование
Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).
Лекция 7. Деревья поиска (начало)
Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.
Лекция 8. Деревья поиска (окончание). Декартовы деревья
Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей.
Лекция 9. B-деревья. Система непересекающихся множеств
B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).
Лекция 10. Задачи RMQ и LCA
Задачи RMQ (range minimum query) и LCA (least common ancestor). Сведение от задачи RMQ к задаче LCA, декартово дерево. Алгоритм Таржана для offline-версии задачи LCA. Простейшие алгоритмы для online-версии задачи LCA: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для к задаче ±1-RMQ. Сведение задачи LCA к задаче ±1-RMQ: эйлеров обход дерева.
Лекция 11. Задачи геометрического поиска
Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.
Лекция 12. Динамическая связность в графах
Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение. Использование амортизации и набора остовных лесов для решения со сложностью O(log^2 n).
habr.com