Здравствуй, Хабр. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
Сложность этого решения O(n²).
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.

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

Эта примечательная гипотеза связывает поведение функции L там, где в настоящее время неизвестно, определена ли она, и порядок группы Ш, про которую неизвестно, конечна ли она!
J.T.Tate, The arithmetic of elliptic curves, Inventiones mathematicae 23 (1974)

(Краткая справка насчёт актуальности цитаты 40-летней давности: после Уайлса и Ко таки стало известно, что функцию L можно определить на всей комплексной плоскости. Конечность группы Ш в общем случае остаётся неизвестной.)

Остаётся обсудить возможность ошибки. В качестве предосторожности против внутренних ошибок компьютера можно прогнать все вычисления дважды или делать проверки внутри программы. Более того, компьютеры — в отличие от людей — устроены так, что их ошибки обычно чересчур велики, чтобы их не заметить. Мы уверены, что в наших результатах нет подобных ошибок. С другой стороны, при кодировании замысловатой схемы вычислений в компьютерную программу неизбежны программистские ошибки. Большинство из них обнаруживаются ещё до основных запусков, из-за того, что программа виснет или выдаёт нелепые результаты. Но программа, которую считается работающей, всё ещё может содержать логические ошибки, проявляющиеся при редких стечениях обстоятельств: и действительно, большинство компьютеров подвержено аномалиям, из-за которых те иногда ведут себя не так, как должны по спецификациям. В сущности, наша программа для этапа (ii) оказалась неточной и пропустила очень небольшое количество эквивалентностей, которые должна была найти.

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

B.J.Birch and H.P.F.Swinnerton-Dyer, Notes on elliptic curves. I, Journal für die reine und angewandte Mathematik 212 (1963)

Под катом не будет формулировки гипотезы; знающие выражения вроде «Euler product» и «holomorphic continuation» (и в смысле языка, и в смысле обозначаемых понятий) могут прочитать пятистраничный pdf с сайта института Клэя. Под катом — некоторая попытка пояснить, на каком направлении развития математической мысли вообще находится гипотеза Бёрча — Свиннертон-Дайера. А также — как можно досчитать до больших чисел вроде тех, что показаны на КДПВ, менее чем за секунду.

На протяжении довольно долгого времени я и мои коллеги, участники Русскоязычной поддержки Wolfram Mathematica, занимались разработкой и коллекционированием полностью бесплатных и качественных ресурсов на русском языке, которые позволили бы любому желающему научиться программировать на языке Wolfram Language (Mathematica) самостоятельно.

Думаю, что пришла пора рассказать об этом на Хабрахабре, создав статью о разрабатываемой коллекции ресурсов, которая будет постоянно расширяться и пополняться, и будет служить, по сути, русскоязычным аналогом страницы "Where can I find examples of good Mathematica programming practice?" на сайте Mathematica at StackExchange.com.

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

Соответственно, недосып – вторая большая проблема для современного человека (и при этом, что характерно, она обычно таки не решает первую). Ложиться спать вовремя зачастую тупо не хочется: есть такое нехорошее ощущение, что тогда в жизни останутся только сон и работа.

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

Что это?

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

RSA является широкоизвестным алгоритмом шифрования с открытым ключом. На его основе, кроме асимметричного шифрования, можно также реализовать электронную подпись (ЭЦП). Эти возможности привлекательны для встраиваемых систем, микроконтроллеров. Сам метод шифрования с виду чрезвычайно прост:

C = (Me) mod n

(1)

где C,M,e,n — целые числа, M — открытый текст, числа e и n представляют собой открытый ключ, C — шифротекст. mod — остаток от деления.

Расширование выглядит столь же просто:

M = (Cd) mod n

(2)

где C,M,n играют ту же роль, что и при шифровании, d — закрытый ключ.

При этом n=p*q, где p и q — простые числа (секретные), e обычно равно 65537, d вычисляется на основе e, p и q. Криптостойкость основана на том, что для достаточно больших p и q задача разложения n на множители или обращения формулы шифрования без знания p и q не решается за приемлемое время.

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

Как заработать миллион за день, стать искусным оратором за неделю, похудеть на 100 кг за 2 дня, стать успешным в тысяча ста начинаниях и прочая мишура регулярно засоряет наше информационное пространство. А порой так хочется взять в руки книгу, которая не просто съест кусок вашего свободного времени повествуя о неприменимых в отечественных реалиях вещах, но и подкинет хотя бы несколько полезных советов, способных оказать позитивное влияние на развитие вашей личности и вашего проекта.

Если вы хотите найти и/или поделиться хорошими книгами, добро пожаловать под кат.

Привет, Хабр!

Мы (@ali_aliev и avenat) с удовольствием представляем вашему вниманию перевод интерактивного учебника «Problem Solving with Algorithms and Data Structures» от Брэда Миллера (Brad Miller) и Дэвида Ранума (David Ranum) из Luther College, что в Айове, США.

О чём?

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

Авторы рассказывают о таких структурах данных, как стеки, очереди (в том числе с приоритетом), деки, хэш-таблицы, списки, деревья и графы. Последним двум вообще посвящены весьма не маленькие главы. Изложение не просто описательное: для каждой структуры предлагается вариант (а иногда и не один) её реализации на Python. Упор, естественно, делается на объектно-ориентированное программирование: создаётся класс, к нему пишутся методы, некоторые из которых авторы оставляют читателям для самостоятельной доработки. Затем идут примеры использования рассмотренной структуры и описание алгоритмов с её участием.

Одна из глав учебника посвящена рекурсии, в том числе её графическому представлению (фракталы). Разбирается несколько известных рекурсивных задач, а в конце наглядно демонстрируется, что эта методика, несмотря на её элегантность, отнюдь не «серебряная пуля».

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

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

Персептрон

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

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



«Вот те раз!» — подумал я. Ни в одном реестре запрещенных сайтов данный ресурс не присутствовал и, с чего билайн его заблокировал — непонятно. Естественно после таких вот «заявочек» в голову полезли страшные мысли: «а что если завтра любимого „кина“ не будет!». Данные мысли тут же подвигли меня начать искать способы борьбы с данной ситуацией, и написать, для тех кому будет интересно, маленький обзор нескольких решений по обходу блокировки сайтов. (под катом скрины)

Итак, как и обещал в первой части, продолжаем упрощать бытовую жизнь хабражителя. Сегодня 8 марта (кстати, девушки, поздравляю!) и части мужчин хочется порадовать своих женщин и освободить их от «рабского труда» на кухне, а другой части – приготовить для себя не традиционные пельмени\вареники\сосиски, а что-то посущественней.
Вот несколько проверенных рецептов, которые пригодятся и первым, и вторым.

Осторожно, много картинок. Голодным не входить!

Перевод статьи Скотта Янга "What are the Intellectual Ideas Everybody Should Know?"

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

Рассмотрим уравнение Френеля в физике. Приложив некоторые усилия, можно построить аналогию между этим уравнением и какой-либо другой областью знаний. Но вряд ли можно сказать, что понимание уравнения приводит к бурным озарениям в области истории или искусства.

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

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

С этой позиции я ставлю следующий вопрос: какие интеллектуальные идеи, могущие быть широко применимы в познании мира, усвоены вами?

Есть один курс, который я бы добавил в программу обучения по всякой инженерной специальности, и он не о компиляторах или сложности алгоритмов. Это “Введение в реальность индустрии”, ибо об этом не говорят и это приводит к никому не нужным обломам. Эта статья претендует стать README.txt для молодого инженера в деле построения карьеры. Ее цель — сделать вас счастливее, заполнив пробелы в образовании относительно того, как работает реальный мир. Я не призываю следовать написанному как подробному руководству, но я надеюсь, что эта информация окажется для вас более ценной, чем то ничто, что вам рассказали об этом в университете.

Рады сообщить, что в издательстве «Питер» вышли вторые тиражи книг: «Битва при черной дыре. Мое сражение со Стивеном Хокингом за мир, безопасный для квантовой механики» — Сасскинд Л. и «Теория струн и скрытые измерения Вселенной» — Шинтан Яу.

Доброго времени суток, уважаемые хабрачитатели!

Скорее всего, многие из вас слышали про олимпиады по спортивному программированию. В последние годы появилось очень много соревнований по этому виду программирования. Это и Google Code Jam, и Topcoder Open, и Russian Code Cup. Сегодня мне посчастливилось лично пообщаться с Романом Удовиченко (в рамках AYcamp, по специальной программе «Саурон»), одним из тех, кто добился в них серьезных успехов. Он живет в городе Минске, в прошлом году окончил Белорусский Государственный Университет, работает в компании Яндекс. Он рассказал, как готовился к олимпиадам и чем они помогли ему в жизни.

Всех заинтересованных прошу под кат.

Привет!

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

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

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

Введение

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

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

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

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

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

Источник: Nature

Некоторое время назад на Хабре была опубликована заметка о возможностях 3D SEM-микроскопии применительно к исследованию структуры человеческого мозга в рамках европейского мегапроекта «The Human Brain Project». Под катом мы постарались максимально подробно – а это значит будет много текста – ответить на заданные вопросы, но начнём по традиции с некоторого введения.
Attention! Впереди очень много текста