Новиков Ф.А. Дискретная математика для программистов (860615), страница 69
Текст из файла (страница 69)
Мир, 1979.3. Владимиров Д. А. Булевы алгебры. Наука, 1969.4. Евстигнеев В. А. Применение теории графов в программировании. Наука,1985.5. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции потеории графов. Наука, 1990.6.
Зыков А. А. Основы теории графов. Наука, 1987.7. Кук В., Бейз Г. Компьютерная математика. Наука, 1990.8. Липский В. Комбинаторика для программистов. Мир, 1988.9. Романовский И. В. Дискретный анализ. Невский диалект, 1999.10. Яблонский С. В.,Лупанов О. Б. Дискретная математика и математическиевопросы кибернетики. Наука, 1974.11. Яблонский С. В. Введение в дискретную математику. Наука, 1986.12. Карпов Ю. Г. Теория автоматов. Питер, 2002.13. Андерсон Д.
Дискретная математика и комбинаторика. Вильяме, 2003.14. Кнут Д. Искусство программирования для ЭВМ. т. 1. основные алгоритмы.Мир, 1977.15. Кнут Д. Искусство программирования для ЭВМ. т. 2. получислеппыеалгоритмы. Мир, 1977.16. Кнут Д. Искусство программирования для ЭВМ. т. 3. сортировка и поиск.Мир, 1977.17. Нечаев В. И. Элементы криптографии, основы теории защиты информации.Высшая школа, 1999.18.
Берж К. Теория графов и её применения. Изд. иностр. лит., 1962.19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.Мир, 1982.Список литературы36920. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка,визуализация и применение.
БХВ-Петербург, 2003.21. Кристофидес Н. Теория графов, алгоритмический подход. Мир, 1978.22. Сачков В. Н. Введение в комбинаторные методы дискретной математики.Наука, 1982.23. Ершов А. П. Введение в теоретическое программирование. Наука, 1977.24. Кон П. Универсальная алгебра. Мир, 1968.25. УилсонР. Введение в теорию графов. Мир, 1977.26. Лавров С. С. Гончарова Л. И.
Автоматическая обработка данных, хранениеинформации в памяти ЭВМ. Наука, 1971.27. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.МЦНМО, 1999.28. Харари Ф. Теория графов. Мир, 1973.29. Чень Ч., Ли Р. Математическая логика и автоматическое доказательствотеорем. Наука, 1983.30. Мендельсон Э. Введение в математическую логику. Наука, 1984.31. Фрид Э.
Элементарное введение в абстрактную алгебру. Мир, 1979.Предметный указательАвтоматическое доказательство теорем(automatic theorem proving), 171Автоморфизм (automorphism), 80Адекватность (adequacy), 150Азбука Морзе (Morse alphabet), 213Аксиома (axiom), 24выбора (of choice), 72логическая (logical axiom), 148регулярности (of regularity), 27собственная (proper axiom), 148формальной теории (of formal theory),147Аксиоматизируемость (axiomatizability),150, 169конечная (finite), 169Алгебра (algebra), 75Линдеибаума-Тарского(Lindenbaum-Tarsky), 117булева (boolean algebra), 99булевых функций (of booleanfunctions), 117высказываний (propositional algebra),146конечно-порожденная (finitelygenerated algebra), 77многоосновная (multi-based algebra), 76подмножеств (of subsets), 36, 76термов свободная (free algebra ofterms), 78универсальная (universal algebra), 75Алгоритм (algorithm)Дейкстры (Edsger Wybe Dijkstra), 286,288Краскала (Joseph Kruskal), 328Лемпела-Зива (Lempel-Ziv), 229Прима (Robert Clay Prim), 330Уоршалла (Stephen Warshall), 58Алгоритм (продолжение)Фано (Robert Mario Fano), 216Флойда (Robert W.
Floyd), 285Хаффмена (David Albert Huffman), 219восстановления упорядоченногоордерева по коду (ordered directedtree recovery), 306вставки узла в дерево сортировки(node insertion in sorting tree), 317выделения компонент сильнойсвязности (strong connectivitycomponent), 283вычисления СДНФ (evaluation ofperfect DNF), 136вычисления значения функции посокращённому дереву решений(evaluation of function on the base ofdecision tree), 138вычисления номера кортежа вустановленном порядке (evaluation oftuple's number in established order),134вычисления объединения слиянием(union by merge), 43вычисления пересечения слиянием(intersection by merge), 44вычитания итераторов (substraction ofiterators), 47генерации всех подмножеств(generation of all subsets), 39генерации перестановок (generation ofpermutations), 186 ,генерации подмножеств (generation ofsubsets), 192жадный (greedy), 75, 103интерпретации (interpretation), 112линейный (linear), 103371Предметный указательАлгоритм (продолжение)метода резолюций (resolution method),176нахождения максимального потока(maximal flow), 279неэффективный (inefficient), 349обхода бинарного дерева (binary treetraverse), 313объединения дизъюнктных итераторов(union of disjunctive iterators), 47определения расстояний от источника(distances from source), 290пересечения итераторов (intersection ofiterators), 46поиска (search)бинарного (binary), 315в глубину (depth first), 258в дереве сортировки (in sortingtree), 316в ширину (breadth first), 258с возвратами (backtracking), 349последовательного раскрашивания(sequential coloring), 359последовательного раскрашивания(улучшенный) (improved sequentialcoloring), 360построения СДНФ (construction ofperfect DNF), 135построения бинарного кода Грея(binary Gray's code), 40построения кода Прюфера (Priifer'scode), 303построения кода упорядоченногоордерева (ordered directed tree code),305построения кратчайшего остова(shortest spanning tree), 328построения максимальныхнезависимых множеств (maximalindependent sets), 352построения эйлерова цикла (Eulercycle), 341приближённый (approximate), 359проверки включения слиянием(checking inclusion by merge), 42проверки правильности скобочнойструктуры (checking parenthesisstructure accuracy), 309распаковки кода Прюфера (unpackingPriifer's code), 304Алгоритм (продолжение)слияния (merge), 42топологической сортировки(topological sorting), 69удаления узла из дерева сортировки(removal of node from sorting tree),319унификации (unification), 152эффективный (efficient), 349Алфавит (alphabet), 73формальной теории (of formal theory),147Аргумент (argument)функции (of function), 60Арифметика двоичная (binary arithmetic),90Ассоциативность (associativity)объединения (of union), 37пересечения (of intersection), 37ATOM (atom), 162ББазис (base), 112векторного пространства (of vectorspace), 94матроида (of matroid), 101пространства коциклов (of cocyclicspace), 339пространства циклов (of cycle space),339Биграф (bigraph), 250Биекция (bijection), 61Бином Ньютона (binomial theorem), 189Блок (block)графа (of graph), 266разбиения (of partition), 35, 195Брат узла (sibling node), 299Буква (letter), 73Булеан (boolean), 36Бэктрекинг (backtracking), 349ВВалентность вершины (vertex valence), 246Вектор (vector), 91циклический (cyclic vector), 336Векторное пространство (vector space), 91бесконечномерное(infinite-dimensional), 95конечномерное (finite-dimensional), 95Величина потока (value of flow), 277372Вершина (vertex)висячая (dangling), 247графа (of graph), 242достижимая (accessible), 261изолированная (isolated), 247концевая (leaf), 247покрывающая (covering), 345разделяющая (separate), 266связанная (connected), 249центральная (central), 250Вес дуги (weight of arc), 284Ветвь (branch)ордерева (of directed tree), 299Включение (inclusion)множеств (of sets), 28Вместимость отношения (arity of relation),52Вхождение (occurrence), 73определяющее (defining), 20переменной (variable)свободное (free), 162связанное (bound), 162Выводимость (inference), 148непосредственная (direct), 148Выполнимость (satisfiability)формулы (of formula), 149, 164Высказывание (proposition)простое (atomic), 143Высота дерева (height of tree), 299Вычет (residual), 234Вычитание (subtraction)матриц (of matrix), 56ГГамма шифра (cypher gamma), 232Геодезическая (geodesic line), 249Гиперграф (hypergraph), 244Гипердуга (hyperarc), 244Гипотеза (hypothesis), 148Гомоморфизм (homomorphism), 79Граница (bound)верхняя (upper), 70, 98наименьшая (least), 98нижняя (low), 70, 98наибольшая (greatest), 98Грань (bound)решётки (lattice)верхняя (upper), 97нижняя (low), 97Предметный указатель 372Грань графа (face of graph), 361Граф (graph), 242п-связный (n-connected), 268Герца (Herz), 282ациклический (acyclic), 248, 292вполне несвязный (totallydisconnected), 249гамильтонов (Hamilton), 343геодезический (geodesic), 249гомеоморфный (homeomorphic), 362двудольный (bipartite), 250древочисленпый (tree-numerical), 292нагруженный (weighted), 244несвязный (disconnected), 249нумерованный (numbered), 244, 342ориентированный (directed), 244пленарный (planar), 361плоский (flat), 361полный (complete), 250полный двудольный (completebipartite), 251полуэйлеров (semi-Euler), 340помеченный (labeled), 244регулярный (regular), 246с петлями (with loops), 244связный (connected), 249субциклический (subcyclic), 293тривиальный (trivial), 250чётный (even), 250эйлеров (Euler), 340График (graph)отношения (of relation), 50Группа (group), 85абелева (abelian), 86, 169альтернированная (alternating), 207делимая (divisible), 169знакопеременная (alternating), 207коммутативная (commutative), 86перестановок (of permutations), 87периодическая (periodic), 169порядка n (rc-order), 169симметрическая (symmetric), 87, 88ДДекодирование (decoding), 209Делитель пуля (zero divisor), 89левый (left), 89правый (right), 89373Предметный указательДерево (tree), 292m-ичное (m-ary), 303АВЛ-дерево (AVL-tree), 323бинарное (binary), 302полное (full), 323выровненное (aligned tree), 322двоичное (binary), 302заполненное (thick), 322корневое (rooted), 297ориентированное (directed), 297подровненное (balanced), 323прошитое (threaded), 312решений (decision), 138сбалансированное по весу (weightbalanced), 324сбалансированное по высоте (heightbalanced), 323свободное (free), 292семантическое (semantic), 138сортировки (sorting), 313, 315упорядоченное (ordered), 300упорядочивания (sorting), 313Дешифрация (decoding), 231Дешифрование (decoding), 231Диагональ (diagonal)прямого произведения (of directproduct), 51Диаграмма (diagram)Веппа (J°hn Venn), 34графа (of graph), 243коммутативная (commutative), 79решений (decision)бинарная (binary), 139Диаметр графа (graph diameter), 249Дивергенция (divergence), 276Дизъюнкция (disjunction)матриц (of matrix), 56Дистрибутивность (distributivity)объединения относительнопересечения (of union with respect tointersection), 37пересечения относительнообъединения (of intersection withrespect to union), 37Длина (length)дуги (of arc), 284маршрута (of route), 249набора (of tuple), 48Длина (продолжение)пути (of path), 284слова (of word), 73Добавление (adding)вершины (of vertex), 253ребра (of edge), 253Доля (part), 251Дополнение (complement), 97графа (of graph), 252множества (of set), 34Дуга (arc), 244насыщенная (saturated), 277EЕдииица (identity)моноида (of monoid), 84решётки (of lattice), 973Задача (problem)iVP-полиая (NP-complete), 344Рамсея (Frank Plumpton Ramsey), 263Штейнера (Jacob Steiner), 331комбинаторная (combinatorial), 180коммивояжёра (travelling salesman),344минимизации дизъюнктивной формы(minimum disjunctive form), 126о Кёнигсбергских мостах (Konigsbergbridges), 241о восьми ферзях (eight queens), 353о выборе переводчиков (translatorchoice), 355о наименьшем покрытии (leastcovering), 354о пяти ферзях (five queens), 353о развозке (transshipment), 355о свадьбах (marriage), 273о трёх домах и трёх колодцах (threehouses, three utilities), 241о четырёх красках (four color), 241переборная (search), 193Заключение правила вывода (conclusion ofinference rule), 148Законы де Моргана (de Morgan laws), 37Замена переменной (substitution), 84линейная (linear), 106374Замыкание (closure), 57, 128множества (of set), 77отношения (of relation), 57формулы (of formula), 164Запись (notation)инфиксная (infix), 51префиксная (prefix), 60Запись (record), 314Зашифровка (enciphering), 231Звезда (star), 347Значение (value)истинностное (truth value), 143функции (of function), 60ИИдемпотентность (idempotency)объединения (of union), 37пересечения (of intersection), 37Измельчение разбиения (refinement ofpartition), 195Изоморфизм (isomorphism), 80алгебр (of algebras), 80, 117вполне упорядоченных множеств (ofwell-ordered sets), 72графов (of graphs), 244линейно упорядоченных множеств (oflinear ordered sets), 71множеств (of sets), 29Инвариант (invariant)графа (of graph), 245массива (of array), 38Инверсия (inversion), 185матрицы (of matrix), 56Инволютивность (involutivity)дополнения (of complement), 37Индикатор (indicator), 28Интерпретация (interpretation)исчисления предикатов (of predicatecalculus), 163представления (of representation), 285формальной теории (of formal theory),149формулы (of formula), 144Инфимум (infimum), 70Инцидентность (incidence), 243Инъекция (injection), 61Источник (source), 252Предметный указатель 374Исчисление (calculus)высказываний (propositions calculus),150предикатов (predicates calculus), 161высшего порядка (higher order), 163первого порядка (first order), 161,163прикладное (applied), 163с равенством (with equality), 168чистое (pure), 161, 163Итератор (iterator), 46ККанал (channel)двоичный симметричный (binarysymmetric), 223связи (communication)с помехами (noisy), 221Каркас (skeleton), 327Карта (map), 241Квантор (quantifier)всеобщности (universal), 161существования (existential), 161Класс (class), 25замкнутый (closed), 128одноцветный (unicolored), 356полный (complete), 130эквивалентности (of equivalence), 65Клика (clique), 250Ключ (key)ассоциативной памяти(content-addressable), 314шифра (of encryption), 231Код (code)Прюфера (Prufer), 303Хэмминга (Hamming), 225множества (of set), 38сообщения (of message), 209элементарный (elementary), 210Кодерево (cotree), 335Кодирование (coding), 209m-ичное (m-ary), 209алфавитное (alphabetic), 210двоично-десятичное (binary codeddecimal), 210двоичное (binary), 209длина (length), 215однозначное (unique), 209оптимальное (optimal), 216375Предметный указательКодирование (продолжение)побуквепное (alphabetic), 210помехоустойчивое (antinoise), 222равномерное (uniform), 21Лс исправлением ошибок (errorcorrection), 222с минимальной избыточностью(optimal), 216самокорректирующееся(self-correcting), 222цепа (price), 215Кодовое слово (codeword), 210Коллизия (collision), 315Кольцо (ring), 88коммутативное (commutative), 88с единицей (with identity), 88целых чисел (of integer numbers), 76Коммутативность (commutativity)объединения (of union), 37пересечения (of intersection), 37Композиция (composition)отношений (of relations), 52подстановок (of substitutions), 84Компонента (component)связности (of connectivity), 249сильной связности (of strongconnectivity), 282Коидепсация орграфа (condensation ofdigraph), 282Конец цепи (circuit end), 248Константа (constant)предметная (object), 161Конструктивизм (constructivism), 27Контекст (context), 351Контроль чётности (parity check), 226Контур (contour), 248Конфигурация (configuration)комбинаторная (combinatorial), 180Конъюнкция (conjunction)допустимая (admissible), 127максимальная (maximal), 127Координаты (coordinates), 94Корень ордерева (root of directed tree), 297Кортеж (tuple), 48, 50, 51Коцикл (cocycle), 337Коэффициент (coefficient)биномиальный (binomial), 189мультиномиальный (multinomial), 194сжатия (of compression), 228Криптография (cryptography), 231Кринтостойкость (cryptostability), 231Крона ордерева (tree top), 299ЛЛес (forest), 292Линейная комбинация (linearcombination), 93Лист ордерева (leaf of directed tree), 299Литерал (literal), 162контрарный (contrary), 174Логическая связка (logical connective), 143MМаршрут (route), 247замкнутый (closed), 248открытый (open), 248Массив (array)дуг (of arcs), 257рёбер (of edges), 257Матрица (matrix)булева (boolean), 56инциденций (incidence), 256смежности (adjacency), 256Матроид (matroid), 100разбиений (of partitions), 105свободный (free), 105трапсверсалей (of transversals), 105Медиана (median)множества (of set), 216Метатеорема (metatheorem), 149Метод (method)аксиоматический (axiomatic), 24резолюций (of resolutions), 171, 172Метрика (metric), 224Множество (set), 23аксиом (of axiom)независимое (independent), 150бесконечное (infinite), 26, 31вершин (of vertex)внешне устойчивое (outer stable),353внутренне устойчивое (internallystable), 346доминирующее (dominating), 353независимое (independent), 346разделяющее (dividing), 270вполне упорядоченное (well-ordered),71376Множество (продолжение)зависимое (dependent), 100заданное (defined by)перечислением элементов(enumeration), 25порождающей процедурой(generating procedure), 25характеристическим предикатом(characteristic predicate), 25замкнутое (closed), 76конечное (finite), 26, 31линейно зависимое (linearlydependent), 93линейно независимое (linearlyindependent), 93линейно упорядоченное (linearlyordered), 68минимальное (minimal), 353наименьшее (least), 353независимое (independent), 100максимальное (maximal), 101несущее (support), 75образующих (of generators), 94пометок (of labels), 244порождающее (generating), 94пустое (empty), 24рёбер (of edges)независимое (independent), 274, 346разделяющее (separate), 270разрезов (of cuts)независимое (independent), 339смежности (adjacency), 243узлов (of nodes)доминирующее (dominating), 354независимое (independent), 354универсальное (universal), 25уровня (level), 67циклов (of cycles)независимое (independent), 339частично упорядоченное (partiallyordered), 68Модель (model), 76множества формул (of set of formulas),149, 164формальной теории (of formal theory),149Модуль (module), 95Моноид (monoid), 84Мономорфизм (monomorphism), 79Предметный указатель 376Мост (bridge), 266Мощность (power, cardinal number)множества (of set), 30, 34мультимножества (of multiset), 28Мультиграф (multigraph), 244Мультимножество (multiset), 28HНабор (tuple), 48Надмножество (superset), 29собственное (proper), 29Начало слова (prefix), 73собственное (proper), 73Неподвижная точка (fixed point), 207Непротиворечивость (consistency)семантическая (semantic), 149формальная (formal), 149Неравенство (inequality)МакМиллана (Kraft-MacMillan), 211треугольника (triangle), 287Носитель (support), 75интерпретации (of interpretation), 163мультимножества (of multiset), 28Нульгруппы (group identity), 86решётки (lattice identity), 97Нуль-вектор (nill vector), 91Нумерация множества (numbering of set),34ООбласть действия квантора (scope ofquantifier), 162Область значений (codomain, value range)отношения (of relation), 51функции (of function), 60Область интерпретации (interpretationdomain), 149Область определения (domain)отношения (of relation), 51функции (of function), 60Область отправления (source range)отношения (of relation), 50функции (of function), 60Область прибытия (target range)отношения (of relation), 50функции (of function), 60Область целостности (integral domain), 89Образ (image), 63Предметный указательОбфускация (obfuscation), 318Обход (traverse)дерева (of tree)внутренний (inorder), 312инфиксный (inorder), 312концевой (postorder), 312левый (preorder), 312постфиксный (postorder), 312правый (postorder), 312прямой (preorder), 302, 312симметричный (inorder), 312Объединение (union)графов (of graphs), 252множеств (of sets), 34Окончание слова (postfix), 73собственное (proper), 73Окрестность (neighborhood)вершины (of vertex), 243метрическая (metric), 224Оператор (statement)возврата (return), 64структурного перехода (structural goto), 47Операция (operation)п-арная (n-ary), 75ассоциативная (associative), 78внешняя (outermost), 112главная (principal), 112дистрибутивная (distributive), 78добавления элемента (of elementadding), 32идемпотентная (idempotent), 78коммутативная (commutative), 78конечноместиая (finitude), 76конкатенации (of concatenation), 73, 81первичная (primary), 45сцепления (of concatenation), 73удаления элемента (of elementremoval), 32Орграф (digraph), 244антисимметричный (antisymmetric),252направленный (directed), 252Ордерево (directed tree), 297Основа (base), 75, 76Остов (skeleton), 327кратчайший (shortest), 327Отец узла (node parent), 299377Отношение (relation)п-арное (n-ary), 51п-местное (n-ary), 51антирефлексивное (antireflexive), 53антисимметричное (antisymmetric), 53бинарное (binary), 50дополнительное (complement), 51линейное (linear), 53обратное (converse), 51однозначное (single-value), 59полное (complete), 54порядка (order), 67алфавитного (alphabetical), 74антилексикографического(antilexicographical), 186лексикографического(lexicographical), 74, 186линейного (linear), 67нестрогого (non-strict), 67строгого (strict), 67частичного (partial), 68равномощности (of equivalence), 30рефлексивное (reflexive), 53симметричное (symmentic), 53сравнимости чисел (congruence), 234тождественное (identical), 51транзитивное (transitive), 53универсальное (universal), 51функциональное (functional), 59частичное (partial), 54эквивалентности (of equivalence), 64ППамять ассоциативная(content-addressable memory), 314Парадокс (paradox)Рассела (Bertrand Russell), 27Паросочетание (matching), 274, 346совершенное (perfect), 274Переменная (variable)несущественная (inessential), 109предметная (object), 161пропозициональная (propositional),143, 150связанная (bounded), 162существенная (essential), 109фиктивная (inessential), 109Пересечение (intersection)множеств (of sets), 34378Перестановка (permutation), 87обратная (inverse), 87тождественная (identity), 87Петля (loop), 244Побочный эффект (side-effect), 113Поглощение (absorbancy), 37, 78Подалгебра (subalgebra), 76Подграф (subgraph), 246изграф, 246остовный (spanning), 246, 327правильный (regular), 246собственный (proper), 246Поддерево (subtree), 298Подмножество (subset), 29собственное (proper), 29Подстановка (substitution), 84, 87Подформула (subformula), 112Поиск (search)бинарный (binary), 315в глубину (depth first), 258в ширину (breadth first), 258двоичный (binary), 315полнотекстовый (full text), 229Показатель (index)элемента (of element), 28Покрытие (covering), 35вершинное (vertex), 345рёберное (edge), 346Поле (field), 90веществествениых чисел (of realnumbers), 76рациональных чисел (of rationalnumbers), 76Полином (polynomial)Жегалкина, 131Полнота (completeness)системы булевых функций (of booleanfunctions set), 130формальной теории (of formal theory),150Полный перебор (exhaustive search), 344Полугруппа (semigroup), 81свободная (free), 82циклическая (cyclic), 81Полуразрешимость (semisolveability)формальной теории (of formal theory),150Полустепепьзахода (in-degree), 247исхода (out-degree), 247Предметный указатель 378Польская запись (polish notation), 311обратная (reverse), 312Помехоустойчивость (noise-immunity), 209Порядок (order)группы (of group), 85установленный (established), 108Последовательность (sequence)конечная (finite), 48Постфикс (postfix), 73Посылка правила вывода (hypothesis ofrule), 148Поток (flow), 277Потомок узла (descendant node), 299Правило (rule)введения (introduction)импликации (of implication), 154вывода (inference)производное (derived), 154формальной теории (of formaltheory), 147двойного вращения (double rotation),326замены (of replacement), 115отделения (of detachment), 151подстановки (of substitution), 115произведения (of product), 181простого вращения (single rotation),325резолюции (resolution), 174сечения (cut), 156склеивания/расщепления(clutching/splitting), 123суммы (of sum), 181транзитивности (of transitivity), 156Предикат (predicate), 161п-арный (n-ary), 161п-местный (n-ary), 161характеристический (characteristic), 25Предложение (clause), 173резольвируемое (resolvable), 174родительское (parent), 174Предок узла (descendant node), 299Преобразование (transformation), 60эквивалентное (equivalent), 123Префикс (prefix), 73Приведение подобных (collecting terms),124Принцип (principle)двойственности (of duality), 119индукции (of induction), 72379Предметный указательПроблема (problem)алгоритхмически неразрешимая(algorithmically unsolvable), 83Продолжение (extension)функции (of function), 60Произведение (product)декартово (Cartesian), 49перестановок (of permutations), 87прямое (direct), 49Прообраз (preimage), 63Пропускная способность (capacity)дуги (of arc), 276разреза (of cut), 277Пространство (space)векторное (vector), 91поиска (search), 193Протаскивание (dragging)отрицаний (of negations), 123, 173Противоречие (contradiction), 144Псевдограф (pseudograph), 244Путь (path), 248кратчайший (shortest), 284Равенство (equality)множеств (of sets), 29упорядоченных пар (of orderedcouples), 48Радиус (radius)графа (of graph), 249Разбиение (separation), 35Разделение (splitting)связанных переменных (of boundedvariables), 173Размерность (dimension)векторного пространства (of vectorspace), 95Размножение вершины (duplication ofvertex), 253Разность (difference)множеств (of sets), 34симметрическая (symmetric), 34Разрез (cut), 270, 334правильный (regular), 334простой (simple), 335фундаментальный (fundamental), 337Разрешимость (solveability)класса формул (formulas class), 122формальной теории (of formal theory),150Разряд (bit)информационный (information), 226контрольный (check), 226Ранг (rank)конъюнкции (of conjunction), 125коциклический (cocyclomatic), 337циклический (cyclomatic), 335Раскраска графа (coloring of graph), 356Раскрытие скобок (removal of brackets),123Расстояние (distance), 224, 249Хэмминга (Hamming), 224кодовое (code), 225Расшифровка (deciphering), 231Расшифровывание (deciphering), 231Расщепление (splitting), 123переменных (variables), 124Ребро (edge)графа (of graph), 242кратное (multiple), 244покрывающее (covering), 345Резольвента (resolvent), 174Решётка (lattice), 96дистрибутивная (distributive), 96ограниченная (bounded), 97с дополнением (complement), 97Родитель узла (parent node), 299Связанность (connectivity)узлов (of nodes)односторонняя (one-way), 282сильная (strong), 282слабая (weak), 282Связка (connective)логическая (logical), 150Связность (connectivity)вершинная (vertex), 267односторонняя (one-way), 282рёберная (edge), 268сильная (strong), 282слабая (weak), 282Семейство (family)дизъюнктное (disjunct), 35множеств (of sets), 25Сеть (network), 252Сжатие (compression), 228адаптивное (adaptive), 229380Сигнатура (signature), 76формальной теории (of formal theory),148Символ (symbol), 73Система (system)образующих (generator set), 77различных представителей (of differentrepresentatives), 273разрезов (of cuts)фундаментальная (fundamental),337циклов (of cycles)фундаментальная (fundamental),335Система счисления (number system)позиционная (positional)десятичная (decimal), 208Скаляр (scalar), 91, 96Склеивание (clutching), 123Сколемизация (skolemising), 173Следствие (consequence)логическое (logical), 145, 149, 166Словарь (dictionary), 228Слово (word), 73, 228машинное (machine), 38пустое (empty), 73Сложность (complexity)временная (time), 180емкостная (space), 180по времени (time), 180по памяти (space), 180Смежность (adjacency)вершин (vertex), 243рёбер (edge), 243Смешанные вычисления (mixedcomputations), 113Соединение (join)графов (of graphs), 252Сообщение (message), 209шифрованное (coded), 231Соответствие (correspondence)взаимно-однозначное (one-to-one), 29Соотношение (relationship)определяющее (defining), 82Сортировка (sorting), 185пузырька (bubble), 185формулы (formula), 124Состав (compound)мультимножества (of multiset), 28последовательности (of sequence), 193Предметный указатель 380Список (list)смежности (adjacency), 257Сравнение (comparison)по модулю (modulo), 233Степень (degree)вершины (of vertex), 246максимальная (maximal), 246минимальная (minimal), 246множества (of set), 50отношения (of relation), 53Сток (sink), 252Стратегия (strategy)метода резолюций (of resolutionmethod), 177неполная (incomplete), 177полная (complete), 177Структура (structure)алгебраическая (algebraic), 75Стягивание (shrinkage)подграфа (of subgraph), 253Сужение (restriction)функции (of function), 60Суперпозиция (superposition), 63Супремум (supremum), 70Схема (scheme)аксиомы (of axiom), 148, 151кодирования (coding), 210правила вывода (of inference rule), 151префиксная (prefix), 211разделимая (separable), 210Схема Горнера (Horner's method), 134Сын узла (child node), 299Сюръекция (surjection), 61TТаблица (table)истинности (of truth values), 107кодов (of codes), 210расстановки (hash), 315хэш (hash), 315Тавтология (tautology), 144, 149Тайнопись (cryptogram), 231Теорема (theorem)Гёделя (Kurt Friedrich Godel), 170, 171Куратовского (Kazimierz Kuratowski),362Маркова-Поста (Markov-Post), 83Менгера (Karl Menger), 271Поста (Emil Leon Post), 131Предметный указательТеорема (продолжение)Форда-Фалкерсона (Ford-Fulkerson),278Холла (Philip Hall), 274формальной теории (of formal theory),148Теория (theory)групп (group), 168полуразрешимая (semisolvable), 176равенства (of equality), 167формальная (formal), 147формальной арифметики (formalarithmetic), 168Терм (term), 78, 162свободный для переменной в формуле(free for variable in formula), 163Тип (type), 76Точка Штейнера (Steiner point), 331Точка сочленения (articulation point), 266Трансверсаль (transversal), 273частичная (partial), 105Транспозиция (transposition), 185Транспонирование (transposition)матрицы (of matrix), 56 *Треугольник Паскаля (Blaise Paskal), 191Турнир (tournament), 252УУдаление (removal)вершины (of vertex), 253пулей (of zeros), 123ребра (of edge), 253Узел (node), 244Укладка графа (graph flattering), 361Умножение (multiplication)вектора на скаляр (of vector on scalar),91матриц (of matrix), 56Универсум (universe), 25, 27Унификатор (unifier), 151наиболее общий (most common), 151общий (common), 151Упаковка (packing), 228Упорядоченная пара (ordered couple), 48Уровень узла (level of node), 299ФФактор-граф (quotient graph), 282Факториал (factorial)двойной (double), 188381Фактормножество (factor set), 66Форма (form)дизъюнктивная (disjunctive), 123, 125нормальная (normal), 122нормальная сокращённая (norrrtalreduced)дизъюнктивная (disjunctive), 127совершенная нормальная (perfectnormal)дизъюнктивная (disjunctive), 121конъюнктивная (conjunctive), 122Формализуемость (formalizability), 150Формула (formula), 111Коши (Augustin Louis Cauchy), 191Кэли (Arthur Cayley), 332Стирлинга (James Stirling), 184Эйлера (Leonard Euler), 362атомарная (atomic), 162бескванторная (quantifier-free), 167в предварённой форме (prenex form),167включений и исключений(inclusion-exclusion), 198выполнимая (satisfiable), 144замкнутая (closed), 162истинная (true), 164ложная (false), 164невыполнимая (unsatisfiable), 144общезначимая (valid), 144, 149, 164открытая (open), 164пропозициональная (propositional), 144противоречивая (contradictory), 149пустая (empty), 172равносильная (equivalent), 114унифицируемая (unificated), 151формальной теории (of formal theory),147Функциональный символ (functionalsymbol), 161п-арный (n-ary), 161п-местный (n-ary), 161Функция (function), 59n аргументов (n arguments), 60п-местная (n-ary), 60Эйлера (Euler), 234алгебры логики (of boolean algebra),107биективная (bijective), 61булева (boolean), 107весовая (weight), 102382Функция (продолжение)взаимно-однозначная (one-to-one), 61двойственная (dual), 118инъективная (injective), 61монотонная (monotone), 70монотонно возрастающая (monotoneincreasing), 70монотонно убывающая (monotonedecreasing), 70обратная (inverse), 62отождествления (identification), 66перехода к образам (image function), 63перехода к прообразам (preimagefunction), 63производящая (course-of-value), 203самодвойственная (self-daul), 118строго монотонная (strict monotone),70строго монотонно возрастающая (strictmonotone increasing), 70строго монотонно убывающая (strictmonotone decreasing), 70сюръектишгая (surjective), 61тотальная (total), 60характеристическая (characteristic), 60,61хэш (hash), 315частичная (partial), 60Характеристика (characteristic)канала (channel), 222Хорда (chord), 335Центр (center)графа (of graph), 250Цепочка (chain)множеств (of sets), 182полная (complete), 182Цепочка (string), 73Цепь (circuit), 248аугментальная (augmenting), 278вершинно-непересекающаяся (pairwisevertex-independent), 270простая (simple), 248рёберно-непересекающаяся (pairwiseedge-independent ), 270эйлерова (euler), 340Предметный указатель 382Цикл (cycle), 185, 248гамильтоиов (hamilton), 343простой (simple), 248, 333фундаментальный (fundamental), 335эйлеров (euler), 340Цифровая подпись (digital signature), 237Цифры (numerals)римские (roman), 2084Частный случай (instance)набора формул (set of formulas), 152наборов формул (set of formulas)совместный (shared), 152совместный (shared), 151формулы (formula), 151Часть графа (section of graph), 246Число (number)Белла (Eric Temple Bell), 197Каталина (Catalan), 205Стирлинга т о р о ю рода (Stirlingsecond kind), 196Стирлинга первого рода (Stirling first.kind), 197Фибоначчи (Fibonacci), 204вершинного покрытия (of vertexcovering), 345вершинное независимости (of vertexindependence), 346вещественное (real), 24взаимно простое (mutually prime), 234инверсий (of inversions), 185коцикломатическое (cocyclomatic), 337натуральное (natural), 24, 77перестановок (of permutations), 182простое (prime), 24псевдослучайное (pseudorandom), 232рёберного покрытия (of edge covering),346рёберное независимости (of edgeindependence), 346размещений (of menage), 180размещений без повторений (of simplemenage), 181сочетаний (of combination), 182сочетаний с повторениями (of completecombination), 183хроматическое (chromatic), 356цикломатическое (cyclomatic), 335чётное (even), 80383Предметный указательШШар (ball), 224Ширина ветвления (width of branching),332Шифр (cipher), 231надёжный (robust), 231раскрытие (decoding), 231с открытым ключом (public key), 235симметричный (symmetric), 232Шифрование (enciphering), 231Шифровка (coded message), 231Шкала (scale)битовая (bit), 38эЭйлерова характеристика (Eulercharacteristic), 362Эквивалентность (equivalence)логическая (logical), 145, 166Экземпляр (instance)класса (of class), 254Эксцентриситет (eccentricity)вершины (of vertex), 249Электронная подпись (digital signature),237Элемент (element)минимальный (minimal), 68множества (of set), 23Элемент (продолжение)нейтральный (neutral), 84, 86аддитивный (additive), 91мультипликативный(multiplicative), 91обратный (inverse), 85Элиминация (elimination)импликации (of implication), 173квантора всеобщности (of universalquantifier), 173квантора существования (of existentialquantifier), 173конъюнкции (of conjunction), 173операции (of operation), 123Эндоморфизм (endomorphism), 80Эпиморфизм (epimorphism), 79ЯЯдро (kernel)графа (of graph).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
