XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 114

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 114)

зависимая 486 -- обобщенная 487 726 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Грамматика контекствотвободная 487 -- однозначная 600 — левояииейная 487 — линейнзя 487 — неукорачивающзя 486 — общего вида 486 - порождающая 472 — правоякнейнэя 487 — регулярная 488 — типа 0 486 — Хомского 472 Грамматики эквававентные 478 Грани параяяеяьные 382 — соседние 382 Грань булеза куба 381 — множества верхющ 79 -- — точная 80 -- нижняя 79 --- точная 80 — последовательности вешщяя точная 82 -- нижшщ точная 83 ГраФ ацикяический 280 — бесконтурный 280 График отображения 1, 41 — соответствяя 44 Граф конечного автомата с выходом 552 — КС-грамматики 613 — неориентированный 276 — — ассоциированный 287 -- взвешенный 307 -- размеченный 307 -- связный 285 — ориентированный 276 — — взвешенный 307, 327 -- размеченный 307, 327 Граф ориентированный сильно связный 286 — слабо связный 288 — соответствия 46 Графы изоморфные 342 Группа 125 — абеяева 126 — автоморфнэмов 346 - аддитивная действительных чисел 164 ---- по модулю 1 165 -- кольца 136 -- целых чисел 127 — вычетов по модулю й аддитивная — коммутативная 126 — конечная 134 — мультипликатявная вычетов по модулю р 142 -- действительных чисел 127 -- поля 140 -- рациональных чисел 127 — — тела 140 — неразложимая 154 — подстановок 127 - - и-й степени 1, 137 — симметрическая множества 127 -- степени и 127 — циклическая 133 Группоид 121 Группы изоморфные 161 Деление 131 Делители нуля 139 Делитель нормальный 162 Дерево вывода 587 — — цепочки в КС-грамматике 594 -- частичное 590 727 Дерево неориентированное 297 — ориентированное 297 — — бинарное 300 --- полное 300 — остовное 304 — — наименьшего веса 308 — помеченное 591 — — Л-свободное 594 — решений 302 — упорядоченное 592 он Диаграмма конечного автомата с выходом 552 — Хассе 81 Диамант 222 Дизъюнктор 448 Дизъюнкциз 1, 95, 385 — злементарнав 406 Дистрибутивность бесконечная 61 Длина вывода 476, 634 — ДНФ 410 — кортежа 39 — пути 278 — слова 463 — цепи 278 ДМП-автомат 688 ДНФ 406 — кратчайшая 410 — минимальная 409 — сокращеннав 412 — тупиковая 420 Доминирование Тб Дополнение 208 — булево 210 — графа неориентированного 346 -- ориентированного 346 — множества 1, 38 Дуга 277 — древесная 321 — заходящая 277 — инцидентная 277 — исходящая 277 — обратнав 322 — поперечная 322 — прямая 321 — пустав 504 — стартовая Т14 Единица кольца 135 — моноида 121 — полукольца 175 — полурешетки 216 — решетки 221 — функции нижняя 436 Единицы мнимые 169 Задача анализа конечного автомата 519 — глобального анализа графов 311 — о кратчайших расстояниях 327 -- перечислении путей 327 — — путях общая 328 — синтеза конечного автомата 518 — сортировки 302 — структурного синтеза конечного автомата с выходом 556 — транзитивного замыканял ориентированного графа 326 — Штейнера 306 Закон сокращения левый 129 -- правый 129 Законы де Моргана 209 --- бесконечные 61 728 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Замыкание множества булевых функций 400 — относительно операции 232 — рефлексивно-транзитивное 69 — элемента 190 Запись аддитивная 126 — мультипликативнвл 126 Значение неопределеное 703 — формулы 399 Изоморфизм 244 — графов 342 — групп 158 — колец 166 — многосортный 270 Импликанта 408 — простая 412 -- избыточнвя 419 — — ядровае 418 Импликацпл 1, 85, 385 Инверсия конечной подстановки 567 — морфизма 565 — набора 434 — цепочки 488 Инвертор 448 Индекс подгруппы в группе левый 154 Иньекцил 1, 41 Иррефлексивность 62 Источник сати 349 Итерация позитивная 469 — элемента 190 — языка 469 Карта Карно 414 Квадрат бинарного отношения 54 — декартов 39 Кваэипорядок 66 Квантор всеобщноств 1, 88 — существования 1, 88 Кватернион сопрлженный 170 КЗ-грамматика 486 — обобщенная 487 КЗ-правило 486 КЗ-язык 489 — обобщенный 489 Класс подгруппы по элементу смежный левый 152 ----- правый 152 — Поста 436 — эквивалентности 70 — языка 488 КНФ 406 Кольца изоморфные 167 Кольцо 135 — булево 173 — вычетов по модулю й 137 — коммутативное 136 — линейных операторов 137 — эндоморфизмов абелевой группы 253 Команда 505 — прнменимая к конфигурации 633 Комбинация линейнае 1х', 359 Композиция бинарных отношений на множестве 54 — соответствий 51 Компонента (связности) 285 — слабой связности (слабая) 288 Компоненты одноименные 39 Конгруэнцил 237 — многосортнзя 273 Конец дуги 277 — отрезка левый 260 -- прелый 260 — пути 278 729 Конец ребра 277 — цепи 278 — цепочки 467 Конкатенация кортежей 123 — слов 466 — языков 468 Константа 23 — булева 375 — индивиднал 23 Конституэнта единицы 406 — нули 407 Контекст КЗ-правила левый 486 -- правый 486 — левый 675 Контур 279 Конус верхний 80 — низсний 80 Конфигурация автомата 496 — выводимая 634 — заключительнал 634 — конечного автомата 499 — машины Тьюринга 571 — МП-аитомата 633 — начальнал 634 — непосредственно вмводимая 633 — тупиковаи 634 Конъюнктор 448 Конъюнкция 1, 85, 385 — элементарнал 406 Координаты точки П1, 33 Корень ориентированного дерева 297 Кортеж 1, 30 — пустой 123 Коэффициенты биномиальные 1, 100 Критерий Поста 439 Крона дерева 588 Крыло вхождения левое 466 — — правое 466 КС-грамматика 487 — однозначная 600 КС-язык 489 — детерминированный 689 Куб булев 210 — декартов 39 — единичный размерности и 377 -- и-мерный 377 Куст 300 Лента входная автомата 495 Лес неориентированный 299 — ориентированный 299 — остовный 304 -- глубинный 318 -- поиска в глубину 318 Лист 298 Литерал 405 Магазин МП-автомата 625 Маркер начала ленты 570 Массив 292 — лидеров 292 Матрица булева 290 — доствжимости 294 — инциденций 289 — меток дуг 328 — симметрическая П1 — смежности вершин 290 Машина Тьюринга 570 -- в алфавите 576 — — детерминированнал 572 -- над алфавитом 576 Метка входная 713 — дуги 307 -- входнаи 553 -- выходная 553 730 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Метка пути 329 -- магазинная 712 — ребра 307 Метод Блейка 425 — Гаусса 1П, 1УУ вЂ” двух включений 34 — неопределенных коэффициентов 432 — определенна семантики аксиоматический 699 - последовательного исключения неизвестных 199 — характеристических функций 103 — эквивалентных преобразований 37 Механизм управления выводом 673 Минимизацня конечного автомата 531 Множества равномощные 1, 89 — равные 29 Множество булевых функций замкнутое 401 --- полное 401 — вполне упорядоченное 81 - замкнутое относительно операции 147 --- операций 230 — континуаяьное 96 — линейно упорядоченное 77 — мощности континуума 96 — не более чем счетное 93 — пустое 1, 31 — слов в алфавите перечисяимое (по Тьюрингу) 577 ---- разрешимое (по Тьюрингу) 577 — состояний машины Тьюринга конечное 570 Множество счетное 1, УΠ— универсаяьное 1, ЗΠ— упорядоченное 75 -- индуктивное 83 — и-эяементное 30 — П-замкнутое 230 Модель 227 — анализирующая 494 — порождающая 494 — распознающая 494 Модуль над кольцом левый 145 — -- правый 145 Моноид 121 — кольца мультипликативный 136 — полукольца аддитивный 176 -- мультипликативный 176 — свободный 124 — симметрический 122 Мономорфкзм 244 Морфием 564 — инверсный 565 — обратный 565 — языка 566 - — инверсный 566 — Л-свободный 565 Мощность континуума 96 — множества 1, 90 МП-автомат 625 — детерминированный 638, 688 — расширенный 688 — эквизаяентный КС-грамматике 640 МП-автоматы эквивазентные 635 Муяьтиграф ориентированный 711 Набор буяев 210 — единичный 210 — значений переменных 376 — нулевом 210 731 Наборы взаимно противоположные 434 Направэение грани 381 Начало дуга 277 — пути 278 — цепочки 466 Нейтраяьный элемент моноида 121 Нетерминая 473 Норма кватернвона 170 Носитель 226 — алгебры 117 Нуль 114 — кольца 135 — левый 114 — относительно операции 114 — пояукояьца 175 — пояурешетки 2 16 — правый 114 — решетки 221 Нумерация 90 — лексикографическая 463 Область значений отображения 41 — значения соответствия 45 — определения соответствия 45 — — частичного отображения 43 — опредеяенности состояния памяти 703 — применимости машины Тьюринга 573 — целостности 141 Образ группы гомоморфиый 159 — кольца гомоморфный 167 — множества при отображении 1, 43 — системы гомоморфный 244 — элемента прн отображении 1, 40 Объединение булево 208 — множеств 1, 88 Объединение решеточное 217 — семейств 269 Ограничение бинарного отношения на подмножество 60 — соответствия на подмножества 58 ОД-функция 555 ОКЗ-грамматика 487 ОКЗ-язык 489 Октава 170 Оператор булез 387 — нулевой 1Ч, 137 — тождественный 1Н, 187 Операции буяевы 210 Операция ассоциативная 114 — бинарная 113 — идемпотентнэя 114 — коммутативная 114 — конкатенарнэя 696 — логическая 24 — многосортиае 266 — нуяьарнзя 113 — решеточная 217 — унарназ 113 — в-ерная 113, 267 — и-местная 113 Определение функции как процедуры 575 Определения взаимно двойственные 81 Основа 684 — вхождения 466 Отец 298 Отношение бинарное 49 -- на множестве 45 ---- антисимметрвчное 63 — — - - иррефяексивное 62 ---- обратное 57 732 ПРЕДМЕТНЫЙ УКАЗА ТЕЛЬ Отношение бинарное на множестве плотное 65 ---- рефлексивное 62 ---- симметричное 63 ---- транзитивное 64 — взаимной достижимости 286 — включения 62 — выводимости 475 двойственное к отношению порядка 75 доминирования 76 достижимости 279 квазнпорлдка 66 линейного порядка 77 — непосредственной выводимости 475 -- достижимости 277, 277 — порядка бб — предпорядка 66 — равенства по модулю 71 — смежности 341 — строгого порядка 66 — — предпорядка 66 — толерантности бб — функциональное по компоненте 50 — частичного порядка 66 — эквивалентности бб — и-арное на множестве 48 - — (и-местное) 48 Отображение биективное 1, 49 — иньективное 41 монотонное 83 на 42 непрерывное 83 обратное 1, 50 сюрьективное 42 тождественное 41 Отображение частичное 43 Отрезок 260 Отрицание 1, 95, 384 — набора 434 Очередь 308 Палиндром 488 Память внутренняя автомата 495 Парадокс Рассела 101 Пара неупорядоченная 37 — упорядоченная 1, 30 Пары упорядоченные равные 38 Пентагон 222 Переименование нетерминалов грамматики 485 Переменное 24 — булево 375 — булевой функции 376 — индивидное 24 — существенное 388 — фиктивное 388 Пересечение булево 208 — множеств 1, 39 — решеточное 217 — семейств 269 — языков суженное 667 Перестановка 1, 100 Переход нз состояния в состояние 504 Петля 277 Подвлгебра 231 — многосортная 269 Подграф 283 — максимальный 284 — остовный 284 — порожденный 284 -- множеством вершин 284 — собственный 284 733 Подгруппа 149 — нетривиальная 149 — нормальная 162 — собственная 149 - тривиальная 149 — циклическая, порожденная элементом а 150 Подгруппоид 148 — собственный 149 Поддерево 300 — максимальное 598 Подкольцо 151 Под уб 383 Подмножество собственное 1, 34 — строгое 34 — упорядоченное 77 Подмоноид 148 — нетривиальный 149 — собственный 149 — тривиальный 149 Подполе 151 Подполугруппа 148 — собственная 149 Подполукольцо 203 Подпространство линейное 1Н Подсемейство 269 Подсистема алгебраической системы 230 Подслово 466 Подстановка 1, 131 — конечная 566 -- инверсная 567 — языков в язык 654 Подтело 151 Подформула 399 Подфраза первого уровне 694 — фрзвы 694 Подход интенсиональный 698 — экстенсиональный 698 Подцепочка 466 Поиск в глубину 312 -- ширину 312 Поле 140 — вычетов по модулю р 142 — действительных чисел 141 — комплексных чисел 141 — рациональных чисел 140 — упорядоченное 228 -- непрерывное 229 Полипом Жегалкина 431 -- первой степени 431 Полугруппа 121 — коммутативная 122 — симметрическая 122 — циклическая 133 Полукольцо 175 — взаимное 204 — двойственное 204 — замкнутое 182 — идемпотентное 176 — коммутативное 176 — матриц над полукольцом 198 — регулярных языков 490 — симметричное 204 — с итерацией 203 Полурешетка 124 — верхняв 214 — наживя 214 Полустепень захода 277 — исхода 277 Порядок 66 — булез 378 — двойственный 75 734 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Порядок естественный идемпотентного полукольца 180 — — полурешетки 213 -- решетки 219 — индуцироввнный 77 — конечной группы 134 — лексикографический 380 - линейный 77 — строгий 66 — частичный 66 — числовой естественный 67 — элемента 134 Последовательность 91 — конфигураций допускающая для цепочки 635 — неубывающая 82 Постфикс цепочки 467 Потомок 298 — подлинный 298 Правило вывода 473, 699 — — контекстно-зависимое 486 -- КС-грамматики цепное 603 — обобщенного поглощения 425 -- склеивания 425 Прагматика языка 462 Предикат 27 — тождественно истинный 28 — — ложный 28 — характеристический 30 Предложение 699 Предок 298 — подлинный 298 Предпорядок 66 — строгий бб Представление об аягоритме интуитивное 575 Предшественник 278 Преемник 278 Преобразование формулы тождественное 402 — — эквивалентное 402 Преобразователь состояний памяти 703 — стирающий 704 Префикс цепочки 466 Признак детерминированности азгоритма 575 — массовости алгоритма 575 — результативности алгоритма 575 Применимость правила вывода 475 Принцип гомоморфной интерпретации 696 — двойственности 205 -- для упорядоченных множеств 81 Пробяема непустоты для конечного автомата 531 — принадлежности 494 — пустоты дяя КС-грамматяк 611 — синтаксического анализа 673 — соответствий Поста 579 Продукцил 473 Проекция конечного автомата с выходом входная 554 — кортежа 39 Произведение 126 — линейных операторов 1Ч, 137 — множеств декартово (прямое) 1, 39 — прямое алгебраических систем 254 — соответствий 51 Прообраз множества 1, 43 — элемента при отображении 1, 41 Пространство линейное 1Ч -- над полем 147 — цепей графа 359 730 рострвнство цикяов графа 359 Путь 278 — в муяьтиграфе 712 — замкнутый 280 — простой 279 СДНФ 406 Семантика денотационнвя 702 — операционаяьнзя 702 — смешанных вычислений 702 — трансформвционнав 702 — языка 461 Равносильность 25 Разбиение 70 — тривиальное 70 Размерность кортежа 39 Размещение без повторений 1, 100 Разность 130 — множеств 1, 33 -- симметрическая 1, 33 Ранг коцикяический 364 — пути 337 — циклический 364 Расстояние по пути 327 Ребро 277 — буяева куба 382 — древесное 317 — инцидентное 277 — обратное 317 Результат применения машины Тьюринга к слову 572 -- операции 113 Рефяексивность 62 Решетка 217 — дистрибутивная 222 Свойство "ство кояяективизирующее 30 — непрерывности 228 — нуля аннуяирующее 139, 176 — характеристическое 30 Связка логическая 24 Сдвиг левый 146 — правый 146 Семейство множеств (индексированное) 60 -- конечное 60 -- не более чем счетное 93 -- счетное 60 — П-замкнутое 269 Сеть 349 — буяева 380 — ориентированная 349 — простая 356 Сечение соответствия 45 — — по множеству 45 Сигиатура 226 — алгебры 117 — многосортнвя 266 Символ 462 — входной конечного автомата 503 — — обозреваемый 626 — выходной 552 — магазина верхний 627 -- начальный 629 — магазинный 627 — направления двяжения головки 570 — недостизсимый 612 — нетерминзяьный 473 -- бесполезный 610 — пустой 570 — строгого включения 34 — терминальный 473 Симметричность 63 Синтаксис языка 460 736 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Система алгебраическая 226 -- конечнал 227 — команд автомата 496 — - мап1ины Тьюринга 570 — — МП-автомата 628 — координат првмоугольная 1П --- декартова 1 - обрзлувнцих 232 -- многосортной алгебры 270 — уравнений линейных алгебраических П1, !43 — формальная 699 Системы алгебраические изоморфные 244 -- однотинные 229 Скаляр модуля 267 Склейка простая 411 СКПФ 406 Слово 463 — пустое 463 Сложение 126 — кольца 135 — полукольца 175 — по модулю 2 385 --- й 128 Сложность алгоритма 290 — СФЭ 453 Событие ХЧ1, 973 Соединение кортежей 123 — слов 466 — языков 468 Соответствие 44 взаимно однозначное 42 всюду определенное 45 обратное 57 пустое 44 универсальное 44 Соответствие функциональное по компоненте 48 Сорт 266 Сортировка топологнческвя 350 Состояние блока управления автомата 495 --- заключительное 497 --- нвчазьиое 497 — конечного автомата 502 --- заключительное 502 --- начальное 502 --- поглощающее 525 --- с выходом 552 ----- заключительное 552 ----- начальное 552 — МП-автомата заключительное 629 -- начальное 629 — памяти 702 -- всюду неопределенное 703 Сочетание 1, !00 Список инцидентности 291 — смежности 291 — — вершины 292 Стек 318 Степень вершины 277 — декартова нулевая 123 — множества декартова 39 — элемента 133 — и-я декартова 254 Стоимость прохождения 329 Сток сети 349 Стратегия „перенос — свертка" 689 Стрелка Пирса 385 Суженке соответствия на подмнозсество 59 ---- строгое 59 Сумма бесконечная 184 — линейных операторов 1Ч, 137 — по модулю й 128 - частичная 187 — элементов последовательности 183 Суперпозиция над множеством 400 - функций 395 — языков в язык 654 СФЭ 449 Схема из функциональных элементов над базисом 449 — над базисом 449 Сын 298 Сюръекцил 1, 43 — каноническая 73 Таблица истинности 26 — Квайна 425 — критериальная 443 — Кэпи 143 — структурная 559 — управляющая 675 Такт работы автомата 495 -- МП-автомата 629 Тезис Тьюринга 576 Тело 140 Теорема 699 — Кантора 94 — Кантора — Бернштейна 98 — Кэпи 252 — Лагранжа 154 — о детерминизации 521 -- квадрате 98 — — неподвижной точке 85 — Ферма малая 155 Теория формальная 699 Терминал 473 Ткп оперыши 267 Тождества кольца основные 137 — полукольца основные 176 Тождество 403 — обобщенного поглощения 425 -- склеивания 425 — поглощения 207, 217 — теоретико-множественное 36 Толерантность 66 Точка отображения неподвижная 1, 65 --- наименьшая 85 Транзитивность 64 Транспозиция 1, 131 Триггер 557 Узел 276 Умножение 126 — в группе (групповое) 126 — кольца 135 — левое 147 — полуковьца 175 — правое 147 Уравнение леволинейное 199 — праволинейное 199 Уравнения канонические конечного автомата с выходом 557 Уровень вершины 349 -- ориентированного дерева 300 Устройство управления машины Тьюринга 570 Утверждение 699 Сйуактор-алгебра многосортная 272 Фактор-группа по нормальному делителю 164 Фактор-кольцо 251 Фактор-множество 71 740 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ о.

Характеристики

Список файлов книги