algorithm discrete programming

The real data that the program processes are integers, real numbers, symbols, and logical values. These simple data types are called basic. All data processed by a computer is stored in computer memory cells, each of which has its own address. In order not to keep track of which address this or that data will be written to, programming languages ​​use the concept of a variable , allowing you to ignore the address of a memory cell and access it using the name ( identifier).

Variable - there is a named object (memory cell) that can change its value. Name variable indicates meaning, and the method of its storage and address remain hidden from the programmer. In addition to its name and value, a variable has type, determining what information is in memory. Type variable sets:

• * the method used for recording information into memory cells;
• * the required amount of memory to store it.

The amount of memory for each type is determined so that any value from the allowed range of values ​​can be placed in it of this type. For example, the byte type can take values ​​from 0 to 255, which in binary code (255 = 11111111 2) corresponds to a memory cell 8 bits long (or 1 byte).

In the algorithms described above, all data is stored in the form of variables. For example, the instruction “Enter two numbers A, b" means the user enters the values ​​of two variables, and the instruction “K=K+1” means increasing the value of the variable K by one.

If variables are present in a program throughout the entire duration of its operation, they are called static. Variables that are created and destroyed at different stages of program execution are called dynamic.

All other data in the program, the values ​​​​of which do not change throughout its operation, are called constants or permanent. Constants, like variables, have a type. They can be indicated explicitly, for example, in the instruction “K = K + 1” 1 there is a constant, or for convenience they can be designated by identifiers: pi = 3.1415926536. Meaning only pi cannot be changed since it is a constant, not a variable.

To improve productivity and quality of work, it is necessary to have data that is as close as possible to real analogues. A data type that allows several variables to be stored together under one name is called structured. Every programming language has its own structured types. Let's consider a structure that combines elements of the same data type - an array .

Array is an ordered collection of quantities of the same type that have a common name, the elements of which are addressed (distinguished) by serial numbers (indices). As an illustration, we can imagine a cabinet containing many numbered drawers (the totality is “Box No. 1,” “Box No. 2,” “Box No. 3,” etc.; “Box” is the general name of all its elements). Access to the contents of a specific box (array element) is carried out after selecting the box by its number (index). Elements of an array in computer memory are stored nearby; single elements of a simple type do not imply such an arrangement of data in memory. Arrays differ in the number of indices that define their elements.

One-dimensional array(a cabinet of drawers in one row) assumes that each element has only one index. Examples of one-dimensional arrays are arithmetic and geometric sequences that define finite series of numbers. The number of elements in an array is called dimension. When defining a one-dimensional array, its dimension is written in parentheses next to its name. For example, if it says: “array A(10) is given,” this means that the elements are given: A R A 2 ,…, a ig . Let's consider algorithms for processing elements of one-dimensional arrays.

The elements of a one-dimensional array are entered element-by-element, in the order necessary to solve a specific problem. Typically, when you need to enter an entire array, the order in which the elements are entered is not important, and the elements are entered in ascending order of their indices.

A data type defines a set of valid values ​​and a set of valid operations.

Simple types.

Simple types are divided into ORDINAL and REAL.

1. ORDERAL TYPES , in turn, there are:

a) whole

Pascal defines 5 integer types, which are defined depending on the sign and value that the variable will take.

Type name	Length (in bytes)	Range of values
		32 768...+32 767
		2 147 483 648...+2 147 483 647

b) logical

The name of this type is BOOLEAN. Boolean values ​​can be one of the Boolean constants: TRUE (true) or FALSE (false).

c) symbolic

The name of this type is CHAR - occupies 1 byte. The value of a character type is the set of all PC characters. Each character is assigned an integer in the range 0…255. This number serves as a code for the internal representation of the symbol.

2. REAL TYPES .

Unlike ordinal types, whose values ​​are always mapped to a series of integers and are therefore represented absolutely precisely in PC, the values ​​of real types define an arbitrary number only with some finite precision depending on the internal format of the real number.

Length of numeric data type, bytes	Numeric data type name	Number of significant digits of a numeric data type	Decimal order range of a numeric data type
			2*1063 +1..+2*1063 -1

STRUCTURED TYPES

Structured data types define an ordered collection of scalar variables and are characterized by the type of their components.

Structured data types, unlike simple ones, define many complex values ​​with one common name. We can say that structural types determine a certain way of forming new types from existing ones.

There are several structuring methods. According to the method of organization and type of components in complex data types, the following varieties are distinguished: regular type (arrays); combined type (records); filetype(files); multiple type(s); string type(strings); in the Turbo Pascal language version 6.0 and older, an object type (objects) was introduced.

Unlike simple data types, structured type data is characterized by the multiplicity of elements that form this type, i.e. a variable or constant of a structured type always has multiple components. Each component, in turn, can belong to a structured type, i.e. nesting of types is possible.

1. Arrays

Arrays in Turbo Pascal are in many ways similar to similar data types in other programming languages. A distinctive feature of arrays is that all their components are data of the same type (possibly structured). These components can be easily organized and any one of them can be accessed simply by specifying a serial number.

The array description is specified as follows:

<имя типа>= array [<сп.инд.типов>] of<тип>

Here<имя типа>- correct identifier;

Array, of – reserved words(array, from);

<сп.инд.типов>- a list of one or more index types, separated by commas; square brackets framing the list are a syntax requirement;

<тип>- any type of Turbo Pascal.

Any ordinal types can be used as index types in Turbo Pascal, except LongInt and range types with the base type LongInt.

Nesting depth structured types in general, and therefore arrays, is arbitrary, therefore the number of elements in the list of type indexes (array size) is not limited, however, the total length of the internal representation of any array cannot be more than 65520 bytes.

2. Records

A record is a data structure consisting of a fixed number of components called record fields. Unlike an array, the components (fields) of a record can be various types. To make it possible to refer to one or another component of a record, the fields are named.

The structure of a post type declaration is:

< Nametype>=RECORD< joint venture. fields>END

Here<имя типа>- correct identifier;

RECORD, END – reserved words (record, end);

<сп.полей>- list of fields; is a sequence of sections of a record separated by a semicolon.

3. Sets

Sets are a set of objects of the same type that are logically connected to each other. The nature of the connections between objects is only implied by the programmer and is in no way controlled by Turbo Pascal. the number of elements included in a set can vary from 0 to 256 (a set that does not contain elements is called empty). It is the inconstancy of the number of its elements that sets differ from arrays and records.

Two sets are considered equivalent if and only if all their elements are the same, and the order of the elements of the set is indifferent. If all the elements of one set are also included in another, the first set is said to be included in the second.

The description of the set type is:

< Nametype>=SET OF< bases. type>

Here<имя типа>- correct identifier;

SET, OF – reserved words (set, of);

<баз.тип>- the base type of set elements, which can be any ordinal type except WORD, INTEGER and LONGINT.

To define a set, the so-called set constructor is used: a list of specifications of the elements of the set, separated by commas; the list is surrounded by square brackets. Element specifications can be constants or expressions of a base type, as well as a range type of the same base type.

4. Files

A file refers to either a named area external memory A PC or logical device is a potential source or receiver of information.

Any file has three characteristic features

it has a name, which allows the program to work with several files simultaneously.

it contains components of the same type. The component type can be any Turbo Pascal type, except files. In other words, you cannot create a “file of files.”

length again created file is not specified in any way when it is announced and is limited only by the capacity of external memory devices.

File type or variable file type can be set in one of three ways:

< Name>= FILE OF< type>;

< Name>=TEXT;

<имя>= FILE;

Here<имя>- file type name (correct identifier);

FILE, OF – reserved words (file, from);

TEXT – name standard type text files;

<тип>- any type of Turbo Pascal, except files.

Depending on the method of declaration, three types of files can be distinguished:

· typed files (set by the FILE OF... clause);

· text files(defined by type TEXT);

· untyped files (defined by the FILE type).

About converting Pascal's numeric data types

In Pascal, implicit (automatic) conversions of numeric data types are almost impossible. An exception is made only for the integer type, which is allowed to be used in expressions of type real. For example, if the variables are declared like this:

Var X: integer; Y: real;

then the operator

will be syntactically correct, although there is an integer expression to the right of the assignment sign and a real variable to the left, the compiler will convert numeric data types automatically. The reverse conversion automatically from the real type to the integer type is impossible in Pascal. Let's remember how many bytes are allocated for variables of type integer and real: 2 bytes of memory are allocated for the integer data type integer, and 6 bytes for real. There are two built-in functions for converting real to integer: round(x) rounds a real x to the nearest integer, trunc(x) truncates a real by discarding the fractional part.

Simple types include ordinal, real, and datetime types.

Ordinal types are different in that they each have a finite number of possible values. These values ​​can be ordered in a certain way (hence the name of the types) and, therefore, each of them can be associated with some integer - the ordinal number of the value.

Real types, strictly speaking, also have a finite number of values, which is determined by the format of the internal representation of a real number. However, the number of possible values ​​of real types is so large that it is not possible to associate an integer (its number) with each of them.

The datetime type is designed to store date and time. In fact, it uses the real format for these purposes.

Ordinal types

Ordinal types include (see Figure 1.1) integer, logical, character, enumerated, and range types. The Ord(x) function can be applied to any of them, which returns the ordinal number of the value of the expression X.

Rice. 1.1

For integer types, the function ord(x) returns the value of x itself, i.e. Ord(X) = x for x belonging to any integer type. Applying Ord(x) to boolean, character, and enumeration types produces a positive integer in the range 0 to 1 (boolean), 0 to 255 (character), 0 to 65535 (enumeration). A range type retains all the properties of the underlying ordinal type, so the result of applying the ord(x) function to it depends on the properties of that type.

You can also apply functions to ordinal types:

pred(x) - returns the previous value of the ordinal type (the value that corresponds to the ordinal number ord(x) -1, i.e. ord(pred(x)) = ord(x) - 1;

succ(x) - returns the next value of the ordinal type, which corresponds to the ordinal number ord(x) +1, i.e. ord(Succ(x)) = ord(x) + 1.

For example, if a program defines a variable

then the function PRED(c) will return the character "4", and the function SUCC(c) will return the character "6".

If we imagine any ordinal type as an ordered set of values ​​increasing from left to right and occupying a certain segment on the number axis, then the function pred(x) is not defined for the left end, and succ (x) is not defined for the right end of this segment.

Whole types. The range of possible values ​​of integer types depends on their internal representation, which can be one, two, four, or eight bytes. In table 1.1 shows the names of integer types, the length of their internal representation in bytes and the range of possible values.

Table 1.1 - Integer types

Name	Length, bytes	Range of values
		0. .. 2 147 483 647
		32 768...+32 767
		2 147 483 648...+2 147 483 647
		9*1018...+9*1018
		0. . .4 294 967 295

The LongWord and Int64 types were first introduced in version 4, but the Smallint and Cardinal types were absent from Delphi 1. The integer type for this version occupies 2 bytes and has a value range from -32768 to +32767, i.e., the same as Smallint.

When using procedures and functions with integer parameters, you should be guided by the “nesting” of types, i.e. wherever word can be used, Byte is allowed (but not vice versa), Longint “includes” Smallint, which, in turn, includes Shortint.

The list of procedures and functions applicable to integer types is given in table. 1.2. The letters b, s, w, i, l denote expressions of type Byte, Shortint, Word, Integer and Longint, respectively,

x is an expression of any of these types; the letters vb, vs, vw, vi, vl, vx denote variables of the corresponding types. An optional parameter is indicated in square brackets.

Table 1.2 - Standard procedures and functions applicable to entire types

Appeal	Result type	Action
		Returns module x
		Returns a character by its code
		Decreases the value of vx by i, and in the absence of i - by 1
		Increases the value of vx by i, and in the absence of i - by 1
		Returns the highest bow of the argument
		Returns the third byte
		Returns the low byte of the argument
		Returns True if the argument is an odd number
	Same as parameter	Returns a pseudorandom number uniformly distributed in the range 0...(w-l)
		Returns the square of the argument
		Swaps bytes in a word

When operating with integers, the result type will correspond to the type of the operands, and if the operands are of different integer types, the general type that includes both operands. For example, when working with shortint and word, the common type will be integer. In the default setting, the Delphi compiler does not produce code to check whether a value is out of range, which can lead to misunderstandings.

Logical types. Boolean types include Boolean, ByteBool, Bool, wordBool and LongBool. IN standard Pascal Only the Boolean type is defined, the remaining logical types are introduced into Object Pascal for compatibility with Windows: the Boolean and ByteBool types occupy one byte each, Bool and WordBool - 2 bytes, LongBool - 4 bytes. Boolean values ​​can be one of the pre-declared constants False or True.

Since the Boolean type is an ordinal type, it can be used in a loop statement of a countable type. In Delphi 32 for Boolean value

Ord(True) = +1, while for other types (Bool, WordBool, etc.)

Ord(True) = -1, so these kinds of operators should be used with caution! For example, for Delphi 6 version, the executable statement showMessage(" --- ") in the following for loop will never be executed:

for L:= False to True do

ShowMessage("--);

If you change the type of the loop parameter L in the previous example to Boolean, the loop will run and the message will appear on the screen twice. [For Delphi versions 1 and 2 ord (True) =+1 for any boolean type.]

Character type. The value of a character type is the set of all PC characters. Each character is assigned an integer in the range 0...255. This number serves as the code for the internal representation of the symbol; it is returned by the ord function.

For encoding in Windows, the ANSI code is used (named after the American National Standard Institute, the American standardization institute that proposed this code). The first half of PC characters with codes 0... 127 corresponds to Table 1.3. The second half of characters with codes 128...255 varies for different fonts. Standard Windows fonts Arial Cyr, Courier New Cyr and Times New Roman use the last 64 codes (from 192 to 256) to represent Cyrillic characters (without the letters “ё” and “Ё”): “A”... “Z” are encoded values ​​192..223, “a”... “i” - 224...255. The symbols “Ё” and “е” have codes 168 and 184, respectively.

Table 1.3 - Character encoding in accordance with the ANSI standard

Characters with codes 0...31 refer to service codes. If these codes are used in the program's character text, they are considered whitespace.

The char type applies relational operations, as well as built-in functions:

Сhar (в) - function of type char; converts an expression of type Byte into a character and returns it with its value;

UpCase(CH) - function of type char; returns a capital letter if сн is a lowercase Latin letter, otherwise returns the symbol сн itself (for Cyrillic, returns the original character).

Enumerated type. An enumerated type is specified by an enumeration of the values ​​it can receive. Each value is named by some identifier and is located in a list surrounded by parentheses, for example:

colors = (red, white, blue);

The use of enumerated types makes programs more visual.

The correspondence between the values ​​of an enumerated type and the ordinal numbers of these values ​​is established by the enumeration order: the first value in the list receives the ordinal number 0, the second - 1, etc. Maximum power the enumerated type has 65536 values, so the enumerated type actually defines some subset of the whole type word and can be considered as a compact declaration of a group of integer constants with values ​​0, 1, etc.

Using enumerated types increases the reliability of programs by allowing you to control the values ​​that corresponding variables receive. In Object Pascal it is allowed inverse conversion: Any expression of a Word type can be converted to a value of an enumerated type, as long as the value of the integer expression does not exceed the cardinality of that type. This conversion is achieved by using an automatically declared function with the name of the enumerated type.

Type-range. A range type is a subset of its base type, which can be any ordinal type except a range type.

A range type is defined by the boundaries of its values ​​within the base type:

<мин.знач.>..<макс.знач.>

Here<мин. знач. >- minimum value of the type-range;<макс. знач. >- its maximum value.

The range type does not have to be described in the type section, but can be specified directly when declaring the variable.

When determining a range type, you must follow the following rules:

two “..” characters are treated as one character, so spaces between them are not allowed; the left border of the range should not exceed its right border.

A range type inherits all the properties of its base type, but with the limitations of its lower power. In particular, if a variable is defined.

The Object Pascal standard library includes two functions that support working with range types:

High(x) - returns the maximum value of the range type to which variable x belongs;

Low (x) - returns the minimum value of the range type.

Real types

Unlike ordinal types, whose values ​​are always mapped to a series of integers and are therefore represented absolutely precisely in PC, the values ​​of real types define an arbitrary number only with some finite precision depending on the internal format of the real number.

Table 1.4 - Real types

IN previous versions Delphi 1...3 Real type occupied 6 bytes and had a range of values ​​from 2.9*10-39 to 1.7*1038. In versions 4 and 5, this type is equivalent to the Double type. If you want (for compatibility reasons) to use 6-byte Reals, you need to specify a compiler directive (SREALCOMPATIBILITY ON).

As can be seen from table. 1.4, a real number in Object Pascal occupies from 4 to 10 contiguous bytes and has the following structure in PC memory.

Here s is the sign digit of the number; e - exponential part; contains binary order; m is the mantissa of the number.

The mantissa m has a length from 23 (for single) to 63 (for Extended) binary digits, which ensures an accuracy of 7...8 for single and 19...20 for Extended decimal digits. The decimal point (comma) is implied before the left (most significant) digit of the mantissa, but when operating on a number, its position is shifted to the left or right in accordance with the binary order of the number stored in the exponential part, therefore operations on real numbers are called floating point (comma) arithmetic .

Note that the arithmetic coprocessor always processes numbers in the Extended format, and the three other real types in this case are obtained by simply truncating the results to the required size and are used mainly to save memory.

A special position in Object Pascal is occupied by the comp and Currency types, which are treated as real numbers with fractional parts of a fixed length: in comp the fractional part has a length of 0 digits, i.e., it is simply absent, in currency the length of the fractional part is -4 decimal places. In fact, both types define a large signed integer that stores 19...20 significant decimal digits (internally they occupy 8 contiguous bytes). At the same time, comp and currency expressions are fully compatible with any other real types: all real operations are defined on them, they can be used as arguments mathematical functions etc. The most suitable application area for these types is accounting.

Composite, or structural, data types, in contrast to simple ones, define sets of complex values ​​with one common name. We can say that structural types define a certain way of creating new data types based on existing ones. Thus, it is possible to form data structures of arbitrary complexity, thereby making it possible to achieve an adequate representation in the program of the data with which it operates.

There are several methods of structuring, each of which differs in the way it refers to individual components and, therefore, in the way it refers to the components included in the structure data. According to the method of organization and type of components in complex data types, the following varieties are distinguished:

• regular type (arrays);
• combined type (records);
• filetype(files);
• multiple type(s);
• string type(strings);
• object type (objects).

Unlike simple data types, structured type data is characterized by the multiplicity of elements that form this type, i.e. a variable or constant of a structured type always has multiple components. Each component, in turn, can belong to a structured type, i.e. nesting of types is possible.

Literature

1. Popov V.B. Pascal and Delphi. Self-instruction manual - St. Petersburg: Peter, 2004. - 544 pp.: ill.

Simple data types

Data types

general characteristics relational data model

The fundamentals of the relational data model were first outlined in an article by E. Codd in 1970. This work served as the impetus for a large number of articles and books in which the relational model received further development. The most common interpretation of the relational data model belongs to K. Date. According to Date, the relational model consists of three parts:

• Structural part.
• The whole part.
• Manipulation part.

Structural part describes what objects are considered by the relational model. It is postulated that the only data structure used in the relational model is normalized n-ary relations.

Integral part describes a special kind of constraint that must be satisfied for any relationship in any relational database. This integrity of entities And foreign key integrity .

Manipulation part describes two equivalent ways to manipulate relational data - relational algebra And relational calculus .

This chapter examines the structural part of the relational model.

Any data used in programming has its own data types.

Important! The relational model requires that the types of data used be simple.

To clarify this statement, let's consider what types of data are usually considered in programming. Typically, data types are divided into three groups:

• Simple data types.
• Structured data types.
• Reference data types.

Simple, or atomic, data types have no internal structure. This type of data is called scalars . Simple data types include the following types:

• Logical.
• String.
• Numerical.

Various programming languages ​​can expand and refine this list by adding types such as:

• Whole.
• Real.
• Date of.
• Time.
• Monetary.
• Enumerable.
• Interval.
• Etc.…

Of course, the concept of atomicity is quite relative. Thus, the string data type can be considered as a one-dimensional array of characters, and whole type data - as a set of bits. The only important thing is that when switching to such low level gets lost semantics (meaning) of data . If a string expressing, for example, the last name of an employee is decomposed into an array of characters, then the meaning of such a string as a single whole is lost.

Structured Data Types are intended for specifying complex data structures. Structured data types are constructed from constituent elements called components, which in turn may have structure. The following data types can be considered as structured data types:

• Arrays
• Records (Structures)

From a mathematical point of view, an array is a function with a finite domain. For example, consider a finite set natural numbers

called an index set. Display

from many to many real numbers specifies one-dimensional real array. The value of this function for some index value is called the array element corresponding to . Multidimensional arrays can be defined similarly.

A record (or structure) is a tuple of some Cartesian product of sets. Indeed, a record is a named, ordered set of elements, each of which belongs to a type. So the entry is an element of the set . By declaring new record types based on existing types, the user can construct arbitrarily complex data types.

What structured data types have in common is that they have internal structure , used at the same level of abstraction, as the data types themselves.

Let us explain this as follows. When working with arrays or records, you can manipulate the array or record both as a single whole (create, delete, copy entire arrays or records) and element by element. For structured data types there are special functions - type constructors, which allow you to create arrays or records from elements of simpler types.

When working with simple data types, for example, numeric ones, we manipulate them as indivisible whole objects. To "see" that a numeric data type is actually complex (a collection of bits), we need to move to a lower level of abstraction. At the program code level, this will look like assembly inserts into the code in the language high level or the use of special bitwise operations.