Страница: 15/26
У некоторых графов есть гамильтонов цикл – это способ соединения всех вершин графа одной кривой, проходящий по его ребрам и не проходящий через одну вершину дважды. Допустим, проверяющему показали гамильтонов цикл графа, но он не знает от какой точки к какой идти, если проверяющий убедился в том, что у проверяемого нужный граф, то он не видит гамильтонов цикл, так как у графа изменились координаты точек.
Каждый вопрос будет понижать шансы на случайный ответ. Сначала, вероятность угадать, равна 1/2, потом 1/4 и через сто вопросов вероятность упадет до 1/2100. Если человек не знает правильного графа и гамильтонова цикла, то ему будет практически невозможно ответить на все вопросы ни разу не ошибавшись, а проверка заканчивается при первой же ошибке.
Как происходит проверка? Допустим, некоторый компьютер (А) устанавливает подлинность представления удалённого компьютера (Б). У компьютера Б есть граф, для которого ему известен гамильтонов цикл.
Сначала компьютер Б посылает граф, который получился из проверочного случайным переименованием вершин. Компьютер А случайным образом выбирает, какую информацию он хочет проверить, совпадение этого графа с тем, что у него есть, или известность компьютеру Б гамильтонова цикла для этого графа. Предположим, что компьютер б хочет убедиться в совпадении этого графа с тем, что есть у него и посылает об этом сообщение компьютеру Б, компьютер Б в свою очередь посылает компьютеру А информацию о том, каким образом надо переименовать вершины графа, чтобы получился исходный. Если подобное преобразование действительно переведет граф в исходный, то компьютер А считает, что на этот вопрос он получил правильный ответ и продолжает проверку.
Далее компьютер Б снова посылает граф, на этот раз, переименовав вершины по-другому (случайным образом). Пусть в этот раз компьютер А выбрал, что хочет узнать гамильтонов цикл, тогда компьютер Б посылает последовательность имен вершин, которая в измененном графе действительно является гамильтоновым циклом. Таким образом, после некоторого числа подобных шагов, компьютер А убеждается, что компьютер Б действительно тот, за которого себя выдаёт, отметим, что при этом компьютер А не сможет сам представится компьютером Б, ведь он так и не узнал гамильтонова цикла для исходного графа, а гамильтонов цикл найти для граф с десятью вершинами уже не просто, а если у графа 100 вершин то это уже почти невозможно. А если вершин 1000, то подбор гамильтонова цикла на современном компьютере займет несколько сотен лет.
Как же генерируются проверочные графы? Пусть в начале есть граф на 1000 вершин, где n-ая вершина соединена с n+1, а 1000 с 1, теперь случайным образом переименуем вершины, и запомним теперь для этого графа гамильтонов цикл далее для каждой пары вершин с вероятностью 34% будем соединять ребром, в конце данной процедуры получим граф, для которого мы знаем цикл и в то же время, найти его кем-то другим не представляется возможным.
Чтобы показать вам всю сложность нахождения гамильтонова цикла рассмотрим граф из семи точек, приведенный на рисунке ниже. Если попытаться самому придумать гамильтонов цикл, то на это уйдет от 30 минут до нескольких часов.
Рис. 11 Гамильтонов цикл
На рисунке показан граф с 7 вершинами; сплошные линии - гамильтонов цикл для данного графа пунктир ребра, по которым не прошла кривая гамильтонова цикла. При возможной реализации проекта, можно будет написать подобное программное обеспечение.
6. Расчет затрат и экономической эффективности планируемой сети.
Расчет доходной части на календарный год.
Приток денежных средств на реализацию проекта –это банковский кредит 25000$ под 12% годовых на 3 года.
Таблица 6.1
|
|
50 |
|
Сумма ежемесячных выплат клиента |
33$ |
|
Сумма годовых выплат одного клиента |
396$ |
|
Сумма годовых выплат всех клиентов |
19800$ |
Следует понимать, что приведенные расчеты весьма приблизительны. Например, очень сложно предугадать, средние ежемесячные выплаты клиента.
Расходы по организации проекта
Расходы по организации и реализации программы доступа в интернет по сетям КТВ складываются из следующих крупных блоков:
- В ыплата процента по кредиту и самого кредита;
- Помесячная плата внешнему провайдеру;
- Приобретение оборудования;
Реферат опубликован: 13/07/2006