Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Пантелеев, Павел Анатольевич
01.01.09
Кандидатская
2006
Москва
101 с. : ил.
Стоимость:
499 руб.
1 Отличимость состояний при искажениях на выходе
1.1 Д-отличимость
р 1.2 /г-отличимость
1.3 ^-отличимость
1.4 Решетчатые автоматы
2 Отличимость состояний при искажениях на входе
2.1 Отличимость множеством слов
2.2 /г-кратная отличимость
2.3 ^-кратная отличимость
2.4 Кратно-приведенные автоматы
3 Сложность безусловных диагностических экспериментов
^ 3.1 Оценка сложности безусловного диагностического
эксперимента
Существенный прогресс в области информационных технологий, наметившийся в последние десятилетия неизбежно ведет к все большему усложнению используемых вычислительных систем. Это делает актуальным проблему тестирования подобных систем, а также создание соответствующего математического аппарата.
Конечные автоматы широко используются при моделировании систем в различных областях, таких, как интегральные микросхемы, некоторые виды программ (лексические анализаторы, поиск по образцу), а в последнее время и в коммуникационных протоколах.
Проблема тестирования конечных автоматов изучалась многими авторами, и в этой области получены математические результаты, имеющие как теоретическое, так и прикладное значение. Самые ранние работы в этой области датируются еще пятидесятыми годами прошлого столетия. В статье Э. Мура "Умозрительные эксперименты с последовательностными машинами" [9] впервые формально определяется понятие эксперимента с автоматами, имеющее центральное значение в области тестирования конечных автоматов. В этой же работе автор получает ряд оценок
сложности некоторых видов экспериментов, а также показывает их достижимость. Более систематическое изучение сложностных характеристик экспериментов с автоматами было проведено А. Гиллом[11]. Им впервые были получены оценки длин различных видов диагностических экспериментов.
Дальнейшее изучение диагностических экспериментов было проведено М.Н. Соколовским[16, 17], который получил асимптотику функции Шеннона длины простого условного диагностического эксперимента для всех состояний автомата, а также достаточно точные оценки для подмножеств состояний. Он также первым обозначил связь между диагностическими экспериментами и сложностью порождения элементов в полугруппах[18].
Еще в работе Мура[9] была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с верхней, получил A.A. Карацуба[12], а также, независимо от него, Т. Хиббард[5]. Последний автор также получил точную оценку для безусловного установочного эксперимента.
В последнее время эксперименты с автоматами находят практическое применение в задаче тестирования коммуникационных протоколов, используемых при построении локальных сетей, а также сети Internet[l, 8]. Коммуникационный протокол представляет собой набор правил, регламентирующих процесс обмена информацией в сети. Он описывается некоторым формальным документом, называемым стандартом. У стандарта может быть несколько программных реализаций. Стандарт протокола и его реализации моделируются конечными автоматами. Задача тестирования реализации протокола заключается в проверке того, что
1.4. Решетчатые автоматы
Рис. 1.7.
П-П гш гш
лл _Ш шиш пл гипш
ЛЛ :_Ш ШЛ ШЛ
Рис. 1.8. Примеры графов Серпинского
Название работы | Автор | Дата защиты |
---|---|---|
Консенсусное мультиагентное управление стохастическими системами | Амелина, Наталья Олеговна | 2012 |
Методы анализа устойчивости асимптотически инвариантных множеств | Купцова, Светлана Евгеньевна | 2006 |
Рекуррентные решения задач оценивания при комбинированных возмущениях | Дигайлова, Ирина Анатольевна | 2003 |