Выбор алгоритмов обработки данных, тестирование и повышение качества программ

Федеральное государственное бюджетное 
образовательное учреждение высшего образования 
«Московский государственный технический университет имени Н.Э. Баумана 
(национальный исследовательский университет)»
Г.С. Иванова, Т.Н. Ничушкина, Е.К. Пугачев
Выбор алгоритмов обработки данных, 
тестирование и повышение качества 
программ
Учебно-методическое пособие

УДК 004.021
ББК 32.973-018.2
 
И20
Издание доступно в электронном виде по адресу 
https://bmstu.press/catalog/item/6756
Факультет «Информатика и системы управления»
Кафедра «Компьютерные системы и сети»
Рекомендовано 
Научно-методическим советом МГТУ им. Н.Э.
 Баумана 
в качестве учебно-методического пособия
Иванова, Г. С.
И20  
Выбор алгоритмов обработки данных, тестирование и повышение качества программ : учебно-методическое пособие / Г. С. Иванова, Т. Н. Ничушкина, Е. К. Пугачев. — Москва : Издательство МГТУ 
им. Н. Э. Баумана, 2020. — 65, [3] с. : ил.
ISBN 978-5-7038-5408-2
Представлены краткое описание основных структур и методов обработки  данных, критерии оценки алгоритмов и структур данных, примеры 
структур данных, способы оценки и повышения эффективности программ, 
способы тестирования программ, варианты заданий, порядок выполнения 
и требования к защите лабораторных работ, предусмотренных учебным планом МГТУ им. Н.Э. Баумана.
Для студентов МГТУ им. Н.Э. Баумана, обучающихся по направлению 
подготовки «Информатика и вычислительная техника».
УДК 004.021
ББК 32.973-018.2
© МГТУ им. Н.Э. Баумана, 2020
© Оформление. Издательство 
ISBN 978-5-7038-5408-2 
МГТУ им. Н.Э. Баумана, 2020

Предисловие
Учебно-методическое пособие предназначено для получения практических навыков в области разработки программ студентами, обучающимися 
на кафедре «Компьютерные системы и сети».
Издание составлено в соответствии с самостоятельно устанавливаемым 
образовательным стандартом (СУОС), основной образовательной программой по направлению подготовки 09.03.01 «Информатика и вычислительная 
техника» бакалавров и предназначено для подготовки к выполнению лабораторных работ по дисциплине «Технология разработки программных систем».
Цель учебно-методического пособия — подготовка студентов к лабораторным работам, связанным с приобретением практических навыков выбора 
структур данных и методов их обработки, а также навыков тестирования 
и оценки качества программ.
После выполнения лабораторных работ студенты будут:
знать
• основные методы реализации операций, таких как поиск, упорядочение и корректировка;
• основные способы организации данных;
• методы тестирования;
• методы оценки эффективности и качества программ;
уметь
• выделять основные свойства структур данных и проводить сравнительный анализ;
• определять качественные и количественные критерии оценки методов обработки данных;
• проводить тестирование программного продукта на этапах проектирования и реализации;
• определять время работы программы;
• определять способы повышения эффективности и качества программы;
владеть
• методиками расчета основных параметров, на основании которых 
осуществляется выбор структур данных и методов их обработки применительно к конкретной задаче;
• методами тестирования программных продуктов;
• методиками оценки качества программ;
• методиками оценки и повышения эффективности программ;
• практическими навыками анализа методов обработки данных;
• практическими навыками составления тестов и проверки работоспособности программы с учетом ее специфики;

Предисловие
4
• практическими навыками по определению эффективного способа 
реализации программы.
Кроме того, студент получит следующие навыки:
• выбора структур данных и алгоритмов их обработки применительно 
к конкретной задаче;
• проведения эффективного тестирования;
• повышения эффективности и качества программ.
Для лабораторных работ необходимо предварительное освоение следующих дисциплин: информатика, основы программирования, объектноориентированное программирование, языки интернет-программирования.
Одной из важных задач учебно-методического пособия является приобретение студентами способности разрабатывать компоненты программных 
систем, используя современные инструментальные средства и технологии 
программирования, а также осуществлять постановку и выполнять эксперименты по проверке корректности и эффективности программ.
В лабораторной работе 1 рассмотрены способы организации структур 
данных, оценки применимости различных структур к конкретным задачам, 
а также способы оценки алгоритмов, реализующие различные методы обработки данных для операций поиска, упорядочения и корректировки данных. 
Студентам необходимо проработать основной вариант по заданию и после 
получения результатов предложить альтернативный вариант решения, в котором устранены недостатки основного варианта.
В лабораторной работе 2 исследованы способы оценки эффективности 
и качества программ. После оценки программы студентам необходимо предложить способы повышения эффективности и качества. Данные улучшения 
должны быть подтверждены практическими результатами замеров.
В лабораторной работе 3 приведены методы тестирования программных 
продуктов, которые используются на разных стадиях разработки и позволяют определять широкий спектр ошибок.
В приложениях представлены примеры оформления лабораторных работ.
Издание позволит студентам самостоятельно изучить важные разделы 
дисциплины «Технология разработки программных систем».
Для успешного освоения материала необходимо внимательно разбирать 
примеры, целесообразно синтезировать и прорабатывать аналогичные примеры. 
Ответы на вопросы позволят обучающемуся самостоятельно оценить степень 
понимания и усвоения теоретических положений, методик и методов. Выполнение заданий обеспечит приобретение умений и навыков, необходимых для 
постановки и решения задач проектирования, тестирования и оценки программ.
Для оценки степени понимания и усвоения теоретических положений, 
методик и методов, приобретения умений и навыков служит информативный отчет по каждой лабораторной работе, где полно и точно представлены 
результаты и их защита. Лабораторные работы студенты выполняют и защищают в компьютерном классе. Варианты заданий, требования к отчету 
и защите приведены отдельно по каждой лабораторной работе.

Введение
При создании программных продуктов необходимо знать подходы разработки отдельных компонентов. Можно выделить следующие три вида 
компонентов: интерфейсные, обрабатывающие и компоненты данных. Эффективная работа любой программной системы зависит от того, насколько 
удачно был сделан выбор методов для реализации основных операций обра
батывающих компонент. Во многих программных системах часто используются операции поиска, упорядочения и редактирования. Только для вышеуказанных операций существует множество методов их реализации. Задача 
выбора метода реализации является непростой, так как в каждом отдельном 
случае необходимо учитывать структуру данных. Удачно принятые решения, 
связанные с выбором структур данных и методов их обработки, позволяют 
экономно использовать ресурсы вычислительной системы, например ресурсы оперативной и внешней памяти, а также процессорное время. Чтобы принять удачные решения, необходимо обладать знаниями, связанными 
с основными факторами, влияющими на выбор структуры данных, которые, 
в свою очередь, зависят от режима работы разрабатываемой системы, решаемых задач предметной области и др.
Этап реализации программного продукта включает процесс его тестирования. Тестирование сложной программы представляет собой непростой 
процесс. Владение навыками составления тестов и разработки алгоритмов 
тестирования программ является важной задачей. Грамотно проведенное 
тестирование разрабатываемой программной системы обеспечивает уверенность в том, что все компоненты работают корректно и соответствуют 
предъявленным требованиям.
Также актуальной задачей является оценка качества уже существующего 
программного продукта, которая связана как с проверкой соответствия программного продукта функциональным требованиям, указанным в техническом задании, так и с оценкой производительности.

Лабораторная работа 1. 
ВЫБОР СТРУКТУР И МЕТОДОВ ОБРАБОТКИ ДАННЫХ
При разработке алгоритмов программ часто возникает задача выбора 
структур данных и методов их обработки. Исходными составляющими для 
решения этой задачи являются описание набора и типов хранимых данных, 
а также перечень операций, выполняемых с ними.
Можно выделить следующие основные вопросы, на которые необходимо ответить при решении поставленной задачи: 
• как логически организовать структуру данных;
• как реализовать структуру данных;
• как осуществлять поиск информации; 
• как упорядочить данные;
• как выполнить функции корректировки данных?
Цель работы: определить основные критерии оценки структуры данных 
и методов ее обработки применительно к конкретной задаче.
Продолжительность работы: 9 часов.
1.1. Краткие теоретические сведения
Структуры данных
На этапе логического проектирования программного продукта разработчик определяет абстрактные структуры данных. Классификация по 
принципу связности элементов данных приведена в табл. 1.1.
При выборе множеств необходимо учитывать следующие их основные 
свойства:
•  элементы множества не пронумерованы;
•  отдельный элемент множества не идентифицируется;
•  с элементами нельзя выполнить какие-либо действия;
•  действия выполняются только над множеством в целом;
•  элементы множества однотипные.
Очень часто при разработке программ используют таблицы. Различают четыре типа таблиц (просмотровые, прямого доступа, двоичного поиска 
и таблицы с перемешиванием). Доступ к таблицам бывает разным, и от этого зависит, например, эффективность поиска данных. Эффективность поиска в таблицах различных типов оценивают, используя две характеристики: 

1.1. Краткие теоретические сведения
7
S — длина поиска — количество записей, которые необходимо просмотреть, 
чтобы найти запись с заданным ключом; L — средняя длина поиска при постоянной частоте обращения.
Таблица 1.1 
Виды структур абстрактных данных
Описание
Тип связности элеменПримеры 
тов структуры данных
структур
 Элементы не связаны Множество
Позволяют хранить ограниченное число значений определенного типа без определенного 
порядка. Доступ путем перебора элементов 
(счетный)
Элементы связаны 
неявно
Таблицы
Данные четко структурированы и занесены 
в специальные таблицы. 
Имеется возможность определить положение 
одного элемента по отношению к другим.
Доступ к элементам может быть последовательным и прямым
Элементы связаны 
явно
Списки, деревья и др.
Элементы структуры имеют служебные 
поля с целью указать непосредственно 
адрес(-а) элемента(-ов) с которым(-и) он(-и) 
связан(-ы). Доступ к элементам косвенный
В просмотровых таблицах доступ к записям последовательный, а основные характеристики следующие: 
S
i
L
N
i =
=
+
 
 
;
/ ,
(
)
1
2
где N — количество записей.
В таблицах прямого доступа ключ однозначно определяет адрес. Основные характеристики: S = 1; L = 1.
Частными случаями таблиц прямого доступа являются: массив, строка, 
запись.
Для массива записей фиксированной длины адреса промежуточных записей задаются формулой
A
A
i
l
i =
+
−
1
1
(
) ,
где Ai — адрес i-й записи; A1 — адрес первой записи; l — длина записи.
В таблицах с перемешиванием (кэш-таблицах) L ≅ 1 при нерегулярных 
ключах. Для построения кэш-таблицы выбирается функция перемешивания (кэш-функция), определенная на множестве значений ключа. Доступ 
к классу прямой, а внутри класса последовательный.
В таблицах двоичного поиска записи сортируют по ключу поиска, что 
позволяет использовать более эффективный алгоритм поиска.