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

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

Абрахам Маслоу

Введение

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

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

Вспоминаю времена, когда молодым и глупым аспирантом, я писал первый вариант кандидатского «кирпича», предназначенный для тщательного «вычитывания» мной и моим научным руководителем. Тогда я не знал о формате EPS, а поэтому экспортировал графики, построенные в Maple в *.bmp-растр и вручную… обводил их в MS Visio для последующей вставки в Word. Были и другие, не менее топорные глупости. Не удивительно, что тогда я проклял всё, и дал себе слово следующую диссертацию писать совершенно по другому.

Путем последовательных итераций, на сегодняшний день я пришел к такому вот решению:



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

Как ранее сообщалось на GeekTimes, EFF при поддержке Mozilla, Cisco, Akamai, IdenTrust и исследователей из Мичиганского университета (University of Michigan) создали новый некоммерческий центр сертификации (Certificate Authority) Let's Encrypt [1]. Целью проекта является ускорение перехода всемирной паутины от HTTP к HTTPS.

Прошел ровно месяц с момента публикации о системе imarker, коммерческой веб-аналитике, которая, по заверению самой системы на тот момент, должна была стоять у Акадо, ТТК, Ростелекома, Эр-Телекома, NetByNet и QWERTY, однако, сейчас официальный сайт изменили, и теперь они заявляют, что работают только с МГТС, Акадо, ТТК, Ростелекомом и QWERTY.

Last-Modified: Fri, 30 Jan 2015 12:57:16 GMT

На самом деле, все немного иначе.

Сухая статистика

Как вы, возможно, помните, я сделал специальную страницу, которая определяет наличие imarker у заходящего на нее посетителя. К сожалению, первые дни она работала не лучшим образом из-за rate limit со стороны imarker, поэтому, чтобы обойти это ограничение, чуть позже я сделал автоматическую генерацию домена нижнего уровня. Также, было незначительное количество ложных срабатываний из-за того, что люди делились сгенерированными уникальными ссылками, а не основной, из-за чего иногда получалось так, что пользователь, у которого нет imarker, дает уникальную ссылку другому пользователю (другу/знакомому/etc), у которого провайдер использует imarker, и, в конечном итоге, заход imarker засчитывается первому. Таких случаев около пары десятков, все они были проверены вручную по логам веб-сервера.

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

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

Но прежде, чем «запустить» материал, еще небольшое отступление. О том, почему вообще я все это писал. Дело в том, что у нас в странах бывшего СССР с образованием в области IT очень туго. С одной стороны нет программ обучения, которые подготовят специалистов на должном уровне (наверное, за очень редкими исключениями, которые можно отнести к погрешности). С другой стороны, из-за широких возможностей самообразования, программисты и не спешат учиться в ВУЗах — все стремятся начать практиковать как можно раньше. Часто изучается только одно направление (например PHP+Mysql — самое популярное) и в бой. Причем, на этом все заканчивается. В итоге у нас огромное количество программистов, которые и базовых вещей не знают. Отсюда вытекают проблемы с качеством кода, и с эффекивностью алгоритмов, с велосипедированием.

Но программирование — это полноценная область знаний, которая требует в том числе и инженерной подготовки. Точно так же, как строительство или телекоммуникации. Да, построить дом (особняк) можно своими руками и без образования. А поднять большинство сайтов можно прочитав пару книг по PHP и HTML. Но многоэтажку без специальной подготовки не построишь, как и Гугл не напишешь, не зная основ.

Возможности для самообразования в компьютерных науках сейчас огромны. Единственное, чего не хватает, — это системности подготовки. Как разобраться, что и в какой последовательности изучать? Мне кажется, что этот материал поможет разложить по полочкам области знаний в компьютерных науках и составить для себя программу изучения по книгам. Выбор книг — тема отдельная, в рамки статьи не входит, но это можно обсудить в комментариях.

Поехали.

UPDATE 1
UPDATE 2

Думаю, что многим будет полезен мой опыт поиска работы программистом за границей. Тем более что он совершенно отличается от описанного в публикации «Как айтишнику уехать в Германию. Часть 1».

Сразу скажу, что я женат и у меня двое детей 5 и 11 лет. Это я говорю к тому, что требования к условиям переезда для семейного человека выше, чем без детей или вообще без семьи. Например, необходимо учитывать увеличение расходов на минимум 3-к квартиру, коммунальные услуги из расчета на 4 чел, платное образование и его уровень. Также важен транспорт, так как каждый день детям нужно добираться в школу и из школы. Еще одним важным критерием выбора страны для переезда является уровень медицины и экология. И наконец, расходы на содержание семьи из 4 человек на порядок выше чем на двоих и тем более — для одного. Все это ставит довольно жесткую нижнюю планку по зарплате.

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

В общей сложности поиск работы мне занял 9 мес. Страной назначения я выбрал Германию, так как IT там на высоком уровне, огромное количество стартапов, особенно в Берлине, высокий уровень бесплатного образования и сильная медицина. К тому же я более менее знал немецкий.

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

В комментариях к одной из ссылок на Hacker News некто утверждал, что использование Rust предотвратило бы Heartlbeed, что код бы даже не скомпилировался. Это прозвучало как вызов!

Тред начинается вот здесь. Я не собирался ни к кому придираться, но утверждение о предотвращении Heartbleed оказалось удачно сформулировано. В отличие от расплывчатых заявлений о безопасности работы с памятью в целом, конкретно данное утверждение можно протестировать.

Довольно часто в программе, работающей с базой данных, в качестве идентификаторов сущностей используются значения целочисленного типа (например, long). Но людям свойственно ошибаться, и программист может по ошибке использовать идентификатор одного типа сущности для адресации другой. Такая проблема может долго оставаться незамеченной, если идентификаторы сущностей пересекаются, а такое бывает довольно часто. К счастью, в языках, позволяющих манипулировать типами, коим является C++, есть довольно простое решение этой проблемы.

Читая М. Липовача «Изучай Haskell во имя добра!», я поначалу не понимал, чем частичное применение отличается от каррирования. Потратил некоторое время на разбор данного вопроса и набросал себе «шпаргалку» по обозначенной теме.

Однажды мне окончательно надоели странички вроде «данный ресурс заблокирован по требованию», которые стали попадаться все чаще и чаще. А еще все больше стало упоминаний про «глубинный интернет», i2p, tor, onion, анонимные p2p сети и вообще повеяло хакерской романтикой детства, когда интернет был чем-то загадочным и был доступен только с двух часов ночи со скоростью 31200…

В общем, была поставлена цель: сделать прокси сервер, через который можно заходить на любые сайты (включая сайты в доменах .i2p и .onion) в обход любых блокировок. Цель обеспечения анонимности не ставилась.

Ужа с ежом удалось скрестить, и вот теперь я, как и 17 лет назад, исследую глубинные слои интернета. Кстати, если говорить про i2p, то скорость по ощущениям не намного больше, чем у интернета 17 лет назад. История циклична.

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

Как это работает:

Основным прокси сервером явлется squid.
Через cache_peer (вышестоящий прокси) squid подключается к i2p и tor. tor является Socks прокси, а squid — http прокси, поэтому между squid и tor встраивается прослойка privoxy.
Также мы имеем обновляемый ACL список всех заблокированных ресурсов в русском интернете.
Squid обрабатывает запросы от браузеров следующим образом:
Если запрашивается URL в домене .i2p, то запрос передается по цепочке в i2p.
Если запрашивается URL в домене .onion, то запрос передается по цепочке в tor.
Если запрашивается запрещенный URL, то запрос передается по цепочке в tor.
Все остальные запросы отправляются напрямую самим squid.

Инструкция как сделать интернет без ограничений своими руками:

Не успела наша команда разработчиков Марьяжа для Android протрезветь после празднования нового 2015 года, как в отзывах на Google Play начали сыпаться единицы за “тормоза”. Единицы сыпались от пользователей достаточно мощных устройств вроде Nexus 5, 6 и 7. Единственное, что их объединяло — это операционная система: Android 5 (Lollipop).

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

И сегодня первая серия — про вопрос, который позволяет не только перенаправить недовольство человека в конструктивное русло, но и может послужить началом многолетнего сотрудничества между людьми, которые вначале друг другу не очень нравились.

А началось все в далеком 2007 году, когда я решил сделать свой первый тренинг. Из этой активности, кстати, тогда родилась книга “Секреты управления программистами” (выложена бесплатно вот в этом пакете книг, требует регистрации), но сейчас не об этом. Вернее, не совсем об этом.

Привет, %username%!
Пользуешься неофициальными bitcoin клиентами? Есть повод присмотреться к ним повнимательней.
После реализации бэкдора для RSA мне стало интересно, как обстоят дела с остальными криптографическими примитивами. Оказывается, целая наука под названием клептография занимается передачей информации в так называемых «подсознательных» каналах. Таких, о которых никому не известно кроме отправителя и получателя. Вроде стеганографии, только внутри криптоалгоритмов.

     Проблема факторизации составных натуральных чисел (сннч) многие столетия удерживает внимание специалистов в различных теоретических (научных) и прикладных областях таких как числовые системы, вычислительная математика и техника, теория чисел, информационная безопасность, криптография, и др., и вынуждает их прикладывать немалые усилия к ее положительному и успешному решению. Тем не менее, проблема и сегодня далека от ее закрытия, завершения. Автор предлагает к рассмотрению и стремится дать читателю понятие о существующих подходах к решению проблемы, ставших уже своеобразной классикой, привести критику и выразить одобрение замечательным находкам.
     В работе излагается один из известных подходов к решению задачи факторизации больших чисел (ЗФБЧ), использующий математику эллиптических кривых (ЭК). Об этой математике, а точнее о технике вычислений приведу цитату авторов из [ 1 ] «Техника, используемая в настоящее время при изучении ЭК, является одной из самых изощренных во всей математике. Мы надеемся, что элементарный подход настоящей работы побудит читателя к дальнейшему изучению этой живой и пленительной ветви теории чисел. Есть много того, что следует изучить, и много работы, которую еще надо проделать. „

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

Большинство уязвимостей в веб сайтах являются результатом изменения HTTP запроса, подмены URL или заголовков, и прочие неожиданные для сервера действия. Обычный пользователь не должен иметь возможности так делать, но так как современное приложение состоит из клиента и сервера, то в реальности сервер не имеет контроля над тем как пользователь использует клиентскую часть.

Из-за этого «двойная валидация» встречается повсеместно — на экране нужно показывать только объекты доступные пользователю, плюс нужно на сервере проверять имеет ли пользователь доступ к данному объекту.

Так возникла идея SecureCanvas — превратить сайт в подобие АТМ/терминала, где пользователь может только печатать и двигать мышку. Вместо попытки перехватить вредоносные запросы мы просто переводим игру в другую плоскость и снижаем поверхность атаки до нуля, разрешая пользователю делать лишь то что он и должен делать — взаимодействовать с сайтом.

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

[первая часть]

Мониторинг пути перемещения документа в Сети классифицируется, как «тривиальная» цель. Запись чата в Facebook – «несложная» задача, в то время как уровень сложности дешифровки писем, отправляемых через российский провайдер интернет-сервисов Mail.ru, рассматривается, как задача «умеренной сложности». Но все три эти уровня классификации не представляют серьезных проблем для АНБ.

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

(Продолжение серии рассказов про Данию)

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

О себе: мне 31 год, я из Севастополя (да, на Хабре земляков всё больше), окончил СевНТУ. У меня красавица-жена и семилетний сын. Занимаюсь образовательным проектом. До переезда в Данию мы 6 лет жили в Киеве.

Причины переезда

Мы не «поравалитики». В целом, нам отлично жилось вна Украине. Конечно, мы понимали, что кругом многим не сладко. Так или иначе, сбежать из страны, прихватив трактор, не тянуло.

Вся идея изначально исходила от жены, её доводы были таковы:

1. посмотреть мир,
2. дать сыну возможность выучиться в мультиязычной среде.

Доводы хорошие, но меня убедили совсем другие вещи:

Знакомьтесь, это обычный «литровый» пакет молока:

• Проверка на внимательность: там 900 грамм. Рядом несколько по 950. Но пакет может быть воспринят как литровый.
• Проверка на знание физики. Рядом лежит похожий кефир. Объём измеряется в миллилитрах, масса — в граммах. Плотность кефира трагически выше плотности воды. То есть 900 грамм кефира 3,2% жирности — это примерно 874,5 миллилитров.

Второй пациент:



25 лет гарантии. Круто, правда? Есть одна проблема. Надо сохранять чек. Проверка, опять же, на знание физики. Чек у них печатается на обычной кассовой термоленте (я проверил на месте). У меня в офисе лежит много чеков. Мы их ксерокопируем, потому что через год-два они полностью выцветают. Самый старый чек, который видел коллега, держался 3 года в папке в архиве. UPD: смотрите самый низ топика, Икея ответила.

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

Осторожно, трафик: под катом много находок с фотографиями.