lekcii2 (Лекции), страница 9

Как минимум, это множество содержит операцию присваивания и отношение равенства. В общем случае операции и отношения, а также алгоритмы их выполнения могут быть заданы процедурно. Но этого вопроса мы пока касаться не будел> ~43~. Поскольку элементы перечислимого типа упорядочены и пронумерованы, .то соответствующее множество значений может быть задано отрезком или диапазоном. И наоборот, конечное упорядоченное множество подряд идущих целых чисел тоже перечислимо и мо- В.

И пусть т1юбустся всем элементам массива А дать значения соответствующих элементов массива В, т, е, переслать массив В в массив А. Д гя описания этих действий, например, на языках Си, Бейсик и Фортран придется написать оператор цикла (типа 1гОН в Паскале), предусмотрев для его организации специальную переменную (ппраме>пр цикла) и (в Фортране и Бейсике) метку конца цикла: жет быть задано отрезком 1 .. Ц Такой тип данных называется Отрезком типа или диа- пазоном, чтобы подчеркнуть его происхождение от какого-нибуды|адтипа (с>упс>ртипа). 1'.ели нумерация и порядок элементов не важны а интересно лишь их наличие или от- сутствие, то может быть введен тип данных лсноэ>сеслпоо. Он также имеет прос сую реали- зацию >'и частичнук> аппаратную поддержку) в виде битовых шкал, в которых каждый бит Отражаст наличис'.

или Отс>утс>твис; с;ОотВс>чстВу ющс'.>О элеълента, ълножес;тва.,Длин<>!Икэды равна, максимальной мощности множества. Ввиду жесткого соответствия бита и представ- ляемого им элемента множества, нумерация элементов неизбежна на. уровне внутреннего представления. Таким образом, для задания конкретного типа, мно>ксствс> программист должен указать тип его элементов, перечислимый, небольшой мощности. В современных языках программирования существуют гораздо более развитые средства поддержки мно- жеств. Все упомянутые выше типы данных: базовые (ВООК ЕА1Ч, 1ЯТЕСЕК, Р>.ЕА1> СНАЯ), тип перечисления и отрезок типа -- являются неструктурнылли (скалярныъли) >липами данных.

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

д.). Однако группа, естественно, состоит из ее членов студентов, при этом каждому студенту со>состав>лен его номер по списку, которым пользуется как сам студент (нал>1»иълер, формируя имя пользователя в системе 11Х1Х или выбирая вариант задания), так и система КАДРЫ для накопления различных сведеллий о каждом студен се с наприълер, о текущей успеваемости по предметам, об успехах и достижениях в научной работе и т. д.) Для представления студенческой грулшы в ЭВ»1 используется структурный тип дан- ных назыВаемый массиВом. Данньк> име>ющие стру'>стуру ълассиВа яВляются соволлу~пно- стьн> компонентов одного и того жс скалярного типа, причем каждый конкретный ком- понент массива может быть явно обозна лен и к каждому компоненту имеется доступ по одному или нескольким индексам, т. е.

Определена, функция. которая по зн>вленияьл соот- ветствукпцего количества индексов опредслляет адрес элемс нта массива. При этом заранее нс делается никаких предположений относительно расположения массива в памяти; оно определяется лишь функцией поиска по и>сдексл.лл. Тип каждого индекса, очнозначно ука- зываюлций жс>лаемый элемент масс;ива, ъюжет быть про>лзвольнь>ъл, но в нем Обяза.тельно должно быть определено отношение порядка лъ>исс,'рлес1, а нс ( и ), что в частности нс позволяет типу геа1 быть индексным), Рассмотрим подробнее четыре базовых типа, данных. 3.2.2 Тип логический Значениями логического типа являются Истина, Ложь и Нслопр>едслслннос>пь >изображаемые словами И, Т, огне, либо Л, Е, Га1ве и 1 ).

Цифровые изображения истинностных значений (1 или О) также могут использоваться. но пока, применяться не будут, чтобы не смешивать их с числовыми омонимаъли. К тем логичес:ким значс;ниям, которые рассматривались в математической логике (И и Л), добавлено еще одно значение — 1, присваиванио которого лк>бому объекту приводит к возникновс,ник> особой ситуации. Таким образом, значение 1 позволяет описать класс особых ситуаций, которые могут возникнуть 140 нри вычислении отношений и логических выражений в случаях, когда результат не имеет никакой осмысленной интерпретации. Неопределенное значение применяется не только в теории, но и на практике: в СУБД, удовлетворяющих стандарту К~Ь-92 (Огас!е, 1ЭВ2, Ровфгеа, МБ ЯЬ Бегат и др,), .4 обозначается словом 1~П.?ЬЬ. Функция интерпретации, связываклцая значения и изображения, в данном случае очевидна. Хотя внутримашинное представление значений может отличаться:например, в языке Си машинное слово трактуется как Ложь, если в нем все его биты нулевые, .и как Истина в противном случае.

С другой стороны, в некоторых реализациях Паскаля Исюпияа изображается единицей только в младшем разряде. Над значениями логического типа определены Ц104~) о одноместная операция - (отрицание, МЕС или 4ь); о двуместные операции й (конъюнкция, АМ), д) и Ч (дизъюнкция, ОН. или ~); о отношения = (эквиваленция, .тождественность) и ф (нетождественность, исключакь щес ИЛИ, ", ХО11).

1ак как результатом проверки отношений являются логические значения, то отношения тоже можно считать логическими операциями, не размыкающими логического типа (не выводящими за его пределы). Результаты выполнения логических операций определяются с помощью следующих таблиц: Конъюнкция Дизъюнкция Тождественность Отрицанис — И Л Л И Операпии логического типа обладают следуя)1цими свойствами. 1. Если хотя бы один операнд имеет значение 4, то и результат имеет значение 2. Если оба операнда дизьюнкции (конъюнкции) истинны (ложны), то истинен или ложен и результат, то есть Х Й Л = Х, Х Ч Х = Х.

3. Если Х истинно, а У имеет произвольное логическое значение, отличное от 4, то Х Ч У также является истинным: Х ЧУ = Х. 4. Если Х ложно, а У имеет произвольное логическое значение, отличное от 4, то Х йУ также является ложным: Х йУ = Х. 5. Дизъюнкция и конъюнкция коммутативны: Х ЧУ = У Ч Х, Х Л У = У д Х. 6. Л Ч ~Х всегда истинно, если только Х ф 7.

Х й — Х всегда ложно, если только Х ф 8. Х = Х (- Л можно заменить на Х). 141 Названные выше операции и отношения могут быть распространены и на вектора длины А' из логических значений следующим образом: кон'ьюнкции (диз'ыонкции, и т. д.) подвергав>тся значения соответствующих компонент векторов и результатом является новый вектор. Покомпонентные булевские операции подобны побитовым операциям над двоичными разрядами машинного слова, Такие поразрядные логические операции реализуются аппаратно над ма|пинными словами фиксированной длины в рстистрах. Условимся считать, что на ленте МТ значение Истина изображается буквой И, значение /Еоаюь буквой Л, .а все остальные буквы (кроме пустой ячейки) соответствуют значеникэ Неопределенвоппь.

Таким образом мы определяем множество изображений И5, векторов из логических значений длины 1 в процессоре ВООЕ (й). Алгоритмы выполнения операций и вычисления отношений процессора ВООЕ (к) можно описать диаграммами следующих машин Тьюринга, которые являются предметом практических занятий и лабораторных работ по курсу [301: Диз ьюнкция ~В (ЛийЛш2(Л)Л) = -* (Лш1ЛиьеЛи>(Л)Л), где,р(ич) = р(а.'1) Ч р(и)е), ибий,ше Е И~~.

Эта диаграмма неструктурирована: луга из ветки Л в ветку И пересекает ветку Е, что можно оправдать ее эффективностью и компа,ктностью. При построении диаграммы МТ $ь учитываются свойства 0 и 2 логических операций. Конъюнкция н (Лил Лис(Л)Л) =~* ~ЛийЛиеЛиз(Л)Л), где Р(й) = ~Р(и'1)ЫР(ше),и', ий, и2 Е Иы Отрицание [Л»>(Л)Л) =>* [Л»>Л6>1Л)Л), где р(>») = р[»>), >й„и Е И5,.

Тождественность [Л>в>Л>и21Л)Л) =~* [Л»ОЛк>2Л>й>(Л)Л), где:р[Ю) = >р(и'>) и— е р(п>2), я:, »>>,.п>э Е И5... Задание: структурировать эту диаграмму. Таким образом, вычислимость по Тьюрипгу логического типа доказана. Лекция 19 3.2.3 Тип целый Из курса алгебры известно, что множество целых чисел состоит из бесконечного числа элементов вида О, ~1, ~2,..., удовлетворяюпи>го системс аксиом и образующего алгебраическое кольцо относительно сложения и умножения. Как уже было сказано вылив, г>ри аппаратной рсализ'щии пропессора фон Неймана, мы поступились абсолютной вычислимостью в пользу практически эффективной частичной вычислимости. Это, в частности, означало, что слова машины ч>он Неймана должны иметь ограниченнук>, небольшую и ц>иксированную длину, и само число слов в памяти машины также должно быть ограничено и невелико.

Поэтому при реализации целого типа в ЭВМ диапазон значений должен быть с>граниченным отрезком числовой оси, .включаю>цим О и слегка, несимметричным (см. и. 1.б)). Несимметричность диапазона вызвана необходимостью однозначного представления нуля, который отнесен к положительным числам, что и приводит к сокращению диапазона положительных чисел на единицу. Поэтому наибольшее положительное число на единицу меньше модуля наименьшего 1прицательного,а их кОды диаметрально прОтивОпОлОжны. З~а~е~~~~~ .

)ашинного ц~~~~~ типа явлин)тся все митек)ати н)скис целые ~~~~а., заклк)- ченные между двумя фиксированными значениями М! Х и МАХ, являннцимися атрибутами конкретного целого типа. К этим значениям добавляются неопределенное значение ( Е ) и переопределенное значение( Т ).