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

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



Читает курс Андрей Райгородский. Доктор физико-математических наук. Профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М. В. Ломоносова. Заведующий кафедрой Дискретной математики ФИВТ МФТИ. Профессор и научный руководитель бакалавриата кафедры «Анализ данных» факультета инноваций и высоких технологий МФТИ. Руководитель отдела теоретических и прикладных исследований компании «Яндекс». (Ещё больше можно узнать в статье о нём на Википедии).

Вероятно, большей части хабрасообщества в 1964 году даже в проекте не было. Однако, в то время жил и работал великий (не побоюсь этого слова) писатель-фантаст, мыслитель, ученый, популяризатор науки и просто человек Айзек Азимов. В 1964 году, находясь под впечатлением от Всемирной выставки, проходившей в Нью-Йорке, он решил представить, как будет выглядеть мир через полвека. В этом, 2014 году, как раз исполняется 50 лет этому предсказанию, поэтому предлагаю вспомнить те предсказания Азимова, что сбылись.

От переводчика: Джон Скит написал несколько статей о строках, и данная статья является первой, которую я решил перевести. Дальше планирую перевести статью о конкатенации строк, а потом — о Юникоде в .NET.

Тип System.String (в C# имеющий алиас string) является одним из наиболее часто используемых и важных типов в .NET, и вместе с тем одним из самых недопонимаемых. Эта статья описывает основы данного типа и развенчивает сложившиеся вокруг него мифы и непонимания.

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

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


Печенье, испечённое по рецепту Ватсона

На пятничном семинаре учебного проекта лаборатории МФТИ-Интел один из студентов задал мне примерно такой вопрос: а почему 64-битный вариант архитектуры процессоров Intel называется x64, а 32-битный — x86? Я начал объяснять, что не всё так просто. Захотелось нарисовать более полную картину. Ведь на самом деле это не x64, и даже не x86.

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

Некоторое время назад уже был опубликован аналогичный пост, с тех пор количество дополнений для Visual Studio 2010,2012 и 2013 перешагнуло планку в 4к, появилось немало новых дополнений. Ниже перечислено 20 наиболее популярных или интересных расширений для Visual Studio 2012 и 2013 в дополнение к предыдущему посту.

В далеком (а может и не очень далеком) 1975 году Альфред Ахо и Маргарет Корасик опубликовали статью, в которой был подробно описан алгоритм эффективного поиска всех вхождений всех строк-образцов в заданную строку. В дальнейшем этот алгоритм и получил название «алгоритм Ахо-Корасик». Неудивительно, что через некоторое время появились технические и «художественные» переводы данной статьи на русский язык. Порой мне даже встречались вольные изложения сути алгоритма в том виде, в котором его понимает автор. Причем последний, судя по тексту, узнал об алгоритме далеко не из первоисточника. Я не знаю существовал ли перевод, который послужил первоисточником проблемы, но мне всё больше и больше попадаются статьи с описанием алгоритма Ахо-Корасик, в котором допущена одна и та же кардинальная ошибка. Последней каплей была статья пользователя rmq на хабре, которую данная ошибка не миновала. Собственно об этой ошибке мне и хотелось бы рассказать общественности в своей статье.
Замечание: статья пользователя rmq, как выяснилось позже, не содержит этой ошибки. Как она решена там расскажу ниже. А ему огромное спасибо, если бы не его топик я бы не написал свой и не получил бы инвайт!
Перед началом, еще пара слов о целевой аудитории: Скорее всего, тем, кто давно знаком с алгоритмом Ахо-Корасик, моя статья будет не интересна, так как о его особенностях они давно уже знают. По крайней мере, все мои знакомые программисты не один раз применявшие данный алгоритм знают о существовании его неверных интерпретаций не понаслышке. А вот новичкам и тем, кому не довелось часто применять его на практике, эта статья может оказаться довольно полезной.
Итак, начнем.

Второго октября в Монреале прошло очередное мероприятие Google Tech Talks.

Более 150 человек пришло с единственной целью — послушать доклад Алекса Ионеску, который известен российской аудитории, в первую очередь, как соавтор книг серии Windows Internals.

Доклад Алекса назывался "The Crazy Open Source Attempt To Rewrite Windows From Scratch" и целиком посвящен операционной системе ReactOS. Выступление насыщено интересными подробностями и содержит в себе практически исчерпывающий отчет об истории создания и современном состоянии проекта ReactOS.


Рекомендуется сразу переключить плеер в разрешение 480р и развернуть на полный экран.
Скачать в максимальном качестве с английскими субтитрами (335 МБ).
magnet:?xt=urn:btih:D74DDE9C8CAD16AB1782DB7B071D8A977A74E0E5

Эта заметка написана по мотивам одного любопытного поста, краткий коммент её же автора к которому сподвиг меня разобраться в происходящем поподробнее. Предлагается сравнить две вариации алгоритма сортировки пузырьком. Первая из них – обычный пузырёк, с небольшой оптимизацией — внутренний цикл можно закончить немного раньше, зная, что оставшаяся часть массива уже отсортирована:
for (i=0; i<N; i++)
  for (j=0; j<N - (i+1); j++)
    if (a[j] > a[j+1])
      swap(a[j], a[j+1]);

Во втором варианте внутренний цикл проходит по другой части массива, однако алгоритмически этот вариант эквивалентен первому (подробности ниже):
for (i=0; i<N-1; i++)
    for (j=i; j>=0; j--)
        if (a[j] > a[j+1])
            swap(a[j], a[j+1]);

Запускаем (код), например, для N=100 000 на массиве int'ов, и получаем около 30 секунд в первом случае, и меньше 10 секунд — во втором, то есть отличие в 3 раза! Откуда же тогда берётся такая разница?

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

Итак, поговорим о:

• InternalsVisibleToAttribute
• TypeForwardedToAttribute
• CallerMemberNameAttribute
• MethodImplAttribute

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

Мы рады сообщить, что тестировать производительность сайтов стало проще, благодаря новым инструментам F12, предназначенным для поиска и исправления связанных с ней проблем. В этом кейсе мы использовали сканер Modern.ie и профилировщик UI из нового набора F12 в IE11. Мы показали эти инструменты разработчикам из команды swish.com, чтобы узнать, как популярный сайт может их использовать для оптимизации работы типичных сценариев его использования. Результат – загрузка сайта стала на 2 секунды быстрее: рост производительности на 40% благодаря нескольким простым изменениям в коде.



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

Каждый программист когда-то давно, в начале своего Пути писал что-то типа вот этого:

double div( double a, double b )
{
	return a / b;
}

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

Я давеча написал комментарий о том, что компании Майкрософт давно пора перестать издеваться над веб-разработчиками и перейти на движок Gecko. Многие, видимо, посчитали это неуместной шуткой; тем не менее, это таки вовсе не шутка, а констатация факта. Те, кто с этим не согласен, видимо не пытались ещё разрабатывать под этот замечательный браузер.

Давайте я расскажу вам, какой это замечательный процесс.

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

На КДПВ стоп-кадр фильма «Железный Человек-2». Как нетрудно догадаться, рисующие этот интерфейс управления боевого костюма дизайнеры зашли в первый попавшийся русскоязычный онлайн-магазин, торгующий кондиционерами (умиляет даже сохранившееся название переменной «kolichectvo») и вырезали часть html-кода…

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

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

Сейчас проходит голосование за лучшие игры 2013.
По этому поводу GMG и 2K Games Объявляет акцию: после голосования вы можете получить на выбор игры.

Итак, что нужно:
1. Регистрация на сайте www.computerandvideogames.com
2. Проголосовать www.computerandvideogames.com/joystick/homepage.php
3. Зайти на страницу goldenjoysticks.greenmangaming.com и ввести email на котором голосовали, потом данные аккаунта GMG.

Ключ вы получите перейдя по ссылке в письме, которая подтверждает что ваша заявка принята.
~24 часа уходит, на перерасчёт голосов!

upd. Все ключи раздали!

upd2. КЛЮЧИ СНОВА В НАЛИЧИИ. Кто не успел вперед!!!
голосование закончено…

Немного предыстории

На рынке игровой индустрии в области ММОРПГ (массовых онлайн игр с элементами ролевого геймплея) в последние годы обозначился очевидный кризис жанра. Большинство ММОРПГ, вышедшие на рынок в последние два года потерпели (мягко говоря) неудачу и были востребованы незначительным числом пользователей. На этом безрадостном фоне для геймеров всего мира одиноко замерцал луч надежды — проект ArcheAge (АА), который взялась разрабатывать южнокорейская компания XLGames (XLG) под руководством Джейка Сонга — создателя легендарной для всех поколений геймеров всего мира ММОРПГ Lineage II.

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