8 Статистическая обработка результатов эксперимента

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

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

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

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

Для каждого i-го измерения Х_i случайная абсолютная погрешность вычисляется по формуле  = Х - Х_i, где X – истинное значение измеряемой величины.

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

Оценкой математического ожидания M[Х] служит среднее арифметическое:

Мерой рассеяния значений случайной величины служит дисперсия D[x], оценка d которой выражается формулой

 .

Меру рассеяния также характеризуют среднеквадратическим отклонением S[x], оцениваемым величиной, равной G = . Оценку приписывают каждому из N результатов наблюдений и называют погрешностью единичного измерения, стандартным отклонением или стандартом.

Для проверки вида погрешности и отбрасывания аномальных наблюдений используют критерий

V_i =

Если, например, для N = 20 выполняется V_i > 2,71 (c вероятностью 0,025), то результат i-го измерения считается грубой погрешностью и отбрасывается как аномальный.

Мерой связи между двумя множествами {a} и {b} экспериментальных данных является коэффициент корреляции

r =

Коэффициент корреляции может принимать значения от -1 до +1. Значение модуля коэффициента корреляции, равное 1, свидетельствует о функциональной зависимости между данными множеств, а нулевое его значение - о полной взаимной независимости элементов множеств.

9 Работа с данными динамической структуры.

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

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

Абстрактный тип данных «дек». Дек – это множество, состоящее из n > 0 узлов х[1], х[2],.., х[n]. Структурные свойства множества ограничиваются лишь относительным положением узлов, т.е. теми условиями, что если n > 0, то x[1] – первый узел; если 1<R<n, то R-ому узлу x[R] предшествует X[R-1] и за ним следует X[R+1]; x[n] является последним узлом. С деком можно выполнить следующие операции:

• поместить элемент (узел) в начало дека;

• взять элемент из начала дека;

• поместить элемент (узел) в конец дека;

• взять элемент из конца дека.

Абстрактный тип данных «стек». Стек – это структура типа «дек», с которым определены только две операции:

• поместить элемент (узел) в конец дека;

• взять элемент из конца дека.

В стеке реализована дисциплина доступа «последний вошел – первый вышел», т.е. данные помещаются в вершину стека и извлекаются только из неё. Стеки широко применяются при обработке различных иерархических структур, при построении компиляторов.

Абстрактный тип данных «очередь». Очередь – это дек, с которым определены операции:

• поместить элемент в начало дека;

• взять элемент из конца дека.

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

Абстрактный тип данных «список». Список – дек, с которым определены следующие основные операции:

• поместить элемент в начало дека;

• поместить элемент в конец дека;

• поместить элемент после заданного (R-того) элемента;

• взять элемент из начала дека;

• взять элемент из конца дека;

• взять элемент после заданного (R-го) элемента;

• взять заданный элемент.

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

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

2. удалить элемент из начала списка;

3. удалить элемент из конца списка;

4. удалить элемент после заданного элемента;

5. удалить заданный элемент.

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

Таким образом, написав один раз все процедуры работы со списком, можно обращаться к нему как к деку, стеку, очереди.

В зависимости от структуры элементов и организации связи между ними списки подразделяются на следующие виды:

2. линейные однонаправленные без головного элемента;

3. линейные однонаправленные с головным элементом;

4. линейные двунаправленные без головного элемента;

5. линейные двунаправленные с головным элементом;

6. циклические однонаправленные без головного элемента;

7. циклические однонаправленные с головным элементом;

8. циклические двунаправленные без головного элемента;

9. циклические двунаправленные с головным элементом.

Абстрактный тип данных «дерево». Дерево – конечное множество узлов с одним выделенным узлом, называемым корнем, другие узлы разделены на m  0 множеств B_1,B₂,…,B_m, которые не пересекаются и каждое из которых представляет дерево (поддерево).

«Упорядоченное двоичное дерево – конечное множество элементов (вершин), которое либо пусто, либо состоит из корня (вершины) с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревом этого корня» (Н. Вирт).

Упорядоченное дерево – это дерево, у которого ребра (ветви), исходящие из каждой вершины, упорядочены.

Считается, что корень дерева находится на уровне 0.

Максимальный уровень какой-либо из вершин дерева называется его глубиной или высотой.

Вершина Y, находящаяся непосредственно ниже вершины X, называется потомком X, и наоборот, вершину X называют предком Y. Если X находится на уровне I, то говорят, что Y лежит на уровне i+1.

Если элемент не имеет потомков, то его называют терминальной вершиной, или истоком, а нетерминальную вершину – внутренней вершиной.

Число непосредственных потомков внутренней вершины называют её степенью.

Максимальная степень всех вершин есть степень дерева. Число ветвей (или ребер), которое нужно пройти от корня к вершине X, называется длиной пути к X. Корень имеет длину пути 0, его прямые потомки имеют путь длиной 1 и т.д.