Давайте представим, что вы устроились много лет назад в 2GIS и вам выпала честь написать алгоритм, который будет прокладывать самый короткий автомобильный маршрут от точки A к точке B.
Вы отправляетесь искать информацию и к счастью натыкаетесь на эту статью, где мы с вами подробно обсудим популярные алгоритмы поиска пути.
Поиск кратчайшего маршрута является сложной задачей, заключающейся в посещении каждого элемента из набора мест и возвращении в исходную точку, что представляет собой NP-усложнённую задачу. NP(в теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).) Она также известна как задача коммивояжера(ЗК) и изучается в области комбинаторной оптимизации, операционного исследования и теоретической информатики. ЗК используется в качестве эталона для многих методов оптимизации. Цель задачи заключается в нахождении одного пути, который может пройти через все узлы (экземпляры) графа всего один раз (гамильтонов цикл) с наименьшей длиной пути, то есть с минимальным евклидовым расстоянием.
Привет, друзья!
В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это шестая часть серии, в которой мы начинаем разбирать алгоритмы.
Сегодня мы поговорим об алгоритмах для работы с множествами.
Код, представленный в этой и других статьях серии, можно найти в этом репозитории.
С вашего позволения, я не буду рассказывать о математических алгоритмах, соответствующий код вместе с комментариями и тестами можно найти в директории math.
Интересно? Тогда прошу под кат.
Данная статья посвящена разработке аппаратуры на SystemVerilog со стороны человека, который сам только начинает углубленно в этом разбираться. Рассчитана она на то, чтобы другим новичкам было проще сориентироваться в незнакомой среде, поэтому некоторые аспекты здесь будет рассмотрены довольно поверхностно и упрощенно...
Хотя алгоритмы определения простоты числа известны с древних времён, полиномиального алгоритма долгое время известно не было. То есть было неизвестно, принадлежит ли эта задача классу сложности P. В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной был впервые предложен полиномиальный алгоритм проверки простоты чисел, поставивший точку в этом вопросе.
Идёт именно этот день в разработке. В этот раз хочу затронуть феномен покера, для которого создается AI и поделиться наблюдениями, которые помогут ответить на вопрос из названия. Покер (Техасский безлимитный холдем) – это очень глубокая игра, которая представляет собой модель бизнес-отношений разных субъектов по определённым метрикам, единым для всех участников процесса. Эти метрики позволяют человеку, принимающему решение, понимать, когда инвестиции в “свое внутреннее состояние” могут быть более или менее успешными. Стратегии строятся каждым игроком, исходя из меняющегося контекста, по заранее определенным правилам. Особенность именно безлимитной версии покера в том, что вследствие большого рычага оценки стоимости текущего контекста, число возможных вариаций действий в дереве принятия решений становится огромным в разрезе одной-единственной покерной раздачи.
Привет, Хабр! Меня зовут Алла, я работаю младшим исследователем в команде Memory‑Augmented models в AIRI и занимаюсь ресерчем на пересечений графов знаний и языковых моделей. Потребность в таких изысканиях понятна любому, кто пытался добиться от ChatGPT точного ответа на конкретный вопрос: подобрать литературу для курсовой, вспомнить название фильма по описанию и тому подобное. Очень часто модель начинает галлюцинировать и выдумывать факты, которых не существует.
Один из способов решения этой проблемы — связать LLM с графом знаний, но сами графы тоже должен кто‑то наполнять. Мы с коллегами доказали, что эту задачу можно автоматизировать с помощью LLM и предложили своё решение, названное Prompt Me One More Time (фанаты Бритни тут?), о котором мне бы и хотелось сегодня здесь рассказать. За подробностями же можно обратиться к статье, представлена нами на воркшопе TextGraphs-17 конференции ACL-2024, недавно прошедшей в Тайланде.
После долгого перерыва мы возвращаемся в мир криптографических алгоритмов. В этот раз мы рассмотрим некоторые широко известные режимы шифрования блочных шифров, такие как ECB, CBC, CFB, OFB, CTR и подготовим небольшую архитектурную задумку, о которой я расскажу под катом.
Если вы еще не видели мои предыдущие статьи по алгоритмам хэширования "Streebog" и "SHA", советую ознакомиться — в этот раз будет сложнее.
OpenStreetMap (OSM) — глобальный проект, образованный вокруг геоинформационной базы данных, наполняемой всеми желающими — как энтузиастами, так и заинтересованными компаниями. Любой может внести свой вклад, однако открытость имеет и оборотную сторону, которая приводит к тому, что в базу часто попадают некорректные правки. Поэтому в экосистеме OSM написано множество валидаторов, которые позволяют поддерживать качество данных на приемлемом уровне.
С 2016 года в open source существует препроцессор метро, который валидирует маршруты скоростного городского транспорта в OSM на предмет полноты и логических/топологических ошибок и преобразует их в форматы, пригодные для сервисов роутинга и рендеринга, в том числе в GTFS. Кроме данных OSM он принимает на вход список сетей общественного транспорта (ОТ), содержащий контрольную информацию о числе линий, станций и прочего в некоторой транспортной сети. Препроцессор успешно себя зарекомендовал в подготовке данных об ОТ для таких приложений, как Maps.me и Organic Maps.
В этой статье я хотел бы поделиться подходом к детектированию одного из видов ошибок, которые довольно часто случаются в данных OSM и автоматический отлов которых представляет собой некоторый вызов — это случайное выпадение станции из маршрута. Все исходные коды валидатора и описываемого алгоритма находятся в открытом доступе. Но сначала определимся с понятиями, используемыми для представления данных об ОТ в OpenStreetMap.
Всем привет! Меня зовут Александра Пилюгина, я продакт-менеджер команды «QR и Фотоплатеж» в управлении «Платежи», банк ВТБ. К нам каждый месяц приходит около 500 тысяч новых клиентов. Специально для них наша команда разработала сервис переноса платежей в ВТБ Онлайн, попутно решив множество проблем с распознаванием платежных документов и извлечения из них полезной информации.
Заходите под кат — расскажу, как мы всё это делали.
Всем привет! Меня зовут Михаил Чайчук, я учусь в магистратуре Вышки на ФКН, где также являюсь исследователем в НУЛ моделей и методов вычислительной прагматики. А недавно я пришел работать в AIRI на должность инженера-исследователя в команду Прикладное NLP, которой руководит Елена Тутубалина. Вместе с ней мы приняли участие в соревновании ImageCLEFmed MEDVQA-GI 2024 по генерации медицинских картинок, которое проводилось в рамках конференции CLEF 2024.
Наш результат оказался лучшим среди 27 зарегистрированных команд! Мы уже опубликовали статью в сборнике соревнования, здесь же я расскажу, как нам удалось добиться победы.
ДИСКЛЕЙМЕР
В этом тексте содержатся изображения, имитирующих результаты эндоскопических исследований желудка и кишечника, таких как гастроскопия и колоноскопия. К сожалению, редактор Хабра не умеет блюрить картинки. Поэтому если вы чувствительны к подобным фотографиям, от чтения этой статьи вам лучше воздержаться.
Приятного аппетитачтения!
Задумывались ли вы, где можно применить навык решения задачек а-ля литкод изи? Я встречаюсь с ними частенько, главное просто присмотреться.
Например, на Linked.in недавно ввели "игры". Я как-то глянул на них на послеобеденном кофе.
Статью адресую всем, у кого есть дети и кто обучает детей/подростков. Тема статьи стала ключевым фактором в моём опыте успешного обучения программированию детей. Это то, что даёт действительно уверенные результаты и помогает формировать личность, сильно выходя за рамки изучаемого предмета.
Из тех, кому вёл уроки более 2-х лет, многие сейчас учатся в технических вузах, кто-то подрабатывает уже. Отсеялись те, кто пошёл учиться изначально “для расширения кругозора”. За всё время более 2-х лет занималось около 50 подростков. В среднем за год через мои занятия проходило 96 человек (8 групп по 12 человек) в школах и на частном обучении около 20 человек в год.
10 лет в сумме проработал в ИТ-образовании. Была и компьютерная грамотность, и робототехника, и программирование, и тренинги, и выездные лагеря по личностному росту, в том числе.
Определение скорости объекта на видеопотоке является актуальной задачей в сфере компьютерного зрения и обработки видео, в частности, в области автономного вождения, контроля на дорогах, видеонаблюдения, спортивной аналитики. Скорость объектов может быть важной информацией в задаче трекинга, определения действий и других задач.
Мы разработали алгоритм, который учитывает движение камеры при помощи оптического потока. Оптический поток определяет движение пикселей между двумя последовательными кадрами. Изменения в потоке являются, смещением пикселей, анализируя которое, можно вычислить относительную скорость движения объекта и скорость фона вокруг него. Из физики известно, что вектор абсолютной скорости является их разностью. Так как смещение в пикселях можно пересчитать в смещение в метрах, то и абсолютная скорость движения в пикселях пересчитывается в скорость в м/с, что требуется для решения задачи.
Всем салют! Давайте решим задачу "Linked List Cycle"
Дан head, являющийся головой связного списка, необходимо определить, есть ли в списке цикл.
Привет, я токсичный программист в области машинного обучения (МЛ), и у меня есть идея создать проект, посвящённый разработке сильного искусственного интеллекта (далее — СИИ (или же AGI)). В небольшом блоге я буду делиться с вами своим опытом в создании чат-бота, который будет обладать СИИ, ну или хотя бы казаться таким.
Настройка ПИД-регулятора для беспилотных автомобилей
Этот проект иллюстрирует концепцию ПИД-регулятора, применяемого в беспилотных автомобилях в рамках программы Udacity «Беспилотный автомобиль»
ПИД-регулятор — это механизм обратной связи в контуре управления, который вычисляет разницу между желаемым заданным значением и фактическим результатом процесса и использует результат для внесения корректировок в процесс. ПИД-регуляторы широко применяются в промышленном и роботизированном управлении процессами.
В контексте беспилотных автомобилей они играют важную роль в управлении такими параметрами движения, как рулевое управление, ускорение и т. д. Сложные алгоритмы, используемые в беспилотных автомобилях, по сути, рассчитывают траекторию и скорость движения беспилотного автомобиля. Автономность может быть реализована только в том случае, если автомобиль следует по траектории с заданной скоростью. Именно здесь PID-регулятор играет свою роль, обеспечивая соблюдение беспилотным автомобилем рассчитанных параметров. Любое отклонение от рассчитанных параметров может привести к непредвиденным или катастрофическим последствиям.
На исторических данных за 1991-2019 год покажем, как можно "увидеть" и "выцепить" признаки переворота. С помощью машинного обучения и ансамблевых модели. Ансамбли (конечно, не музыкальные), как показывает практика, – более эффективны в таких делах, и самое главное - хорошо "тюнятся" и "чипуются".
*Nota Bene (та Bene, что ни разу не гессерит). При всем негативном отношении к революциям, переворотам и прочим событиям в любой части мира, это – объективная реальность, которую можно не только изучать, но и предупреждать.
