4511
правок
Приближенные словари: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
• Рандомизированные схемы с двусторонней ошибкой, которым разрешено ошибаться как в положительных, так и в отрицательных случаях (то есть эти схемы могут с малой вероятностью сказать «Нет», когда запрашиваемый элемент u содержится в множестве S, и «Да», когда это не так); | • Рандомизированные схемы с двусторонней ошибкой, которым разрешено ошибаться как в положительных, так и в отрицательных случаях (то есть эти схемы могут с малой вероятностью сказать «Нет», когда запрашиваемый элемент u содержится в множестве S, и «Да», когда это не так); | ||
• Рандомизированные схемы с односторонней ошибкой, в которых ошибки ограничены только отрицательными случаями (то есть эти схемы никогда не дают ответа «Нет», когда | • Рандомизированные схемы с односторонней ошибкой, в которых ошибки ограничены только отрицательными случаями (то есть эти схемы никогда не дают ответа «Нет», когда запрашиваемый элемент u содержится в множестве S); | ||
• Детерминированные схемы, в которых ошибки не допускаются. Основные приемы, используемые в [ ], основаны на двухцветных раскрасках систем специальных множеств, связанных с «r-cover-free семейством множеств» ''//семейство множеств, в котором ни одно из множеств не содержится в объединении r (или меньше) других множеств из этого же семейства//'', рассмотренным в [3,5,9]. Более подробную информацию можно найти в работе [2]. | • Детерминированные схемы, в которых ошибки не допускаются. Основные приемы, используемые в работе [2], основаны на двухцветных раскрасках систем специальных множеств, связанных с «r-cover-free семейством множеств» ''//семейство множеств, в котором ни одно из множеств не содержится в объединении r (или меньше) других множеств из этого же семейства//'', рассмотренным в [3,5,9]. Более подробную информацию можно найти в работе [2]. | ||
