Z - алгоритм
Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна n, а длина шаблона - m, тогда общее затраченное время составит O(m+n) с линейной пространственной сложностью. Для этого мы строим специальный Z-массив.
Что такое Z массив?
Для строки str0..n-1 массив Z имеет ту же длину, что и строка. Элемент Zi массива Z хранит длину самой длинной подстроки, начиная с Zi, которая таке является префиксом str0..n-1
Пример:
str = "aaaaaa"
Z = {x, 5, 4, 3, 2, 1}
Data Science: Алгоритмы и Структуры данных | Чат 💬
Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна n, а длина шаблона - m, тогда общее затраченное время составит O(m+n) с линейной пространственной сложностью. Для этого мы строим специальный Z-массив.
Что такое Z массив?
Для строки str0..n-1 массив Z имеет ту же длину, что и строка. Элемент Zi массива Z хранит длину самой длинной подстроки, начиная с Zi, которая таке является префиксом str0..n-1
Пример:
str = "aaaaaa"
Z = {x, 5, 4, 3, 2, 1}
Data Science: Алгоритмы и Структуры данных | Чат 💬
❤2
Для чего и как построить Z-массив
Идея состоит в том: чтобы объеденить темплейт и текст и создать единую строку, а после для нее построить Z-array. Если что, на все это нам понадобиться не больше чем линейное время. А вот для построения самого Z-array нам уже понадобиться квадратичная функция.
Для построения нам придется поддерживать определенный интервал L,R, который по факту и содержит необходимую подстроку. Шаги следующие:
1.Если i-шаг> R, то нет префиксной подстроки, которая начинается перед i и заканчивается после i. Поэтому сбрасываются L и R и вычисляются новые
2. Если i <= R, то K = i - L, и тем самым Zi >= min(ZK, R-i + 1)
Появляются 2 случая тогда:
1. Если ZK < R-i + 1 то нет префиксной подстроки и интервал остается прежним
2. Если наоборот больше: то можно расширить интервал
Data Science: Алгоритмы и Структуры данных | Чат 💬
Идея состоит в том: чтобы объеденить темплейт и текст и создать единую строку, а после для нее построить Z-array. Если что, на все это нам понадобиться не больше чем линейное время. А вот для построения самого Z-array нам уже понадобиться квадратичная функция.
Для построения нам придется поддерживать определенный интервал L,R, который по факту и содержит необходимую подстроку. Шаги следующие:
1.Если i-шаг> R, то нет префиксной подстроки, которая начинается перед i и заканчивается после i. Поэтому сбрасываются L и R и вычисляются новые
2. Если i <= R, то K = i - L, и тем самым Zi >= min(ZK, R-i + 1)
Появляются 2 случая тогда:
1. Если ZK < R-i + 1 то нет префиксной подстроки и интервал остается прежним
2. Если наоборот больше: то можно расширить интервал
Data Science: Алгоритмы и Структуры данных | Чат 💬
16 сентября в Arena Breakout: Infinite выходит седьмой сезон — «Утопия»
Если не сталкивались с игрой: это бесплатный тактический шутер про вылазки за добычей. Заходишь на локацию со своим снаряжением, набираешь лут и пытаешься уйти живым. Погиб — потерял всё, что было с собой.
Что завозят в новом сезоне:
• Заражённая зона — три карты превращаются в биоопасные локации с ночью, туманом и ливнем, по ним бродят шесть видов мутантов. Другие игроки при этом никуда не делись
• Режим на выживание — отдельный PvE без риска: снаряжение с собой не берёшь и ничего не теряешь, просто отбиваешься от волн и открываешь усиления
• Торговец прямо в рейде — можно обменять припасы и разведданные или докупить снаряжение
• Два новых ствола, сезонные обвесы и переработанная стрельба: дальность выше, попадания в голову ощутимее
• На старте бесплатно выдают прокачиваемую сапёрную лопату, скины и билеты, а между игроками разыгрывают 200 000 очков
Игра бесплатная, качается в Steam, российский регион поддерживается → https://abi.go.link/2wzTb
Если не сталкивались с игрой: это бесплатный тактический шутер про вылазки за добычей. Заходишь на локацию со своим снаряжением, набираешь лут и пытаешься уйти живым. Погиб — потерял всё, что было с собой.
Что завозят в новом сезоне:
• Заражённая зона — три карты превращаются в биоопасные локации с ночью, туманом и ливнем, по ним бродят шесть видов мутантов. Другие игроки при этом никуда не делись
• Режим на выживание — отдельный PvE без риска: снаряжение с собой не берёшь и ничего не теряешь, просто отбиваешься от волн и открываешь усиления
• Торговец прямо в рейде — можно обменять припасы и разведданные или докупить снаряжение
• Два новых ствола, сезонные обвесы и переработанная стрельба: дальность выше, попадания в голову ощутимее
• На старте бесплатно выдают прокачиваемую сапёрную лопату, скины и билеты, а между игроками разыгрывают 200 000 очков
Игра бесплатная, качается в Steam, российский регион поддерживается → https://abi.go.link/2wzTb
Задача N - королев
Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель.
Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом.
Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов:
1. попробуйте визуализировать данную проблему
2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений
Data Science: Алгоритмы и Структуры данных | Чат 💬
Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель.
Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом.
Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов:
1. попробуйте визуализировать данную проблему
2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений
Data Science: Алгоритмы и Структуры данных | Чат 💬
Telegram
Data Science: Алгоритмы и Структуры данных
Мы не претендуем на оригинальность контента, мы лишь собираем материал из открытых источников.
Ссылка: @Portal_v_IT
Сотрудничество, авторские права: @oleginc, @tatiana_inc
Канал на бирже: https://telega.in/c/structuredata
Ссылка: @Portal_v_IT
Сотрудничество, авторские права: @oleginc, @tatiana_inc
Канал на бирже: https://telega.in/c/structuredata
Машинное обучение: анализ временных рядов Azure Machine Learning для поиска аномалий
В данной статье автор рассказывает, как использовать модуль Time Series Anomaly Detection сервиса машинного обучения Azure Machine Learning для определения аномальных показателей датчиков.
➡️ Читать статью
Data Science: Алгоритмы и Структуры данных | Чат 💬
В данной статье автор рассказывает, как использовать модуль Time Series Anomaly Detection сервиса машинного обучения Azure Machine Learning для определения аномальных показателей датчиков.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Наивное решение проблемы N-королев
Вчера была интересная задача и я надеюсь, она многим понравилась! Однако пора приступить к способам ее решения. Начну я с самого простого способа (по факту перебора). Скорее всего вы этим способом и пользовались при выставлении королев(ферзей) на доске.
Итак:
1. Создать цикл с проверкой того, что есть непроверенные конфигурации
2. Внутри цикла генерировать новую конфигурацию и если королевы не атакуют, тогда распечатать эту конфигурацию.
Проблема данного подхода, я думаю, очевидна! Это глупый и наивный перебор абсолютно всех вариантов и он займет недопустимое количество времени.
А вот хорошее решение, я сегодня уже подскажу, но расскажу о нем завтра. Есть такой подход как BackTracking - попробуйте посмотреть в его направлении.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Вчера была интересная задача и я надеюсь, она многим понравилась! Однако пора приступить к способам ее решения. Начну я с самого простого способа (по факту перебора). Скорее всего вы этим способом и пользовались при выставлении королев(ферзей) на доске.
Итак:
1. Создать цикл с проверкой того, что есть непроверенные конфигурации
2. Внутри цикла генерировать новую конфигурацию и если королевы не атакуют, тогда распечатать эту конфигурацию.
Проблема данного подхода, я думаю, очевидна! Это глупый и наивный перебор абсолютно всех вариантов и он займет недопустимое количество времени.
А вот хорошее решение, я сегодня уже подскажу, но расскажу о нем завтра. Есть такой подход как BackTracking - попробуйте посмотреть в его направлении.
Data Science: Алгоритмы и Структуры данных | Чат 💬
❤1
Backtracking алгоритм (Поиск с возвратом)
Один из самых известных алгоритмов по решению специфичных задач поиска - является Backtracking алгоритм. Это по факту даже техника для рекурсивного решения проблем, пытаясь построить решение постепенно, удаляя те решения, которые не удовлетворяют условиям.
Данным алгоритмом решается ряд задач (очень схожих по смыслу): нахождение позиций шахматным фигурам, решение судоку, проблемы с раскраской, различные пазлы, гимильтоновый цикл и другие схожие тематики.
Обратите внимание на картинку - там представлен способ решения нашей задачи N-Queens. Картинка очень удобна для понимания самого подхода и поможет вам уже воспроизвести алгоритм (рекурсивный) самостоятельно!
Data Science: Алгоритмы и Структуры данных | Чат 💬
Один из самых известных алгоритмов по решению специфичных задач поиска - является Backtracking алгоритм. Это по факту даже техника для рекурсивного решения проблем, пытаясь построить решение постепенно, удаляя те решения, которые не удовлетворяют условиям.
Данным алгоритмом решается ряд задач (очень схожих по смыслу): нахождение позиций шахматным фигурам, решение судоку, проблемы с раскраской, различные пазлы, гимильтоновый цикл и другие схожие тематики.
Обратите внимание на картинку - там представлен способ решения нашей задачи N-Queens. Картинка очень удобна для понимания самого подхода и поможет вам уже воспроизвести алгоритм (рекурсивный) самостоятельно!
Data Science: Алгоритмы и Структуры данных | Чат 💬
Математика в машинном обучении
В данном видео автор ответит на вопрос, нужно ли знать математику, чтобы заниматься машинным обучением и рассмотрит 4 основные математические дисциплины, составляющие машинное обучение - линейная алгебра, теория вероятностей, исчисление и статистика. А также, на примерах, покажет, как их использовать.
➡️ Смотреть видео
⬇️ Скачать видео
Data Science: Алгоритмы и Структуры данных | Чат 💬
В данном видео автор ответит на вопрос, нужно ли знать математику, чтобы заниматься машинным обучением и рассмотрит 4 основные математические дисциплины, составляющие машинное обучение - линейная алгебра, теория вероятностей, исчисление и статистика. А также, на примерах, покажет, как их использовать.
⬇️ Скачать видео
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM
Очень простое объяснение сложности алгоритмов
Иногда я нахожу на просторах интернета очень неплохие статьи, которыми могу поделиться. Сегодня одна из таких, которая позволит вам на базовом уровне разобраться что же такое сложность алгоритмов:
https://thatcomputerscientist.com/big-o-notation-explained-as-easily-as-possible
Для более глубокого изучения данного вопроса я порекомендую курс Роберта Седжевика:
https://www.coursera.org/learn/analysis-of-algorithms
Он максимально позволит вам овладеть данной темой.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Иногда я нахожу на просторах интернета очень неплохие статьи, которыми могу поделиться. Сегодня одна из таких, которая позволит вам на базовом уровне разобраться что же такое сложность алгоритмов:
https://thatcomputerscientist.com/big-o-notation-explained-as-easily-as-possible
Для более глубокого изучения данного вопроса я порекомендую курс Роберта Седжевика:
https://www.coursera.org/learn/analysis-of-algorithms
Он максимально позволит вам овладеть данной темой.
Data Science: Алгоритмы и Структуры данных | Чат 💬
XOR Linked List
Начнем рассматривать сложные структуры данных. Сегодня начнем одной из таких: XOR связный список.
Обычный двусвязный список требует места для двух адресных полей для хранения адресов предыдущего и следующего узлов. Версия двусвязного списка с XOR может быть создана с использованием только одного пространства для адресного поля с каждым узлом.
В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Начнем рассматривать сложные структуры данных. Сегодня начнем одной из таких: XOR связный список.
Обычный двусвязный список требует места для двух адресных полей для хранения адресов предыдущего и следующего узлов. Версия двусвязного списка с XOR может быть создана с использованием только одного пространства для адресного поля с каждым узлом.
В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.
Data Science: Алгоритмы и Структуры данных | Чат 💬
6 шагов, которые помогут стать специалистом по Data Science
Давно думали разобраться в науке о данных, но не знали, с чего начать? Мы собрали материалы, которые помогут стать специалистом по Data Science.
➡️ Читать статью
Data Science: Алгоритмы и Структуры данных | Чат 💬
Давно думали разобраться в науке о данных, но не знали, с чего начать? Мы собрали материалы, которые помогут стать специалистом по Data Science.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM
Продолжение обсуждения про XOR Linked List
Итак, я предлагаю перед тем как продолжать более детально смотреть на определенные примеры и задачи по данной теме. Всё таки немного глубже посмотреть на данную структуру.
Я нашел идеальную статью по этой теме:
https://www.linuxjournal.com/article/6828?page=0,0
Не обращайте внимание на дату создания. Ибо этот топик актуален до сих пор. Ну и плюсом будет в принципе глянуть на Linux Journal: там публиковалось очень много интересных топиков в свое время.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Итак, я предлагаю перед тем как продолжать более детально смотреть на определенные примеры и задачи по данной теме. Всё таки немного глубже посмотреть на данную структуру.
Я нашел идеальную статью по этой теме:
https://www.linuxjournal.com/article/6828?page=0,0
Не обращайте внимание на дату создания. Ибо этот топик актуален до сих пор. Ну и плюсом будет в принципе глянуть на Linux Journal: там публиковалось очень много интересных топиков в свое время.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Обход связного XOR списка
Продолжаем тему XOR Linked List и сегодня поговорим про обходы данного листа.
Перемещаться по списку XOR мы можем как в прямом, так и в обратном направлении. Просматривая список, нам нужно запоминать адреса узла, к которому ранее осуществлялся доступ, чтобы вычислить адрес следующего узла.
Например когда мы находимся в узле С, у нас должен быть адрес B. Из XOR мы выщемляем адрес для C, а при помощи C (и функции npx) мы можем узнать адрес следующей ноды.
Завтра посмотрим на SourceCode для полного понимания данного процесса.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Продолжаем тему XOR Linked List и сегодня поговорим про обходы данного листа.
Перемещаться по списку XOR мы можем как в прямом, так и в обратном направлении. Просматривая список, нам нужно запоминать адреса узла, к которому ранее осуществлялся доступ, чтобы вычислить адрес следующего узла.
Например когда мы находимся в узле С, у нас должен быть адрес B. Из XOR мы выщемляем адрес для C, а при помощи C (и функции npx) мы можем узнать адрес следующей ноды.
Завтра посмотрим на SourceCode для полного понимания данного процесса.
Data Science: Алгоритмы и Структуры данных | Чат 💬
❤1
7 трюков для глубокого обучения, о которых вы не знали
Неочевидные приемы для глубокого обучения, сокращающие время выполнения моделей и повышающие точность их результатов. Код прилагается.
➡️ Читать статью
Data Science: Алгоритмы и Структуры данных | Чат 💬
Неочевидные приемы для глубокого обучения, сокращающие время выполнения моделей и повышающие точность их результатов. Код прилагается.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM
Структура данных - Префиксное(нагруженное) дерево - Trie
Сегодня (и последующие несколько дней) разберем еще одну продвинутую структуру данных: Trie
Префиксное дерево (Trie) - эффективная структура данных для поиска информации. Используя Trie, сложность поиска у вас сведется к длине ключа, что является оптимальным пределом.
Используя Trie - вы можете икать и вставлять ключ за О(M): где M максимальная длина строки. Однако будет штраф за то как это хранится.
Еще плюсом Trie будет являеться то, что вы легко сможете вывести все слова в алфавитном порядке
А также поможет вам эффективно решать задачи по поиску префикса(суффикса). Задачу подобную я скоро опубликую: она как раз была недавно в leetcode challenge
Data Science: Алгоритмы и Структуры данных | Чат 💬
Сегодня (и последующие несколько дней) разберем еще одну продвинутую структуру данных: Trie
Префиксное дерево (Trie) - эффективная структура данных для поиска информации. Используя Trie, сложность поиска у вас сведется к длине ключа, что является оптимальным пределом.
Используя Trie - вы можете икать и вставлять ключ за О(M): где M максимальная длина строки. Однако будет штраф за то как это хранится.
Еще плюсом Trie будет являеться то, что вы легко сможете вывести все слова в алфавитном порядке
А также поможет вам эффективно решать задачи по поиску префикса(суффикса). Задачу подобную я скоро опубликую: она как раз была недавно в leetcode challenge
Data Science: Алгоритмы и Структуры данных | Чат 💬
Актуальная математика: самый понятный курс по анализу данных
Актуальная математика – это курс, который поможет понять, как работает анализ данных и поиск информации на примерах специалистов.
➡️ Читать статью
Data Science: Алгоритмы и Структуры данных | Чат 💬
Актуальная математика – это курс, который поможет понять, как работает анализ данных и поиск информации на примерах специалистов.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM
Описание операции вставки в Trie
Каждый узел в Trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный символ-ключ. Интересно то, что последний узел каждого поддерева Trit - будет являться концом слова.
Простая структура Node выглядит примерно так:
1. Инициализация детей
2. флаг о конце слова
Вставка в Trie - одна из простых операций. Каждый символ вставляется как отдельный узел Trie. Важно, обратить внимание, что дочерние элементы - это массив указателей(ссылок) на узлы дерева следующего уровня. Ключевой символ действует как индекс в дочернем массиве. Если входной ключ новый или расширенный - нам нужно построить таким образом ключи и пометить конец слова флагом конца. Длина ключа - определляет нашу глубину Trie.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Каждый узел в Trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный символ-ключ. Интересно то, что последний узел каждого поддерева Trit - будет являться концом слова.
Простая структура Node выглядит примерно так:
1. Инициализация детей
2. флаг о конце слова
Вставка в Trie - одна из простых операций. Каждый символ вставляется как отдельный узел Trie. Важно, обратить внимание, что дочерние элементы - это массив указателей(ссылок) на узлы дерева следующего уровня. Ключевой символ действует как индекс в дочернем массиве. Если входной ключ новый или расширенный - нам нужно построить таким образом ключи и пометить конец слова флагом конца. Длина ключа - определляет нашу глубину Trie.
Data Science: Алгоритмы и Структуры данных | Чат 💬
❤1
Если вы хотите серьезно погрузиться в AI, то Вам просто необходимо освежить свои математические навыки!
В данном видео автор описывает свою стратегию максимально быстрого изучения математики.
➡️ Смотреть видео
⬇️ Скачать видео
Data Science: Алгоритмы и Структуры данных
В данном видео автор описывает свою стратегию максимально быстрого изучения математики.
⬇️ Скачать видео
Data Science: Алгоритмы и Структуры данных
Please open Telegram to view this post
VIEW IN TELEGRAM