С недавних пор существует элегантная формула для вычисления числа Пи, которую в 1995 году впервые опубликовали Дэвид Бэйли, Питер Борвайн и Саймон Плафф:


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

Намедни прочел интересную статью про рейтинги. В качестве практического руководства ее не рекомендую использовать (почему смотрите в комментариях к ней), однако, чтиво интересное и натолкнуло меня на одну мысль.
Допустим у нас есть рейтинг от 1 до 5. И некоторые оценки накручены, некоторые пользователи наобум поставили. Как отфильтровать зерна от плевел?

Итак, тема рейтинговых систем продолжает будоражить умы хабрапользователей. Появляются всё новые и новые схемы, формулы, тесты. И каждый раз всё сводится к одному и тому же вопросу: как совместить среднюю оценку пользователей с нашей уверенностью в этой оценке. Например, если один фильм получил 80 положительных и 20 отрицательных голосов, а другой — 9 положительных и 1 отрицательный, то какой из фильмов лучше? Не претендуя на создание новой универсальной рейтинговой системы, я всё же предложу один из возможных подходов к решению именно этого вопроса.

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

Гомоморфное шифрование — криптографическая система, которая позволяет проводить определенные математические действия с открытым текстом путем произведения операций с зашифрованным текстом.

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

На днях появилось видео очередных испытаний приводнения корабля «Орион».



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

В прошлый раз (почти год назад) мы определяли части речи в русском тексте, производили морфологический анализ слов. В этой статье мы пойдем на уровень выше, к синтаксическому анализу целых предложений.

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

"Мама мыла раму":

(предложение
    (именная гр. (сущ мама))
    (глаг. гр. (глаг мыла)
        (именная гр. (сущ раму)))
    (. .)))

Это называется синтаксическим деревом предложения. В графическом виде его можно представить следующим образом (в упрощенном виде):

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

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.

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

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

Данная инструкция содержит пошаговый алгоритм установки и настройки LXD. Инструкция рассматривает следующие темы:

— Установка и запуск контейнера.
— Настройка сети.
— Настройка статических IP адресов для контейнеров.
— Настройка NAT и Iptables.
— Создание бэкапов и восстановление из них.
— Отличительные особенности от Docker.

Продолжаем наш цикл статей о контейнеризации. Если первые две статьи (1 и 2) были посвящены теории, то сегодня мы поговорим о вполне конкретном инструменте и об особенностях его практического использования. Предметом нашего рассмотрения будет LXD (сокращение от Linux Container Daemon), созданный канадцем Стефаном Грабе из компании Canonical.

Любой, кто интересовался игровым или околоигровым контентом в сети, будь то видео на youtube, игровые паблики в социальных сетях или просто стримы на Twitch, сталкивался с рекламой площадок G2A.com, gabe-game-easy-и-прочих-сторов.

Этой рекламы, вместе с рекламой различных сервисов ставок и не самых чистоплотных скин-рулеток настолько много, что часть аудитории уже перестала обращать на нее внимание, ведь кто поведется на текст «Купи любимую игру в два раза дешевле!», когда это возможно только в период скидок?

Как вообще подобные площадки существуют столько лет и чем они занимаются?

KolibriOS – миниатюрная операционная система, ядро и большинство программ которой написано на языке ассемблер. Это, конечно же, не означает, что другим языкам программирования путь в KolibriOS закрыт. К примеру, за время эволюции этой операционной системы было несколько попыток разработать инструментарий или адаптировать библиотеки для создания приложений на языке C/C++. В репозитории KolibriOS до сих пор есть работающие примеры, использующие ранние наработки адаптации C/C++ кода, например (root)/programs/games/kosilka или (root)/programs/system/shell, использующие разные подходы и обертки C/Asm.

На текущее время самой перспективной из существующих библиотек, на мой взгляд, является newlib. Она состоит из адаптированной libc, C-оберкой над основными coreAPI функциями и toolchain’а для сборки.

К сожалению, в KolibriOS нативного компилятора C/C++ еще не существует, текущий toolchain предполагает сборку приложений в ОС Windows или Linux.

Данная статья является инструкцией по настройке newlib для ОС Windows.

Привет, GT!

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

Проблема
В один «прекрасный» момент я обнаружил, что VPN отвалился и больше не поднимается. Не буду описывать долгое исследование проблемы — скажу сразу итог: помогло изменение номера порта. Помогло ненадолго: через пару-тройку дней туннель оборвался снова и снова был восстановлен сменой порта.

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

3.0 Однофайловый коммит

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

3.1 Начальное состояние

Состояние системы, когда соединение с БД только что было поднято, поверхностно изображено на рисунке справа. Справа показана информация, которая хранится на энерго-независимом носителе. Каждый прямоугольник — это сектор. Синий цвет говорит о том, что этот сектор содержит оригинальные данные. Посередине изображён дисковый кеш операционной системы. В самом начале нашего примера кеш холодный, это изображено белым цветом. На левой части рисунка — содержимое оперативной памяти процесса, который использует SQLite. Соединение с БД только что было открыто, и никакой информации прочитано не было.

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



Лекция была прочитана Борисом hr0nix Янгелем на факультете компьютерных наук, открытом в Высшей школе экономики при поддержке Яндекса. Сам Борис окончил ВМиК МГУ и Школу анализа данных Яндекса. Работал в Microsoft Research Cambridge в группе Кристофера Бишопа над фреймворком Infer.NET. Сейчас Борис — ведущий разработчик поиска Яндекса.

Под катом — расшифровка рассказа.

Вступление

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

Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.

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

«Обычное» программирование

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

Немного воды

Уже более полутора лет назад прошла новость о том, что «DARPA намерено совершить революцию в машинном обучении». Конечно, DARPA всего лишь выделила деньги на исследовательскую программу, связанную с вероятностным программированием. Само же вероятностное программирование существует и развивается без DARPA достаточно давно, причем исследования ведутся, как в ведущих университетах, таких как MIT, так и в крупных корпорациях, таких как Microsoft. И вовсе не зря DARPA, Microsoft, MIT и т.д. обращают пристальное внимание на эту область, ведь она по-настоящему перспективна для машинного обучения, а, может, и для искусственного интеллекта в целом. Говорят, что вероятностное программирование для машинного обучения будет играть ту же роль, что и высокоуровневые языки для обычного программирования. Мы бы привели другую параллель – с ролью Пролога, которую он сыграл для старого доброго ИИ. Вот только в Рунете по данной теме до сих пор можно найти лишь единичные ссылки, и то в основном содержащие лишь описания общих принципов. Возможно, это связано с тем, что потенциал вероятностного программирования еще только начал раскрываться и оно не стало основным трендом. Однако на что же способны или будут способны вероятностные языки?

Технология Secure Boot нацелена на предотвращение исполнения недоверенного кода при загрузке операционной системы, то есть защиту от буткитов и атак типа Evil Maid. Устройства с Secure Boot содержат в энергонезависимой памяти базу данных открытых ключей, которыми проверяются подписи загружаемых UEFI-приложений вроде загрузчиков ОС и драйверов. Приложения, подписанные доверенным ключом и с правильной контрольной суммой, допускаются к загрузке, остальные блокируются.

Более подробно о Secure Boot можно узнать из цикла статей от CodeRush.

• О безопасности UEFI, часть пятая

  
  

• Укрощаем UEFI SecureBoot

  
  

Чтобы Secure Boot обеспечивал безопасность, подписываемые приложения должны соблюдать некоторый «кодекс чести»: не иметь в себе лазеек для неограниченного доступа к системе и параметрам Secure Boot, а также требовать того же от загружаемых ими приложений. Если подписанное приложение предоставляет возможность недобросовестного использования напрямую или путём загрузки других приложений, оно становится угрозой безопасности всех пользователей, доверяющих этому приложению. Такую угрозу представляют загрузчик shim, подписываемый Microsoft, и загружаемый им GRUB.

Чтобы от этого защититься, мы установим Ubuntu с шифрованием всего диска на базе LUKS и LVM, защитим initramfs от изменений, объединив его с ядром в одно UEFI-приложение, и подпишем его собственными ключами.