Это заключительная часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма.
Соловьёв Евгений Евгеньевич @suenot
Пользователь
Lock-free структуры данных. Основы: Атомарность и атомарные примитивы
15 мин
Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.
Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует
А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый
Обзор алгоритмов кластеризации данных
10 мин
Приветствую!
В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
Задачи на собеседованиях в Яндексе
15 мин
Открытые вакансии на должность разработчика в Яндексе есть всегда. Компания развивается, и хороших программистов не хватает постоянно. И претендентов на эти должности тоже хоть отбавляй. Главная сложность – отобрать действительно подходящих кандидатов. И в этом плане Яндекс мало чем отличается от большинства крупных IT-компаний. Так что базовые принципы, описываемые в этой статье, могут быть применимы не только к Яндексу.
Однако стоит оговориться, что статья все же про подбор разработчиков. Т.е. собственно тех восьмидесяти процентов сотрудников, на которых держится массовая разработка. Часто мы нанимаем людей на специальные вакансии: например, разработчиков систем компьютерного зрения, лингвистов, экспертов по машинному обучению. В этом случае формат собеседования может заметно отличаться.
Однако стоит оговориться, что статья все же про подбор разработчиков. Т.е. собственно тех восьмидесяти процентов сотрудников, на которых держится массовая разработка. Часто мы нанимаем людей на специальные вакансии: например, разработчиков систем компьютерного зрения, лингвистов, экспертов по машинному обучению. В этом случае формат собеседования может заметно отличаться.
Фильтр Калмана
10 мин
Туториал
В интернете, в том числе и на хабре, можно найти много информации про фильтр Калмана. Но тяжело найти легкоперевариваемый вывод самих формул. Без вывода вся эта наука воспринимается как некое шаманство, формулы выглядят как безликий набор символов, а главное, многие простые утверждения, лежащие на поверхности теории, оказываются за пределами понимания. Целью этой статьи будет рассказать об этом фильтре на как можно более доступном языке.
Фильтр Калмана — это мощнейший инструмент фильтрации данных. Основной его принцип состоит в том, что при фильтрации используется информация о физике самого явления. Скажем, если вы фильтруете данные со спидометра машины, то инерционность машины дает вам право воспринимать слишком быстрые скачки скорости как ошибку измерения. Фильтр Калмана интересен тем, что в каком-то смысле, это самый лучший фильтр. Подробнее обсудим ниже, что конкретно означают слова «самый лучший». В конце статьи я покажу, что во многих случаях формулы можно до такой степени упростить, что от них почти ничего и не останется.
Machine Learning. Курс от Яндекса для тех, кто хочет провести новогодние каникулы с пользой
8 мин
Туториал
Новогодние каникулы – хорошее время не только для отдыха, но и для самообразования. Можно отвлечься от повседневных задач и посвятить несколько дней тому, чтобы научиться чему-нибудь новому, что будет помогать вам весь год (а может и не один). Поэтому мы решили в эти выходные опубликовать серию постов с лекциями курсов первого семестра Школы анализа данных.
Сегодня — о самом важном. Современный анализ данных без него представить невозможно. В рамках курса рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Читает курс лекций Константин Вячеславович Воронцов, старший научный сотрудник Вычислительного центра РАН. Заместитель директора по науке ЗАО «Форексис». Заместитель заведующего кафедрой «Интеллектуальные системы» ФУПМ МФТИ. Доцент кафедры «Математические методы прогнозирования» ВМиК МГУ. Эксперт компании «Яндекс». Доктор физико-математических наук.
Сегодня — о самом важном. Современный анализ данных без него представить невозможно. В рамках курса рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Читает курс лекций Константин Вячеславович Воронцов, старший научный сотрудник Вычислительного центра РАН. Заместитель директора по науке ЗАО «Форексис». Заместитель заведующего кафедрой «Интеллектуальные системы» ФУПМ МФТИ. Доцент кафедры «Математические методы прогнозирования» ВМиК МГУ. Эксперт компании «Яндекс». Доктор физико-математических наук.
Лекции от Яндекса для тех, кто хочет провести каникулы с пользой. Дискретный анализ и теория вероятностей
3 мин
Туториал
Для тех, кому одного курса на праздники мало и кто хочет больше, продолжаем нашу серию курсов от Школы анализа данных Яндекса. Сегодня подошла очередь курса «Дискретный анализ и теория вероятностей» – даже более фундаментального, чем предыдущий. Но без него нельзя представить ещё большую часть современной обработки данных.
В рамках курса рассматриваются основные понятия и методы комбинаторного, дискретного и асимптотического анализа, теории вероятностей, статистики и на примере решения классических задач демонстрируется их применение.
Читает курс Андрей Райгородский. Доктор физико-математических наук. Профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М. В. Ломоносова. Заведующий кафедрой Дискретной математики ФИВТ МФТИ. Профессор и научный руководитель бакалавриата кафедры «Анализ данных» факультета инноваций и высоких технологий МФТИ. Руководитель отдела теоретических и прикладных исследований компании «Яндекс». (Ещё больше можно узнать в статье о нём на Википедии).
В рамках курса рассматриваются основные понятия и методы комбинаторного, дискретного и асимптотического анализа, теории вероятностей, статистики и на примере решения классических задач демонстрируется их применение.
Читает курс Андрей Райгородский. Доктор физико-математических наук. Профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М. В. Ломоносова. Заведующий кафедрой Дискретной математики ФИВТ МФТИ. Профессор и научный руководитель бакалавриата кафедры «Анализ данных» факультета инноваций и высоких технологий МФТИ. Руководитель отдела теоретических и прикладных исследований компании «Яндекс». (Ещё больше можно узнать в статье о нём на Википедии).
Самый главный алгоритм
1 мин
От всей души рекомендую видео лекцию А. Степанова (человека создавшего STL): «о истории алгоритма нахождения наибольшего общего делителя», это популярная лекция оказалась бесконечно интересной, в ней рассказывается, на примере этого алгоритма о развитие алгоритмического знания всего человечества с эпистемологической точки зрения в разрезе истории с античных времен с Пифагора до наших дней до Кнута.
Посмотреть можно здесь:
часть1
video.yandex.ru/users/ya-events/view/129
часть2
video.yandex.ru/users/ya-events/view/128
Посмотреть можно здесь:
часть1
video.yandex.ru/users/ya-events/view/129
часть2
video.yandex.ru/users/ya-events/view/128
«Теоретический минимум» Леонарда Сасскинда издан на русском
4 мин
Рады сообщить, что в издательстве «Питер» вышел перевод новой книги Леонарда Сасскинда и Джорджа Грабовски — «Теоретический минимум» (ориг: The Theoretical Minimum: What You Need to Know to Start Doing Physics).
В Америке эта книга, несмотря на свой формат лекций по физике и классической механике, неожиданно стала настоящим бестселлером, а The Wall Street Journal вообще признал ее «Книгой 2013 года». В России книга вышла в издательстве «Питер» при поддержке гуманитарного фонда «Династия», цель которого — содействовать изданию лучших современных научно-популярных книг в области естественных и гуманитарных наук.
Мы уже издавали одну книгу Сасскинда на русском — «Битву при черной дыре» (пост о ней был на Хабре) — но «Теоретический минимум» по формату и содержанию кардинально от нее отличается.
В Америке эта книга, несмотря на свой формат лекций по физике и классической механике, неожиданно стала настоящим бестселлером, а The Wall Street Journal вообще признал ее «Книгой 2013 года». В России книга вышла в издательстве «Питер» при поддержке гуманитарного фонда «Династия», цель которого — содействовать изданию лучших современных научно-популярных книг в области естественных и гуманитарных наук.
Мы уже издавали одну книгу Сасскинда на русском — «Битву при черной дыре» (пост о ней был на Хабре) — но «Теоретический минимум» по формату и содержанию кардинально от нее отличается.
Есть ли у Вселенной центр и куда указывает «дьявольская ось»?
Простой
9 мин
Первые пятьсот лет прошлого тысячелетия никто не сомневался, что непоколебимый центр мира существует - и в нем находится Земля. Потом Коперник потряс основы мироздания, переместив Солнце в центр Вселенной и опустив Землю до рядовой планеты. Центр у Вселенной сохранился, но осадочек остался. Дальше – больше: потом и Солнце приравняли к обычным звездам и стали считать, что Млечный Путь является Вселенной, соответственно, центр нашей Галактики и является центром мира.
Настал 20 век вместе с полной чехардой в науке. Весто Слайфер, сын фермера и сотрудник частной обсерватории Лоуэлла, уже в первое десятилетие этого беспокойного века показал, что Млечный Путь – тоже рядовая галактика, несмотря на то, что она нам как родная. Где центр у Вселенной будем делать? – совсем растерялись астрономы. Но в 1922 году многомудрый Фридман, на основе недавно созданной теории Эйнштейна придумал такую хитрую модель расширяющейся Вселенной, в которой центра-то и нет! Такая модель распухающего во все стороны теста с изюмом, где все изюминки (галактики) двигаются друг от друга, или, другими словами, расстояние между всеми галактиками растет. Так что, где хотите, там центр Вселенной делайте, да хоть на Земле! Чувствуете, как круг замкнулся?
Конечно, концепция чего-то, которое неизвестно откуда и куда расширяется во всех точках одновременно, в обычных головах никак не укладывается. Ну и что? Зато всем понятно, что только космологи могут объять необъятное, а другие пусть просто благоговеют, глядя на них.
Ускорение Python в 2 раза с помощью multiprocessing, async и MapReduce
Средний
16 мин
Python действительно может считаться относительно медленным языком программирования по сравнению с некоторыми другими языками, такими как C++ или Java. Однако, существуют различные библиотеки и инструменты, которые позволяют ускорить выполнение счетных задач в Python. Рассмотрим как можно ускорить анализ данных в 2 раза!
На чем разработать свой стартап или с чего начать хакатон в 2024? (часть 1)
Средний
5 мин
Обзор
Попробуем собрать свой идеальный boilerplate для full-stack разработки в 2024 году. В этой статье мы будем постепенно собирать свой шаблон для быстрого запуска стартапов.
Сразу предупреждаю, что статья будет холиварной, всех хейтеров прошу в комменты, предлагайте решения со ссылкой на публичные кейсы.
Математические основы кодирования и шифрования
10 мин
Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.
Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.
О контра- и ковариантных тензорах
Средний
57 мин
Записки «чайника», травмированного тензорным исчислением
Тема, заявленная в названии, пожалуй, самая запутанная в тензорном исчислении. Высокоучёные авторы мудрых книг в большинстве случаев ограничиваются только формальными определениями понятий ко- и контравариантности, не опускаясь до подробного пояснения их геометрической и физической сути. Похоже, в этом вопросе они сознательно или бессознательно воспроизводят ситуацию, характерную для квантовой физики: «Не старайтесь понять, просто считайте!». Но если в квантовой физике подобный подход безальтернативен, то в данном случае – вряд ли.
Подзаголовок даже комплиментарен для меня, поскольку в своём восприятии математики я даже не «чайник», а, скорее, «валенок». По этой причине мне очень хорошо понятны проблемы «чайников», с которыми они сталкиваются в попытках постичь математические абстракции. Поэтому материал предназначен не для «продвинутых», они и без меня разберутся, а для… В общем, для таких же, как я, «задвинутых» в математике (только в ней!). При этом предполагается хотя бы «шапочное» знакомство с тензорным исчислением.
Математика остаётся непонятной для многих потому, что нам её объясняют люди, которые понимают её на интуитивном уровне, или, выражаясь более изящно, «на уровне интуитивных образов» [1-7 ≡ Л.1, с. 7]. Нам же, нематематикам, для того, чтобы что-то понять, надо это «что-то» увидеть не в абстрактном («интуитивном»), а в реальном, физически представимом пространстве (по-научному это – «визуализация») или, ещё лучше, поковырять его пальцем (научный термин пока еще не придумали. Открыт приём предложений).
Криптографы открыли новую основу для квантовой секретности
Средний
10 мин
Перевод
Допустим, вы хотите отправить личное сообщение, провести тайное голосование или надёжно подписать документ. Если вы выполняете любую из этих задач на компьютере, то для обеспечения безопасности ваших данных вы полагаетесь на шифрование. Это шифрование должно выдерживать атаки взломщиков, работающих на своих собственных компьютерах, поэтому современные методы шифрования основаны на предположениях о том, какие математические задачи компьютерам сложно решать.
Но когда в 1980-х годах криптографы заложили математические основы этого подхода к информационной безопасности, несколько исследователей обнаружили, что вычислительная сложность — не единственный способ защитить секреты. Оказалось, что квантовая теория, изначально разработанная для понимания физики атомов, глубоко связана с информацией и криптографией. Исследователи нашли способ обеспечить безопасность нескольких конкретных криптографических задач непосредственно на основе законов физики. Но эти задачи были странными исключениями — для всех остальных, казалось, не существовало альтернативы классическому вычислительному подходу.
К концу тысячелетия исследователи квантовой криптографии думали, что на этом история закончилась. Но всего за несколько последних лет в этой области произошёл ещё один сейсмический сдвиг.
Андрей Карпати: Bitcoin на Python (часть 1)
21 мин
Перевод
Андрей Карпати — директор по искусственному интеллекту и Autopilot Vision в Tesla.
Я считаю, что блокчейн — классная штука, потому что он расширяет open source разработку софта до open source + state. Это кажется интересным нововведением в компьютерных парадигмах; Мы не просто делиться кодом, мы можем предоставить общий доступ к работающему компьютеру, и любой человек в любом месте может использовать его открыто и без разрешения. Семена этой революции, возможно, начались с биткойна, поэтому мне стало любопытно вникнуть в него более подробно, чтобы получить интуитивное понимание того, как он работает. И в духе «то, что я не могу создать, я не понимаю», что может быть лучше, чем реализовать биткойна с нуля?
Мы собираемся создать, поставить цифровую подпись и транслировать биткойн-транзакцию на чистом Python, с нуля и с нулевыми зависимостями. В процессе мы немного узнаем о том, как биткойн представляет ценность. Давай попробуем.
(кстати, если визуальный формат этого поста вас раздражает, посмотрите версию jupyter notebook, у которой идентичный контент).
Шаг 1: создание крипто сущности
Для начала мы хотим создать совершенно новую криптографическую сущность, которая представляет собой всего лишь пару ключей: публичный и приватный. Биткойн использует криптографию на эллиптических кривых (Elliptic-Сurve Сryptography, ECC) вместо чего-то более распространенного, например RSA, для защиты транзакций. Я не собираюсь здесь углубляться в ECC, потому что другие проделали значительно лучшую работу, например, я считаю серию постов в блоге Андреа Корбеллини очень полезным ресурсом. Здесь мы просто напишем код, но чтобы понять, почему он работает математически, вам нужно прочитать эти посты.
Роботизированная история с древних времён до наших дней
Простой
14 мин
Ретроспектива
История роботов начинается задолго до XX века. Две сотни лет назад появились автоматоны, способные писать тексты, рисовать и пускать стрелы, а в начале нашей эры встречаются упоминания о различных механизмах, которых можно было бы назвать роботами. Они изображали людей и животных, выполняли различные действия – например, наливали вино или заходили в комнату короля.
В этой статье поговорим об истории человекоподобных роботов и о том, к чему она нас привела. При этом специально не затрагиваем такие темы, как специализированные роботы для спасения людей в чрезвычайных ситуациях, автомобили с автопилотом, роботов-собак и летательные аппараты.
Какие моменты в истории создания роботов вам кажутся наиболее важными? И какими вы видите роботов будущего? Появятся ли антропоморфные машины на наших кухнях в ближайшее время? Пишите в комментариях!
Эксперты призывают готовиться к криптоапокалипсису
3 мин
На прошедшей в Лас-Вегасе конференции Black Hat с особым заявлением выступили четверо исследователей кибербезопасности: Алекс Стеймос, Том Риттер, Томас Птачек и Джавед Сэмюель. Суть их просьбы сводилась к следующему: существующие алгоритмы, лежащие в основе современной криптографии, могут находиться в опасности прогресса решения математических задач, поэтому всем нам следует отказаться от существующих SSL-сертификатов в пользу более новых методов криптографии.
Общеизвестно, что в основе асиметричной криптографии лежит два ключа: один может зашифровать данные, другой используется для их расшифровки. Это возможно благодаря свойствам односторонних функций. Предполагается, что некоторые математические операции трудны и могут быть выполнены лишь за экспоненциальное время, то есть за время, возрастающее экспоненциально при линейном увеличении размерности задачи. Однако, существование таких функций, то есть свойство экспоненциального возрастания сложности так и остаётся недоказанной гипотезой.
Существует ненулевая вероятность того, что в будущем найдётся подобное решение, возможное за полиномиальное время, что сулит криптографический апокалипсис. Суть доклада квартета исследователей сводилась к тому, что этот момент может быть не так отдалён от настоящего времени, в то время как альтернативные и более современные методы криптографии не имеют большого распространения.
Генерируем цепочку сертификатов с эллиптическими кривыми при помощи OpenSSL
8 мин
Думаю многие слышали о криптографии эллиптических кривых, о томчто работает она во много раз быстрее RSA и при несоизмеримо меньшей длине ключа обеспечивает несоизмеримо большую стойкость ко взлому. Если не слышали, то можно глянуть на wiki или почитать в книгах А.А. Болотова.
К сожалению, данный вид шифрования слабо распространен. Я постараюсь объяснить как им пользоваться и поможет мне в этом OpenSSL.
Чтобы не быть голословным приведу сравнение необходимых длин ключей для обеспечения сравнимой стойкости ко взлому для различных алгоритмов. Нам интересна правая часть.
Видно, что популярным сегодня ключам RSA длиной 1024-2048 бит соответствует всего навсего 160-224битный ключ ECC (Elliptic Curve Cryptography)
Ну а чтобы понять какой RSA тормоз достаточно попробовать сгенерировать самый длинный из предложенных в таблице ключей (и пойти вздремнуть):
openssl genrsa 15360
Желающих прикоснуться к «next gen» криптографии, придуманной аж в 1985 году, прошу под кат.
Эллиптическая криптография: теория
7 мин
Туториал
Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.