Шпаргалка по "Информатике и ИТ"

2. Делению подвергается  каждый из подмассивов с приписыванием  очередных символов бинарного  кода, как и на предыдущем шаге. Деление продолжается до тех пор, пока каждый из конечных подмассивов не будет содержать только 1 символ алфавита.

Пример:         

	Сортировка
		1	1
		1	0	1
		1	0	0
		0	1	1
		0	1	0
		0	0	1	1
		0	0	1	0
		0	0	0	1
		0	0	0	0	1
		0	0	0	0	0

Как видно символам с наименьшей вероятностью соответствуют коды наибольшей длины, а с наибольшей вероятностью – наименьшие.

Сформированные бинарные коды должны отвечать следующим условиям:

1) все коды должны быть  уникальными;

2) должно выполняться  свойство префикса: ни один произвольный  код меньшей длины не может  быть началом произвольного кода  большей длины.

Как видно, могут существовать различные (равнозначные) варианты разделения массива. Различные разделения будут  соответствовать различные варианты кодов. Наилучший из возможных является тот вариант, которому соответствует  наименьшее значение интегрального  коэффициента С:

,     где  – вероятн. в соотв. с таблицей; l_i – длина кода.

Коэффициент С показывает среднее кол-во bit в сформировавшихся бинар. последовательностях, приходящихся на один символ алфавита А.

Алгоритм обратного  преобразования (распаковки) наоборот, т.е. компрессор и декомпрессор должны пользоваться одинаковой таблицей код-символов и наоборот.

В этом процессе на выходе должны быть символы сообщения на основе исходного алфавита А. при этом важны  два параметра: l_min, l_max.

Первый шаг: анализируется l_min первых символов в последовательности Y_n2 на предмет их соответствия каких-либо из комбинаций в таблице. Если соответствие найдено, то на выходе преобразователя будет символ а_i. Если не найдено – второй шаг: кол-во анализируемых символов увеличивается на 1 и выполняется процедура первого шага. Если на каком-либо шаге находится соответствие, то анализу подвергаются следующая l_min символов. Если ни на каком из шагов не найдено соответствие, то производится анализ последовательности: l_min+(i-1) = l_max. Если на этом i-том шаге не найдено соответствие, то либо работа преобразования закончена и принято решение, либо принято какое-либо другое решение.

Динамический метод или адаптивный метод: частота появления символов все время меняется и по мере считывания нового блока данных происходит перерасчет начальных значений частот.

Статические методы характеризуются хорошим быстродействием  и не требуют значительных ресурсов оперативной памяти. Они нашли  широкое применение в многочисленных программах-архиваторах, например ARC, PKZIP и др., но для сжатия передаваемых модемами данных используются редко  — предпочтение отдается арифметическому  кодированию и методу словарей, обеспечивающим большую степень сжатия.

 

 

 

 

 

 

 

 

 

 

18 Сжатие и распаковка информации  по методу Хаффмана.

Метод Хаффмана предусматривает  генерацию бинарных последовательностей  на основе дерева алфавита, которое  составляют попарные объединения виртуальных  символов, образующие узлы дерева. Причем две ветви, образующие узел, обозначаются соответственно 1 и 0. Созданный узел образует виртуальный символ алфавита с вероятностью появления, равной сумме  вероятностей, образующих узел, в дальнейшем этот узел может участвовать в  создании нового. Объединение символов начинается с двух символов с наименьшими  вероятностями. Структурно дерево имеет  вид иерархию. Последний узел называется корнем. Стремиться нужно к тому, чтобы на каждой ветви узлы создавали символы с примерно одинаковыми вероятностями. Бинарный код каждого символа исходного алфавита создают обозначения ветвей дерева при их обходе от корня дерева к данному символу.

Прямое преобразование заключается в замене каждого символа соответствующим бинарным кодом.

Обратное преобразование наоборот, т.е. компрессор и декомпрессор должны пользоваться одинаковой таблицей код-символ и наоборот. Т. е. процедура сжатия и распаковки такая же, как и у метода Шеннона-Фано

	1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 Сортировка
	=0,3 =0,54
	=0,2 корень дерева дерева
	=0,14 =0,46
	=0,26
	узел (а10,а8) – виртуальный символ виртуальный символ =0,12
	=0,07

 

Формально можно выделить 4 уровня иерархии.

Сформированные бинарные коды должны отвечать следующим условиям:

1) все коды должны быть  уникальными;

2) должно выполняться  свойство префикса: ни один код  меньшей длины не может быть  началом кода большей длины.

Могут существовать различные  варианты объединения символов в  пары. Наилучший вариант – когда  ему соответствует минимальное  значение интегрального коэффициента R:     [bit],  l_i – длина бинарного кода для i-того символа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

19 Сущность символ-ориентированных методов сжатия информации.

Сущность символ-ориентированных (словарных) методов состоит в  последовательном анализе сжим. информации с целью поиска повторяющихся или проаналированных ранее в данном документе последовательностей и замене таких последовательностей на более короткие. Методы, основанные на словарном подходе, не рассматривают статистические модели, они также не используют коды переменной длины. Вместо этого они выбирают некоторые последовательности символов, сохраняют их в словаре, а все последовательности кодируются в виде меток, используя словарь. Словарь может быть:

– статический словарь – является постоянным. Иногда в него добавляют новые последовательности, но никогда не удаляют.

– динамический (адаптивный) словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается и добавление, и удаление данных из словаря по мере чтения входного файла.

К этим методам  сжатия относятся следующие алгоритмы: LZ77/78, LZW, LZO и др.

LZ-алгоритм. Почти все практические словарные кодировщики принадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заменяются указателем на то место, где они в тексте уже ранее появлялись. Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие и разделяется на два семейства - алгоритмы типа LZ77 и алгоритмы типа LZ78. Этот метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов.

Раскодирование сжатого  текста осуществляется напрямую –  происходит простая замена указателя  готовой фразой из словаря, на которую  тот указывает. Одной из форм такого указателя есть пара (i,j), которая заменяет последовательность из j символов, начинающуюся со смещения i во входном потоке. По мере выполнения обработки словарь скользит по входному потоку данных. Скользящее окно имеет длину N и состоит из двух частей: последовательности уже закодированных символов, которая и является словарем, и упреждающего буфера, или буфера предварительного просмотра.

Пример: сжать строку "кот_ломом_колол_слона" длиной 21 символ. Пусть длина буфера равна 7 символам, а размер словаря больше длины сжимаемой строки.

Для кодирования i нам достаточно 5 битов, для j нужно 3 бита, и пусть символы требуют 1 байта для своего представления. Тогда всего мы потратим 12·(5+3+8) = 192 бита. Исходно строка занимала 21·8 = 168 битов, т.е. LZ77 кодирует нашу строку еще более расточительным образом.

 

 

 

 

 

 

 

 

 

 

20 Безопасность информационных технологий

Безопасность  – это свойство ИС обеспечить доступ к информационным ресурсам пользователя и процессам, которые имеют право на это, и блокировать несанкционированный доступ к объектам и процессам.

Под несанкционированным доступом (НД) понимается попытка получения доступа к информационным ресурсам без ведома и разрешения владельца этих ресурсов.

Цель несанкционированного доступа: крадеж информации, уничтожение информации, модификация информации.

Как организуется такой доступ:

- Доступ с носителя (HDD, DVD)

- Посредствам анализа  ЭМИ (электромагнитного излучения)

- Использование специализированного  ПО (деструктивные программные средства, вирусы, трояны, hacker, cracker).

Информация – сведения (данные) о внутреннем и окружающем нас мире, событиях, процессах, явлениях и т. д., воспринимаемые и передаваемые людьми или техническими устройствами.

Информационная (информационно-вычислительная) система – организационно упорядоченная совокупность документов, технических средств и информационных технологий, реализующая информационные (информационно-вычислительные) процессы.

Информационные  технологии (IT) — совокупность способов, методов и средств для выполнения операций над информацией (данными).

Безопасность IT

Особенности:

– Информация стала наиболее дорогим продуктом в межличностных, межгосударственных и экономических  отношениях людей. Информацию можно  оценить количественно.

– В сфере IT занято с каждым годом все больше людей.

– Информация становится одной  из основных причин совершения преступлений. Ежегодные потери фирм и организаций  от компьютерных преступлений составляет сотни млрд.

Поэтому информацию нужно  защищать от несанкционированного доступа.

 

21 Назначение и особенности использования  криптографических методов в  ИС

Криптос – тайный, графо  – писать. Криптология – тайнопись, наука о тайнах. Имеет 2 области: криптография и криптоанализ (анализ стойкости  методов, расшифровка). Факт применения криптографических методов является очевидным.

Основное назначение – ↑ уровня конфиденциальности информации (max затруднение для лиц, которые не должны эту информацию видеть и анализировать). Общая структурная система информационной системы с криптопреобразованием:

[Источник ] →х_к→ [Шифратор (К)] →х_n (С)→ [Канал] →у_n→ [Дешифратор] → ^у_n → [Получатель].

х_к – открытый текст, который нужно преобразовать.

С – шифрограмма, зашифрованный текст, тайное сообщение.

Криптопреобразование осуществляется на основе соответствующих алгоритомов, а также на основе тайной информации, которая называется ключом (К).

После криптопреобразования текст принимает форму, максимально затрудняющую анализ.

Современная криптография строится на 2 основных принципах (проблемах):