- •Оглавление
- •6 Тестирование 88
- •8.3 Организация разработки программного изделия 215
- •8.4 Организация обслуживания разработки программного изделия 230
- •8.5 Организация выпуска документации 239
- •8.6 Организация испытаний программных изделий 248
- •1 Введение. Проблемы современного программирования
- •2 Этапы разработки программного обеспечения
- •2.1 Анализ требований, предъявляемых к системе
- •2.2 Определение спецификаций
- •2.3 Проектирование
- •2.4 Кодирование
- •2.5 Тестирование
- •2.6 Эксплуатация и сопровождение
- •2) Определение спецификаций;
- •3) Проектирование;
- •4) Кодирование;
- •Контрольные вопросы
- •1. Этапы разработки программного обеспечения.
- •2. Анализ требований, предъявляемых к системе.
- •3 Методы разработки программного обеспечения как научная дисциплина
- •3.1 Методы управления разработкой
- •3.1.1 Выполнение проекта
- •3.1.2 Методика оценки затрат
- •3.1.2.1 Методика инженерно-технической оценки затрат
- •3.1.2.2 Оценка на основе распределения Рэлея
- •3.1.3 Контрольные точки
- •3.1.4 Средства разработки
- •3.1.5 Надежность
- •3.2 Методы проведения разработки программного обеспечения
- •3.3 Развитие методов разработки программного обеспечения
- •3.3.1 Язык определения задач и анализатор задач
- •3.3.2 Система структурного анализа и проектирования sadt
- •3.3.3 Система srem
- •3.3.4 Методика Джексона
- •3.4 Выводы
- •Контрольные вопросы
- •1. Методы разработки программного обеспечения как научная дисциплина.
- •4 Методы разработки программного обеспечения
- •4.1 Язык проектирования программ
- •4.2 Стратегия проектирования
- •4.2.1 Нисходящее проектирование и нисходящая разработка
- •4.2.2 Структурное проектирование
- •4.3 Данные
- •4.3.1 Обзор структур данных
- •4.3.1.1 Массивы
- •4.3.1.2 Структуры
- •4.3.1.3 Списки
- •4.3.1.4 Очереди
- •4.3.1.5 Стеки
- •4.3.1.6 Множества
- •4.3.1.7 Графы
- •4.3.1.8 Деревья
- •4.3.2 Абстрактные конструкции
- •4.3.2.1 Фиксированные типы данных абстрактного типа
- •4.3.2.2 Размещение указателей
- •4.3.2.3 Защита данных от несанкционированного доступа
- •Контрольные вопросы
- •2. Нисходящее проектирование и нисходящая разработка.
- •9. Абстрактные конструкции.
- •5 Правильность программ
- •5.1 Аксиомы
- •5.2 Правила преобразования данных
- •5.3 Доказательства правильности программ
- •Контрольные вопросы
- •1. Правильность программ.
- •6 Тестирование
- •6.1 Психология и экономика тестирования программ
- •6.2 Экономика тестирования
- •6.2.1 Тестирование программы как черного ящика
- •6.2.2 Тестирование программы как белого ящика
- •6.2.3 Принципы тестирования
- •6.3 Ручное тестирование
- •6.3.1 Инспекции и сквозные просмотры
- •6.3.2 Инспекции исходного текста
- •6.3.3 Список вопросов для выявления ошибок при инспекции
- •6.3.3.1 Ошибки обращения к данным
- •6.3.3.2 Ошибки описания данных
- •6.3.3.3 Ошибки вычислений
- •6.3.3.4 Ошибки при сравнениях
- •6.3.3.5 Ошибки в передачах управления
- •6.3.3.6 Ошибки интерфейса
- •6.3.3.7 Ошибки ввода-вывода
- •6.3.3.8 Другие виды контроля
- •6.3.4 Сквозные просмотры
- •6.3.5 Оценка посредством просмотра
- •6.4 Проектирование теста
- •6.4.1 Тестирование путем покрытия логики программы
- •6.4.1.1 Покрытие операторов
- •6.4.1.2 Покрытие решений
- •6.4.1.3 Покрытие условий
- •6.4.1.4 Покрытие решений/условий
- •6.4.1.5 Комбинаторное покрытие условий
- •6.4.2 Эквивалентное разбиение
- •6.4.2.1 Выделение классов эквивалентности
- •6.4.2.2 Построение тестов
- •6.4.3 Анализ граничных значений
- •6.4.4 Применение функциональных диаграмм
- •6.4.5 Предположение об ошибке
- •6.4.6 Стратегия
- •Контрольные вопросы
- •3. Принципы тестирования.
- •9. Анализ граничных значений.
- •11. Предположение об ошибке.
- •7 Технология разработки программ
- •7.1 Разбиение задачи на независимые подзадачи
- •7.2 Разбиение задачи на одинаковые по сложности части
- •7.3 Рекурсия и динамическое программирование
- •7.3.1 Рекурсия
- •7.3.2 Динамическое программирование
- •7.3.3 Моделирование
- •7.4 Поиск
- •7.4.1 Поиск в списках
- •7.4.2 Деревья поиска
- •7.4.3 Стратегия распределения памяти
- •7.5 Сортировка
- •7.6 Алгоритм выбора из конечного состояния
- •7.7 Сопрограммы
- •Контрольные вопросы
- •8 Методы управления проектированием программных изделий
- •8.1 Организация управления проектированием программного изделия
- •8.1.1 Понятие изделия как средства общения
- •8.1.2 Нисходящий анализ процесса управления проектированием программного изделия
- •8.1.3 Организация взаимодействия
- •8.1.4 Установление целей, средства их достижения
- •8.1.5 Подбор и обучение кадров
- •8.2 Организация планирования разработок программного изделия
- •8.2.1 Виды планов
- •8.2.2 Декомпозиция планов
- •8.2.3 Организационная структура группы планирования
- •8.2.4 Планы, связанные с созданием программных изделий
- •8.2.5 Опытный образец изделия
- •8.2.6 Организация планирования в фазе исследования
- •8.2.7 Организация планирования в стадии анализа осуществимости
- •8.2.8 Организация планирования в фазах конструирования и кодирования
- •8.2.9 Организация планирования в фазах оценки и использования
- •8.2.10 Обязанности группы планирования при рассмотрении и утверждении планов разработки программного изделия
- •8.3 Организация разработки программного изделия
- •8.3.1 Организация разработки программного изделия в фазе исследований
- •8.3.2 Организация разработки программного изделия в фазе анализа осуществимости
- •8.3.3 Организация разработки программного изделия в фазе конструирования (проектирования)
- •8.3.4 Организация разработки программного изделия в фазе программирования
- •8.3.5 Организация разработки программного изделия в фазе оценки
- •8.3.6 Окончание проекта
- •8.3.7 Участие группы разработки в фазовых обзорах
- •8.4 Организация обслуживания разработки программного изделия
- •8.4.1 Организационная структура группы обслуживания
- •8.4.2 Организация обслуживания программного изделия в фазе исследования
- •8.4.3 Организация обслуживания в фазах анализа осуществимости и конструирования
- •8.4.4 Организация обслуживания в фазе программирования и оценки
- •8.4.5 Организация обслуживания в фазе использования
- •8.4.6 Участие группы обслуживания в фазовых обзорах
- •8.5 Организация выпуска документации
- •8.5.1 Организационная структура группы выпуска документации
- •8.5.2 Стандарты и практические руководства
- •8.5.3 Организация выпуска документации в фазах исследований и анализа осуществимости
- •8.5.4 Организация выпуска документации в фазах конструирования и программирования
- •8.5.5 Организация выпуска документации в фазах оценки и использования
- •8.5.6 Участие группы выпуска документации в фазовых обзорах
- •8.6 Организация испытаний программных изделий
- •8.6.1 Современное состояние методов обеспечения качества программного изделия
- •8.6.1.1 Виды испытаний программного изделия. Стадии испытаний
- •8.6.1.2 Режимы испытаний программ
- •8.6.1.3 Категории испытания программного изделия
- •8.6.2 Организационная структура группы испытаний
- •8.6.3 Организация испытаний в фазах исследований и анализа осуществимости
- •8.6.4 Организация испытаний в фазах конструирования и программирования
- •8.6.5 Организация испытаний в фазе оценки
- •8.6.6 Организация испытаний в фазе использования
- •8.6.7 Участие группы испытаний в фазовых обзорах
- •Контрольные вопросы
- •1. Понятие изделия как средства общения.
- •4. Подбор и обучение кадров.
- •6. Организационная структура группы планирования.
- •Список литературы
7.4.2 Деревья поиска
Если данные организованы как структура дерева, алгоритм поиска сводится к алгоритму, просматривающему все узлы дерева. Для ведения поиска существуют два основных алгоритма поиска: поиск в глубину и поиск в ширину.
Поиск в глубину. При поиске в глубину каждая ветвь дерева просматривается слева направо.
Для двоичных деревьев алгоритм поиска имеет простую рекурсивную структуру (рис. 7.1):
Рис. 7.1 — Схема поиска по двоичному дереву
DEPTHFIRST: procedure(TREE);
declare 1 TREE,
2 KEY,
2 ARGUMENT, /* данные */
2 RightSon, /* ноль, если нет сына*/
2 LeftSon; /* ноль, если нет сына */
if TREE = null then return;
if текущий узел не KEY then do;
call DEPTHFIRST(LtftSon);
call DEPTHFIRST(RightSon);
end;
end DEPTHFIRST;
Заметим, что если дерево упорядочено таким образом, что LeftSon имеет ключ, величина которого меньше, чем значение корневого узла, а величина ключа для RightSon больше, чем значение корневого узла, то такой алгоритм аналогичен алгоритму двоичного поиска.
Поиск в ширину. Это алгоритм поиска, при котором просматривается каждый уровень в направлении сверху вниз (рис. 7.2).
Рис. 7.2 — Поиск в ширину
При таком алгоритме параллельного поиска быстро находятся кратчайшие ветви дерева. В общем виде алгоритм имеет структуру:
BREADTHFIRST: procedure(solution);
declare 1 TREE,
2 ARGUMENT, /* данные */
2 SONS(N); /* произвольные деревья */
declare (solution, NextStep) set of TREE;
/* переход вниз для каждого уровня */
do while (solution 0);
NextStep = {TREE.SONS(I) для всех I и TREE
в solution};
call BREADTHFIRST(NextStep);
end;
end BREADTHFIRST;
Поиск в ширину очень популярен при решении задачи о лабиринте.
Поиск с возвратом. Для многих алгоритмов часто требуется перебор возможных вариантов решения задачи. Один из таких способов перебора называется поиском с возвратом.
Алгоритм:
Вызвать первую часть;
do while (не окончится);
вызвать следующую часть;
do while (нет возможности продолжить);
Вернуться на предыдущий уровень;
Проверить возможность альтернативного решения
для этого уровня;
end;
end;
Алгоритм поиска в глубину является примером поиска с возвратом:
Начать с корневого узла;
do while (существуют не просмотренные узлы);
Перейти к узлу «левый сын», если возможно;
Иначе перейти к узлу «правый брат»;
do while (нет узлов «левый сын» и «правый брат);
Перейти к узлу «отец»;
Перейти к узлу «правый брат», если можно;
end;
end;
7.4.3 Стратегия распределения памяти
Одним из типов поиска являются задачи по распределению памяти (наиболее характерны они при создании ОС), однако во многих прикладных алгоритмах эти задачи возникают при создании прикладных программ, работающих с большим объемом данных. Если до начала обработки полный объем данных, которые подлежат обработке, неизвестен, то используется общий подход для распределения областей этой памяти согласно заданным требованиям.
Дана фиксированная область памяти, задача заключается в том, чтобы занимать и освобождать меньшие области памяти большой областью, без выхода за границы памяти. При распределении памяти проверяются наибольшие свободные области. Обычно эти области малы для размещения в них всех данных, и, следовательно, память становится фрагментной. Имеются следующие способы уменьшения фрагментности.
Первое возможное размещение. Последовательно просматриваются области памяти, пока не найдется первая, достаточная для размещения. Вся область организована в список и упорядочена по адресам (рис. 7.3).
Рис. 7.3 — Схема распределения памяти
Поиск в этом списке осуществляется последовательно до тех пор, пока не будет найдена достаточно большая область для размещения данных. Тогда эта область изымается из списка, а на это место помещается меньшая свободная область — оставшаяся незанятая часть исключенной области. С помощью этого метода легко освобождать ранее занятые области памяти. С этой целью просматривается список, как только он будет упорядочен по адресам, то нетрудно найти место, чтобы пометить освобожденную область памяти. Соседние адреса — смежные в списке, поэтому легко объединить две свободные области в одну, большую по размеру.
Данный способ самый простой, однако поскольку занятие области памяти осуществляется после нахождения первой области, достаточной для размещения данных, память становится фрагментной.
Наилучшее размещение. Последовательно просматриваются все области, выбирается наименьшая область, размер которой больше или равен требуемому объему для размещения данных. В этом случае области связываются друг с другом по размеру, а не по адресам. Алгоритм размещения-освобождения аналогичен первому возможному размещению. Однако в этом случае стратегия размещения приводит к меньшей фрагментности, потому что используется область наименьшего размера для размещения данных. Однако так как свободная область не упорядочена по адресам, алгоритм объединения двух свободных областей в область большего объема довольно сложен.
Сопрягаемые области памяти. Областями памяти являются N цепочек размером 2N каждая. Если область размером 2K отсутствует, а имеется свободная область размером 2K+1, то она разбивается на две сопрягаемые области размером 2K. После того как области освободятся, они рассматриваются как области размером 2K, которые можно объединить в область размером 2K+1.