Понятно, зачем теоретики находят эффективные алгоритмы решения задач какого-то класса, а потом практики их реализуют. Но теоретики стараются также доказать, что для некоторых задач эффективных алгоритмов (и даже вообще никаких алгоритмов) не существует. Что при этом им удаётся и не удаётся, и зачем это может быть нужно? В лекции речь идет о «проблеме остановки» и задачах, к которым она сводится, о знаменитом классе NP, а также о простых нижних оценках.



Лекция был прочитана в Малой Школе анализа данных, которую Яндекс организует для старшеклассников. Автор — Александр Шень. Окончил мехмат МГУ, под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии». Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.

Под катом — расшифровка лекции.

(Иллюстрации к статье А.П. Ершова «Программирование — вторая грамотность»)

Стив Джобс не написал ни строчки кода, Билл Гейтс — написал. Пол Грэм — первоклассный программист, Питер Тиль — юрист по образованию, сооснователь PayPal и владелец Palantir (написал ли он что-нибудь?), а Илон Маск в детстве написал свою игру и успешно её продал.

Никита truesnow из #tceh сказал мне, что на курсе «Врубаемся в Ruby» они научат программировать любого человека, даже с нуля. Я спросил его: «А с гуманитарием справитесь?» И мы задумались, были ли случаи, когда «гуманитарий» выучил язык программирования?

На ум сразу пришел бомж-программист, но после успеха с его приложением он предпочёл остаться «дзен-монахом». Есть ли еще примеры? Вдохновляющий пример, что научиться кодить может каждый — слепой программист. Когда я прочитал статью на Хабре «Смотря на код с закрытыми глазами», то понял, что нет преград, кроме собственных отмазок.

А у меня для вас есть три истории из моей жизни. Просто три истории.

История первая — ламер

Слово «ламер» я прочитал в «Компьютерре». Там давалось такое определение: «Ламер — отнюдь не безграмотный человек, не умеющий (как бы это помягче выразиться?) программировать». Окрылённый истиной я побежал и рассказал об этом друзьям-одноклассникам, но они предпочли поиграть в футбол, вместо того чтобы освоить суперспособности. Забавно, что потом все они зарабатывали программированием деньги, а я нет. Через неделю я записался в краевую станцию юных техников (КСЮТ), где был кружок по программированию. Там для новичков давали qbasic. А боги прогали на C.

Перевод блог-поста главного автора сборщика мусора в Go, Ричарда Хадсона, изобретателя многих алгоритмов для GC в других языках, одного из ведущих инженеров Intel (сейчас работает в Google).

Go планирует свой сборщик мусора (GC) не только для 2015 года, но и для 2025 и дальше: это должен быть GC, который поддерживает современные принципы разработки программ и хорошо масштабируется вместе с появлением нового софта и железа в следующие десятилетия. В этом будущем нет места для пауз GC с «остановкой мира» (stop-the-world), которые были преградой для более широкого применения таких безопасных и надёжных языков, как Go.

Go 1.5, первый проблеск этого будущего, достиг цели уменьшить верхнюю планку пауз до 10мс, которую мы поставили перед собой год назад. Некоторые впечатляющие цифры вы можете посмотреть в докладе на GopherСon. Эти улучшения времени отклика привлекли много внимания; блог пост Робина Верлангена «Миллиарды запросов в день встречают Go 1.5» подтверждает наши расчеты реальными результатами. Отдельно нам понравились скриншоты графиков продакнш-сервера от Алана Шреве и его комментарий «Holy 85% reduction!».

Управление памятью – одна из главных задач ОС. Она критична как для программирования, так и для системного администрирования. Я постараюсь объяснить, как ОС работает с памятью. Концепции будут общего характера, а примеры я возьму из Linux и Windows на 32-bit x86. Сначала я опишу, как программы располагаются в памяти.

Каждый процесс в многозадачной ОС работает в своей «песочнице» в памяти. Это виртуальное адресное пространство, которое в 32-битном режиме представляет собою 4Гб блок адресов. Эти виртуальные адреса ставятся в соответствие (mapping) физической памяти таблицами страниц, которые поддерживает ядро ОС. У каждого процесса есть свой набор таблиц. Но если мы начинаем использовать виртуальную адресацию, приходится использовать её для всех программ, работающих на компьютере – включая и само ядро. Поэтому часть пространства виртуальных адресов необходимо резервировать под ядро.



Это не значит, что ядро использует так много физической памяти – просто у него в распоряжении находится часть адресного пространства, которое можно поставить в соответствие необходимому количеству физической памяти. Пространство памяти для ядра отмечено в таблицах страниц как эксклюзивно используемое привилегированным кодом, поэтому если какая-то программа пытается получить в него доступ, случается page fault. В Linux пространство памяти для ядра присутствует постоянно, и ставит в соответствие одну и ту же часть физической памяти у всех процессов. Код ядра и данные всегда имеют адреса, и готовы обрабатывать прерывания и системные вызовы в любой момент. Для пользовательских программ, напротив, соответствие виртуальных адресов реальной памяти меняется, когда происходит переключение процессов:

Примеры найденных жучков (источник фото: Интернет)

Дело было еще во Владивостоке.
Знакомые, владельцы турфирмы, рассказали, что однажды уборщица их спросила: «А почему вечером, когда все уходят, у вас сверху, на шкафу что-то мигает?». Полезли на шкаф, а там — чуть ли не автомобильный аккумулятор и рация, прикрученная синей изолентой. Вот такой суровой бывала дальневосточная прослушка.

Я узнал, что компания detsys.ru проводит у себя бесплатное обучение по пользованию индикаторами поля и попросил у них на недельку три экземпляра антижучков и еще парочку имитаторов сигналов для проверки работоспособности поисковой техники, для того чтобы повозиться с ними в Хакспейсе.

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

Внимание! Реклама! Пост оплачен Капитаном Очевидность!

Ниже под катом вы найдёте 15 пунктов, описывающих правильную организацию ресурсов, доступных по протоколу HTTP — веб-сайтов, «ручек» бэкенда, API и прочая. «Правильный» здесь означает «соответствующий рекомендациям и спецификациям». Большая часть ниженаписанного почти дословно переведена из официальных стандартов, рекомендаций и best practices от IETF и W3C.



Вы не найдёте здесь абсолютно ничего неочевидного. Нет, серьёзно, каждый веб-разработчик теоретически эти 15 пунктов должен освоить где-то в районе junior developer-а и/или второго-третьего курса университета.

Однако на практике оказывается, что великое множество веб-разработчиков эти азы таки не усвоило. Читаешь документацию к иным API и рыдаешь. Уверен, что каждый читатель таки найдёт в этом списке что-то новое для себя.

Очень далеко за МКАДом, где бродят только геологи и редкие медведи (забегая вперёд — они те ещё токсикоманы), есть производственный комплекс. На вход приходит добытая руда, на выходе — концентрат, который позже может и жахнуть.


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

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


Это цветной кадр с одной из камер. Всё, вообще всё покрыто серой пылью.

В отличие от тёплых и прельстивых офисов и стерильных ЦОДов, на этом объекте постоянно нехило шарашит электромагнитное излучение от кабелей с ногу толщиной, помехи от пусков разного оборудования. И ещё тут отличная пыль, которая накапливается по сантиметру в сутки.

Демон инициализации systemd де-факто уже стал стандартом в современных Linux-системах. На него перешли многие популярные дистрибутивы: Debian, RHEL/CentOS, Ubuntu (начиная с версии 15.04). В systemd используется принципиально иной (по сравнению с традиционным инструментом syslog) подход к логгированию.
В его основе лежит централизация: специализированный компонент journal cобирает все системные сообщения (сообщения ядра, различных служб и приложений). При этом специально настраивать отправку логов не нужно: приложения могут просто писать в stdout и stderr, a journal сохранит эти сообщения автоматически. Работа в таком режиме возможна и с Upstart, но он сохраняет все логи в отдельный файл, тогда как systemd сохраняет их в бинарной базе, что существенно упрощает  систематизацию и поиск.

Хранение логов в бинарных файлах также позволяет избежать сложностей с использованием парсеров для разных видов логов. При необходимости логи можно без проблем переконвертировать в другие форматы (более подробно об этом будет рассказано ниже).
Journal может работать как совместно с syslog, так и полностью заменить его.
Для просмотра логов используется утилита journalctl. Об особенностях и тонкостях работы с ней мы расскажем в этой статье.

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



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

Думали ли вы когда-нибудь о том, что однажды слишком быстро втянулись в веб-программирование на PHP? И вот уже прошло много лет, у вас хороший опыт, и вы не думаете ни о каких других способах „делать“ веб, кроме как на PHP. Может быть, у вас возникают сомнения в правильности выбора, однако непонятно, как найти способ быстро его проверить. А хочется примеров, хочется знать, как изменятся конкретные аспекты деятельности.

Сегодня я попробую ответить на вопрос: «А что если вместо PHP писать на Python?».

Сам я долгое время задавался этим вопросом. Я писал на PHP 11 лет и даже являюсь сертифицированным специалистом. Я научился его «готовить» так, чтобы он работал в точности, как мне надо. И когда я в очередной раз читал на Хабре перевод статьи о том, как всё в PHP плохо, я просто недоумевал. Однако подвернулся случай пересесть на Ruby, а потом и на Python. На последнем я и остановился, и теперь попробую рассказать вам PHP-шникам, как нам питонистам живётся.

В первой части мы начали изучение Ansible, популярного инструмента для автоматизации настройки и развертывания ИТ-инфраструктуры. Ansible был успешно установлен, описаны принципы работы, базовая настройка. В завершении статьи мы показали как быстро установить nginx на несколько серверов.

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



В этой части вы узнаете, как писать единый Ansible playbook для разных ОС (например с rpm и deb), как обслуживать множество хостов и не писать их все в inventory, как сгруппировать сервера по регионам InfoboxCloud и многое другое.

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

Здравствуй, хабраюзер. Вот и подоспела третья часть моей статьи, которая подытожит цикл (часть 1 и часть 2) статей для начинающих. Эта часть будет посвящена конкретному примеру применения Chef в облаке Amazon. Как я уже упоминал – это достаточно популярный сценарий. Для простоты понимания, будет рассмотрен случай с двумя ec2-instance (виртуальные сервера Amazon), один из которых будет выполнять роль Chef-сервера, а второй – узла.

AWS и Chef

Сразу же уточню, что запускать instance мы будем используя AWS CloudFormation. Можно было бы, конечно, запустить и управлять ними вручную, но какой смысл в такой автоматизации?

Однажды у меня возник интерес к GPS, а еще чуть раньше — к платформе Arduino. Поэтому со Sparkfun были заказаны, с разницей в пару дней, Arduino Duemilanove, GPS Shield и GPS приемник EM-406A.
Заказ пришел и частично лежал на полке, а недавно дошли руки до этого комплекта…

Собранный GPS Shield, подключенный к Arduino

Данный цикл из 5 статей рассчитан на тех, кому стало мало возможностей привычных «тинек» и ардуинок, но все попытки перейти на более мощные контроллеры оканчивались неудачей или не приносили столько удовольствия, сколько могли бы. Все ниженаписанное проговаривалось мной много раз на «ликбезе» программистов нашей студии (которые часто сознавались, что переход с «тинек» на «стмки» открывает столько возможностей, что попадаешь в ступор, не зная за что хвататься), поэтому смею надеяться, что польза будет всем. При прочтении подразумевается, что читающий — человек любопытный и сам смог найти и поставить Keil, STM32Cube и понажимать кнопки «ОК». Для практики я использую оценочную плату STM32F3DISCOVERY, ибо она дешевая, на ней стоит мощный процессор и есть куча светодиодиков.

Каждая статья рассчитана на «повторение» и «осмысление» где-то на один околовечерний час, ибо дом, семья или отдых…

В предыдущем своем посте я попытался коротко ознакомить вас с платформой Nucleo от ST.
В этом посте я хочу рассказать вам на живом примере некоторые сильные стороны этой платформы, которая имеет все шансы потеснить приевшиеся всем Arduino, и показать что все примеры кода и шилды от Arduino, прекрасно подходят для платформы Nucleo.

В этом топике я хотел бы рассказать о том, как устроена кассандра (cassandra) — децентрализованная, отказоустойчивая и надёжная база данных “ключ-значение”. Хранилище само позаботится о проблемах наличия единой точки отказа (single point of failure), отказа серверов и о распределении данных между узлами кластера (cluster node). При чем, как в случае размещения серверов в одном центре обработки данных (data center), так и в конфигурации со многими центрами обработки данных, разделенных расстояниями и, соответственно, сетевыми задержками. Под надёжностью понимается итоговая согласованность (eventual consistency) данных с возможностью установки уровня согласования данных (tune consistency) каждого запроса.

NoSQL базы данных требуют в целом большего понимания их внутреннего устройства чем SQL. Эта статья будет описывать базовое строение, а в следующих статьях можно будет рассмотреть: CQL и интерфейс программирования; техники проектирования и оптимизации; особенности кластеров размещённых в многих центрах обработки данных.

В продолжение темы об оптимизации хоста с VMware ESXi, рассмотрим как поступать со Swap'ом в инфраструктуре живущей на СХД NetApp FAS. Хотя эта статья должна быть полезна и не только владельцам систем NetApp FAS.

Одна из важнейших возможностей виртуализации заключается в возможности более эффективно утилизировать серверное оборудование, что подразумевает Overcommit ресурсов. Если мы говорим об ОЗУ, это означает, что мы можем настроить каждой виртуальной машине больше памяти, чем есть на сервере на самом деле. А дальше мы полагаемся на ESXi, чтобы тот разрулил борьбу за ресурсы — забрал (такой процесс часто называют reclamation) не нужную память одной виртуальной машины и отдал той, которая в ней действительно нуждается. В тот момент когда не хватает памяти, начинается процесс свапинга памяти.

Начнём с того, что есть два типа свапинга, которые могут происходить на ESXi хосте. Их очень часто путают, поэтому давайте условно будем называть их Тип 1 и Тип 2.


Расположение данных VMware ESXi по умолчанию

В продолжение темы об оптимизации хоста для взаимодействия с СХД NetApp FAS, эта статья будет посвещена оптимизации производительности VMWare ESXi, предыдущие статьи были посвящены тюнингу ОС Linux и Windows в среде SAN. Компания NetApp давно тесно сотрудничает с VMware, подтверждением тому может стать тот факт, что нашумевшая технология vVOL была реализована одной из первых ещё в релизе Clustered Data ONTAP 8.2.1 (Август 2014), в то время как vSphere 6.0 ещё даже не выпущен. В связи с чем системы хранения NetApp FAS крайне популярны в этом окружении. Часть про Disk Alignment будет полезна не только владельцам NetApp.

Настройки VMWare ESXi можно разделить на следующие части:

• Оптимизация гипервизора
• Оптимизация гостевой ОС (GOS)
• Оптимальные настройки SAN (FC/FCoE и iSCSI)
• Настройки NAS (NFS)
• Проверка совместимости оборудования, прошивок и ПО

Для поиска узкого места обычно выполняют методику последовательного исключения. Предлагаю перво-наперво начать с СХД. А дальше двигаться СХД -> Сеть (Ethernet / FC) -> Хост ( Windows / Linux / VMware ESXi 5.Х и ESXi 6.X ) -> Приложение.

После ответов на 14 вопросов об индексах, которые вы стеснялись задать, у меня возникло гораздо больше комментариев, уточнений и исправлений. Скомпилировать из всего этого статью выглядело затеей с минимумом пользы. И это заставило меня призадумался, а почему вообще мы должны «стесняться задавать» подобные вопросы? Стыдно не знать? А есть ли способ разобраться, не вгоняя себя в краску? Есть. Причем он избавит от многочисленных неточностей, которыми изобилуют многие «ответы». Вы будете чувствовать буквально каждый байт вашей базы кончиками своих пальцев.

Для этого, я предлагаю «поднять капот» у SQL Server и окунуться в сладостный мир шестнадцатеричных дампов. Может статься, что внутри все гораздо проще, чем вам казалось.