Алгоритмы *

Многие (особенно в постсоветских странах) относятся к списыванию довольно беззаботно. Ученики в школах, студенты в университетах, а затем и специалисты в своей работе заимствуют чужие идеи и решения, не чувствуя вины за обман. Между тем плагиат — это не безобидное «подумаешь, списал», а серьезная проблема, которая ведет к мошенничеству и коррупции [1, 2]. 

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

Написание своего шахматного движка - обширная тема, про которую пишут целые книги.

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

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

Я запрограммировал 15 шахматных вариаций - для каждой опишу неожиданные ходы и результаты партий компьютера друг с другом.

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

Друзья по играм: Бен, Билли, Том Миллер и другие, с интересом ждали правил игры, в которую Сойер превратит задание на этот раз. 

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

-- Пропади я пропадом, если не уберу подальше от улицы все кусты, что будут похуже этого!

Том в задумчивости осмотрел ряд таких же кустов.

-- Вот второй куст, он повиднее этого! Но почём мне знать насколько он хорош? Пусть пока постоит на месте. Тётушка точно будет недовольна, если мы будем дёргать горшки почём зря.

-- Третий тоже повыше моего, оставим и его до срока.

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

-- Попался, оборванец! Что ж поделать, многоуважаемый недоросль, ваше место займёт более возвышенный кандидат!

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

Он схватил второй куст и перенёс его на пустующее место в ряду, возле своего образца.

Поднимая свой образец с земли, Том с жалостью сказал ему: -- Судя по всему, дружок,  тебе не украшать собой вход у калитки... Но пойдём дальше, поищем ещё кого-то похуже тебя.

Есть данные за 2 дня мая 2005 года 2 дня мая 2006 года. Цель найти в сумме 1440 сравнений[60*24] звездный год.

На сайте habr.com/ru уже были похожие публикации осенью 2021 года:

Как посчитать синус быстрее всех

Как посчитать синус быстро

Не на Habr Как сделать быструю функцию для вычисления синуса? топик начат в 2003 году последний отклик в 2020 году.

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

Разбираю разные подходы к созданию ботов и смотрю на их эффективность

Заработает ли бот достаточно денег?
Будет ли стабильный заработок?
Достигнет ли он когда-нибудь годового дохода в $100,000?

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

Поиск самого длинного палиндрома в строке за O(n).

Сегодня, в субботу 26 февраля, на Сколковской Школе Синтеза Цифровых Схем Михаил Коробков проводит занятие по технологиям функциональной верификации: constrain solvers, cover bins и concurrent assertions. Примеры, которые мы подготовили для школы, вращаются вокруг протокола AXI для систем на кристалле, вопросы про который спрашивают например на интервью в хардверное отделение компании Meta и другие.

На предыдущих занятиях школы мы изучали в основном аспект проектирования на языке описания аппаратуры Verilog. Но как участники уже успели заметить, Verilog — это не только язык для описания и синтеза схем, но и язык программирования для написания тестов. В некоторых компаниях на каждого инженера, который пишет код на верилоге на уровне регистровых передач, приходится два или три инженера, которые пишут код для верификации.

Суть деятельности Verification Engineer заключается в создание фреймворков, которые тестируют хардверные дизайны на прочность, посылая к ним псевдослучайные транзакции и учитывая покрытие интересных сценариев (functional coverage). Базовые элементы этих технологий должен знать и хороший RTL Design Engineer.

Приглашаем присоединяться к трансляции занятия на канале школы в YouTube, в субботу 26 февраля с 12.00 до 15.00:

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

Исследуя большое пространство, нужно собирать сокровища, разбираться с обитателями и охранной системой. При этом важно избегать ловушек, которые можно вычислить по цифрам. Как в игре «Сапёр».

Игра получилась на удивление играбельной, извините за тавтологию. Интересное сочетание экшена/аркады и паззла/адвенчуры. Разрешите рассказать вам о паре алгоритмических задач, возникших при генерации уровней. Сами алгоритмы простые. Однако интересно именно то, что их можно использовать в игре.

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

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

Как мы уже говорили в первой части, для демонстрации анализа алгоритма в более широком контексте примером послужит расстояние редактирования Левенштейна. Расстояние редактирования также иногда называют поиском похожих строк (или нечетким поиском). Это метрика редактирований (изменений символов), необходимых для преобразования одной строки в другую (целевую) строку. Из самых известных применений алгоритма можно выделить предоставление предложений по правильному написанию, нечеткий поиск по строке поискового запроса и сравнение последовательностей ДНК/РНК.

По сравнению с бинарным поиском, который построен вокруг одной операции поиска, классический алгоритм Левенштейна поддерживает три операции: вставить/insert, удалить/delete и заменить/substitute (символ в строке). Расстояние редактирования, которое он выдает, является минимальным количеством необходимых операций.

В один из вечеров у меня появились наукообразные вопросы. Можно ли «растворить» какой-либо видеофайл, разместив его в теле другого видеофайла так, чтобы при этом первый видеофайл можно было относительно легко и беспрепятственно достать обратно? Кроме того, чтобы не углубляться в математику проблемы, можно ли это желание реализовать своими силами за один вечер, предположим на языке Python без использования каких-либо сторонних стеганографических библиотек и иных специальных инструментов?

• Формулировать требования к покупке по мере сравнения вариантов.
  
  
  Пример с соковыжималкой

  Предположим, он ищет соковыжималку, но ещё не знает, какие они бывают. По мере изучения товаров он примерно начинает понимать, что хочет. На старте у него нет ни фиксированного бюджета, ни требований, только мечта. Дальше нужно сопоставить мечту с конкретной карточкой товара. С точки зрения метрики покупки, пользователь будет довольно долго бесцельно бродить в начале — но мы понимаем, что эта часть была очень важна, там он изучал предложение и понимал, как устроен мир.
• Приходить с примерным бюджетом и выбирать что-то под него, например, при поиске подарка. В этой ситуации у пользователя даже нет мечты, он ходит по категориям и ищет что-то, что его «зацепит».
• Более-менее точно понимать, что хочет купить (часто вплоть до модели товара), но искать лучшее предложение.
• Знать модель товара и проверять, насколько честна цена на неё, насколько хороши отзывы и так далее.

История Bash Today - сервиса бронирования площадок для мероприятий в Москве и Санкт-Петербурге , основанного в 2015 г.

Серьёзная проблема для сервиса бронирований — прямые платежи от клиентов площадкам по заявкам, пришедшим через маркетплейс. Из-за этого компания лишается своей комиссии. Стандартные инструменты выявления подобных схем, такие как опрос пользователей, сбор обратной связи после мероприятий и так далее, имеют ограниченную эффективность, так как осуществляются случайным образом. Поэтому нашей R&D-команде была поставлена задача повысить эффективность проверок с помощью алгоритмов AI.

В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W.W. Adams, P. Loustanau. An Introduction to Groebner Basis (параграф 2.7).

Silicon Forest в штате Орегон не так известен как Silicon Valley в Калифорнии, но он несомненно входит в топ-5 хайтек-мест в США. Просто факт из Википедии: хотя штаб-квартира Интела остается в Калифорнии, но еще в 1990-х компания начала переносить самую продвинутую разработку микроархитектуры в Орегон. Как очевидец, могу сообщить банальную причину: в начале интернет-бума цены на дома в Долине выросли вдвое, а потом втрое, и агломерация вокруг Портланда стала ближайшим местом бегства из Калифорнии для инженеров, которые хотели купить дом, но не хотели переучиваться на джаву и становиться дотком-миллионерами.

Но "Кремниевым Лесом" окресности Портленда назвали еще до описываемых событий. После второй мировой войны там выросла компания-производитель осциллографов Tektronix, а в начале 1980-х годов - производитель софтвера для проектировщиков микросхем Mentor Graphics (сейчас Siemens EDA). Чуть позже в Лесу возник производитель ПЛИС Lattice, а потом подтянулись японские компании: Fujitsu, Epson, NEC. Наконец, там сделали отделения IBM и HP, и "Кремниевый Лес" состоялся.

Жить в области Портленда хорошо. Полтора часа езды налево - океан. Полтора часа направо - горные лыжи. В самом Портленде - самый большой в мире книжный магазин, вокруг много лесных троп и рыбалки. Одна проблема для юного русского программиста: где искать девушек?

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

Детали и крутые фото из заповедников – под катом.

В посте покажем несколько кейсов команд – под наше увеличительное стекло попали два решения на основе нейронных сетей (одно отлавливает медведей на фотоловушках, а другое подсчитывает рыб) и таймлайн новостей Камчатки за последние 20 лет (расскажем, зачем вообще такое понадобилось). 

Привет, Хабр! Расскажу о решении нестандартной задачи: алгоритм определения силлабо-тонического стихотворного размера по строке на русском языке. Опишу все нюансы и неочевидные подводные камни, с которыми столкнулся.

В этой публикации я представляю поверхностный обзор статьи от исследователей LinkedIn «Representation Learning in Heterogeneous Professional Social Networks with Ambiguous Social Connections». В указанной статье частично представлена структура графа знаний LinkedIn’s Economic Graph и относительно подробно описан метод обучения эмбеддингов Star2Vec. Я попытаюсь объяснить основные этапы построения векторных представлений, что называется "на пальцах".

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

1. Skip-gram и его адаптация под графы (word2veс, LINE, DeepWalk);

2. общие понятия о графах знаний.