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

^{Вот так люди видят вашу страницу}

Привет!
Проблема вот в чём. Если зайти на практически любой сайт интернет-магазина или компании с услугами, вы встретите контент. Точнее — отвратительные тексты, которые писали, кажется, маркетологи, воспитанные сеошниками.

Разумеется, можно не делать, как они. Если работать по-умному, то вы поможете и читателям по жизни, и себе в продажах.

По моим примерным подсчётам (усреднение с ряда позиций), конверсии для нас выглядят так:

• Только название и картинка — около 1,5%.
• С описанием от производителя — чуть более 2%.
• С описанием человека, который держал это в руках и знает правила — около 6%.

Ниже — рассказ про то, как мы доводили время на сайте от 3 минут сначала до 6:40, а потом до 20:48. Да-да, двадцати минут сорока восьми секунд для среднего посетителя. Честного среднего, с учётом отказов и по полной выборке.

Так и подмывало озаглавить тему: «Закат компании Гугл близок!», но все-таки слишком уж «желто» было бы.

Теперь к делу. Что такое «гомоморфное шифрование» и причем тут Гугл?

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

Удивительно, но до недавних пор не существовало криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption), т.к. суммы и умножения хватит, чтобы выразить любую математическую функцию. Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст (посмотрите на формулу RSA и вспомните определение mod), поэтому через некоторое количество шагов накопленный шум делает расшифровку невозможной. Насколько я помню из презентации, говорилось, что подобные схему все же существуют, но они экспоненциональны по «эффективности».

Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации. Не вдаваясь в подробности (да и не буду делать вид, что на 100% понял все математические выкладки), смысл его решения заключается в том, что он использует двойное шифрование. Т.е. через определенное количество шагов он «снимает верхний слой» (первое шифрование) и «убирает» накопившийся «шум».

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

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

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

Долгое время полностью гомоморфная криптосистема оставалась для всех криптографов мира священным Граалем, недостижимым идеалом. И вот в 2009 году Craig Gentry в своей диссертации впервые описал полностью рабочую схему гомоморфного шифрования.
Несколько математических подробностей идеи Gentry а также пример реализации его алгоритма вы найдете под катом.

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

Итак, вернемся к теме поста. Я давно хотел немного больше узнать о комплексных числах, а не только то, что корень из минус единицы равен i. Особенно вызывали интерес фигуры имеющие фрактальную структуру, хотелось понять, что это значит, и как сделать такую визуализацию. Где то на полке стояла книжка по ТФКП, а так же закончился курс по комплексному анализу на курсере, и появилось немного свободного от работы времени. Приступим.

Статья рассчитана на людей, которые знакомятся со средой Visual Studio и пытаются компилировать в ней свои Си++-проекты. В незнакомой среде всё кажется странным и непонятным. Особенно новичков раздражает файл stdafx.h, из-за которого возникают странные ошибки во время компиляции. Очень часто всё заканчивается тем, что новичок долгое время везде старательно отключает Precompiled Headers. Чтобы помочь людям разобраться что к чему, и была написана эта статья.

Добрый день!

Как представитель проекта Лекториум рад сообщить — мы опубликовали весь архив Computer Science клуба.
Кроме того, почти год назад мы организовали запись всех лекций на хорошие камеры и микрофоны.
А в этом году планируем подключить вебинары.


Большинство лекций читается на русском языке. Все записи снабжены презентациями и описаниями.

UPD. Кратко. Старые лекции в плохом качестве, а новые с 2010 года с хорошим звуком и в 720p.
UPD 2 Расширили канал, видео грузится теперь без проблем.

Под катом перечень курсов и несколько вопросов касательно вебинаров.

В этой заметке я опишу две утилиты, которые помогут ускорить работу системы Linux, а конкретно — запуск приложений: prelink и preload. Prelink оптимизирует исполняемые файлы для быстрого связывания с библиотеками. Preload кэширует часто используемые библиотеки и программы.
Подробности под катом.

Всем известно, что функциональное программирование распространяется с быстротой огня по современным языкам программирования. Недавние примеры — Java 8 и C++, оба из которых теперь поддерживают лямбда-функции.

Итак, начнём (и да прибудет с нами веселье). Этот текст также доступен в виде слайдов на Slideshare. На написание этой статьи автор был вдохновлён создателем JSON Дугласом Крокфордом.

Функция Identity, которая принимает аргумент и возвращает тот же самый аргумент:

auto Identity = [](auto x) {
  return x;
};
Identity(3); // 3

Примечание переводчика: Новой по сравнению с C++11 является возможность не указывать названия типов.

Наверное, многие C++-программисты слышали про мультиметоды и знают о том, что по сей день нет для этого языка приемлемой реализации: ни языковой поддержки, ни внешних библиотек. Есть кодогенераторы, выкрутасы через виртуальные методы, частный случай двойной диспетчеризации aka паттерн Посетитель (Visitor). Но ведь хочется просто реализовать несколько функций и указать: этот набор функций — есть мультиметод и точка.

О мультиметодах и некоторых подходах к их библиотечной реализации давно писали Мейерс и Александреску. Почти 20 лет эти идеи обсуждаются в различной литературе по C++, но до сих пор так и не были развиты до законченного решения, которое можно было бы удобно использовать в реальных проектах…

Я решил попытать счастья, дерзнуть, предложить свое видение этой проблемы и способ ее решения. Получилась шаблонная библиотека на одних только заголовочниках.
Это реализация под стандарт C++03, на чистом C++: без каких-либо кодогенераторов и дополнений. Цель — библиотека с простым и понятным интерфейсом для реализации возможности перегружать функций по типу (и даже по значению) во время выполнения (это была программа минимум, в конечном итоге получилось еще много вкусностей).

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

bool foo(int important, int& pOut, int sometimes = 1, int occasionally = 2, int rarely = 3)
{
//...
}

Проблемы здесь могут быть следующие

1. Пользователи постоянно путают порядок параметров, тип их практически полностью совпадает, поэтому компилятор ничем помочь не может (разве что иногда со вторым параметром).
2. Из необязательных параметров чаще всего нужен один, причем если это не sometimes, пользователи вынуждены вспоминать значения по умолчанию, чтобы задать их в вызове явно. Значения по умолчанию разные, так что ошибок снова много
3. Нет никакой возможности выразить зависимость значений по умолчанию одних параметров от других.

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

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

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

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

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

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

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

Максим вводит понятие стоп-слов. Стоп-слова не характерны для текстов в информационном стиле и если вы встретили его — задумайтесь и перефразируйте это место. Стоп-слова это «кстати», междометия, модальные глаголы, отглагольные существительные и другие, всего около 100.

В какой-то момент мне стало сложно искать эти слова в текстах, поэтому я создал себе в помощь Test The Text. Test The Text выделяет в тексте слова нехарактерные для информационного стиля и объясняет почему.

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

В статистике тоже есть нечестный метод, который позволяет получить примерный ответ на многие практические вопросы без анализа, грубой компьютерной силой: бутстрап (англ. bootstrap). Придумал и опубликовал его в 1979 году Брэдли Эфрон.

Так как приходиться уже не первый раз объяснять как это делается, решил оформить в виде How-To в картинках
Скачиваем архив putty отсюда putty.zip
1. Распаковываем и запускаем ssh-keygen

Выбираем ключ ssh-rsa и длину 2048 бит. Жмем «Generate».

За последнюю неделю Хабр пополнился сразу несколькими статьями об игре «Жизнь». Что ж, тогда и я поделюсь своими наработками по этой теме.

Предисловие

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

UPD. 2025. The demo of Graph Unfolding Cellular Automata (GUCA) has been re-implemented in TypeScript: https://github.com/roma-goodok/guca

Введение

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

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

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



Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

Урок Maxima

Введение

Maxima — свободная система компьютерный алгебры (Computer algebra system — CAS), основанная на Common Lisp. В своих функциональных возможностях она едва уступает другим современным платным CAS, таким как Mathcad, Mathematica, Maple; может проводить аналитические (символьные) вычисления, численные расчеты, строить графики (при помощи gnuplot). Имеется возможность написания скриптов и даже трансляции их в код на Common Lisp с последующей компиляцией. В виду того, что maxima писалась из разрабатывалась программистами lisp, ее синтаксис может показаться несколько запутанным, поскольку язык является сразу и императивным и функциональным. Я попытаюсь разъяснить именно эти моменты и доступно изложить суть функционального подхода, и совсем не буду акцентировать внимания на конкретных математических функциях: их довольно легко освоить самостоятельно. В данной статье рассматривается именно особенности исчисления и синтаксических конструкций maxima.

Внутренняя модель nVidia GPU – ключевой момент в понимании GPGPU с использованием CUDA. В этот раз я постараюсь наиболее детально рассказать о программном устройстве GPUs.

Приветствую вас, хабралюди!

Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.



Сегодня поговорим о ArrayList-ах

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.