Кандаминимум 010109 - ответы к экзамену по смежной специальности

Ссылки сюда (2) →

[на всё окно][свернуть]

Понятие программного средства и его жизненный цикл. Понятие качества ПС, критерии качества ПС

Целью программирования является описание процессов обработки данных (в дальнейшем — просто процессов). Согласно ИФИПа [1.1]: данные (data) — это представление фактов и идей в формализованном виде, пригодном для передачи и переработке в некоем процессе, а информация (information) — это смысл, который придается данным при их представлении. Обработка данных (data processing) — это выполнение систематической последовательности действий с данными. Данные представляются и хранятся на т. н. носителях данных. Совокупность носителей данных, используемых при какой-либо обработке данных, будем называть информационной средой (data medium). Набор данных, содержащихся в какой-либо момент в информационной среде, будем называть состоянием этой информационной среды. Процесс можно определить как последовательность сменяющих друг друга состояний некоторой информационной среды.

Описать процесс — это значит определить последовательность состояний заданной информационной среды. Если мы хотим, чтобы по заданному описанию требуемый процесс порождался автоматически на каком-либо компьютере, необходимо, чтобы это описание было формализованным. Такое описание называется программой. С другой стороны, программа должна быть понятной и человеку, так как и при разработке программ, и при их использовании часто приходится выяснять, какой именно процесс она порождает. Поэтому программа составляется на удобном для человека формализованном языке программирования, с которого она автоматически переводится на язык соответствующего компьютера с помощью другой программы, называемой транслятором. Человеку (программисту), прежде чем составить программу на удобном для него языке программирования, приходится проделывать большую подготовительную работу по уточнению постановки задачи, выбору метода ее решения, выяснению специфики применения требуемой программы, прояснению общей организации разрабатываемой программы и многое другое. Использование этой информации может существенно упростить задачу понимания программы человеком, поэтому весьма полезно ее как-то фиксировать в виде отдельных документов (часто не формализованных, рассчитанных только для восприятия человеком).

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

Под жизненным циклом ПС (software life cycle) понимают весь период его разработки и эксплуатации (использования), начиная от момента возникновения замысла ПС и кончая прекращением всех видов его использования [3.1-3.4]. Жизненный цикл охватывает довольно сложный процесс создания и использования ПС (software process). Этот процесс может быть организован по-разному для разных классов ПС и в зависимости от особенностей коллектива разработчиков.

В настоящее время можно выделить 5 основных подходов к организации процесса создания и использования ПС [3.5].

• Водопадный подход. При таком подходе разработка ПС состоит из цепочки этапов. На каждом этапе создаются документы, используемые на последующем этапе. В исходном документе фиксируются требования к ПС. В конце этой цепочки создаются программы, включаемые в ПС.
• Исследовательское программирование. Этот подход предполагает быструю (насколько это возможно) реализацию рабочих версий программ ПС, выполняющих лишь в первом приближении требуемые функции. После экспериментального применения реализованных программ производится их модификация с целью сделать их более полезными для пользователей. Этот процесс повторяется до тех пор, пока ПС не будет достаточно приемлемо для пользователей. Такой подход применялся на ранних этапах развития программирования, когда технологии программирования не придавали большого значения (использовалась интуитивная технология). В настоящее время этот подход применяется для разработки таких ПС, для которых пользователи не могут точно сформулировать требования (например, для разработки систем искусственного интеллекта).
• Прототипирование. Этот подход моделирует начальную фазу исследовательского программирования вплоть до создания рабочих версий программ, предназначенных для проведения экспериментов с целью установить требования к ПС. В дальнейшем должна последовать разработка ПС по установленным требованиям в рамках какого-либо другого подхода (например, водопадного).
• Формальные преобразования. Этот подход включает разработку формальных спецификаций ПС и превращение их в программы путем корректных преобразований. На этом подходе базируется компьютерная технология (CASE-технология) разработки ПС.
• Сборочное программирование. Этот подход предполагает, что ПС конструируется, главным образом, из компонент, которые уже существуют. Должно быть некоторое хранилище (библиотека) таких компонент, каждая из которых может многократно использоваться в разных ПС. Такие компоненты называются повторно используемыми (reusable). Процесс разработки ПС при данном подходе состоит скорее из сборки программ из компонент, чем из их программирования.

ЖЦ ПС: этап внешнего описания-этап конструирования-этап кодирования-этап аттестации-(конец стадии разработки)-(стадия производства программных изделий)-(стадия эксплуатации ПС с фазами применения и сопровождения)

Совокупность свойств ПС, которая образует удовлетворительное для пользователя качество ПС, зависит от условий и характера эксплуатации этого ПС, то есть от позиции, с которой должно рассматриваться качество этого ПС. Поэтому при описании качества ПС, прежде всего, должны быть фиксированы критерии отбора требуемых свойств ПС. В настоящее время критериями качества ПС (criteria of software quality) принято считать [3.6-3.10]:

• функциональность,
• надежность,
• легкость применения,
• эффективность,
• сопровождаемость,
• мобильность.

Функциональность — это способность ПС выполнять набор функций, удовлетворяющих заданным или подразумеваемым потребностям пользователей. Набор указанных функций определяется во внешнем описании ПС.

Надежность подробно обсуждалась в первой лекции.

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

Эффективность — это отношение уровня услуг, предоставляемых ПС пользователю при заданных условиях, к объему используемых ресурсов.

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

Мобильность — это способность ПС быть перенесенным из одной среды (окружения) в другую, в частности, с одного компьютера на другой.

В технике известны четыре подхода обеспечению надежности [3.11]:

• предупреждение ошибок;
• самообнаружение ошибок;
• самоисправление ошибок;
• обеспечение устойчивости к ошибкам.

Принципы модульного программирования

Приступая к разработке каждой программы ПС, следует иметь ввиду, что она, как правило, является большой системой, поэтому мы должны принять меры для ее упрощения. Для этого такую программу разрабатывают по частям, которые называются программными модулями [7.1, 7.2]. А сам такой метод разработки программ называют модульным программированием [7.3]. Программный модуль — это любой фрагмент описания процесса, оформляемый как самостоятельный программный продукт, пригодный для использования в описаниях процесса.

Не всякий программный модуль способствует упрощению программы [7.2]. Выделить хороший с этой точки зрения модуль является серьезной творческой задачей. Для оценки приемлемости выделенного модуля используются некоторые критерии. Так, Хольт [7.4] предложил следующие два общих таких критерия:

• хороший модуль снаружи проще, чем внутри;
• хороший модуль проще использовать, чем построить.

Майерс [7.5] предлагает для оценки приемлемости программного модуля использовать более конструктивные его характеристики:

• размер модуля,
• прочность модуля,
• сцепление с другими модулями,
• рутинность модуля (независимость от предыстории обращений к нему).

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

Прочность модуля — это мера его внутренних связей. Чем выше прочность модуля, тем больше связей он может спрятать от внешней по отношению к нему части программы и, следовательно, тем больший вклад в упрощение программы он может внести. Для оценки степени прочности модуля Майерс [7.5] предлагает упорядоченный по степени прочности набор из семи классов модулей. Самой слабой степенью прочности обладает модуль, прочный по совпадению. Это такой модуль, между элементами которого нет осмысленных связей. Такой модуль может быть выделен, например, при обнаружении в разных местах программы повторения одной и той же последовательности операторов, которая и оформляется в отдельный модуль. Необходимость изменения этой последовательности в одном из контекстов может привести к изменению этого модуля, что может сделать его использование в других контекстах ошибочным. Такой класс программных модулей не рекомендуется для использования. Вообще говоря, предложенная Майерсом упорядоченность по степени прочности классов модулей не бесспорна. Однако, это не очень существенно, так как только два высших по прочности класса модулей рекомендуются для использования. Эти классы мы и рассмотрим подробнее.

Функционально прочный модуль — это модуль, выполняющий (реализующий) одну какую-либо определенную функцию. При реализации этой функции такой модуль может использовать и другие модули. Такой класс программных модулей рекомендуется для использования.

Информационно прочный модуль — это модуль, выполняющий (реализующий) несколько операций (функций) над одной и той же структурой данных (информационным объектом), которая считается неизвестной вне этого модуля. Для каждой из этих операций в таком модуле имеется свой вход со своей формой обращения к нему. Такой класс следует рассматривать как класс программных модулей с высшей степенью прочности. Информационно прочный модуль может реализовывать, например, абстрактный тип данных.

В модульных языках программирования как минимум имеются средства для задания функционально прочных модулей (например, модуль типа FUNCTION в языке ФОРТРАН). Средства же для задания информационно прочных модулей в ранних языках программирования отсутствовали. Эти средства появились только в более поздних языках. Так в языке программирования Ада средством задания информационно прочного модуля является пакет [7.6].

Сцепление модуля — это мера его зависимости по данным от других модулей. Характеризуется способом передачи данных. Чем слабее сцепление модуля с другими модулями, тем сильнее его независимость от других модулей. Для оценки степени сцепления Майерс предлагает [7.5] упорядоченный набор из шести видов сцепления модулей. Худшим видом сцепления модулей является сцепление по содержимому. Таким является сцепление двух модулей, когда один из них имеет прямые ссылки на содержимое другого модуля (например, на константу, содержащуюся в другом модуле). Такое сцепление модулей недопустимо. Не рекомендуется использовать также сцепление по общей области — это такое сцепление модулей, когда несколько модулей используют одну и ту же область памяти. Такой вид сцепления модулей реализуется, например, при программировании на языке ФОРТРАН с использованием блоков COMMON. Единственным видом сцепления модулей, который рекомендуется для использования современной технологией программирования, является параметрическое сцепление (сцепление по данным по Майерсу [7.5]) — это случай, когда данные передаются модулю либо при обращении к нему как значения его параметров, либо как результат его обращения к другому модулю для вычисления некоторой функции. Такой вид сцепления модулей реализуется на языках программирования при использовании обращений к процедурам (функциям).

Рутинность модуля — это его независимость от предыстории обращений к нему. Модуль будем называть рутинным, если результат (эффект) обращения к нему зависит только от значений его параметров (и не зависит от предыстории обращений к нему). Модуль будем называть зависящим от предыстории, если результат (эффект) обращения к нему зависит от внутреннего состояния этого модуля, изменяемого в результате предыдущих обращений к нему. Майерс [7.5] не рекомендует использовать зависящие от предыстории (непредсказуемые) модули, так как они провоцируют появление в программах хитрых (неуловимых) ошибок. Однако такая рекомендация является неконструктивной, так как во многих случаях именно зависящий от предыстории модуль является лучшей реализаций информационно прочного модуля. Поэтому более приемлема следующая (более осторожная) рекомендация:

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

В процессе разработки программы ее модульная структура может по-разному формироваться и использоваться для определения порядка программирования и отладки модулей, указанных в этой структуре. Поэтому можно говорить о разных методах разработки структуры программы. Обычно в литературе обсуждаются два метода [7.1, 7.7]: метод восходящей разработки и метод нисходящей разработки.

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

Метод нисходящей разработки заключается в следующем. Как и в предыдущем методе сначала строится модульная структура программы в виде дерева. Затем поочередно программируются модули программы, начиная с модуля самого верхнего уровня (головного), переходя к программированию какого-либо другого модуля только в том случае, если уже запрограммирован модуль, который к нему обращается. После того, как все модули программы запрограммированы, производится их поочередное тестирование и отладка в таком же (нисходящем) порядке. При этом первым тестируется головной модуль программы, который представляет всю тестируемую программу и поэтому тестируется при «естественном» состоянии информационной среды, при котором начинает выполняться эта программа. При этом те модули, к которым может обращаться головной, заменяются их имитаторами (так называемыми заглушками [7.5]). Каждый имитатор модуля представляется весьма простым программным фрагментом, который, в основном, сигнализирует о самом факте обращения к имитируемому модулю, производит необходимую для правильной работы программы обработку значений его входных параметров (иногда с их распечаткой) и выдает, если это необходимо, заранее запасенный подходящий результат. После завершения тестирования и отладки головного и любого последующего модуля производится переход к тестированию одного из модулей, которые в данный момент представлены имитаторами, если таковые имеются. Для этого имитатор выбранного для тестирования модуля заменяется самим этим модулем и, кроме того, добавляются имитаторы тех модулей, к которым может обращаться выбранный для тестирования модуль. При этом каждый такой модуль будет тестироваться при «естественных» состояниях информационной среды, возникающих к моменту обращения к этому модулю при выполнении тестируемой программы. Таким образом, большой объем «отладочного» программирования при восходящем тестировании заменяется программированием достаточно простых имитаторов используемых в программе модулей. Кроме того, имитаторы удобно использовать для того, чтобы подыгрывать процессу подбора тестов путем задания нужных результатов, выдаваемых имитаторами. При таком порядке разработки программы вся необходимая глобальная информация формируется своевременно, то есть ликвидируется весьма неприятный источник просчетов при программировании модулей. Некоторым недостатком нисходящей разработки, приводящим к определенным затруднениям при ее применении, является необходимость абстрагироваться от базовых возможностей используемого языка программирования, выдумывая абстрактные операции, которые позже нужно будет реализовать с помощью выделенных в программе модулей.

Конструктивный подход к разработке программы представляет собой модификацию нисходящей разработки, при которой модульная древовидная структура программы формируется в процессе программирования модулей. Разработка программы при конструктивном подходе начинается с программирования головного модуля, исходя из спецификации программы в целом. При этом спецификация программы принимается в качестве спецификации ее головного модуля, который полностью берет на себя ответственность за выполнение функций программы. В процессе программирования головного модуля, в случае, если эта программа достаточно большая, выделяются подзадачи (внутренние функции), в терминах которых программируется головной модуль. Это означает, что для каждой выделяемой подзадачи (функции) создается спецификация реализующего ее фрагмента программы, который в дальнейшем может быть представлен некоторым поддеревом модулей. Важно заметить, что здесь также ответственность за выполнение выделенной функции несет головной (может быть, и единственный) модуль этого поддерева, так что спецификация выделенной функции является одновременно и спецификацией головного модуля этого поддерева. В головном модуле программы для обращения к выделенной функции строится обращение к головному модулю указанного поддерева в соответствии с созданной его спецификацией. Таким образом, на первом шаге разработки программы (при программировании ее головного модуля) формируется верхняя начальная часть дерева.

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

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

Структурное программирование и пошаговая детализация

Структурное программирование

Также см. rupedia:Структурное программирование.

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

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

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

Структурное программирование иногда называют еще «программированием без GO TO». Однако дело здесь не в операторе GO TO, а в его беспорядочном использовании. Очень часто при воплощении структурного программирования на некоторых языках программирования (например, на ФОРТРАНе) оператор перехода (GO TO) используется для реализации структурных конструкций, не снижая основных достоинств структурного программирования. Запутывают программу как раз «неструктурные» операторы перехода, особенно переход на оператор, расположенный в тексте модуля выше (раньше) выполняемого оператора перехода. Тем не менее, попытка избежать оператора перехода в некоторых простых случаях может привести к слишком громоздким структурированным программам, что не улучшает их ясность и содержит опасность появления в тексте модуля дополнительных ошибок. Поэтому можно рекомендовать избегать употребления оператора перехода всюду, где это возможно, но не ценой ясности программы.

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

Пошаговая детализация

Структурное программирование дает рекомендации о том, каким должен быть текст модуля. Возникает вопрос, как должен действовать программист, чтобы построить такой текст. Часто программирование модуля начинают с построения его блок-схемы, описывающей в общих чертах логику его работы. Однако современная технология программирования не рекомендует этого делать без подходящей компьютерной поддержки. Хотя блок-схемы позволяют весьма наглядно представить логику работы модуля, при их ручном кодировании на языке программирования возникает весьма специфический источник ошибок: отображение существенно двумерных структур, какими являются блок-схемы, на линейный текст, представляющий модуль, содержит опасность искажения логики работы модуля, тем более, что психологически довольно трудно сохранить высокий уровень внимания при повторном ее рассмотрении. Исключением может быть случай, когда для построения блок-схем используется графический редактор и они формализованы настолько, что по ним автоматически генерируется текст на языке программирования.

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

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

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

• Начало модуля на базовом языке, то есть первое предложение или заголовок (спецификацию) этого модуля.
• Раздел (совокупность) описаний на базовом языке, причем вместо описаний процедур и функций, а только их внешнее оформление.
• Неформальное обозначение последовательности операторов тела модуля как одного обобщенного оператора, а также неформальное обозначение тела каждого описания процедуры или функции как одного обобщенного оператора;
• Последнее предложение (конец) модуля на базовом языке.

Неформальное обозначение обобщенного оператора на псевдокоде производится на естественном языке произвольным предложением, раскрывающим в общих чертах его содержание. Единственным формальным требованием к оформлению такого обозначения является следующее: это предложение должно занимать целиком одно или несколько графических (печатных) строк и завершаться точкой (или каким-либо другим знаком, специально выделенным для этого).

Базисные типы данных в традиционных языках программирования

Среди ада-объектов можно выделить объекты данных (то есть объекты, которым разрешено играть роль данных по отношению к каким-либо операциям). Каждый объект данных в Аде характеризуется определенным типом. Своеобразие этого языка в значительной степени связано именно с системой типов. Для тех, кто работал только с Фортраном, Алголом и Бейсиком, многое в этой системе окажется совершенно незнакомым. В частности, возможность определять новые типы, отражающие особенности решаемой задачи. Для освоивших Паскаль адовские типы привычнее. По сравнению с Паскалем система адовских типов полнее и строже, лучше отвечает своему назначению.

Тип — важнейшая компонента аппарата прогнозирования-контроля. Приписывая объекту данных определенный тип, ограничивают его возможное поведение. С другой стороны, зная тип, получают возможность это поведение контролировать. Наконец, зная ограничения на возможное поведение, можно рационально выделять память и другие ресурсы. С типом в Аде связывают три основных ограничения:

Во-первых, тип ограничивает область значений объекта; во-вторых, набор операций, в которых объекту разрешено фигурировать; в-третьих, набор допустимых для него ролей в этих операциях (скажем, в качестве второго операнда, результата и т. п.).

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

Дадим краткое введение в каждую из категорий типов.

Скалярные типы

Когда определяют перечисляемый тип, явно указывают перечень лексем, которые и составляют область возможных значений объектов вводимого типа. Такой перечень может быть списком дней недели (понедельник, вторник, среда, четверг, пятница, суббота, воскресенье), списком символов некоторого алфавита (`A',`B',…,`Z') и т. п. Перечисляемые типы избавляют программиста от необходимости кодировать содержательные объекты целыми числами. Перечисляемые типы BOOLEAN (логический) и CHARACTER (символьный) считаются предопределенными, то есть встроенными в язык и действующими без предварительного явного объявления в программе. Набор символов типа CHARACTER соответствует алфавиту ASCII — американскому стандарту на коды символов.

Числовые типы обеспечивают точные и приближенные вычисления. В точных вычислениях пользуются целыми типами. Область возможных значений для таких типов — конечный диапазон целых чисел. В приближенных вычислениях пользуются либо абсолютными типами (для них задается абсолютная допустимая погрешность), либо относительными типами (задается относительная погрешность). Абсолютная погрешность задается явно и называется дельтой, относительная погрешность вычисляется по заданному допустимому количеству значащих цифр в представлении числа. Подразумевается, что абсолютные типы будут представлены машинной арифметикой с фиксированной точкой (запятой), а относительные — с плавающей. Типы INTEGER (целый), FLOAT (плавающий), и DURATION (временные задержки для управления задачами) считаются предопределенными.

Составные типы

Скалярные типы (и перечисляемые, и числовые) выделяются тем, что объекты этих типов считаются атомарными (не имеющими составляющих). Составные типы, в отличие от скалярных, позволяют определять структурированные объекты (массивы и записи). Массивы служат значениями регулярных типов — компоненты массивов доступны по индексам. «Регулярность» массивов проявляется в том, что все компоненты должны быть одного типа. Записи (структуры) служат значениями комбинированных типов — их компоненты могут быть различных типов; компоненты записей доступны по именам-селекторам. Имена компонент одной и той же записи должны быть различны; компоненты называются также полями записи.

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

Ссылочные типы

Если структура объектов составных типов (в случае вариантных типов — все варианты такой структуры) фиксируется статически (то есть до начала выполнения программы), то ссылочные типы позволяют создавать и связывать объекты динамически (при исполнении программы, точнее, при исполнении генераторов). Тем самым появляется возможность динамически создавать сколь угодно сложные конгломераты объектов. Генератор создает объект указанного (статически известного) типа и обеспечивает доступ к вновь созданному объекту через переменную соответствующего ссылочного типа. Передавая (присваивая) ссылки, можно организовать произвольные структуры. Важно, что и элементы, и связи в таких динамических структурах можно менять при исполнении программы.

Приватные типы

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

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

Понятие операционной системы (ОС). Основные концепции современных ОС (Unix, Windows NT)

Осторожно! Не очень профессиональная лажа! Взято из методички для подготовки к гос.экзамену. Также см. rupedia:Операционная система, местами там более вменяемо.

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

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

Наиболее известными в настоящее время являются следую­щие ОС: MS DOS, Windows 95, Windows 98, Windows 2000, Windows NT, UNIX, QNX, Linux, Solaris, OS/2, MacOS.

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

Ядро ОС — программы, непосредственно обеспечивающие разделение вычислительных ресурсов и управление ими. Ядро обыч­но является резидентной частью ОС. Ядро работает в режиме ОС, или в привилегированном режиме.

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

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

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

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

По способам организации размещения файлов во внешнем запоминающем устройстве (ВЗУ) выделяются файловые системы с одноуровневой организацией файлов в виде непрерывных сегмен­тов, файловые системы с блочной организацией файлов и иерархи­ческие файловые системы.

При одноуровневой организации файлов в виде непре­рывных сегментов в пределах пространства ВЗУ выделяется неко­торая область для хранения данных, которая называется каталогом. Каталог имеет следующую структуру:

Имя

Начальный блок

Конечный блок

«Начальный блок» ссылается на некоторый относительный адрес пространства ВЗУ, с которого начинается файл с заданным именем. «Конечный блок» определяет последний блок данного фай­ла. Функция открытия файла сводится к нахождению в каталоге име­ни файла и определении его начала и конца. Это действие очень простое. Если создается новый файл, то он записывается на свобод­ное место. Чтение происходит также достаточно просто. Проблемы возникают, когда в файл нужно записать дополнительную информа­цию, а свободного пространства за этим файлом нет. В этом случае система может запустить некий процесс, который перенесет этот файл в другое место памяти и добавит нужную информацию (а это достаточно сложно), а может просто отказаться произвести запись в файл. Кроме того, при долговременной работе такой файловой сис­темы на диске случается фрагментация (ситуация, когда есть сво­бодные фрагменты памяти, но среди них нет такого, куда можно было бы разместить файл). Борьба с фрагментацией также достаточ­но сложна и опасна для такой организации файловой системы, кото­рая практически пригодна лишь для однопользовательской операци­онной системы.

В файловой системе с блочной организацией файлов пространство ВЗУ разделено на блоки. В такой файловой системе распределение информации происходит аналогично распределению информации о процессе в системе со страничной организацией опе­ративной памяти. В общем случае, с каждым именем файла связан набор номеров блоков устройства, в которых размещены данные этого файла. Причем, номера этих блоков имеют произвольный порядок, то есть блоки могут быть разбросаны по всему устройству. При такой организации нет фрагментации, хотя могут быть потери из-за хранения информации порциями, кратными целому блоку.

В файловых системах с блочной организацией файлов с ка­ждым файлом связаны имя файла и имя пользователя (по ним про­исходит доступ к файлу). В таких системах требуется уникальность имен лишь среди файлов одного пользователя. При этом файлы объ­единены в каталоги с табличной структурой, где i-тая строка соот­ветствует i-тому блоку файловой системы (занятому или свободно­му). Если блок занят, то в соответствующей строке указывается имя файла (либо ссылка на него) и имя пользователя (а может быть и еще какая-то дополнительная информация).

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

В иерархической файловой системе все файлы объедине­ны в структуру, которая называется деревом. В корне дерева нахо­дится корень файловой системы. Если узел дерева является листом, то это отдельный файл (либо файл-каталог в случае пустого катало­га). Узлы дерева, отличные от листа, являются файлами-каталогами. Именование файлов в такой иерархической файловой системе может происходить как относительно ближайшего каталога (на одном уровне имена не могут повторяться), так и с использованием полного имени файла, которое составляется из всех имен каталогов, которые находятся на пути от корня файловой системы к конкретному файлу. Полные имена файлов есть пути, а в дереве от корня до любого узла существует единственный путь, следовательно, нет проблем с уни­фикацией имен, то есть иерархическая структура файловой системы дос­таточно удобна для организации многопользовательской работы. Кроме того, такая система может очень просто наращиваться.

Основные функции ОС:

• управление использованием времени центрального процессора (или нескольких процессоров в много­процессорных системах),
• управление «подкачкой» и буфером ввода процес­сов,
• управление разделяемыми ресурсами (в частности, сетевым взаимодействием компьютеров),
• обработка прерываний,
• защита ресурсов и установка ограничений на ис­пользование ресурсов,
• вызов специальных обслуживающих программ, буферизация ввода/вывода.

Управление использованием времени центрального процессора

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

Пакетные ОС

Пусть есть некоторое количество счетных задач, они требуют большого объема вычислений и мало обращаются к внешним устройствам. Эти задачи должны выполняться в одной вычислительной системе. В такой ситуации критерием эффективности работы вычислительной системы является степень загрузки ЦП. Если он мало простаивает, то система работает эффективно. Этого можно добиться с использованием соответствующего алгоритма планирования, который заключается в следующем. Запускается некоторый набор задач в режиме мультипрограммирования. Алгоритм планирования времени ЦП в этом случае будет следующий: если ЦП выделен одному из процессов, то этот процесс будет занимать ЦП до наступления одной из следующих ситуаций:

• обращение к внешнему устройству.
• завершение процесса.
• зафиксированный факт зацикливания процесса.

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

ОС разделения времени

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

В системе используется некоторый параметр Δt — квант вре­мени. Все множество процессов, которое находится в мультипро­граммной обработке, подразделяется на два подмножества. Первое подмножество составляют те процессы, которые еще не готовы к продолжению выполнения: например, те процессы, которые заказа­ли себе обмен и ждут его результатов. Второе подмножество — про­цессы, которые готовы к выполнению. Работа будет осуществляться следующим образом. Тот процесс, который в данный момент време­ни занимает ЦП, будет владеть им до наступления одного из сле­дующих событий:

• обращение с заказом на обмен,
• завершение процесса,
• исчерпание выделенного данному процессу кванта времени Δt.

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

ОС реального времени

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

Смешанные ОС

Реально, большинство современных ОС являются сме­шанными системами, то есть у них присутствует в элементах планиро­вания использования ЦП как алгоритмы, позволяющие управлять счетными задачами, так и алгоритмы, позволяющие управлять инте­рактивными задачами либо задачами отладочными, для которых надо немного времени ЦП.

Примером такой организации планирования ЦП может быть следующая схема. Планировщик построен по двухуровневой схеме. Мы считаем, что множество задач может содержать, предпо­ложим, счетные задачи и интерактивные задачи. Первый уровень определяет приоритет между двумя классами задач и либо отдает ЦП сначала счетной задаче, либо интерактивной задаче. А второй уровень определяет то, о чем мы говорили перед этим, то есть как вы­брать задачу в пределах одного класса и как ее прервать. Такая сме­шанная система может работать следующим образом. Первый уро­вень планирования будет работать по такому принципу: если в дан­ный момент нет ни одной интерактивной задачи, готовой к выпол­нению (а это вполне реальная ситуация, если пользователи занима­ются редактированием текста), то ЦП передается счетным задачам, но добавляется одно условие: как только появляется хотя бы одна интерактивная задача, счетная задача прерывается и управление пе­редается блоку интерактивных задач. Это то, что касается первой функции управления процессами.

Управление подкачкой и буфером ввода.

Пусть большое количество людей сидит за компьютерами, и все одновременно запустили какие-то процессы. Вычислительная система не может принять для работы в мультипрограммном режиме все задачи — это слишком много. В этом случае образуется буфер ввода задач или буфер ввода процессов, то есть буфер, в котором аккумулируются те процессы, которые ожидают начала своей обра­ботки процессором. Возникает проблема очередности выбора про­цессов из этого буфера для начала обработки. Это задача планирова­ния буфера.

Задача планирования «подкачки» возникает тогда, когда процессор выполняет сразу несколько программ, и все они целиком не помещаются в оперативной памяти. В этом случае для продолже­ния вычислений время от времени может быть необходимо какие-то из обрабатываемых задач (или их фрагменты) откачивать на внеш­нее запоминающее устройство, а какие-то подкачивать в оператив­ную память.

Для решения задач планирования буфера ввода и «подкач­ки» также нужны алгоритмы планирования, но они не столь принци­пиальные, как при планировании времени ЦП.

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

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

Управление разделяемыми ресурсами.

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

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

Обработка прерываний.

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

В момент возникновения прерывания действия аппаратуры вычислительной системы следующие:

• В некоторые специальные регистры аппаратно заносит­ся (сохраняется) информация о выполняемой в данный момент программе. Это минимальная информация, не­обходимая для начала обработки прерывания. Обычно в этот набор данных входит счетчик команд, регистр результата, указатель стека и несколько регистров об­щего назначения. Происходит так называемое малое «упрятывание».
• В специальный управляющий регистр, иногда называе­мым регистром прерываний, помещается код возник­шего прерывания.
• Запускается программа обработки прерываний, входя­щая в состав операционной системы. Эта программа производит анализ причины прерывания. Если преры­вание было фатальным (деление на ноль, например), то ОС прекращает выполнение программы, в которой воз­никло данное прерывание. Если же прерывание не фа­тальное, производится дополнительный анализ ситуа­ции и делается вывод о том, можно ли оперативно об­работать прерывание. Пример прерывания, которое всегда можно обработать оперативно — прерывание по таймеру. А прерывание, связанное, например, с прихо­дом информации по линии связи, нельзя обработать оперативно, так как предварительно надо подкачать про­грамму ОС, которая займется обработкой этого преры­вания. При этом сначала происходит полное «упряты­вание»: все регистры сохраняются в таблицах системы (а не в аппаратных регистрах, как раньше) и фиксиру­ется то, что некоторые фрагменты программы, находя­щиеся в оперативной памяти, могут быть перенесены (при необходимости) на внешнее устройство, а затем производится обработка прерывания и возврат из пре­рывания.

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

Защита ресурсов и установка ограничений на использо­вание ресурсов.

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

Для вычислительных систем со страничной организацией памяти механизм защиты памяти может быть устроен, например, следующим образом: в таблице приписки, в которой отражено соот­ветствие между физической и виртуальной памятью, в строках, от­носящихся к страницам, не принадлежащим данной программе или еще не загруженным в оперативную память, находится код меньше нуля. При попытке обратиться к такой странице в системе возникает прерывание по защите памяти. Обрабатывая это прерывание, ОС про­веряет, действительно ли этой страницы памяти у данной програм­мы нет, и, если эта страница чужая, то ОС прекращает выполнение данного процесса с диагностикой обращения в чужую память. Если же какие то страницы еще не загружены в память, то ОС игнорирует прерывание, так как ошибки нет.

Персонификация пользователей

Современные многопользовательские ОС также решают за­дачу персонификации пользователей.

Персонификация — это возможность операционной системы идентифицировать конкретного пользователя и в соответствии с этим принимать те или иные действия, в частности, по защите дан­ных.

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

Буферизация ввода/вывода

По аналогии со способами борьбы с разницей в скорости доступа к различным компонентам вычислительной системы опера­ционная система вводит в своих пределах программную буфериза­цию, которая также решает проблемы сглаживания времени доступа и проблемы синхронизации в целом. Сглаживание проблем, связан­ных с временем доступа, заключается в том, что практически каждая операционная система имеет КЭШ-буфера, которые аккумулируют обращения (образуют их очередь) к внешнему запоминающему уст­ройству (ВЗУ) аналогично аппаратной буферизации при работе с оперативной памятью. Это позволяет существенно оптимизировать операционную систему. Признаком наличия такой буферизации яв­ляется требование завершить выполнение операционной системы перед выключением машины. Степень этой буферизации определяет реальную эффективность системы.

Принципы объектно-ориентированного программирования

Определение. Объектно-ориентированное программирование — это методология программирования, которая основана на представлении программы в виде совокупности объектов, каждый из которых является реализацией определенного класса, а классы образуют иерархию на принципах наследования.

Ключевыми отличиями ООП от других методологий программирования являются следующие отличия:

• ООП использует в качестве элементов конструкции объекты, а не алгоритмы
• Каждый объект является реализацией какого-либо определенного типа (класса)
• Классы организованы иерархически

При несоблюдении хотя бы одного из указанных требований программа перестает быть ОО. (В частности при нарушении 3 имеем программирование на основе Абстрактных Типов Данных)

Определение. Язык программирования называется объектно-ориентированным тогда и только тогда, когда выполнены следующие условия:

• Имеется поддержка объектов в виде абстракции данных имеющих интерфейсную часть в виде поименованных операций и защищенную область локальных данных
• Объекты относятся к соответствующим типам (классам)
• Классы могут наследовать атрибуты и методы от суперклассов (базовых классов)
• Имеется поддержка полиморфных функций

Объектно-ориентированный подход основывается на следующих элементах:

• Абстрагирование
• Инкапсуляция (ограничение доступа)
• Иерархия (в частности наследование)
• Полиморфизм

Абстрагирование

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

Абстрагирование концентрирует внимание на внешних особенностях объекта и позволяет отделить самые существенные особенности поведения от деталей их осуществления.

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

Инкапсуляция (ограничение доступа)

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

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

Абстрагирование и ограничение доступа дополняют друг друга: абстрагирование фокусирует внимание на внешних особенностях объекта, а ограничение доступа не позволяет объектам-пользователям различать внутреннее устройство объекта.

В описании класса можно выделить две части:

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

Изменение реализации, вообще говоря, не влечет за собой изменение интерфейса.

Иерархия

Определение. Иерархия в ОО — это ранжированная или упорядоченная иерархия абстракций.

Основными видами иерархических структур применительно к сложным системам являются структура классов (иерархия по номенклатуре) и структура объектов (иерархия по составу).

Примеры иерархий:

• Наследование означает такое соотношение между классами, когда один класс использует структурную или функциональную часть одного или нескольких других классов (соответственно простое или множественное наследование). Иными словами, наследование — такая иерархия абстракций, в которой подклассы наследуют строение от одного или нескольких суперклассов. (Иерархия обобщение — специализация)
• Агрегирование (отношение по составу). Объект состоит из подобъектов.

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

• Обособленную (private) — видимая только для самого класса
• Защищенную (protected) — видимую также и для подклассов
• Общедоступную (public) — видимую для всех

Полиморфизм

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

Полиморфизм может быть статическим и динамическим:

• Статический — перекрытие операций (Ада, C++,Object Pascal).
• Динамический — механизм виртуальных функций

Виртуальные функции являются примером полиморфных функций. Виртуальная функция может быть переопределена в производном классе, следовательно ее реализация зависит от всей последовательности методических описаний и наследственной иерархии. Какая именно из виртуальных функций будет вызвана — зависит от динамического типа объекта и определяется в момент обращения к виртуальной функции. Для этого используется таблица виртуальных функций, определенная для каждого класса.

Дополнительные возможности ОО языков

Некоторые языки позволяют определять несколько специальных методов класса:

• Конструктор — специальная процедура класса для создания и/или инициализации начального состояния объекта. В частности, конструктор может инициализировать таблицу виртуальных функций.
• Деструктор — специальная процедура класса, которая делает состояние объекта неопределенным и (или) ликвидирует сам объект.

Некоторые преимущества ОО подхода:

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

Основные понятия реляционной модели данных. Понятие о языке SQL

Также см. rupedia:Реляционная модель данных, rupedia:Нормальная форма, rupedia:SQL.

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

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

Реляционная модель является теоретической основой не только широко распространенных на сегодняшний день реляционных баз данных и соответствующих СУБД, но и всей области баз данных. Впервые принципы реляционной модели были изложены Е. Ф. Коддом в 1969-70 годах. Позднее в 70-х годах были получены основные теоретические результаты в этой области и появились первые прототипы реляционных СУБД. Наиболее бурное развитие области пришлось на 80-е годы, и это привело к тому, что уже к середине 80-х годов реляционные системы практически вытеснили с мирового рынка ранние СУБД и остаются до сих пор наиболее распространенными. Причиной такой популярности реляционных систем по сравнению с другими СУБД являются такие достоинства реляционного подхода к организации баз данных как:

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

Основные термины

Реляционный подход к организации баз данных базируется на понятии отношения, и, собственно, само название подхода (а также соответствующих БД и СУБД) произошло от английского термина «relation» (отношение). Для удобства изложения рассмотрим в качестве примера отношение СТУДЕНТЫ, которое содержит информацию о студентах некоторого учебного заведения, и проиллюстрируем на нем основные понятия реляционной модели данных. К числу таких понятий относятся тип данных, домен, атрибут, кортеж, первичный ключ и отношение.

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

Домен представляет собой именованное множество атомарных значений одного и того же типа. При этом под атомарным значением подразумевается значение, не имеющее внутренней структуры в реляционной модели, то есть значение, которое не может быть представлено в терминах более мелких понятий той же модели. Таким образом, атомарное значение является наименьшей семантической единицей данных в реляционной модели. Примером атомарного значения может служить любое отдельное данное из отношения СТУДЕНТЫ (конкретный номер группы, размер стипендии и т. д.).

Все домены в реляционной базе данных имеют уникальные имена, и каждый домен задает множество допустимых значений данного типа. Для определения домена указывается базовый тип данных элементов этого домена и некоторый предикат, с помощью которого формулируются возможные ограничения на значения элементов домена, то есть во многом понятие домена в базах данных аналогично понятию подтипа в языках программирования. Например, домен «Номера групп» определен на базовом типе целых чисел, и в качестве ограничения используется тот факт, что значения элементов домена (номера групп) должны принадлежать диапазону 101—530.

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

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

Именованное множество пар вида {имя атрибута, имя домена} называется схемой отношения. Мощность такого множества называется степенью или арностью отношения. Из свойств атрибутов отношения следует, что все входящие в данную схему имена атрибутов различны, и каждый атрибут соответствует единственному домену. Например, схема отношения СТУДЕНТЫ содержит четыре пары указанного вида, следовательно, степень этого отношения равна четырем, и данное отношение является 4-арным.

Кортеж, соответствующий некоторой схеме отношения, представляет собой множество пар вида {имя атрибута, значение}, причем это множество содержит по одной паре такого вида для каждого имени атрибута указанной схемы отношения, а в качестве значения может употребляться любое допустимое значение из домена данного атрибута. Для кортежа так же, как и для схемы отношения, определено понятие его степени или арности (количество входящих в кортеж пар), при этом из определения понятия кортежа следует, что арность кортежа всегда совпадает с арностью соответствующей схемы отношения.

Отношение представляет собой множество кортежей, соответствующих одной схеме отношения. Мощность этого множества называется кардинальным числом данного отношения. Часто схему отношения называют заголовком отношения, а само отношение как множество кортежей — телом отношения.

Общепризнанным неформальным представлением отношения является таблица некоторого специального вида. Эта таблица состоит из заголовка, в качестве которого используется схема отношения, и некоторого числа неповторяющихся строк, каждая из которых является кортежем отношения. Имена атрибутов при данном способе представления соответствуют именам столбцов таблицы. Примером такой таблицы может служить таблица, задающая отношение СТУДЕНТЫ.

Свойства отношений

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

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

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

Тот факт, что все кортежи данного отношения различны, гарантирует наличие у каждого отношения первичного ключа, под которым подразумевается некоторый набор атрибутов, значения которых однозначным образом определяют кортеж отношения. Таким образом, доступ к конкретному кортежу отношения осуществляется по первичному ключу. Исходя из свойства уникальности кортежей, в качестве первичного ключа отношения всегда можно использовать полный набор атрибутов данного отношения, однако при формальном определении первичного ключа необходимо обеспечивать неизбыточность составляющего этот ключ набора атрибутов. Это означает, что такой набор атрибутов должен быть минимальным в том смысле, что он не должен содержать в себе атрибуты, которые можно отбросить, не нарушая основное свойство первичного ключа — однозначно определять кортеж. Так, первичным ключом отношения СТУДЕНТЫ является набор из одного единственного атрибута СТНОМЕР, поскольку значение именно этого атрибута однозначным образом определяет любой кортеж данного отношения.

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

Если доступ к конкретному кортежу отношения осуществляется по первичному ключу, то доступ к значению какого-либо атрибута в кортеже всегда осуществляется по имени этого атрибута.

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

Реляционная модель данных

Реляционной моделью данных называется формальная теория, лежащая в основе реляционных систем. Фундамент этой теории составляют теория множеств и логика предикатов. Реляционная модель описывает некоторый набор основных понятий и признаков, которыми должны обладать все СУБД и управляемые ими базы данных, основывающиеся на этой модели. Реляционная модель рассматривает данные только на логическом уровне, что позволяет абстрагироваться от конкретного способа их реализации.

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

Часть реляционной модели, связанная со структурой данных, — структурная часть модели — фактически уже описана в предыдущих разделах. В структурной части модели декларируется, что единственной структурой данных, используемой в реляционных базах данных, является нормализованное n-арное отношение.

Рассмотрению аспекта целостности данных посвящена целостная часть реляционной модели. Здесь формулируются следующие два требования целостности, которые должны поддерживаться в любой реляционной СУБД:

• целостность сущностей;
• целостность по ссылкам.

Более подробно эта часть модели описана в следующем разделе.

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

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

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

Целостность данных

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

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

Пусть, например, в реляционной базе данных требуется представить сущность ГРУППА с атрибутами ГРНОМЕР (номер группы), ГРКОЛ (количество студентов в группе) и ГРСТУД (множество студентов группы), причем для каждого студента необходимо также хранить СГНОМЕР (номер студенческого билета), СТИМЯ (фамилия студента), СТСТИП (размер стипендии студента). Тогда для соблюдения ограничения нормализованное отношение необходимо представить сущность ГРУППА в виде двух отношений: ГРУППЫ (ГР НОМЕР, ГРКОЛ) с первичным ключом ГР_НОМЕР и СТУДЕНТЫ (СТНОМЕР, СТИМЯ, СТ_СТИП, СТ_ГР_НОМ) с первичным ключом СТНОМЕР.

В данном представлении основное назначение атрибута СТГРНОМ состоит в том, чтобы иметь возможность восстанавливать полную сущность ГРУППА. При этом существенно, что значение атрибута СТГРНОМ в любом кортеже отношения СТУДЕНТЫ должно соответствовать значению атрибута ГРНОМЕР в некотором кортеже отношения ГРУППЫ, то есть по сути оба эти атрибута должны представлять одно и то же свойство сущности. Такой атрибут называется внешним ключом, поскольку его значения однозначно характеризуют сущности (задают значения их первичного ключа), представленные кортежами другого отношения. В этом случае говорят, что отношение, в котором определен внешний ключ, ссылается на отношение, в котором такой же атрибут является первичным ключом. В нашем примере отношение СТУДЕНТЫ ссылается на отношение ГРУППЫ.

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

Оба указанные требования целостности данных должны поддерживаться реляционными СУБД. Для поддержки требования целостности сущностей достаточно обеспечить уникальность первичного ключа в рамках любого отдельного отношения. Основные проблемы по обеспечению целостности по ссылкам возникают при выполнении удаления кортежа из отношения, на которое имеется ссылка. Эти проблемы могут быть решены одним из следующих способов. Первый способ заключается в запрете удаления кортежей, на которые имеются ссылки. Второй способ при удалении кортежа, на который имеются ссылки, приводит к автоматической замене внешнего ключа на неопределенное значение во всех кортежах, ссылающихся на удаленный кортеж. И, наконец, третий способ (каскадное удаление) заключается в том, что наряду с удалением кортежа, на который имеются ссылки, удаляются все ссылающиеся на него кортежи. Выбор конкретного способа обеспечения целостности по ссылкам во многом определяется спецификой прикладной области.

Реляционная алгебра

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

• объединения отношений,
• пересечения отношений,
• вычитания отношений,
• прямого произведения отношений.

Специальные реляционные операции включают операции:

• ограничения отношения,
• проекции отношения,
• соединения отношений,
• деления отношений.

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

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

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

Все указанные теоретико-множественные операции реляционной алгебры являются ассоциативными и (за исключением операции вычитания отношений) коммутативными, то есть:

(А ор В) ор С = А ор (В ор С),

А ор В = В ор А, где А, В, С — отношения, ор — теоретико-множественная операция.

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

Операция реляционного деления определена над бинарным и унарным отношениями. В результате деления получается унарное отношение, содержащее в качестве кортежей все значения первого атрибута кортежей бинарного отношения, для которых множество значений второго атрибута (при фиксированном значении первого атрибута) совпадает с множеством значений исходного унарного отношения. То есть результатом деления бинарного отношения А(а,Ь) на унарное отношение В(Ь) является унарное отношение С(а), состоящее из таких кортежей v, для которых в отношении А имеются кортежи <v, w> такие, что множество значений {w} совпадает с множеством значений атрибута b в отношении В.

Заметим, что к бинарному и унарному отношениям можно привести отношения большей арности за счет введения понятия составного атрибута. Пусть, например, заданы отношения А с заголовком {a₁, a₂, ..., a_n, b₁, b₂, ..., b_m} и В с заголовком {b₁, b₂, ..., b_m}, причем атрибут Ы отношения А и атрибут b_i отношения В имеют одно и то же имя и определены на одном и том же домене. Тогда множество атрибутов {aj} называется составным атрибутом а и, соответственно, множество атрибутов {b_j} - составным атрибутом b. После этого можно говорить о реляционном делении бинарного отношения А(а,b) на унарное отношение В(Ь).

Реляционное исчисление

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

Рассмотрим более подробно исчисление кортежей. Переменной этого исчисления является кортежная переменная, определяемая с помощью оператора RANGE, который указывает, кортежи какого отношения представляет данная переменная. Доступ к атрибутам кортежной переменной осуществляется по указанию имени переменной и имени атрибута. Для выражения условий, накладываемых на кортежные переменные, используются правильно построенные формулы (WFF — Well-Formed Formula). WFF строятся на базе простых сравнений (сравнений атомарных значений) с помощью логических связок NOT, AND, OR, конструкции IF … THEN и кванторов EXIST и FORALL.

Так же, как в исчислении предикатов в исчислении кортежей определяется понятие свободного и связанного вхождения переменной, при этом связывание вхождения переменной производится кванторами. Связанное вхождение ограничивает область видимости соответствующей переменной пределами ближайшей объемлющей WFF, связавшей данную переменную. Для определения набора и имен атрибутов результирующего отношения в исчислении кортежей используется понятие целевого списка. Элементом целевого списка в общем случае является конструкция вида var.attr, где var — имя свободной переменной, attr -имя атрибута отношения, на котором определена переменная var. Если имя переменной в целевом списке указано без имени атрибута, то в целевой список включаются имена всех атрибутов определяющего отношения. При формировании целевого списка необходимо обеспечивать уникальность имен атрибутов результирующего отношения, для этого любое повторное вхождение имени атрибута в целевой список должно быть заменено новым именем.

Выражением исчисления кортежей называется конструкция вида tl WHERE wff. Значением этого выражения является отношение, тело которого определяется указанной в данном выражении WFF, а набор атрибутов и их имена — целевым списком tl.

В исчислении доменов областью определения переменных являются домены. Правила построения формул и выражений исчисления доменов аналогичны соответствующим правилам исчисления кортежей. Основным отличием является наличие в исчислении доменов дополнительного набора предикатов, с помощью которого выражается условие членства или условие принадлежности. Для n-арного отношения R это условие имеет вид:

R (pair₁,…, pair_m) (m <= n),

где каждая пара pair; задается конструкцией A:v, в которой А -имя атрибута отношения R, v — либо литерал, либо имя переменной домена. Условие членства принимает значение true тогда и только тогда, когда в отношении R существует кортеж, содержащий заданные значения указанных в нем атрибутов.

Литература:

• К. Дейт. Введение в системы баз данных. −6-е издание. Издательский дом «Вильяме», 1999.
• С. Д. Кузнецов. Основы современных баз данных. Информационно-аналитические материалы Центра Информационных Технологий: http://citforum.ru/database/osbd/contents.shtml

Экспертные системы: архитектура, типы решаемых задач, области применения

Также см. rupedia:Экспертная система.

Работы по созданию Экспертных систем (ЭС) — первая попытка практического применения результатов в области Искусственного интеллекта (ИИ).

Определение. Экспертная система (ЭС) — вычислительная система, в которой представлены знания специалистов в некоторой конкретной узкоспециализированной предметной области и которая в рамках этой области способна принимать решения (решать задачи) на уровне эксперта-профессионала.

Основные особенности ЭС:

• ориентированы на решение практических задач в трудно формализуемых узких предметных областях,
• результаты работы сравнимы с результатами человека-эксперта,
• «прозрачность» решения,
• открытая совокупность знаний.

Основные компоненты ЭС (архитектура ЭС):

• решатель / машина вывода (решение задач пользователя),
• база знаний (хранение знаний, необходимых для решения задач),
• подсистема объяснений (объяснение того, как получено решение),
• пользовательский интерфейс,
• подсистема приобретения знаний,
• интерфейс администратора / инженера знаний.

Типичные задачи, решаемые с помощью ЭС:

• Интерпретация — описание ситуации по информации, поступающей от датчиков (SPE — определение концентрации гамма-глобулина в крови).
• Прогноз — определение вероятных последствий заданных ситуаций (PLANT/cd — определения потерь урожая от черной совки).
• Планирование — определение последовательности действий (TATR — планирование авиаударов по аэродромам противника).
• Диагностика — выявление причин неправильного функционирования системы (MYCIN — диагностика бактериальных инфекций).
• Отладка — составление рецептов исправления неправильного функционирования системы (ONCOCIN — планирования химиотерапевтического лечения).
• Ремонт — выполнение последовательности предписанных исправлений (TQMSTUNE — настройка масс-спектрометра).
• Проектирование — построение конфигурации объектов при заданных ограничениях (XCON (R1) — выбор оптимальной конфигурации аппаратных средств (VAX)).
• Наблюдение — сравнение результатов наблюдения с ожидаемыми результатами (VM — наблюдение за состоянием больного в палате интенсивной терапии).
• Обучение — диагностика, отладка и ремонт поведения обучаемого (GUIDON — обучение студентов-медиков (антибактериальная терапия)).
• Управление — управление поведением системы как целого.

Решатель ЭС:

• Вызов процедур (модулей / правил) по образцу -> гибкая схема взаимодействия (управления).
• Продукция — правило вида p:a->b (где: p — предусловие, a — антецедент, b — консеквент).

Основной цикл работы:

• выборка (правил-кандидатов)
• сопоставление / означивание
• разрешение конфликтов
• выполнение / действия

Метазнания в ЭС

Выбор правил:

• П1: утечка серной кислоты -> использовать анион-обменник (стоимость: дорого, источник информации: доктор Грин, степень опасности: невелика)
• П2: утечка серной кислоты -> использовать уксусную кислоту (стоимость: дешево, источник информации: практикант Грун, степень опасности: велика)
• П3: прежде всего использовать правило, требующее минимальных затрат
• П4: прежде всего использовать правило, внесенное в БЗ специалистом
• П5: прежде всего использовать правило с минимальной степенью опасности

Оправдание правил:

• П6: утечка серной кислоты -> использовать известь (оправдание: нейтрализация, образование нерастворимого и химически неактивного вещества)
• П7: утечка уксусной кислоты -> использовать известь (оправдание: нейтрализация)
• П8: утечка соляной кислоты -> использовать известь (оправдание: нейтрализация)

Обнаружение ошибок в правилах:

• ПР01: использовать известь — нет антецедента
• ПР02: утечка: соляная кислота -> использовать известь
• ПР03: соляная кислота -> использовать известь — проверить: не совпадает ли предусловие с предусловием предыдущего правила
• П9: если некоторое правило никогда не срабатывает, проверить его предусловие

Стратегические правила:

• П10: пространство поиска относительно мало -> оправдан полный перебор
• П11: один из конъюнктов часто ложен -> перенести его в начало
• П12: фрагмент часто выполняется -> оптимизировать его
• П13: фрагмент часто выполняется & редко меняется -> скомпилировать его
• П14: утечка вещества, которое не описано в БЗ -> база знаний по утечкам неадекватна

Объяснение в ЭС

Цель — обосновать, аргументировать ответ в максимально естественной форме.

Что объяснять?

• как получено решение
• как использована некоторая информация (факты, правила)
• почему не использована некоторая информация (факты, правила)
• что использовано в целом при решении задачи (факты, правила)

Для кого нужны объяснения?

• эксперты
• инженеры знаний
• пользователи
• изучающие (новички)

Построение ЭС

Этапы:

• идентификация ПО (цели и характеристики ЭС, ресурсы, участники разработки)
• концептуализация (основные понятия и связи между ними, основные задачи)
• формализация (запись на выбранном языке представления знаний, формирование БЗ)
• реализация
• проверка правил, тестирование

Извлечение экспертных знаний и формирование баз знаний

• Наблюдение на рабочем месте: ИЗ получает представление о характерных задачах.
• Обсуждение задач: ИЗ узнает, как организованы знания Э (понятия, гипотезы), как Э работает с неполной, неточной, противоречивой информацией, какие процедуры необходимы для решения задач.
• Описание задач: ИЗ узнает, как связаны между собой задачи одного класса, классы задач.
• Анализ задач: ИЗ пытается найти и сформулировать стратегии решения задач.
• Доводка системы: ИЗ проверяет сформированную совокупность знаний (БЗ).
• Оценивание системы: Э оценивает точность работы ИЗ и правильность сформированной БЗ.
• Проверка системы: объективная оценка результатов работы ИЗ и Э (и сформированной БЗ).

Параллелизм обработки информации в вычислительных системах

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

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

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят — ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени — ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы, конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость.

Классификация Флинна

Cамой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М.Флинном. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.

• SISD (single instruction stream / single data stream) — одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка — как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.
• SIMD (single instruction stream / multiple data stream) — одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными — элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.
• MISD (multiple instruction stream / single data stream) — множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе.
• MIMD (multiple instruction stream / multiple data stream) — множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.

Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике того или иного компьютера. Если говорится, что компьютер принадлежит классу SIMD или MIMD, то сразу становится понятным базовый принцип его работы, и в некоторых случаях этого бывает достаточно. Однако видны и явные недостатки. В частности, некоторые заслуживающие внимания архитектуры, например dataflow и векторно-конвейерные машины, четко не вписываются в данную классификацию. Другой недостаток — это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попадают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования.

Массивно-параллельные системы (MPP)

Система состоит из однородных вычислительных узлов, включающих:

• один или несколько центральных процессоров (обычно RISC),
• локальную память (прямой доступ к памяти других узлов невозможен),
• коммуникационный процессор или сетевой адаптер
• иногда — жесткие диски (как в SP) и/или другие устройства В/В

К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т. п.)

Общее число процессоров в реальных системах достигает нескольких тысяч (ASCI Red, Blue Mountain).

Существуют два основных варианта ОС для управления такими компьютерами:

• Полноценная ОС работает только на управляющей машине (front-end), на каждом узле работает сильно урезанный вариант ОС, обеспечивающие только работу расположенной в нем ветви параллельного приложения. Пример: Cray T3E.
• На каждом узле работает полноценная UNIX-подобная ОС (вариант, близкий к кластерному подходу). Пример: IBM RS/6000 SP + ОС AIX, устанавливаемая отдельно на каждом узле.

Программирование в рамках модели передачи сообщений (MPI, PVM, BSPlib)

Примеры: IBM RS/6000 SP2, Intel PARAGON/ASCI Red, SGI/CRAY T3E, Hitachi SR8000, транспьютерные системы Parsytec.

Симметричные мультипроцессорные системы (SMP)

Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора (HP 9000). Аппаратно поддерживается когерентность кэшей.

Наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число — не более 32 в реальных системах. Для построения масштабируемых систем на базе SMP используются кластерные или NUMA-архитектуры.

Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel-платформ поддерживается Windows NT). ОС автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling), но иногда возможна и явная привязка.

Программирование в модели общей памяти. (POSIX threads, OpenMP). Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания.

Примеры: HP 9000 V-class, N-class; SMP-cервера и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др.).

Системы с неоднородным доступом к памяти (NUMA)

Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, то есть к памяти других модулей. При этом доступ к локальной памяти в несколько раз быстрее, чем к удаленной. В случае, если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре cc-NUMA (cache-coherent NUMA)

Масштабируемость NUMA-систем ограничивается объемом адресного пространства, возможностями аппаратуры поддежки когерентности кэшей и возможностями операционной системы по управлению большим числом процессоров. На настоящий момент, максимальное число процессоров в NUMA-системах составляет 256 (Origin2000).

Обычно вся система работает под управлением единой ОС, как в SMP. Но возможны также варианты динамического «подразделения» системы, когда отдельные «разделы» системы работают под управлением разных ОС (например, Windows NT и UNIX в NUMA-Q 2000).

Программирование аналогично SMP.

Примеры: HP HP 9000 V-class в SCA-конфигурациях, SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000, SNI RM600.

Параллельные векторные системы (PVP)

Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).

Эффективное программирование подразумевает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание (для одновременной загрузки нескольких процессоров одним приложением).

Примеры: NEC SX-4/SX-5, линия векторно-конвейерных компьютеров CRAY: от CRAY-1, CRAY J90/T90, CRAY SV1, серия Fujitsu VPP.

Кластерные системы

Набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта массивно-параллельного компьютера. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. При объединении в кластер компьютеров разной мощности или разной архитектуры, говорят о гетерогенных (неоднородных) кластерах.

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

Используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые — Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки.

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

Примеры: NT-кластер в NCSA, Beowulf-кластеры.

Историческая справка

IBM 701 (1953), IBM 704 (1955): разрядно-параллельная память, разрядно-параллельная арифметика.

Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно-последовательную память, из которой слова считывались последовательно бит за битом. Первым коммерчески доступным компьютером, использующим разрядно-параллельную память (на CRT) и разрядно-параллельную арифметику, стал IBM 701, а наибольшую популярность получила модель IBM 704 (продано 150 экз.), в которой, помимо сказанного, была впервые применена память на ферритовых сердечниках и аппаратное АУ с плавающей точкой.

IBM 709 (1958): независимые процессоры ввода/вывода.

Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого быстрого внешнего устройства, а по тем временам это магнитная лента, была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода процессор фактически простаивал. В 1958 г. к компьютеру IBM 704 присоединили 6 независимых процессоров ввода/вывода, которые после получения команд могли работать параллельно с основным процессором, а сам компьютер переименовали в IBM 709. Данная модель получилась удивительно удачной, так как вместе с модификациями было продано около 400 экземпляров, причем последний был выключен в 1975 году — 20 лет существования!

IBM STRETCH (1961): опережающий просмотр вперед, расслоение памяти.

В 1956 году IBM подписывает контракт с Лос-Аламосской научной лабораторией на разработку компьютера STRETCH, имеющего две принципиально важные особенности: опережающий просмотр вперед для выборки команд и расслоение памяти на два банка для согласования низкой скорости выборки из памяти и скорости выполнения операций.

ATLAS (1963): конвейер команд.

Впервые конвейерный принцип выполнения команд был использован в машине ATLAS, разработанной в Манчестерском университете. Выполнение команд разбито на 4 стадии: выборка команды, вычисление адреса операнда, выборка операнда и выполнение операции. Конвейеризация позволила уменьшить время выполнения команд с 6 мкс до 1,6 мкс. Данный компьютер оказал огромное влияние, как на архитектуру ЭВМ, так и на программное обеспечение: в нем впервые использована мультипрограммная ОС, основанная на использовании виртуальной памяти и системы прерываний.

CDC 6600 (1964): независимые функциональные устройства.

Фирма Control Data Corporation (CDC) при непосредственном участии одного из ее основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 — первый компьютер, в котором использовалось несколько независимых функциональных устройств.

CDC 7600 (1969): конвейерные независимые функциональные устройства.

CDC выпускает компьютер CDC-7600 с восемью независимыми конвейерными функциональными устройствами — сочетание параллельной и конвейерной обработки.

ILLIAC IV (1974): матричные процессоры.

Проект: 256 процессорных элементов (ПЭ) = 4 квадранта по 64ПЭ, возможность реконфигурации: 2 квадранта по 128ПЭ или 1 квадрант из 256ПЭ, такт 40нс, производительность 1Гфлоп;

CRAY 1 (1976): векторно-конвейерные процессоры

В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray Research, которая в 1976 г. выпускает первый векторно-конвейерный компьютер CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая производительность 160 миллионов операций в секунду, оперативная память до 1Мслова (слово — 64 разряда), цикл памяти 50нс. Главным новшеством является введение векторных команд, работающих с целыми массивами независимых данных и позволяющих эффективно использовать конвейерные функциональные устройства.

Конвейерность и параллелизм

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

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

Выполнение типичной команды можно разделить на следующие этапы:

• выборка команды — IF (по адресу, заданному счетчиком команд, из памяти извлекается команда);
• декодирование команды / выборка операндов из регистров — ID;
• выполнение операции / вычисление эффективного адреса памяти — EX;
• обращение к памяти — MEM;
• запоминание результата — WB.

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

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

Существуют три класса конфликтов:

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

Технология работы в сети Интернет (браузеры, способы описания сайтов)

См. также rupedia:Список браузеров.

Литература (из списка вопросов)

• Кауфман В. Ш. Языки программирования. Концепции и принципы. М.: Радио и связь, 1993.
• Жоголев Е. А. Лекции по технологии программирования. -

  http://sp.cs.msu.su в разделе «Информация».

• Машечкин И. В., Петровский М. И., Скулачев П. Д., Терехин А. Н. Системное Программное Обеспечение: файловые системы ОС Unix и Windows NT (конспект лекций). — М.: Диалог-МГУ, 1997.
• Робачевский А. Операционная система UNIX. — СПб: BHV — Санкт-Петербург, 1997.
• Дейт К.Дж. Введение в системы баз данных. — М. *Киев: Диалектика, 1998.
• Интеллектуализация ЭВМ. — М.: Высшая школа, 1989.
• Смирнов А. Д. Архитектура вычислительных систем. — М.: Наука, 1990.
• Нильсен М. Знакомьтесь: World Wide Web. — Киев: BHV, 1996.

Утверждено на Совете факультета ВМиК МГУ 29 марта 2000 г.

Источники сборки статьи

• Замок Дракона (без башни). Например, «Лекция 8 — Разработка программного модуля» — http://ergeal.ru/txt/archive/cs/tp/08.htm.
• Файл:Компиляция-ASP-Спецчасть-старая.doc.
• esyrwiki:Языки программирования, 05 лекция (от 19 сентября) и последующие.
• Методические материалы для подготовки к государственному экзамену по прикладной математике и информатике (по программе специалистов). А. В. Боресков, И. А. Волкова, И. В. Дмитриева, Г. П. Иванова, Е. А. Кузьменкова, С. И. Орлик, Д. С. Романов. Москва, Планета Знаний, 2007.