Как обеспечить избыточную целостность? Пытаемся с коллегами найти решение логической задачи, уже, если честно, нет уверенности что оно есть.
Итак задача:
Есть 1000 заключенных, и есть числа от 1 до 1000, которым присвоено собственное значение. Например:1 = 0f88Hs
2 = UdD16j
3 = NkP4V4
4 = bRKitt
5 = 3rLqBA
6 = 5gH6LE
7 = 0wrICY
8 = 58CEoM
9 = 1oCn43
...
1000 = Id2401
Каждый заключенный знает свою пару [ число = значение ] и пару предыдущего, как минимум. Но еще он может запомнить N-ное количество случайных пар (или не случайных, по договоренности).
Утром придут надзиратели и уведут заключенных - случайное количество (до 75%, то есть может остаться 250 человек, а может и 500) случайных заключенных. Например, на расстрел. Количество и порядок неизвестен.
Итак, вопрос: каково минимальное количество пар и по какому алгоритму должен запомнить каждый заключенный для гарантированного восстановления последовательности значений? Как изменится этот алгоритм если уведут 90% заключенных или только 25%? Как равномерно перераспределить нагрузку если к имеющейся 1000 добавят еще 1000, а чисел останется столько же, просто два заключенных будут помнить одно и то же число?
Как обеспечить избыточную целостность? Пытаемся с коллегами найти решение логической задачи, уже, если честно, нет уверенности что оно есть.
Итак задача:
Есть 1000 заключенных, и есть числа от 1 до 1000, которым присвоено собственное значение. Например:1 = 0f88Hs
2 = UdD16j
3 = NkP4V4
4 = bRKitt
5 = 3rLqBA
6 = 5gH6LE
7 = 0wrICY
8 = 58CEoM
9 = 1oCn43
...
1000 = Id2401
Каждый заключенный знает свою пару [ число = значение ] и пару предыдущего, как минимум. Но еще он может запомнить N-ное количество случайных пар (или не случайных, по договоренности).
Утром придут надзиратели и уведут заключенных - случайное количество (до 75%, то есть может остаться 250 человек, а может и 500) случайных заключенных. Например, на расстрел. Количество и порядок неизвестен.
Итак, вопрос: каково минимальное количество пар и по какому алгоритму должен запомнить каждый заключенный для гарантированного восстановления последовательности значений? Как изменится этот алгоритм если уведут 90% заключенных или только 25%? Как равномерно перераспределить нагрузку если к имеющейся 1000 добавят еще 1000, а чисел останется столько же, просто два заключенных будут помнить одно и то же число?
Итак задача:
Есть 1000 заключенных, и есть числа от 1 до 1000, которым присвоено собственное значение. Например:1 = 0f88Hs
2 = UdD16j
3 = NkP4V4
4 = bRKitt
5 = 3rLqBA
6 = 5gH6LE
7 = 0wrICY
8 = 58CEoM
9 = 1oCn43
...
1000 = Id2401
Каждый заключенный знает свою пару [ число = значение ] и пару предыдущего, как минимум. Но еще он может запомнить N-ное количество случайных пар (или не случайных, по договоренности).
Утром придут надзиратели и уведут заключенных - случайное количество (до 75%, то есть может остаться 250 человек, а может и 500) случайных заключенных. Например, на расстрел. Количество и порядок неизвестен.
Итак, вопрос: каково минимальное количество пар и по какому алгоритму должен запомнить каждый заключенный для гарантированного восстановления последовательности значений? Как изменится этот алгоритм если уведут 90% заключенных или только 25%? Как равномерно перераспределить нагрузку если к имеющейся 1000 добавят еще 1000, а чисел останется столько же, просто два заключенных будут помнить одно и то же число?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для обеспечения избыточной целостности в данной ситуации можно использовать метод шифрования и распределения информации между заключенными.
Минимальное количество пар, которое должен запомнить каждый заключенный, чтобы гарантированно восстановить последовательность значений, будет зависеть от количества удаваемых заключенных и процента удаления. Оптимально запомнить каждому заключенному значения нескольких индексов в последовательности (например, каждый 10-й или каждый 100-й).
Если уводятся 90% заключенных, то необходимо увеличить количество запоминаемых значений на каждого оставшегося заключенного. Алгоритм остается таким же, но объем информации для запоминания увеличивается.
Если уводятся всего 25% заключенных, то можно уменьшить количество запоминаемых значений на каждого заключенного.
Для равномерного распределения нагрузки при добавлении еще 1000 заключенных, можно использовать более сложные алгоритмы, где каждый заключенный запоминает информацию не только о своем числе, но и о числах других заключенных. Таким образом, информация будет распределена между всеми участниками более равномерно.
Для более точного расчета оптимального количества значений, которые должен запомнить каждый заключенный, можно использовать математическое моделирование и анализ вероятностей.