Pull to refresh

Издержки больших проектов или взгляд на программирование в команде изнутри

Reading time 1 min
Views 3.7K
GTD *
Ни для кого не секрет, что разработка больших программных продуктов требует не только эффективного руководства, но и эффективных процессов, которым следуют все разработчики. На примере своей компании я постараюсь описать жизненный цикл проекта и цену его разработки и поддержки. Те, кто работает в небольших командах из нескольких человек, смогут сравнить и представить, что их ждет при увеличении штата или же чего они избежали, если расширяться не планируют. А в комментариях можно покритиковать, указать на ошибки и предложить альтернативы.

Итак, собственно, к делу.

Мы занимаемся системами электронной биржевой торговли, аналитикой рынка и поставкой маркет-данных в реальном времени. К таким системам предъявляются повышенные требования по надежности — каждая ошибка может привести к потере больших денег.
Читать дальше →
Total votes 82: ↑76 and ↓6 +70
Comments 112

Топ-10 результатов в области алгоритмов за 2012 год

Reading time 4 min
Views 49K
Programming *Data Mining *Algorithms *
Translation
Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке:
Читать дальше →
Total votes 114: ↑114 and ↓0 +114
Comments 8

У нас было 540 точек, 120 мерчендайзеров, 30 ТП, 2 супервайзера, 5 таблиц в XLS и один пакет на ПО маршрутизации

Reading time 6 min
Views 36K
КРОК corporate blog Geoinformation services *
image
Пример XLS-таблицы, которая используется до внедрения системы – и отлично подходит в качестве источника первичных данных.

Есть такой классный тип математических задач — маршрутизация торговых представителей (ТП). Хорошо известный каждому, изучавшему дискретную математику.

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

Фактически, задача сводится к двум:
  • Обобщенной задаче коммивояжера (TSP).
  • И построению оптимального расписания-плана.

При этом в задачах также учитываются доступные ресурсы (например, наличие машин, их вместимость, проходимость дорог и так далее), параметры точек (время ее работы точки, частота посещения, перечень задач, которые требуется решать в данной точке и так далее), изменения, например, внезапный переезд одного ларька на другой конец города. Ну и финальный штрих — довольно часто эта задача решается супервайзером с высшим гуманитарным образованием.
Читать дальше →
Total votes 31: ↑25 and ↓6 +19
Comments 51

PKI (Public Key Infrastructure) с помощью JavaScript? Теперь это возможно с помощью библиотек PKIjs и ASN1js

Reading time 5 min
Views 12K
Information Security *JavaScript *
Представляю вашему вниманию две библиотеки, реализующие практически полный спектр требуемого функционала для организации инфраструктуры PKI: PKIjs и вспомогательную библиотеку ASN1js. Библиотеки свободны доступны и распространяются по лицензии, позволяющей использовать их код без особых ограничений, даже в коммерческих продуктах. Полный код данных библиотек доступен на GitHub: PKIjs + ASN1js.

Дабы привлечь читателей прямо во введении приведу краткий список особенностей вышеупомянутых библиотек:
  1. Объектно-ориентированный код;
  2. Работа с HTML5 (ArrayBuffer, Promises, WebCrypto (используется «dev nightly build» Google Chrome));
  3. Возможность создавать, проверять, получать внутренние данные, изменять данные для следующих объектов:
    1. Сертификаты X.509
    2. Списки отзыва (CRL) X.509
    3. Запросы на сертификат (PKCS#10)
    4. OCSP запросы;
    5. Ответы OCSP сервера
    6. Time-stamping (TSP) запросы
    7. Ответы TSP сервера
    8. CMS Signed Data
    9. CMS Enveloped Data

  4. Реализация собственной «certificate chain validation engine» на JavaScript;
  5. … И многое другое! Смотрите под катом!


Читать дальше →
Total votes 31: ↑31 and ↓0 +31
Comments 18

ASN1js и PKIjs — год после создания

Reading time 4 min
Views 7.4K
Information Security *JavaScript *
Почти год назад я рассказал о новых библиотеках PKIjs и ASN1js. Пришло время рассказать о развитии этих библиотек. Для ASN1js за это время были сделаны в основном «косметические» изменения. Из существенных изменений можно заметить только возможность конвертации любых объектов ASN.1 в JSON формат. А вот с PKIjs произошли более существенные перемены.

Итак, текущие основные особенности PKIjs:
  • Полная поддержка Web Cryptography API;
  • Ограниченная возможность использования как в iPhone (через использование Safari), так и в Android приложениях (Google Chrome);
  • Расширилось количество примеров. В частности, добавились примеры использования PKIjs для проверки подписей в PDF файлах и для проверки подписей в S/MIME;
  • Использование всех алгоритмов подписи из Web Cryptography API:
    • RSASSA-PKCS1-v1_5 (PKCS#1 v1.5);
    • RSA-PSS (PKCS#1 v2);
    • ECDSA (подпись на ECC, Elliptic Curve Cryptography);
  • Первая реализация «certificate chain verification engine» (верификация цепочки сертификатов) на чистом JavaScript и проходящая основные тесты NIST;
  • Первая и пока единственная реализация «Suite B» для подписи и шифрования данных в виде CMS (Cryptographic Message Syntax) в «open-source» на чистом JavaScript;
    • Подпись CMS с помощью ECDSA;
    • Шифрование с применением схем «ephemeral-static» ECDH;
    • Использование AES-CBC и AES-GCM;
    • Использование расширенного списка алгоритмов хеширования: от SHA-1 до SHA-512;
    • Возможность создания зашифрованных сообщений на основе использования пароля с использованием алгоритмов серии AES;

Читать дальше →
Total votes 14: ↑13 and ↓1 +12
Comments 6

Муравьиная оптимизация и сетевые алгоритмы

Reading time 8 min
Views 19K
Издательский дом «Питер» corporate blog Algorithms *Mathematics *
Translation
Как вы могли заметить, у нас тут затишье. Но наш творческий поиск не прекращается, и первая октябрьская публикация будет посвящена ACO (Ant Colony Optimization)



Отдавая должное автору, мы не будем публиковать здесь последнюю часть статьи, содержащую пример на JavaScript, а предложим вам опробовать его на сайте оригинала. Под катом же вы найдете перевод теоретической части, доступно рассказывающей о тонкостях муравьиной оптимизации в различных сценариях.
Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Comments 1

Электронная амеба и задача коммивояжера

Reading time 11 min
Views 2.7K
ua-hosting.company corporate blog Algorithms *Manufacture and development of electronics *Popular science Biotechnologies


Какой самый ценный ресурс на планете? Нефть, вода или может чистый воздух? Самый ценный ресурс, по мнению многих, это время. Его всегда не хватает, люди постоянно куда-то спешат, а любая деятельность так или иначе связана с временем: сколько баррелей нефти добывает одна нефтяная платформа в единицу времени, сколько клиентов обслуживает ресторан в единицу времени, сколько строк кода пишет программист в единицу времени и т.д. Правильное распределение задач по времени играет важную роль не только в промышленных или корпоративных масштабах, но и в быту. Мы всегда стараемся распределить свой день так, чтобы он прошел максимально эффективно и без лишних проблем. Можно сказать, что мы каждый день, сами того не подозревая, решаем свою собственную версию задачи коммивояжера. Ученые из университета Хоккайдо, вдохновившись одноклеточными амебами, решили создать аналоговый компьютер по их подобию, который может предложить самый эффективный метод решения знаменитой задачи комбинаторной оптимизации. Почему именно амебы стали вдохновителями этого труда, по какому принципу работала созданная система, и насколько эффективно она решала задачу коммивояжера? Об этом мы узнаем из доклада ученых. Поехали.
Читать дальше →
Total votes 15: ↑14 and ↓1 +13
Comments 3

Задача коммивояжера (TSP) точное решение — метод динамического программирования

Reading time 9 min
Views 12K
Python *Algorithms *

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

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

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

Читать далее
Total votes 10: ↑10 and ↓0 +10
Comments 16

Задача коммивояжера (TSP) точное решение — метод ветвей и границ

Reading time 17 min
Views 12K
Python *Algorithms *C *

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

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

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

Читать далее
Total votes 32: ↑32 and ↓0 +32
Comments 42

Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)

Reading time 20 min
Views 19K
High performance *Python *Perfect code *Algorithms *

Дочитав эту статью до конца, вы сможете решать точно задачу коммивояжёра на сотню элементов за считанные секунды!

Заинтригованы? Тогда, добро пожаловать под кат.

Читать далее
Total votes 124: ↑124 and ↓0 +124
Comments 40