Рубрика «Алгоритмы» - 9

Есть проблемы гораздо сложнее, чем NP-Complete - 1

Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.

В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »

Что такое нейросеть? В базовом понимании, нейросеть – это совокупность связанных нейронных блоков, выполняющих обработку информации.

I. Основы нейросетей

В поисковых системах ежедневно растет количество запросов, что такое нейросеть (далее — НС). Прежде всего это связано с растущим интересом к технологиям на базе искусственного интеллекта (далее — ИИ). Многие из нас даже не подозревают, что мы практически ежедневно используем модели глубокого обучения. Запросы Siri или взаимодействие с чат-ботами в мессенджерах — один из ярких примеров использования НС. 

Читать полностью »
RSync на стероидах с поддержкой Windows - 1

На Хабре периодически рассказывают о новых инструментах для синхронизации данных. Это интересная тема. Такие программы используются:

  • для синхронизации файлов на разных устройствах,
  • дедупликации,
  • резервного копирования,
  • сжатия.

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

Кроме того, инструменты синхронизации интересны с алгоритмической точки зрения. Любопытно, как люди умудряются оптимизировать базовые алгоритмы типа rsync, которые вроде бы работают идеально. Но нет, всегда можно придумать что-то получше.
Читать полностью »

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

Интерактивные книги 2: на этот раз про геймдизайн и алгоритмы - 1

Итак, знакомьтесь — Амит Патель (Amit Patel) и его интерактивные статьи на стыке математики, алгоритмов и программирования. Небольшой дисклаймер: поскольку я не могу встроить интерактивные иллюстрации на Хабр, то буду использовать анимированные gif. Некоторые из них могут быть тяжелые.Читать полностью »

Ускоряем приложение: никаких фреймворков — только математика - 1

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

Читать полностью »

Вычислительная сложность некоторых игр и головоломок - 1

Есть несколько причин смотреть на игры как на нечто большее, чем просто на развлечения. Как станет яснее по ходу дела, многие игры основаны на сложных вычислительных задачах, хотя зачастую и с более низким «входным барьером», поскольку они редко требуют наличия формального образования.

Читать полностью »

Красивый двоичный поиск без ветвления - 1

Недавно я прочитал пост Алекса Мускара Beautiful Binary Search in D. В нём описывается алгоритм двоичного поиска под названием «алгоритм Шора». Я никогда не слышал о нём и его невозможно загуглить, но увидев алгоритм, я думал только об одном: «он без ветвления». Кто знал, что может существовать двоичный поиск без ветвления? Поэтому я занялся его трансляцией в алгоритм для итераторов C++, не требующий индексации на основе единицы или массивов фиксированного размера.

В GCC он более чем в два раза быстрее, чем std::lower_bound, который сам по себе — очень высококачественный двоичный поиск. Цикл поиска прост, а генерируемый ассемблерный код красив. Меня потрясло, что он существует, но им, похоже, никто не пользуется.
Читать полностью »

Алгоритмы балансировки нагрузок - 1


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

В этом посте мы рассмотрим способы, которыми один балансировщик нагрузок может распределять HTTP-запросы на множество серверов. Мы начнём снизу и проделаем весь путь вверх до современных алгоритмов балансировки нагрузок.
Читать полностью »

Ответом на задачу по упаковке цветов в бесконечной сетке оказалось число 15 - 1

Видео

В задаче по «упаковке цветов графа» (в оригинале packing coloring, — прим. пер.) спрашивается, сколько чисел необходимо для заполнения бесконечной сетки так, чтобы идентичные числа никогда не оказывались слишком близко друг к другу. И новый арифметический эксперимент с использованием компьютера даёт на удивление простой ответ.

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

Простая процедурная генерация мира, или Шумы Перлина на Python - 1

Недавно я выпустил статью, в которой рассказал о библиотеке Ursina Engine и показал, как создать свою трехмерную игру на Python. Между разделами вскользь упомянул про шум Перлина. Это один из базовых алгоритмов процедурной генерации, который можно использовать для создания красивых игровых миров. Хочу рассказать о нем подробнее и показать, как работать с модулем perlin-noise.

Если вам интересно, как просто генерировать реалистичные трехмерные ландшафты на Python, добро пожаловать под кат!
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js