Категорически приглашаем всех желающих на онлайн-курс «Введение в теоретическую информатику» Александра Ханьевича Шеня, подготовленный совместно с Computer Science центром и платформой Stepic. Курс начнётся 24 февраля.



Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).

В общем, у Александра Ханьевича огромный опыт чтения лекций как школьникам, так и студентам и аспирантам. Рассказывает он очень увлекательно и понятно. В онлайн-курсе он даст обзор различных направлений Theoretical Computer Science: криптография, инварианты циклов, вычислимость, переборные задачи, игры, коды, интерактивные доказательства и многое другое (всего в курсе восемнадцать глав!). В курсе будет много задач — как простых (закрепляющих изученный материал), так и более сложных, над которыми придётся поломать голову и тем, кто уже был знаком с теорией.

Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104

Недавно viktorpanasiuk опубликовал задачу о конфетах, которая «зацепила» многих (в частности, koldyr опубликовал на Хабре свое аналитическое решение), в том числе и меня. Задача практическая, от инженера-кондитера, формулировалась так: «Найти максимально допустимое отклонение массы конфеты при ее производстве, чтобы нетто коробки, состоящей из n=12 штук их, не выходило за пределы M=310±7 грамм в 90% случаев. Закон распределения считать нормальным».

Автор решил задачу, исходя из предположения о нормальном распределении конфет по массе, и нашел среднюю массу конфеты (очевидно, равную µ=M/n=25.83 г) и стандартное отклонение σ=1.23 г. Использование метода Монте-Карло, т.е. генерация N*n случайных чисел с гауссовым распределением конфет со средним µ и стандартным отклонением σ, подтверждает правильность решения. Распределение масс коробок является гауссовым, и его параметры близки к найденным аналитически (расчеты в Mathcad Express в форматах MCDX и XPS прилагаются). На левом графике показана гистограмма плотности распределения (по массе) конфет, а на правом — соответственно, распределения коробок.



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

Поводом к переводу статьи стало то, что я искал книгу автора «The Outer Limits of Reason». Спиратить книгу я так и не смог, зато наткнулся на статью, которая в довольно сжатом виде показывает взгляд автора на проблему.

Вступление

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

После написания статьи про анализ малвари с avito, несколько моих twitter-читателей откликнулись и прислали SMS, которые получили после публикации объявлений на avito.

Сначала я хотел честно и подробно написать о методах снижения размерности данных — PCA, ICA, NMF, вывалить кучу формул и сказать, какую же важную роль играет SVD во всем этом зоопарке. Потом понял, что получится текст, похожий на вырезки из опусов от Mathgen, поэтому количество формул свел к минимуму, но самое любимое — код и картинки — оставил в полном объеме.

Примечание переводчика: при переводе старался максимально пользоваться терминологией, которую предлагает сам Google в русскоязычной версии документации по Android, таким образом «service» стал «службой», «content provider» стал «поставщиком контента», и так далее. А вот «activity» стать «операцией» так и не смог — не пересилил я себя. Извините.

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

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

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

Идея написать популярно про большие числа пришла во время чтения недавней статьи, речь в которой шла о числах-гигантах, имеющих хоть какой-то физический смысл. И заканчивается она упоминанием числа Грэма. Того числа, которое будет точкой отсчета сегодняшней статьи. Чтобы представить себе масштабы бедствия я настоятельно рекомендую предварительно прочитать вот эту статью, в которое объясняется о числе Грэма на пальцах^_TM — там автор очень красочно и последовательно рассказывает о границах восприятия, в которые мы себя зажимаем, когда говорим о больших числах.

Специалисты израильской security-компании Perception Point сообщили об обнаружении опасной 0day уязвимости в ядре Linux с идентификатором CVE-2016-0728. Уязвимость относится к типу Local Privilege Escalation (LPE) и охватывает все версии и модификации Linux, в которых используется ядро версии 3.8 и выше. Как не трудно догадаться, с ее помощью атакующие могут поднять свои привилегии в системе до максимального уровня root. Эксплойт может быть использован в системе уже после того как атакующие получили к ней удаленный доступ и запустили его на исполнение. Он также может использоваться вредоносными программами для получения в системе максимальных привилегий.



На ядре Linux основана и одна из самых востребованных на сегодняшний день мобильных ОС — Android. Таким образом, те версии Android, которые используют ядро Linux указанных версий также подвержены данной уязвимости. Это относится к версиям Android KitKat (4.4-4.4.4) и выше.

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

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

Наличие большого числа библиотек, реализующих Фурье преобразований (во всевозможных вариантах быстрых версий), делает реализацию алгоритмов не очень сложной задачей для программирования.
Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools

Здравствуйте, уважаемые хабровчане! Мы решили возобновить публикации еще до окончания больших праздников, но в сегодняшней статье все-таки раскрыта тема справедливой раздачи подарков. Сама же статья, как понятно из названия, посвящена сравнительному анализу параллелизма и конкурентности.

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

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

Прошло несколько месяцев после анонса соревнования между профессиональным снайпером, вооруженным обычной винтовкой, и новичком, с небольшим опытом подготовки, вооруженным «умной» Linux-винтовкой. Результаты соревнования появились на официальном сайте производителя винтовки TrackingPoint.

Это шестая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли
5. Произведения и копроизведения

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

Рассмотрим подробнее место произведения и копроизведения типов в программировании.

Произведение типов

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

Строго говоря, произведение типов не коммутативно: нельзя подставить пару типа (Int, Bool) вместо (Bool, Int), хотя они и содержат одни и те же данные. Однако произведение коммутативно с точностью до изоморфизма, задаваемого функцией swap, которая обратна самой себе:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

Можно рассматривать такие пары как различные форматы хранения одной и той же информации, как big endian и little endian.

Эти два графа являются изоморфными

Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.

Представляю на ваш суд ещё один перевод коанов о Мастере Фу на русский язык. В данный сборник вошли все коаны, на данный момент опубликованные на сайте Эрика Реймонда. Надо сказать, что сам Эрик личность весьма неординарная, но упоминания в данной статье стоящая. Помимо холиваров в списках рассылки всевозможных проектов за его авторством также несколько серьёзных трудов о Unix — в том числе и о сообществе, без которого экосистема современных открытых проектов не была бы возможной (полный список книг). Идея перевести коаны в очередной раз пришла мне в голову во время чтения одного из таких трудов, а именно «The Art of Unix Programming», поскольку многое из скрытого смысла коанов становится ясно только после прочтения очередной главы оттуда.

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

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



В качестве таковых рассмотрим следующие:

• Реализуем пакет доступа к API ВКонтакте.
  Код будет работать как в «native» приложениях, так и в приложениях JavaScript через GHCJS, компилятор Haskell в JavaScript
  
• Напишем одностраничное браузерное приложение, используя наше API
  

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

Схема отработки аварии первого уровня в «Мультикарте»

Есть такой миф, что у нас отказоустойчивых инфраструктур у крупных компаний не было примерно до 2007 года. Мол, именно тогда начали появляться документы DRP (аварийного восстановления), выделяться отделы риск-менеджмента и так далее.

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

А теперь поехали развеивать другие мифы про DRP и непрерывности. Ну и заодно расскажу про наш последний проект — аварийные планы «Мультикарты», то есть той системы, через которую идут все ваши оплаты картами в России.

Ну и, конечно, истории былинных провалов.

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

Примерами могут служить последняя цифра номера кредитной карты, девятая цифра VIN автомобилей, продаваемых в в США, или последняя цифра ISBN.

Алгоритм контрольной цифры ван Дамма — относительно новый и потому малоизвестный. Он опубликован 2004 году.

Алгоритм обнаруживает все ошибки в одной цифре и все одиночные перестановки соседних цифр. Он заметно проще, чем сравнимый по возможностям алгоритм Верхуффа, и не требует использования специальных символов (таких как X в 10-значном ISBN).