К моему удивлению, предыдущую статью приняли достаточно тепло. Сегодня продолжим рассмотрение этого вопроса.

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

Часть 2

Под метдом Монте-Карло понимается численный метод решения
математических задач при помощи моделирования случайных величин. Представление об истории метода и простейшие примеры его применения можно найти в Википедии.

В самом методе нет ничего сложного. Именно эта простота объясняет популярность данного метода.

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

Однако одну и ту же задачу можно решать различными вариантами метода Монте-Карло, которым отвечают различные значения . Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее значение .

Стандарт 802.11ac принят в 2014 году, а устройства с его поддержкой, как водится, появились раньше. Как многие знают, в нем значительно увеличена скорость передачи данных (теоретически, до 6.7 Гбит/с!). Достигается это благодаря увеличенной ширине каналов (до 160 МГц), количеству потоков (до 8) и новой улучшенной модуляции (256-QAM). Конечно, не все новшества стандарта стали доступны сразу. Реализация на точках доступа и клиентских станциях происходит поэтапно. Первая волна (wave 1) устройств поддерживает каналы 80 МГц, модуляцию 256-QAM и два-три пространственных потока. Корпоративные точки доступа второй волны (wave 2), появившиеся в 2015 году, поддерживают ширину канала до 80 МГц и до четырех пространственных потоков, что дает скорость 1.7 Гбит/с. Также, для второй волны устройств добавлена поддержка многопользовательского пространственного мультиплексирования MultiUser-MIMO (MU-MIMO). Эта технология позволяет передать несколько потоков информации нескольким пользователям одновременно (ага, точка доступа превращается в некий беспроводной коммутатор). Сейчас практически любое новое устройство с беспроводной Wi-Fi сетью поддерживает как минимум первую волну стандарта.

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

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

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

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

Наш первый пост в этом году мы решили посвятить очень базовой теме, лекция на которую была прочитана в Малом ШАДе. Занимаются в нём старшеклассники, которым интересны технологии, отсюда специфичность изложения — лекция будет особенно интересна тем, кто только начинает программировать и задумывается о том, в каком направлении развиваться. Для них же у Яндекса есть курс «Введение в программирование (С++)», который можно пройти на платформе Stepic.org.

Лектор Михаил Густокашин — куратор академических программ Яндекса, директор центра студенческих олимпиад факультета компьютерных наук ВШЭ. Михаил подготовил десятки победителей и призёров Всероссийских олимпиад по программированию.



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

Как всегда, под катом — подробная расшифровка лекции, чтобы вы могли сориентироваться в ее содержании.

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

Перевод поста Devendra Kapadia "New in the Wolfram Language: Symbolic PDEs".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации.

---

Уравнения в частных производных (УрЧП) играют очень важную роль в математике и ее приложениях. Их можно использовать для моделирования реальных явлений, таких как колебания натянутой струны, распространения потока тепла в стержне, в финансовых областях. Цель этой статьи — приоткрыть завесу в мир УрЧП (тем кто еще с ним не знаком) и ознакомить читателя с тем, как можно эффективно решать УрЧП в Wolfram Language, используя новый функционал для решения краевых задач в DSolve, а так же новую функцию DEigensystem, которая появилась в версии 10.3.

История УрЧП восходит к работам известных математиков восемнадцатого века — Эйлера, Даламбера, Лапласа, однако развитие этой области в последние три столетия так и не остановилось. И потому в статье я приведу как классические, так и современные примеры УрЧП, что позволит рассмотреть эту область знаний под разными углами.

Давайте начнем с рассмотрения колебаний натянутой струны с длиной π, закрепленной на обоих концах. Колебания струны можно смоделировать с помощью одномерного волнового уравнения, приведённого ниже. Здесь u(x,t) — вертикальное смещение точки струны с координатой х в момент времени t:

Рыцарь в образовании и компьютерных науках, мужик, в честь которого назвали логику, первый, кто признался в своей ошибке на миллиард долларов, разработчик qsort, празднует сегодня, 11 января, свое 82-летие. (Наверняка вместе с Кнутом.)

Утро 26 ноября началось для меня с интересной новости — ребята из Perfect Privacy опубликовали информацию об уязвимости Port Fail, которая позволяет раскрывать IP-адрес клиентов VPN-сервисов с функцией проброса портов. Я немного понегодовал из-за того, что ее назвали уязвимостью, т.к. это никакая не уязвимость, а особенность маршрутизации: трафик до IP-адреса VPN-сервера всегда идет напрямую, в обход VPN. Вполне очевидная вещь, подумал я, о которой должен знать любой сетевой администратор. Заметка вменяемая и технически грамотная, придраться можно только к слову vulnerability (уязвимость). Но потом за дело взялись СМИ, и пошло-поехало…



Критическая уязвимость во всех протоколах VPN на всех операционных системах. У-у-у, как страшно!

В новости, опубликованной на Geektimes, изначально имевшей желтый заголовок, было сказано о награде в $5000 за найденную «уязвимость» от Private Internet Access — одного из крупнейших VPN-сервисов. «$5000 за типичную, совершенно очевидную любому сетевику вещь?» — подумал я — «Невероятно!», и высказал свое негодование по этому поводу в комментариях, попутно расписав еще одну, не менее очевидную, особенность маршрутизации, с которой сталкивался любой настраивавший работу двух и более интернет-провайдеров на одном компьютере: ответ на входящий запрос не обязательно уйдет через этого же провайдера и с этим же IP, чего запросившая сторона совсем не ожидает. Если мы представим, что вместо второго провайдера у нас VPN-соединение, то отправив запрос на IP-адрес нашего провайдера, при определенных условиях может получиться так, что ответ на наш запрос мы получим с IP VPN-сервера.

Хочу поподробнее рассказать об интересном проекте компании Edison. Перед разработчиками поставили задачу написать софт для микротомографа, они с этим отлично справились, а потом запихивали в этот томограф семечки, болты, конденсаторы и моль. А серьезным дядям этот томограф нужен, чтобы проверять алмазы и не покупать дырявые.

А еще сегодня 16 декабря, день рождения Иоганна Радона, австрийского математика, ректора Венского университета, который в 1917 году ввел интегральное преобразование функции многих переменных, родственное преобразованию Фурье, используемое сегодня во всех томографах.

Иоганн Радон был профессором 6 университетов (а в одном из них даже без кафедры), был президентом Австрийского математического общества. В Австрии в честь него назвали «Институт вычислительной и прикладной математики» и медаль.

О том, как проходила разработка софта для томографа и какие задачи решались в процессе — под катом.

Прим. переводчика: Это перевод статьи Питера Брайта (Peter Bright) «How security flaws work: The buffer overflow» о том, как работает переполнение буфера и как развивались уязвимости и методы защиты.

Беря своё начало с Червя Морриса (Morris Worm) 1988 года, эта проблема поразила всех, и Linux, и Windows.



Переполнение буфера (buffer overflow) давно известно в области компьютерной безопасности. Даже первый само-распространяющийся Интернет-червь — Червь Морриса 1988 года — использовал переполнение буфера в Unix-демоне finger для распространения между машинами. Двадцать семь лет спустя, переполнение буфера остаётся источником проблем. Разработчики Windows изменили свой подход к безопасности после двух основанных на переполнении буфера эксплойтов в начале двухтысячных. А обнаруженное в мае сего года переполнение буфера в Linux драйвере (потенциально) подставляет под удар миллионы домашних и SMB маршрутизаторов.

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

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

Когда мы общаемся с нашими заказчиками, то, будучи специалистами в этой области, активно используем соответствующую терминологию, в частности слово «распознавание». При этом слушающая аудитория, воспитанная на Cuneiform и FineReader, часто вкладывает в этот термин именно задачу сопоставления вырезанного участка изображения некоторому числу (коду символа), которая в наши дни решается нейросетевым подходом и является далеко не первым этапом в задаче распознавания информации. В начале необходимо локализовать карточку на изображении, найти информационные поля, выполнить сегментацию на символы. Каждая перечисленная подзадача с формальной точки зрения является самостоятельной задачей распознавания. И если для обучения нейронных сетей существуют зарекомендовавшие себя подходы и инструменты, то в задачах ориентации и сегментации каждый раз требуется индивидуальный подход. Если вам интересно узнать про подходы, которые мы использовали при решении задачи распознавания банковской карточки, тогда добро пожаловать под кат!

Введение

Допустим у нас есть некоторое множество, которое состоит из N элементов. Будем считать, что элементы пронумерованы от нуля до N-1. Набор k-элементных подмножеств данного множества (сочетаний) можно представить либо в виде массива индексов длины k. Либо в виде последовательности из N бит, в которой установлено ровно k из них. У Дональда Кнута в его TAoCP приводится алгоритм генерации сочетаний в лексикографическом порядке, когда сочетания заданы в виде массива индексов. Мы попробуем перенести этот алгоритм на случай битовых масок.

Всем привет!

Спешим поделиться видеозаписями выступлений с очередной встречи минского Python-сообщества.

Под катом вы найдете доклады:

• Deliberate Practice: Coding Dojo, Code Kata and Coderetreat / Сергей Сергиенко
• Быстрая разработка десктоп-приложений с Penta.by / Андрей Пучко
• WRK: Modern HTTP benchmarking tool / Алексей Романов

Приятного просмотра!

Часть 1

Давай сразу код!

import numpy as np
X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
alpha,hidden_dim = (0.5,4)
synapse_0 = 2*np.random.random((3,hidden_dim)) - 1
synapse_1 = 2*np.random.random((hidden_dim,1)) - 1
for j in xrange(60000):
    layer_1 = 1/(1+np.exp(-(np.dot(X,synapse_0))))
    layer_2 = 1/(1+np.exp(-(np.dot(layer_1,synapse_1))))
    layer_2_delta = (layer_2 - y)*(layer_2*(1-layer_2))
    layer_1_delta = layer_2_delta.dot(synapse_1.T) * (layer_1 * (1-layer_1))
    synapse_1 -= (alpha * layer_1.T.dot(layer_2_delta))
    synapse_0 -= (alpha * X.T.dot(layer_1_delta))

Часть 1: Оптимизация

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

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

О чём статья

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

Дайте код!

X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
syn0 = 2*np.random.random((3,4)) - 1
syn1 = 2*np.random.random((4,1)) - 1
for j in xrange(60000):
    l1 = 1/(1+np.exp(-(np.dot(X,syn0))))
    l2 = 1/(1+np.exp(-(np.dot(l1,syn1))))
    l2_delta = (y - l2)*(l2*(1-l2))
    l1_delta = l2_delta.dot(syn1.T) * (l1 * (1-l1))
    syn1 += l1.T.dot(l2_delta)
    syn0 += X.T.dot(l1_delta)

Слишком сжато? Давайте разобьём его на более простые части.

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

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

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

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

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

Всем привет!

Давно хотел начать цикл статей, посвященных цифровой обработке сигналов на ПЛИС, но по разным причинам так и не мог к этому приступить. К счастью, в распоряжении появилось немного свободного времени, поэтому периодически я буду публиковать материалы, в которых отражены различные аспекты, связанные с ЦОС на ПЛИС.


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