Сборник ответов к экзамену - polpoz.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Сборник ответов к экзамену - страница №1/15



Стандартизация, сертификация и управление качеством ПО

Сборник ответов к экзамену

Made by {group 371}

ПРОГРАММОМЕТРИКА

1.1. Программометрика: характеристика, задачи, классификация моделей, область применения


Программометрика (метрическая теория программ) - научное и прикладное направление информатики в области проектирования и управления разработкой программных средств информационных систем (ПС ИС), имеющее следующие задачи:

  • количественный анализ возможности и целесообразности разработки автоматизированных процедур и функций ИС в заданной постановке;

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

  • планирование и управление разработкой ПС, оценка трудоемкости его создания, технико-экономическое обоснование;

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

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

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


1.2. Понятие алгоритмической сложности. Верхняя оценка алгоритмической сложности


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

Определение алгоритмической сложности объекта. Пусть  - произвольная частично-рекурсивная функция. Тогда мерой сложности последовательности х назовем величину



где р - программа (код), по которой  восстанавливает х; l(p) - ее длина (количество двоичных разрядов), а s - множество всех допустимых программ.

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

Максимальное значение энтропии: (при Pi=1/s, т.е. все символы в последовательности равновероятны), а её наименьшее значение: Hmin = . После нахождения s, при котором приращение минимально, можно определить, что максимум энтропии минимален при N  , а наоборот -  Это и есть верхняя оценка уровня алгоритмической сложности.


1.3. Свойства алгоритмической сложности


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

  1. l(x), т.е. сложность последовательности х не превосходит ее длины.

  2. lim K=  , , т.е. сложность последовательности неограниченно растет с увеличением ее длины.

  3. Все последовательности, для которых уровень сложности примерно равен длине последовательности: К l(х), - случайны.

  4. Подавляющее число последовательностей (почти все) несжимаемы, т.е. случайны.

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

  6. Алгоритмическая сложность любой последовательности не может превосходить количества двоичных разрядов, необходимых для записи их порядковых номеров, т.е. её энтропии. Энтропия Н произвольной последовательности длины N: , где s - количество символов в алфавите.

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



1.4. Вероятностная модель текста программы. Закон Ципфа


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

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


izumzum.ru