Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Билет 3.
1вопрос.
Арифметические действия над двоичными числами. Числа с плавающей и фиксированной запятыми. Способы представления и арифметические действия.
Арифметические действия основаны на использовании таблиц сложения, вычитания и умножения.
|
+ |
- |
* |
|
0 + 0 = 0 |
0 – 0 = 0 |
0 * 0 = 0 |
|
0 + 1 = 1 |
10 – 1 = 1 |
0 * 1 = 0 |
|
1 + 0 = 1 |
1 – 0 = 1 |
1 * 0 = 0 |
|
1 + 1 = 10 |
1 – 1 = 0 |
1 * 1 = 1 |
Двоичное сложение выполняется по тем же правилам, что и десятичное, только перенос в следующей разряд происходит после того, как сумма достигнет двух (0 – в текущем разряде, 1 – в следующем разряде).
10111,10101
+
110,1011_
11110,01011
При вычитании «0 – 1» занимаем единицу в старшем разряде. Если там нуль, то заём выполняется в ближайшем разряде, где есть 1. При этом занимаемая единица равна двум единицам целого разряда.
10010
-
101
1101
Умножение.
100,1
*
10,1
1001
1001__
1011,01
Деление производится с использованием таблиц вычитания и умножения.
1100,011 : 10,01 = 110001,1 : 1001
110001,1 |1001
- 101,1
1001
1101
-
1001
1001
-
1001
0
Числа с плавающей и фиксированной запятыми. Арифметические операции над числами.
Применяются два основных способа представления чисел – с фиксированной и плавающей запятой. Так, программирование для ЭВМ, работающих в системе с фиксированной запятой, значительно усложняется, поскольку помимо алгоритмических трудностей этот процесс требует ещё отслеживания положения запятой.
Фиксированная запятая.
Разрядная сетка машины имеет постоянное число разрядов – n. При представлении чисел с фиксированной запятой считают, что запятая всегда находится перед старшим разрядом, а все числа, которые участвуют в вычислениях, считаются по абсолютной величине меньше единицы:
|X| < 1.
Введём две характеристики чисел: диапазон изменения и точность представления. Диапазон изменения характеризуется теми пределами, в которых могут находиться числа, с которыми оперирует машина. Точность представления – это отличное от нуля самое малое число.
Таким образом, диапазон чисел, с которыми работает ЭВМ, есть:
|X|min |X| |X|max
2-n |X| 1 – 2-n
Числа, которые выходят за диапазон изменения, в ЭВМ не могут быть представлены точно. Если |X| < |X|min = 2-n, то такое число воспринимается как нуль. Если |X| > |X|max = 1 – 2-n, то такое число воспринимается как бесконечно большое. Этим двум случаям соответствуют понятия машинного нуля и машинной бесконечности.
При оптимальном округлении абсолютная ошибка:
|ΔX| = 0,5*2-n.
Минимальная относительная ошибка:
,
так как (1 – 2-n) = 1 при большом n.
Максимальная относительная ошибка:
.
Плавающая запятая.
В ЭВМ с плавающей запятой число представляется в виде:
X = ± Mx * (q ± p),
где Mx - мантисса числа, q – основание системы счисления, p – порядок.
Разрядная сетка машины – это лишь условное изображение основных слогов в числе. Заметим, что в реальной ЭВМ может быть принят любой другой порядок расположения.
Пусть m разрядов отведено под изображение мантиссы, а k разрядов под изображение порядка. Тогда для двоичной системы и нормализованного вида числа:
q = 2; 0,1 < Mx < 1 - нормализованная мантисса.
Абсолютная ошибка представления числа в ЭВМ с плавающей запятой равна:
|ΔX| = 0,5*2-m.
Т. к. 2-1 < |Mx| < 1 – 2-m, то минимальная относительная ошибка:
при большом m, а максимальная относительная ошибка:
Видно, что относительная ошибка в ЭВМ с плавающей запятой не зависит от порядка числа. При этом точность представления больших и малых чисел изменяется незначительно.
Теоретически «плавающая запятая» имеет преимущества перед «фиксированной». Но соответствующее устройство получается намного сложнее. К тому же специфика выполнения операций с плавающей запятой требует большего числа микроопераций, что приводит к снижению быстродействия ЭВМ. Однако «плавающая запятая» снимает с программиста обязанность отслеживать положение запятой в вычислениях и значительно упрощает сам процесс программирования вычислительных задач.
Выполнение арифметических операций над числами, представленными с фиксированной запятой.
Основной особенностью различных методов выполнения арифметических операций является то, что любая операция (сложение, вычитание, умножение, деление и др.) сводится к некоторой последовательности микроопераций, таких как сложение, сдвиг, передача и преобразование кодов.
Сложение выполняется по правилам сложения чисел в позиционных системах счисления. То есть эта операция выполняется поразрядно, а возникающий в младших разрядах перенос направляется в старшие разряды.
0,101101 1-ое слагаемое
+
0,000101 2-ое слагаемое
0,101000 сумма
0,00101 перенос
0,100010 сумма
0,01 перенос
0,110010 сумма
Операции сложения производятся одновременно над всеми разрядами двух слагаемых и продолжаются до тех пор, пока возникают переносы. Возникающие переносы приводят к продолжению операции. Это одна из особенностей позиционных систем. Видим, что собственно операция определения частичной суммы слагаемых выполняется в один приём, а возникающие переносы распространяются на всё более старшие разряды.
Сдвиг.
Различают два вида микрооперации нулями сдвига: логический сдвиг и арифметический сдвиг. Логический сдвиг приводит к смещению всех разрядов числа, включая и знак, влево или вправо. При этом освобождающиеся разряды заполняются или единицами. Арифметический сдвиг выполняется над частью числа, часть сдвинутых разрядов теряется. (Очевидно, знаковый разряд должен исключаться из рассмотрения).
Передача.
Эта микрооперация предполагает, что некоторый код (число) записывается в соответствующее устройство и вытесняет тот код, который там находился до передачи. Различают два вида передач: запись (с разрушением ранее записанной информации) и чтение (без разрушения).
Преобразование.
Функция, выполняемая над передаваемыми числами, называется преобразованием. Чаще других в арифметических основах рассматривают инвертирование кода. Это поразрядная микрооперация (1 i n), которая выполняется над всеми разрядами одновременно.
2вопрос.Управление файлами в ОС.
Совместное использование файлов
В многопользовательской системе практически всегда необходима возмож ность совместного использования файлов пользователями. При этом возникают два вопроса: права доступа и управление одновременным доступом.
Права доступа
Файловая система должна обеспечить возможность управляемого доступа к файлу со стороны множества пользователей. Обычно права доступа к файлу пре доставляются пользователям или группам пользователей. Используется широкий диапазон прав доступа. В приведенном списке указаны права доступа, которые могут быть предоставлены определенному пользователю по отношению к неко торому файлу.
Отсутствие. Пользователь не может обнаружить даже существование файла, не говоря уже о доступе к нему. Для обеспечения такого ограничения нуж но запретить пользователю чтение пользовательского каталога, содержаще го этот файл.
Знание. Пользователь может обнаружить существование файла и устано вить его владельца. После этого пользователь может обратиться к владель цу для получения дополнительных прав доступа к файлу.
Выполнение. Пользователь может загрузить и выполнить программу, одна ко выполнить копирование файла не может. Пользовательские программы часто бывают доступны с таким ограничением.
Чтение. Пользователь может осуществить чтение файла для любой цели, включая копирование и выполнение. Некоторые системы могут разли чать чтение и копирование. В таком случае содержимое файла может быть выведено на дисплей, однако выполнить копирование файла поль зователю не удастся.
Добавление. Пользователь может добавить данные в файл, часто только в его конец, но произвести изменение или удаление содержимого файла ему не уда стся. Это право полезно при накоплении данных из различных источников.
Обновление. Пользователь может выполнять изменение, удаление или добавле ние данных в файле. Обычно сюда относятся операции начальной записи в файл, полной или частичной перезаписи, полного или частичного удаления данных. Некоторые системы различают разные степени обновления.
Изменение защиты. Пользователь может изменять права доступа, предос тавленные другим пользователям. Обычно это право принадлежит только владельцу файла. В некоторых системах пользователь может распростра нить это право на других пользователей. Для защиты от злоупотребления этим механизмом владелец файла может определять, какие права могут быть изменены.
Удаление. Пользователь может удалить файл из файловой системы.
Владелец обладает все ми перечисленными правами и может предоставлять права остальным пользова телям. Доступ может быть предоставлен различным классам пользователей.
Конкретный пользователь. Индивидуальные пользователи, определяемые посредством своих идентификаторов.
Группы пользователей. Множество пользователей, не определенных инди видуально. Система должна обладать некоторым способом отслеживания членства пользователей в группе.
Все. Все пользователи, имеющие доступ к системе. Файлы общего пользо вания доступны для всех пользователей.
Одновременный доступ
Если права доступа позволяют добавлять или обновлять файл более чем од ному пользователю, то в этом случае операционной системой или системой управления файлами должен быть организован определенный порядок работы пользователей с файлом.
Записи и блоки
Записи представляют собой логическую единицу доступа к файлу, в то время как единицами ввода-вывода при сохранении во внешней памяти являются блоки. Для выполнения операций ввода-вывода необходимо организовать записи в блоки.
Размещение файлов
При размещении файлов возникает ряд вопросов.
1. Необходимо ли сразу выделять файлу максимальное пространство при его создании?
2. Для файла отводится пространство в виде одного или нескольких непрерывных единиц, которые мы будем называть порциями. Размер такой порции может варьироваться от одного блока до целого файла. Какой размер порции следует использовать при размещении файла?
3. Какой тип структур данных или таблиц используется для учета порций файла? Такая таблица обычно называется таблицей размещения файлов.
Предварительное динамическое размещение
Стратегия предварительного размещения файла при запросе на его создание требует, чтобы заранее был известен максимальный размер файла. Эта стратегия приводит к перерасходу дискового пространства и предпочтительнее использовать динамическое размещение, при котором выделение пространства под порции файла происходит по мере необходимости.
Методы размещения файлов
Наиболее широко используются три метода: непрерывный, цепочечный и индексированный. При непрерывном размещении создаваемому файлу выделяется отдель ное непрерывное множество блоков. Таким образом, это стратегия предварительного размещения с порциями переменного размера. Для каждо го файла таблице размещения необходим только один элемент, определяю щий начальный блок и длину файла. Непрерывное размещение является наилучшим с точки зрения индивидуального файла последовательного досту па. Для повышения производительности ввода-вывода при последовательной обработке одновременно может обрабатываться большое количество блоков. Выборка одиночного блока осуществляется очень просто. Время от времени возникает потребность в выполнении упаковки для освобождения необходимого пространства на диске. Кроме того, как уже упоминалось, при предварительном размещении в момент создания файла следует объявлять его размер.
Цепочечное размещение файла. Обычно размещение выполняется по од ному блоку. Каждый блок содержит указатель на следующий блок в цепочке. В этой схеме таблице размещения файлов необходим только один элемент для ка ждого файла, указывающий начальный блок и длину файла. Такой тип физической организации лучше всего подходит для файлов последовательного доступа, обработка данных в которых выполняется последовательно. Для выбора отдельного блока файла необходимо отследить всю цепочку до достижения искомого блока. Цепочечная методика имеет одну особенность — к ней неприме ним принцип локализации.
Индексированное размещение решает ряд проблем непрерывного и цепо чечного размещения файлов. В этом случае в таблице размещения файлов име ется отдельный одноуровневый индекс для каждого файла. Индекс содержит по одной записи для каждой порции файла. Обычно индексы файла физически не хранятся в виде части таблицы размещения файлов; вместо этого индексы файла сохраняются в отдельном блоке, и в элементе таблицы размещения файла имеет ся указатель на этот блок. Индексированное размещение поддерживает как последовательный, так и прямой доступ к файлу и потому является наиболее популярным видом файлового размещения.
3вопрос. Ассиметричные системы шифрования: основные понятия и определения, области применения. Алгоритм RSA, особенности его практического использования.
Ассиметричные системы шифрования
Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций , что
По известному x довольно просто найти значение f(x), тогда как определение x из f(x) сложно в смысле теории.
Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x), можно вычислить x. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.
Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции f(АЛИСАГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:
Имя f(имя_пароль)
АЛИСА РОМАШКА
БОБ НАРЦИСС
Вход в систему теперь выглядит так:
Имя: АЛИСА
Пароль: ГЛАДИОЛУС
Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к АЛИСАГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция необратимая.
Полезно рассмотреть также схему на примере большого абонентского справочника, состоящего из нескольких толстых томов. По нему очень легко найти номер любого жителя города, но почти невозможно найти по известному номеру абонента. Теперь для каждой буквы из отправляемого сообщения выбирается случайно имя, начинающееся на ту же букву. Таким образом, букве ставится в соответствие номер телефона абонента или шифр. Отправляемое сообщение «КОРОБКА» будет шифроваться следующим образом:
Сообщение Выбранное имя Криптотекст
К Королёв 5643452
О Орехов 3572651
Р Рузаева 4673956
O Осипов 3517289
Б Батурин 7755628
К Кирсанова 1235267
А Арсеньева 8492746
Криптотекстом будет являться цепочка номеров, записанных в порядке их появления в таблице. Из примера следует, что одному и тому же сообщению может соответствовать несколько криптотекстов.
Примеры таких криптотекстов:
Криптотекст 1 Криптотекст 2 Криптотекст 3
1235267 5643452 1235267
3572651 3517289 3517289
4673956 4673956 4673956
3517289 3572651 3572651
7755628 7755628 7755628
5643452 1235267 5643452
8492746 8492746 8492746
Чтобы расшифровать текст, достаточно иметь справочник, составленный согласно возрастанию номеров. Этот справочник является лазейкой (секрет, который помогает получить начальный текст), известной только легальным пользователям. Не имея на руках копии справочника, криптоаналитик затратит очень много времени на расшифровку.
Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. - функция шифрования для произвольного ключа eK, такая что:
Здесь , где C — пространство шифротекстов, а , где M — пространство сообщений.
- фукция расшифрования , с помощью которой можно найти исходное сообщение m, зная шифротекст c :
{: eK }- набор шифрования, а {: } — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная , невозможно решить уравнение , то есть для данного произвольного шифротекста , невозможно найти сообщение . Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. является односторонней функцией, а d - лазейкой.
Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемых Алиса и Боб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего называют Евой.
1 Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).
2 Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: , c — полученный шифротекст.
3 Боб расшифровывает шифротекст c, применяя обратное преобразование однозначно определённое значением d.
Алгоритм RSA
Система основана на трудности разложения очень больших целых чисел на простые сомножители. Алгоритм ее работает так:
Практическое использование алгоритма RSA
Для алгоритмов, основанных на открытых ключах, существует ряд математических проблем, которые не всегда учитываются при построении криптосистемы. К ним можно отнести выбор начальных значений, на основе которых создаются ключи. Есть определенные числа, позволяющие очень быстро вычислить секретный ключ. В то же время правильный выбор начальных значений позволяет гарантировать невозможность вскрытия методом «грубой силы» в течение нескольких сотен лет при современном развитии вычислительной техники.