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

Даже если вам удастся ежедневно изменять шифр, подобные простые шифры достаточно легко взламываются методом грубой силы. Допустим, я вижу сообщение «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. Какое максимальное количество голосов вы сможете получить (Сан-Франциско+Чикаго)?

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

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

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

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