Data Science: Алгоритмы и Структуры данных

Backtracking алгоритм (Поиск с возвратом) Один из самых известных алгоритмов по решению специфичных задач поиска - является Backtracking алгоритм. Это по факту даже техника для рекурсивного решения проблем, пытаясь построить решение постепенно, удаляя те решения, которые не удовлетворяют условиям. Данным алгоритмом решается ряд задач (очень схожих по смыслу): нахождение позиций шахматным фигурам, решение судоку, проблемы с раскраской, различные пазлы, гимильтоновый цикл и другие схожие тематики. Обратите внимание на картинку - там представлен способ решения нашей задачи N-Queens. Картинка очень удобна для понимания самого подхода и поможет вам уже воспроизвести алгоритм (рекурсивный) самостоятельно!

Наивное решение проблемы N-королев Вчера была интересная задача и я надеюсь, она многим понравилась! Однако пора приступить к способам ее решения. Начну я с самого простого способа (по факту перебора). Скорее всего вы этим способом и пользовались при выставлении королев(ферзей) на доске. Итак: 1. Создать цикл с проверкой того, что есть непроверенные конфигурации 2. Внутри цикла генерировать новую конфигурацию и если королевы не атакуют, тогда распечатать эту конфигурацию. Проблема данного подхода, я думаю, очевидна! Это глупый и наивный перебор абсолютно всех вариантов и он займет недопустимое количество времени. А вот хорошее решение, я сегодня уже подскажу, но расскажу о нем завтра. Есть такой подход как BackTracking - попробуйте посмотреть в его направлении.

Задача N - королев Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель. Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом. Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов: 1. попробуйте визуализировать данную проблему 2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений

​Математика в жизни не пригодится? Задача: Женя знает математику на уровне «посчитать зарплату после вычета налога» и «оставить курьеру 10% чаевых», при этом хочет работать в IT-сфере. Какова вероятность, что Женя сможет трудоустроиться? Ответ: Недостаточно данных. Зато данных всегда хватает в работе аналитиков и специалистов по Data Science. Выполнять задачи этим специалистам помогают электронные таблицы, базы данных, языки программирования и математика. Если ваши математические навыки остались, как у Жени, на уровне 7 класса школы, прокачайте их на курсе «Математика для анализа данных» от Практикума. И вероятность вашего трудоустройства пойдёт вверх 📈 Программа курса разработана с учётом требований IT-рынка и содержит все необходимые разделы: - Линейная алгебра: матрицы, векторы, нормы и определители. - Математический анализ: функции и их свойства, производные и интегралы. - Линейная регрессия, коллинеарность, визуализация и другие приложения алгебры в анализе данных. - Теория вероятностей и статистика: гипотезы, A/B-тесты и бутстрэп. А в конце курса студенты проходят математическое собеседование в тренажёре-симуляторе. Итого: Начать учиться можно бесплатно и в любой момент. Специальная подготовка не нужна. После регистрации и оплаты вы получаете доступ к полному курсу, рассчитанному на 4 месяца. Обучение стоит 30 000 ₽ единоразово или в рассрочку — от 1 631 ₽/мес.

Для чего и как построить 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. Если наоборот больше: то можно расширить интервал

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}

Задача на бинарные строки Давайте сначала разберемся что такое бинарные строки! На самом деле тут ничего сложного: это строки которые могут содержать только 2 различных символа. К примеру a и b: abbbbaaa А теперь после теории, перейдем к задаче. Преобразуйте данную строку в строку, в которой не будет содержаться значение подстроки "ab". Чтобы убрать "ab", мы можем пользоваться операциями, в которой мы заменим эту подстроку на "bba". Основная цель данной задачи, найти общее количество операций, которые необходимы для преобразование данной строки. Input : s = 'abbaa' Output : 2 Объяснение: Тут, 'ab'baa заменяется на s = bbabaa bb'ab'aa а тут на s = bbbbaaa Нам потребовалось 2 операции на это. Попробуйте решить данную задачу.

🎉 Среди студентов МГУ прошло голосование на 3 лучших телеграм-канала по программированию. Поздравляем победителей: Просто Python – канал для всех, кто хочет освоить самый перспективный язык 2022 года. Гайды для новичков, шпаргалки, фишки, программы и многое другое. Этичный Хакер – уроки по хакингу, инструкциии по взлому, деанону, защите устройств и бесплатными курсами по информационной безопасности. IT-Сэнсэй - хранилище бесплатных курсов и плейлистов по программированию от топовых онлайн-школ и преподавателей.

Разница между 2мя большими числами 1. Поверните обе строки (чтобы конец стал началом) - reverse string operation. Создайте пустую строку для результата 2. Продолжайте вычитать цифры одну за одной из 0го индекса(в повернутых строка) - до конца меньшей строки, добавьте разницу, если она положительна в конец результата. Если разница отрицательна, то прибавьте 10 и отслеживайте перенос как +1, если положительный, то перенос равен 0 3. Снова переверните результативную строку Как видите: чтобы посчтитать разницу между 2мя строками - мы используем обычную математику(якобы в столбик)

Разница между 2мя большими числами Даны два числа в виде строк. Числа могут быть очень большими (не помещаться в long long int), задача - найти разницу этих двух чисел.

Структура данных - строки Строки определяются как массив символов. Разница между символьным массивом и строкой заключается в том, что строка заканчивается специальным символом "\0" Объвить строку так же просто как объявить одномерный массив. Обращаю особое ваше внимание, что каждый символ строки хранится отдельно в ячейке. И как одномерный массив - строки имеют всё те же свойства.

Топологическая сортировка Самый простой вариант данной сортировки - это изменение DFS обхода. В DFS мы начинаем с вершины, сначала выводим ее на печать, а зачем рекурсивно вызываем DFS для смежных вершин. В топологической сортировке - мы будем использовать стек! Мы не будем печатать сразу наши вершины, мы будем сначала вызывать рекурсивно топологическую сортировку для всех вершин, а после их записывать в стек. В результате мы распечатаем содержимое стека. Самое важное, что вершина помещается только тогда, когда все ее смежные вершины находятся в стеке.

Senior Pack — это книги, юмор и новости. Собрали для вас все самое основное: Сливы платных книг для программирования: 📚 Полка Разработчика 📖 Кладовая Книг 🗄 Архив Разработчика 🚽 IT Memes — свежий IT юмор, отобранный нейросетью; 🗞 3D News — актуальные новости из IT-индустрии.

Топологическая сортировка Топологическая сортировка для ориентированного ациклического графа (DAG) - это линейное упорядочение вершин таким образом, что для каждого направленного ребра u-v: вершина u идет перед v в порядке. Топологическая сортировка для графа невозможна, если граф не является DAG. Завтра мы рассмотрим саму сортировку!

Как определить зацикливание в ориентированном графе Проблема: дан ориентированный граф. Необходимо проверить содержит ли граф цикл или нет Алгоритм 1. Создайте граф, используя заданное количество ребер и вершин (условно, если граф еще не создан) 2. Создайте рекурсивную функцию, которая инициализирует текущий индекс или вершину, а также создает стек рекурсии 3. Отметьте текущий узел как посещенный, а также отметьте индекс в стеке рекурсии 4. Найдите все вершины, которые примыкают к данному узлу(но еще ни разу не посещались). Рекурсивно вызывайте данную функцию для этих вершин. 5. Если рекурсивный вызов вернет - true - значит это и есть истина и ваш финальный ответ. Кстати, если соседние вершины уже присутствуют в стеке рекурсии - вы можете сразу вернуть true

Алгоритм транспонирования графа Мы проходим по списку смежности, и когда мы находим вершину v в списке смежности вершины u, которая указывает на ребро от u до v в основном графе, мы просто добавляем ребро от v до u в транспонированный граф, т.е. добавляем u в смежность список вершины v нового графа. Таким образом, обходя списки всех вершин основного графа, мы можем получить транспонированный граф. Таким образом, общая временная сложность алгоритма составляет O (V + E), где V - количество вершин графа, а E - количество ребер графа.

Найти работу в сфере айти можно 2 методами: Первый. Бесконечно скроллить HeadHunter и пытаться что-то выклевать на LinkedIn. Офигеть от условий и закрыть. Второй. Подписаться на IT Jobs. Это база адекватных предложений, где даже для новичков много мест с хорошей з/п. Тут найдете работу как в Яндексе (именно сюда крупняки присылают вакансии напрямую), так и в молодых стартапах! В общем, не теряйте времени и находите работу в 2 клика: @devs_it

Транспонирование графа У многих графов есть еще одно условие, то что их можно транспонировать. Давайте сначала разберемся с тем, что же такое транспонирование. Транспонированый ориентированный граф G - это другой ориентированный граф на том же множестве вершин со всеми ребрами, перевернутыми по сравнению с ориентацией соответствующих ребер в G. То есть, если G содержит ребро (u, v), то обратное (transpose / reverse) G содержит ребро (v, u) и наоборот.

Простой алгоритм для задачи нахождения материнской вершины Самым тривиальным способом решения данной задачи будет выполнение BFS/DFS для всех вершин и выяснить: сможем ли мы достичь всех вершин из этой вершины. Данный подход неэффективен, если наши графы достаточно большие, ибо его время будет O(V(E + V)). Однако, это самый простой путь для решения подобных задач. К тому же, мы недавно рассмотрели BFS / DFS

Задача: найти материнскую вершину в графе Итак нам дан граф, нам нужно найти материнскую вершину. Материнской вершиной в графе G = (V, E) называется вершина v такая, что все остальные вершины в G могут быть достигнуты путем из v. Есть несколько кейсов, которые позволяют это сделать. 1. Ненаправленный связанный граф - в этом случае все вершины являются материнскими вершинами, поскольку мы можем достичь все другие узлы в графе из выбранного 2. Ненаправленный/Направленный исключенный граф - в этом случае нет материнских вершин, поскольку мы не можем достичь всех узлов из выбранного 3. Направленный связнфй граф - в этом случае мы должны найти вершину v в графе, что удостоена условию "маринский"