• Динамическое программирование. Классические задачи

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

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

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

    Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
    Читать дальше →
  • Эффективный счёт в уме или разминка для мозга

    Эта статья навеяна топиком «Как и насколько быстро вы считаете в уме на элементарном уровне?» и призвана распространить приёмы С.А. Рачинского для устного счёта.
    Рачинский был замечательным педагогом, преподававшим в сельских школах в XIX веке и показавшим на собственном опыте, что развить навык быстрого устного счёта можно. Для его учеников не было особой проблемой посчитать подобный пример в уме:

    image

    Далее рассмотрим несколько трюков для ускорения умственного счёта...
  • POKA-YOKE проектирование: от «запаха» к благоуханию

    • Translation
    От переводчика. Это перевод серии постов из блога Марка Симана. Я не хочу объединять некоторые из постов, несмотря на то, что они небольшие по размеру, а просто постараюсь соблюсти структуру, предложенную Марком.

    Ещё немного от переводчика. POKA-YOKE можно перевести как «дуракоустойчивый» или отказоустойчивый.

    Инкапсуляция является одной из самых недопонимаемых концепций в объектно-ориентированном программировании (ООП). Похоже на то, что большая часть людей думает, что, имеющая отношение к инкапсуляции, концепция «сокрытия информации», просто означает, что закрытые поля должны быть раскрыты через публичные свойства (или getter\setter-методы в языках, которые не обладают поддержкой свойств).
    Читать дальше →
  • Почему 98% текстов на ваших сайтах не работают. Вообще. И как это починить


      Вот так люди видят вашу страницу

      Привет!
      Проблема вот в чём. Если зайти на практически любой сайт интернет-магазина или компании с услугами, вы встретите контент. Точнее — отвратительные тексты, которые писали, кажется, маркетологи, воспитанные сеошниками.

      Разумеется, можно не делать, как они. Если работать по-умному, то вы поможете и читателям по жизни, и себе в продажах.

      По моим примерным подсчётам (усреднение с ряда позиций), конверсии для нас выглядят так:
      • Только название и картинка — около 1,5%.
      • С описанием от производителя — чуть более 2%.
      • С описанием человека, который держал это в руках и знает правила — около 6%.

      Ниже — рассказ про то, как мы доводили время на сайте от 3 минут сначала до 6:40, а потом до 20:48. Да-да, двадцати минут сорока восьми секунд для среднего посетителя. Честного среднего, с учётом отказов и по полной выборке.
      Читать дальше →
    • Cache-Conscious Binary Search

        Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.
        Читать дальше →
      • Собеседование разработчика

          Техническое собеседование – практически неотъемлемый атрибут трудоустройства любого разработчика, а для старших разработчиков – проведение их (собеседований) ещё и чуть ли не повседневная обязанность. Но как за короткий срок (в идеале 20-30 минут) составить у себя более менее приемлемое представление о реальном опыте соискателя?

          Читать дальше →
        • Руководство разработчика Prism — часть 1, введение

          • Translation
          • Tutorial
          Если вы разрабатываете приложения для XAML-based платформ, таких как WPF, Silverlight, Windows Phone, или Windows Store, то Prism, определённо, сильно поможет вам упростить их разработку. После создания нескольких проектов с использованием Prism, я убедился в работоспособности такого подхода и решил подготовить перевод официального руководства Prism. Итак, часть первая, что же такое Prism.
          Оглавление
          1. Введение
          2. Инициализация приложений Prism
          3. Управление зависимостями между компонентами
          4. Разработка модульных приложений
          5. Реализация паттерна MVVM
          6. Продвинутые сценарии MVVM
          7. Создание пользовательского интерфейса
            1. Рекомендации по разработке пользовательского интерфейса
          8. Навигация
            1. Навигация на основе представлений (View-Based Navigation)
          9. Взаимодействие между слабо связанными компонентами

          Prism является руководством, разработанным для того, чтобы помочь проектировать и создавать насыщенные, гибкие и легко поддерживаемые Windows Presentation Foundation (WPF) приложения, Silverlight Rich Internet Applications (RIAs), и программы под Windows Phone 7-8, а также Windows Store приложений. Используя паттерны проектирования, которые воплощают важные принципы архитектурного дизайна, такие как разделение ответственности (Separation of Concerns, SoC) и слабая связанность (Loose coupling), Prism помогает вам проектировать и писать приложения со слабо связанными компонентами, которые могут независимо развиваться и потом объединяться в одно целое с минимальными усилиями. Этот тип приложений известен как составные приложения.

          Читать дальше →
        • Применение JSON-Schema в тестировании и документировании API

            Справочный API 2ГИС разрабатывается уже 4 года. Появилось около 40 методов, которые возвращают достаточно крупные и иерархически сложные структуры в формате JSON и XML. Совсем недавно я решил поделиться накопленным опытом и выступить на конференции DevConf.
            Одна из тем доклада вызвала наибольший интерес у участников — это использование JSON-Schema при тестировании формата выдачи API. В этой статье я расскажу, какие задачи решает этот подход, какие имеет ограничения, что вы получаете из коробки, а что идёт бонусом. Поехали!


            Читать дальше →
          • Повышаем безопасность закрытых ssh-ключей

            • Translation
            Вы когда-нибудь интересовались механизмом работы ssh-ключей? Или тем, насколько безопасно они хранятся?

            Я использую ssh каждый день много раз — когда запускаю git fetch или git push, когда развертываю код или логинюсь на сервере. Не так давно я осознал, что для меня ssh стал магией, которой я привык пользоваться без понимация принципов ее работы. Мне это не сильно понравилось — я люблю разбираться в инструментах, которые использую. Поэтому я провел небольшое исследование и делюсь с вами результатами.

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

            Итак, если вам доводилось прибегать к аутентификации по ключу, то у вас, скорее всего, есть файл ~/.ssh/id_rsa или ~/.ssh/id_dsa в домашнем каталоге. Это закрытый (он же приватный) RSA/DSA ключ, а ~/.ssh/id_rsa.pub или ~/.ssh/id_dsa.pub — открытый (он же публичный) ключ. На сервере, на котором вы хотите залогиниться, должна быть копия открытого ключа в ~/.ssh/authorized_keys. Когда вы пытаетесь залогиниться, ssh-клиент подтвержает, что у вас есть закрытый ключ, используя цифровую подпись; сервер проверяет, что подпись действительна и в ~/.ssh/authorized_keys есть открытый ключ, и вы получаете доступ.

            Что же хранится внутри закрытого ключа?

            Читать дальше →
          • StringBuilder прошлое и настоящее

              Вступление


              Моя прошлая статья была посвящена особенностям строкового типа данных String в .NET. Эта статья продолжает традицию, однако на этот раз мы рассмотрим класс StringBuilder.

              Как известно, строки в .NET являются неизменяемыми (не используя unsafe), а поэтому проводить с ними операцию конкатенации в больших количествах не самая лучшая идея. Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память:

              string s = string.Empty;
              for (int i = 0; i < 100; i++)
               {
                  s += "T";
               }
              
              Читать дальше →
            • Дон Джонс. «Создание унифицированной системы IT-мониторинга в вашем окружении» Глава1.Управление вашим IT окружением: четыре вещи, которые вы делаете неправильно

              • Translation

              От переводчика

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

              Начав выкладывать на хабре некоторые свои статьи и переводы, касающиеся тематики мониторинга ИТ-инфраструктуры, мне опять пришлось столкнуться с очень узким и техническим пониманием этой темы, которое у меня уже когда-то было и поэтому у меня однажды возникла идея изложить это системно. Я даже начал, не торопясь, писать статью на эту тему, но интуитивно понятные вещи не очень хорошо ложились на бумагу – за деревьями не получалось леса. Конечно, у нас у всех есть Google и возможность подсмотреть что пишут другие авторы, но не тут-то было. Бесчисленные статьи и заметки в блогах были посвящены техническим аспектам взгромождения очередной системы мониторинга на очередную версию операционной системы и связанное с этим героическое преодоление трудностей. Cтатей по методологии мониторинга, принципами выбора метрик, правильного построения процесса и увязывания его с бизнесом было очень мало и они также описывали некоторые частные случаи применения мониторинга для решения той или иной проблемы и не более того. А потом мне случайно попалась в руки совсем небольшая книга Дона Джонса «Создание унифицированной системы ИТ-мониторинга в вашем окружении (ENG)».
              Читать дальше →
            • Завершён перевод книги «Pro Git»

                Что может быть лучшим подарком на день знаний для программиста? Конечно, полезная книга ;) Поэтому команда переводчиков «Pro Git» поднапряглась и доделала перевод книги на русский язык.

                «Pro Git» — это довольно обширная обучающая книга о Git от Скотта Шакона — активного участника разработки проектов Git и GitHub. Автор рассматривает в тексте всевозможные аспекты работы с Git'ом, начиная с установки программы и базовых принципов работы децентрализованных систем контроля версий, и заканчивая рассмотрением внутреннего устройства Git'а и созданием валидных объектов в базе Git'а собственными руками. Несмотря на довольно обширный материал и затрагивание довольно специфических тем, книга написана довольно простым языком, содержит массу примеров и иллюстраций, и поэтому должна быть понятна и новичкам, только начинающим знакомиться с системами контроля версий.

                Последняя версия перевода книги доступна в форматах pdf, epub, mobi.
                Также доступна онлайн-версия перевода, но она, к сожалению, не обновлялась с мая.
                Читать дальше →
              • Узнайте бандлер получше

                • Translation
                • Tutorial
                Бандлер оказался замечательным средством установки и отслеживания джемов, которое так нужно каждому руби проекту настолько, что почти каждый проект использует его. Однако, несмотря на его повсеместность, большинство пользователей не знают о встроенных средствах и помощниках бандлера. В попытке повысить осведомленность (и производительность Руби разработчиков), я собираюсь рассказать вам о них.

                Читать дальше →
              • Git Rebase: руководство по использованию

                • Tutorial
                Rebase — один из двух способов объединить изменения, сделанные в одной ветке, с другой веткой. Начинающие и даже опытные пользователи git иногда испытывают нежелание пользоваться ей, так как не видят смысла осваивать еще один способ объединять изменения, когда уже и так прекрасно владеют операцией merge. В этой статье я бы хотел подробно разобрать теорию и практику использования rebase.

                Теория


                Итак, освежим теоретические знания о том, что же такое rebase. Для начала вкратце — у вас есть две ветки — master и feature, обе локальные, feature была создана от master в состоянии A и содержит в себе коммиты C, D и E. В ветку master после отделения от нее ветки feature был сделан 1 коммит B.


                Читать дальше →
              • Локализация ASP.NET MVC приложений

                  На тему локализации уже было несколько статей на Хабре, например Локализация ASP.NET MVC приложения с помощью БД или MVC 2: Полное руководство по локализации, но все-таки проблема до сих пор актуальна.

                  Совсем недавно у нас возникла задача локализации (перевода) интерфейса сайта на другой язык. Наш проект разрабатывается на ASP.NET MVC и в проекте достаточно много клиентского кода на JavaScript и шаблонах jQuery. Еще одним важным моментом для нас является возможность интерактивной работы переводчиков, фактически перевода сайта на лету.
                  Читать дальше →
                • 7 паттернов рефакторинга толстых моделей в Rails

                  Толстые модели сложны в поддержке. Они, конечно, лучше, чем контроллеры, захламленные логикой предметной области, но, как правило, нарушают Single Responsibility Principle(SRP). “Всё, что делает пользователь” не является single responsibility.
                  В начале проекта SRP соблюдается легко. Но со временем модели становятся де-факто местом для бизнес-логики. И спустя два года у модели User больше 500 строчек кода и 50 методов в public.
                  Цель проектирования — раскладывать растущее приложение по маленьким инкапсулированным объектам и модулям. Fat models, skinny controllers — первый шаг в рефакторинге, так давайте сделаем и второй.
                  Второй шаг
                • Работа с виртуальными машинами KVM. Лимитирование ресурсов виртуальной машины



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

                    Читать дальше →
                  • Настройка Nginx + LAMP сервера в домашних условиях. Часть 1: Настройка frontend — backend


                      Здравствуйте. Недавно я задавал вопрос по поводу создания цикла статей. Вот первая статья.

                      В этом цикле статей вы узнаете как грамотно настроить LAMP сервер, аля «хостинг только мощней».
                      Мы будем использовать следующий стек: nginx — apache-mpm-itk — mod_php — mysql — linux/debian.

                      Буду освещать следующие темы:
                      • Настройка frontend — backend
                      • Расчет возможностей сервера, настройка mysql и backend
                      • Рассказ об опыте на базе intel s3420gp

                      Совершенно уверенно могу сказать, что настройка LAMP сервера не ограничивается 6-10 командами установки и раскомментирования определенных строчек в файлах настройки.
                      Пример: по умолчанию nginx не дает возможности закачать на сервер тело запроса больше чем 1M. Если не настроить данный параметр, будет возникать ошибка 414 (Request-URI Too Large), при попытке добавления небольшой серии фотографий.
                      У apache совершенно противоположное: у него тело запроса по умолчанию не ограничено. Это делает возможным совершать пакости.

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

                      Мы узнаем о том какие бывают простые атаки и как от них защищаться. Сразу скажу, что при базовой конфигурации frontend в лице nginx — backend apache все равно остается уязвим.

                      Я практически уверен, что я не смогу уместить все в одну статью. Добро пожаловать под кат.
                      Читать дальше →
                    • Настройка Nginx + LAMP сервера в домашних условиях Часть 2: Настройка backend: PHP + MySQL

                        Здравствуйте.

                        В предыдущей статье, мы познакомились с настройкой связки nginx + apache в режиме хостинга и репозиториями dotdeb.
                        В этой статье мы познакомимся с настройкой backend: PHP, MySQL.

                        В части PHP мы познакомимся со следующими темами:
                        — общая настройка PHP
                        — правильная настройка PHP + Postfix для отправки писем через внутренний SMTP сервер посредством функции mail(),
                        — настройка кеширования кода и/или данных на основе APC.

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

                        Кто заинтересовался, добро пожаловать под кат
                        Читать дальше →
                      • Генерация PDF на сервере в Ruby

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

                        HTML-вёрстка сама по себе имеет немного ценности и не единственное, чем можно нагрузить верстальщика.

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

                        Варианты генераторов для Ruby


                        Согласно сайту Ruby Toolbox существует два принципиальных подхода к генерации PDF-файлов:


                        Первый вариант подразумевает генерацию HTML-страницы и конвертацию её в PDF, в то время как второй позволяет, по факту, работать с canvas и генерировать документ без дополнительных прослоек.

                        Я выбрал вариант с использованием Prawn (по большей части, конечно, по тому, что предыдущая версия PDF-файла генерировалась этим способом) даже не смотря на то, что мне пришлось вынырнуть из привычного мне мира HTML и CSS

                        Тех, кому интересно приглашаю под хабракат.
                        Читать дальше →
                        • +15
                        • 3.6k
                        • 6