### Book

## Proceedings of the First International Conference on Data Compression, Communications and Processing

This book constitutes the refereed proceedings of the First International Conference on Data Compression, Communications and Processing held in Palinuro, Italy, in June 2011.

We consider a compact text index based on evenly spaced sparse suffix trees of a text \cite{KU-96}. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. The algorithm is based on a notion of suffix links different from that of~\cite{KU-96} and on the packing of several letters into one computer word.

This research aims to extend my previous work that analyzed community lifecycle within social network Vkontakte. One of serious problems of that work was inability to analyze whole graph, since Vkontakte’s API do not allow to download all network in a reasonable time, thus you are restricted with number of requests per second. This paper discuss main achievements of that work and propose one method that should be included in that kind of researches and should help to make more precise conclusions.

The new technology used for data processing of population census results is described. The system was recently launched by Rosstat for 2002 and 2010 censuses. It gives the user an opportunity of on-line tabulation any demographic table from micro data with no need to download the data themselves and to set up any software. The examples of the results absent in the official census tabulation obtained by means of this system are given.

A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation.

The textbook contains necessary information about universal and classical algebras, systems of axioms for the basic algebraic structures (groupoid, monoid, semi-groups, groups, partial orders, rings, fields). The basic cryptographic algorithms are described. Error-correcting codes - linear, cyclic, BCH are considered. Algorithms for designing of such codes are given. Many examples are shown. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty of National research university Higher school of economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.