- •Оглавление
- •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 Поиск
Поиск — это процесс нахождения нужных значений в некотором множестве. Семейство элементов может быть структурированным либо нет. Если оно не структурировано, поиск обычно означает нахождение нужного элемента в списке. Если семейство элементов структурировано (дерево, граф и др.), то под поиском понимают нахождение правильного пути в структуре.
Обычно каждый элемент имеет три компонента:
ключ — это элемент, используемый для доступа к данным (он может быть именем в справочнике, словом в индексе или названием раздела в таблице);
аргумент — это числа, связанные с элементом (адрес, номер телефона и др.);
структуру — это дополнительная информация, принимаемая для описания данных, такая, как адрес следующего элемента в семействе и т.п.
7.4.1 Поиск в списках
Данный поиск проводится четырьмя различными способами: прямым, линейным, двоичным и хешированием.
Прямой поиск. При прямом поиске местоположение элемента определяется непосредственно с помощью ключа (комната в здании). Прямой поиск применяется тогда, когда число элементов фиксировано и их сравнительно немного.
Линейный поиск. Данный вид поиска наиболее простой для программной реализации, хотя его выполнение занимает много времени. Элементы проверяются последовательно, по одному, пока нужный элемент не будет найден. В отличие от прямого поиска здесь нет системы в расположении элементов. Если список содержит N элементов, то каждый раз в среднем будут проверяться N/2 элементов. Линейный поиск медленный, но позволяет легко добавлять новые элементы, помещая их в конец списка. Хорошо разработанная программа обычно имеет простую (линейную) структуру, и, следовательно, такую же структуру должны иметь и данные, поэтому линейный поиск в таких структурах эффективен.
Двоичный поиск. Для ведения двоичного поиска ключи должны быть упорядочены по величине или алфавиту. В этом случае можно добиться среднего времени поиска log2N. При двоичном поиске ключ сравнивается с ключом среднего элемента списка. Если значение ключа больше, то та же самая процедура повторятся для второй половины списка, если же меньше, то для первой. Таким образом, за шаг этого процесса список уменьшается наполовину.
Основная трудность при двоичном поиске — как вводить новые элементы. Так как список упорядочивается, то введение нового элемента может вызвать переписывание всех элементов для того, чтобы новый элемент поместить в нужном месте.
Хеш-поиск. Этот вид поиска является попыткой применить прямой поиск для поиска в больших наборах данных. Из изначального значения ключа вычисляется значение псевдоключа, называемого хеш-кодом, и этот код используется как индекс в таблице адресов элементов. Если все ключи соответствуют разным хеш-кодам, то любой элемент будет найден за один прямой поиск.
Пример. В абстрактном компиляторе может быть отведено 1000 мест для имен переменных. В языке допускаются слова из 6 символов. Это позволяет создавать 266 имен, что гораздо больше, чем размер таблицы символов. Но если каждое число, представляющее имя, уменьшить до числа, находящегося между 0 и 999, то имена могут быть записаны в таблицу. Алгоритмы вычисления хеш-кодов различны, например имя (ключ) можно рассматривать как двоичное число. Это число можно разделить на размер таблицы, остаток использовать как код. Другие алгоритмы предлагают сложение битов внутри числа или некоторые другие функции с ключом.
Недостатком хеш-поиска является тот факт, что некоторые идентификаторы могут иметь одинаковые хеш-коды, поэтому возникает проблема обработки пересечений элементов, т.е. элементов, имеющих одинаковые хеш-коды. Когда определенное значение хеш-кода встречается первый раз, его помещают в определенное место в таблице. Если произошло пересечение с другим элементом, его помещают в другое место в соответствии со следующим алгоритмом:
INSERT: procedure (ключ, аргумент);
declare 1 TABLE(размер),
2 KEY,
2 ARGUMENT;
declare хеш–код;
Вычислить хеш–код;
/* если запись находится в таблице */
if TABLE(хеш-код).KEY = ключ then return;
/* обработка совпадающих хеш-кодов */
do while (TABLE(хеш-код).KEY0 &
TABLE(хеш-код).KEYключ);
хеш–код = новое значение, зависящее от
(хеш–код, ключ);
end;
TABLE(хеш-код).KEY = ключ;
TABLE(хеш-код).ARGUMENT = аргумент;
end INSERT;
Таким образом, в случае пересечения элементов имеется переход к следующему месту в таблице. Если нужное место занято, — то переход на место, расположенное на некотором расстоянии от занятого, или вычисление нового хеш-кода, исходя из имеющегося ключа и кода.
Основным недостатком хеш-поиска является тот факт, что при плотном заполнении таблицы алгоритм ввода элементов весьма трудоемок.