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

Прочитав пост Свой сапер на своих батниках и пробежавшись по коду, наткнулся на комментарий, что в батниках нет массивов (кстати, в последней версии Сапера, о котором идёт речь в том посте, нет этого комментария). Так вот, если в батнике необходимо использовать некоторый набор значений, то логично объявить такое кол-во переменных, которое требуется и работать с ними. Собственно данный сценарий эту задачу помогает решить проще. Вот несколько примеров:

echo Создание массива А:
call :array new A "'one','two','three','foo','bar'"
echo Получение третьего элемента в result:
call :array get A 3 result
echo %result%
echo Изменение нулевого элемента
call :array set A 0 "первый элемент"

На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

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

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

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

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

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

Также рискну обрисовать пути решения проблем, состоящие в том, чтобы поменять то, что можно поменять (в основном — себя), а не то, чего изменить нельзя (скажем, рынок труда).

Ошибка №1

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

Я предлагаю взглянуть на корень ошибки (да-да, это ошибка). Если соискатель получает слишком много приглашений — значит, он неправильно составил резюме. Ведь именно резюме послужило причиной лавинообразного интереса.

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

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

Считается, что сборщик мусора – черный ящик, работу которого нельзя предугадать.

А еще говорят, что GC в .NET практически не настраиваемый. А еще, что нельзя посмотреть исходники как классов .NET Framework, так и CLR, GC и т.п.

А я скажу как бы ни так!

В данной статье мы рассмотрим:

• структура организации размещения объектов в памяти
• CLR 4.5 Background Server GC
• правильная настройка сборщика мусора
• эффективный апгрейд приложений до .NET 4.0+
• правильное ручное управление памятью

В прошлом году мы участвовали в выставке TechEd Russia и, конечно, много общались с посетителями. Тогда выяснилось, что российские разработчики хорошо знают нашу компанию как производителя .NET контролов, но мало кто слышал о том, что у DevExpress есть фреймворк — eXpressApp Framework (XAF) — объединяющий большинство наших WinForms и ASP.NET продуктов. Тогда и родилась идея рассказать русскоязычному сообществу o XAF, которая воплощается в жизнь сейчас.

Итак, что же такое XAF и зачем вам предлагается запомнить еще одну трехбуквенную аббревиатуру? Проще говоря, XAF — это фреймворк для быстрой разработки других трехбуквенных вещей, таких как CRM, ERP, EAM, WMS и т.д. (любых приложений для бизнеса).

XAF может быть полезен не только опытным .NET-разработчикам. «Порог вхождения» невысок — можно смело сказать, что приступить к разработке ХАF-приложений можно вообще не имея опыта в .NET. Так что сисадминам-мастерам-на-все-руки XAF может помочь создать серьезное корпоративное приложение и избавиться от вороха расшаренных экселевских таблиц или Access-базы в которые пользователи что-то заносят и пытаются анализировать.

В то же время, продвинутые разработчики могут создавать сколь угодно сложные решения (пример – Галактика EAM).

Наверное, многие уже знают, что 9 и 10 ноября в Москве (в «Крокус Экспо») будет проходить Tech∙Ed Russia 2011 — одна из самых крупных конференций по разработке ПО в нашей стране!

Эта конференция является развитием всем известной Платформы и предполагает участие разработчиков со всего постсоветского пространства. Чтобы оценить её масштаб, достаточно упомянуть 160 докладов в 15 треках, 200 докладчиков и экспертов международного уровня и несколько тысяч рядовых участников.

Мы, Developer Express, выступаем одним из спонсоров конференции. Если вы собираетесь посетить Tech∙Ed Russia в эти дни, обязательно посетите наш стенд в выставочном зале №17. На нашем стенде вы сможете пообщаться с нами на любые интересующие вас вопросы, узнать побольше о наших продуктах и увидеть воочию новинки, которые ожидают вас в следующей версии.

Кроме того, на нашем стенде можно будет зарегистрироваться для участия в розыгрыше ценных призов, который состоится 10 ноября в 15:30. Вы сможете выиграть лицензии на наши продукты (CodeRush, DXperience и eXpressApp Framework), а также поощрительный приз – игровую консоль Xbox ;-)

До встречи на Tech∙Ed!

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

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

Мы называем такой подход RDD — Report-Driven Design.

Приветствую всех читателей Хабра! Решив написать эту статью, я обнаружил на Хабре много материалов по графам и, в частности, по топологической сортировке. Например, здесь довольно подробно описана теоретическая часть и приведены примеры основных алгоритмов. Поэтому не буду повторяться, а расскажу о практической области применения Topological sorting, а точнее, хочу поделиться личным опытом применения этого метода при разработке продуктов DevExpress. Из статьи станут понятны мотивы и причины, побудившие к использованию этого алгоритма. В конце я приведу наш вариант реализации алгоритма для сортировки зависимых объектов.

При разработке DXScheduler for WPF мы получили от пользователя сценарий, в котором использовался MVVM шаблон.
Пользовательский объект назначался свойству DataContext нашего планировщика, а в XAML-разметке осуществлялась «привязка» к соответствующим свойствам объекта с использованием Binding-выражений.
Но возникла проблема — планировщик содержал некий невизуальный объект Storage, который хранил набор настроек для данных. В том виде, в котором были записаны Binding-выражения, свойства объекта-стораджа не обновлялись.

О том, как была решена эта проблема, вы узнаете ниже…

Компания DevExpress объявила о выходе новой версии своего продукта DXperience, который содержит компоненты для программистов, ведущих свою разработку на платформе .NET с помощью MS Visual Studio. Версия DXperience 10.2 содержит множество новых продуктов и улучшений для таких популярных направлений как Silverlight, WPF, ASP.NET MVC, а также традиционных ASP.NET и Windows Forms.

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

Много ли вы видели ноутбуков, которые оснащены GPS датчиком? Примерные оценки можно посмотреть тут, 58 штук из 4380, то есть 1.3%. Прямо скажем — не много. Трудно назвать все причины, по которым производители не оснащают портативные компьютеры, в общем-то, недорогим чипом, но наша заметка как раз о том, как ваш ноутбук снабдить функциональностью геолокации, даже если GPS датчика у вас нет. А заодно вы узнаете, как очень просто получить ваши координаты программным способом.

В своей работе нам приходится писать много тестов. Чтобы делать это быстро, мы используем шаблоны CodeRush. В этой статье мы расскажем вам, как создавать собственные шаблоны для тестирования. В качестве примера возьмём такую задачу: протестировать правильный порядок вызовов защищенных методов класса. Будем использовать только NUnit без применения библиотек типа NMock и им подобных.

В первой части статьи мы рассмотрели script-fu скрипты «Быстрая тень» и «Подрезать уголки» и пообещали показать, как красиво оформить скриншот фрагмента окна. Пришло время исполнить обещанное. Сегодня будем разбирать скрипт «Кадрирование с эффектом волны», который позволяет отсечь часть изображения по волнистым линиям, похожим на синусоиды.

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