Методическое пособие по выполнению практических заданий _Осущест. Методическое пособие по выполнению практических заданий

• Название: Методическое пособие по выполнению практических заданий
• Дата: 10.03.2023
• Размер: 2.03 Mb.
• Имя файла: Методическое пособие по выполнению практических заданий _Осущест.docx
• Тип: Методическое пособие; #979604
• страница: 3 из 4

Алгоритм симплекс-метода

Последовательность действий можно описать следующим образом:

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

• 
  находится так называемое опорное решение, служащее «точкой отсчета»;
  
• 
  последовательно перебираются вершины симплекса. Если в данной точке значение критерия больше (или меньше) предыдущего, то процесс продолжается. Когда значение критерия уже нельзя улучшить, значит, решение найдено.
  

То есть, смысл симплексного метода следующий: все линейные неравенства, которым в многомерном пространстве соответствуют полуплоскости, ограничивают некий симплекс. При этом уравнению, описывающему оптимизируемый критерий, соответствует гиперплоскость.

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

Практический пример применения симплексного метода

Решим симплексным методом задачу. Максимизируем функцию

L=X+Z→max

при ограничениях

{Y−X+Z=1,X−2Z+T=2.

У нас есть четыре переменные – X,Y,Z,T – причем критерий зависит лишь от двух переменных. Примем Т и Y за базисные переменные и выразим их через остальные две свободные переменные. Получим:

L=X+Z→max,

{Y=1+X−Z,T=2−X+2Z.

При X и Z равных нулю, базисные переменные равны Y=1,T=2. Значение критерия L=0. Значит, точка (1,0,0,2) является базисным решением. Начнем перебор вершин симплекса. Увеличить критерий можно увеличив Z до единицы. Тогда при Z=1,X=0 базисные переменные примут значения Y=0,T=4. Новое допустимое решение – это точка (0,0,1,4), критерий равен L=1.

Теперь выразим Z и T через Y и X:

L=1−Y+2X→max,

{Z=1−Y+Z,T=4−2Y+X.

Увеличить L можно только увеличив X. Однако X можно увеличивать бесконечно, исходя из системы уравнений. Следовательно, критерий L будет принимать неограниченно большие значения, решения задачи симплекс-методом не существует. В этом случае говорят, что имеет случай бесконечного симплекса.

Ход работы:

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

Завод	Транспортные издержки, ф. ст. за единицу Торговый склад						Предложение т
	1	2	3	4	5
A	20	27	33	25	34	200
B	22	36	34	28	26	250
C	26	29	27	26	28	300
Потребность, т	100	150	200	100	200

Требуется определить минимальную стоимость транспортировки на декабрь.

Р ешатель:



Практическая работа 9.

Тестирование и отладка программ.

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

Выполнение программы с целью обнаружения ошибок называется тестированием. Виды ошибок и способы их обнаружения (Таблица 4)

Таблица 4.



Тест – это набор контрольных входных данных совместно с ожидаемыми результатами. В число входных данных время зависимых программ входят события и временные параметры. Ключевой вопрос – это полнота тестирование: какое количество, каких тестов гарантирует, возможно, более полную проверку программу? Исчерпывающая проверка на всем множестве входных данных недостижима.

• 
  В любой нетривиальной программе на любой стадии ее готовности содержатся необнаруженные ошибки;
  

• 
  Тестирование – технико-экономическая проблема, основа на компромиссе время – полнота. Поэтому нужно стремиться к возможно меньшему количеству хороших тестов с желательными свойствами.
  

Свойства Теста:

Детективность: тест должен с большой вероятностью обнаруживать возможные ошибки.

Покрывающая способность: один тест должен выявлять как можно больше ошибок.

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

Используются два вида критериев:

• 
  Функциональные тесты составляются исходя из спецификации программы;
  

• 
  Структурные тесты составляются исходя из текста программ.
  

Таблица 5. Виды критериев и их функциональность





Рис.10 (Траектории вычислений при структурном тестировании).

Тестирование «белого ящика» и «чёрного ящика».

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

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

Порядок разработки тестов.

По внешней спецификации разрабатываются тесты:

• 
  Для каждого класса входных данных;
  

• 
  Для граничных и особых значений входных данных.
  

Контролируются все ли классы выходных данных, при этом проверяются и добавляются при необходимости нужные тесты.

Систематическое тестирование предполагает также ведение журнала отладки, в котором фиксируется ошибка и в дальнейшем – исправление.

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

Аксиомы тестирования:

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

1. 
   Автор теста – не автор программы.
   
2. 
   Тесты разрабатываются одновременно или до разработки программы.
   
3. 
   Необходимо предсказывать ожидаемые результаты теста до его выполнения и анализировать причины расхождения результатов.
   
4. 
   Предыдущее тестирование необходимо повторять после каждого внесения исправлений в программу.
   
5. 
   Следует повторять полное тестирование после внесения изменений в программу или после переноса её в другую среду.
   
6. 
   В те программы, в которых обнаружено много ошибок, необходимо дополнить первоначальный набор тестов.
   

Автоматизация тестирования.

А. Автоматизация прогона тестов актуальная для 5-6 аксиомы Майерса. Пишутся командные файлы для запуска программы с каждым тестом из набора и сравнением реального результата с ожидаемым.

Б. Средства автоматизации подготовки тестов и анализа их результатов.

1. 
   Генераторы случайных тестов в заданных областях входных данных. Отладчики (для локализации ошибок).
   
2. 
   Анализаторы динамики. Обычно входят в состав отладчиков; применяются для проверки соответствия тестовых наборов структурных критериев тестирования.
   
3. 
   Средства автоматической генерации структурных тестов методом «символического выполнения» Кинга.
   

Модульное тестирование.

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

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

Являясь по способу исполнения структурным тестированием или тестированием «белого ящика», модульное тестирование характеризуется степенью, в которой тесты выполняют или покрывают логику программы. Тесты, связанные с структурным тестирование, строятся по следующим принципам:

• 
  На основе анализа потока управления. В этом случае элементы которые должны быть покрыты при прохождении тестов, определяются на основе структурных критериев тестирования С0, С1, С2. К ним относятся вершины, дуги, пути управляющего графа программы (УГП), условия, комбинации условий и т.п.
  

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

Тестирование на основе потока управления.

К особенностям использования структурных критериев тестирования С0, С1, С2 следует добавить критерий покрытия условий, заключающийся в покрытии всех логических условий в программе. Критерии покрытия решений и условий не заменяют друг друга, поэтому на практике используются комбинированный критерий покрытия условий/решений, совмещающий требования по покрытию и решений, и условий.

Тестирование на основе потока данных.

Этот вид тестирования направлен на выявление ссылок на неинициализированные переменные и избыточные присваивания.

Методы проектирования тестовых путей для достижения заданной степени тестированности в структурном тестировании.

Процесс построения набора тестов при структурном тестировании принято делить на три фазы:

• 
  Конструирования УГП;
  

• 
  Выбор тестовых путей;
  
• 
  Генерация тестов, соответствующих тестовым путям.
  

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

На третей фазе по известным путям тестирования осуществляется поиск подходящий тестов, реализующих прохождение этих путей.

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

• 
  Статические методы;
  
• 
  Динамические методы;
  
• 
  Методы реализуемых путей.
  

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

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

Методы реализуемых путей. Данная методика заключается в выделении из множества путей подмножества всех реализуемых путей.

Интеграционное тестирование.

Интеграционное тестирование – это тестирование части системы, состоящей из двух и более модулей. Основная задача интеграционного тестирования – поиск дефектов.

Интеграционное тестирование применяется на этапе сборки модульного оттестированных модулей в единый комплекс. Известны два метода сборки модулей:

• 
  Монолитный характеризующийся одновременным объединением всех модулей в тестируемых комплекс.
  

• 
  Инкрементальный, характеризующийся пошаговым наращиванием комплекса программ с пошаговым тестирование собираемого комплекса. Выделяют две стратегии:
  

-“Сверху вниз” и “Снизу вверх”.

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

Недостатки нисходящего тестирования:

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

• 
  Сложных организации и разработки среды для реализации исполнения модулей в нужной последовательности
  
• 
  Параллельная разработка модулей верхних и нижних уровней приводит к ней всегда эффективной реализации модулей из-за подстройки ещё тестировании модулей нижних уровней уже к оттестированным модулям верхних уровней
  

Системное тестирование.

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

Категории тестов системного тестирования:

1. 
   Полнота решения функциональных задач.
   

1. 
   Стрессовое тестирование (предельные объемы).
   
2. 
   Корректность использования ресурсов.
   
3. 
   Оценка производительности.
   
4. 
   Эффективность защиты.
   
5. 
   Проверка инсталляции.
   
6. 
   Корректность документации.
   

Эффективность и оптимизация.

Средства оптимизации, используемые компиляторами, делят на две группы:

• 
  Машинно-зависимые (ориентированы на конкретный язык, выполняют оптимизацию кода на уровне машинных команд);
  

• 
  Машинно-независимые (выполняют оптимизацию на уровне входного языка).
  

Способы уменьшения времени выполнения.

При их написании необходимо:

• 
  Выносить вычисление константных, т.е не зависящих от параметров цикла, выражений из циклов;
  

• 
  Избегать «длинных» операций;
  
• 
  Минимизировать преобразование типов в выражениях;
  
• 
  Оптимизировать записи условных выражений;
  
• 
  Исключать многократные обращения к элементам массивов по индексам;
  
• 
  Избегать использования различных типов в выражении и т.п.