Finite State Entropy (FSE) – алгоритм энтропийного кодирования, чем-то похожий и на алгоритм Хаффмана, и на арифметическое кодирование. При этом он взял лучшее от них обоих: работает так же быстро, как хаффмановский, и со степенью сжатия как у арифметического кодирования.

FSE принадлежит семейству кодеков ANS (Asymmetric Numeral Systems),  изобретённых Яреком Ду́дой. На основе его исследований Ян Колле разработал оптимизированный вариант алгоритма, впоследствии названный FSE.

В заметках Яна Колле непросто разобраться, поэтому я изложу объяснение в несколько ином порядке, более удобном для понимания, на мой взгляд.

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

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

Я открою этот цикл статьёй о Theano — библиотеке, которая используется для разработки систем машинного обучения как сама по себе, так и в качестве вычислительного бекэнда для более высокоуровневых библиотек, например, Lasagne, Keras или Blocks.

Theano разрабатывается с 2007 года главным образом группой MILA из Университета Монреаля и названа в честь древнегреческой женщины-философа и математика Феано (предположительно изображена на картинке). Основными принципами являются: интеграция с numpy, прозрачное использование различных вычислительных устройств (главным образом GPU), динамическая генерация оптимизированного С-кода.

Создатель 144-ядерного процессора GA144 и языка программирования Forth, известный программист Чарльз Мур (Charles H. Moore), известный также под именем Чак Мур (Chuck Moore), в своей лекции рассказывает о перспективах применения 144-х ядерного асинхронного чипа, созданного его компанией, GreenArrays, а также его программировании. Ведь его чип потребляет всего лишь 7 пДж энергии (при выполнении базовой инструкции ALU, что занимает 1.5 наносекунды), что делает его незаменимым в случаях, когда процессор может питаться лишь от автономного источника энергии без возможности подзарядки, начиная от разработок в сфере медицины и заканчивая робототехникой. Незадействованные ядра потребляют всего 100 нановатт, в то время, как активным, требуется всего 4 милливатта при обработке 666 MIPS: плотный код сводит к минимуму количество выполняемых инструкций, уменьшая количество выборки команд, переключения транзисторов и рабочего цикла.

Так как лекция еще не публиковалась ранее, мы опубликовали её для Вас на youtube:



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

Сам процессор поступил в продажу в 2011-м году, по цене $20. В этой публикации мы постарались систематизировать имеющуюся новую информацию и заполнить пробелы, которые могут возникнуть после чтения документации от GreenArrays.

Троичные вычисления

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

• Считаем до трёх: раз
• Считаем до трёх: два (память)
• Считаем до трёх: три (счётчики)
• Считаем до трёх: четыре (однотритный вычислитель и система команд трёхтритного)

Я выбрал сбалансированную троичную систему, в которой один трит может представлять одно из трёх значений -1, 0 или 1. Весьма подробно о ней можно почитать тут.

На любые вопросы из разряда «зачем?!» я отвечаю заранее: «Because I can».

В Университете ИТМО продолжается подготовка к приему будущих бакалавров, магистров и аспирантов — проходят Дни открытых дверей, олимпиады для школьников и Конгресс молодых ученых.

О том, как устроена Приемная кампания-2017, сегодня расскажет Анна Веклич, первый заместитель председателя Приемной комиссии, начальник Департамента по стратегическим коммуникациям Университета ИТМО.

В этом материале мы постарались собрать все, что нужно абитуриенту: от статистики прошлых лет до устройства мегафакультетов Университета и бонусов при поступлении.

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

Итак, задача вполне себе житейская.

Некий Мужик занимается перепродажей коров: он скупает их за фиксированную небольшую цену a рублей у местного населения и пытается продать с наценкой посетителям рынка. Предположим для простоты, что покупатели по своей платежеспособности делятся на n классов, и, что любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей. Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое. Если в момент появления покупателя у Мужика нет коров, то первый не становится в очередь, а удаляется восвояси и обратно уже не возвращается. Задачи бы попросту не было, если бы не два правдоподобных условия:

Введение

В последние годы вездесущие нейронные сети находят все больше и больше применений в различных областях знаний, вытесняя классические алгоритмы, использовавшиеся многие годы. Не стала исключением и область компьютерного зрения, где год за годом все больше и больше задач решаются при помощи современных нейронных сетей. Настало время написать об еще одном павшем бойце в войне "Традиционное зрение vs. Глубокое Обучение". Долгие годы на задаче поиска локальных особенностей изображений (так называемых ключевых точек) безраздельно властвовал алгоритм SIFT(Scale-invariant Feature Transform), предложеный в далеком 1999 году, многие сложили головы в попытках превзойти его, но удалось это лишь Deep Learning'у. Итак, встречайте, новый алгоритм поиска локальных особенностей — LIFT (Learned Invariant Feature Transform).

Привет всем, кто проходит курс машинного обучения на Хабре!

В первых двух частях (1, 2) мы попрактиковались в первичном анализе данных с Pandas и в построении картинок, позволяющих делать выводы по данным. Сегодня наконец перейдем к машинному обучению. Поговорим о задачах машинного обучения и рассмотрим 2 простых подхода – деревья решений и метод ближайших соседей. Также обсудим, как с помощью кросс-валидации выбирать модель для конкретных данных.

UPD 01.2022: С февраля 2022 г. ML-курс ODS на русском возрождается под руководством Петра Ермакова couatl. Для русскоязычной аудитории это предпочтительный вариант (c этими статьями на Хабре – в подкрепление), англоговорящим рекомендуется mlcourse.ai в режиме самостоятельного прохождения.

Сегодня представляем вашему вниманию один из свежих курсов Технопарка — «Алгоритмы и структуры данных». Он представляет собой изучение базовых алгоритмов и структур данных, необходимых программистам для качественного решения ежедневных задач. В курсе представлены алгоритмы для работы с массивами, сортировки. Рассказывается об элементарных структурах данных: стек, очередь, списки, куча. Также в программу включены различные деревья поиска и хеш-таблицы. Курс дает представление о том, как оценивать эффективность алгоритмов, все алгоритмы курса оцениваются по времени работы и по количеству используемой дополнительной памяти. Вас ждут шесть лекций:

• «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»;
• «Жадные алгоритмы»;
• «Сортировки»;
• «Поиск. Списки»;
• «Деревья»;
• «Хеш-таблицы».

Четыре лекции курса читает Степан Мацкевич, руководитель группы извлечения онтологической информации в компании ABBYY. Он был ведущим программистом при написании серверной части продукта ABBYY InfoExtractor на основе технологии ABBYY Compreno (анализ текстов и перевода).

Еще две лекции ведет Георгий Иванов, разработчик Поиска Mail.Ru, занимающийся задачами обработки поисковых запросов.

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

ВВС США, а именно Air Force Research Lab (AFRL), использует возможности процессора для идентификации военных и гражданских транспортных средств при радиолокации с воздуха. Военные утверждают, что чип работает не хуже, чем мощный военный компьютер. Но энергии при этом потребляется в двадцать раз меньше.

[Перевод первой части находится здесь.]

Унаследованный код

Build — это выдающийся движок, а множество игр, использовавших его, принесли большую и заслуженную славу и Кену Силверману, и 3D Realms.

Кен Силверман выполнил условия договора: он предоставил двоичный файл потрясающего 3D-движка с хорошо задокументированными методами и форматами ресурсов. В качестве признания его заслуг 3D Realms указала его имя в титрах как «Ken 'I can do that' Silverman» (Кен «Я могу это сделать» Силверман). Но разработка Build была сосредоточена на возможностях и скорости, а не удобстве портирования и чтения. После изучения кода я думаю, что open source-разработчики избегали его по следующим причинам:

• Его обескураживающе сложно читать и получать из него знания.
• Он не был портируемым.

В этой статье я перечислил часть сложностей, с которыми столкнулся. Также я выпустил порт Chocolate Duke Nukem 3D, призванный решить эти проблемы. Я хотел, чтобы люди запомнили, какой уровень гениальности нужен был для создания 3D-движка в то время. Кроме того, я хотел, чтобы они осознали, как движимый страстью подросток смог внести вклад в одну из величайших игр всех времён.

Традиционно сообщаем об открытии набора на кафедру математических и информационных технологий.



Академический университет существует с 2008 года. За это время мы успели открыть аспирантуру, магистратуру и бакалавриат (да, именно в таком порядке); cтать Национальным исследовательским университетом; выиграть мегагрант по биоинформатике и еще много всего. В этом посте мы расскажем о том как к нам поступить и том, что нового у нас произошло в течение года.

Уйдя с работы в Amazon, я провёл много времени за чтением отличного исходного кода.

Разобравшись с невероятно замечательным кодом idSoftware, я принялся за одну из лучших игр всех времён: Duke Nukem 3D и за её движок под названием "Build".

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

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

Что: трассировка каскадов воксельных конусов

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

Таким способом обрабатывается и прямое, и отражённое освещение. Он позволяет нам рассчитывать на PlayStation 4 три отражения глобального освещения в полудинамических сценах. Мы трассируем конусы в 16 фиксированных направлениях через шесть каскадов 3D-текстур и выполняем поглощение света с помощью направленного затенения в экранном пространстве (Screen Space Directional Occlusion) и сферическими окклюдерами динамических объектов для получения конечного результата. Движок также поддерживает модель сферического освещения на основе гармоник, что позволяет рассчитывать освещение частиц и реализовать спецэффекты, например аппроксимированное подповерхностное рассеяние (approximating subsurface scattering) и преломляющие материалы.

Доброго времени, Хабр!

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

Начну с небольшой вводной. Будучи студентом 4-го, на тот момент, курса бакалавриата, я изучал курс «Компьютерная графика». Много там было разных интересных (и не очень) заданий, но одно прямо особо запало мне в душу: интерполяция кубическими сплайнами с заданными первыми производными на концах интервала. Пользователь должен был задавать значения первых производных, а программа — считать и выводить на экран интерполяционную кривую. Особенность и основная сложность задания заключена в том, что задаются именно первые производные, а не вторые, как в классической постановке сплайн-интерполяции.
Как я ее решал, и к чему оно в итоге пришло, я как раз и изложу в этой статье. И да, если по описанию задачи вы не поняли ни в чем ее смысл, ни в чем сложность, не переживайте, все это я также постараюсь раскрыть. Итак, поехали.

А, нет, погодите один момент. Вот вам два числовых ряда:
a) 2, 4, 6, 8, ?
b) 1, 3, ?, 7, 9

Какие числа должны стоять на месте вопросов и почему? Вы действительно уверены в своем ответе?

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

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

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

Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице.

Если вы хотите только попробовать её в работе, то можете скачать отсюда. Либо пролистайте вниз до раздела «Исходный код и использование». Хотите подробностей — читайте дальше.

В прошлом году в Академическом университете прошел первый конкурс студенческих работ по теоретической информатике и дискретной математике им. Алана Тьюринга. Недавно мы объявили второй конкурс (срок подачи работ 10 мая 2017 года), а в этой статье мы расскажем об итогах первого конкурса.

Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.

Статья основана на ответе в StackOverflow. Начну с описания проблемы, с которой я столкнулся. Есть несколько сущностей в базе данных, которые нужно отображать в виде таблиц на UI. Для доступа к базе данных используется Entity Framework. Для этих таблиц есть фильтры, по полям этих сущностей. Нужно написать код для фильтрации сущностей по параметрам.