Алгоритмы обработки больших массивов. Алгоритмы обработки данных

Федеральное агентство по образованию

Федеральное государственное учреждение высшего профессионального образования

Кафедра вычислительной математики и информационных технологий

Курсовая работа

По дисциплине

Структуры и алгоритмы компьютерной обработки данных

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. Организация доступа к части слова может на столько увеличить размер оттранслированной программы, что выигрыша из-за отказа от выравнивания не будет.

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

массив файл алгоритм обработка