{'fraction_non_alphanumeric': 0.015274618134546636, 'fraction_numerical': 0.0019499512512187196, 'mean_word_length': 5.156, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Information structure of sequential programs

The paper deals with the information structure of sequential programs with linear index expressions. We show that it is described by a finite set of linear functions. The number of functions in the set is independent of the values of external parameters on which the program text may depend. The description of the information structure by linear functions opens up great opportunities for adapting the sequential programs to the requirements of supercomputers and parallel computer systems. The advent of supercomputers and parallel computer systems for solving large applied problems has radically changed the idea of the complexity of algorithms. In order to effectively solve problems on monoprocessor computers we need to know only several characteristics of algorithms, viz. the total number of operations, the accuracy, and the required memory size. The total number of operations is the most important characteristic that specifies the time necessary for solving a problem on a monoprocessor computer. Therefore the complexity of algorithms mainly depends on this characteristic. When working on parallel computers the total number of operations is no longer a deciding factor in determining the time of the problem solution. In order to effectively solve a problem, now we need to know a detailed information structure of algorithms, i.e. the information links between separate operations. The idea of the algorithm complexity has also changed. The conventional notation of algorithms, e.g. mathematical formulae, programs written in algorithmic languages, etc. does not contain explicit information about the links between the operations. Nevertheless it is very important to have such information but it may be obtained only from the conventional notation. Much attention is being given to the problem of studying the information structure of algorithms in the whole world. However, until recently there has not been found the answer to one of the fundamental questions of how the set of information links is organized. We are the first to exhaustively tackle this question in this paper for a very important class of algorithms. Before we start studying the problem we must decide on formalization of the notation of the algorithm. We consider the algorithm to be written in FORTRAN. We suppose that the control part of the program is described by a system of DO loops and conditional statements that realize branching. An arbitrary structure of loop nesting and branching is allowed. Only arithmetic statements and assignment statements are allowed as executable statements. The program may have formal parameters whose values are not initially known. These parameters are called external parameters. Let all references to the array elements, the bounds of loops, and the branching conditions be given by expressions linearly dependent on the loop parameters and the external program parameters. We assume, if necessary, that the ' Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow 117334, Russia