А не замахнуться ли нам на Эдсгера нашего Дейкстру?

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

В общем случае минимизируемая величина — это необязательно расстояние, — весами ребер графа могут быть стоимости, штрафы, убытки, времена, — любые величины, которые можно складывать. Задача является классической, наиболее простой алгоритм поиска кратчайшего пути дал Э. Дейкстра в 1959 году.

Мы в 1cloud стараемся рассказывать о различных технологиях — например, контейнерах, SSL или флеш-памяти.

Сегодня мы продолжим тему памяти. Разработчик Роберт Элдер (Robert Elder) в своем блоге опубликовал материал с описанием возможностей виртуальной памяти, которые известны не всем инженерам. Мы представляем вашему вниманию основные мысли этой заметки.

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

Для начала хочу поблагодарить автора статей «Декодирование JPEG для чайников» и «Изобретаем JPEG», которые очень помогли мне в работе по написанию данной публикации. Когда я занялся вопросами изучения алгоритмов сжатия изображений с потерями, то в части алгоритма JPEG меня всё время мучил вопрос: «Почему роль базисного преобразования в алгоритме JPEG отведена именно частному случаю преобразования Фурье?». Здесь автор даёт ответ на этот вопрос, но я решил подойти к нему не с точки зрения теории, математических моделей или программной реализации, а с точки зрения схемотехники.

Алгоритм сжатия изображений JPEG является алгоритмом цифровой обработки сигналов, которые, аппаратно, как правило, реализуются либо на цифровых сигнальных процессорах, либо на программируемых логических интегральных схемах. В моём случае, выбор для работы цифрового сигнального процессора означал бы приход к тому, от чего я пытался уйти — к программной реализации, поэтому решено было остановиться на программируемой логике.

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life):

Введение

В последние несколько лет голосовые интерфейсы окружают нас все плотнее. То, что когда-то демонстрировалось только в фильмах о далеком будущем, оказалось вполне реальным. Дело дошло уже до встраивания движков для синтеза (Text To Speech — TTS) и распознавания (Automatic Speech Recognition — ASR) речи в мобильные телефоны. Более того, появились вполне доступные API для встраивания ASR и TTS в приложения.

Ныне создавать программы с голосовым интерфейсом может любой желающий (не поскупившийся заплатить за движок). Наш обзор будет посвящен именно использованию имеющихся движков (на примере Nuance) а не созданию таковых. Также будут даны общие сведения необходимые каждому программисту впервые сталкивающемуся с речевыми интерфейсами. Статья также может быть полезна руководителям проектов, пытающимся оценить целесообразность интеграции голосовых технологий в их продукты.
Итак, начнем…

Но для затравки — анекдот:
Урок русского языка в грузинской школе.
Учитель говорит: «Дети, запомните: слова сол, фасол и вермишел пишутся с мягким знаком, а слова вилька, булька, тарелька – без мягкого знака. Дети, запомните, потому что понять это невозможно!»

Раньше этот анекдот казался мне смешным. Теперь — скорее жизненным. Почему так? Сейчас постараюсь объяснить…

Продолжаю свой цикл статей про упрощенный аналог OpenGL на Rust, в котором уже вышло 2 статьи:

1. Пишем свой упрощенный OpenGL на Rust — часть 1 (рисуем линию)
2. Пишем свой упрощенный OpenGL на Rust — часть 2 (проволочный рендер)

Напоминаю, что основой моего цикла статей является «Краткий курс компьютерной графики» от haqreu. В предыдущих статьях я шел не очень быстро. Фактически на одну статью курса у меня получилось 2 статьи. Это связанно с тем, что в своих статьях я сосредоточиваюсь главным образом на нюансах работы с Rust, а когда только изучаешь новый язык, сталкиваешься с большим количеством новых для тебя нюансов, нежели чем когда программируешь на нем уже некоторое время. Думаю дальше Rust будет подбрасывать меньше граблей, и я выровняю соотношение своих статей к статьям оригинального курса.

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


То, что мы получим по итогам данной статьи

Мир вам ничего не должен – он был тут раньше вас.
— Марк Твен

Читатель спрашивает:

А почему Вселенная не сжалась в чёрную дыру сразу после Большого взрыва?

Честно говоря, я и сам об этом много думал. И вот почему.

Микробиологи из Каролинского медицинского института в Швеции научились автоматизировать процесс получения «ДНК оригами» – фигур заданной формы, которые получаются сворачиванием длинных нитей ДНК. Компьютерная симуляция позволяет быстро рассчитать необходимые действия для получения заданной фигуры. Это ещё один шаг к наносборке и созданию 3D-принтеров, работающих в нано-масштабе.

Идея о возможности сворачивать нити ДНК в нужные структуры появилась ещё в 1980-х годах. Текущий метод исполнения этой задачи разработали учёные из Калифорнийского технологического института. Для начала нужно взять длинную одиночную нить вирусного ДНК, к которой добавляют короткие нити, служащие скрепляющими «скобами». Скобы соединяются с длинной нитью предсказуемым образом, а их размещение для получения нужной формы просчитывается на компьютере.

Как-то раз захотелось автору чего-то нового на замену хорошему, и решил он подключиться к GPON от одного известного оператора. И была автору поставлена в квартиру волшебная коробочка, через которую можно было звонить по телефону, выходить в интернет и смотреть телевизор, а заведен в нее при этом настоящий оптический кабель. И зовут эту коробочку optical network terminal (ONT) Sercomm RV6688, сделана она по заказу этого самого оператора и раскрашена соответствующим логотипом.
Работает коробочка. А автору не сидится, и опять захотелось чего-то большего, и решил он разобрать(ся), как же все это волшебство внутри коробочки получается и можно ли им тонко управлять. Но какое может быть волшебство без сюрпризов.

кадр из фильма Миссия Невыполнима II

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

Первый успех

Было решено попробовать следующий вариант:

• Добавить неизвестный номер в адресную книгу телефона;
• Зайти по очереди в приложения, привязанные к номеру (Viber, WhatsApp);
• Открыть новый чат с вновь созданным контактом и по фотографии определить отправителя.

Мне повезло и в моём случае в списке контактов Viber рядом с вновь созданным контактом появилась миниатюра фотографии, по которой я, не открывая её целиком, распознал отправителя и удовлетворенный проведенным «расследованием» написал смс с благодарностью за поздравления.

Сразу же за секундным промежутком эйфории от удачного поиска в голове появилась идея перебором по списку номеров мобильных операторов составить базу [номер_телефона => фото]. А еще через секунду идея пропустить эти фотографии через систему распознавания лиц и связать с другими открытыми данными, например, фотографиями из социальных сетей.

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

Что такое воспроизводимость? Да всё просто – мы хотим получать одну и ту же «хорошую цифирь» от запуска к запуску, потому что для нас это важно. Это критично во многих областях, где сейчас активно используются параллельные вычисления.

Итак, как вы помните, для машинных вычислений существенную роль играет порядок суммирования, и, если у нас имеются циклы, распараллеленные с помощью любой технологии, то неизбежно возникнет проблема воспроизводимости результатов, потому что никто не знает в каком порядке будет проводиться суммирование, и на сколько «кусков» будет разбит наш исходный цикл. В частности это проявляется при использовании OpenMP в редукциях.

На прошлой неделе я обновил свои мониторы. Выбросил Apple Cinema Display и на их место взял 4К-мониторы от Dell. Как печатнику, мне понравился предыдущий апгрейд с чёрно-белых до grayscale-мониторов в 90-х годах. Но 4К – ещё лучше. Дисплеи высокого разрешения уже пришли на смартфоны и планшеты. Приятно, что они появляются и у ноутбуков и декстопов. Шрифты выглядят чудесно.

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



Но что есть «4К»? С лёгкой руки маркетологов, это экран размера 3840 на 2160 пикселей (3840 – это ну почти 4000). По каждой из сторон разрешение в два раза больше, чем у HDTV, то есть 1920х1080.

Спервоначалу люди говорили, что у 4К-экранов «в два раза больше пикселей». На самом деле, если вы удвоите количество пикселей линейно, это всё равно, что вы разрежете каждый пиксель как по вертикали и по горизонтали. То есть, на экране 4К в 4 раза больше пикселей, чем у HDTV.

И, что характерно, на этом останавливаться никто не собирается, на горизонте уже дисплеи 7680 х 4320, известные как 8К. С другой стороны, разрешение, воспринимаемое человеческим глазом, имеет границы. Переход на 4К заметен. На 8К – менее заметен. В какой-то момент нужно будет перестать делить пиксели.

Но что, если они не перестанут? Что, если они будут делить пиксели бесконечно? Сколько тогда пикселей будет на экране?

а) по количеству положительных целых чисел
б) меньше
в) больше

Если вам не интересна математика, тогда итог статьи такой: купите 4К-монитор. Не стоит благодарности.

     Время идёт, и мультиклеточный процессор продолжает расти, развиваться. Пока, правда, не размножается, и состоит всего из 4-х клеток, но это все у него впереди. В данной статье попытаюсь описать основные особенности нового процессора Мультиклет R1, его характеристики и функционал, а также сравнить процессор нового поколения с родоначальником династии — процессором Мультиклет P1.
     Кратко пробежимся по историческим моментам выпуска процессоров, заглянем ненадолго в теоретические основы работы наших процессоров, обратим внимание на особенности нового процессора и его основные возможности, сравним процессоры P1 и R1, покажем прототип первого продукта на R1, и в завершении сделаем небольшой анонс.


Рис 1. Кремниевая пластина процессоров R1

Введение

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

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

Что представляет собой цикл вычислений на квантовом компьютере?

1. Приготовили кубиты в нужном количестве и нужном нам начальном состоянии.
2. Собрали кубиты в квантовый регистр.
3. Применили к квантовому регистру последовательность операций.
4. Произвели измерение кубитов, составляющих квантовый регистр. Получили в итоге двоичное число, размерность которого совпадает с размерностью квантового регистра.
5. Поразмыслили над полученным результатом.
6. Повторили цикл вычислений (пункты с 1. по 5.), возможно, много раз.
7. Поразмыслили над результатом.

За каждым из пунктов стоят тома непрошибаемой теории. Но мы же программисты. Многие ли из нас знают так уж хорошо, что там и как крутится-вертится в классических процессорах. Да, практически, никто. Да оно, вроде бы, не очень и надо. Может и здесь как-нибудь так. Нам бы среду (IDE-шку какую-никакую, или чего там есть?), пару тезисов… мы чего-нибудь накалякаем, ткнём кнопочку “run”, квантовый компилятор (или чего там у них) выдаст нам синтаксис, мы его подправим. Глядишь, потихонечку пойдёт-поедет!

Кручинин Дмитрий, Долотов Евгений, Кустикова Валентина, Дружков Павел, Корняков Кирилл

Введение

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

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

Белый карлик глазами художника

Американские астрономы в своей новой работе, опубликованной в журнале Science, рассказывают, как им удалось довести точность измерения больших космических расстояний до 4%. Помогли им в этом звёзды особого типа — сверхновая типа Ia.

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

В этой новости причудливо смешались изобретение 17 века, его улучшение из 19 века, забота о возобновляемой энергии из 20-го века и новинка века 21-го. Всё это соединилось в занимательном устройстве, созданном немецким авиаинженером Андреасом Хаузером. Охарактеризовал он свой проект как первый в мире двигатель Стирлинга на солнечной энергии, напечатанный на 3D-принтере.

Шотландский священник и изобретатель Роберт Стирлинг запатентовал свою версию теплового двигателя в 1816 году. Он улучшил и доработал конструкцию двигателей, прототипы которых были известны, по крайней мере, с 17 века.

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

Перевод поста Piotr Wendykier "Extending Van Gogh's Starry Night with Inpainting"
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~8 МБ).

Могут ли компьютеры научиться рисовать, как Ван Гог? Определенно да, до некоторой степени! Для этого, подобно художникам-копиистам, алгоритму сначало потребуется взять некоторое оригинальное произведение, а затем он сможет на их основе создать что-то сам. Насколько хорошо он сможет с этим справиться? Пожалуйста, судите сами.


Вторая премия на фотоконкурсе ZEISS