рефераты рефераты
Главная страница > Курсовая работа: Алгоритмы обработки больших массивов. Алгоритмы обработки данных  
Курсовая работа: Алгоритмы обработки больших массивов. Алгоритмы обработки данных
Главная страница
Банковское дело
Безопасность жизнедеятельности
Биология
Биржевое дело
Ботаника и сельское хоз-во
Бухгалтерский учет и аудит
География экономическая география
Геодезия
Геология
Госслужба
Гражданский процесс
Гражданское право
Иностранные языки лингвистика
Искусство
Историческая личность
История
История государства и права
История отечественного государства и права
История политичиских учений
История техники
История экономических учений
Биографии
Биология и химия
Издательское дело и полиграфия
Исторические личности
Краткое содержание произведений
Новейшая история политология
Остальные рефераты
Промышленность производство
психология педагогика
Коммуникации связь цифровые приборы и радиоэлектроника
Краеведение и этнография
Кулинария и продукты питания
Культура и искусство
Литература
Маркетинг реклама и торговля
Математика
Медицина
Реклама
Физика
Финансы
Химия
Экономическая теория
Юриспруденция
Юридическая наука
Компьютерные науки
Финансовые науки
Управленческие науки
Информатика программирование
Экономика
Архитектура
Банковское дело
Биржевое дело
Бухгалтерский учет и аудит
Валютные отношения
География
Кредитование
Инвестиции
Информатика
Кибернетика
Косметология
Наука и техника
Маркетинг
Культура и искусство
Менеджмент
Металлургия
Налогообложение
Предпринимательство
Радиоэлектроника
Страхование
Строительство
Схемотехника
Таможенная система
Сочинения по литературе и русскому языку
Теория организация
Теплотехника
Туризм
Управление
Форма поиска
Авторизация




 
Статистика
рефераты
Последние новости

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

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

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

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

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

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

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

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

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 = <s0, s1,s2, ..., sn-1>, причем 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.  Повторяя предыдущие шаги, сливаем четверки в восьмерки и т. д., каждый раз «удваивая» длинуслитых подпоследовательностей до тех пор, пока не будет упорядочена целиком вся последовательность.

Страницы: 1, 2, 3

рефераты
Новости