Максимизация числа различных подслов
Наверно, наиболее очевидный способ интерпретации «как можно более разнообразного поведения» слова — это наличие у него как можно большего числа различных подслов.
В слове длины N имеется всего
N + (N-1) + (N-2) + … + 2 + 1 = N(N+1)/2 (*)
подслов (слагаемые соответствуют подсловам длины 1, 2 и т.д.). Можно попытаться максимизировать количество разных подслов, сделав все подслова какой-то длины k различными. При этом все подслова большей длины тоже автоматически будут различны, т.е. мы получим как минимум (N-k+1)(N-k+2)/2 разных подслов длины k и больше. Значение k при этом можно выбрать так, чтобы максимизировать полученное выражение при фиксированном N, т.е. как можно меньше.
При этом имеется всего mk разных m-слов длины k, а если они все реализуются как подслова одного слова, длина этого слова должна быть не меньше mk+k-1. Предположим, что существуют такие «наиболее плотные» слова, что все их подслова длины k различны и в то же время включают в себя все возможные m-слова длины k, и они нам известны. Тогда для заданного N можно найти минимальное k, такое, что N ? mk+k-1, т.е. m(k-1)+(k-1)-1 < N ? mk+k-1, и в качестве искомого слова взять начало длины N соответствующего «наиболее плотного» слова. Это гарантирует различие всех подслов длины k в нем.
Для того, чтобы еще увеличить количество разных подслов в нашем слове, можно попытаться найти «наиболее плотное» слово для (k-1), которое продолжается в «наиболее плотное» слово для k. Взяв начало этого последнего мы получим наилучший результат — в полученном слове длины N все подслова минимально возможной длины k различны, и в то же время в нем в качестве подслов содержатся все возможные слова длины (k-1) и, соответственно, меньшие — все слагаемые в формуле (*) имеют максимальные возможные значения.
Осталось выяснить два момента.
- Существуют ли «наиболее плотные» слова для всех m и k, и если это так, можно ли их продолжать до «наиболее плотных» слов для m и (k+1)? Есть ли достаточно эффективные алгоритмы для построения таких слов?
- Какой тестовой гипотезе, т.е.
какому допущению относительно свойств тестируемой системы, соответствует выбранное понимание «наиболее разнообразного» поведения слова? Для какого рода систем этот подход дает действительно оптимальное покрытие различных возможных ситуаций?
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий