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

b	i
HELLO	VI	0	R		L		D

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

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

Алгоритм Диффи—Хеллмана использует два ключа: открытый и закры­тый. Открытый ключ известен обеим сторонам. Его можно опубликовать на сайте, отправить электронной почтой друзьям и вообще сделать с ним все, что вам заблагорассудится. Его не нужно скрывать. Когда другая сторона захочет отправить вам сообщение, она зашифрует его с примене­нием открытого ключа. Зашифрованное сообщение можно расшифровать только с закрытым ключом. При условии, что вы являетесь единственным владельцем закрытого ключа, никто другой расшифровать сообщение не сможет!
Алгоритм Диффи—Хеллмана продолжает применяться на практике вместе с его наследником RSA. Если вы интересуетесь криптографией, алгоритм Диффи—Хеллмана станет хорошей отправной точкой: он элегантен и не особо сложен.
Линейное программирование
Самое лучшее я приберег напоследок. Линейное программирование — одна из самых интересных областей, которые мне известны.
Линейное программирование используется для максимизации некоторой характеристики при заданных ограничениях. Предположим, ваша компа­ния выпускает два продукта: рубашки и сумки. На рубашку требуется 1 м ткани и 5 пуговиц. На изготовление сумки необходимо 2 м ткани и 2 пуго­вицы. У вас есть 11м ткани и 20 пуговиц. Рубашка приносит прибыль $2, а сумка — $3. Сколько рубашек и сумок следует изготовить для получения максимальной прибыли?
Здесь мы пытаемся максимизировать прибыль, а ограничения определяют количество имеющихся материалов.
Другой пример: вы политик, пытающийся получить максимальное ко­личество голосов. Исследования показали, что на каждый голос жителя Сан-Франциско требуется примерно час работы (маркетинг, исследования и т. д.), а на каждый голос жителя Чикаго — 1,5 часа. Вам нужны голоса как минимум 500 жителей Сан-Франциско и как минимум 300 жителей Чикаго. В вашем распоряжении 50 дней. Кроме того, затраты на жителя Сан-Франциско составляют $2, а на жителя Чикаго — $1. Ваш бюджет составляет $1500. Какое максимальное количество голосов вы сможете получить (Сан-Франциско+Чикаго)?
На этот раз вы стремитесь к максимуму голосов при ограничениях по вре­мени и деньгам.
Возможно, вы думаете: «В этой книге много говорилось о вопросах оптими­зации. Как они связаны с линейным программированием?» Все алгоритмы, работающие с графами, могут быть реализованы средствами линейного программирования. Линейное программирование — намного более общая область, а задачи с графами составляют ее подмножество.
В линейном программировании используется симплекс-метод. Этот ал­горитм достаточно сложен, поэтому я не привожу его в книге. Если вы интересуетесь задачами оптимизации, поищите информацию о линейном программировании!
Эпилог
Надеюсь, этот краткий обзор показал, как много вам еще предстоит узнать. Я считаю, что лучший способ узнать что-то — найти тему, которая вас инте­ресует, и изучить ее. Надеюсь, эта книга закладывает достаточно надежную основу для этого.
Ответы к упражнениям

Глава 1

1. 
   Имеется отсортированный список из 128 имен, и вы ищете в нем зна­чение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
   

Ответ'. 7

2. 
   Предположим, размер списка увеличился вдвое. Как изменится мак­симальное количество проверок?
   

Ответ: 8

3. 
   Известна фамилия, нужно найти номер в телефонной книге.