Федеральноеагентство по образованию
Федеральноегосударственное учреждение высшего профессионального образования
Кафедравычислительной математики и информационных технологийКурсоваяработа
По дисциплине
Структуры иалгоритмы компьютерной обработки данных
2009г.
Введение
Целью курсовойработы стала задача проектирования многофункциональной структуры компьютернойобработки данных. Рассмотрение и разработка программ с такими операциями как:найти расстановку пяти ферзей, при которой каждое поле шахматной доски будетнаходится под ударом хотя одного из них, исследовать зависимость количествасравнений в методе Шелла от выбора разных формул для вычисления шага, вTrie-дереве определить количество слов, содержащих букву А, обработка текстовыхданных, хранящихся в произвольном файле на магнитном диске. Выполнениетестирования программ для нормальных, граничных и исключительных условий. А также задачи и алгоритмы обработки больших массивовдействительных и натуральных чисел.
Глава 1. Задачи иалгоритмы обработки больших массивов действительных и натуральных чисел
1.1ОГРАНИЧЕННЫЕ ТИПЫ
Частоприходится сталкиваться с положением, когда переменной присваивается значениенекоторого типа, лежащее только внутри определенного интервала значений. Такоеположение можно подчеркнуть, определив, что указанная переменная относится кограниченному типу. Такой тип задается следующим образом
TYPE T = [min..max]
где min и max —выражения, определяющие концы такого диапазона.Отметим, что операндами этих выражений могут быть только константы.
ПРИМЕРЫ
TYPHyear = [1900„ 1999]
TYPE digit =[«0»..«9»]
Однако влегальности подобных присваиваний можно удостовериться без выполнения программылишь в тех случаях, когда речь идет о присваивании констант.
1.2МАССИВ
Вероятно,наиболее широко известная структура данных — массив. В некоторых языках толькомассивы и существуют. Массив состоит из компонент, причем все они одного типа,называемого базовым. Поэтому структура массивов однородна. Кроме того, массивыотносят к так называемым структурам со случайным доступом. Для того чтобыобозначить отдельную компоненту, к имени всего массива добавляется индекс, он-тои выделяет нужную компоненту. Индекс — это значение специального типа,определенного как тип индекса данного массива.
TYPE T = ARRAY[TI]OF T0
Спомощью индекса можно выделить любую отдельную компоненту любого массива. Еслиесть переменная-массив х, то селектор для массива обозначается с помощью именисоответствующего массива, за которым следует необходимый индекс i требуемой компоненты — xi или x[i]. Из-затрадиционности первого, обычного обозначения компоненты массивов стали называтьпеременными с индексами.
Обычныйприем работы с массивами, в особенности с большими массивами, — выборочноеизменение отдельных его компонент, а не конструирование полностью новогосоставного значения. При этом переменная-массив рассматривается как массивсоставляющих переменных и возможно присваивание отдельным компонентам,например, x[i,j ]:= 0.125. Хотявыборочное изменение приводит только к коррекции одной-единственной компоненты,с концептуальной точки зрения мы должны рассматривать его как изменение всегосоставного значения. Полученный результат может оказаться за пределами интервала,выделенного для индексов данного массива. Мы будем предполагать, что«порядочная» вычислительная система в случае ошибочного обращения кнесуществующей компоненте массива должна давать некоторое предупреждающеесообщение.
Составляющиемассивов сами могут быть составными значениями. Переменная-массив, компонентыкоторой опять же массивы, называется матрицей. Например,
М: ARRAY[1..1O] OF Row
этомассив, состоящий из десяти компонент (строк), каждая из которых состоит изпяти компонент типа REAL, и называетсяматрицей размером 10X5 с вещественными составляющими.
Еслинеобходимо выполнить некоторую операцию надо всеми компонентами массива или надсоседними компонентами некоторой секции массива, то для этого удобновоспользоваться оператором цикла. В приведенном примере вычисляется суммаэлементов и отыскивается максимальный элемент массива.
1.3ПРЕДСТАВЛЕНИЕ МАССИВОВ
Смыслиспользования в программировании абстрактных понятий заключается в том, чтопрограмму можно построить, понять и проверить, основываясь на законах,управляющих именно этими понятиями.
Любоепредставление структуры массива заключается в отображении массива(абстрактного) с компонентами типа Т на память, которая представляет собоймассив с компонентами типа WORD.
Надоучитывать следующие соображения:
1. Выравнивание уменьшает используемую память.
2. Отказ от выравнивания может привестик необходимости использования доступа к части слова.
3. Организация доступа к части словаможет на столько увеличить размер оттранслированной программы, что выигрышаиз-за отказа от выравнивания не будет.
Вбольшинстве языков программирования программист не имеет возможности управлятьпредставлением абстрактных данных.
массив файл алгоритм обработка
1.4ПОСЛЕДОВАТЕЛЬНОСТИ
Массивы- это гибкая структура данных. Размер массива может быть очень велик и неумещаться в памяти компьютера, в этих случаях данные хранятся на магнитныхносителях. Такие массивы размеры, которых очень велики, принято называтьпоследовательностями. Последовательностный тип можно было бы описать следующимобразом:
TYPE T = SEQUENCE OF To
Уже изописания ясно, что все элементы последовательности имеют один и тот же тип.Последовательность s из п элементовмы будем обозначать s = , причем N называется длинойпоследовательности. Прямое следствие бесконечности мощностипоследовательностного типа — невозможность выделить для соответствующейпеременной память заданного размера. Вместо этого мы должны выделять память впроцессе выполнения программы по мере роста последовательности. Если жепоследовательность уменьшается, то память можно и возвращать. В любом случаеследует пользоваться некой схемой динамического распределения.Последовательности по существу присутствуют во всех приложениях вычислительныхмашин, они как бы вездесущи. Данные такой структуры превалируют во всех техслучаях, когда идет работа с памятями разного вида, т. е. когда данныепередаются из внешней памяти, скажем дисков или лент, в оперативную, главнуюпамять и обратно.
Преимуществотакой приверженности последовательному доступу, который, как бы то ни было,представляет собой серьезное ограничение, заключается в относительной простотетребуемого механизма управления памятью. Но еще более важной, если речь идет обобменах данными со вторичной памятью, выглядит возможность пользоватьсяэффективной техникой буферизации. Последовательный доступ позволяет нам для«перекачки» данных между памятями различного вида использовать непрерывныепотоки данных. Буферизация предполагает, что части потока накапливаются в такназываемых буферах, а затем, уже при заполнении всего буфера, передаются куданужно. В результате, что особенно важно, более эффективно используетсявторичная память.
Нижеприведеннаячасть программы показывает как обычно реализуется последовательность
DEFINITION MODULE FileSystem;
FROM SYSTEM IMPORT WORD;
CONST MaxLength = 4096:
TYPE Sequence = RECORD pos, length: CARDINAL;
eof: BOOLEAN;
a: ARRAY [0 „ Maхength-1 OF WORD
END;
PROCEDURE Open(VARf; Sequence):
PROCEDURE WriteWord(VAR f: Sequence; w; WORD)!
PROCEDURE Reset(VAR f:Sequence);
PROCEDURE ReadWord(VAR f: Sequence; VAR W; WORD);
PROCEDURE Close(VAR f: Sequence);
END FileSystem.
Обратитевнимание, что в этом примере максимальная достижимая длина последовательности —произвольная константа. Если в какой-либо программе случится, чтопоследовательность станет длиннее, то это будет рассматриваться не как ошибка впрограмме, а скорее как неадекватная реализация. С другой стороны, операциячтения за фактическим текущим концом последовательности действительно должнасчитаться ошибкой в программе.
1.5СОРТИРОВКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Прямоеслияние
К сожалению, алгоритмы сортировки,приведенные в предыдущем разделе, невозможно применять для данных, которыеиз-за своего размера не помещаются в оперативной памяти машины и находятся,например, на внешних, последовательных запоминающих устройствах памяти, таких,как ленты или диски.
В такомслучае мы говорим, что данные представляют собой (последовательный) файл…Наиболее важный из них — сортировка с помощью слияния. Слияние означаетобъединение двух (или более) последовательностей в одну-единственнуюупорядоченную последовательность с помощью повторяющегося выбора из доступных вданный момент элементов. Слияние намного проще сортировки, и его используют каквспомогательную операцию в более сложных процессах сортировкипоследовательностей. Одна из сортировок на основе слияния называется простым,слиянием. Она выполняется следующим образом:
1. Последовательность а разбивается надве половины: b и с.
2. Части b и с сливаются, при этом одиночные элементы образуютупорядоченные пары.
3. Полученная последовательность подименем о вновь обрабатывается как указано в пунктах 1, 2; при этом упорядоченныепары переходят в такие же четверки.
4. Повторяя предыдущие шаги, сливаемчетверки в восьмерки и т. д., каждый раз «удваивая» длинуслитыхподпоследовательностей до тех пор, пока не будет упорядочена целиком всяпоследовательность.
Действияпо однократной обработке всего множества данных называются фазой. Наименьший жеподпроцесс, повторение которого составляет процесс сортировки, называется проходомили этапом.
Теперьперейдем к более детальному рассмотрению программы слияния. Данные мы будемпредставлять как массив, обращение к элементам которого, однако, идет строгопоследовательно. Если рассматривать массив как последовательность элементов,имеющих два конца, то его весьма просто можно использовать вместо двухпоследовательностей. Мы будем при слиянии брать элементы с двух концов массива,а не из двух входных файлов.Направление пересылки сливаемых элементовизменяется на первом проходе после каждой упорядоченной пары, на втором — послекаждой упорядоченной четверки и т. д., равномерно заполняя две выходныепоследовательности, представляемые двумя концами одного массива. После каждогопрохода массивы «меняются ролями», выходной становится входным и наоборот.
Еслиобъединить два концептуально различных массива в один-единственный, но двойногоразмера, то программа еще более упрощается. В этом случае данные представляютсятак:
a: ARRAY[1..2*n] OF item
Начальноезначение р равно 1, и перед каждым последующим проходом она удваивается. Дляпростоты мы предполагаем, что всегда n равно степени двойки. Таким образом, первая версия программы сортировкис помощью простого слияния имеет такой вид
PROCEDURE MergeSort:
VAR i, j, k, L: index; up: BOOLEAN; p: INTEGER;
BEGIN up: = TRUE; p: = 1;
REPEAT инициации индексов;
IFupTHEN i:=l; j:=n; k:=n+1;L:=2*n
ELSE k:= l;L:= n; i := n+1; j := 2*n
END;
слияниер-наборов из i- и j-входов в k- и L-выходы;
Up:= ~up; p:=2*p
UNTIL p = n
END MergeSort
Следующийэтап — уточнение операторов, выделенных курсивом. Ясно, что процесс слияния n элементов сам представляет собойпоследовательность слияний последовательностей, т. е. р-наборов. После каждоготакого частичного слияния выход переключается с нижнего на верхний конецвыходного массива и наоборот, что гарантирует одинаковое распределение в обоихнаправлениях. Если сливаемые элементы направляются в левый конец выходногомассива, то направление задается индексом к и после пересылки очередногоэлемента он увеличивается на единицу. Если же элементы направляются в правыйконец, то направление задается индексом L и он каждый раз уменьшается. Для упрощения фактическогооператора слияния будем считать, что направление всегда задается индексом к, нопосле слияния р-набора будем менять местами значения к и L, приращение же всегда обозначаетсячерез h, имеющее значение либо 1, либо —1.
Посколькуна каждом проходе р удваивается и сортировка заканчивается при р> n, то всего требуется [logn] проходов. На каждом проходе поопределению копируются по одному разу все n элементов
Алгоритмсортировки слиянием выдерживает сравнение даже с усовершенствованными методами.Однако, хотя здесь относительно высоки затраты на работу с индексами, решающеезначение играет необходимость работать с памятью размером 2n. Поэтому сортировка слиянием длямассивов, т. е. для данных, размещаемых в оперативной памяти, используетсяредко.
Естественноеслияние
В случаепрямого слияния мы не получаем никакого преимущества, если данные в начале ужечастично упорядочены. Размер сливаемых на к-м проходе подпоследовательностейменьше или равен 2к и не зависит от существования более длинных ужеупорядоченных подпоследовательностей, которые можно было бы просто объединить.Фактически любые две упорядоченные подпоследовательности длиной m иn можно сразу сливать в одну последовательность из m + n элементов. Сортировка, при которой всегда сливаются двесамые длинные из возможных подпоследовательностей, называется естественнымслиянием.
Упорядоченныеподпоследовательности часто называют строками. Однако так как слово «строка»еще чаще употребляется для названия последовательности символов, то мы дляупорядоченных подпоследовательностей будем использовать термин «серия». Поэтомув сортировке естественным слиянием объединяются (максимальные) серии, а непоследовательности фиксированной (заранее) длины. Если сливаются двепоследовательности, каждая из nсерий, то результирующая содержит опять ровно n серий. Следовательно, при каждом проходе общее число серииуменьшается вдвое и общее число пересылок в самом плохом случае равно n*|logn|, а в среднем даже меньше. Ожидаемое же числосравнений, однако, значительно больше, поскольку кроме сравнений, необходимыхдля отбора элементов при слиянии, нужны еще дополнительные — междупоследовательными элементами каждого файла, чтобы определить конец серии.
Следующимнашим упражнением будет создание алгоритма естественного слияния с помощью тогоже приема пошагового уточнения, который применялся при объяснении алгоритмапрямого слияния.
VARL: INTEGER; а, b, с: Sequence
REPEAT Reset(a); Reset(b); Reset(c):
Распределение;(*с распределяется в а иb*)
Reset(a); Reset(b); Reset(c);
L: = 0; слияние (*аи b сливаются в с *)
UNTILL = 1
Две фазыявно выделяются как два различных оператора. Теперь их надо уточнить, т. е.переписать с большей детализацией. Уточненное описание распределения (distribute) приведены ниже .
RЕРЕАТ copyrun(c, a);
IF~c.eof THENcopyrun(c,b)END
UNTIL с.eof
REPEAT mergerun; L: = L+1
UNTIL b.eof;
IF ~a.eof THEN copyrun(a, c); L := L+l END
Такойметод распределения приводит предположительно к следующему результату: либо в аи b будет поровну серий, либо в а будетна одну больше. Поскольку соответствующие пары серий сливаются в одну, то b а может оказаться еще одна лишняясерия, ее нужно просто скопировать.
Вместотого чтобы программировать явно этот механизм в нашей программе, мыпредпочитаем определить еще один уровень абстракции. Это будет новый модуль сименем Sequences, для пользователя он заменит модуль FileSystem. Кроме того, мы определяем соответственно и новый тип дляпоследовательности, но он будет ссылаться на Sequence из FileSystem. В этом новомтипе будет фиксироваться не только конец последовательности, но и конец сериии, конечно же, первый элемент оставшейся части последовательности. Новый тип исвязанные с ним операции задаются таким модулем определений:
DEFINITION MODULE Sequences;
IMPORT FileSystem;
TYPE item = INTEGER;
Sequence = RECORD first: item;
eor.eof: BOOLEAN;
f: FileSystem.Sequence
END;
PROCEDURE OpenSeq(VARs: Sequence);
PROCEDURE OpenRandomSeq(VARs: Sequence; length, seed: INTEGER); PROCEDUREStartRead(VARs: Sequence);
PROCEDURE StartWrite(VAR s: Sequence);
PROCEDURE copy(VAR x, y: Sequence);
PROCEDURE CloseSeq(VAR s: Sequence);
PROCEDURE ListSeq(VAR s: Sequence);
END Sequences.
Процесссравнения и выбора ключей при слиянии серий заканчивается, как толькоисчерпается одна из двух серий. После этого оставшаяся неисчерпанной серияпросто передается в результирующую серию, точнее копируется ее «хвост».
Сбалансированноемногопутевое слияние
Затратына любую последовательную сортировку пропорциональны числу требуемых проходов,так как по определению при каждом из проходов копируются все данные. Один изспособов сократить это число — распределять серии в более чем двепоследовательности. Слияние rсерий поровну распределенных в N последовательностей даст в результате r/N серий. Второй проход уменьшит это число до г/N2, третий — до r/N3 и т. д., после к проходов останется r/Nkсерий. Поэтому общее число проходов,необходимых для сортировки nэлементов с помощью N-путевогослияния, равно
k = [logNn]
В программесортируется массив файлов. Мы начнем с определений и к двум уже знакомым типам item и sequence добавим тип
seqno = [l..N]
Теперьможно представить алгоритм.
MODULE BalancedMerge;
VAR1, j: seqno;
L: INTEGER; (* число распределяемых серий *).
t: ARRAY seqno OF seqno;
BEGIN (*распределение начальных серий в- t[l] ...t[Nh] *)
j:=Nh;L:=0;
REPEAT
IF j
копированиеодной серии из f0 впоследовательность J;
L:=L+1
UNTIL fo.eof;
FORi:=l TO N DO t[i]:=I END;
REPEAT (* слияние изt[l]...t[nh] в t[nh+l]...i[n]*)
установкавходных последовательностей;
L: = 0;
j:=Nh+l; (*j-индекс выходной последовательности*)
REPEAT L:=L+1;
слияниеа серий с входов b i(j);
IF j
UNTIL все входы исчерпаны
переключениепоследовательностей
UNT1L L = 1
(•отсортированная последовательность в t [1 ] *)
END BalancedMerge,
Многофазнаясортировка
Мы ужепознакомились с необходимыми приемами и в достаточной мере готовы кисследованиям и программированию, связанным с новыми, более эффективными, чемсбалансированная сортировка, алгоритмами. В основе нашего очередногоусовершенствования лежит отказ от жесткого понятия прохода и переход к болееизощренному использованию последовательностей. Мы больше не будем считать, чтоесть N/2 входов и столько же выходов и онименяются местами после каждого отдельного прохода. Более того, уже само понятиепрохода делается расплывчатым. Новый метод был изобретен Р. Гилстэдом [2.3] иназывается многофазной сортировкой (Polyphase Sort).
Многофазнаясортировка более эффективна, чем сбалансированная, поскольку она имеет дело сN—1-путевым слиянием, а не с N/2-путевым,если она начинается с N последовательностей. Ведь число необходимых проходовприблизительно равно logN *n, где n — число сортируемых элементов, а N — степень операциислияния, — это и определяет значительное преимущество нового метода.
Фактическиоперация слияния почти идентична той же операции в сортировке с помощью N-путевого слияния, разница только втом, что здесь алгоритм исключения последовательности несколько проще.
Глава 2. Практические задачи по алгоритмам обработки данных
2.1 Решение задачи о пятиферзях
Постановка задачи: Найтирасстановку пяти ферзей, при которой каждое поле шахматной доски будетнаходится под ударом хотя одного из них.
Задача опяти ферзях — хорошо известный пример использования метода проб и ошибок и алгоритмовс возвратом. Для подобных задач характерно отсутствие аналитического решения.Вместо этого они требуют большого объема изнурительных вычислений, терпения иаккуратности. Поэтому такие задачи стали почти исключительно прерогативойвычислительных машин, которые обладают этими свойствами в гораздо большейстепени, чем люди, даже гениальные.
Посколькумы знаем, что по шахматным правилам ферзь бьет все фигуры, расположенные на тойже горизонтали, вертикали или диагонали доски, то мы заключаем, что каждаявертикаль может содержать одного и только одного ферзя.
Осталось решить, какпредставить расположение пяти ферзей на доске. Очевидно, что доску можно былобы вновь изобразить в виде квадратной матрицы, но после некоторого размышлениямы обнаруживаем, что такое представление значительно усложнило бы проверкубезопасности позиции. Это крайне нежелательно, поскольку такая операциявыполняется наиболее часто. Поэтому нужно выбрать представление, котороенасколько возможно упростит эту проверку. Лучше всего сделать наиболеедоступной ту информацию, которая действительно важна и чаще всего используется.В нашем случае это не расположение ферзей, а информация о том, помещен ли ферзьна данной горизонтали или диагонали.
2.2 Сортировка Шелла
Постановказадачи: Написать программу, которая реализует сортировку Шелла.
В 1959г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямоговключения. Сначала отдельно группируются и сортируются элементы, отстоящие другот друга на расстоянии 4. Такой процесс называется четверной сортировкой. Послепервого прохода элементы перегруппировываются— теперь каждый элемент группыотстоит от другого на две позиции — и вновь сортируются. Это называется двойнойсортировкой. И наконец, на третьем проходе идет обычная или одинарнаясортировка.
Ясно,что такой метод в результате дает упорядоченный массив, и, конечно же, сразувидно, что каждый проход от предыдущих только выигрывает. Так же очевидно, чторасстояния в группах можно уменьшать по-разному, лишь бы последнее былоединичным, ведь в самом плохом случае последний проход и сделает всю работу.Все t расстояний обозначаютсясоответственно hi, h2, ..., ht, для них выполняются условия
ht = l. hJ+1
Каждая h-сортировка программируется каксортировка с помощью прямого включения. Причем простота условия окончанияпоиска места для включения обеспечивается методом барьеров.
2.3 Trie-дерево
Постановказадачи: В Trie-дереве определить количество слов, содержащих букву А.
Деревом называетсясвязный ориентированный граф без циклов, каждая вершина которого имеет толькоодно входящее ребро.
Узел и поддеревья связанымежду собой ветвями. Число ветвей, выходящих из узла, определяют его арность.Если все узлы имеют одинаковую арность, равную n, то такая структура называется n-арным деревом. Если n = 2, то дерево называется бинарным.
Одним извидов сильно ветвящихся деревьев является Trie-дерево. Название Trie-дерево происходит отискусственно образованного слова trie, от полного слова retrieval (поиск).Такое дерево используется тогда, когда ключами поиска являются достаточнокороткие слова. Чем больше коротких слов содержится в Trie-дереве, темэффективнее соотношение количества слов к количеству памяти, расходуемой подхранение элементов в Trie-дереве. Каждый ключ в Trie-дереве можно рассматриватькак список символов, а все списки вместе — как дерево поиска. В такой структуреузлу уровня i + 1 ставится в соответствие i-ый символ слова, поэтому каждый узел содержит лишь одинсимвол. Методы поиска по такому дереву экономны по памяти и по времени.
Чтобы найти элемент втаком дереве, нужно, пройдя первый куст дерева, собрать слово. Затем, используялюбой из методов поиска, найти в этом слове нужную нам подстроку. Если она существует,то функция поиска возвращает значение строки, в которой содержится заданнаяподстрока. Если запустить цикл, в котором найденные слова мы будем удалять, томы удалим все слова из дерева, которые содержат указанную подстроку.
2.4 Обработка текстовых данных, хранящихся в текстовомфайле
Постановка задачи:подсчитать число слов с чётной длиной.
В настоящее времятекстовые файлы получили огромное распространение. Реализация программпредставляет собой определенный алгоритм, где данные хранятся не в самойпрограмме, а в отдельном файле. Программа в ходе работы к текстовуму файлуобращается в течение работы два раза, для получения обрабатываемых данных и длявывода результата работы. В основе программы лежит отсортировывание слов четнойи нечетной длины. Это происходит по средствам сравнивания длин слов.
Заключение
В курсовой работе рассмотреныметоды обработки больших массивов натуральных и действительных чисел. Этотвопрос очень актуален в наше время, потому что в настоящее время размеробрабатываемых данных постоянно увеличивается.
Также помня о задачахсовременности, не стоит забывать и о логических задачах, которые решаютсятолько по средствам вычислительных машин. Программ о пяти ферзях именно такая.Еще вовремя наших дедушек задумывались о ее решение, но только сейчас она сталареализуемой.
В этой курсовой работетак же рассмотрены такие задачи, как: сортировка Шелла, нахождение элементов в Trie-дереве и задачу с текстовымиданными.
Эти задачи очень частоприменяемы и программисты часто используют их для решения более сложных икомплексных задач. Поэтому решение этих задач является большим шагом на пути ктому, чтобы разрабатывать новые способы для обработки данных.
Список литературы
1. Вирт Н. Алгоритмы и структуры данных.— СПб.: Невский диалект, 2001. 352 с.
2. Дмитриева М. В… Кубенский А. А.Турбо Паскаль и Турбо Си: построение и обработка структур данных: Учебноепособие. — СПб.: Изд-во С.- Петербургского университета, 1995. — 245 с.
3. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск: Пер. с англ. — М.: Вильяме, 2000. — 822 с.
4. Мейер Д., Бодуэн К. Методыпрограммирования. Т. 1,2.— М.: Мир, 1985.
5. Вирт Н. Алгоритмы и структурыданных+программы. — СПб.: Невский диалект, 2001. — 406 с.