Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Мухина, Светлана Анатольевна
01.01.09
Кандидатская
2009
Москва
64 с.
Стоимость:
499 руб.
Оглавление
1 Введение
1.1 Диаграмма Хассе
1.1.1 Степени вершин
1.1.2 Длины цепей, соединяющих две вершины
1.1.3 Мощность антицепей
1.1.4 Геометрические свойства диаграммы Хассе
1.2 Бинарный алфавит
1.3 д-ичный алфавит
2 Бинарный алфавит
2.1 Основные понятия и определения
2.2 Метод коэффициентов
2.3 Установление связи между характеристиками частичного порядка
“быть фрагментом”
2.3.1 Независимость от вида фрагмента
2.3.2 Рекуррентное соотношение для п,&)
2.3.3 Точное соотношение для 7дг(т, п, к)
2.3.4 Следствия
2.3.5 Примеры
3 д-ичный алфавит
3.1 Основные понятия и определения
3.2 Число слов, содержащих в качестве фрагмента фиксированное
слово а
3.3 Серийное представление слов
3.4 Число фрагментов д-ичного слова
3.5 Композиция слов
3.6 Примеры
3.7 Мощность антицепей
Глава
Введение
1.1 Диаграмма Хассе
Комбинаторика слов представляет собой важный раздел дискретной математики, имеющий глубокое внутреннее содержание, разнообразные связи со многими классическими областями современной математики и многочисленные приложения в теории информации, математической генетике, структурной лингвистике и т.д.
Основным объектом исследования являются слова, множества слов, части слова, связь частей слова, упорядоченность на множестве слов.
Итак, пусть В — {01,02,, ая} - ц-ичный алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а € В*, то любое слово а', полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на В*, который мы будем обозначать стандартным образом
а' < а, (1.1)
есди а' - фрагмент а.
Геометрически отношение (1.1) описывается с помощью диаграммы
веса Хэмминга т, содержащих в качестве фрагмента заданное слово длины п и веса Хэмминга к.
Пример 2.6 Пусть к — 0. Тогда справделиво
при N — т п,
Кт; (2.19)
0, при N — т < п.
Рм(т,п, 0)
Данное соотношение следует из примера 2.5 (случай к = 0 и а = 0", см. раздел 2.3.3) и независимости функции Р(т,п, к) от вида фрагмента. Пример 2.7 Пусть к = 1. Тогда справделиво
1)=(т)-(т+т”2)' (2'20)
Действительно, при к — 1 имеем:
**»» и - х? (;:!) (*-„:*+0 (2-21)
у=п—1 4 ' 4 '
Подробное вычисление суммы (2.21) представлено в примере 2.5 (случай к = 1 и а = 0П_11, см. раздел 2.3.3).
Пример 2.8 Пусть к = 2. Тогда справедливо
„ , /т + п — 3 (т + п- 4
ЗДт.п,2)=(Д-( т т_1 (ЛГ-т.-гг+З). (2.22)
Действительно, при к — 2 ’’явное” выражение для функции Ддг(т, п, 2) принимает вид:
ТМт, п, 2) = СУ ~ 0 ( АГ М ~ У )
+ Vп — 3 / ЛГ — тп — п + 2
у=п-2 4
т+п-4 / 1 / дг
/2/ — 1Л
Название работы | Автор | Дата защиты |
---|---|---|
Задачи оптимизации структуры многоуровневых иерархических систем | Ерзин, Адиль Ильясович | 1984 |
Решения кооперативных динамических игр | Корниенко, Елена Алексеевна | 2003 |
Вопросы построения комитета несовместной системы неравенств | Кобылкин, Константин Сергеевич | 2005 |