42.Навести метод розгалужень і меж
Обхід усіх вузлів дерева пошуку варіантів може виявитися надто довгим. Наприклад, якщо в дереві всі вузли є допустимими, кожний проміжний вузол має m синів, а глибина дерева n, то всього в дереві 1+m+m2+ … +mn=(mn+1-1)/(m-1) вузлів. Уже за m=10 та n=10 це більш, ніж 1010. Якщо припустити, що комп'ютер здатний обробити 105 вузлів за секунду, то обхід такого дерева триватиме 105 секунд, або приблизно добу.
Існує багато практичних задач, де вимагається відшукати чи побудувати не всі можливі варіанти, а лише один із них, найкращий у деякому розумінні, визначеному в задачі. Отже, тут з'являється таке поняття, як цінність варіантів. Загальним принципом розв'язання таких задач є скорочення обходу дерева варіантів. У ньому відкидаються деякі гілки, про які можна стверджувати, що вони не містять варіантів більш цінних, ніж уже знайдені. Розглянемо приклад.
Приклад. Нехай є 6 завдань, час виконання яких відповідно 7, 8, 9, 10, 11, 12. Якщо в зазначеному порядку розподілити перші три завдання між процесорами, а потім давати їх у тому ж порядку процесорам, що звільняються, то перший процесор закінчить роботу в момент 7+10=17, другий – у момент 8+11=19, а третій – 9+12=21. Маємо вартість 21. Проте їх можна розподілити інакше – 7+12, 8+11, 9+10, одержавши вартість 19.ç
Перше, що ми зробимо в розв'язанні задачі – упорядкуємо завдання за незростанням часу їх виконання. Отже, нехай P1, … , Pn – завдання, часи виконання T1, … , Tn яких задовольняють нерівності T1 ³ … ³ Tn. Розподіл можна подати послідовністю пар вигляду (i; k), де i – номер завдання, k – номер процесора, на якому воно виконується. Наприклад, за часів 12, 11, 10, 9, 8, 7 найкращий розподіл подається як
<(1; 1), (2; 2), (3; 3), (4; 3), (5; 2), (6; 1)>.
Подібно до розміщень ферзів, можна говорити про повний розподіл – довжини n, та неповний – меншої довжини. Так само утворимо дерево пошуку розподілів. Його коренем є порожній розподіл, синами кореня – три розподіли <(1; 1)>, <(1; 2)>, <(1; 3)> тощо, тобто синами кожного розподілу вигляду
v=<(1; k1), … , (i; ki)>
за i<n є три розподіли
v1=<(1; k1), … , (i; ki), (i+1; 1)>,
v2=<(1; k1), … , (i; ki), (i+1; 2)>,
v3=<(1; k1), … , (i; ki), (i+1; 3)>.
Повні розподіли є листками вигляду <(1; k1), … , (n; kn)>.
Тепер займемося упорядкуванням обходу дерева таким чином, щоб варіанти з меншою вартістю оброблялися якомога раніше, а варіанти з більшою вартістю – якомога пізніше. За розподілом v=<(1; k1), … , (i; ki)>, де i£ n, неважко обчислити трійку часів роботи процесорів (S1, S2, S3) з його виконання. Очевидно, його вартістю є найбільше з S1, S2, S3. Такий розподіл за i<n та час Ti+1 дають три варіанти трійок, відповідних його розподілам-синам v1, v2, v3:
(S1+Ti+1, S2, S3), (S1, S2+Ti+1, S3), (S1, S2, S3+Ti+1).
За i+1=n неважко вибрати найменшу з цих трьох вартостей. Проте за i+1<n нас будуть цікавити не стільки вартості цих неповних розподілів, скільки нижні оцінки вартості тих повних розподілів, які з них можна одержати. Цією оцінкою є вартість, менше якої не може бути вартість повних розподілів.
Розглянемо найпростіший спосіб такого оцінювання. Очевидно, що за неповного розподілу v перших i завдань із трійкою часів (S1, S2, S3) всі розподіли, що є його нащадками, мають вартість не меншу, ніж
E(v)=max{S1, S2, S3, min{S1, S2, S3}+Ti+1}.
Отже, оцінка E(v) є нижньою межею для вартості нащадків розподілу v.
Організуємо обхід дерева розподілів таким чином, що:
1. для кожного з вузлів обчислюється зазначена оцінка вартості,
2. вузли розглядаються у порядку зростання їх оцінок,
3. вузли з оцінкою, більшою від вартості вже одержаного повного розподілу, взагалі не розглядаються.
Ці міркування складають суть методу розгалужень і меж. Упорядкування вузлів робить обхід цілеспрямованим, а відкидання явно неперспективних піддерев скорочує його.
43. Навести криптографічні алгоритми шифрування.
Пусть
—
пространство ключей, а
и
—
ключи шифрования и расшифрования
соответственно.
—
функция шифрования для произвольного
ключа
,
такая что:
Здесь
,
где
—
пространство шифротекстов, а
,
где
—
пространство сообщений.
—
функция
расшифрования, с помощью которой можно
найти исходное сообщение
,
зная шифротекст
:
{
:
} —
набор шифрования, а {
:
} —
соответствующий набор для расшифрования.
Каждая пара
имеет
свойство: зная
,
невозможно решить уравнение
,
то есть для данного произвольного
шифротекста
,
невозможно найти сообщение
.
Это значит, что по данному
невозможно
определить соответствующий ключ
расшифрования
.
является
односторонней функцией, а
—
лазейкой.[3]
Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемыми Алиса и Боб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего называют Евой.
Боб выбирает пару
и
шлёт ключ шифрования
(открытый
ключ) Алисе по открытому каналу, а ключ
расшифрования
(закрытый
ключ) защищён и секретен (он не должен
передаваться по открытому каналу).Чтобы послать сообщение Бобу, Алиса применяет функцию шифрования, определённую открытым ключом : , — полученный шифротекст.
Боб расшифровывает шифротекст , применяя обратное преобразование , однозначно определённое значением .
44. Навести криптографічні алгоритми дешифрування.
метод Цезаря(расшифровка)
Пример
Суть задачи
, должна шифровать и расшифровывать...
Шифровка: < shagalkin evgeniy -> vkdjdonlqchyjhqla >...
И наоборот:
< vkdjdonlqchyjhqla -> shglkin evgeniy >
2 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
|
unit Unit1; interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type TForm1 = class(TForm) Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel; Button1: TButton; Button2: TButton; Button3: TButton; Memo1: TMemo; Memo2: TMemo; Edit1: TEdit; procedure Button3Click(Sender: TObject); procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); private { Private declarations } public { Public declarations } end;
const U:array[0..26] of char = ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ');
var Form1: TForm1; a:array[0..26] of char; i, j, k: integer; s, s2:string;
implementation
uses Unit2;
{$R *.dfm}
procedure TForm1.Button3Click(Sender: TObject);
begin Close; end;
procedure TForm1.Button1Click(Sender: TObject);
begin if edit1.text='no' then begin; For i:=0 to 26 do begin a[i]:=U[(i+1) mod 27]; end; s:=Memo1.Lines.Text; for i:=1 to length(s) do for j:=0 to 26 do if s[i]=a[j] then s2:=s2+a[(j+3) mod 27]; Memo2.Lines.Text:=s2; s2:=''; memo1.Clear; end else form2.show end;
procedure TForm1.Button2Click(Sender: TObject);
begin if edit1.text='no' then begin; For i:=0 to 26 do begin a[i]:=U[(i+1) mod 27]; end; s:=Memo1.Lines.Text; for i:=1 to length(s) do for j:=0 to 26 do if s[i]=a[j] then s2:=s2+a[(j-3) mod 27]; Memo2.Lines.Text:=s2; s2:=''; memo1.Clear; end else form2.show end; end. |