Представление чисел со знаком. Двоично-дополнительный код.

Часть 1 №1

Машинное представление числовых данных в ЭВМ.

Для представления информации в памяти ЭВМ (как числовой, так и не числовой) используется двоичный способ кодирования. Элементарная ячейка памяти ЭВМ имеет длину 8 бит (1 байт). Каждый байт имеет свой номер (его называют адресом). Наибольшую последовательность бит, которую ЭВМ может обрабатывать как единое целое, называют машинным словом. Длина машинного слова зависит от разрядности процессора и может быть равной 16, 32 битам и т.д. Все числовые переводятся в двоичную систему счисления и записываются в определённом формате в основном в одном машинном слове. Для кодирования символов достаточно одного байта. При этом можно представить 255 символов (с десятичными кодами от 0 до 255).

Машинное представление целых чисел .

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

Представление чисел со знаком. Двоично-дополнительный код.

В машинном представлении чисел со знаком используется следующий подход:

Числа положительные записываются, так же как и без знаков, для записи отрицательных чисел используется двоично-дополнительный код. При этом в обоих случаях старший разряд является знаковым. 0= ‘+’, 1= ‘-’;

Правила построения двоично-дополнительного кода для целого отрицательного числа:

1)модуль отрицательного числа записать в двоичном виде 2)инвертировать его 3)прибавить к инверсному коду единицу.

Проблема представления целых чисел. Ее решение.

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

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

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

Машинное представление вещественных чисел. Мантисса и порядок.

В памяти компьютера вещественные числа представлены в форме с плавающей точкой, в двоичной системе счисления. Десятичное число D в этой форме записи имеет вид D=+- m*10ⁿ, где m и n – соответственно мантисса числа и его порядок. Например, число 357.5 можно записать в виде: 3575*10^-1, 0.3575*10³. Последняя запись – нормализованная форма числа с плавающей точкой. Обычная же запись числа в виде 357.5 называется формой записи с фиксированной точкой. Такое представление чисел в компьютерах используется только на этапах их ввода или вывода, в то время как хранение и обработка вещественных чисел осуществляется именно в форме с плавающей точкой.

Машинная точность

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

Так, например, если при 6 десятичных разрядах к числу 0.214724 прибавить число, меньшее по модулю половины последнего разряда (т.е. меньшее по модулю 0.0000005), в результате получится то же самое число 0.214724. Величина ошибки округления определяется количеством разрядов мантиссы. При округлении по дополнению (которое, как правило, и реализуется в компьютерах) максимальная относительная погрешность округления равна и называется машинной точностью.

Верные цифры.

Пусть а - точное значение,

- приближенное значение некоторой величины.

Абсолютной погрешностью приближенного значения называется величина

Значащими цифрами числа называют все цифры в его записи, начиная с первой ненулевой слева.

Значащую цифру числа называют верной, если абсолютная погрешность числа не превосходит единицы разряда, соответствующего этой цифре.

Часть 1 №2

Энтропия. Избыточность.

Энтропия(H)-мера неопределенности случайного объекта с конечным множеством состояний А_i с соответствующими им вероятностями р _i Величину Н называют средним количеством информации на знак, информацией на знак или энтропией источника сообщений.

Н=∑ р _i_*log(1/ р _i )

Избыточность(Е)-это мера бесполезно совершаемых альтернативных выборов. Разность L-H называют избыточностью кода. Также избыточность можно выразить в процентах, при этом относительная избыточность будет равна 100%*(L-H)/L.

Оптимальное кодирование.

Этот вид кодирования используется для уменьшения объемов информации на носителе. Код называется оптимальным, если его избыточность равна нулю.Для кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа – lср по формуле

где k – число символов исходного алфавита; n_s – число двоичных разрядов для кодирования символа s; f_s– частота символа s; причем

При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования - иначе будет потеряна информация. Этот параметр определяется предельным значением двоичных разрядов возможного эффективного кода – l_пр:

где n – мощность кодируемого алфавита, f_i – частота i-го символа кодируемого алфавита.

Как видно из формулы, этим пределом сжатия является энтропия.

Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результат - эффективные коды.

Алгоритм составления эффективного кода методом Шеннона-Фано:

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

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

3) Приписать произвольному одному из этих подмножеств (подсписков) символ " 0", а другому - " 1".

4) Рассматривая каждое из этих подмножеств (подсписков) как исходное, применительно к каждому из них осуществить операции, указанные в пунктах (2) и (3).

5) Этот процесс продолжать до тех пор, пока в каждом из очередных подмножеств не окажется по одной букве.

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

Алгоритм составления эффективного кода методом Хаффмена:

2) Объединим два наименее вероятных символа алфавита источника в один символ, вероятность которого равна сумме соответствующих вероятностей.

2*) Таким образом, нужно построить код для источника, у которого число символов уменьшилось на 1. Повторяя этот процесс несколько раз, приходим к более простой задаче кодирования источника, алфавит которого состоит из символов 0 и 1.

3) Возвращаясь на один шаг назад, имеем, что один из символов нужно разбить на два символа; это можно сделать, обавив к соответствующему кодовому слову символ 0 для одного из символов и символ 1 - для другого.

3*) Возвращаясь еще на один шаг назад, нужно таким же образом разбить один из трех имеющихся симво- лов на два символа, и так далее.

4) В результате около каждого исходного символа получим его двоичный код

Префиксные коды.

Префиксные коды - это коды однозначность декодирования которых достигается без помощи каких-либо разделительных символов. Обладают свойством: ни одна более короткая кодовая комбинация не является началом любой другой более длинной комбинации

Первая теорема Шеннона

Теорема о кодировании без шума: для n-кратного расширения достаточно высокой кратности средняя длина кодового слова L может быть сколь угодно близкой к энтропии источника.

Аналого-цифровое преобразование .

Для преобразования любого аналогового сигнала (звука, изображения) в цифровую форму необходимо выполнить три основные операции: дискретизацию, квантование и кодирование.

Первый этап формирования цифрового сигнала – дискретизация. Дискретизируют сигнал в соответствующий момент времени, а затем удерживают полученное значение отсчета до момента формирования следующего отсчета. Отсчет сигнала используют для получения его цифрового представления. Причина удерживания величины отсчета может быть не совсем очевидна. «Период удерживания» дает время аналого-цифровому преобразователю (АЦП)

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

Квантование — это отображение вещественных чисел в некоторое счётное

множество чисел, а именно в множество всех кратных некоторого числа Δ ,

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

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

Существует несколько вариантов основной формы ИКМ:

• Дельта-Модуляция (ДМ);

• Дифференциальная ИКМ (ДИКМ);

• Адаптивная Дифференциальная ИКМ (АДИКМ)

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

Часть 1 №3

Передача и восприятие информации .

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

Вторая теорема Шеннона.

Поток информации c=2*f _m*H где f частота Н энтропия.

максимальный поток информации по передающему каналу, или пропускную способность канала: c_max=2*f_m*H_max=f_m*log₂(1 +N_s/N_r)

Полосой пропускания (пропускной способностью) оценивается количество информации, которое может быть передано по каналу. Ширина полосы пропускания измеряется в битах в секунду (бит/с) - для цифровых сигналов или в герцах (Гц) - для аналоговых сигналов, например, звуковых волн. Ширина полосы пропускания для аналоговой системы равна разности вычитания наинизшей передаваемой частоты из наивысшей.

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

Расстояние Хэмминга.

Расстояние Хемминга показывает насколько «далеко» расположены разрешённые кодовые комбинации друг от друга. Расстояние Хемминга между двумя разрешёнными комбинациями определяется количеством различных двоичных разрядов между этими комбинациями. Минимальное из этих расстояний называется Минимальным расстоянием Хемминга и обозначается «d_min». d_min является важной характеристикой линейного блокового кода. Она определяет другую не менее важную характеристику- корректирующую способность: 2t< d_min. Корректирующая способность определяет, сколько ошибок передачи кода можно гарантированно исправить.

d min> 2t+S t-кратность ошибок которые можно исправить, s-которые можно обнаружить. Количество исправленных ошибок=1, 2, …t, количество обнаруженых= t+1… t+S

Часть 2 №1

Обработка сообщений и информации. Классификация видов обработки информации.

Всякое правило обработки сообщений можно понимать как отображение (функцию) ν ;

которое сообщениям m из некоторого множества сообщений M ставит в соответствие новые сообщения m' из множества сообщений M’. Каждое из сообщений m и m’ - это последовательность знаков.

Алгорифм Маркова

Элементарной операцией над последовательностями знаков может считаться замена подслова на некоторое слово (текстовая замена). Будем исходить из множеств M и M’ слов над общим набором знаков V (это можно делать без ограничения общности). Отдельную операцию замены (продукцию) будем записывать в виде а -> b и понимать её так:

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

Часть2 №2

P, NP и NP полные проблемы.

Неформально класс NP можно определить с помощью понятия, которое мы будем называть недетерминированным алгоритмом. Такой алгоритм состоит из двух различных стадий – стадии угадывания и стадии проверки.

Класс NP, определяемый неформально, - это класс всех задач распознавания П, которые при разумном кодировании могут быть решены недетерминированными ( N - nondeterministic) алгоритмами за полиномиальное ( P - polynomial) время принадлежность задачи П классу P влечет принадлежность дополнительной задачи классу P, но не известно, имеет ли место аналогичное утверждение для класса NP.

Любой детерминированный алгоритм может быть использован в качестве стадии проверки недетерминированного алгоритма.

Способность недетерминированного алгоритма проверить за полиномиальное время экспоненциальное число возможностей может навести на мысль, полиномиальные недетерминированные алгоритмы являются более мощным средством, чем полиномиальные детерминированные алгоритмы.

Фундамент теории NP-полных задач был заложен в работе С. Кука, опубликованной в 1971 г. под названием " Сложность процедур вывода теорем". В этой короткой, но элегантной работе Кук получил несколько важных результатов. Во-первых, он подчеркнул важность понятия " сводимость за полиномиальное время", т. е. сводимость, которая выполняется с помощью алгоритма с полиномиальной временной сложностью. Если одна задача сводится за полиномиальное время к другой, то любой полиномиальный алгоритм решения второй задачи может быть превращен в полиномиальный алгоритм решения первой. Во-вторых, он обратил внимание на класс задач распознавания свойств (класс NP), которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве. (Задачей распознавания свойств называется задача, решениями которой могут быть либо " да", либо " нет".) Большинство не поддающихся решению задач, которые встречаются на практике, после переформулировки их в виде задач распознавания попадают в этот класс. В-третьих, С. Кук доказал, что одна конкретная задача из NP, называемая задачей о выполнимости, обладает тем свойством, что всякая другая задача из класса NP может быть сведена к ней за полиномиальное время'). Таким образом, если задача о выполнимости может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима, а если какая-то задача из NP труднорешаема, то и задача о выполнимости также должна быть труднорешаемой Таким образом, в некотором смысле задача о выполнимости - " самая трудная" в классе NP. Вопрос о том, действительно ли NP-полные задачи труднорешаемы, в настоящее время считается одним из основных открытых вопросов

Полиномиальная сводимость.

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

Проблема-переполнение памяти.

Сводимость по Карпу также называют полиномиальной сводимостью, а часто — просто сводимостью.

Часть 2 №3

Односторонние функции и криптосистемы с открытым ключом. Примеры криптографических протоколов.

Односторонняя функция эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает нашу функцию с более чем экспоненциально малой вероятностью.

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

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

Часть 2 №4