Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 55

Шрифт
Интервал

стр.

= 1, b = 2 и т.д. Если после этого я отправлю вам сообщение «4,15,7», вы сможете преобразовать его в «d,o,g». Но чтобы эта схема сработала, необходимо согласовать шифр между сторонами. Договориться о шифре по электронной почте невозможно, потому что злоумышленник может перехватить сообщение, узнать шифр и расшифровать сообщения. Даже если передать шифр при личной встрече, злоумышленник может угадать шифр, если он достаточно прост. Значит, шифр придется ежедневно менять. Но тогда нам придется ежедневно проводить личные встречи для изменения шифра!

Даже если вам удастся ежедневно изменять шифр, подобные простые шифры достаточно легко взламываются методом грубой силы. Допустим, я вижу сообщение «9,6,13,13,16 24,16,19,13,5». Я предполагаю, что при шифровании используется подстановка a = 1, b = 2 и т.д.

Бессмыслица. Пробуем a = 2, b = 3 и т.д.

Сработало! Подобные простые шифры взламываются достаточно легко. Во Вторую мировую войну в Германии использовался намного более сложный шифр, но и он был взломан.

Алгоритм Диффи—Хеллмана решает обе проблемы:

• знание шифра обеими сторонами не обязательно. Следовательно, им не придется встречаться и согласовывать шифр;

• расшифровать зашифрованные сообщения чрезвычайно сложно.

Алгоритм Диффи—Хеллмана использует два ключа: открытый и закрытый. Открытый ключ известен обеим сторонам. Его можно опубликовать на сайте, отправить электронной почтой друзьям и вообще сделать с ним все, что вам заблагорассудится. Его не нужно скрывать. Когда другая сторона захочет отправить вам сообщение, она зашифрует его с применением открытого ключа. Зашифрованное сообщение можно расшифровать только с закрытым ключом. При условии, что вы являетесь единственным владельцем закрытого ключа, никто другой расшифровать сообщение не сможет!

Алгоритм Диффи—Хеллмана продолжает применяться на практике вместе с его наследником RSA. Если вы интересуетесь криптографией, алгоритм Диффи—Хеллмана станет хорошей отправной точкой: он элегантен и не особо сложен.


Линейное программирование

Самое лучшее я приберег напоследок. Линейное программирование — одна из самых интересных областей, которые мне известны.

Линейное программирование используется для максимизации некоторой характеристики при заданных ограничениях. Предположим, ваша компания выпускает два продукта: рубашки и сумки. На рубашку требуется 1 м ткани и 5 пуговиц. На изготовление сумки необходимо 2 м ткани и 2 пуговицы. У вас есть 11 м ткани и 20 пуговиц. Рубашка приносит прибыль $2, а сумка — $3. Сколько рубашек и сумок следует изготовить для получения максимальной прибыли?

Здесь мы пытаемся максимизировать прибыль, а ограничения определяют количество имеющихся материалов.

Другой пример: вы политик, пытающийся получить максимальное количество голосов. Исследования показали, что на каждый голос жителя Сан-Франциско требуется примерно час работы (маркетинг, исследования и т.д.), а на каждый голос жителя Чикаго — 1,5 часа. Вам нужны голоса как минимум 500 жителей Сан-Франциско и как минимум 300 жителей Чикаго. В вашем распоряжении 50 дней. Кроме того, затраты на жителя Сан-Франциско составляют $2, а на жителя Чикаго — $1. Ваш бюджет составляет $1500. Какое максимальное количество голосов вы сможете получить (Сан-Франциско+Чикаго)?

На этот раз вы стремитесь к максимуму голосов при ограничениях по времени и деньгам.

Возможно, вы думаете: «В этой книге много говорилось о вопросах оптимизации. Как они связаны с линейным программированием?» Все алгоритмы, работающие с графами, могут быть реализованы средствами линейного программирования. Линейное программирование — намного более общая область, а задачи с графами составляют ее подмножество.

В линейном программировании используется симплекс-метод. Этот алгоритм достаточно сложен, поэтому я не привожу его в книге. Если вы интересуетесь задачами оптимизации, поищите информацию о линейном программировании!


Эпилог

Надеюсь, этот краткий обзор показал, как много вам еще предстоит узнать. Я считаю, что лучший способ узнать что-то — найти тему, которая вас интересует, и изучить ее. Надеюсь, эта книга закладывает достаточно надежную основу для этого.


стр.

Похожие книги