A b a a d

A b e c d a c b b d b a b a a d

A b a a d

A b e c d a c b b d b a b a a d

1 3 5 0 5

A b c d e

Начало поиска ведется с первой позиции:

Последний символ образца совпадает с наложенным символом d строки, а предпоследний нет, то есть K =1. Из таблицы смещений для символа c строки находим L = 5. Сдвигаем образец вправо на L - K = 4 позиции:

Последний символ образца не совпадает с символом b строки, значит K =0, а L = 3. Сдвигаем образец вправо на L - K = 3 позиции:

a b e c d a c b b d b a b a a d

a b a a d

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

a b e c d a c b b d b a b a a d

a b a a d

Теперь в соответствии со смещением для символа b из таблицы сдвигаем образец на 3 позиции и получаем искомое вхождение образца:

a b e c d a c b b d b a b a a d

a b a a d

Для кодовой таблицы, состоящей из 256 символов, таблица смещений будет представлять собой массив целых чисел, индексы которого изменяются от 0 до 255 и соответствуют кодам символов. Имеется много модификаций описанного алгоритма [9, 10]. Некоторые из них строятся на основе использования теории конечных автоматов.

Эффективность алгоритма Бойера – Мура в среднем выше по сравнению с алгоритмом КМП, но существенно зависит от длины текста и длины образца. Так при длине строки до 10 символов он показывает себя хуже, даже чем последовательный поиск. Алгоритм КМП менее чувствителен к размерности текста и образца. Его можно использовать как универсальный, когда неизвестны длины строки и образца.

Алгоритм Рабина работает быстрее последовательного, но медленнее КМП, однако простота и малые трудозатраты на реализацию делают его привлекательным для использования в неспециальных программах.

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

Мы рассматривали точное совпадение символов образца и текста. Существует много разновидностей неточного поиска [10]. Например, можно не учитывать окончаний слов, искать по нескольким образцам, допускать наличие символов, не принадлежащих образцу и т. п.

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

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

Другое определение [7]: тестирование - это процесс выполнения программы с целью обнаружения в ней ошибок. Такое определение цели стимулирует поиск ошибок в программах. Отсюда также ясно, что “удачным” тестом является такой, на котором выполнение программы завершилось с ошибкой. Напротив, “неудачным можно назвать тест, не позволивший выявить ошибку в программе.

В [7, 8] сформулированы основные принципы организации тестирования:

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

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

3. По тем же соображениям организация - разработчик программного обеспечения не должна “единолично” его тестировать (должны существовать организации, специализирующиеся на тестировании программных средств).

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

5. Нужно тщательно подбирать тест не только для правильных (предусмотренных) входных данных, но и для неправильных (непредусмотренных).

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

7. Следует сохранять использованные тесты (для повышения эффективности повторного тестирования программы после ее модификации или установки у заказчика);

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

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

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

Существует два основных вида тестирования: функциональное и структурное.

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

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

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

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

Наиболее слабым из критериев полноты структурного тестирования является требование хотя бы однократного выполнения (покрытия) каждого оператора программы. Более сильным критерием является так называемый критерий С1: каждая ветвь алгоритма (каждый переход) должна быть пройдена (выполнена) хотя бы один раз.

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

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

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

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

В тестирование многомодульных программных комплексов можно выделить четыре этапа:

· тестирование отдельных модулей;

· совместное тестирование модулей;

· тестирование функций программного комплекса, то есть поиск различий между разработанной программой и ее внешней спецификацией;

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

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

Литература

1. Кнут Д. Искусство программирования. Тома 1-3. – М.: Издат. дом “Вильямс”, 2003.

2. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1980. – 406 c.

3. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. – 360 с.

4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с.

5. Лэнгсам И., Огенстайн М., Тенебаум А. Структуры данных для персональных ЭВМ. – М.: Мир, 1989. – 568 с.

6. Трамбле Ж., Соренсон П. Введение в структуры данных. – М.: Машиностроение, 1982. - 784 с.

7. Майерс Г. Надежность программного обеспечения. – М.: Мир, 1980. – 360 с.

8. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. – М.: Мир, 1980. – 278 с.

9. Фараонов В.В. Турбо Паскаль 7.0. Практика программирования: Учебное пособие. – М.: Нолидж, 1997. – 432 с.

10. Нильсон Н. Искусственный интеллект. Методы поиска решений. – М.: Мир, 1973. – 270 с.

11. Автоматизация поискового конструирования / Под ред. А.И. Половинкина. – М.: Радио и связь, 1981. – 344 с.

12. Топп У., Форд У. Структуры данных в С++. – М.: Бином, 2000. – 815 с.

13. Галочкин В.И. Структуры и организация даннных в ЭВМ: Методические указания к выполнению лабораторных и расчетно-графических работ для студентов второго курса специальности 2204. – Йошкар-Ола: 1994. – 42 с.

14. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Издат. дом “Вильямс”, 2003. – 382 с.

15. Нехорошкова Л.Г. Управление проектами: лабораторный практикум. – Йошкар-Ола: МарГТУ, 2009. – 151 с.

16. Окулов. С. М. Программирование в алгоритмах. – М.: БИНОМ, 2006. –383 с.

17. Бентли Дж. Жемчужины программирования: 2-е издание. – СПб.: Питер, 2002. – 272 с.

18. Меньшиков, Ф.В. Олимпиадные задачи по программированию / Ф.В. Меньшиков. – СПб.: Питер, 2003. – 315 с.

19. Смит, Б. Методы и алгоритмы вычислений на строках. – М.: Изд. дом «Вильямс», 2006. – 496 с.

20. Галочкин В.И. Алгоритмы и программы. Задачи повышенной сложности: учебное пособие. – Йошкар-Ола: ГОУ ВПО МарГТУ, 2012. – 208 с.

Содержание

1. Типы данных
2. Линейные списки
2.1. Стеки
2.2. Очереди
2.3. Двусвязные списки и мультисписки
3. Деревья
3.1. Организация в памяти и рекурсивный обход
3.2. Обход деревьев с помощью стека
3.3. Пример программы с обходами дерева
3.4. Прошитые деревья. Леса
4. Графы
4.1. Представление графа. Транзитивное замыкание
4.2. Пример программы с использованием матрицы смежности
4.3. Поиск путей на графе в глубину
4.4. Поиск путей на графе в ширину
4.5. Алгоритмы поиска кратчайших путей Дейкстры и Флойда
4.6. Остовные деревья
4.7. Поиск циклов на ориентированных графах
5. Поиск данных
5.1. Последовательный, индексно- последовательный, бинарный поиск
5.2. Бинарные деревья поиска
5.3. Балансировка деревьев поиска
5.4. Б-деревья
5.5. Хеширование
6. Сортировка данных
6.1. Методы внутренней сортировки
6.2. Методы внешней сортировки
7. Алгоритмы перебора вариантов
7.1. Поиск с возвратом
7.2. Метод ветвей и границ
7.3. Игровые деревья. Принцип минимакса
7.4. α – β отсечение 7.5. Поиск в ширину. Волновой алгоритм 7.6. Рекуррентные соотношения 7.7. Динамическое программирование
7.8. Эвристические алгоритмы 8. Длинная арифметика
9. Смешанные системы счисления
10. Перестановки различных элементов
10.1. Лексикографический порядок
10.2. Векторы инверсий
10.3. Транспозиция смежных элементов
10.4. Случайные перестановки
11. Подмножества множеств
11.1. Коды Грея
11.2. K-подмножества (сочетания) 12. Трудоемкость алгоритмов 13. Строки
14. Тестирование и отладка программ
Литература

Дата добавления: 2014-01-11