автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка методов и алгоритмов диагностирования программного обеспечения с использованием графа потока данных

003452942

На правах рукописи

ДМИТРИЕВ Дмитрий Валерьевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ДИАГНОСТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ ГРАФА

ПОТОКА ДАННЫХ

Специальность 05.13.01 - «Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

___|

Нижний Новгород 2008

003452942

Работа выполнена на кафедре «Информатика и системы управления» Нижегородского государственного технического университета им. P.E. Алексеева

Научный руководитель: - доктор технических наук, профессор

Соколова Элеонора Станиславовна

Официальные оппоненты: - доктор технических наук профессор

Крылов Владимир Владимирович

- кандидат технических наук доцент Уваров Петр Иванович

Ведущая организация: Научно-исследовательский Центр

контроля и диагностики, Н.Новгород

Защита состоится «4» декабря 2008 г. в. часов на заседании

диссертационного совета № Д.212.165.05 в Нижегородском государственном техническом университете им. P.E. Алексеева (НГТУ) по адресу: 603600, г. Нижний Новгород, ГСП-41, ул. К.Минина, 24.

С диссертацией можно ознакомиться в библиотеке НГТУ.

Ваш отзыв на автореферат в одном экземпляре, заверенный печатью, просим направлять на имя ученого секретаря совета

Автореферат разослан « Ц $ » 2008 г.

Ученый секретарь диссертационного совета

A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы.

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

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

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

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

Фундаментальные теоретические и прикладные вопросы тестирования и диагностики программного обеспечения изложены в работах Майерса, Бейзера, Макгрегора, Боехма и ряда других зарубежных авторов. Среди отечественных авторов следует отметить Пархоменко П.П. и Липаева В.В.. В качестве модели тестирования и диагностирования программного обеспечения в этих работах предлагается использовать управляющий граф программы. Следует отметить, что методы, разработанные для данной модели, хорошо зарекомендовали себя при тестировании и диагностике процедурно-ориентированного программного обеспечения. При переходе к объектно-ориентированному программному

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

В тоже время модель представления программ в виде графа потока данных, отражающего информационные зависимости между операциями над данными в программе, позволяет значительно расширить возможности автоматизирования решения задач локализации ошибок за счет повышения информативности тестовых прогонов программного обеспечения.

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

Цель работы

Разработка и исследование моделей, методов и алгоритмов диагностирования программ на граф-моделях потока данных с целью локализации местоположения ошибки в вычислительном программном коде. Автоматизация разработанных методов для их практического применения.

Методы исследования

В теоретических исследованиях диссертационной работы использовались методы теории графов, теории множеств, методы оптимизации, численное моделирование, модели, методы и алгоритмы теории надежности. Для практической апробации разработанных алгоритмов применено программное моделирование тестирования и диагностирования, реализованное на языке Delphi 5. Графический материал при проведении исследований получен с использованием пакета Microsoft Excel.

Объекты исследования

Объектами исследования являются программные реализации вычислительных алгоритмов на языке С++ для различных сред разработки.

Научная новнзна диссертационной работы

1. Разработана граф-модель потока данных для диагностирования программного обеспечения, позволяющая существенно сократить затраты по поиску и локализации ошибки в программном обеспечении за счет увеличения информативности тестирования.

2. Разработан алгоритм построения в фоновом режиме графа потока данных при тестировании программы с сохранением идентификаторов обработанных данных для целей диагностирования ошибок.

3. Разработан метод оптимизации списка операций, подвергаемых проверке в случае выявления несоответствия требованиям спецификаций, на основе анализа графа потока данных алгоритма.

4. Предложены критерии ранжирования операций над данными, подверженных проверке, в соответствии которым построена оптимальная последовательность их проверок. Получены оценки эффективности критериев ранжирования.

5. Разработан метод оценки сложности алгоритма с целью его оптимизации на базе граф-модели потока данных. Предложен метод автоматизации получения исходных данных для целей распараллеливания алгоритма с использованием граф-модели потока данных.

Практическая значимость работы

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

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

Разработанные математические модели и алгоритмы доведены до практической реализации, что подтверждено свидетельством о государственной регистрации программы для ЭВМ.

Реализация результатов работы

Разработанные математические модели реализованы в среде Microsoft Visual Studio NET 2003. Алгоритмы анализа информации о тестовом прогоне реализованы в среде Delphi 5; используются в учебном процессе в виде прикладных задач в лекциях курсов «Надежность, эргономика и качество АСОиУ» и «Технология программирования» для студентов, обучающихся по специальности 22.02.00 «Автоматизированные системы обработки информации и управления» в ГОУ ВПО Нижегородского Государственного Технического Университета им. P.E. Алексеева. Разработанный программный продукт «Диагностирование вычислительного процесса» передан в Центр контроля и диагностики Госстандарта РФ, в Научно-исследовательский вычислительный центр Федеральной налоговой службы и в ООО «Теком».

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на Всероссийских научно-технических конференциях "Информационные системы и технологии" ИСТ-2004, ИСТ-2005, ИСТ-2006, на Международной научно-технической конференции "Информационные системы и технологии" ИСТ-2007, на VI Международной конференции «Идентификация систем и задачи управления» SICPRO '07, на 11-й Нижегородской сессии молодых ученых (технические науки).

Публикации

По результатам диссертационной работы опубликовано 13 работ в печатных изданиях, в том числе 2 работы в изданиях, рекомендованных ВАК.

Структура и объём работы

Диссертационная работа изложена на 156 печатных листах, включает 18 рисунков и состоит из введения, 5 глав, заключения, списка литературы и 6 приложений.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе исследуется состояние проблемы диагностики программного обеспечения, приводится обзор литературных источников по проблеме обеспечения качества программного обеспечения, анализируются основные результаты, полученные в этой области за последнее время.

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

Проведенный анализ работ в области тестирования и диагностики программных средств показал отсутствие общего подхода к построению эффективных моделей, методов и алгоритмов диагностирования причин проявления ошибок в объектно-ориентированных программах. В результате сформулированы цели и постановка задач исследования — разработка моделей, методов и алгоритмов диагностирования вычислительных алгоритмов, программно реализованных на объектно-ориентированном языке, с целью уменьшения затрат по выявлению местоположения ошибки.

Во второй главе в результате проведенных исследований разработаны модель графа потока данных, методы и алгоритмы диагностирования вычислительных алгоритмов объектно-ориентированного программного обеспечения.

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

Обозначим G=(V,A) — ориентированный упорядоченный граф без контуров и петель, где V={vi,v2, . . . ,v„} - множество вершин графа потока данных, соответствующих операциям обработки данных, U={U|,U2,. . ., Up} -множество связей между операциями обработки данных, отображаемых направленными дугами Uj={vn,vi2} (j = '.Pi ¡¡¡261,и). Эквивалентная матричная модель - матрица смежности вершин графа, эквивалентная списочная модель -список смежности вершин графа (список примыканий). Отметим, что дуги в этом графе соответствуют распространению ошибки от причины ее возникновения к следствиям ее проявления.

На рисунке 1, для наглядного отображения зависимостей по данным вычислительного процесса, приведено графическое представление классов геометрических фигур: Triangle (треугольник), Line (линия) и Point (точка) и класс, вычисляющий их отношения Ratio (отношение). Информационные зависимости между полями (-) и методами (+) классов отображаются стрелками.

Triangle

-a,b,c:double

-P1,P2,P3:Point

+Show()jvoid

Ratio

+Move(...):void

+FindMax(...):void

+Lslncluded(...):void •t-LsCrossingr^jivoid

Point

-x,y:double

+Show():void

Line

-length:double

-P1,P2:Point

■KSetLengthQ.double

Рисунок 1. Зависимости по данным для вычислительного процесса

Граф-модель потока данных программы, реализующей вычислительный алгоритм, хорошо приспособлена к решению задач диагностирования и локализации ошибки, описывая все множество ветвей вычислительного процесса во время тестового прогона, повлекшего проявление ошибки на определенном этапе. Свойства и особенности графа потока данных позволяют широко применять данную модель в задачах тестирования и отладки программного обеспечения, в задачах выявления местоположения ошибки в тех случаях, когда ошибка в программе не совпадает с местом ее проявления.

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

Для создания современного программного обеспечения используются объектно-ориентированные языки. Проведено исследование основных свойств программного обеспечения объектно-ориентированной парадигмы с целью анализа проблем, обусловленных особенностями процедур тестирования и диагностирования вычислительных алгоритмов:

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

наследование ставит вопросы о повторении тестирования наследуемых операций.

полиморфизм приводит к неоднозначности с вызовом операций, которая может быть разрешена только на этапе выполнения.

событийная управляемость объектно-ориентированного программного обеспечения (нет явного указания последовательности исполнения операторов).

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

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

В результате исследований разработана обобщенная структура модели тестирования и диагностирования объектно-ориентированного программного обеспечения в виде графа потока данных, на основе которой предложены методы и алгоритмы диагностирования ошибок программного обеспечения (рисунок 2).

Рисунок 2. Блок схема тестирования и диагностирования вычислительных

алгоритмов

На рисунке 2 затемненные блоки (2,4,8) содержат известные, успешно применяемые методы тестирования и диагностирования, органично

встраиваемые в предлагаемую модель, а также файлы тестируемого программного кода (1) являющиеся исходными данными для предложенного метода. Блоки 3,5,6,7 содержат методы и алгоритмы, разработанные автором в результате выполнения работы.

Представлен разработанный метод автоматизированного построения графа потока данных вычислительного алгоритма для диагностирования ошибок в процессе тестового прогона программы, а также алгоритм анализа графа потока данных для локализации места возникновения причин выявленного несоответствия требованиям спецификаций.

Для автоматизации процесса построения графа потока данных применяется метод автотрассировки, основанный на возможности переопределения переменных вещественного типа на переменные класса Number. Класс Number,с одной стороны, выполняет те же операции, что и double. (арифметика, ввод/вывод), а с другой стороны, строит вершины и дуги графа, соответствующие этим операциям.

Разработанный метод позволяет:

- широко и управляемо варьировать диапазон интеграции программных вычислительных алгоритмов в вершины графа потока данных при тестовом прогоне, при этом существенно облегчая поиск источника ошибок;

- учитывать особенности диагностирования, связанные с инкапсуляцией, наследованием, полиморфизмом и событийной управляемостью за счет сохранения информационных зависимостей по данным в виде графа;

- осуществить внедрение модели в процессе тестирования при минимальной модификации программы;

- реализовать предложенную модель и методы диагностирования ошибок в рамках компилятора языка С++;

- выявить некорректности с точки зрения грамотного стиля программирования в виде «висячих» вершин графа.

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

Под уровнем агрегации будем понимать степень детализации отображения вычислительного алгоритма графом, т.е. варьировать размером объекта алгоритма, с точностью до которого мы хотим выявить местоположение ошибки.

Для предложенной модели разработаны три уровня агрегации операций в вершины графа:

низший - при выполнении каждой элементарной операции е строится вершина графа, соответствующая обрабатываемой операции;

средний - вершины графа соответствуют простым операторам р. Как правило, это присваивание или операции ввода/вывода;

высокий - каждой вершине графа соответствует некоторый блок Ь программного кода (функция, цикл, условный оператор, линейный блок операторов и т.д.).

При диагностировании разработанного программного продукта предлагается стратегия применения сначала высокого уровня агрегации. Это обусловлено тем, что применение более детализированных уровней агрегации на ранних этапах диагностирования ошибки приведет к существенному увеличению трудоемкости процедуры диагностирования. Блок-схема алгоритма детализации вычислительного процесса представлена на рисунке 3.

("начало ) *

■■■■ 1 11 Отпаака Н ■■ 1 -■■ -----

Тестовый прогон

| Тестовый прогон Граф потока данных на верхнем уровне детализация 1

1 ребуется детал> «заиия веошины? - да

Тестовый прогон для вершины верхнего уровня детализации Граф потока данных на среднем уровне детализации

I Построение списка диагностируемых вершин для среднего уровня детализаций

Проверка очередной веошинуреднего уровня детализации

. Требуется детализация вершины?

Тестовый прогон для вершины I Граф потока данных на среднего уровня детализации 1 низшем уровне детализации

I Прррерка очередной вершины^ниэ^иего уровня детализации

Рисунок 3 Алгоритм детализации вычислительного процесса В работе решается задача минимизации объема диагностической информации для локализации места возникновения причины выявленной ошибки. Для этих целей разработан алгоритм анализа графа потока данных вычислительного процесса, реализованный в виде приложения.

Пусть в процессе тестового прогона было выявлено несоответствие требованиям спецификаций в операции, соответствующей вершине v„ в графе потока данных. Разработанная модель позволяет значительно сократить число строчек программного кода, подверженных проверке за счет повышения информативности тестового прогона.

Стратегия диагностирования и локализации дефекта в программной реализации вычислительного алгоритма заключается в анализе полученного в результате тестового прогона списка вершин-операций графа потока данных.

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

Исследования программ, реализующих вычислительные алгоритмы, показали, что число операций в проверочной таблице значительно меньше общего числа операций программного кода за счет того, что в таблицу заносятся только операции, участвовавшие в тестовом прогоне и повлиявшие на выявленное несоответствие. Результаты моделирования процесса тестирования и отладки программных реализаций вычислительных алгоритмов показали, что количество операций, подверженных проверке при применении разработанной модели диагностирования в виде графа потока данных, снижается во много раз. Моделирование произведено с помощью разработанного программного продукта «Моделирование вычислительного процесса для оценки диагностирования ошибок». На данное программное обеспечение получено свидетельство о регистрации.

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

Пусть V= N+I - число проверок, которое необходимо последовательно выполнить для выявления местоположения ошибки в программе без применения модели, где N - номер вершины в графе потока данных алгоритма, в которую вносится ошибка (нумерация вершин идет с нуля).

Введем следующие обозначения:

V¡d+ - множество вершин граф-модели, подверженных проверке при ранжировании по степени исхода дуг;

V¡d" - множество вершин граф-модели, подверженных проверке при ранжировании по степени захода дуг;

У0(1 - множество вершин граф-модели, подверженных проверке при ранжировании по сумме степеней исхода и захода.

Для оценки методов ранжирования вершин-операций рассчитывается значение ф, равное отношению мощности множества проверок по каждому методу к мощности множества проверок без применения модели в виде графа потока данных:

Ф=Ук/У,

где Ук - мощность множества проверок при к-ом методе ранжирования. Очевидно, что чем меньше значение ф, тем выше эффективность метода сортировки вершин графа потока данных, подверженных проверке.

Для 100 тестовых прогонов, выявивших ошибку, и, соответственно, для

100 процедур диагностирования были получены следующие результаты:

«V

1265 1265

= 1;

<Ру

1107 1265

= 0,875; ^~ = 0,516.

Таким образом, сортировка вершин проверочной таблицы по степени захода и по сумме степеней исхода и захода позволяет значительно повысить эффективность поиска ошибки.

Представлены результаты моделирования процесса тестирования и диагностирования программной реализации вычислительного алгоритма с применением предложенной модели (рисунок 4).

' О Ст1.000000): ) -1А ' 1 [-1.000000): ) -1.1: ' 2 (-4.000000): ) -1.2: ' а 1-гоооооо):

I -1.3:

• 4 (=9,000000):

) -1.4:

• Б (—ЭОООООО):

) -1.6:

• Б (-26.000000):

) -1.6:

• 7 (-4.000000):

I -1.7: ц_

Л

я;;:..

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

Третья глава посвящена автоматизации разработанных методов и алгоритмов диагностирования ошибок в программных модулях. Приведено

описание метода внедрения автоматизированных алгоритмов в программный проект для практического применения. Описаны пути интеграции предложенной модели в тестируемый проект на основе стандартных средств редакторов сред разработки С++. Приведена спецификация разработанного конвертора, предназначенного для автоматизации процедуры внедрения класса Number. Работа конвертора состоит из следующих этапов:

1. Поиск всех описаний переменных типа, подлежащего переопределению (для вычислительных алгоритмов осуществляется поиск всех переменных вещественного типа float/double). Имена этих переменных запоминаются в списочной структуре.

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

3. Обработка всех строчек программного кода, в командах которых используются переменные из списочной структуры.

Описана процедура интеграции графа потока данных в- проект Visual Studio Net 2005 с использованием конвертора.

В четвертой главе описываются возможности применения графа потока данных для анализа и оптимизации вычислительных алгоритмов.

Повышение надежности и качества программного обеспечения -ресурсоемкая задача. В этой связи актуальна задача оптимизации алгоритмов обработки данных и распараллеливания.

Анализ существующих методов в области оценки сложности вычислительных алгоритмов выявил необходимость автоматизирования процесса оптимизации вычислительных алгоритмов.

Показано, что, используя разработанную граф-модель потока данных, эффективно решаются задачи оценки сложности вычислительных алгоритмов, проводится анализ сложности их реализации с целью оптимизации количества вычислений.

Пусть имеем входные тестовые наборы размерности п, образующие множество D„ (D„eD). Обозначим мощность множества D„ через MDn, предполагая, что множество D„ - конечное.

Тогда алгоритм А, имея на входе различные тестовые наборы из множества D„, будет, в общем случае, задавать в случае входного воздействия dj наибольшее, а в случае dj i,j е {^М^} наименьшее количество исполняемых операций.

Проанализировав множество графов потока данных, полученных в процессе тестовых прогонов, получены следующие оценки трудоемкости алгоритма:

1. f*(и) = max{fA(d)}~ худшая трудоемкость, полученная в процессе

ЛО,

исполнения алгоритма, характеризуемая наибольшим количеством операций, совершаемых алгоритмом А на тестовых наборах размерности п.

2. f* (и) = min {/, (d)} - лучшая трудоемкость, полученная в процессе

dcDm

исполнения алгоритма, характеризуемая наименьшим количеством операций, совершаемых алгоритмом А на тестовых наборах размерности п.

3. f л(п) = —— сРеДняя трудоемкость, полученная в процессе

Ми, dmDn

исполнения алгоритма, характеризуемая средним количеством операций, совершаемых алгоритмом А на тестовых наборах размерности п.

Для простоты процесса моделирования при оценке трудоемкости алгоритмов учитывались количества операций сравнения, арифметических операций и операций присваивания.

Представлено исследование известных алгоритмов сортировки для массивов размерности до 100 элементов и получены оценки их трудоемкостей (рисунок 5):

(. - . - - Труд ом кость алгоритма сорти ровки

Пузырьковый Минимакс Простая вставка Двоичная вставка

Б3376 61662 44316 36743

63504 61701 43482 36087

64504 61663 43994 37521

57659 61690 42267 36651

63063 61677 43737 34480

62027 61672 43899 39040

62841 61664 42783 35310

59072 61677 43961 33572

63966 61686 41683 35586

/:« 57659 61662 41683 33572

tfw 64504 61701 44316 39040

ш 62223,6 61676,9 43346,9 36110,0

Рисунок 5. Оценка трудоемкостей алгоритмов сортировки массивов целых

чисел

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

Представлен разработанный алгоритм анализа графа потока данных для целей распараллеливания по критериям минимального времени выполнения работы алгоритма. Выявлено, что оптимальная схема параллельного исполнения вычислительного алгоритма для целей диагностирования позволяет

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

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

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

Пусть ошибка проявилась при исполнении процедуры Та1£еЮЙ!зеЮпВ307, тогда, отследив распространение ошибки по графу потока данных, диагностированию подвергаются процедуры (ЖзеЮГРаут_Мат, РгосРаутепЮЙ^Б и Та1веЮЙ5еЮпБ307.

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

Таким образом, подтверждена возможность применения разработанных методов диагностирования ошибок для обеспечения снижения трудоемкости диагностирования программ на этапе отладки.

В заключении формулируются основные результаты, полученные в диссертационной работе.

В приложении приведены программные коды, реализующие - предложенные алгоритмы, и документы, подтверждающие практическое применение результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана модель и методы диагностирования вычислительных алгоритмов объектно-ориентированного программного обеспечения с минимальной модификацией программного кода для ее внедрения.

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

3. Выполнена адаптация разработанных методов для вычислительных алгоритмов различной природы и применение их для различных степеней детализации локализации ошибки.

4. Решена задача повышения информативности тестовых прогонов .за счет добавления дополнительной информации о вычислительном процессе с помощью препроцессорных средств компилятора.

5. Проведен анализ и показана эффективность применения ранжирования списка операций, подверженных проверке по степени захода и сумме степеней исхода и захода.

6. Разработаны средства автоматизации предложенной модели в программный проект (конвертор).

7. Разработанные алгоритмы реализованы в виде программного обеспечения, позволяющего в фоновом режиме тестового прогона получить диагностическую информацию об ошибках.

8. Показана возможность использования разработанных алгоритмов для оценки трудоемкости вычислительного процесса на этапе тестирования и его распараллеливания.

Публикации в изданиях, рекомендованных ВАК РФ

1. Дмитриев, Д. В. Адаптация генетических алгоритмов к решению задач назначения точек контроля в объектах с большим числом состояний / Д. В. Дмитриев, Э. С. Соколова, С. В. Капранов // Нейрокомпьютеры, Москва, 2007.

2. Дмитриев, Д. В. Построение автотрассировочного графа для тестирования вычислительных алгоритмов / Д. В. Дмитриев, Э. С. Соколова // Системы управления и информационные технологии, Воронеж, 2007.

Публикации по теме диссертационного исследования

3. Дмитриев, Д. В. Обнаружение дефектов в процессе проектирования и эксплуатации программ / Д. В. Дмитриев, Э. С. Соколова // Научный журнал по теоретическим и экспериментальным . проблемам ЕСТЕСТВЕННЫХ НАУК «Успехи современного естествознания №2 2004»

4. Дмитриев, Д. В. Разработка метода построения графа переходов для модулей программного обеспечения с подготовкой для тестирования / Д. В. Дмитриев // Тезисы докладов Всероссийской научно-технической конференции Информационные системы и технологии ИСТ - 2004. НГТУ, Н.Новгород, 2004г.

5. Дмитриев, Д. В. Модель тестирования объектно-ориентированного программного обеспечения / Д. В. Дмитриев // Тезисы докладов Всероссийской научно-технической конференции Информационные системы и технологии ИСТ - 2005. НГТУ, Н.Новгород, 2005г.

6. Дмитриев, Д. В. Модель и алгоритмы тестирования вычислительных алгоритмов объектно-ориентированного программного обеспечения / Д. В. Дмитриев, Э. С. Соколова // печ. Труды Нижегородского государственного технического университета, том 54, выпуск 12.Системы обработки информации и управления, НГТУ, Н.Новгород, 2005г.

7. Дмитриев, Д. В. Алгоритмы тестирования вычислительных алгоритмов объектно-ориентированного программного обеспечения / Д. В. Дмитриев // Труды Нижегородского государственного технического университета, том 54, выпуск 12. Системы обработки информации и

управления, НГТУ, Н.Новгород, 2005г.

8. Дмитриев, Д. В. Модель и алгоритмы тестирования объектно-ориентированного программного обеспечения / Д. В. Дмитриев // 4-ая Международная молодежная научно-техническая конференция (Будущее технической науки), НГТУ, Н.Новгород, 2005г.

9. Дмитриев, Д. В. Оптимизация тестирования программ по критерию обхода дерева вычислительных операций / Д. В. Дмитриев // Тезисы докладов Всероссийской научно-технической конференции Информационные системы и технологии ИСТ - 2006. НГТУ, Н.Новгород, 2006г.

10. Дмитриев, Д. В. Об одном методе обнаружения ошибок в программных модулях / Д. В. Дмитриев, Э. С. Соколова //11-ая Нижегородская сессия молодых учёных (технические науки), программа, НГТУ Н.Новгород, 2006г.

11. Дмитриев, Д. В. Разработка метода тестирования тупиковых операций в объектно-ориентированных программах / Д. В. Дмитриев, Э. С. Соколова // Труды VI Международной конференции «Идентификация систем и задачи управления», Институт проблем управления им. В.А. Трапезникова РАН, Москва, 2007г.

12. Dmitriev, D. V. Development of the method of testing of deadlock operations in object-oriented programs / D. V. Dmitriev, E. S. Sokolova // Proceedings of the VI INTERNATIONAL CONFERENCE "System identification and control problems", V. A. Trapeznikov Institute of Control Sciences, Moscow, 2007.

13. Дмитриев, Д. В. К вопросу о тестировании рекурсии методом автотрассировки в вычислительных алгоритмах / Д. В. Дмитриев // Тезисы международной научно-технической конференции Информационные системы и технологии (ист-2007)" Посвященной 90 -летаю НГТУ.

Подписано в печать 24.10.08. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 669.

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИЗ ПРОБЛЕМЫ ТЕСТИРОВАНИЯ И ДИАГНОСТИРОВАНИЯ ПРОГРАММНЫХ СРЕДСТВ.

1.1 Методы тестирования и диагностирования программных средств.

1.2 Тестирование классов с использованием потока данных.

1.3 Методы оценки сложности вычислительных алгоритмов и их распараллеливания.

1.4 Постановка задачи исследования.

ГЛАВА 2 МЕТОДЫ ТЕСТИРОВАНИЯ И ДИАГНОСТИРОВАНИЯ

ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ ГРАФА ПОТОКА

ДАННЫХ.

2.1 Особенности тестирования и диагностирования объектно-ориентированного программного обеспечения.

2.2 Основные термины и определения, используемые при разработке модели и алгоритмов диагностирования программного обеспечения.

2.3 Структура разработанного метода тестирования и диагностирования объектно-ориентированных вычислительных алгоритмов.

2.4 Модель диагностирования программного обеспечения с использованием графа потока данных.

2.5 Метод автоматизированного построения граф-модели потока данных алгоритма для целей диагностирования и отладки вычислительного алгоритма в процессе тестового прогона.

2.6 Алгоритмы анализа графа потока данных вычислительного алгоритма, полученного в процессе тестового прогона, для целей тестирования и диагностирования.

2.7 Исследование методов упорядочивания списка проверочных вершин граф-модели потока данных с целью повышения эффективности работы алгоритмов.

2.8 Выводы.

ГЛАВА 3 АВТОМАТИЗАЦИЯ РАЗРАБОТАННЫХ МЕТОДОВ И ВНЕДРЕНИЕ В

ПРОГРАММНЫЙ ПРОЕКТ ДЛЯ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ.

3.1 Интеграция класса Number в тестируемый проект для целей диагностирования вычислительных алгоритмов.

3.2 Разработка спецификации конвертора.

3.3 Интеграция графа потока данных в проект С++ на платформе Visual Studio Net 2005 с использованием конвертора.

3.4 Выводы.

ГЛАВА 4 ПРИМЕНЕНИЕ ГРАФА ПОТОКА ДАННЫХ ДЛЯ АНАЛИЗА И

ОПТИМИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ.

4.1 Применение граф-модели потока данных для оценки сложности вычислительных алгоритмов.

4.2 Анализ сложности реализации программных алгоритмов с целью их оптимизации на основе графа потока данных.

4.3 Модель графа потока данных для целей распараллеливания вычислительного алгоритма.

4.5 Выводы.

ГЛАВА 5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ МЕТОДОВ ДИАГНОСТИРОВАНИЯ ОШИБОК ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

5.1 Описание работы программы расчеты зачетов налоговых платежей.

5.2. Оптимизация диагностирования программы зачета налоговых платежей

5.3. Выводы.

Актуальность проблемы.

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

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

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

Проблема снижения трудоемкости диагностирования объектно-ориентированного программного обеспечения с целью локализации ошибок (под ошибкой понимаем дефект в программе, повлекший несоответствие требованиям спецификаций) - задача актуальная, поскольку на тестирование и отладку программного обеспечения уходит до 80 процентов затрат на разработку [48]. Основная проблема диагностирования программного обеспечения заключается в том, что ошибка, проявление которой выявлено на этапе тестирования, может находиться не в месте ее проявления. Тогда для упрощения локализации ошибок необходимо в процессе тестирования сохранять необходимую для целей диагностирования информацию о работе программы.

Фундаментальные теоретические и прикладные вопросы тестирования и диагностики программного обеспечения изложены в работах Майерса Г., Бейзера Б., Макгрегора Д., Боехма Б. и ряда других зарубежных авторов [72, 6, 48, 49]. Среди отечественных авторов следует отметить Липаева В.В. и Пархоменко П.П. [46, 52]. В качестве модели тестирования и диагностирования программного обеспечения в этих работах рассматривается управляющий граф программы. Следует отметить, что методы, разработанные для данной модели, хорошо зарекомендовали себя при тестировании и диагностике традиционного, процедурно-ориентированного программного обеспечения. При переходе к объектно-ориентированному программному обеспечению основные свойства объекта (инкапсуляция, наследование и полиморфизм) накладывают дополнительные особенности на тестирование и диагностику ошибок в программе. Кроме того, объектно-ориентированная парадигма подразумевает событийную управляемость. Это означает, что передача управления может осуществляться путем генерации сообщений различными объектами с дальнейшим разбором сообщений соответствующими обработчиками и передачей этих сообщений объектам, для которых данные сообщения предназначены. В результате модель в виде графа по управлению становится недостаточной для целей диагностирования программ объектно-ориентированной парадигмы.

В тоже время модель представления программ в виде графа потока данных, отражающего информационные зависимости между операциями над данными в программе, позволяет значительно расширить возможности автоматизации решения задач локализации ошибок за счет повышения информативности тестовых прогонов объектно-ориентированного программного обеспечения.

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

Цель работы

Разработка и исследование моделей, методов и алгоритмов диагностирования программ на граф-моделях потока данных с целью локализации местоположения ошибки в вычислительном программном коде. Автоматизация разработанных методов для их практического применения.

Методы исследования

В теоретических исследованиях диссертационной работы использовались методы теории графов, теории множеств, методы оптимизации, численное моделирование, модели, методы и алгоритмы теории надежности. Для практической апробации разработанных алгоритмов применено программное моделирование тестирования и диагностирования, реализованное на языке Delphi 5. Графический материал при проведении исследований получен с использованием пакета Microsoft Excel.

Объекты исследования

Объектами исследования являются программные реализации вычислительных алгоритмов на языке С++ для различных сред разработки.

Научная новизна диссертационной работы

1. Разработана граф-модель потока данных для тестирования и диагностирования программного обеспечения, позволяющая существенно сократить затраты по поиску и локализации ошибки в программном обеспечении за счет увеличения информативности тестирования.

2. Разработан алгоритм построения в фоновом режиме графа потока данных при тестировании программы с сохранением идентификаторов обработанных данных для целей диагностирования ошибок.

3. Разработан метод оптимизации списка операций, подвергаемых проверке в случае выявления несоответствия требованиям спецификаций, на основе анализа графа потока данных алгоритма.

4. Предложены критерии ранжирования операций над данными, подверженных проверке, в соответствии которым построена оптимальная последовательность их проверок. Получены оценки эффективности критериев ранжирования.

5. Разработан метод оценки сложности алгоритма с целью его оптимизации на базе граф-модели потока данных. Предложен метод автоматизации получения исходных данных для целей распараллеливания алгоритма с использованием граф-модели потока данных.

Практическая значимость работы

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

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

Разработанные математические модели и алгоритмы доведены до практической реализации, что подтверждено свидетельством о государственной регистрации программы для ЭВМ (Приложение 5). На защиту выносятся:

1. Модель тестирования и диагностирования объектно-ориентированного программного обеспечения в виде графа потока данных.

2. Алгоритм автоматизации построения графа потока данных в процессе тестового прогона программы.

3. Алгоритм анализа графа потока данных для локализации места возникновения ошибки.

4. Исследование, анализ и оценка эффективности разработанных алгоритмов диагностирования ошибок.

5. Применение модели графа потока данных для оценки сложности вычислительного процесса и его распараллеливания.

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на Всероссийских научно-технических конференциях

Информационные системы и технологии" ИСТ-2004, ИСТ-2005, ИСТ-2006, на Международной научно-технической конференции "Информационные системы и технологии" ИСТ-2007, на VI Международной конференции «Идентификация систем и задачи управления» 81СРЯО '07, на 11-й Нижегородской сессии молодых ученых (технические науки).

Публикации

По результатам диссертационной работы опубликовано 13 работ в печатных изданиях, в том числе 2 работы в издании, рекомендованном ВАК.

Структура и объем работы

Диссертационная работа изложена на 156 печатных листах, включает 18 рисунка и состоит из введения, 5 глав, заключения, списка литературы и 6 приложений.

4.5 Выводы

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

2. Разработанная модель тестирования и диагностирования вычислительных алгоритмов объектно-ориентированного программного обеспечения позволяет эффективно проводить оценку сложности вычислительных алгоритмов на этапе тестовых прогонов.

3. Анализ графа потока данных позволяет выявить фрагменты программного кода, оптимизация которых эффективна.

4. Применение модели тестирования и диагностирования вычислительного алгоритма в виде графа потока данных открывает широкие возможности для распараллеливания исполнения алгоритма по нескольким процессорам для целей увеличения производительности.

5. Анализ графа потока данных, полученного в процессе тестового прогона позволяет определить время выполнения параллельного алгоритма на множестве процессоров и оценить эффективность проведенного распараллеливания.

6. Оптимальная схема параллельного исполнения вычислительного алгоритма для целей диагностирования позволяет упростить процедуру локализации местоположения ошибки в программе за счет использования семантической близости вычислений.

ГЛАВА 5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ МЕТОДОВ ДИАГНОСТИРОВАНИЯ ОШИБОК ПРОГРАММНОГО

ОБЕСПЕЧЕНИЯ

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

Налоговые расчеты являются сложным вычислительным процессом из-за большого количества переменных, участвующих в расчете и большого количества зависимостей по данным между ними.

Современные средства автоматизирования диагностирования вычислительного процесса, применяемые для отладки программ налоговых расчетов, используют списки вызовов функций в процессе тестового прогонов и программы визуализации SQL-запросов в виде диаграмм.

Диаграммы SQL позволяют визуализировать запрос, отображая графически зависимости по данным на стадии проектирования. Список вызовов функций отображает зависимость исполняемых операторов в процессе тестового прогона.

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

5.1 Описание работы программы расчеты зачетов налоговых платежей

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

Решение задачи автоматизации зачетов платежей реализовано в специализированной программе.

С 2008 года вступили в силу некоторые изменения в НК РФ, которые были внесены Федеральным законом № 137-ФЭ. Внесение изменений в программу в соответствии с новыми требованиями ставят задачу проведения повторного тестирования и диагностирования программного продукта. Сложность и требования к качеству обуславливают применение средств автоматизированного тестирования и диагностирования.

ЗАКЛЮЧЕНИЕ

В данной диссертационной работе разработаны новые модели и методы процедур диагностирования вычислительных алгоритмов объектно-ориентированного программного обеспечения. Основные научные и практические результаты диссертации сводятся к следующему:

1. Разработана модель и методы тестирования и диагностирования вычислительных алгоритмов объектно-ориентированного программного обеспечения с минимальной модификацией программного кода для ее внедрения.

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

3. Выполнена адаптация разработанных методов для вычислительных алгоритмов различной природы и применение их для различных степеней детализации локализации ошибки.

4. Решена задача повышения информативности тестовых прогонов за счет добавления дополнительной информации о вычислительном процессе с помощью препроцессорных средств компилятора.

5. Проведен анализ и показана эффективность применения ранжирования списка операций, подверженных проверке по степени захода и сумме степеней исхода и захода.

6. Разработаны средства автоматизации предложенной модели в программный проект (конвертор).

7. На базе полученных алгоритмов разработано программное обеспечение для анализа результатов тестовых прогонов в программной среде Delphi.

1. Алферова З.В. Теория алгоритмов М.: Статистика, 1987.

2. Архангельский Б.В., Черняховский В.В. Поиск устойчивых ошибок в программах — М.: Радио и связь, 1989.

3. Ахо А. Построение и анализ вычислительных алгоритмов— М.: Мир, 1978.

4. Бардзинь Я.М., Бичевский Я.Я., Калныньш A.A. Построение полной системы примеров для проверки корректности программ — Ученые записки Латв. Гос. ун-та, 1974, т.210.

5. Безбородое Ю.М. Индивидуальная отладка программ — М.: Наука, 1982.

6. Бейзер Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и систем — СПб.: Питер, 2004.

7. Бичевский Я.Я., Борзов Ю.В. Развитие методов символического тестирования программ — М.: Автоматика и телемеханика, 1982, №2.

8. Благодатских В., Волнин В., Поскакалов К. Стандартизация разработки программных средств— М.: Финансы и статистика, 2005.

9. Блау С.А., Липаев В.В., Позин Б.А. Эффективность тестирования программных модулей— М.: Автоматика и телемеханика, 1984, №4.

10. Ю.Блау С. А., Позин Б.А. Анализ планов тестирования программных модулей с учётом нереализуемых маршрутов —

11. М.: Программирование, 1988, №4.

12. П.Борзов Ю.В. Тестирование программ с использованием символического исполнения— М.: Программирование, 1980, №1.

13. Борзов Ю.В., Дишлерс Г.Э., Медведис Н.Э., Уртанс Г.Б. Система символического тестирования ПЛ/1 программ — Управляющие системы и машины, 1986, №6.

14. З.Воеводин В.В. Параллельные вычисления — СПб.: БХВ-Петербург, 2002.

15. Гергель В.П. Теория и практика параллельных вычислений — http://www.intuit.rU/department/calculate/paralltp/l/paralltpl.html.

16. Гудман С. Хидетниеми С. Введение в разработку и анализ алгоритмов — М.: Мир, 1981.

17. Деревяго С. С++ 3rd: комментарии. — http://ders.stml.net/срр/, 2004.

18. Дмитриев Д.В. Алгоритмы тестирования вычислительных алгоритмов объектно-ориентированного программного обеспечения — Системы обработки информации и управления: Труды Нижегород. гос. техн. ун-та / НГТУ. Н.Новгород, 2005. -Т.54, В.12. - С.82-84.

19. Дмитриев Д.В. К вопросу о тестировании рекурсии методом автотрассировки в вычислительных алгоритмах — Информационные системы и технологии (Ист-2007): тез. докл. Всерос. научн.-техн. конф., Нижегород. гос. техн. ун-т. -Н.Новгород, 2007. С.241.

20. Дмитриев Д.В. Модель и алгоритмы тестирования объектно-ориентированного программного обеспечения — IV

21. Международная молодежная научно-техническая конференция «Будущее технической науки». Н.Новгород: НГТУ, 2005. -С.54-55.

22. Дмитриев Д.В. Модель тестирования объектно-ориентированного программного обеспечения — Информационные системы и технологии (Ист-2005): тез. докл. Всерос. научн.-техн. конф., Нижегород. гос. техн. ун-т. -Н.Новгород, 2005. С.144-145.

23. Дмитриев Д.В. Соколова Э.С. Модель и алгоритмы тестирования объектно-ориентированного программного обеспечения — Системы обработки информации и управления: Труды Нижегород. гос. техн. ун-та / НГТУ. Н.Новгород, 2005. -Т.54, В.12. - С.77-81.

24. Дмитриев Д.В. Соколова Э.С. Построение автотрассировочного графа для тестирования вычислительных алгоритмов— Журн. Системы управления и информационные технологии, №1 (31). -Воронеж, 2007.- С.47-51.

25. Дмитриев Д.В., Соколова Э.С. Обнаружение дефектов в процессе проектирования и эксплуатации программ — Научный журнал по теоретическим и экспериментальным проблемам ЕСТЕСТВЕННЫХ НАУК «Успехи современного естествознания». №2. Москва, 2004 - С.47-51.

26. Дмитриев Д.В., Соколова Э.С., Капранов С.Н. Адаптация генетических алгоритмов к решению задач назначения точек контроля в объектах с большим числом состояний— М.: Журн. Нейрокомпьютеры, №11. 2007. С.59-64.

27. Долбак Л.В. Методика отладки и испытаний управляющих алгоритмов и программ АСУ— М.: Программирование, 1984, №3.

28. Дробушевич Л.Ф. Оценка структурной сложности программ — М.: Программирование, 1987, №1.

29. Дробушевич Л.Ф. Метод оценки топологической сложности программ — Управляющие системы и машины, 1988, №4.

30. Ермаков Г.В. Тестирование MIXAL программ с помощью символического исполнения— М.: Программирование, 1988, №1.

31. Ерофеев В.И. Средства отладки программ в ОС ЕС ЭВМ — М.: Статистика, 1979.

32. Ершов Н.М. Построение графов вычислительных алгоритмов методом автотрассировки — М.: Программирование, 2000, №6.

33. Журнал Xaker Online — http://www.xakep.ru/post/36487/.

34. Иыуду К.А., Арипов М.М. Автоматизация генерации путей для тестирования программ, записанных на Фортране— М.: Программирование, 1986, №2.

35. Иыуду К.А., Арипов Н.М. Тестирование программ на основе минимального покрытия ее графа — Управляющие системы и машины, 1985, №4.

36. Катков В.Л., Шимаров В.А. Статический анализ программы с помощью её управляющего графа— Управляющие системы и машины, 1986, №2.

37. Катков ВЛ., Ермаков Г.В. Система автоматизации тестирования М1ХАЬ программ — М.: Программирование, 1985, №3.

38. Колякин Ю.Д. Отладка программного обеспечения в диалоговой многотерминальной системе — Управляющие системы и машины, 1983, №2.

39. Корнеев В.В. Параллельные вычислительные системы — М.: Нолидж, 1999.

40. Коростиль Ю.М., Гуляев В.А. Комплекс программ для диагностирования программных модулей микропроцессорных систем — Управляющие системы и машины, 1988, №3.

41. Косяченко С.А., Кульба В.В., Мамиконов А.Г., Соколова Е.Б. Использование сетей Петри для локализации ошибок в процессе системной отладки комплексов программ— М.: Автоматика и телемеханика, 1988, №5.

42. Котляров В.А. Основы тестирования программного обеспечения — Курс лекций. Университет информационных технологий: www.intuit.ru.

43. Кудинов А. Отладка приложений на С++ — http://www.devdoc.ru/index.php/content/view/debugging p3.htm.

44. Кулямин В.В. Стандартизация и Тестирование Выполнения Математических Функций в вычислениях с плавающей точкой —

45. М.: Программирование, 2007, №3.

46. Липаев В.В. Отладка систем управляющих алгоритмов ПВМ реального времени — М.: Сов. радио, 1974.

47. Липаев В.В. Тестирование программ — М.: Радио и связь, 1983.

48. Липаев В.В., Серебровский Л.А., Гаганов П.Г. Технология проектирования комплексов программ АСУ — М.: Радио и связь, 1983.

49. Майерс Г. Искусство тестирования программ — М.: Финансы и статистика, 1982.

50. Макгрегор Д., Сайке Д. Тестирование объектно-ориентированного программного обеспечения — М.: О1а8ой, 2002.

51. Макконелл Дж. Основы современных алгоритмов— М.: Техносфера, 2004.

52. Париш А., Бори Р., Кодес Д. Автоматизированное Тестирование на Базе Потокового Графа Объектно-Ориентированных Программных Модулей — Журнал Систем и ПО, № 23, 1993.

53. Пархоменко П.П., Правильщиков П.А. Диагностирование программного обеспечения— М.: Автоматика и телемеханика, 1980, №1.

54. Поваров Г.Н. О структурной теории сетей связи — Сб.: Проблемы передачи информации, Изд-во АН СССР. -1959, вып. 1.

55. Позин Б.А. Метод структурного построения тестов для отладки управляющих программ— М.: Программирование, 1980, №2.

56. Правильщиков П.А. Построение тестов для программ — М.:

57. Автоматика и телемеханика, 1977, №5.

58. Риндфлайт Д. Отладка программ в системах 360/370 на основе дампов памяти ОС — М.: Машиностроение, 1982.

59. Сагунов В.И. Диагностирование кратных ошибок в программных модулях — М.: Программирование, 1988, №4.

60. Сагунов В.И., Соколова Э.С., Беляева С.И. Диагностирование кратных ошибок в программных модулях— М.: Деп. в ИНФОРМприбор., 1989, №4561.

61. Синицын C.B. Налютин Н.Ю. Верификация программного обеспечения — http : //www. intuit .ru/department/se/ver ify/3 /.

62. Таненбаум Э. Архитектура компьютера — СПб.: Питер, 2002.

63. Торопов Д.И. О построении тестирующих маршрутов программы — Управляющие системы и машины, 1987, №6.

64. Уртанс Г.Б. Функции путей программы— М.: Программирование, 1987, №4.

65. Франкл П., Джей И. Подходящее семейство Критериев Тестирования Потока Данных — ИИЭР Труды по Разработке ПО, том 14, № 10, Октябрь 1988.

66. Хазаров A.M., Цвид С.Ф. Методы оптимизации в технической диагностике машин — М: Машиностроение, 1984.

67. Шимаров В.А. Об одном методе тестирования программы на основе минимального покрытия ее графа — Управляющиесистемы и машины, 1988, №5.

68. Шимаров В.А. Средства поддержки структурного тестирования программ — Управляющие системы и машины, 1988, №2.

69. Шураков В.В. Надежность программного обеспечения систем обработки данных — М.: Статистика, 1981.

70. Шураков В.В. Надежность программного обеспечения систем обработки данных — М.: Финансы и статистика, 1987.

71. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods — Prentice Hall, Englewood Cliffs, New Jersey, 1989.

72. Boehm B. Software Engineering Economic Prentice —- Hall, Inc, N.J. 1981.

73. Burnstein I/ Practical Software Testing. A process-oriented approach — Springer-Verlag, New York, 2003.

74. Buyya R. High Performance Cluster Computing. Volume 1: Architectures and Systems. Volume 2: Programming and Applications — Prentice Hall PTR, Prentice-Hall Inc., 1999.

75. Culler D., Singh J.P., Gupta A. Parallel Computer Architecture — A Hardware/Software Approach Morgan Kaufmann, 1998.

76. Hockney R.W., Jesshope C.R. Parallel Computers 2. Architecture, Programming and Algorithms — Adam Hilger, Bristol and1. Philadelphia, 1988.

77. IEEE 754 Стандарт чисел с плавающей точкой — 1985.

78. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing. — The Benjamin/Cummings Publishing Company, Inc., 1994 (2nd edn., 2003).

79. Mc Cabe T.I. A complexity measure — IEEE Trans. Software Eng., 1976, 2, №4.

80. Patterson D.A., Hennessy J.L. Computer Architecture: A Quantitative Approach. 2d ed — San Francisco: Morgan Kaufmann, 1996.

81. Quinn M.J Parallel Programming in С with MPI and OpenMP — New York, NY: McGraw-Hill, 2004.

82. Ramamoorthy C.V., Kim K.H., Chen W.T. Optimal placement of software Monitors Aiding. Systematic Testing— IEEE Trans. Software Eng., 1975, v. SE-1, № 4.

83. Ramamoorthy C.V., Sin Bun F. Ho., Chen W.T. On the automated generation of program test data— IEEE Trans. Software Eng, 1976, v. SE-2, № 4.

84. Roong-Ko Doong, Phyllis G. Frankl. ACM Transactions on Software Engineering and Methodology, April 1994.

85. Shekhar H. Kirani, Wei-Tek Tsai Method Sequence Specification and Verification of Classes — Object-Oriented Programming, October 1994.

86. Tanenbaum A. Modern Operating System. 2nd edn. — Prentice Hall, 2001.

87. Turner C.D., Robson D.J. The State-Based Testing of Object-Oriented Programs, Proceedings of IEEE Conference on Software Maintenance, 1993.

88. Xu Z., Hwang K. Scalable Parallel Computing Technology, Architecture, Programming — Boston: McGraw-Hill, 1998.