Реализация алгоритма внешней сортировки.

Внешние сортировки, это сортировки находящиеся во внешней памяти. Алгоритм Фон-Неймана, сортировка файлов.

Const n = 50;

M = 100;

Var a:array [1..n] of real;

B:array [1..m] of real;

C:array [1..m+n] of real;

I,j,k: integer

Begin

For i:=1 to n do

Read (a[i]);

For j:=1 to m do

Real (b[j]);

K:=1; i:=1; j:=1;

While (I<=n) and (j<=m) do begin

If a[i] <=b[i] then begin c[k]:=a[i];

I:=i+1;

End;

Else begin c[k]:=b[j];

J:=j+1; end;

K:=k+1; end;

While I <=n do begin c[k]:=a[i]; I:=i+1; End;

K:=k+1; end;

While I <=m do begin c[k]:=b[j];

J:=j+1;

K:=k+1; end;

For k:=1 to n+m do write (c[k]); end.

 

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

Хеширование – способ построения упорядоченного массива. Для того что бы определить место элемента в последовательности используется Хеш- функция: h=code (Ai) div N. N- кол-во элементов в последовательности. Code (Ai) -внутренний вид элемента

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

 

Основными структурами для хранения данных из некоторого множества являются:

1. список – O(n)

2. деревья – О(log[n])

3. массив – O(const)

 

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

-Ускорение поиска в деревьях достигается за счет структуры дерева и этот вопрос сводится к вопросу балансировки.

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

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

 

Для деревьев хеширование применяется следующим образом:

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

 

Хеш функция ставить в соответствие элементу множества S некоторый элемент другого множвества R, которая является линейно упорядоченной.

f(a)=b, a принадлежит S, b принадлежит R. Таким образом за счет f достигается преобразование множества S в множество R.

 

Элементы множества r таким образом будут использоваться в качестве ключей на основании которых элементы множества S будут помещаться в дерево на основании этих же ключей будет производится и поиск элементов в дереве. Как правило в качестве множества R, выбираются множества целых или вещественных чисел.

 

Идея использования хеширования:

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

 

Самым желаемым свойство функции H является:

H(a[k])=i[l] и при этом h(a[k])<>h(a[i]) при k<>0. для разных элементов S хотелось бы чтобы функция h возвращала разные значения. Если удастся построить h для некоторого множества S то в этом случае функция h будет называться идеальной. Как правило на практике этого достич не удется.

По этому на практике возникают ситуации когда h(a[k])=h(a[i]) при k<>0 – такие случаи называются коллизиями. Поэтому при возникновении коллизий требуется определить механизм их разрешения. Разрешение коллизий выполняется либо с помощью ре: хеширования, либо за счет использования метода цепочек.

Сформулируем общие требования функции h:

1. функция h должна быть построена на основе учета особенностей типа данных элементов множества S.

2. простота вычисления функций.

3. для функции h должен быть определен способ разрешения коллизий.

 

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

h(a)=code(a) mod N, где N – количество элементов массива(желательно чтобы равно либо больше чем количество элементов множества S). Code(a) – десятичная запись машинного представления элемента а во внутренней памяти.

 

Можно использовать особый вид хеш функций:

 

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

Пусть имеется некоторая хеш функция , для которой требуется составить набор хеш функций.

 

Линейное ре-хеширование, в этом случае набор функций вычисляется следующим образом:

+: самое просто для понимания и реализации

-: элементы для которых будут возникать коллизия, будут попадать на соседние места массива и образовывать блоки.

 

- с.в.

program Sprav;

const N=1000;

type

sprav=record

FIO:string[50];

Pol:(m,w);

Phone:String[15];

end;

var sprav:array[1..N] of TSprav;

h,i:Integer;

s:string;

function h0(s:string):integer;

var i,h:integer;

const a=3; b=5;

begin

h:=0;

for i:=1 to length(s) do h:=h+ord(s[i]);

f:=(a*h+b) mod N +1;

ho:=h;

end;

 

function hi(s:string; i:integer):integer;

begin

hi:=(h0(s)+i) mod N +1;

end;

 

\\сдесь должна быть еще 1 всп-ая проц/фнукция

procedure init;

var i:integer;

begin

for i:=1 to N do begin

sprav[i].FIO:='';

end;

 

end;

 

function search(fio:string):integer;

var h:integer;

begin

h:=h0(fio);

while((i<=N) and (Sprav[h].FIO<>fio)) and ((h<=N) and (sprav[h].FIO<>'')) do

begin

i:=i+1;

h:=hi(fio,i);

end;

if (i<=N) and (Sprav[h].FIO-fio) then

search:=h

else search:=0;

end;

end;

 

80. Понятие тестирования. Тестирование с точки зрения «черного ящика» и «белого ящика». Пошаговое, нисходящее, восходящее тестирование.

 

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

Тестирование – запуск программ на разных исходных данных и анализ результатов с целью оценки работоспособности программы.

 

Существует две стратегии тестирования: «черный ящик» и «белый ящик».

Функциональное тестирование (метод чёрного ящика) – выполняется с точки зрения пользователя системы. ii. Структурное тестирование (​метод белого ящика) – основывется на знании внутренней структуры программы.

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

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

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

 

Пошаговое тестирование

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

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

 

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

Нисходящее

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

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

 

Восходящее

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

 

Преимущества восходящего тестирования:

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

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

 

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

 

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

 

81 Понятие тестирования. Принципы тестирования.

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

Тестирование – запуск программ на разных исходных данных и анализ результатов с целью оценки работоспособности программы.

 

Принципы:

Основными принципами тестирования являются:

1)описание предполагаемых значений выходных данных или результатов должно быть необходимой частью тестового набора;

2)тесты для неправильных и непредусмотренных входных данных следует разрабатывать так же тщательно, как для правильных и предусмотренных,

3)необходимо проверять не только делает ли программа то, для чего она предназначена, но и не делает ли она то, что не должна делать; нельзя планировать

4)тестирование в предположении, что ошибки не будут обнаружены

5)вероятность наличия необнаруженных ошибок в части программы пропорциональна числу ошибок, уже обнаруженных в этой части;

6)тестирование - процесс творческий.

1. Каждый тест должен сопровождаться описанием результатов.

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

3. Проведение бета-тестирования, особенно ПП, предназначенного для рынка.

4. Результаты тестирования д.б. досканально изучены.

5. Необходимо проверить работу программы на недопустимых входных данных.

6. Необходимо сохранить использованные тесты (чтобы не пропустить имеющиеся тесты; при установка у нового заказчика неплохо пропустить их).

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

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

Тестирование проводят по следующим уровням:

1. Тестирование отдельных процедур и функций.

2. Совместное тестирование процедур и функций.

3. Тестирование функций программного комплекса.

4. Тестирование всего комплекса в целом.

На 1 и 2 может применяться структурное тестирование, на последних – функциональное. Если логика программы очень сложная, то надо провести тщательное структурное тестирование. Особая опасность в компбинациях разных условий.

 

82 Методы ручного тестирования.

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

Инспекции и сквозные просмотры

Инспекции исходного текста и сквозные просмотры являются основными методами ручного тестирования. Так как эти два метода имеют

много общего, они рассматриваются здесь совместно.

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

Вейнберга [9]. Оба метода предполагают некоторую подготовительную работу. Завершающим этапом является «обмен мнениями» – собрание,

проводимое участниками проверки. Цель такого собрания – нахождение

ошибок, но не их устранение (т. е. тестирование, а не отладка).

 

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

 

83 Понятие отладки. Методы отладки.

 

Отладка – выявление и устранение ошибок в программе, если такие обнаружены в процессе тестирования.

Отладка - это процесс локализации и исправления ошибок в программе.

Методы:

- ручного тестирования;

- индукции;

- дедукции;

- обратного прослеживания.

-силовые методы(?)

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

Метод индукции включает:

1)определение данных тестирования, имеющих отношение к ошибке;

2)анализ от частного к общему позволит выявить закономерности в данных тестирования. В результате анализа выдвигается гипотеза о причине ошибки;

3)для подтверждения гипотезы разрабатывается тесты, которые должны либо подтвердить, либо опровергнуть гипотезу;

4)если дополнительные тесты подтверждают гипотезу, можно приступать к исправлению ошибки

Для больших программ необходимо определить фрагмент программы, в котором может быть локализована ошибка.

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

1)перечисление возможных причин или гипотез:

2)использование данных тестирования для исключения некоторых возможных причин;

3)уточнение выбранной наиболее вероятной гипотезы, возможно с использованием дополнительных тестов;

4)доказательство выбранной гипотезы совпадает с п.4 и п.5 метода индукции.

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

Силовые методы

-Использование дампа (распечатки) памяти.

-Использование отладочной печати в тексте программы - произвольно и в большом количестве.

-Использование автоматических средств отладки - трассировки с отслеживанием промежуточных значений переменых.

 

Отладка – процесс, осуществляемый после удачного выполнения теста. Процесс отладки начинается при обнаружении ошибки:

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

2.фиксируется или исправляется ошибка

Методы:

1).Метод «грубой силы»

-отладка с помощью дампа памяти

-отладка в соответствии с общим предложением «расставить операторы печати по всей программе»

2).Метод индукции

Шаг 1.определение данных, имеющих отношение к ошибке

Шаг2.организация данных

Шаг3.выдвижение гипотезы

Шаг4.доказательство гипотезы

3)Метод дедукции

Шаг1.перечисление возможных причин или гипотез

Шаг2.использование данных для исключения возможных причин

Шаг3.уточнение выбранной гипотезы.

Шаг4.доказательство выбранной гипотезы.

4).Метод тестирования (заключается в использовании тестов)