Книга
Fundamentals of Computation Theory, 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings
The volume is dedicated to Boris Mirkin on the occasion of his 70th birthday. In addition to his startling PhD results in abstract automata theory, Mirkin’s ground breaking contributions in various fields of decision making and data analysis have marked the fourth quarter of the 20th century and beyond. Mirkin has done pioneering work in group choice, clustering, data mining and knowledge discovery aimed at finding and describing non-trivial or hidden structures—first of all, clusters, orderings, and hierarchies—in multivariate and/or network data.
This volume contains a collection of papers reflecting recent developments rooted in Mirkin's fundamental contribution to the state-of-the-art in group choice, ordering, clustering, data mining, and knowledge discovery. Researchers, students, and software engineers will benefit from new knowledge discovery techniques and application directions.
Статья посвящена описанию применения разработанной в МИЭМ объектно-атрибутной архитектуры вычислительной системы для реализации система искусственного интеллекта.
Проблема создания интеллектуальных систем чрезвычайно актуальная в наше время, однако до сих пор не было предложено достаточно эффективного способа построения подобных систем. Все существующие способы (фреймовые системы, нейронные сети, объектно-ориентированное программирование, нейронные сети, семантические сети) не обладают достаточной гибкостью или не обеспечивают достаточную абстракцию данных, необходимую для подобных задач. Объектно-атрибутная же архитектура обладает всеми необходимыми качествами для создания интеллектуальных систем: абстракция данных, гибкость организации вычислительного процесса, изоморфизм данных и программы, высокий параллелизм вычислений и т.д.
Также в статье приведен пример объектно-атрибутной программы, предназначенной для смыслового распознания текста. В данном примере приведены необходимые для организации функциональные устройства (ФУ): в объектно-атрибутная архитектуре алгоритм задается не как последовательность выполняемых команд, а как описание обмена информацией между ФУ (концепция, управления вычислительным процессом потоком данных (dataflow)). В статье также описывается синтез абстрактных данных от простого к сложному, происходящий в ОА-вычислительной системе.
Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток называется допустимым, если сумма весов $T$-путей, проходящих через каждую вершину $v$, не превышает $c(v)$. Величиной $F$ называется сумма весов $F(P)$, а стоимостью $F$ называется сумма (по всем $T$-путям $P$) произведений $F(P)$ на стоимости путей $P$ относительно функции $a$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.
We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ documents, and (iii) all shortest extensions of $P$ which occur only in $d$ selected documents. For these problems, we propose efficient algorithms based on suffix trees and using advanced data structure techniques. For problem (i), we propose an optimal solution with constant running time per output word.
Пусть задан орграф $G = (VG,AG)$. Четным фактором $M \subseteq AG$ называется множество ребер, образованное набором вершинно непересекающихся путей и четных циклов. Четные факторы были введены Гиленом и Каннингхемом, они обобщают т.н. path matchings в неориентированных графах. Задача нахождения четного фактора максимального размера в графе общего вида является NP-трудной, однако для класса нечетно циклически симметричных орграфов эта задача является полиномиальной. К настоящему моменту был известен лишь один комбинаторный способ ее решения, принадлежащий Папу. Этот алгоритм имеет сложность $O(n^4)$ (где $n$ обозначает число вершин в $G$, а $m$ обозначает число ребер). В данной работе мы развиваем новую технику разреженного восстановления и строим алгоритм со сложностью $O(n^3 \log n)$, находящий нечетный фактор максимального размера в нечетно циклически симметричном орграфе. Наш подход также применим к другим аналогичным задачам, например к задаче нахождения максимального простого $b$-паросочетания без квадратов.
We study a new variant of the string matching problem called {\em cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear-space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the {\em weighted level ancestor} problem.
This book constitutes the refereed proceedings of the 12th Industrial Conference on Data Mining, ICDM 2012, held in Berlin, Germany in July 2012. The 22 revised full papers presented were carefully reviewed and selected from 97 submissions. The papers are organized in topical sections on data mining in medicine and biology; data mining for energy industry; data mining in traffic and logistic; data mining in telecommunication; data mining in engineering; theory in data mining; theory in data mining: clustering; theory in data mining: association rule mining and decision rule mining.