Отчёт по лабораторной работе "шифры и криптоанализ"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное  автономное образовательное учреждение высшего

профессионального образования

«САНКТ-ПЕТЕРБУРГСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО  ПРИБОРОСТРОЕНИЯ»

 

КАФЕДРА № 14

 

 

  ОТЧЕТ   ЗАЩИЩЕН С ОЦЕНКОЙ

 

  ПРЕПОДАВАТЕЛЬ

проф., к.т.н.				Н.А.Шехунова
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

 

 

Отчёт   по лабораторной работе №1

"ШИФРЫ И КРИПТОАНАЛИЗ"

по дисциплине: "Методы и средства защиты компьютерной информации"

    РАБОТУ ВЫПОЛНИЛИ

 

СТУДЕНТЫ    ГР.	5011				Е.Ю.Фортышев А.В.Антонов И.Г.Прибора Е.Я.Шевцов
			подпись, дата		инициалы, фамилия

 

 

 

 

г. Санкт-Петербург

2013

 

 

Исходные данные

 

Вариант №1: KYVIVZJEFFKYVICREXLRXVSLKWIVETY

 

 

Программа:

 

Задача 1.

 

 

1. Постановка задачи

Найти кратчайшие пути и  расстояния между данной вершиной S и всеми другими вершинами графа.

 

 

 

2. Описание алгоритма Дейкстры

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до A. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация: Метка самой вершины A полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от A до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма: Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина U, имеющая минимальную метку. Вершины, в которые ведут рёбра из U, назовем соседями этой вершины. Для каждого соседа вершины U, кроме отмеченных, как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки U и длины ребра, соединяющего U с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину U как посещенную и повторим шаг алгоритма.

 

 

Ограничения алгоритма:

Алгоритм работает только для графов без рёбер отрицательного веса. 

 

 

3. Результаты

     

Рис.1

 

 

Таблица 1.1

Вершина	Метки
s	0
a		11	11	11	11	11	11	11
b		3
c		5	5
d			6	6	6
e			5	5
f			11	7	7	7
h					9	9	8

 

 

4. Обсуждение результатов

В полученной Таблице 1.1 показано последовательное изменение меток вершин. Последняя найденная метка в строке подчёркнута и является кратчайшим расстоянием от вершины S до той вершины, в чьей строке находится эта метка.

Окончательное распределение  меток и кратчайшие пути показаны на графе с выделенными путями (Рис.1).

 

 

Задача 2.

 

 

1. Постановка задачи

Найти кратчайшие пути между  всеми парами вершин графа.

 

 

 

2. Описание алгоритма Флойда

 

.

начало

1) для k  от 1 до n шаг 1 цикл ;

2) начало ;

3) для i  от 1 до n  шаг 1 цикл ;

4) начало ;

5) для  j  от 1 до n  шаг 1 цикл ;

6) начало ;

7) если  w_ik + w_kj < w_ij , то

w_ij := w_ik + w_kj ;

z_ij := z_ik ;

8) конец цикла;

9) конец цикла;

10) конец цикла;

конец

 

 

Ограничения алгоритма:

Алгоритм работает только для графов без рёбер отрицательного веса. 

 

 

3. Результаты

Таблица 1.2

     S         A         B         C        D        E         F        H

0	11	3	5	6	5	7	8
	0	7		10	9	15	13
		0		3	2	8	6
			0	9	8	2	3
				0	3	14	7
					0	11	4
						0	1
							0

       S

       A

       B

       C

       D

       E

       F

       H

     

 

Таблица 1.3

     S         A         B         C        D        E         F        H

	A	B	C	B	B	C	C
		B		D	B	B	B
				D	E	F	E
		B		B	B	F	F
					E	E	H
						F	H
							H

       S

       A

       B

       C

       D

       E

       F

       H

     

 

4. Обсуждение результатов

Окончательные результаты работы алгоритма представлены в Таблице 1.2 – Таблице 1.3. Найдены все кратчайшие пути между всеми парами вершин.

В Таблице 1.2 находятся длины кратчайших путей для любой вершины графа от неё к остальным, если такой путь существует. А в Таблице 1.3 – вершины, образующие кратчайшие пути между парами вершин.

 

Ответы на вопросы:

1.5) Если стоимости всех весов дуг равны, алгоритм Дейкстры идентичен поиску в ширину.

Шаг алгоритма: Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается первая вершина U (не надо искать минимальную, т.к. ею всегда будет 1я из непосещённых). Вершины, в которые ведут рёбра из U, назовем соседями этой вершины. Для каждого соседа вершины U, кроме отмеченных, как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки U и длины ребра, соединяющего U с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину U как посещенную и повторим шаг алгоритма.

 

2.4) Матрица связности  – квадратная матрица NxN, элементы  которой равны 1, если существует  маршрут, соединяющий соответствующие  вершины, и 0, если нет такого  маршрута. Модификация алгоритма Флойда для получения матрицы связности (S) может быть следующей:

начало

1) для k  от 1 до n шаг 1 цикл ;

2) начало ;

3) для i  от 1 до n  шаг 1 цикл ;

4) начало ;

5) для  j  от 1 до n  шаг 1 цикл ;

6) начало ;

7) если  w_ik + w_kj < w_ij , то

w_ij := w_ik + w_kj ;

z_ij := z_ik ;

8) если  z_ij  > 0 , то

S_ij := 1;

    иначе   S_ij := 0;

9) конец цикла;

10) конец цикла;

11) конец цикла;

конец