Есть такая интересная задача — построение 3D структуры по набору изображений (фотографий) — Structure from Motion. Как её можно решить? После некоторых размышлений приходит на ум такой алгоритм. Найдём на всех изображениях характерные особенности (точки), сопоставим их друг с другом и триангуляцией найдём их трёхмерные координаты. Тут правда есть проблема — неизвестно положение камер при съёмке. Можно ли их найти? Вроде можно. Действительно, пусть у нас N точек на кадре и M кадров. Тогда неизвестных будет 3 * N (трёхмерные координаты точек) + 6 * (M — 1) (координаты камер (вместо 6 может стоять другое число, но сути это не меняет)). Уравнений же у нас 2 * M * N (у каждой точки на каждом изображении есть две координаты). Выходит, что уже для двух изображений и 6 точек задачка разрешима. Под катом описание принципиальной схемы решения задачи SfM (по возможности без формул — но со ссылками для вдумчивого изучения).

Источник: www.sciencephoto.com

Немногие знают об Эрнсте Александерсоне. Имя этого очень талантливого инженера теряется в сиянии имен его блистательных коллег — Томаса Эдисона, Гульермо Маркони, Николы Тесла, Александра Попова… Однако на счету Александерсона 345 патентов на изобретения, связанные с электротехникой и радиоэлектроникой, и он по праву считается одним из пионеров радиовещания и телевидения; последний свой патент он получил, будучи в возрасте 89 лет! В отличие от знаменитых изобретателей, чьи имена у всех на устах, Александерсон не стремился к славе, не участвовал в громких скандалах и историях, а просто работал, придумывая и создавая очень нужные и важные для зарождающейся радиоэлектроники устройства.

Читая главу «Двоичные деревья» из книги Джона Монгана Programming Interviews Exposed я задумался о том, как чаще всего рекурсию объясняют начинающим программистам: через сортировку, обход двоичного дерева, построение последовательности Фибоначчи и т.д. Неужели нельзя найти пример поинтереснее? Из закоулков сознания вырвался Лисп, который по своей природе неотделим от понятия рекурсии. Более того, небольшой интерпретатор Лиспа — отличный пример для исследования рекурсии.

Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.

«В 1997 году Deep Blue обыграл в шахматы Каспарова.
В 2011 Watson обставил чемпионов Jeopardy.
Сможет ли ваш алгоритм в 2013 году отличить Бобика от Пушистика?»

Эта картинка и предисловие — из челленджа на Kaggle, который проходил осенью прошлого года. Забегая вперед, на последний вопрос вполне можно ответить «да» — десятка лидеров справилась с заданием на 98.8%, что на удивление впечатляет.

И все-таки — откуда вообще берется такая постановка вопроса? Почему задачи на классификацию, которые легко решает четырехлетний ребенок, долгое время были (и до сих пор остаются) не по зубам программам? Почему распознавать предметы окружающего мира сложнее, чем играть в шахматы? Что такое deep learning и почему в публикациях о нем с пугающим постоянством фигурируют котики? Давайте поговорим об этом.

Есть старые игры, которые можно назвать легендарными. Спустя десятилетия у них сохраняется большая аудитория увлечённых игроков. Среди таких легенд — Doom, «Цивилизация». К ним же относится и пошаговая стратегия UFO: Enemy Unknown (X-COM).

С момента первоначального выпуска X-COM в 1994 году создано более десятка «клонов» или «духовных преемников» этой игры. И вот сейчас сообщество завершило работу над OpenXcom 1.0 — первым мажорным релизом свободной версии OpenXcom. В свободной версии поддерживается большее разрешение, добавлены новые фичи и исправлены многие баги оригинальной X-COM.

Как-то поиграв в оффисе в hexbug, зародилась идея написать игрушку по схожим мотивам.
По текущему роду деятельности я веб разработчик и поэтому захотелось чтобы в игре использовался только HTML, JavaScript и CSS — средства знакомые каждому вебразработчику. Никакого вам flash или даже canvas. Звучит хардкорно, но на самом деле сейчас HTML + CSS3 это очень мощные и гибкие средства визуализации, а писать игровой код на JavaScript — одно удовольствие. Вдобавок захотелось чтобы игра была с сетевым мультиплеером, притом интерактивной — никаких там шашек, карточных игр, пошаговых стратегий, все должно быть в действии и движении.

Вот что получилось в итоге:



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

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

Статья, которую я предлагаю вам почитать, не нова — она опубликована аж 29 марта. Но на Реддите ее запостили всего несколько дней назад, да и актуальности своей она точно не потеряла. Интересность ее в том, что автор на простом и коротком примере демонстрирует практическое применение трех больших и популярных библиотек: numpy, scipy и pygame. Про первые две многие слышали, но все больше в контексте научных работ, так что интересно посмотреть на их применение в «обычной» жизни. В конце статьи прекрасная видео-демонстрация результата, хотя бы ее точно стоит посмотреть.

Авторский код сохранен без изменений, несмотря на то, что он оформлен не по PEP-8 и за его валидность я не ручаюсь. Настоящий рабочий код так или иначе есть на ГитХабе, ссылку вы найдете в конце статьи.

Запишите звук, измените тон 50 раз и сопоставьте каждому новому звуку клавишу на клавиатуре компьютера. Получится Пианопьютер!

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



Согласно условиям теста Тьюринга, он считается пройденным, если программе удастся убедить в своей человечности хотя бы 30% судей в процессе 5-минутного текстового общения.

Некоторые приятные сюрпризы предугадать просто невозможно.

Хотите посмотреть на исходные коды одних из самых первых 3D-игр, да еще и за авторством знаменитого игрового программиста? Пожалуйста! Вашему вниманию предлагаются исходные коды таких игр, как Catacomb 3-D и Hovertank 3D. Написаны игры когда-то были в Borland Turbo Pascal и Borland C++ 2.0; выложены сегодня под лицензией GPL.

Когда-то Кармак набивал руку на Hovertank 3D (считается самым первым в истории шутером от первого лица). Потом был Catacomb 3D: The Descent (выпущенный все еще Softdisk — но разработанный уже id Software). Обе игры вышли в 1991 году, и вроде как особым успехом не пользовались. Однако, в 1992 году прогремел Wolfenstein 3D, навсегда изменивший мир шутеров. Видимо, открытие исходных кодов приурочено к выпуску новой (и на удивление хорошей) части этой серии. Если вам интересно узнать про историю этих игр чуть больше, то можете почитать мой перевод.

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

Введение

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

Наука и жизнь, №3, 1998

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

Синоптики предсказывают, что к 2016 году наступит второй ледниковый период трафик в беспроводных сетях на 10% превзойдёт трафик в проводном Ethernet. При этом от года в год частных точек доступа становится примерно на 20% больше.

При таком тренде не может не радовать то, что 80% владельцев сетей не меняют пароли доступа по умолчанию. В их число входят и сети компаний.

Этим циклом статей я хочу собрать воедино описания существующих технологии защит, их проблемы и способы обхода, таким образом, что в конце читатель сам сможет сказать, как сделать свою сеть непробиваемой, и даже наглядно продемонстрировать проблемы на примере незадачливого соседа (do not try this at home, kids). Практическая сторона взлома будет освещена с помощью Kali Linux (бывший Backtrack 5) в следующих частях.

Статья по мере написания выросла с 5 страниц до 40, поэтому я решил разбить её на части. Этот цикл — не просто инструкция, как нужно и не нужно делать, а подробное объяснение причин для этого. Ну, а кто хочет инструкций — они такие:

Используйте WPA2-PSK-CCMP с паролем от 12 символов a-z (2000+ лет перебора на ATI-кластере). Измените имя сети по умолчанию на нечто уникальное (защита от rainbow-таблиц). Отключите WPS (достаточно перебрать 10000 комбинаций PIN). Не полагайтесь на MAC-фильтрацию и скрытие SSID.

Оглавление:
1) Матчасть
2) Kali. Скрытие SSID. MAC-фильтрация. WPS
3) WPA. OpenCL/CUDA. Статистика подбора

Или как я перестал бояться и полюбил ассемблер

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

Хорошая мера защиты — обновления программного обеспечения. Китайские клоны автоматически отмирают после каждой новой прошивки, а лояльные пользователи получают нашу любовь, заботу и новые возможности. Робин Гуды при таком раскладе, естественно, достанут свои логические анализаторы, HEX-редакторы и начнут ковырять процесс прошивки с целью ублажения русско-китайского сообщества.

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

Прямая трансляция по ссылке. Уже ИДЕТ!
Запуск прошел успешно!
Стыковка с МКС успешна!
Все системы работают нормально.

Прямая трансляция запуска ТПК «Союз ТМА-13М». Космодром Байконур.

Начало: 20:55:00 28 мая 2014 (Время московское, МСКЛВ).
Окончание: 00:55:00 29 мая 2014 (Время московское, МСКЛВ).
Время запуска: 23:57:42 28 мая 2014 (Время московское, МСКЛВ).

Видео-трансляция велась и с борта космического корабля.
Подробнее о миссии Союз ТМА–13М.

Возникла передо мной задача — автоматически выполнять действие при вставке какого-нибудь storage device в Дебиане. К примеру, просто автоматически монтировать его. А может, монтировать и синхронизировать данные, если устройство известно. А может, проверять его clamav на всякую фигню и запускать на нём что-нибудь типа USB-вакцины. Может, и включить сирену, если владельца рядом с компьютером нет =)

К примеру, есть у меня флешки, штук этак 5-7. На каждой записано что-то своё, одна — загрузочная, одна с документами, одна с программами, одна с музыкой и с фотками… И стоит дома сервер, на котором все-все копии того, что на флешках, есть. Хотелось бы мне, чтобы с одной флешкой синхронизировались документы, с другой — музыка и фотки, с третьей — загрузочные образы, и так далее. Только вот нужно это дело как-то автоматически запускать, потому как не годится каждый раз через SSH на сервер лезть и ручками всё править. Поэтому нужно что-то, где можно было бы флешки прописать и действия, нужные при подключении, задать. А там один раз скрипт синхронизации написал — и готово.

Только вот ничего готового и полностью подходящего в Гугле не нашлось. Часть решений тянут за собой кучу зависимостей и не рассчитаны на headless-установку, часть устарели, часть не имеют всего необходимого функционала, а часть позволяют это сделать, только вот слишком муторно, настраивать трудно, и вообще, NIH ;-) Поэтому написал я свой демон автоматического монтирования, ну и выкладываю его сюда, может, пригодится кому-то ещё, может, такому же владельцу домашнего сервера, который точно так же хочет синхронизировать флешки с домашним NAS. Да и хочется, чтобы кто-нибудь код покритиковал, на ошибки указал и решения некоторых проблем подсказал — смотреть в конце топика.

Windows принято не любить. Однако, зачастую, фраза: «Книгу писателя не читал, но осуждаю» очень хорошо описывает эту ситуацию. Несмотря на укоренившееся презрение к «Винде», отдельные вещи в ней реализованы весьма удачно, и именно об одной из них мы хотели бы написать. Отдельные фрагменты WinAPI, хотя и были реализованы достаточно давно, по разным причинам, и часто незаслуженно, выпали из поля зрения широкой аудитории.
В этой статье речь пойдёт о встроенной в ОС реализации lock-free стека и сравнении его производительности с кросс-платформенными аналогами.

Arduino, RaspberryPi,… Эти слова всё чаще встречаются в Сети в контексте создания управляющих контроллеров для всякого применения, от умного дома до мигания светодиодами. Несмотря на техническую навороченность, эти железки до ужаса скучные. Посудите сами: подал питание, загрузил программу,… и всё! А что делается внутри кремния, установленного на печатную плату — сие нам не ведомо. Или неинтересно?
Поводом решения проблемы «неинтересности» стала любовь к процессору 6502, на котором собирались первояблоки и еще кое-кем помнимые «Агаты», а также кучка валяющихся без дела микросхем. Схем на этом процессоре в Интернете много, но тех, которые могли бы быть полезными в хозяйстве — практически нет. Результат работы — контроллер «Аюша», уже готовый захватывать управлять миром, помогать нам в любительской лаборатории, схемотехнику которого мы знаем, можем изменять по своим прихотям, и который в большинстве случаев применения заменяет *дуины и аналогичные борды.

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

Сайт Noisli содержит коллекцию фоновых шумов на любой вкус и возможность смешивать их в произвольной пропорции. Здесь есть и звуки природы — шум дождя, плеск воды, пение птиц, шуршание листьев, и звуки техногенного характера — стук колёс поезда, звук работающего вентилятора, и звуки многолюдного кафе. Есть и искусственные белый, розовый и коричневый шум. Коллекция звуков постоянно пополняется.

Думаю, многие знакомы с весьма необычной игрой Minecraft (справа — пример сгенерированной в ней карты), в которой игрок находится на (практически) бесконечной поверхности Земли и может исследовать окружающий мир с минимальными ограничениями.

Как же автору игры, Notch'у, удалось добиться подобного сходства его случайных «миров» с земными просторами? В этом топике я как раз и рассмотрю один из способов построить искусственный ландшафт такого рода (и вскользь упомяну пару других способов), а также расскажу о моем небольшом усовершенствовании этого алгоритма, позволяющем значительно увеличивать размеры ландшафта без заметных потерь в производительности.

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

Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

В один прекрасный день надоедает нажимать Shift, чтобы вывелся символ ~ вместо `.
Надоедает тянуться до Esc, при этом клавишей CapsLock пользуетесь РЕДКО.
Надоедает смещать кисть вниз и нажимать Ctrl/Cmd/Win слабым мизинчиком, либо, не дай бог, тянуться до них большим пальцем.
Надоедает лезть за PgUp, PgDn, Home и End, двигая руку каждый раз, чтобы всего лишь промотать страницу вниз.
Надоедает каждый раз, когда вы делаете опечатку, со злобой смотреть на клавиатуру в поисках кнопки Backspace.



Сегодня мы узнаем, как навсегда избавиться от этих мучений.

Зачем это всё?

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

Многие раскладки для печати (Dvorak, Colemak и т.п.) сильно улучшают расположение клавиш, ставя их ближе к тем местам, куда нужно меньше тянуться. Но при этом совершенно забывают о модификаторах, спец. символах и командных клавишах (Enter, Backspace, Tab, Esc, Delete). А мы подумаем о том, как улучшить существующее положение вещей.

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