Пояснительная записка к курсовой работе по дисциплине «Структуры и алгоритмы обработки данных»

Научно-исследовательский университет

Томский политехнический университет

Институт Кибернетики

Кафедра ОСУ



Пояснительная записка к курсовой работе

по дисциплине «Структуры и алгоритмы обработки данных»

Вариант №14


Исполнитель

студент, 8В83 ____________ А.Н. Ролдугин

(подпись)

____________

(дата)
Руководитель

доцент ____________ О.Б. Фофанов

(подпись)

____________

(дата)


Томск 2010

Содержание

1. Моделирование абстрактных типов данных (АТД) для различных реализаций

1.1 Постановка задачи

Система состоит из трёх процессоров P1, P2, P3, очереди F, стека S и распределителя R (рис.1).В систему поступают запросы на выполнение задач трёх типов – Т1, Т2 и Т3, каждая для своего процессора. Запрос можно представить записью:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte;{тип задачи 1-Т1, 2-Т2,

3-Т3}

end;

Генератор задач



О

Ч

Е

Р

Е

Д

Ь




Распределитель задач

Стек

Процессор

Р3

Процессор

P2

Процессор

Р1

Рис.1
Поступающие запросы ставятся в очередь. Если в “голове” очереди находится задача Ti и процессор Ti свободен, то распределитель ставит задачу на выполнение в процессор Pi, а если процессор Pi занят, то распределитель отправляет задачу в стек и из очереди извлекается следующая задача. Задача из стека поступает в соответствующий ей свободный процессор только тогда, когда очередь пуста.
Модель реализации стека и очереди

1. 
   Стек на массиве в статической памяти, элементы стека – в динамической.
   
2. 
   Очередь на ДЛС. “Хвост” очереди – первый, а “голова” - последний элемент ОЛС
   

1.2 Краткое теоретическое описание реализуемых объектов

Стек – это специальный тип списка, в котором все вставки и удаления выполняются в начале(FIFO-first in first out), называемом вершиной (top). То есть всегда есть доступ только к верхнему элементу, к дальнейшим можно обращаться только после удаления первого. В нашем случае стек представлен динамической структурой: элемент стека – запись, содержащая указатель на следующий элемент.

Очередь – специальный тип списка - (queue), в котором вставка элементов осуществляется с одного конца (rear), а удаление с другого (front). В динамической реализации в записи присутствуют 3 указателя: на следующий элемент, на текущий и на предыдущий.

1.3 Набор допустимых операций

Для стека:

IndexLast () - возвращает индекс последнего элемента стека.

Size() - возвращает размер стека.

get() - удаляет элемент из вершины стека (выталкивает из стека)

add (x). Помещает элемент х в вершину стека.

Для очереди:

getLast() – возвращает последний элемент очереди.

add (x). Помещает элемент х в конец очереди.

deq() удаляет последний элемент очереди, при этом возвращая его .

Size() - возвращает размер очереди.

1.4 Результат работы программы

Вывод по разделу

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


2. Поиск информации в различных структурах данных

2.1 Постановка задачи

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

1. Реализовать алгоритмы поиска:

• 
  Алгоритм Боуэра-Мура (четный вариант)
  

2. Построить графики зависимости количества операций сравнения от количества символов в массиве.
3. Определить временную сложность алгоритма и сравнить с экспериментальными исследованиями