В этом словаре представлены термины и понятия курса "Алгебраические методы в информатике", читаемого проф. Е.М. Бениаминовым студентам Отделения интеллектуальных систем в гуманитарной сфере.
Словарь доступен для чтения и поиска всем пользователям (даже не зарегистрированным в системе), а его редактирование доступно только авторам словаря.
Настоящий раздел посвящен алгебраическому моделированию абстрактных типов данных. Вводятся понятия алгебраической системы, сигнатуры, многосортной алгебры, а также абстрактного типа данных и его реализации. Определяются гомоморфизмы реализаций абстрактного типа данных. Приводятся примеры описания типов данных в виде алгебраических систем с равенствами, раскрывающими смысл операций.
В программировании понятие абстрактного типа данных является одним из основных понятий объектно-ориентированного моделирования. В основе объектно-ориентированной реализации абстрактного типа данных лежит понятие класса. Объекты классов — элементов реализаций абстрактного типа данных можно использовать точно так же, как и значения встроенных типов данных. В определение интерфейса класса входит перечисление имен операций (методов). Соотношения между операциями в программировании чаше всего не описываются, а остаются в головах программистов и выражаются в реализации методов в виде программ. Пользователи классов узнают о соотношениях между операциями в основном по метафоре, стоящей за названиями класса и именами его операций, либо по поведению объектов этих классов и из описания, содержащегося в комментариях к определению класса или в тексте Help, если этот класс системный. Ниже на примерах мы пытаемся показать, что соотношения между операциями класса выражают важную часть их смысла.В
настоящем разделе для реализаций абстрактных типов данных вводятся понятия
подалгебры и прямой суммы алгебр, доказываются некоторые теоремы о
гомоморфизмах, а также обсуждаются примеры абстрактных типов данных —
инволюция, полугруппа, моноид, группа.
В
настоящем разделе вводится важное для приложений в информатике понятие булевой
алгебры. Доказывается теорема Стоуна о каноническом представлении конечных
булевых алгебр и о представлении произвольных булевых алгебр в виде алгебры
множеств.
В настоящем разделе рассматривается некоторая теоретико-множественная конструкция для построения так называемой свободной или инициальной реализации абстрактного типа данных. Элементы этой модели представляют собой классы эквивалентных (равных) термов, равенство которых следует из системы определяющих соотношений абстрактного типа данных. Далее обсуждается понятие вычисления в инициальной реализации абстрактного типа данных.
Вычислить значение терма в инициальной модели, значит найти канонический терм, эквивалентный исходному терму. В общем случае проблема вычисления в инициальной реализации для произвольных абстрактных типов данных алгоритмически неразрешима. Но иногда вычисление может быть сведено к сходящейся системе правил переписывания термов, которую при вычислениях применяют к исходному терму. Проблемы сходимости системы правил переписывания и ее связь с системой уравнений определяющих соотношений абстрактного типа данных также обсуждаются ниже.
Для многих практических приложений достаточно ограничиться вычислениями в некотором конечном фрагменте реализации абстрактного типа данных. Примерами таких фрагментов являются машинные числа для множества целых или действительных чисел или программные реализации абстрактных типов данных.
Отделение описания абстрактного типа данных от его реализации и возможность изменения реализаций типа данного, не меняя программ, использующих этот тип данных, позволяет повышать эффективность работы всей программы за счет локальных улучшений в реализациях абстрактных типов.В данном разделе рассматривается общее определение понятия операции над типами данных в рамках алгебраического подхода к типам данных в программировании. Операция над типами данных из набора абстрактных типов данных A1, …, An в абстрактный тип данных B определяется как функция, которая по набору моделей абстрактных типов данных A1, …, An строит модель абстрактного типа данных B, при этом выполняется так называемое условие естественности — изоморфным моделям исходных абстрактных типов должны соответствовать изоморфные модели B.
Для того чтобы привести содержательные примеры операций над типами данных нам понадобятся некоторые вспомогательные средства, которые мы введем в следующем подразделе.Первоначально в теории баз данных существовали три основные модели баз данных: иерархическая, сетевая и реляционная. В настоящем разделе описываются некоторые средства моделирования баз данных реляционного типа.
Реляционный подход к моделированию баз данных на логическом уровне был введен Е.Ф. Коддом. Суть реляционного подхода к моделированию данных состоит в том, что состояние описываемого мира (или рассматриваемой его части) можно представить в виде набора отношений (таблиц), а обработка данных сводится к операциям над отношениями. Поэтому основными понятиями подхода являются понятия схемы отношения, состояния схемы отношения и операций над отношениями.
Обработка информации с точки зрения реляционной модели заключается в получении новых отношений из отношений, хранящихся в ЭВМ, с помощью точно описанных процедур, которые называются операциями над отношениями. В различных информационных системах может использоваться разный класс операций над отношениями. В традиционном подходе Е.Ф. Кодда этот класс порождается (путем композиции) операциями проекции, соединения отношений, переименования атрибутов отношений и теоретико-множественными операциями объединения, пересечения и разности над отношениями с одинаковыми наборами атрибутов.
Операции над отношениями понимаются в рассматриваемом здесь алгебраическом подходе к моделям баз данных как алгебраические операции.
Грубо говоря, под реляционной алгеброй понимается множество, замкнутое относительно объявленных операций над отношениями. Так как эти операции имеют разные области определения, то алгебраическая система получается многоосновной. Соотношения между операциями, которые выполняются на любых отношениях, называются аксиомами реляционной алгебры.
В разных информационных системах, вообще говоря, могут быть выбраны разные классы операций над отношениями, но, как правило, эти классы замкнуты относительно композиции операций и содержат ряд простых необходимых операций так, что к исследованию возникающих при моделировании таких информационных систем алгебр могут быть с успехом применены методы современной алгебры.В настоящем приложении приводятся упражнения по описанию типов данных. Многие из них сопровождаются решениями или указаниями к решениям.
Приложение
ориентировано на помощь при проведении практических занятий с использованием
настоящего учебного пособия. В нем дано большое количество примеров решения
упражнений по наименее освещенным в литературе на русском языке темам, соответствующим
первому и четвертому разделам книги. Целью практических занятий является
закрепление теоретического материала и приобретение практических навыков
построения и исследования алгебраических моделей в программировании. В
результате изучения курса студенты осваивают основные понятия универсальной
алгебры, учатся строить алгебраические модели типов данных, получают представление
об инициальных реализациях абстрактного типа данных, знакомятся с
алгебраическими моделями баз данных. Практические занятия включают в себя
разбор и обсуждение основных теоретических положений курса и соответствующих
примеров, а также решение большого количества задач, поясняющих основные
положения, в том числе с использованием компьютера. Некоторые из разобранных
здесь упражнений уже были даны в качестве заданий к разделу I.