В 1998 году Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград опубликовали статью «The PageRank Citation Ranking: Bringing Order to the Web», в которой описали знаменитый теперь алгоритм PageRank, ставший фундаментом Google. Спустя чуть менее двух десятков лет Google стал гигантом, и даже несмотря на то, что его алгоритм сильно эволюционировал, PageRank по-прежнему является «символом» алгоритмов ранжирования Google (хотя только немногие люди могут действительно сказать, какой вес он сегодня занимает в алгоритме).

С теоретической точки зрения интересно заметить, что одна из стандартных интерпретаций алгоритма PageRank основывается на простом, но фундаментальном понятии цепей Маркова. Из статьи мы увидим, что цепи Маркова — это мощные инструменты стохастического моделирования, которые могут быть полезны любому эксперту по аналитическим данным (data scientist). В частности, мы ответим на такие базовые вопросы: что такое цепи Маркова, какими хорошими свойствами они обладают, и что с их помощью можно делать?

Помните очаровательного котика, которые чихал в заставке советского мультфильма? Мы помним, и нашли его — вместе с ворохом другой рисованной фантастики. В детстве она пугала и обескураживала, поскольку поднимала серьезные, взрослые темы. Настала пора пересмотреть старые мультфильмы, чтобы узнать, о каком будущем мечтали в той стране.

Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».

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

Процессоры, используемые в наших продуктах — это, в основном, 16- и 32-битные микроконтроллеры Microchip, имеющие RAM от 8 до 32 кБ, и ROM от 128 до 512 кБ, без MMU. Иногда, для самых простых устройств, используются еще более скромные 8-битные чипы.

Очевидно, что у нас нет (разумных) шансов использовать ядро Linux. Так что нам нужна какая-нибудь RTOS (Real-Time Operating System). Находятся даже люди, которые не используют никаких ОС в микроконтроллерах, но я не считаю это хорошей практикой: если железо позволяет мне использовать ОС, я ее использую.

Несколько лет назад, когда мы переходили с 8-битников на более мощные 16-битные микроконтроллеры, мои коллеги, которые были гораздо более опытными, чем я, рекомендовали вытесняющюю RTOS TNKernel. Так что это — та ОС, которую я использовал в разных проектах в течение пары лет.

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

Вместо введения

Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.

В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за priority_queue в STL C++. В конце статьи приводится краткий рассказ и ее реализация.

Вступление

Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.

Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.

Надеюсь что эта статья будет полезна:
1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science
2. Профессионалам, которые хотят закрыть «дыры» и пробелы
3. Может кто-то из преподавателей возьмет на заметку для своих курсов.
4. Студентам, аспирантам американских вузов — хотелось бы тоже получить фидбэк, особенно касается последних трендов в образовании

Что же здесь будет написано? Минимум философии и общих мыслей: конкретная программа undergraduate и graduate курсов, конечно из дисциплин наиболее мне близких. Все курсы были лично прочувствованы на собственной шкуре, по этому и пишу. (Я пытался записаться на все интересные курсы, которые были, но мой основной упор — системное программирование, базы данных и искусственный интеллект. Отсюда конечно некий bias, но пытаюсь предложить более-менее универсальную программу).

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

FutoIn — с одной стороны, это «клей» из стандартов/спецификаций разных мастей для унификации программных интерфейсов различных существующих проектов по устоявшимся типам, с другой — это концепция для построения и масштабирования компонентов проекта и инфраструктуры, написанных на разных технологиях, без потребности в добавления этого самого «клея».

AsyncSteps — это спецификация и реализация программного интерфейса для построения асинхронных программ в независимости от выбранного языка или технологии.

Цели, поставленные для концепции:

• реализация (с оговорками) должна быть возможна на всех распространённых языках программирования с поддержкой объектов и анонимных функций. Репрезентативный минимум: С++, C#, Java, JavaScript, Lua (не ООП), PHP, Python;
• написанная программа должна легко читаться (сравнимо с классическим вариантом);
• должны поддерживаться исключения языка (Exceptions) с возможностью перехвата и разворачиванием асинхронного стека до самого начала;
• требуется удобство для написания асинхронных библиотек с единым подходом для вызова, возврата результата и обработки ошибок;
• предоставить простой инструмент для естественного распараллеливания независимых веток программы;
• предоставить простой инструмент создания асинхронных циклов с классическим управлением (break, continue) и меткой для выхода из вложенных циклов;
• предоставить место для хранения состояния исполняемой бизнес-логики;
• возможность отменять абстрактную асинхронную задачу, правильно завершая выполнение (освобождая внешние ресурсы);
• возможность легко интегрироваться с другими подходами асинхронного программирования;
• возможность ограничивать время выполнения задачи и отдельно каждой подзадачи;
• возможность создавать модель задачи для копирования (улучшения производительности критичных частей) или использования как объект первого класса для передачи логики в качестве параметра (а-ля callback);
• сделать отладку асинхронной программы максимально комфортной.

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

Содержание:

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

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

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

В Священных Языковых Войнах в качестве окончательного аргумента нередко приводят — поскольку языки полны по Тьюрингу, постольку они и равноценны. Под катом попытка уточнить этот тезис для тех, кто уже справился с Python и теперь планирует изучить Erlang или Haskell по спецификации. Материал обзорный, не методичный с картинками.

Одним из основных ограничений при проектировании протяженных оптических транспортных сетей является соотношение сигнал-шум (OSNR). WDM-сети должны функционировать в допустимых пределах OSNR, чтобы обеспечить корректную работу систем.

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

На этот раз я хочу подойти к вопросу планирования с другой стороны. А именно, теперь я постараюсь рассказать про планирование не потоков, а их “младших братьев”. Так как статья получилась довольно объемной, в последний момент я решила разбить ее на несколько частей:

1. Многозадачность в ядре Linux: прерывания и tasklet’ы
2. Многозадачность в ядре Linux: workqueue
3. Protothread и кооперативная многозадачность

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

Рассказывать я постараюсь подробно, описывая основное API и иногда углубляясь в особенности реализации, особо заостряя внимание на задаче планирования.

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

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


Поиск векторов движения для компенсации движения (-: Об этом далее...

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

Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.

Приятного времени суток!

Сколько человек хочет заняться разработкой под Android, но в силу определенных обстоятельств все никак не может начать (у кого-то нет времени, кому-то скучно просто прорешивать примеры, лень, неопределенность)? Сколько человек добавляет каждую, кажущуюся интересной и полезной, статью на хабре в избранное и забивает? До конкурса ВКонтакте на разработку мессенджера под Android, я был среди числа вышеописанных пользователей. Но в один роковой момент все изменилось…