Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка icon

Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка



НазваниеН. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка
Дата конвертации28.08.2012
Размер182.2 Kb.
ТипПояснительная записка
1. /Расчетно-пояснительная записка.docН. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка



Московский государственный технический университет им. Н.Э. Баумана

Факультет информатики и систем управления

Кафедра Компьютерные системы и сети


Расчетно-пояснительная записка

к курсовой работе на тему:

Алгоритмы сортировки


Студент: ____________ (Огнев В. А.) Группа ИУ6-21.


Руководитель: ______________ (Пугачёв Е. К.)


Москва 2001


Аннотация.

В данной расчётно-пояснительной записке рассмотрены основные этапы разработки обучающей программы «Алгоритмы сортировки», а именно: анализ задания, выбор технологии, языка и среды разработки; определение структуры программного продукта; разработка интерфейса пользователя; описание реализации программного продукта; выбор стратегии тестирования и разработка тестов. В Приложение 1 помещено развернутое техническое задание на данный проект. В Приложение 2 помещено руководство пользователя программы «Алгоритмы сортировки». В Приложении 3 даны словесные описания алгоритмов сортировки, реализованных в данной программе.

Содержание

Введение……………………………………………………4

1. Анализ задания и выбор технологии, языка и среды разработки. 5

2. Определение структуры программного продукта 7

2.1. Анализ процесса обработки информации и выбор структур 7

данных для ее хранения 7

1.2.Описание основных алгоритмов предметной области 8

2.3. Построение структурной схемы программного продукта 11

3. Разработка интерфейса пользователя 12

3.1. Общие положения. Выбор формы диалога 12

3.2. Разработка форм ввода-вывода информации 13

3.3. Определение множества обрабатываемых событий 14

4. Описание реализации программного продукта. 16

4.1 Разработка иерархии классов программы 16

4.2 Разработка обработчиков событий 16

5. Выбор стратегии тестирования и разработка тестов 20

Заключение……………………………………………………………………23

Приложение 1. Техническое задание.

Приложение 2. Руководство пользователя.

Приложение 3. Описания алгоритмов сортировки.

Введение.


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

1.Анализ задания и выбор технологии, языка и среды разработки.



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

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

Итак, при разработке интерфейса пользователя программы «Алгоритмы сортировки» будет использоваться объектный подход в совокупности с технологией событийного программирования, т.е. методы создаваемых классов будут являться обработчиками событий. Обработчики же событий будут выполнены по правилам процедурного программирования.

В соответствие с техническим заданием (пункт 3.4), в качестве языка программирования выбран язык Object Pascal 9.0 и разработка будет проводиться в среде Delphi 5.0, которая позволяет визуально создавать интерфейс программы, используя большую библиотеку стандартных классов (компонент). Основным достоинством данной среды, является то, что обработку сообщений операционной системы она заменяет обработкой событий, что освобождает от необходимости расшифровки сообщений системы и тем самым существенно упрощает разработку программного продукта.

2.Определение структуры программного продукта

2.1. Анализ процесса обработки информации и выбор структур

данных для ее хранения


Из требований к функциональным характеристикам программы (пункт 3.1 технического задания) следует, что в программе в качестве основной структуры для хранения данных должен использоваться одномерный массив чисел. Копия этого массива должна передаваться на сортировку по выбранному алгоритму. (На сортировку должна передаваться именно копия массива, так как может потребоваться отсортировать один и тот же массив различными методами, например, обычным и усовершенствованным «методами пузырька»). Количество элементов исходного массива может изменяться в процессе работы программы. Так как разрабатываемая программа предназначается для использования во время учебных занятий, то процесс единичной сортировки не должен продолжаться слишком долго (не более 5 мин), поэтому максимальное количество элементов исходного массива можно ограничить цифрой 200 000. Для экономии оперативной памяти элементами этого массива пусть будут целые числа от 0 до 255 (на хранение одного такого числа необходим 1 байт памяти). В языке Object Pascal 9.0 этот массив можно реализовать по одному из двух способов: либо как статический, либо как динамический. При реализации по первому варианту необходимо объявить массив на максимальное (200 000) количество элементов, который будет существовать всё время работы программы. При передаче этого массива по значению в процедуры сортировки потребуется ещё 200 кбт памяти. Кроме того, в процедуры сортировки необходимо будет передавать количество элементов в массиве, которые нужно сортировать. При реализации по второму варианту массив с заданным пользователем числом элементов будет создаваться в процессе работы программы. При такой реализации, массив с 20 000 элементов будет занимать в памяти 20 кбт, а не 200, как в первом варианте. Однако, надо заметить, что работа с динамическим массивом происходит значительно медленнее. Очевидно, что второй вариант предпочтительнее, так как он экономит ресурсы машины


    1. Описание основных алгоритмов предметной области




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


  • методом прямого выбора;

  • «методом пузырька» (метод прямого обмена);

  • усовершенствованным «методом пузырька» (шейкерная сортировка);

  • методом прямой вставки;

  • методом бинарного дерева;

  • по алгоритму Шелла;

  • по алгоритму Хоара;


Словесное описание данных алгоритмов помещено в Приложение 3. Здесь же приведём подробное описание лишь самого быстрого алгоритма сортировки – алгоритма Хоара (рис. 1).


Список переменных алгоритма:

a[1..nn] – сортируемый глобальный массив;

k, n – номера крайних элементов сортируемой части массива;





ложь истина


ложь истина


ложь истина


ложь истина


ложь истина


ложь истина





Рис. 1. Алгоритм Хоара


i - текущий индекс массива, увеличивающийся на единицу при продвижении по массиву слева направо;

j - текущий индекс, уменьшающийся на единицу при продвижении по массиву справа налево;

х – значение элемента – медианы сортируемой части массива a[1..nn]

Суть алгоритма Хоара заключается в следующем. Найдем такой элемент массива, который разобьет его на две части: те элементы, которые меньше делящего элемента, и те, которые по величине не меньше его (т.е. как бы отсортируем один элемент, определив его окончательное местоположение). Этот элемент назовём медианой массива (хотя, строго говоря, под медианой понимают средний элемент упорядоченного массива). После этого применим ту же процедуру к более коротким левой и правой частям массива, затем к частям частей и т.д. Как видно, данный алгоритм является рекурсивным. При его реализации приходится иметь дело с древовидной рекурсией. Конечность глубины рекурсии в процедуре (см. Приложение 3) гарантируется тем, что размер сортируемой части массива на каждом уровне рекурсии уменьшается хотя бы на единицу.

Текст процедуры, реализующей данный алгоритм, а также пример её вызова помещены в Приложение 2.

Алгоритм вывода графических пояснений к методу Хоара не намного отличаются от алгоритма, приведённого на рис.1 (обмен элементов a[i] и a[j] прорисовывается на экране и в «сортируемом» массиве всего 10 элементов).


2.3. Построение структурной схемы программного продукта




Так как было решено использовать объектно-ориентированный подход лишь при разработке пользовательского интерфейса, то очевидно будет необходимо определить лишь один объект, ответственный за диалог с пользователем – главную экранную форму программы MyForm.


создать


завершить


Рис. 2. Структурная схема программного продукта (объектная декомпозиция).


Методы класса, к которому принадлежит обект MyForm будут определены после разработки главной формы программы.

3.Разработка интерфейса пользователя




3.1. Общие положения. Выбор формы диалога



При разработке интерфейса пользователя наиболее важным является вопрос выбора формы диалога между программой и пользователем. Существует три формы диалога:

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

2). Табличная – включает следующие конкретные типы:

а) выбор операции на исполнение из меню;

б) заполнение и редактирование шаблонов данных;

в) комбинированный;

Достоинства табличной формы диалога – это простота и лёгкость в освоении (поэтому она максимально подходит для использования в большинстве обучающих программ).

3). Фразовая – использует ограниченный естественный язык, причём инициатором шага диалога может быть как пользователь, так и система.

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

3.2. Разработка форм ввода-вывода информации










Рис. 3. Экранная форма (при активизации различных страниц)


Как видно из рисунка 3 на форме программы расположена многостраничная панель, позволяющая экономить пространство окна.

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

На второй странице панели выделена область для вывода графической информации (цвет этой области совпадает с цветом панели), имеется 3 кнопки обычного вида и группа из 2 радиокнопок, позволяющая задавать скорость выдачи пояснений и их детализацию.


3.3. Определение множества обрабатываемых событий



На рисунке 4 показан граф состояния интерфейса и обозначены события, при которых состояние интерфейса изменяется.

События:

С1 – активация формы

С2 – нажатие на кнопку «Сортировка»

С3 – нажатие на кнопку «Очистить таблицу»

С4 – нажатие кнопки «Закрытие программы»

С5 – счелчок по странице «Графические пояснения»

С6 – счелчок по странице «Сравнение алгоритмов»

С7 – нажатие кнопки «Нарисовать»

С8 – выбор первого пункта в списке доступных методов сортировки

С9 – счелчок по радиокнопке

С10 –нажатие кнопки «Далее»


Рисунок 3


Рис 4. Граф состояния интерфейса (отдельно)


С11 – нажатие кнопки «Сброс»

Примечание: В процессе работы программы в любой момент возможно переключение между страницами «Сравнение алгоритмов» и «Графические пояснения», однако переходы между этими состояниями (за исключением одного) не показаны, чтобы рисунок не потерял ясность.


4.Описание реализации программного продукта.

4.1 Разработка иерархии классов программы



Диаграмма классов программы показана на рисунке 5. При разработке данной диаграммы максимально использовались возможности среды Delphi 5.0. Почти все методы разработанного класса являются обработчиками событий в соответствие с графом состояния интерфейса. Метод Delay осуществляет временную задержку.


4.2 Разработка обработчиков событий


Приведём обобщённые алгоритмы нескольких обработчиков событий.

Обработчик события нажатия на кнопку «Сортировка» TMyForm.GoSortButtonClick (см. рис. 6) использует три переменных типа TТime: time1, time2 и dt для записи соответственно моментов времени начала и конца сортировки массива. Dt:=time2-time1. Ветвление осуществляется в зависимости от значения свойства ListBoxMethods1.itemindex. При этом в процедуру сортировки передаётся копия глобального массива а[1..nn]. Процедура сортировки изменяет глобальную переменную AmountComprise (счётчик количества сравнениё в процессе сортировки). Вначале и в конце работы данного обработчика происходит изменение экранной формы (некоторые её компоненты становятся недоступными и наоборот).

Обработчики TMyForm.ButtonDrawClick устроен сложнее. Он может вызывать процедуры вывода графических пояснений: GrafBTree; GrafHoara

2 1


1 1


1 1 1 1

1 1

1 1

1 1 2

1

1

1 1 3

1 1

1


->FormActivate 1 6

ButtonGoSortClick 2

ButtonGenerateArrayClick

ButtonClearGridClick 1

ButtonDrawClick

Delay 2

ButtonNextClick

ButtonResetClick

ListBoxMethods2Click


Условные обозначения:




- классы Delphi - наследование


- класс, созданный 3 1 - включение

при решении задачи объектных полей


-> Xx - методы

Рис. 5. Диаграмма классов.


и GrafShell. Каждая из этих процедур также имеет сложную структуру. Рассмотрим, например, процедуру вывода графических пояснений к алгоритму Хоара. Она в своём теле содержит 4 вспомогательных процедуры и одну вспомогательную функцию (см. рис. 7).







Time1:= текущее время








Time2:= текущее время

Dt:=Time2-Time1



Рис. 6 .Алгоритм работы обработчика TMyForm.GoSortButtonClick.





Рис. 7. Разработка процедуры выдачи графических пояснений GrafHoara().

Функция CalCol(i,st,ed) возвращает значение типа TСolor – цвет, которым необходимо закрашивать ячейку массива с номером i, если st и ed – границы сортируемой части массива.

Процедура Exchange(st,ed,a,b) осуществляет вывод на экран процесса обмена элементов сортируемого массива с индексами a и b, причём st и ed – также границы сортируемой части массива.

Процедура DoComment() выдаёт текстовые пояснения о ходе сортировки.

Процедура DrawSquare(st,ed) осуществляет отрисовку всех ячеек массива с индексами от st до ed.

Процедура Sort(st,ed,i1,j1) управляет выводом на экран графических пояснений: st и ed – границы сортируемой части массива; i1,j1 - текущие индексы (необходимы для организации рекурсии).


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

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




Примечание: Все процедуры модуля ProcSort.pas получают в качестве параметра копию глобального динамического массива А[1..nn]


Рис. 8 . Взаимодействие модулей программного продукта в процессе компиляции и компоновки


5.Выбор стратегии тестирования и разработка тестов


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

При разработке данной программы часто возникала необходимость проверить корректность работы того или иного алгоритма сортировки. Особенность этих алгоритмов в том, что на вход им всегда подаётся некоторый несортированный массив, а на выходе должен быть отсортированный массив. С одной стороны, это облегчало тестирование – легко оценить правильность выходного массива (если число элементов в нём не слишком велико), с другой стороны – при отладке приходится иметь дело с массивом, за перемещением элементов которого порой трудно уследить.

Существует три основных стратегии тестирования

  • «ручное» тестирование

  • тестирование по принципу «чёрного ящика»

  • тестирование по принципу «белого ящика»

«Ручное» тестирование эффективно, если его выполняет группа программистов. Программа «Алгоритмы сортировки» разрабатывалась одним человеком, поэтому данная стратегия не применялась.

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

Стратегия тестирования по принципу «белого ящика», или стратегия тестирования, управляемая логикой программы (с учетом алгоритма), позволяет проверить внутреннюю структуру программы. В этом случае тестирующий получает тестовые данные путем анализа логики программы. Данная стратегия наиболее приемлема, поскольку логика программы известна, имеются в наличии алгоритмы всех операций. Недостатком данной стратегии является невозможность проверки соответствия программы её спецификации, но так как количество функций, которые должна выполнять программа согласно техническому заданию, невелико, то этот недостаток не является существенным (несоответствие программы её спецификации итак сразу будет видно).

Разработанные тесты приведены в табл. 1.

Таблица 1.

Номер теста

Назначение теста

Значения исходных данных

Ожидаемый результат

1

Проверка правильности под-счёта числа сравнений при сор-тировке методом «пузырька»

Входной массив с 3 элементами:

44 87 134

Число сравнений = 3

2

------ при шейкерной сортировке

-

Число сравнений = 2

3

------ при сортировке методом прямого выбора

-

Число сравнений = 3

4

------ при сортировке методом прямых вставок

-

Число сравнений = 3

5

------ при сортировке методом бинарного дерева

-

Число сравнений = 10

6

------ при сортировке методом Шелла

-

Число сравнений = 4

7

------ при сортировке методом Хоара

-

Число сравнений = 3

8

Проверка правильности под-счёта числа сравнений при сор-тировке методом «пузырька»

Входной массив с 5 элементами:

56 249 5 218 112

Число сравнений = 10

9

------ при шейкерной сортировке

-

Число сравнений = 9

10

------ при сортировке методом прямого выбора

-

Число сравнений = 10

11

------ при сортировке методом прямых вставок

-

Число сравнений = 10

12

------ при сортировке методом бинарного дерева

-

Число сравнений = 22

13


------ при сортировке методом Шелла

-

Число сравнений = 12

14

------ при сортировке методом Хоара

-

Число сравнений = 19


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

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


Заключение

Созданная программа может помочь студентам ВУЗов лучше уяснить себе суть 7 методов сортировки (у этих методов есть одна общая черта – в процессе сортировки не заводятся дополнительные массивы). Однако методов (алгоритмов) сортировки массивов в оперативной памяти ЭВМ гораздо больше. Если необходимо, к данной программе без особого труда можно добавить процедуры, осуществляющие сортировку и по другим методам.

На учебных занятиях (особенно на маломощных машинах) не рекомендуется запускать на сортировку массивы с числом элементов, большим 150 тыс. Это может затянуться на 5-7 мин (при этом выводится индикатор хода процесса).




Похожие:

Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconДагестанский государственный педагогический университет математический факультет кафедра преподавания математикм и информатики

Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconДагестанский государственный педагогический университет Математический факультет Кафедра преподавания математики и информатики

Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconДокументы
...
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconДокументы
...
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconКафедра предпринимательства и управления Расчетно-Графическая работа №1 По дисциплине «Логистика» Тема: «складская логистика» (
Цель метода авс – контроль за состоянием запасов товарно –материальных ценностей
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconКафедра предпринимательства и управления Расчетно-Графическая работа №1 По дисциплине «Логистика» Тема: «складская логистика» (
Цель метода авс – контроль за состоянием запасов товарно –материальных ценностей
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconО проведении региональной олимпиады по информатике для учащихся 9-11 классов
Факультет информатики Московского государственного областного гуманитарного института (кафедра информатики) доводит до Вашего сведения,...
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconНекоторые из направлений использования распределенных систем управления
Моделирование и оптимизация аппаратно-программного комплекса технологического контура системы управления космического аппарата
Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconДокументы
1. /literature.doc
2. /manreg01-Введение в теорию...

Н. Э. Баумана Факультет информатики и систем управления Кафедра Компьютерные системы и сети Расчетно-пояснительная записка iconЖук Анастасия Игоревна Системы дифференциальных уравнений в алгебре обобщенных функций
Белорусский государственный университет Механико-математический факультет Кафедра функционально анализа
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов