Методы обработки данных и оценки программ

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

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

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

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

Введение
Существуют разные классы программных продуктов и разные технологии их разработки. Независимо от класса программного продукта стоит 
задача создания качественного программного продукта. Также существуют 
общие вопросы, которые возникают независимо от того, какая технология 
будет использоваться. Получение ответов на вышеуказанные вопросы является непростой задачей. В частности, при разработке программ необходимо 
найти ответы, связанные с выбором структур данных и методов их обработки. Правильные решения обеспечат эффективную работу создаваемого программного продукта, в частности, эффективное использование процессорного времени, ресурсов оперативной и внешней памяти. Важно отметить, 
что выбор структуры данных зависит от многих факторов, например, от 
режима работы разрабатываемой системы, от решаемых задач предметной 
области и др.
Отдельно можно выделить задачу создания качественного программного продукта. Здесь важную роль играют процессы контроля и тестирования. В настоящее время не существует методов тестирования, после применения которых обеспечивается гарантия отсутствия ошибок. Несмотря 
на это, процесс тестирования является очень важным и требует больших 
временных и трудовых затрат. Разработчик должен знать основные методы 
тестирования, которые позволяют выявлять большое количество ошибок, 
допущенных при составлении программ. Знание современных методов тестирования позволяет контролировать разные стадии разработки и обеспечить раннее обнаружение ошибок, что, в свою очередь, уменьшает время 
создания программного продукта. Приобретение навыков формирования 
тестовых наборов, каждый из которых с максимальной вероятностью может обнаружить ошибку, является важной задачей учебного процесса при 
подготовке программистов. Особое место занимают структурный и функциональный подходы, которые позволяют обеспечить всестороннее тестирование программного обеспечения.

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

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

Глава 1. Структуры и методы обработки данных
приводится к натуральному числу — номеру элемента. В таблицах прямого 
доступа ключ можно не хранить. Длина поиска и средняя длина поиска равны единице (S = 1, L = 1).
Недостаток таблиц прямого доступа состоит в том, что подобная организация таблицы редко применима, так как ключи часто бывают непоследовательными или изменяются в недопустимо больших диапазонах, достоинство — быстрота поиска.
Частными случаями таблиц прямого доступа являются:
• массив — множество элементов, расположенных таким образом, что 
упорядоченное множество целых чисел (ключ) однозначно определяет позицию каждого элемента, а также обеспечивает возможность организации 
прямого доступа к каждому элементу. Если упорядоченное множество содержит N чисел, то массив N-мерный. Числа, входящие в упорядоченное 
множество, называются индексами. Каждый индекс имеет свой диапазон изменения;
• строка — одномерный массив символов;
• запись — конечное упорядоченное множество элементов, в общем 
случае различных типов. Ключом является порядковый номер поля или его 
имя.
Логический порядок элементов в просмотровых таблицах и таблицах 
прямого доступа при реализации обычно совпадает с физическим порядком 
расположения элементов. Элементами являются записи. Записи могут быть 
фиксированной, переменной и неопределенной длины. В зависимости от 
типа записи таблицы реализуются массивом записей или массивом векторов (статических или динамических), в котором основной массив содержит 
адреса векторов записей.
Для массива записей фиксированной длины адреса промежуточных записей задаются формулой
A
A
i
l
i =
+
−
1
1
(
) ,
где Ai — адрес i-й записи; A1 — адрес первой записи; l — длина записи.
Достоинство массива записей фиксированной длины — экономное использование памяти, так как записи располагаются одна за другой без промежутков, недостаток — необходимо заранее знать общее число записей, их 
длину и диапазон изменения ключей.
Таблицы с перемешиванием, или кэш-таблицы, — результат попытки 
построить таблицу, где L ≅ 1, при нерегулярных ключах. Для построения 
кэш-таблицы выбирают функцию перемешивания (кэш-функцию), определенную на множестве значений ключа. Такая функция разбивает весь диапазон ключей на эквивалентные классы максимально равномерно. Далее для 
класса ключей адрес определяется как при прямом доступе, а внутри класса — последовательно (рис. 1.2).
Недостаток таблиц с перемешиванием в сложности построения 
кэш-функции, так как при слишком большом количестве классов часть из