Буквально пару часов назад в Санкт-Петербурге завершился открытый чемпионат по программированию Яндекс.Алгоритм 2013. Состязания состояли из нескольких онлайн-раундов по 100 минут, за победу боролись более 3000 программистов из 84 стран. По результатам трёх отборочных раундов в финал вышли 25 лучших.



Финалисты должны были решить шесть алгоритмических задач за 100 минут. Первое место занял недавний победитель ACM ICPC 2013 в составе команды НИУ ИТМО Геннадий Короткевич (tourist), который набрал меньше всего штрафного времени. Второе место досталось выпускнику НИУ ИТМО Евгению Капуну (eatmore). Третье место занял представитель Тайваня Ши Бисюнь.

В подготовке заданий для чемпионата участвовали специалисты из нескольких стран: России, Беларуси, Польши и Японии. Главными составителями задач стали разработчики минского офиса Яндекса (как и все сотрудники компании, к участию в состязаниях они не допускались). Мы попросили всех авторов разобрать задания, которые они подготовили для участников Яндекс.Алгоритма. Кстати, все задачи не удалось решить никому, лучший результат — три решённые задачи — показали только три участника.

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

Это перевод интересной статьи о дизайнерах и их принципах работы How to Work with Designers.

Чтобы дизайнеры вас понимали, говорите не о показателях, а о пользователях

Чаще всего при этом смысл не особо меняется. К примеру, вы говорите об увеличении конверсии регистраций посетителей сайта на X%. Другими словами, вы хотите упростить для пользователей процедуру регистрации. Вроде бы речь идет об одном и том же, однако сказано разными словами. Дизайнеры лучше воспримут второй вариант, потому что они обычно ближе к пользователям.

Еще примеры таких «переводов»:

• Можем ли мы увеличить кликабельность этой кнопки? → Как нам убедиться, что пользователь знает о новой возможности, которой легко воспользоваться?
• Нужно, чтобы эти изменения не ухудшили показатели → Необходимо убедиться, что эти изменения не доставят пользователям неудобств.

Дисклеймер: для понимания этой статьи требуются начальные знания теории графов, в частности знание поиска в глубину, поиска в ширину и алгоритма Беллмана — Форда.

Введение

Наверняка вы сталкивались с задачами, которые приходилось решать перебором. А если вы занимались олимпиадным программированием, то точно видели NP-полные задачи, которые никто не умеет решать за полиномиальное время. Такими задачами, например, является поиск пути максимальной длины без самопересечений в графе и многим известная игра — судоку, обобщенная на размер . Полный перебор крайне долгий, ведь время его работы растёт экспоненциально относительно размера входных данных. Например, время поиска максимального пути в графе из 15 вершин наивным перебором становится заметным, а при 20 — очень долгим.

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

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

Одним из первых онлайновую версию открыл «Журнал молекулярной биологии» (“Journal of Molecular Biology”) от издательства Elsevier. Как и предполагалось, в первое время посещаемость сайта была крайней малой. Но вскоре в редакции заметили, что одна из статей в выпуске 324, том 1, за 15 ноября 2002 года пользуется повышенной популярностью. Посещаемость этой страницы была во много раз больше, чем у всех остальных. Статья называлась «Молекулярный анализ, локализация ткани и связей Ca²⁺ рианодинового рецептора Caenorhabditis elegans».

Руководство журнала задалось вопросом, что же такого интересного в научной статье о Caenorhabditis elegans.

Вы все еще публикуете проект вручную? Тогда мы идем к вам

Под катом гайдлайн по внедрению CI для .NET проектов «с нуля», включающий:

1. Автоматические ежедневные сборки
2. Уведомления о проблемах
3. Интеграцию с баг-трекером и системой контроля версий
4. Версионирование продукта
5. Версионирование базы данных
6. Автоматизированные выкладки и бекапы

Наш архитектор департамента серверной виртуализации Павел Емельянов дал интервью журналу «Системный администратор». Мы решили опубликовать здесь его интервью, в котором он рассказал о проекте CRIU, о том, как команда разработчиков работает с Linux-сообществом и с Линусом Торвальдсом, и об изменениях, которые могут произойти в области виртуализации в ближайшие годы.

Как-то мы сидели в баре с Джошем Лонгом и ещё несколькими друзьями с работы, когда он обнаружил, что я на «эй, ты!» с математикой. А он как раз недавно наткнулся на вот этот вопрос на StackOverflow и сейчас спросил меня, что это означает:



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

Функционально говоря, Хиндли-Милнер (или Дамас-Милнер) — это алгоритм для вывода типов, основанный на рассмотрении того, как они используются. Он буквально формализует интуитивное знание о том, что тип может быть выведен через функционал, который он поддерживает.

Итак, мы хотим формализовать алгоритм вывода типа для любого заданного выражения. В этом посте я собираюсь остановиться на том, что означает «формализовать что-то», а затем описать «кирпичики» формализации Хиндли-Милнера. Во второй части я дам более конкретное описание этих блоков. Наконец, в третьей части я переведу вопрос со StackOverflow.

Что это?

πfs это революционная файловая система, которая вместо того, чтобы тратить место на вашем жестком диске, хранит все данные в π. Вам никогда больше не придется заботится о свободном месте! Вам говорили, что 100% сжатие невозможно? Да вот же оно!

Как собрать?

πfs собирается элементарно:

./configure
make

Да и использовать его не сложнее:

πfs -o mdd=<metadata directory> <mountpoint>

Где metadata directory — каталог с метаданными (названия файлов, смещение в π), а mountpoint ­— каталог монтирования.

Что же π делает с моими данными?

π — одна из самых важных констант математики, и у нее есть куча интересных свойств (о которых можно прочесть в статье на википедии)
Одним из таких свойств числа π предположительно является нормальность, что означает, что все его числа распределяются равномерно, при условии, что это дизъюнктивная последовательность, т.е. все конечные числовые последовательности находятся внутри него. Если мы рассмотрим число π по основанию 16 (HEX), то это предположение верно. Первая запись об этом была в 2001 году.
Ну а если так, то зачем нам хранить все эти эксабайты данных на винчестерах, если мы можем найти их в π?

Посвящается Чарльзу, sine qua non.


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

Сегодня я расскажу тебе, %username%, именно такую детективную историю. И завязкой в этой истории будет внезапное возникновение вот здесь, под номером 5, одной подозрительно русской фамилии:

www.w3.org/2001/tag

История эта начинается в дождливом марте 2013 года, когда я узнал, что рабочая группа W3C Pointer Events собирает последние комментарии к своей спецификации. (Честно говоря, я совершенно не помню, какая была погода в марте, но мне почему-то хочется, чтобы она была дождливой.)

Продолжение. Первая часть перевода была опубликована вчера.

---

Некого винить, кроме себя

Критики монополии частных издателей предлагают простое решение — журналы с открытым доступом. Так же, как и обычные журналы, они принимают статьи, организовывают процесс рецензирования и публикуют их. Но они не требуют денег за подписку — все статьи свободно доступны онлайн. Чтобы покрыть расходы, они берут с учёных, желающих публиковаться небольшой гонорар (в среднем около 2000 долларов). Рецензенты, которые решают, какие статьи стоит публиковать, не получают денег от журналов, чтобы избежать соблазна принимать всё подряд. В отличие от традиционных журналов, которые требуют исключительных авторских прав в обмен на возможность публиковаться, журналы с открытым доступом практически свободны от копирайтных ограничений.

Если университеты финансируют исследования, и их сотрудники как пишут, так и рецензируют статьи, то почему же они все до сих пор не переключились на журналы с открытым доступом? Успешных примеров таких открытых проектов как Public Library of Science пока очень немного. Всё дело в том, что сложившаяся научная культура делает такой переход очень трудным.

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

Привет!

Многие используют Base64 кодирование, реже Base32 и еще реже ZBase32 (вы знаете о таком?), но не все понимают их алгоритмы. В статье я описываю достоинства, недостатки данных кодировок, а также рассказываю о их реализации.

Этот жестокий мир теплового хаоса

Мы живем в компьютерном мире, а современная электроника в части кремниевых «мозгов» достаточно тёплая вещь — процессоры нагреваются нещадно, как основные, так и специализированные, GPU например. В каждом электрическом изделии присутствуют радиаторы пассивные и если совсем много тепла нужно рассеять — то и вентиляторы.
Как известно, электротехника это наука о контактах. Так же можно сказать, что и теплотехника — тоже наука о контакте, о тепловом контакте и передаче тепла от теплого к холодному посредством конвекции и/или излучения. Но не будем в это углубляться, поговорим о конкретном решении, направленном на уменьшение перегрева оборудования и сопутствующего шума от активных систем воздушного охлаждения в паре металл-металл.

Август 2013

(Это одно из двух эссе по фандрайзингу. Скоро выйдет следующее по тактике фандрайзинга.)

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

Инвесторы ищут стартапы, которые станут очень успешными. Легко сказать! В стартапах, как и в некоторых других областях, распределение стартапов по степени их успешности подчиняется степенному закону, только в стартапах кривая распределения ещё круче. Очень успешные стартапы настолько успешны, что затмевают собою все остальные. А поскольку число крупных успехов в год можно по пальцем пересчитать (есть мнение, что их в среднем 15 успешных стартапов в год), то инвесторы вообще смотрят на стартапы в черно-белых очках – либо у вас есть шанс стать одним из 15, либо нет.

Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

Давно была идея собрать воедино интересные вопросы, касающиеся сетей.

Объединяет их то, что все они довольно простые, но мы подчас о них не задумываемся (я во всяком случае о них не задумывался).
В общем я их собрал, подбил, нашёл ответы.
Итак, блиц опрос:

Начнём с самых низких уровней и с самых простых вопросов

В1. Почему для витой пары выбран такой странный порядок: синяя пара на 4-5, разрывая зелёную, которая на 3, 6?

В2. В стандарте Ethernet между кадрами всегда имеется промежуток, называемый IFG (Inter Frame Gap) длиною 12 байтов. Для чего он нужен, и почему он присутствует в современных стандартах?

Мы, портал Айти-Событие.рф, 31 июля провели Первую IT-мастерскую совместно с компанией EMC Corporation. Лектором выступил руководитель направления Mainframe в рамках подразделения ESD (Enterprise Storage Division) корпорации EMC Сергей Поспелов. Сергей рассказывал о суперкомпьютерах и о внутренней архитектуре систем корпоративного уровня.

Введение

Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:

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

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

Такое решение верное, и задача прошла все назначенные ей тесты. Однако мой преподаватель сказал, что задачу можно решить намного красивее. Так я и познакомился с замечательной конструкцией: деревом Штерна — Броко.

    На написание данного текста меня сподвигло ощущение незнания многими принципов работы, использования (или даже незнание о существовании) параллельной защиты от импульсных перенапряжений в сети, в том числе и вызванных разрядами молний
    Импульсные помехи в сети довольно распространены, они могут возникать во время грозы, при включении/выключении мощных нагрузок (поскольку сеть это RLC цепь, то в ней при этом возникают колебания, вызывающие выбросы напряжения) и многие другие факторы. В слаботочных, в том числе цифровых цепях, это еще более актуально, поскольку коммутационные помехи достаточно хорошо проникают через источники питания (больше всего защищенными являются Обратноходовые преобразователи — в них энергия трансформатора передается на нагрузку, когда первичная обмотка отключена от сети).
    В Европе уже давно де-факто практически обязательна установка модулей защиты от импульсных перенапряжений (далее буду, для простоты, называть грозозащитой или УЗИП), хотя сети у них получше наших, а грозовых областей меньше.
    Особо актуальна стало применение УЗИП последние 20 лет, когда ученые стали разрабатывать все больше вариантов полевых MOSFET транзисторов, которые очень боятся превышения обратного напряжения. А такие транзисторы используются практически во всех импульсных источниках питания до 1 кВА, в качестве ключей на первичной (сетевой) стороне.
    Другой аспект применения УЗИП — обеспечение ограничения напряжения между нейтральным и земляным проводником. Перенапряжение на нейтральном проводнике в сети может возникать, например, при переключении Автомата ввода резерва с разделенной нейтралью. Во время переключения, нейтальный проводник окажется «в воздухе» и на нем может быть что угодно.

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!