Алгоритмы *

Полтора года назад я рассказывал про свой пет‑проект по визуальному программированию — falang.io. Основная его особенность состоит в том, что пользователь не управляет расположением икон на схеме, только их содержимым. Все остальные соединительные линии рисуются автоматически алгоритмом по строгим правилам. В т.ч. continue, break, return.

На данный момент, помимо обычных текстовых диаграмм, у меня появился Low‑code констркутор логики с упрощенной семантикой, который может экспортироваться в 5 современных языков программирования: C++, C#, Rust, Go, TypeScript.

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

Динамическое программирование — это метод решения сложных задач путём разбиения их на более мелкие подзадачи, решение которых легче и проще.

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

Сегодня мы порассуждаем об одной из самых древних и знаменитых настолок — шахматах. Что вообще нужно для комфортной игры двух человек по сети?

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

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

Предлагаю с этого и начать.

Ранее был предложен некоторый Алгоритм деления 2W‑битовых чисел с использованием операций над W‑битовыми числами. Для тестирования использовались целые числа языка С++, что не позволяло проверять, например, 128-битные целые числа. Однако, в язык Python встроена поддержка целых чисел неограниченной ширины (Big Integer), а также имеется API для вызова методов Python из программ на языке С/С++. Это позволяет протестировать разные алгоритмы с числами, в том числе деление, используя в качестве результата строковое представление чисел.

В данной статье расписаны шаги для использования Python C API в программе на языке С++, а также показан пример вызова оператора деления двух целых чисел с возвратом результата в виде строки С. Использовалась следующая программная конфигурация:

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

В данной статье предлагаю рассмотреть историю создания мной сборщика Java проектов под названием Conveyor (https://github.com/maximtereshchenko/conveyor): опыт написания проекта сложности выше средней, различные проблемы, причины принятия технических решений, примеры использования шаблонов проектирования

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

В конце прошлого года технологический гигант IBM объявил о том, что может показаться важной вехой в квантовых вычислениях: о первом в мире чипе под названием Condor, содержащем более 1000 квантовых битов или кубитов. Прошло всего два года после того, как компания представила Eagle, первый чип с более чем 100 кубитами. Казалось, что эта область стремительно движется вперёд. Создание квантовых компьютеров, способных решать полезные задачи за рамками даже самых мощных классических суперкомпьютеров, требует ещё большего их масштабирования — возможно, до многих десятков или сотен тысяч кубитов. Но это ведь всего лишь вопрос техники, верно?

Анекдот из журнала. Один мужчина купил дом c искусственным интеллектом. Уже через неделю умный дом называл его лентяем, а через месяц мужчина сам мыл посуду и стирал носки, после чего ему включался футбол.

Понятия Естественный интеллект и Искусственный интеллект (ЕИ, ИИ от лат. intellectus - познание - понимание, рассудок), способность мышления, рационального познания, у человека – ЕИ, у робота – ИИ. ИИ можно определить как область компьютерной науки, занимающуюся автоматизацией разумного поведения неживых объектов. Здесь не будем оценивать и анализировать многочисленные другие определения ИИ и заострять внимание на предлагаемых разными авторами текстах, чтобы не застрять на этом. Понимание ИИ как системы, способной решать задачи доступные в прошлом только человеку, без всяких упоминаний эмуляции сознания, — также используется. И современные системы ИИ вполне этому определению отвечают.     

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

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

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

Привет, Хабр! Меня зовут Данил Картушов.

В этом посте я расскажу, как музыкальная платформа Deezer, используя метаданные, с первых секунд научилась рекомендовать персонализированные треки новым пользователям!

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

Описание способа нахождения значения произвольного элемента последовательности Фибоначчи за логарифмическое время.

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

Шёл 2022 год. Я обратил внимание на новый интересный проект CUTLASS, отличающийся очень высокой скоростью выполнения операций умножения матриц. Я взял большую задачу по умножению матриц — 8192 x 8192 x 8192, и померял производительность в PyTorch, где используется библиотека cuBLAS.

Вам нравятся старые Legend of Zelda времён SNES и GBA? Может быть, вам пришлась по вкусу Dark Souls? А, возможно, вы ещё и фанат Quake? Но что объединяет все эти игры? Для меня это в первую очередь дизайн уровней. Головоломки, удобные шорткаты и нелинейность исследования - вот то, что делает карту игры частью общего игрового процесса и вдыхает жизнь в процесс исследования мира.

В наше время расцвета жанра rogue-lite вопрос генерации игровых уровней актуален как никогда. Однако по-настоящему интересные уровни в жанре - большая редкость, я бы даже сказал, феноменальная. Чаще всего уровни представляют собой просто наборы заранее заготовленных комнат-коробок, случайным образом приставленных друг к другу, без какой-либо логичной высокоуровневой картины. Но, всё же, я знаю одну игру, которая взяла принципиально другой подход: Unexplored. На мой взгляд, она пересмотрела устоявшийся стереотип об ограничениях левелдизайна в рогаликах. Всё, что для этого понадобилось - циклическая генерация подземелий (Cyclic dungeon generation).

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

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

Может показаться, что на самом деле просто не было существенного прогресса с 60х годов, так как Дейкстра предоставил почти асимптотически оптимальный алгоритм решения задачи. На самом деле нет, прогресс был и придумали много чего интересного, хоть и действительно с того времени фокус сместился на другие задачи. Приглашаю под кат если интересно узнать что такого напридумывали, что используется в современных логистических системах, почему меня огорчает отсутствие учёта флага единства в HOMM3 при расчёте пути, ну и наконец, что за мужики на картинке выше рядом с Дейкстрой?

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

Небольшая заметка студента о том, как самостоятельно реализовать алгоритмы SHA256 и SHA512 на Rust.

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