Алгоритмы *

Алгоритм бинарного (или двоичного) один из базовых алгоритмов, которые часто используется при решении алгоритмических задач. На LeetCode на момент написания этой статьи порядка 190 задач в решении которых он используется (можно посмотреть это здесь: https://leetcode.com/tag/binary-search/). Бинарный поиск разбирается во множестве статей, его идея достаточно несложная и интуитивно понятная. Однако алгоритм имеет некоторое количество "подводных камней". В этой заметке я хотел бы показать решение одной из задач с его помощью.

Этот пост о том, как можно решить задачу разбора строки по контектстно-свободной грамматике с помощью SMT-решателя. Здесь будет введение в тему, описание принципов работы и ссылка на github с работающей программой.

Суффиксное дерево (Suffix Tree, ST) – это структура данных, которая позволяет "проиндексировать" строку за линейное время от её длины, чтобы потом быстро находить подстроки (за время О(длина искомой подстроки)).

Тема построения Suffix Tree и его применения хорошо раскрыта в Интернет (википедия, статья на хабр про алгоритм Вейнера, язык Си, и статья на хабр про алгоритм Укконена). Но всегда есть соблазн поучаствовать в соревновании "написать проще и яснее", хотя шансов мало. Тем не менее, рискну.

Несмотря на сложность, алгоритм построения ST умещается в 35 строк на python (см. ниже метод _build_tree). Их буквально можно выучить и воспроизводить по памяти как некое произведение искусства, как воплощенный в набор символов труд человеческой мысли, причём не одного человека, и первые из них точно гении. :) Есть соблазн, всматриваясь в код, прикоснуться к великому и чему-то научиться.

С вашим языком программирования все в порядке — он просто производит вычисления с плавающей запятой. Изначально компьютеры могут хранить только целые числа, так что им нужен какой-то способ представления десятичных чисел. Это представление не совсем точное. Именно поэтому, чаще всего, 0.1 + 0.2 != 0.3.

ИТ-эксперт Эрик Уиффин, директор по инжинирингу компании Devetry, провел любопытный эксперимент: сравнил вывод в разных языках программирования при вычислениях с плавающей запятой. В рамках опыта автор продемонстрировал специфику выполнения одной и той же математической операции в нескольких десятках языков.

Предлагаем хабрасообществу наш перевод этого материала. Обращаем ваше внимание, что позиция автора не всегда может совпадать с мнением МойОфис.

Здравствуйте, друзья! Данным постом мы открываем цикл статей об алгоритмах и структурах данных.

В этой статье мы поговорим о том, зачем вообще их нужно знать веб-разработчикам, и затронем тему оценки сложности алгоритмов и Big O нотации.

Зачем мне алгоритмы? Я фронтендер!

Вы наверняка задумались: «А зачем мне нужно тратить своё время на изучение этих сложных алгоритмов, если я работаю с фронтендом? Как знание графов и бинарных деревьев поможет мне лучше отцентровать одну div-ку внутри другой div-ки?»

С одной стороны, знание алгоритмов и структур данных действительно напрямую не пригодится вам в практической работе. Но с другой стороны, существует одна весомая причина инвестировать немного своего времени в их изучение: знание алгоритмов и структур данных сделает вас лучше как разработчика.

Многие веб-разработчики на таких форумах, как Reddit и Stack Overflow, отмечали, что, освоив даже на базовом уровне эти фундаментальные основы программирования, чувствовали себя увереннее, профессиональнее и писали более чистый и структурированный код.

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

Кстати, именно по этой причине многие крупные IT-компании требуют от своих потенциальных сотрудников знания фундаментальных основ computer science, к которым как раз относятся алгоримты и структуры данных, и с пристрастием спрашивают их на собеседованиях.

Ведь они ищут лучших из лучших, и знание алгоритмов как раз делает вас лучше как разработчика. Тем более, лучше инвестировать свое свободное время в новые знания и навыки, чем в сериалы на Netflix.

И на этой прекрасной ноте давайте перейдем к основной теме статьи.

Сегодня расскажу о решении важной для многих из нас и ставшей уже классической задачи ― детектировании позы человека на изображении. Решать её я предлагаю с использованием библиотеки OpenPose. Всё самое интересное ― под катом. Сразу скажу, что статья небольшая, но наглядная ― я постаралась без лишних слов показать возможности библиотеки. В первую очередь она предназначена для начинающих специалистов, но, возможно, и профи найдут что-то полезное для себя.

Здесь описан алгоритм мозга, который с небольшими вариациями управляет разнообразными мыслительными процессами и все наше мышление есть по сути его комбинации. Я предполагаю, что он соответствует созданному эволюцией алгоритму разума, так как он простой и универсальный. Проявления этого алгоритма участвуют, как в распознавании картинки, так и в мышлении.

Вывод HTML-дерева из локального файла в окно программы-оболочки «Windows PowerShell» версии 5.1 (или в окно программы-оболочки «PowerShell» версии 7) с помощью скрипта на языке PowerShell в операционной системе «Windows 10». Используется библиотека «HTML Agility Pack».

В качестве упражнения в алгоритмах и структурах данных рассмотрено несколько способов обхода и вывода HTML-дерева: NLR (прямой с приоритетом обхода потомков слева направо), NRL (прямой с приоритетом обхода потомков справа налево), LRN (обратный). Примеры практической реализации.

На хабре существует огромное множество статей на подобные темы, эта статья не будет исключением. Я лишь хотел бы поделиться своим опытом подготовки к кодинг интервью в крупные компании. Постараюсь описать процесс настолько подробно, насколько я его запомнил, со статистикой, таймлайном и моим отношением к нему.

С докладами технического трека Positive Hack Days 11 мы вас уже познакомили, настал черед трека, посвященного проблематике искусственного интеллекта и машинного обучения. AI-трек шел всего день, зато как: вместе с экспертами из «Ростелекома», Security Vision, Bloomtech LLC и других известных компаний мы поговорили о биометрических алгоритмах обнаружения витальности в Единой биометрической системе, о том, как компаниям обмениваться данными, не обмениваясь ими, и о том, какие методы машинного обучения помогают в выявлении сетевых атак. Делимся докладами, которые «зашли» участникам форума больше всего.

Учёные обнаружили новый тип задач, которые квантовые компьютеры могут решать намного быстрее, чем их классические аналоги.

В 1994 году один математик придумал, как заставить квантовый компьютер делать то, на что не способен обычный классический компьютер. Работа показала, что, в принципе, машина, основанная на правилах квантовой механики, может эффективно разбить большое число на его простые множители – задача настолько сложная для классического компьютера, что она составляет основу большей части современной компьютерной безопасности.

Последовал всплеск оптимизма. Возможно, решили учёные, мы сможем изобрести квантовые алгоритмы, способные решить огромный спектр самых разных задач.

Не так давно я захотел написать свой шахматный движок. На удивление в Интернете нашлось не так много хороших статей на эту тему. Были статьи с довольно слабыми программами, многие из которых даже умудрялись пропускать некоторые важные правила. А были статьи с хорошими программами (некоторые из них были даже чуть лучше чем получилось у меня в итоге), но там авторы рассказывали лишь основные идеи, пропуская подробности, из-за чего написать что-то свое по таким статьям было проблематично. Поэтому после написания своей программы, я решил написать статью, дабы облегчить жизнь интересующимся в данной теме. Я не претендую на лучшую шахматную программу или на чистейший код, но эта статья будет хорошим и легким началом для тех, кто хочет написать что-то свое.

По этой ссылке приложение для поиска по датасету Open Images and Places 365 (3.5 миллиона картинок)

Загружаете свою картинку - получаете 18 похожих.

Мы продолжаем цикл статей про математику и смежные дисциплины в компьютерной графике по курсу Александра Паничева, ведущего разработчика логики в UNIGINE. В этот раз поговорим о функциях плавности, которые используются в анимации (и не только).

Как написать программу, чтобы победить на конкурсе плохого кода? Этот вопрос я задал сам себе, когда прочёл о необычном челлендже на форуме reddit. Да, вы правильно поняли. Это статья не о чистом коде и правильных тестах. Но здесь не будет и речи о плохом, заурядно плохом коде, том коде, который мы очень часто видим в наших проектах. Я расскажу об экстремальном, невообразимом, гениально плохом коде, коде, который использует те возможности джавы, о которых вы, скорее всего, и не догадывались, и те приёмы, которые вы никогда не встретите в обычных проектах. Сможете ли вы использовать эти приёмы на практике? Думаю, нет. Если вы прагматичный человек, то сэкономите своё время и остановитесь. Не читайте эту статью. Однако если вы хотите немного отвлечься от повседневной рутины, увидеть и узнать что-то новое о нашем любимом языке Java, - милости просим!

Когда моя сестра переехала в другой город и познакомилась с соседями, оказалось, что дедушка и бабушка ее соседа и наши бабушка с дедушкой были хорошими друзьями и общались, живя рядом в другом городе – два поколения назад. Интересно, когда обнаруживаются такие неожиданные связи. Согласно теории сетей, пути, соединяющие узлы сети, зачастую короче, чем могло бы показаться.

Если каждый в сети знает k других людей, то можно упрощенно предположить, что, начав от этого человека и совершив n переходов от узла к узлу, мы найдем kⁿ человек. Учитывая экспоненциальный рост, потребуется совсем немного времени, чтобы построить путь от любого конкретного человека до любого другого в графе.

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

В главе 20 книги Networks Crowds and Markets ее авторы Дэвид Изли и Джон Клейнберг дают теоретический аппарат, описывающий, как в реальном мире могут возникать феномены, укладывающиеся в граф «мир тесен». В этой теории сочетается идея гомофилии, согласно которой схожие люди кучкуются вместе, и идея слабых связей, где отношения ветвятся в масштабах всей сети. Объяснение основано на работе Дункана Уоттса и Стива Строгаца. Давайте проследим эти примеры при помощи кода, написанного при помощи Neo4j.

Warning: Текст ниже сухой, так как написан больше для публичного логирования и интересен будет скорее тем, кто библиотеку уже использует.