В статье рассматривается размер памяти, необходимый и достаточный для хранения графа из класса неориентированных корневых упорядоченных связных графов как нумерованных, так и ненумерованных. Введение содержит основные определения и постановку задачи. Граф корневой, если одна из вершин выделена и названа корнем. Граф упорядоченный, если для каждой вершины все инцидентные ей рёбра линейно упорядочены. Граф нумерованный, если все его вершины помечены различными идентификаторами, в частности, пронумерованы целыми числами от 0 до n -1, где n число вершин графа. Два неориентированных корневых упорядоченных графа G и G` считаются слабо изоморфными, если существует взаимно-однозначное соответствие вершин такое, что: 1) соответствующие вершины имеют одинаковые степени, 2) рёбра ab из графа G и a`b` из графа G` , инцидентные соответствующим вершинам a и a` и имеющие в этих вершинах одинаковые номера, ведут в соответствующие вершины b и b` , 3) корни соответствуют друг другу. Для нумерованных графов при изоморфизме дополнительно требуется совпадение номеров соответствующих вершин. Графы рассматриваются с точностью до слабого изоморфизма. Показано, что память, необходимая и достаточная для хранения любого графа из указанного класса, имеет размер Q( mlogn ) для нумерованных графов, Q( n +( m - n +1) logn ) для ненумерованных графов с числом вершин n и числом рёбер m , и Q( n² logn ) для графов без кратных рёбер и петель с числом вершин n . Также показано, что память, достаточная для хранения последовательности рёбер длины O ( n ) или остова графа, имеет размер O ( nlog ( n D)) или O ( nlog D), соответственно, где D максимальная степень вершины.

Предложен общий подход к решению задач на неориентированном упорядоченном корневом связном графе коллективом автоматов, расположенных в вершинах графа и обменивающихся сообщениями по рёбрам графа. Автоматы считаются полуроботами, т.е. размер их памяти может расти вместе с ростом числа n вершин и числа m рёбер графа, но описание графа может не помещаться в памяти автомата. В разделе 2 классифицируются модели коллектива автоматов на графе в зависимости от размера памяти автомата, времени срабатывания автомата и ёмкости ребра (числа сообщений, одновременно перемещающихся по ребру). Выбрана модель максимального распараллеливания, в которой время срабатывания автомата считается нулевым, а ёмкость ребра неограниченной. Это позволяет получать нижние оценки сложности алгоритмов решения задач. Раздел 3 определяет правила оценки алгоритмов. В разделе 4 описаны базовые процедуры обработки сообщений и проводится классификация используемых сообщений в зависимости от маршрутов, проходимых сообщениями, и способа размножения или слияния сообщений. На основе этих процедур предлагается строить алгоритмы решения задач на графах, что демонстрируется в следующих разделах статьи. В разделах 5-9 предложены алгоритм построения остова графа, алгоритм универсального «стопора», определяющего конец работы любого алгоритма по отсутствию в графе сообщений, используемых этим алгоритмом, алгоритм построения дерева кратчайших путей, алгоритм нумерации вершин графа, и алгоритм сбора полуроботами информации о графе в неограниченной памяти автомата корня. Предложенные алгоритмы имеют линейную сложность от n и m , и используют число сообщений, линейно зависящее от n и m . В разделе 10 рассматривается задача поиска максимального пути в нумерованном графе, которая относится к классу NP . За счёт неограниченного (экспоненциального) числа сообщений алгоритм решения этой задачи имеет линейную сложность. В заключении подводятся итоги и намечаются направления дальнейших исследований: решение других задач на графах и расширение подхода на ориентированные графы, а также недетерминированные и динамические графы.

Существующие исследования, которые посвящены анализу развития ядра операционной системы Linux, рассматривают ядро вместе с поставляемыми с ним загружаемыми модулями или некоторые конкретные подсистемы ядра. Целью данной работы является оценка развития ядра без загружаемых модулей, для чего предлагается метод определения границы между ними. Оценка развития дается для всех версий ядра операционной системы Linux, выпущенных за последние 7,5 лет. Также приводятся результаты классификации и распределение типовых ошибок, исправленных в ядре, на основе анализа изменений, которые были сделаны в стабильных ветках ядра за последние 2 месяца 2015 года. Полученные результаты могут быть использованы при оценке актуальности и применимости различных методов и инструментов обеспечения качества программных систем.

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

В октябре 2013 г. состоялась восьмая встреча исследователей в области баз данных. Первая подобная встреча прошла в феврале 1988 г., так что между ними прошло 25 лет. После каждой встречи публиковался отчет, содержащий обзор современного состояния области и программу исследований на ближайшее будущее – своего рода набор прогнозов развития исследовательской деятельности. В этой статье рассматриваются наиболее интересные прогнозы из отчетов о встречах исследования, обсуждается, насколько они оказались обоснованными, в какой мере сбылись или не сбылись. В числе рассматриваемых разнородных вопросов технологии баз данных содержатся следующие: роль специализированной аппаратуры при построении эффективных СУБД; SQL и приложения баз данных; перспективы объектно-реляционных расширений; распределенные неоднородные системы баз данных; базы данных и Web; базы и хранилища данных, OLAP и data mining; компонентная организация СУБД; критерии оптимизации запросов; самонастраиваемость и самоуправляемость СУБД; архитектура СУБД и новые аппаратные возможности: SSD, энергонезависимая память, массивно-многопоточные процессоры; специализированные СУБД; пространства данных; проблема Больших Данных и реакция на нее в сообществе баз данных; изменения в архитектуре компьютерных систем.

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

В последние годы многие научные коллективы исследуют поведение организованных сообществ в различных областях, например, изучают поведение растущих городов в соответствии с теорией фракталов. Теория фракталов является мощным инструментом для анализа взаимосвязи между ростом городов и распределением сети центров здравоохранения для населения. Целью данной работы является разработка методологии, основанной на теории фракталов, для изучения сообщества общественных организаций в области здравоохранения в государстве Чили, а также для изучения роста населения и эффективного расположения медицинских центров для обслуживания населения. Авторами статьи предложен эмпирический подход для анализа ситуации в области здравоохранении и различных эффектов приложения данного подхода. Известно, что фрактальная теория применима к задачам физики и математики. Имеется много примеров, в которых изучается геометрия объектов для обеспечения понимания многообразных форм в природе. В связи с этим, мы представляем в этой работе ряд идей и свои первые результаты анализа фрактального поведения процесса урбанизации в городах, влияния урбанизации на расположение центров здравоохранения с использованием простейших счетных алгоримтов и спектральных методов с использованием программного обеспечения ImaCal. Результаты исследования позволят лучше понимать разные аспекты миграции населения в связи с размещением центров здоровья людей.

Локальная диффузия и топологическая структура завихрения и поля скоростей измерены в переходном режиме от гомогенной линейно стратифицированной жидкости до ячеистой или многоуровневой структуры посредством конвективного охлаждения и/или нагревания. Подобные структуры возникают, создавая конвективный поток, при использовании массива термоэлектрических устройств (элементы Peltier/Seebeck), которые генерируют значительный тепловой поток. Описанные в статье эксперименты направлены на изучение различных чисел Прандтля с использованием пластовой и пресной воды, чтобы сформировать градиенты плотности и низкие числа Прандтля для режимов смешения с градиентами температуры. Набор безразмерных параметров определяет условия численнего и мелкомасштабного лабораторного моделирования для различных геофизических течений. Поля скорости, плотности и их градиенты были вычислены и визуализированы с использованием открытого программного пакета DigiFlow и численного моделирования на базе уравнений Рейнольдса с k-e моделью турбулетности. Когда конвективный нагрев и охлаждение происходят на стороне стратифицированной вложенной ячейки (комбинации внутренних волн и плавучести) управляемая турбулентность намного более сложна, если числа Релея и числа Рейнольдса вылики. Вычисления моментов высшего порядка и перемежаемость важны для изучения процессов перемешивания в сложных течениях. В данной работе представлены некоторые примеры с использованием Thermoelectric Convection Didactive Device (TCDD), созданного в BEROTZA, главным образом в симметричного двумерного образца. Но существует много других технических вариантов устройства, например, с использованием охлаждения и нагревания, создания стенок под углом с вертикалью, позволяющих протестировать более сложные варианты с применением численных экспериментов.

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