ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ МЕР ХОЛСТЕДА ДЛЯ СОПОСТАВЛЕНИЯ ТЕКСТОВ ПРОГРАММ И ИХ ОПИСАНИЙ

ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ

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

  • 1) наложение шаблона. Этот способ трудно реализуем, так как и тексты программ, и тексты описаний могут отличаться в зависимости от стиля программирования;
  • 2) анализ существа предложения. Данный способ требует разработки сложных программных средств, способных осуществить семантический разбор исходных кодов и сопровождающей их документации;
  • 3) «измерение» текста программы и соответствующей спецификации. В этом случае задачей исследования является поиск способа этого измерения. Нахождение такого способа позволит, во-первых, сопоставлять исходные тексты программ между собой и, во-вторых, сопоставлять тексты на естественном языке с текстом программы.

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

ПОИСК МЕРЫ И СПОСОБОВ ИЗМЕРЕНИЯ ПРОГРАММ И ИХ ОПИСАНИЙ

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

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

Таблица 9.1

Название модели

Формула, обозначение

Метрики сложности

Метрики Холстеда: длина программы объем программы оценка ее реализации трудность ее понимания трудоемкость кодирования уровень языка выражения информационное содержание оптимальная модульность

N=nxogynx2log2«2 V= Nog2n L*=(2n2)/(nN2)

E = V/L

D = (nxN2)(ln2)=/L*

x*=v/d2=v/l*2

/= V/D M= n*2/6

Метрики Джилба: количество операторов цикла количество операторов условия число модулей или подсистем отношение числа связей между модулями к числу модулей отношение числа ненормальных выходов из множества операторов к общему числу операторов

^100/>

j

^IF Amod

f~ mod

f = N*sv/L

Метрики Мак-Кейба: цикломатическое число цикломатическая сложность

MG) = m — n + p v(G) = X{G) + 1 = mn + 2

Метрика Чепена — мера трудности понимания программ на основе входных и выходных данных

H=0,5T + P + 2M + 3C

Метрика Шнадевида — число путей в управляющем графе

s=ipici

Метрика Майерса — интервальная мера

[v, ... v2]

Метрика Хансена — пара (цикломатическое число, число операторов)

{v, N}

Метрика Чена — топологическая мера Чена

M(G) = (v(G), N, Q0)

Метрика Вудворда — узловая мера (число узлов передач управления)

%

Метрика Кулика — нормальное число (число простейших циклов в нормальной схеме программы)

Norm (P)

Название модели

Формула, обозначение

Метрика Хура — цикломатическое число сети Петри, отражающей управляющую структуру программы

Метрики Витворфа, Зулевского: мера сложности потока управления мера сложности потока данных

У (Р)

ад

Метрика Петерсона — число многовходовых циклов

NmmP

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

и

м

функциональное отношение (отношение числа вершин графа к функциональному числу)

f=NXl/fl

регулярные выражения (число операндов, операторов и скобок в регулярном выражении управляющего графа программы)

p(G) = N + L + Sk

Метрика Пивоварского — модифицированная цикломатическая мера сложности

N(G) =nG)+1P.

Метрика Пратта — тестирующая мера

Test (Pr)

Метрика Кантоне — характеристические числа полиномов, описывающих управляющий граф программы

PCN*

Метрика Мак-Клура — мера сложности, основанная на числе возможных путей выполнения программы, числе управляющих конструкций и переменных

C(V) = D(V) x J(V)/N

Метрика Кафура — мера на основе концепции информационных потоков

1(G)

Метрика Схуттса, Моханти — энтропийные меры

e(G)

Метрика Коллофело — мера логической стабильности программ

h(G)

Название модели

Формула, обозначение

Метрика Зольновского — Симмонса — Тейера

Взвешенная сумма различных индикаторов:

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

1(а, р, у, v) Z(X, X, и, к)

Метрика Берлингера — информационная мера

I(R) = m(FR)xF(R))2

Метрика Шумана — сложность с позиции статистической теории языка

Н(Т)

Метрика Янгера: логическая сложность с учетом истории вычислений сложность проектирования насыщенность комментариями число внешних обращений число операторов

А(оз)

Cc = Zlog2(/' + )[ZnCxy(n) Х=К/С

с.

Прогноз модели

Модели Холстеда прогноз системных ресурсов прогноз числа ошибок модель фирмы IBM модель общей сложности модели связности сплайн-модель

Р= 3/8(5,- 1) -2r«

В = Mog2/7/3000 В = 2ЪМХп)

5 = 21,1 +0,1 V+COMP(S) р„ = 0,15(5; + Si)+0,7Cii Pr= 1/2ZX.(A2^.+A N)i ln{ д?2 + Длф + a + fiZ. + у (V,

Оценочные модели

Джелински—Моранды

R (t) = e~(T~ 1 + 1)ф/

Вейса—Байеса

Rx{t) = Яе_/-(,-|)ф)/ W, F/tv..., t._x)dXd0

Шика—Вол вертона

Rl(t) = e-F(N-' + V)l*/2

Литтлвуда

Нельсона

R/t) = ехр{Цп( 1 - Pj)}

Название модели

Формула, обозначение

Халецкого

Rft) = P~-a(l-ff)/n.

Модель отлаженности

R.{t) = Р~- pf.(x, X, п)

Мозаичная модель

R,(t)= 1-р(а

Примечание:

пх — число уникальных операторов программы, включая символы-разделители, имена процедур и знаки операций (словарь операторов); п2 — число уникальных операндов программы (словарь операндов);

Nx — общее число операторов в программе;

N2 — общее число операндов в программе.

Учитывая введенные обозначения, можно определить:

п = пх + п2 — словарь программы;

N= Nx + N2 — длина программы;

п' = п[ + п'2 теоретический словарь программы;

N'= «jlog2(«j) + w2log2(«2) — теоретическая длина программы (для стилистически корректных программ отклонение N от N' не превышает 10%);

V= Mog2« — объем программы;

V = N’Xoglri — теоретический объем программы, где п* — теоретический словарь программы;

L = V/V— уровень качества программирования, для идеальной программы L = 1;

L’ = (2n2)/(nxN2) — уровень качества программирования, основанный лишь на параметрах реальной программы без учета теоретических параметров;

ЕС= V/(U)2 сложность понимания программы;

D = 1 /1! — трудоемкость кодирования программы;

у’ = V/D2 уровень языка выражения;

/= V/D — информационное содержание программы, данная характеристика позволяет определить умственные затраты на создание программы;

Е = N'ogl{n/L) — оценка необходимых интеллектуальных усилий при разработке программы, характеризующая число требуемых элементарных решений при написании программы.

Остальные метрики не приняты во внимание. С ними можно ознакомиться по ссылке http://www.viva64.com.

Анализ показывает, что для постоянного мониторинга ПО наиболее полезна так называемая словарная метрика, основанная на метрических соотношениях Холстеда, цикломатических мерах МакКейба и измерениях Тейера. Метрика Холстеда позволяет производить оценку степени документированности программного кода.

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

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

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

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

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

  • • рассмотренные меры Холстеда для сопоставительного анализа текстов программ и их спецификаций не применялись. Следовательно, в настоящий момент нет экспериментального подтверждения возможности такого их использования;
  • • теория Холстеда не является общепризнанной. В некоторых работах делается попытка доказать несостоятельность использования оценки Холстеда для аппроксимации длины программы. В работе доказательство проводится на примере 34 программ на алгоритмическом языке PL/1. Одной из существенных задач при проведении эксперимента является обоснованный выбор экспериментального материала. В качестве последнего выбран ставший классическим «Пакет научных подпрограмм — Библиотека исходных модулей» (ПНП-БИМ), реализованный международным сообществом математиков и программистов на алгоритмическом языке FORTRAN. История развития этого языка (более 50 лет и по настоящее время) такова, что он может рассматриваться как материал для эксперимента. Основания для выбора ПНП-БИМ следующие:
    • 1) значительный набор программных модулей (около 400 программ);
    • 2) единый язык программирования и строгая форма документации, соответствующая требованиям международных стандартов и ЕСПД;
    • 3) реализация в данной библиотеке практически всех численных методов, апробированных в ведущих мировых научных центрах;
    • 4) пакет совершенствовался международным сообществом математиков и программистов на протяжении многих десятков лет, поэтому его можно считать идеальным с точки зрения качества программирования;
    • 5) наличие единообразной документации на каждый программный модуль, полностью отвечающей требованиям стандартов. На основании анализа, проведенного ранее, в качестве объективных мер выбраны: объем, потенциальный объем и интеллектуальное содержание, которые в дальнейшем будем обозначать L .

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

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

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

где п — количество совпадающих подряд символов; N— количество символов в более длинном слове; к — значение критерия распознавания.

Правомерность применения описанного способа распознавания, а также значение к должны определяться в процессе эксперимента исходя их минимума ошибок распознавания и максимума скорости обработки. Содержание словаря определяется выбранным экспериментальным материалом. Документация на программные модули в ПНП-БИМ составлена на английском языке, поэтому в качестве операторов в словарь заносятся слова, определенные в [24] как функциональные. Для решения задач эксперимента их количество установлено равным 360.

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

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

• возможность построения словаря из слов документации ПНП-

БИМ;

• возможность обучения системы в случае отсутствия объективного

критерия качества;

• возможность наглядного отображения результатов.

Результаты эксериментальных исследований. Далее приведены результаты исследований, проведенных в соответствии с методикой, описанной ранее.

Подготовительный этап. На рис. 9.1 изображена зависимость среднего объема текстов описания от частоты занесения слов в еловарь. Анализ этой зависимости показывает, что увеличение словаря за счет включения в него слов, встречающихся в текстах описаний пакета ПНП-БИМ менее 40 раз, практически не сказывается на величине вычисленного объема текстов описания. В связи с этим при построении словаря в него заносятся слова, встречающиеся в текстах описания более 40 раз. При этом с учетом определенного в [24J списка обязательных слов объем словаря для исследования составляет 900 слов. Анализ приведенной зависимости показывает, что при значении критерия распознавания, равном 0,65, ошибки распознавания минимальны. Данное значение критерия принято за номинальное. При уменьшении номинального значения критерия увеличение количества нераспознанных слов связано с неправильной идентификацией слов по словарю. При увеличении номинального значения критерия количество нераспознанных слов растет за счет несовпадения основных форм слов, занесенных в словарь, и производных форм слов, встречающихся в текстах описаний. При выбранном номинальном значении критерия распознавания среднее время обработки одного текста описания составляет до десятков секунд. Это значение вполне приемлемо для проведения исследований.

Основной этап. На основании выбранного критерия и объема словаря был проведен основной объем исследований, результаты которого представлены в графическом виде на рис. 9.1 и 9.2. Результаты эксперимента можно разделить на три группы. К первой группе относятся сопоставительные графики текстов программ и текстов соответствующих описаний. Ко второй группе относятся сопоставительные графики текстов программ и описаний, полученные в процессе сознательного ухудшения текста описания. К третьей группе относятся графики характеристик L для текстов программ.

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

  • 1) размещение матриц в памяти;
  • 2) операции с матрицами;
  • 3) операции с полиномами;
  • 4) интерполирование и сглаживание функций;
  • 5) подстановки, суммы и пределы последовательностей;
  • 6) численное дифференцирование функций;
  • 7) численное интегрирование функций;
Зависимость частотной границы занесения слов в словарь

Рис. 9.1. Зависимость частотной границы занесения слов в словарь

от средного объема текстов

Зависимость среднего времени обработки текстов описаний и количества нераспознанных слов от значения критерия распознавания

Рис. 9.2. Зависимость среднего времени обработки текстов описаний и количества нераспознанных слов от значения критерия распознавания

  • 8) специальные функции;
  • 9) гармонический анализ;
  • 10) безусловная оптимизация;
  • 11) непараметрическая статистика;
  • 12) элементарная статистика;
  • 13) дискриминантный анализ.

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

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

где VPi — объем /-й программы; VSi объем /-й спецификации; KNv нормирующий коэффициент.

При этом

где п — число обрабатываемых программ.

Нормированную разность «интеллектуального содержания», значения которой откладываются по оси ординат, можно представить формулой

где I pi — «интеллектуальное содержание» i-й программы; ISi «интеллектуальное содержание» /-й спецификации; Кт нормирующий коэффициент.

При этом

где г — число обрабатываемых программ.

Анализ представленных графиков позволяет сделать следующие выводы.

1. Существуют группы программ, для которых с увеличением сложности программы увеличивается значение AV; аналогичная зависимость прослеживается и для А/ . Рассмотрим причины, порождающие указанную зависимость, на примере программ QL2 и QL9. Тексты программ и соответствующих описаний приведены далее. Обе программы предназначены для интегрирования методом

Гаусса и отличаются количеством узлов интегрирования. При этом очевидно, что программа QL9, использующая девятиточечный метод, сложнее программы QL2, которая использует двухточечный метод.

Анализ текстов описаний на эти программы показывает, что с точки зрения количества операндов и операторов они идентичны, а различие между ними заключается в том, что в разделе METHOD указывается разное количество узлов интегрирования. В результате вычислений характеристик L для программ QL2 и QL9 получаем:

Следовательно,

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

  • 2. Значения АУи А/для 298 программ и соответствующих текстов описаний отличаются не более чем на 20%.
  • 3. Значения АУи А/для 44 программ отличаются не более чем на 10%.
  • 4. На графиках имеются резкие выбросы, свидетельствующие о резком несоответствии характеристик L , вычисленных для текста программы, и характеристик L , вычисленных для текстов описаний.

Рассмотрим причины, порождающие ухудшение несоответствия на примере сопоставительного анализа программ DET5 и HARM. Тексты соответствующих программ и тексты соответствующих описаний приведены далее.

Анализ текстов показывает, что описание программы DET5 полностью раскрывает метод производимых ею вычислений. Сопоставительный анализ текста программы HARM и ее описания показывает, что спецификация является неполной. Недостаточно раскрыт метод производимых вычислений, поскольку имеются ссылки на литературу, в которой приводится полное описание используемого программой алгоритма быстрого преобразования Фурье. Таким образом, резкие выбросы на рассматриваемых графиках объясняются либо недостаточным документированием соответствующих программ, либо «ссылочным» характером документирования.

Текст спецификации и программы QL2

С ..................................................................

С

С SUBROUTINE QL2

С

С PURPOSE

С ТО COMPUTE INTEGRAL (EXP (-Х) *FCT (X), SUMMED

OVER X FROM 0 C TO INFINITY).

C

C USAGE

C CALL QL2 (FCT, Y)

C PARAMETER FCT REQUIRES AN EXTERNAL STATEMENT

C

C DESCRIPTION OF PARAMETERS

C FCT - THE NAME OF AN EXTERNAL FUNCTION

SUBPROGRAM USED.

C Y - THE RESULTING INTEGRAL VALUE.

C

C REMARKS

C NONE

C

C SUBROUTINES AND FUNCTION SUBPROGRAMS REQUIRED C THE EXTERNAL FUNCTION SUBPROGRAM FCT (X)

MUST BE FURNISHED C BY THE USER.

C

C METHOD

C EVALUATION IS DONE BY MEANS OF 2-POINT

GAUSSIAN-LAGUERRE

C QUADRATURE FORMULA, WHICH INTEGRATES EXACTLY

WHENEVER

C FCT (X) IS A POLYNOMIAL UP TO DEGREE3.

C FOR REFERENCE, SEE

С V. I.KRYLOV, APPROXIMATE CALCULATION OF

INTEGRALS,

C MACMILLAN, NEW YORK/LONDON, 1962, PP.130-132

AND347-352 .

C

C ..................................................................

c

SUBROUTINE QL2 (FCT, Y)

C с

Х=3.414214

Y=.14 644 66*FCT (X)

Х=.5857864

Y=Y+.8535534 *FCT (X)

RETURN

END

Текст спецификации и программы QL9

С ..................................................................

С SUBROUTINE QL9 С PURPOSE

С ТО COMPUTE INTEGRAL (EXP (-Х) *FCT (X), SUMMED

OVER X FROM 0 C TO INFINITY).

C USAGE

C CALL QL9 (FCT, Y)

C PARAMETER FCT REQUIRES AN EXTERNAL STATEMENT

C DESCRIPTION OF PARAMETERS

C FCT - THE NAME OF AN EXTERNAL FUNCTION

SUBPROGRAM USED.

C Y - THE RESULTING INTEGRAL VALUE.

C REMARKS

C NONE

C SUBROUTINES AND FUNCTION SUBPROGRAMS REQUIRED C THE EXTERNAL FUNCTION SUBPROGRAM FCT (X)

MUST BE FURNISHED C BY THE USER.

C METHOD

C EVALUATION IS DONE BY MEANS OF 9-POINT

GAU S SIAN-LAGUE RRE

C QUADRATURE FORMULA, WHICH INTEGRATES EXACTLY

WHENEVER

C FCT (X) IS A POLYNOMIAL UP TO DEGREE17.

C FOR REFERENCE, SEE

С V.I.KRYLOV, APPROXIMATE CALCULATION OF

INTEGRALS,

C MACMILLAN, NEW YORK/LONDON, 1962, PP.130-132

AND347-352 .

C

C ..................................................................

SUBROUTINE QL9 (FCT, Y)

C

Y—.329087 4E-10*FCT (X) Х=18.83360

Y=Y+.41107 69E-7*FCT (X) Х=13.46624

Y=Y+.6592123E-5*FCT (X) Х=9.372985

Y=Y+.30524 98E-3*FCT (X) X=6.204957

Y=Y+.005599627*FCT (X) X=3.783474

Y=Y+.0474 605 6*FCT (X)

X=2.005135

Y=Y+.199287 5*FCT (X)

X=.8072200 Y=Y+.4112140*FCT (X)

X=.1523222

Y=Y+.33 612 64 *FCT (X)

RETURN

END

На рис. 9.3 представлена зависимость ДКот полного описания поогоамм.

Зависимость нормированной разности AV от условной степени

Рис. 9.3. Зависимость нормированной разности AV от условной степени

ухудшения описания L

Зависимость нормированной разности А/ от условной степени ухудшения описания L

Рис. 9.4. Зависимость нормированной разности А/ от условной степени ухудшения описания L

На рис 9.4 представлен график значений AV при ухудшении текста описания путем исключения разделов METHOD и REMARKS. Значению 0 соответствует нормированная разность —0,1147; значению 100 — единица. Шаг равен 0,0111.

Под условной степенью ухудшения, равной 1, 2, 3, понимаются соответственно полное описание; описание, ухудшенное до раздела METHOD; описание ухудшенное до раздела REMARKS. Аналогичная зависимость найдена и для AI .

Анализ результатов измерения программ. В приложении 1 приведены тексты программ на языке Фортран.

Как будет показано далее (и это видно из текста), размер программы вычисления быстрого преобразования Фурье значительно больше размера программы вычисления производной. При этом размеры спецификаций приблизительно равны. Далее приведен графический материал, описывающий результаты численных экспериментов. Отчетливо видно, что существует явная связь между ростом нормированной разности объема и условной разностью описания. Это позволяет считать, что меры АУи L можно применять в качестве объективных показателей. То же можно полагать и для других мер. На рис. 9.5—9.12 приведены графики результатов экспериментальных исследований по измерению программ.

Нормированная разность значений объемов при описании до раздела METHOD

Рис. 9.7. Нормированная разность объемов текстов при описании до раздела REMARKS

Рис. 9.9. Нормированная разность значений объемов при описании до раздела METHOD

Рис.9.11. Объем программ

Рис. 9.12. Интеллектуальное содержание программ

Анализ графиков, изображенных на рисунках 9.5—9.12, показывает, что ухудшение описания путем исключения из них указанных разделов приводит к изменению значений нормированных разностей AV и А/ , причем проявляется зависимость следующего характера: чем больше ухудшается описание, тем больше становятся значения AV и А/ .

Анализ зависимостей / и V от экспертной оценки сложности программ показывает, что на участках группировки программ по возрастанию сложности вычислений наблюдается увеличение значений / и V . Указанная зависимость наглядно иллюстрируется сопоставлением текстов программ QL2 и QL9, представленных на рис. 9.9 и 9.10. Анализ, проведенный ранее, свидетельствует о том, что программа QL9 является более сложной по отношению к программе QL2. Это заключение подтверждается экспериментальными данными:

Приведем другой пример — текст программы HARM. Попытка сопоставить текст этой программы и, например, текст обсуждавшейся ранее программы QL2 приводит к выводу о том, что программа HARM значительно сложнее программы QL2. Если теперь обратиться к результатам эксперимента, то можно увидеть, что объем программы HARM более чем в 1000 раз, а интеллектуальное содержание — более чем в 100 раз больше, чем у программы QL2.

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

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

«В своих палатах белокаменных Устроил Садко по-небесному:

На небе солнце — и в палатах солнце;

На небе месяц — и в палатах месяц;

На небе звезды — и в палатах звезды».

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

Пример тавтологии в тексте программы:

Вместо: Н =Х2.

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

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

Меры количества информации в СУБД и каналах связи. Семантическая мера в лингвистике. Далее будет рассматриваться модель СУБД как бесконечная линия связи. Если через линию связи без помех передается последовательность дискретных сообщений длительностью Т, то скорость передачи информации по каналу связи (бит/с) составит

где / — количество информации, содержащейся в последовательности сообщений.

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

Скорость передачи сообщений в общем случае зависит от статистических свойств сообщений и параметров канала.

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

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

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

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

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

ПЕРЕДАЧА СИГНАЛА ПО КАНАЛУ С ПОМЕХАМИ

При передаче сигнала через канал с помехами сообщения искажаются и на приемной стороне нет уверенности в том, что принято именно то сообщение, которое передавалось. Поскольку для оценки качества передачи применима семантическая мера количества информации («смысла»), обсуждаемые вопросы относятся и к лингвистике. Считается, что сообщение недостоверно, если вероятность правильности его после приема не равна единице. В этом случае количество получаемой информации уменьшается на величину неопределенности, вносимой помехами, т.е. вычисляется как разность энтропии сообщения до и после приема: H{i) — энтропия источника сообщений; Hj(i) — энтропия сообщений на приемной стороне.

Таким образом, скорость передачи по каналу связи с помехами составляет:

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

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

где Fm полоса частот канала (Гц); Wc средняя мощность сигнала; Wsh — средняя мощность помех (равномерный спектр) с нормальным законом распределения амплитуд в полосе частот канала связи.

Следовательно, можно передавать информацию по каналу с помехами без ошибок, если скорость передачи информации меньше пропускной способности канала, определяемой формулой для с. Для скорости v > с при любой системе кодирования частота ошибок принимает конечное значение, причем оно растет с увеличением значения v. Из выражения для с следует, что для канала с очень высоким уровнем шумов {Wsh > 1VJ максимальная скорость передачи близка к нулю.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >