ТЕОРЕТИЧНИ (МАТЕМАТИЧЕСКИ) ОСНОВИ
НА КОМПЮТЪРНАТА ИНФОРМАТИКА II ЧАСТ

Димитър Петров Шишков

ДАННИ

Тип данни конкретен и абстрактен. Примитивни
и съставни типове данни. Мощност на тип данни.

Абстрактни структури за данни

ТИП ДАННИ

Конкретен тип данни (ТД) е

DT = {A, Og, D, F, R, Op, Ax}, Op R,

където А е азбука; Og множество от два вида генериращи операции с резултат в D, първични без аргументи от D, и комбинирани с аргументи от D; D множеството от данни от тип DT с определен формат F над азбуката A; F множество от правила и отношения, които определят групирането на знаковете от A в D; R релации над дадения тип данни DT; Op R множеството от операции над D; Ax правила, които описват връзките между елементите на D и между елементите на D и операциите от Op.

Абстрактен тип данни е

АDT = {D, R, Op, Ax}, Op R.

Ако Г_DT е пораждаща граматика, то

Г_DT = {A, N, P, s},

където A е множеството на терминалните символи (азбуката), N множеството на нетерминалните символи (металингвистичните променливи); P списъкът от продукциите (продукционните правила), а s е аксиомата (стартовият, началният символ). Тогава

конкретен DT = {ADT, Г_DT}.

Аксиомата (началният символ) на граматиката Г_DT е <даннаоттипDT>.

МОЩНОСТ НА ТИП ДАННИ

Мощност M(DT) на ТД DT е броят на елементите му. Ще използваме за модел следните типове:

type T = set of (1, 2, 3, 4);

REC = record i, j: integer; s: T end;

var list: array[1..max] of REC;

1.Мощност на елемент е броят на допустимите му стойности,

например M(i) = M(integer) = M()+M() = 65536.

2.Мощност на множеството s от подмножествата на тип SET с n елемента е 2ⁿ, например M(s) = 2₄ = 16.

3.Мощност на запис е произведението от мощностите на полетата в него, например M(REC) = M(i) M(j) M(s).

4.Мощност на масив, на който стойностите на всичките му елементи са инициализирани, е мощността на типа на елемент от масива на степен броя на елементите на масива (масивът може да се разглежда като запис от еднотипни елементи), например М(list) = (M(REC))^max.

5.Мощност на знаков низ с най-много n елемента. В литературата се приема, че мощността на този тип е мощността на масив от тип char с n елемента. Това погрешно схващане бе