4794

Концепция данных в программировании

Лекция

Информатика, кибернетика и программирование

Концепция данных Элементарные конструкции языка программирования: алфавит, данные, имена. Типы данных. Вычислительные структуры (многосортные алгебры) как формальные средства описания данных. Носители и сигнатуры, формы записи. Термы. Интерпретации ...

Русский

2012-11-27

80.5 KB

23 чел.

Концепция данных

Элементарные конструкции языка программирования: алфавит, данные, имена. Типы данных. Вычислительные структуры (многосортные алгебры) как формальные средства описания данных. Носители и сигнатуры, формы записи. Термы. Интерпретации как семантика вычислительных структур.

Алфавит языка Паскаль

В языке используются:

1.Латинские буквы (большие и маленькие), знак подчеркивания ’_’

2.Цифры 0,...,9

3.Математические символы +, -, *, /, <, >, =

4.Разделители: ; , “ ‘ . : ^

5.Скобки ( ) [ ] { }

6.Другие символы (используемые для печати): буквы национальных алфавитов, !, ?, \, |, ...

В различных версиях могут использоваться различные наборы символов. Сейчас широко используется набор символов кода ASCII (American Standard Code for Information Interchange). Этот код предусматривает расширения для национальных алфавитов, символов псевдографики, которые могут меняться от версии к версии.

Данные

Данные есть общее понятие для всего того, с чем оперирует ЭВМ. Языки программирования позволяют нам абстрагироваться от деталей представления данных на машинном уровне прежде всего за счет введения понятия типа данных.

В языке Паскаль представляются числа и строки.

Целые числа записываются в десятичной системе счисления: 137, -56, +26 .

Вещественные числа используют также десятичную нотацию, причем целая часть отделяется от дробной не запятой, а точкой. Для обозначения порядка числа в качестве разделителя используется буква Е. Например, -5.1Е14 означает -5.1, умноженное на 10 в степени 14 (-5,1*1014). Степени чисел могут быть и отрицательными: 6.74Е-8, -56.89Е-10.

Последовательности символов, заключенные в одиночные кавычки, называются строками. Если в строку нужно включить кавычку, то вместо нее записывают две кавычки:

‘ строка из символов ‘, ‘ апостроф ‘’ в слове ‘

Имена

Именем в языке Паскаль называется последовательность (латинских) букв, знака подчеркивания ‘_’ и цифр, начинающаяся с буквы либо со знака подчеркивания. Хотя имена могут быть сколь угодно длинными, в реализации количество значащих символов в имени может быть ограничено. В стандарте языка имена различаются по первым восьми символам. Это означает, что имена VeryLongNumber, VeryLongCardinal в стандарте языка обозначают (именуют) один и тот же объект.  Кроме того, язык не различает больших и маленьких букв. Поэтому имена Sin, SIN, sin неразличимы.

Имена используются для обозначения программ, констант, типов, переменных, процедур и функций. Например:

Pi, Сonstant - имена констант; x, y1, y2, Counter - имена переменных;

Integral, MaxMin - имена процедур; Man, Color, WeekDay - имена типов;

Некоторые имена предопределены заранее. Например:

Sin - имя для обозначения функции синус;  Read - имя для обозначения процедуры чтения;

Они называются стандартными. Все другие имена выбираются программистом по его усмотрению. Однако в целях улучшения читаемости программы рекомендуется выбирать имена, несущие информацию о поименованном объекте.

Практически все реализации языка допускают использование только латинских букв в именах, поэтому программы не так понятны неанглоязычным пользователям, как этого хотелось бы.

Стандартные простые типы данных языка Паскаль

В языке очень тщательно в соответствии с концепцией структурного программирования проработано понятие типа данных. Существуют так называемые простые (элементарные) типы, которые либо определены как стандартные, либо определяются программистом. Определен также механизм описания и использования сложных типов из более простых как из базовых.

Языки программирования позволяют нам абстрагироваться от деталей представления данных на машинном уровне прежде всего за счет введения понятия типа данных.

  •  простые (элементарные) типы либо определены как стандартные, либо определяются программистом.
  •  В ЯП определяется также механизм описания и использования структурных (составных) типов из более простых как из базовых.
  •  Абстрактные типы данных реализуются средствами ЯП как составные типы

Стандартные простые типы данных

Integer,  Real, Char,  Boolean

Простые типы, определяемые программистом 

Перечисляемый тип, Скалярный тип

Структурные типы данных  

Регулярный тип,  комбинированный тип, множественный тип,  файловый тип, ссылочный тип

В языке Паскаль определены 4 стандартных простых типа данных:

Integer   (целый);

Real   (вещественный);

Char   (символьный).

Boolean  (логический);

Для полного описания каждого типа данных, используемых в языке программирования, необходимо знать:

  1.  множество допустимых значений для данных этого типа;
  2.  допустимые операции над данными этого типа;
  3.  функции, определенные на данных этого типа или принимающие значения в этом типе;
  4.  допустимые отношения на данных этого типа.

Тип данных Integer

Значениями целого типа являются элементы зависящего от реализации подмножества (отрезка) целых чисел. Это означает, что существует стандартная константа с именем MaxInt, такая что для любого данного X типа Integer

-MaxInt < X < MaxInt

Наиболее распространенное для 16 разрядных ПЭВМ значение

MaxInt = 215 - 1 = 32767.

Операции:

* - умножение; div -  целочисленное деление; mod - остаток от целочисленного деления; + -  сложение;   -   -  вычитание;

Функции:

Abs(x) - х ;

Sqr(x) - х2;

Trunc(x) - отбрасывание дробной  части от вещественного х;

Round(x) - округление вещественного x;

Succ(x) - х + 1;

Pred(x) - х - 1;

С некоторыми другими функциями мы познакомимся позже - при определении других типов данных.

Отношения:

 < - меньше     <= - меньше или равно

 > - больше      >= - больше или равно

 = - равно       <> - неравно

Тип данных Real

Значениями вещественного типа являются элементы зависящего от реализации подмножества вещественных чисел. В TP-6 диапазон типа Real [ 2.9*10 -39 ... 1.7*10 38 ]

Операции:

*  - умножение;      /   - деление;

+  - сложение;        -   - вычитание;

Функции:

Abs(x) - модуль х;

Sqr(x) - х в квадрате;

Sqrt(x) - корень из х.

Sin(x) - sin х;

Cos(x)- cos х;

Arctan(x)- arctg х;

Ln(x)  - ln х;

Exp(x) - e х;

Отношения: такие же, как и для типа Integer.

Числовые типы Integer и Real совместимы. Это означает, что данные типа Integer могут обрабатываться как вещественные числа и результат будет иметь тип Real.

Тип данных Сhar

Значениями символьного типа являются элементы конечного и упорядоченного множества символов. Символы этого множества определяются реализацией. Они должны быть и на вводных, и на выводных устройствах. Большинство ПЭВМ поддерживает ASCII - код, поэтому в реализациях языка множество значений типа Char совпадает с некоторым расширением ASCII - символов. ASCII код каждому символу, определенному в нем, ставит в соответствие один байт.

Вне зависимости от реализации множество символов включает:

A,  B, C, ... , Z, _  (знак подчеркивания)

 1, ... , 9 - (десятичные цифры)

 Символ пробела.

Функции:

 Ord(x) - порядковый номер x.

Chr(n)- символ с порядковым номером N.

 Pred(x)- символ, предшедствующий x.   

Succ(x) - символ, следующий за x.

Отношения.

Как уже сообщалось, тип данных Сhar упорядочен. Это означает, что данные типа Сhar можно сравнивать, как и данные числовых типов, с помощью отношений:

= , <> , > , < , >= , <= .

Порядок на множестве букв латинского алфавита согласован с алфавитным, а на множестве цифр - с числовым.

Логический тип данных Boolean будет описан ниже - когда мы будем изучать понятие условия.

Тип данных Boolean 

Условия используются в программах для организации ветвлений и повторяющихся действий. Условием в языке является логическое выражение - выражение типа Boolean. Булевские значения - это логические истинностные значения: True (истина) и False (ложь).

Этот тип данных, как и другие простые типы данных, упорядочен. На нем определены функции Ord, Succ, Pred.

Таким образом , имеют место следующие соотношения :

False < True ,

Ord (False)=0,  Ord (True)=1,

Succ (False)=True,  Pred (True)=False.

На множестве < True, False > определены логические операции

Операции:

 And - логическая коньюнкция ( и )

  Or - логическая дизньюнкция ( или )

Not - логическое отрицание ( не )

Эти операции определяются следующими таблицами истинности:

                                     

And

False

True

Or

False

True

x

Not (x)

False

False

False

False

False

True

False

True

True

False

True

True

True

True

True

False

Отношения, определенные ранее для простых стандартных типов являются операциями, результат которых имеет логический тип. Иными словами, булевское значение дает любая из операций отношений :  =, < > , <= , < , > , >= , in.

Для типа Boolean определены стандартные функции, принимающие значения этого типа (логические значения):

Odd(Х) { Odd(Х) = True, если Х - целое нечетное число

 Odd(Х) = False, если Х - целое четное число}

Eoln(F) { конец строки в текстовом файле}

Eof(F) { конец файла}

Функции Eoln(F) и Eof(F) будут определены при описании файлов.

Условия можно классифицировать как простые и сложные.

Простые условия определены диаграммой:

Сложные условия конструируются из простых с помощью логических операций.

Приведем примеры простых и сложных выражений типа Boolean (условий).

Простые выражения типа Boolean (условия) :

Sin(2*x) > Ѕ, (X + Y) mod Prime = 0,

b*b > 4*a*c ,

Number div Modulo = 2, Odd(A*P + B),

Flag ;

Сложные выражения типа Boolean (условия) :

а) (а + i > в) or ( х [Index] = с )

{ Здесь а, в, с - переменные типа Real, х - массив вещественных чисел , Index - переменная типа Integer }

б) Odd (n) And (n < 10е4)

в) Eof(f) Or (f^.data = 0)            {f - файл действительных чисел}

г) Not(beta) And (gamma)   {beta и gamma - переменные типа Boolean}

д) (A > B) = (C > D)

Логические выражения преобразуются по законам логики высказываний. Например,

Not((A > 0) And (B <> 0))  <==>  Not(A > 0) Or Not(B <> 0)  <==>   (A <= 0) Or (B = 0)

Преобразования логических выражений часто приводят к уменьшению их сложности и, тем самым, оптимизации программы по времени.

Вычислительные структуры как формальные средства описания данных

Вычислительная структура ЯП состоит из семейства множеств, называемых носителями, и семейства отображений (операций, функций) между носителями.

Понятие вычислительной структуры используют для описания совокупности типов данных, определенных в ЯП, как единого целого.

Проектирование и реализация структур данных осуществляется в терминах АТД и ВС сверху-вниз, а описания – снизу вверх.

Рисунок иллюстрирует методологию проектирования и реализации структур данных для некоторой предметной области в терминах вычислительной структуры ЯП.

Задача: Построить систему визуализации хода решения задачи на построения с помощью циркуля и линейки

Пример АТД Планиметрия (лекция 1)

Примитивные типы объектов:    точка, прямая, окружность.

Имена типов (Паскаль)       Point,      Line,         Circle

Примитивные операции и заголовки функций и процедур (Паскаль):

Line: (точка, точка)  прямая

Procedure DoLine (A, B: Point; var p: Line)

Circle: (точка, точка)  окружность

Procedure DoCircle (A, B: Point; var c: Circle)

CircleRad: (точка, точка, точка)  окружность

Procedure DoCirRad (A, B, C: Point; var c: Circle)

Аналогично определяются процедуры для:

IntersectLines(прямая, прямая) точка

IntersectCircles(окружность, окружность) (точка, точка)

IntersectLineCircle(прямая, окружность) (точка, точка)

Математические определения:   Данные

Точка     (X, Y)     (X, Y)

Прямая     aX + bY = c    (a, b, c)  

Окружность  (x - X)2 + (y - Y)2 = R2 ((X, Y), R)

Определения типов (Паскаль) используемые для вычислений

Type Point = Record

      X, Y:Real

  End;

Circle = Record

      C: Point;

      R: Real

   End;

Circle = Record

      a, b, c: Real

        End;

Семейство отображений как множество определяется сигнатурой вычислительной структуры, которая содержит в качестве элементов описания вида

<имя отображения>: <список имен типов аргументов> <тип результата>

Например:

Trunc : Real Integer   >= : Real, Real Boolean

 

Наглядную иллюстрацию элемента сигнатуры дают рисунки.

Каждому элементу сигнатуры в ЯП предписана форма записи (префиксная скобочная или бесскобочная, инфиксная, постфиксная)

Семантика отображений определяет результаты (значения) соответствующих операций и функций.  

Термы. Интерпретации как семантика вычислительных структур.

Понятие терма

Термы составляются из переменных, констант, имен функций, операций в соответствии с общепринятыми математическими правилами. Точное понятие терма в языке программирования определяется в терминах вычислительных структур.

Именно:

Терм задает порядок вычисления его значения, основанный на общепринятых правилах, которые могут быть сформулированы в виде рекурсивных определений.

Sqr(sin(X)) + Sqr(cos(X)) = 1   Trunc(Abs(B - A)) + 1

Формы записи

Префиксная форма записи формулы атомарного терма имеет вид

<имя функции>(<список аргументов >)

 Например:  Sin(X),   Log(a, X),    GCD(A, B)

В математике по традиции используют инфиксную форму записи бинарных операций и порядок вычислений в бесскобочных термах. Например 

A + B  вместо  Add(A, B)    A or B  вместо  or(A, B)

A + B+C вместо (A+B)+C   A+B*C вместо A+(B*C

Специальные правила определяют семантику бесскобочного терма при помощи понятия старшинства (приоритета) бинарных операций.


Правила вычисления значений термов в языке Паскаль

Наибольший приоритет имеют функции и логическая операция not, далее следуют мультипликативные операции, аддитивные операции и отношения.

Таблица приоритетов

Функции  not.

Мультипликативные операции:  *    /    div    mod     and

Аддитивные операции:     +    -   or

Отношения:     =   <>   >   <   >=   <=    in

Операции одного приоритета вычисляются слева направо. Это соответствует группировке скобок в бесскобочном терме влево.

a + b + c = (a + b) + c,               a * b * c = (a * b) * c

Вычисление значения терма дает промежуточные результаты - данные некоторого типа, точно определенного знаком терма типами операндов (аргументов).

Любое несоответствие типа значения операнда приведет к ошибке, выявляемой компилятором при синтаксическом анализе.  

Примеры несоответствий типов

A/B div 10  (A + 1) or (B > 0)

Значение терма может быть неопределенным вследствие выхода аргументов терма за границы области определения.

Примеры неопределенностей

A/(B - B) + B  Sqrt(-1)

Точные определения семантики термов включают области определения атомарных термов

Пример

Семантика атомарных термов описывается соотношениями

Sqr(X) = X*X    Sqr(Sqrt(X)) = X  Sqrt(Sqr(X)) = Abs(X)


Выражение

  Отношение

Выражение

Логическая функция

огическое значение

Простое

условие

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

предметной области

Составные (структурные) типы данных

языка программирования

Простые типы данных

языка программирования

Вычислительные структуры ЯП

Real

Integer

Trunc

Real

Real

>=

Boolean


 

А также другие работы, которые могут Вас заинтересовать

35409. Операційна система Ms – Dos. Команди Ms – Dos 133 KB
  DOC із каталогу TEXT логічного диска D:; DEL .ВАК активного каталогу. Якщо вам потрібно вилучити всі файли із каталогу наприклад за допомогою команди DEL . Перейменовуються всі файли із заданого каталогу які підходять під шаблон заданий у першому імені файла в команді.
35412. ЭЛЕКТРОННО-ЛУЧЕВАЯ ЛИТОГРАФИЯ 331.82 KB
  Плотность тока при экспозиции составляет около 105 А см2 в случае использования фотокатодов из йодида цезия имеющего наибольший срок службы. В этом случае освещающий луч фокусируется на маске а не проходит через нее освещая ее целиком как это имеет место в проекционной системе. Ходом луча управляет специальный микропроцессор или ЭВМ. Результаты этого пооцесса получаются удовлетворительными только в том случае если отверстия в резисте имеют подтравленные стенки.
35413. Превращения энергии при свободных затухающих электромагнитных колебаниях. Функции энергии электрического и магнитного полей от времени 197.5 KB
  Основные параметры волны: амплитуда частота фаза период волновое число длина волны фазовая скорость. При распространении волны частицы среды не движутся вместе с волной а колеблются около своих положений равновесия. Волны бывают продольные когда колебания происходят вдоль линии распространения волны и поперечные когда колебания происходят поперек этой линии Поперечные волны б Продольные волны Продольные волны могут распространяться исключительно в среде тогда как поперечные и в вакууме. Часто нам приходится сталкиваться с...
35414. Животноводческая ферма 414.16 KB
  Техническое обслуживание машины и оборудования животноводческих комплексов и ферм организуется с учетом особенностей хозяйств, которые можно разделить на три группы
35415. Проектирование информационных систем в среде Rational Rose 469.5 KB
  Для успешной реализации проекта объект проектирования «Приемное отделение стационара» должен быть прежде всего адекватно реализован в программной среде Rational Rose
35416. ВЫЧИСЛЕНИЕ МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИЙ 88.5 KB
  ВАРИАНТ 13 Алгоритм: псевдокод Объявляем переменные alpha beta z1 z2; Считываем значения параметров и переводим их в радианы; Вычисление значения функций и вывод на экран. блоксхема НАЧАЛО alpha beta z1 z2 z1 = sinalpha cos2 beta alpha cosalpha sin2 beta alpha; z2 = 1 sin2 beta cos2 beta z1...