Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Информация ее представление и измерение [3] 2

Работа добавлена на сайт samzan.net:

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 9.11.2024

Самарский государственный архитектурно-строительный университет

О.В. Прохорова

ИНФОРМАТИКА

Курс лекций

Самара 2012

1. Информация, ее представление и измерение

Информатика – это наука об информационных процессах, о моделях, об алгоритмах и алгоритмизации, о программах и программировании, об исполнителях алгоритмов и различных исполняющих системах об их использовании в обществе, в природе, в познании [1].

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

Теоретическая информатика (brainware, "мозговое" обеспечение) изучает теоретические проблемы информационных сред.

Практическая, прикладная информатика (software, "гибкое", программное обеспечение) изучает практические проблемы информационных сред.

Техническая информатика (hardware, "тяжелое", аппаратное обеспечение) изучает технические проблемы информационных сред.

Пример. Задача построения математической модели прогноза кредитного риска банка – это задача теоретической информатики и экономики.

Построение алгоритма прогноза по этой модели – задача теоретической информатики.

Разработка компьютерной программы (комплекса программ) для прогноза риска – задача практической информатики.

Часто (особенно, в области практической информатики) говорят о предметной информатике, например, о медицинской информатике, физической информатике, компьютерной физике и т.д.

Предметная область науки "информатика" – информационные системы, модели, языки их описания, технологии их актуализации.

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

Понятие "информация" имеет различные трактовки в разных предметных областях. Например, информация может пониматься как:

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

Рассмотрим фундаментальное понятие информатики на основе понятия "алфавит" . Дадим формальное определение алфавита.

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

Буквой или знаком называется любой элемент x алфавита X, где . Понятие знака неразрывно связано с тем, что им обозначается ("со смыслом"), они вместе могут рассматриваться как пара элементов (x, y), где x – сам знак, а y – обозначаемое этим знаком.

Пример. Примеры алфавитов: множество из десяти цифр, множество из знаков русского языка, точка и тире в азбуке Морзе и др.

Конечная последовательность букв алфавита называется словом в алфавите (или над алфавитом).

Длиной |p| некоторого слова p над алфавитом Х называется число составляющих его символов.

Слово (обозначаемое символом Ø) имеющее нулевую длину, называется пустым словом: |Ø| = 0.

Множество различных слов над алфавитом X обозначим через S(X) и назовем словарным запасом (словарем) алфавита (над алфавитом) X.

В отличие от конечного алфавита, словарный запас может быть и бесконечным.

Слова над некоторым заданным алфавитом определяют сообщения.

Пример. Слова над алфавитом десятичных цифр и знаков арифметических операций – "1256", "23+78", "35–6+89", "4".

В алфавите должен быть определен порядок следования символов алфавита, то есть любой алфавит имеет упорядоченный вид X = {x1, x2, …, xn} .

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

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

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

Информация по отношению к источнику или приемнику бывает трех типов: входная, выходная и внутренняя.

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

Информация по стадии ее использования бывает первичная и вторичная.

Информация по ее полноте бывает избыточная, достаточная и недостаточная.

Информация по доступу к ней бывает открытая и закрытая.

Есть и другие типы классификации информации.

Основные свойства информации:

полнота;
актуальность;
адекватность;
понятность;
достоверность;
массовость;
устойчивость;
ценность и др.

Информацию можно трактовать как содержание сообщения.

Сообщение – форма информации.

Любые сообщения измеряются в байтах, килобайтах, мегабайтах, гигабайтах, терабайтах и т.д., а кодируются в компьютере с помощью алфавита из нулей и единиц, т.е. записываются и реализуются в ЭВМ в битах.

Приведем основные соотношения между единицами измерения сообщений:

1 бит (binary digit– двоичное число) = 0 или 1,

1 байт = 8 бит,

1 килобайт (1Кб) = 213бит,

1 мегабайт (1Мб) = 223бит,

1 гигабайт (1Гб) = 233 бит,

1 терабайт (1Тб) = 243 бит,

Пример. Найти неизвестные х и у, если заданны соотношения:

128y (Кб) = 32x (бит);

2x (Мб) = 2y (байт).

Решение. Выравниваем единицы измерения информации:

128y (Кб) =27y (K) = 27y *213(бит)= 27y+13 (бит)= 25х (бит);

5х = 7y + 13.

2x (Мб) = 2х * 223(бит) = 2х+20 (байт) = 2y (байт).

x+ 20 = y.

Отсюда получаем систему двух алгебраических уравнений:

Решая эту систему, окончательно получаем, x = –76,5, у = –56,5.

Для измерения информации используются различные подходы и методы, например, с использованием меры информации по Р. Хартли и К. Шеннону.

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

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

Рассмотрим различные меры информации. Сначала рассмотри меру Р. Хартли.

Пусть известны N состояний системы S (N - число опытов с различными, равновозможными, последовательными состояниями системы). Если каждое состояние системы закодировать двоичными кодами, то длину кода d необходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N:

Логарифмируя это неравенство, можно записать:

Наименьшее решение этого неравенства или мера разнообразия множества состояний системы и задается формулой Р. Хартли:

H = log2N (бит).

Если во множестве X = {x1, x2, ..., xn} искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее log2n (единиц) информации.

Уменьшение Н говорит об уменьшении разнообразия состояний N системы.

Увеличение Н говорит об увеличении разнообразия состояний N системы.

Мера Хартли подходит лишь для идеальных, абстрактных систем, так как в реальных системах состояния системы не равновероятны.

Для таких систем используют меру К. Шеннона.

Мера Шеннона оценивает информацию отвлеченно от ее смысла:

где n – число состояний системы; рi – вероятность (относительная частота) перехода системы в i-е состояние (сумма всех pi должна равняться 1).

Если все состояния рассматриваемой системы равно возможны, равновероятны, то есть рi = 1/n , то из формулы Шеннона можно получить (как частный случай) формулу Хартли:

I = log2n ,

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

Пример. Если положение точки в системе из 10 клеток известно, например если точка находится только в одной - во второй клетке, то есть

рi = 0, i = 1, 3, 4, …, 10, р2 = 1 ,

то тогда получаем количество информации, равное нулю:

I = log21 = 0 .

Введем величину:

fi = –nlog2pi.

В термодинамике известен так называемый коэффициент Больцмана

k = 1.38 * 10–16 (эрг/град)

и выражение (формула Больцмана) для энтропии или меры хаоса в термодинамической системе:

Сравнивая выражения для I и S, можно заключить, что величину I можно понимать как энтропию из-за нехватки информации в системе (о системе).

Основное функциональное соотношение между энтропией и информацией имеет вид:

I + S(log2e) / k = const.

Из этой формулы следуют важные выводы:

Увеличение меры Шеннона свидетельствует об уменьшении энтропии (увеличении порядка) системы;
Уменьшение меры Шеннона свидетельствует об увеличении энтропии (увеличении беспорядка) системы.

Положительная сторона формулы Шеннона – ее отвлеченность от смысла информации. Кроме того, в отличие от формулы Хартли, она учитывает различие состояний, что делает ее пригодной для практических вычислений. Основная отрицательная сторона формулы Шеннона – она не распознает различные состояния системы с одинаковой вероятностью.

Методы получения информации можно разбить на три большие группы.

Эмпирические методы или методы получения эмпирических данных.
Теоретические методы или методы построения различных теорий.
Эмпирико-теоретические методы (смешанные) или методы построения теорий на основе полученных эмпирических данных об объекте, процессе, явлении.

Охарактеризуем кратко эмпирические методы.

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

Кроме классических форм их реализации, в последнее время используются опрос, интервью, тестирование и другие.

Охарактеризуем кратко эмпирико-теоретические методы получения информации:

Абстрагирование – выделение наиболее важных для исследования свойств, сторон исследуемого объекта, процесса, явления и игнорирование несущественных и второстепенных.
Анализ – разъединение целого на части с целью выявления их связей.
Декомпозиция – разъединение целого на части с сохранением их связей с окружением.
Синтез – соединение частей в целое с целью выявления их взаимосвязей.
Композиция — соединение частей целого с сохранением их взаимосвязей с окружением.
Индукция – получение знания о целом по знаниям о частях.
Дедукция – получение знания о частях по знаниям о целом.
Эвристики, использование эвристических процедур – получение знания о целом по знаниям о частях и по наблюдениям, опыту, интуиции, предвидению.
Моделирование (простое моделирование), использование приборов – получение знания о целом или о его частях с помощью модели или приборов.
Логический метод– поиск знаний путем воспроизведения частей, связей или элементов в мышлении.
Макетирование– получение информации по макету, представлению частей в упрощенном, но целостном виде.
Актуализация– получение информации с помощью перевода целого или его частей (а следовательно, и целого) из статического состояния в динамическое состояние.
Визуализация– получение информации с помощью наглядного или визуального представления состояний объекта, процесса, явления.

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

Информационная система – это система, в которой элементы, структура, цель, ресурсы рассматриваются на информационном уровне.

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

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

2. Общая характеристика процессов сбора, передачи и обработки информации

2.1. Системы счисления и действия в них

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

Алфавит Х из р символов и правила записи (изображения) и обработки чисел с помощью символов этого алфавита называются системой счисления (нумерацией) с основанием р. Число х в системе с основанием р обозначается как (х)р или хр [1].

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

Все системы счисления строятся по общему принципу.

Определяется величина р – основание системы, любое число х записывается в виде комбинации степеней веса р от 0-й до n-й степени следующим образом:

(x)p = xnpn + xn–1pn–1 + ... + x1p1 + x0p0.

Наиболее используемые в информатике системы счисления кроме десятичной – это:

1) двоичная, над алфавитом Х = {0,1};

2) восьмеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7};

3) шестнадцатеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F}, где символы А, В, С, D, Е, F имеют, соответственно, десятичные веса:

A	B	C	D	E	F
10	11	12	13	14	15

Пример. 11012 = 1 * 23 + 1 * 22 + 0 * 21 + 1 * 20 = 8 + 4 + 1 = 1310,

1578 = 1 * 82 + 5 * 81 + 7 * 80 = 64 + 40 + 7 = 11110,

A6F16 = 10 * 162 + 6 * 161 + 15 * 1 = 267110.

Пример. Найти: 1210 = ?2. Решение:

1210 = 8 + 4 = 1 * 23 + 1 * 22 + 0 * 21 + 0 * 20 = 11002.

Пример. Найти 2910 = ?8.

Решение имеет вид: 2910 = 3 * 81 + 5 * 80 = 358;

Пример. Найти 7910 = ?16.

Решение: 7910 = 64+15= 4 * 161 + 15 * 160 = 4F16.

Для перевода из 2-ой в 8-ую системы счислений и наоборот, из 2-ной в 16-ную системы счислений и наоборот, из 8-ной в 16-ную и обратно используется таблица следующего вида:

ОСНОВАНИЕ СИСТЕМЫ
10			2
0			0000
1			0001
2			0010
3			0011
4			0100
5			0101
6			0110
7			0111
8			1000
9			1001
10			1010
11			1011
12			1100
13			1101
14			1110
15			1111

При переводе в 8-ную систему или из нее необходимо группировать информацию в тройки биты, а при переводе в 16-ную или из нее – группировать - в четверки битов. Можно добавлять, если нужно, незначащие нули слева от целой части или отбрасывать их.

Сложение в двоичной системе счисления осуществляется по правилам

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 210 = 102 (единица идет в старший разряд).

Таблица вычитания в двоичной системе счисления имеет вид

0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 0 – 1 = 10 – 1 = 1 (единица забирается из старшего разряда).

Таблица умножения в двоичной системе счисления имеет вид

0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.

Таблица деления в двоичной системе счисления имеет вид

0 : 0 = не определено, 1 : 0 = не определено, 0 : 1 = 0, 1 : 1 = 1.

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

Дополнительный код = обратный код + единица в младшем разряде.

Пример.

10011 двоичное число,

01100 обратный код этого двоичного числа,

01101 дополнительный код этого двоичного числа;

457 восьмеричное число,

320 обратный код этого восьмеричного числа,

321 дополнительный код;

А9 шестнадцатеричное число,

56 обратный код этого шестнадцатиричного числа,

57 дополнительный код.

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

Пример. Произвести вычитание двоичных чисел через сложение уменьшаемого с дополнительным кодом вычитаемого.

11110101011

- 1010101010

Решение.

а) расширим размерность вычитаемого до размерности уменьшаемого, добавив нуль слева, получим: 01010101010

б) вычислим обратный код к вычитаемому, получим: 10101010101

г) вычислим дополнительный код для вычитаемого, прибавив 1 к младшему разряду обратного кода, получим: 10101010110.

д) сложим уменьшаемое с полученным дополнительным кодом вычитаемого, получим:

11110101011

+ 10101010110

____________

1)10100000001. (Старший разряд отбрасывается).

Что совпало с результатом прямого вычитания предыдущего примера.

2.2. Общая характеристика процессов передачи информации

Пространство сообщений. Коды обнаружения и исправления ошибок

Введем пространство сообщений в виде E(n, Um), где Um - алфавит, m - размерность алфавита, n - число символов из алфавита, образующих сообщение (слово) [2]. Такое пространство сообщений можно рассматривать как метрическое пространство, в котором расстояние между двумя сообщениями x и y, обозначаемое d (x, y) есть число различающихся символов в сообщениях x и y.

Пример. Пусть имеем алфавит U2 = {0,1} и пространство сообщений E(6, U2), в котором формируются сообщения: x = (0 1 0 1 0 0), y = (1 1 1 0 0 0). Расстояние по Хеммингу между этими сообщениями будет равно 3, то есть d (x, y) = 3.

Приведенное определение расстояния d(x,y) в пространстве сообщений удовлетворяет всем свойствам расстояния. В процессе передачи информации по каналам связи возможно искажение передаваемого сообщения. При использовании двоичного алфавита искажение может привести к тому, что в принятом сообщении какая-нибудь переданная единица сменит свое значение на ноль или наоборот ноль исказится и примет значение единица. Возникает вопрос, как построить коды, позволяющие обнаруживать такие сбои при передаче информации или даже позволяющие восстановить значения искаженных разрядов. Назовем коды, обладающие свойством обнаружения сбоев и восстановления искаженных разрядов при передаче информации помехоустойчивыми.

Рассмотрим случай, когда в процессе передачи сообщения оно может исказиться не более чем в k разрядах. В пространстве сообщений E(n, U2) выделим подмножество

Hk  E( n, U2), обладающее тем свойством, что для  x, y  Hk выполняется неравенство:

d (x, y) > k.	(2.1)

Множество Hk назовем множеством осмысленных слов. Тогда любое x1  Hk будет бессмысленным словом. Предположим, что при передаче слова x  Hk оно исказилось и перешло в x1, но поскольку по условию искажение может произойти не более чем в k разрядах, то расстояние d(x, x1) k, следовательно, x1  Hk и x1 есть бессмысленное слово. Таким образом, коды, удовлетворяющие условию (8.1), есть коды с обнаружением ошибки.

Пример. В пространстве сообщений E(3, U2 ) сформировать множество осмысленных слов.

Решение. Предлагается в качестве множества осмысленных слов H1 рассматривать множество { 000, 011, 110,101} c расстоянием между кодами 2. Тогда при k = 1 при передаче сообщения искажение в любом одном разряде превратит слово в бессмысленное.

Пример. В пространстве сообщений E(n-1, U2) сформировать множество осмысленных слов.

Решение. Предлагается в качестве множества H1 осмысленных слов рассматривать множество кодов, к которым добавляется один разряд, значение которого выбирается таким образом, чтобы общее число единиц в словах x  H1 было четным. Если в качестве пространства сообщений рассматривать Е(3, U2) = (000, 001, 010, 011, 100, 101, 110, 111 ), то в качестве H1 можно предложить множество

H1 = { 0000,1001,1010, 0011,1100, 0101, 0110,1111 }.

Искажение любого одного разряда в этих словах превращает их в бессмысленные, так как исказится четность числа. В рассмотренном примере 4-х разрядный код с обнаружением ошибки дает возможность составить 2n , то есть 16 различных слов. Однако, в качестве осмысленных слов, то есть подлежащих передаче по каналу связи используется только 8.

Коды с избыточностью - это коды, у которых количество осмысленных слов меньше общего числа возможных слов. Наличие избыточности является необходимым условием построения помехоустойчивых кодов. Рассмотрим построение кодов с обнаружением и исправлением ошибок, возникших при передаче сообщений. Предположим, что в процессе передачи информации может исказиться не более k разрядов кода. Множество осмысленных слов Hk  E(n, U2) назначим таким образом, чтобы расстояние между его кодами подчинялось условию:

d (x, y) > 2k

(2.2)

для  x, y  Hk. Пусть в результате искажения код x перешел в код x1, тогда

d(x, x1) k.

Запишем неравенство треугольника

d(x, y)  d (x, x1) + d (x1, y).

Усилим неравенство:

2k < k + d(x1, y) ,

что равносильно неравенству

d(x1,y) > k.

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

Пример. В пространстве сообщений Е(4, U2) назначить множество осмысленных слов с расстоянием 3.

Решение. Если расстояние между сообщениями d(x, y) = 3, то, выбрав k = 1, для множества осмысленных слов зададим условие d(x, y)  2k. Что позволяет в качестве осмысленных слов выбрать коды: 0000, 0111. Тогда, если при передаче сообщения x = 0000 оно исказится и примет вид x1 = 0001, то d(x, x1) = 1, d(x1, y) = 2. Следовательно, передано было сообщение 0000, то есть введенное множество H1 позволяет определять ошибку в переданном сообщении, и позволяет восстанавливать сообщение, подвергшееся искажению.

2.3. Кодирование и шифрование информации

Возникновение индустрии обработки информации привело к возникновению индустрии средств ее защиты и к актуализации самой проблемы защиты информации, проблемы информационной безопасности.

Одна из наиболее важных задач информатизации процессов – кодирование сообщений и шифрование информации.

Вопросами защиты и скрытия информации занимается наука кpиптология. Кpиптология имеет два основных напpавления – кpиптогpафию и кpиптоанализ.

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

"Криптография" - система перекодировки сообщения с целью сделать его непонятным для непосвященных лиц.

Введем некоторые основные понятия кодирования и шифрования.

Код – правило соответствия набора знаков одного множества Х знакам другого множества Y. Если каждому символу Х при кодировании соответствует отдельный знак Y, то это кодирование. Если для каждого символа из Y однозначно отыщется по некоторому правилу его прообраз в X, то это правило называется декодированием.

Кодирование – процесс преобразования символов алфавита Х в символы алфавита Y.

При представлении сообщений в ЭВМ все символы кодируются байтами.

Пример. Если каждый цвет кодировать двумя битами, то можно закодировать не более 22 = 4 цветов, тремя – 23 = 8 цветов, восемью битами (байтом) – 256 цветов.

Сообщение, которое мы хотим передать адресату, назовем открытым сообщением. Оно определено над некоторым алфавитом.

Зашифрованное сообщение может быть построено над другим алфавитом. Назовем его закрытым сообщением. Процесс преобразования открытого сообщения в закрытое сообщение и есть шифрование.

Если А – открытое сообщение, В – закрытое сообщение (шифр) , f – правило шифрования, то f(A) = B.

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

При кодировании нет такого секретного ключа, так как кодирование ставит целью лишь более сжатое, компактное представление сообщения.

Если k – ключ, то можно записать f(k(A)) = B. Для каждого ключа k, преобразование f(k) должно быть обратимым, то есть f(k(B)) = A. Совокупность преобразования f(k) и k называется шифром.

Традиционные симметричные криптосистемы

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

Функциональная схема взаимодействия участников симметричного криптографического обмена приведена на рис. 2.1.

Рис. 2.1. Функциональная схема симметричной криптосистемы

В симметричной криптосистеме секретный ключ необходимо передать всем участникам криптографической сети по некоторому защищенному каналу.

В настоящее время симметричные шифры - это:

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

Существует множество (не менее двух десятков) алгоритмов симметричных шифров, существенными параметрами которых являются:

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

Распространенные алгоритмы симметричного шифрования:

DES и TripleDES (3DES)
AES (Rijndael)
ГОСТ 28147-89

В частности, AES — симметричный алгоритм блочного шифрования, принятый в качестве американского стандарта шифрования правительством США в 2002году, до него c 1977 года официальным стандартом США был алгоритм DES. По состоянию на 2006 год AES является одним из самых распространённых алгоритмов симметричного шифрования.

Шифры традиционных симметричных криптосистем можно разделить на следующие основные виды [3,4]:

1. Шифры замены.

2. Шифры перестановки.

3. Шифры гаммирования.

Шифрование методом замены

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

Рассмотрим наиболее известные шифры моноалфавитной замены.

Шифрование методом Цезаря

Свое название данный шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э).

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

С=P+K (mod M),

(2.3)

где P – номер символа открытого текста в алфавите, С – соответствующий ему номер символа шифротекста, K – ключ шифрования (коэффициент сдвига), M – размер алфавита (для русского языка M=32)

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

Пример. Таблица подстановок для символов русского текста при ключе K=3 представлена в таблице 4.1. Данной таблице соответствует формула

С=P+3 (mod 32)

(2.4)

Табл. 2.1. Табл. подстановок шифра Цезаря для ключа K=3

А		Г	Р		У
Б		Д	С		Ф
В		Е	Т		Х
Г		Ж	У		Ц
Д		З	Ф		Ч
Е		И	Х		Ш
Ж		Й	Ц		Щ
З		К	Ч		Ь
И		Л	Ш		Ы
Й		М	Щ		Ъ
К		Н	Ь		Э
Л		О	Ы		Ю
М		П	Ъ		Я
Н		Р	Э		А
О		С	Ю		Б
П		Т	Я		В

Согласно формуле (2.4) открытый текст «БАГАЖ» будет преобразован в шифротекст «ДГЖГЙ».

Дешифрование закрытого текста, зашифрованного методом Цезаря согласно (2.3), осуществляется по формуле

P=C-K (mod M)

(2.5)

Шифрование методами перестановки

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

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

Метод простой перестановки

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

Пример. Зашифруем открытый текст «ПРИЕЗЖАЮДНЕМ» методом перестановки с ключом К=3142.

П	Р	И	Е	З	Ж	А	Ю	Д	Н	Е	М
3	1	4	2	3	1	4	2	3	1	4	2
И	П	Е	Р	А	З	Ю	Ж	Е	Д	М	Н

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

Шифрование методом гаммирования

Под гаммированием понимают наложение на открытые данные по определенному закону гаммы шифра [5].

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

Общая схема шифрования методом гаммирования представлена на рис. 2.3.

Рис. 2.3. Схема шифрования методом гаммирования

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

Перед шифрованием открытые данные обычно разбивают на блоки одинаковой длины, например по 64 бита. Гамма шифра также вырабатывается в виде последовательности блоков той же длины.

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

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

2.4. Компьютерные вирусы

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

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

Пример. Одну из самых популярных антивирусных программ AIDSTESTавтор (Д. Лозинский) обновляет иногда дважды в неделю. Известная антивирусная программа AVPлаборатории Касперского содержит в своей базе данные о нескольких десятках тысяч вирусах, вылечиваемых программой.

Вирусы бывают следующих основных видов:

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

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

Вирусы могут проникать в сеть, например:

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

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

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

3. Модели решения функциональных и вычислительных задач

3.1. Модели и моделирование

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

По уровню, "глубине" моделирования модели бывают:

эмпирические - на основе эмпирических фактов (опытов);
теоретические - на основе математических описаний;
смешанные, полуэмпирические - на основе эмпирических зависимостей и математических описаний.

Проблема моделирования состоит из трех задач:

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

Схема построения модели М системы S с входными сигналами X и выходными сигналами Y изображена на рис. 3.1.

Рис. 3.1. Схема построения модели

Если на вход М поступают сигналы из X и на выходе появляются сигналы Y, то задан закон (правило) f функционирования модели / системы.

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

Классификацию моделей проводят по различным критериям.

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

Пример. Закон Ньютона F=a*m - это статическая модель движущейся с ускорением a материальной точки массой m. Эта модель не учитывает изменение ускорения от одной точки к другой.

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

Пример. Динамическая модель закона Ньютона будет иметь вид:

F(t)=a(t)*m(t).

Модель дискретная, если она описывает поведение системы только в дискретные моменты времени.

Пример. Если рассматривать только t = 0, 1, 2, …, 10 (сек), то модель St = gt2/2 или числовая последовательность S0 = 0, S1 = g/2, S2 = 2g, S3 = 9g/2, :, S10 = 50g может служить дискретной моделью движения свободно падающего тела.

Модель непрерывная, если она описывает поведение системы для всех моментов времени некоторого промежутка времени.

Пример. Модель S = gt2/2, 0 < t < 100 непрерывна на промежутке времени (0;100).

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

Пример. Пусть модель экономической системы производства товаров двух видов 1 и 2, в количестве x1 и x2 единиц и стоимостью каждой единицы товара a1 и a2 на предприятии описана в виде соотношения:

a1x1 + a2x2 = S,

где S - общая стоимость произведенной предприятием всей продукции (вида 1 и 2). Можно ее использовать в качестве имитационной модели, по которой можно определять (варьировать) общую стоимость S в зависимости от тех или иных значений объемов производимых товаров.

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

Пример. Приведенные выше физические модели - детерминированные. Если в модели S = gt2 / 2, 0 < t < 100 мы учли бы случайный параметр - порыв ветра с силой p при падении тела:

S(p) = g(p) t2 / 2, 0 < t < 100,

то мы получили бы стохастическую модель (уже не свободного!) падения.

Модель функциональная, если она представима в виде системы каких- либо функциональных соотношений.

Модель теоретико-множественная, если она представима с помощью некоторых множеств и отношений принадлежности им и между ними.

Пример. Пусть задано множество X = {Николай, Петр, Николаев, Петров, Елена, Екатерина, Михаил, Татьяна} и отношения: Николай - супруг Елены, Екатерина - супруга Петра, Татьяна - дочь Николая и Елены, Михаил - сын Петра и Екатерины, семьи Михаила и Петра дружат друг с другом. Тогда множество X и множество перечисленных отношений Y могут служить теоретико-множественной моделью двух дружественных семей.

Модель называется логической, если она представима предикатами, логическими функциями.

Например, совокупность логических функций вида:

z = x y x, p = x y

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

Модель игровая, если она описывает, реализует некоторую игровую ситуацию между участниками игры.

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

Cледует помнить, что не все модели могут быть исследованы или реализованы алгоритмически.

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

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

Модель называется графовой, если она представима графом или графами и отношениями между ними.

Модель называется иерархической (древовидной), если представима некоторой иерархической структурой (деревом).

Модель называется сетевой, если она представима некоторой сетевой структурой.

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

Таблица работ при строительстве дома
№	Операция	Время выполнения (дни)	Предшествующие операции	Дуги графа
1	Расчистка участка	1	нет	-
2	Закладка фундамента	4	Расчистка участка (1)	1-2
3	Возведение стен	4	Закладка фундамента (2)	2-3
4	Монтаж электропроводки	3	Возведение стен (3)	3-4
5	Штукатурные работы	4	Монтаж электропроводки (4)	4-5
6	Благоустройство территории	6	Возведение стен (3)	3-6
7	Отделочные работы	4	Штукатурные работы (5)	5-7
8	Настил крыши	5	Возведение стен (3)	3-8

Сетевая модель (сетевой график) строительства дома дана на 3.2.

Рис. 3.2. Сетевой график строительства работ

Две работы, соответствующие дуге 4-5, параллельны, их можно либо заменить одной, представляющей совместную операцию (монтаж электропроводки и настил крыши) с новой операцией длительностью 3+5=8, либо ввести на одной дуге фиктивное событие.

Модель называется языковой, лингвистической, если она представлена некоторым лингвистическим объектом, формализованной языковой системой или структурой.

Модель натурная, если она есть материальная копия объекта моделирования.

Например, глобус - натурная географическая модель земного шара.

Модель геометрическая, графическая, если она представима геометрическими образами и объектами.

3.2. Основные свойства модели и моделирования

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

Как правило, модель включает в себя: объект О, субъект А (не обязательно) , задачу Z, ресурсы B, среду моделирования С.

Модель можно представить формально в виде: М = < O, А, Z, B, C >.

Основные свойства любой модели:

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

Жизненный цикл моделируемой системы:

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

Моделирование – есть метод системного анализа.

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

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

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

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

Моделирование рассматривается, как особая форма эксперимента, эксперимента не над самим оригиналом, т.е. простым или обычным экспериментом, а над копией оригинала. Здесь важен изоморфизм систем оригинальной и модельной.

Изоморфизм - равенство, одинаковость, подобие.

3.3. Классификация видов моделирования

Рис. 3.3. Классификация видов моделирования

При физическом моделировании используется сама система, либо подобная ей в виде макета, например, летательный аппарат в аэродинамической трубе.

Математическое моделирование есть процесс установления соответствия реальной системе S математической модели M и исследование этой модели, позволяющее получить характеристики реальной системы.

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

Аналитическая модель может быть исследована методами:

аналитическими (устанавливаются явные зависимости, получаются, в основном, аналитические решения);
численными (получаются приближенные решения);

Компьютерное математическое моделирование формулируется в виде алгоритма (программы для ЭВМ), что позволяет проводить над моделью вычислительные эксперименты.

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

Статистическое моделирование использует обработку данных о системе с целью получения статистических характеристик системы.

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

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

Экономический эффект при математическом моделировании состоит в том, что затраты на проектирование систем в среднем сокращаются в 50 раз.

3.4. Компьютерное моделирование

Компьютерное моделирование от постановки задачи до получения результатов проходит следующие этапы:

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

формулировка задачи;
определение цели и приоритетов моделирования;
сбор информации о системе, объекте моделирования;
описание данных (их структуры, диапазона, источника и т.д.).

Пред модельный анализ:

анализ существующих аналогов и подсистем;
анализ технических средств моделирования:
ЭВМ;
периферии.
анализ программного обеспечения:
языков программирования;
пакетов прикладных программ;
инструментальных сред.
анализ математического обеспечения:
моделей;
методов;
алгоритмов.

Анализ задачи (модели):

разработка структур данных;
разработка входных и выходных спецификаций, форм представления

данных;

проектирование структуры и состава модели (подмоделей).

Исследование модели:

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

чувствительности модели.

Программирование (проектирование программы):

выбор метода тестирования и тестов (контрольных примеров);
кодирование на языке программирования (написание команд);
комментирование программы.

Тестирование и отладка:

синтаксическая отладка;
семантическая отладка (отладка логической структуры);
тестовые расчеты, анализ результатов тестирования;
оптимизация программы;

Оценка моделирования:

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

Сопровождение:

анализ применения, периодичности использования, количества

пользователей, типа использования (диалоговый, автономный и др.),

анализ отказов во время использования модели;

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

режимов моделирования, в том числе и под модифицированную среду;

нахождение, исправление скрытых ошибок в программе.

Использование модели.

3.5. Функции алгебры логики

Рассмотрим множество векторов X = {<x1... xn>}. Будем предполагать, что координаты этих векторов могут принимать значения 0 или 1. Таким образом множество X состоит из 2n векторов. Произведем отображение множества X в множество Y = {0, 1} [6].

Определение. Функцией алгебры логики называется функция, дающая однозначное отображение X в Y.

Определение. Если две функции алгебры логики f1(x1... xn) и

f2( x1... xn) принимают на всех наборах значений аргументов одинаковые значения, то их называют равными.

Теорема 1. Число различных функций алгебры логики, зависящих от n аргументов конечно и равно 2n.

Приведем иллюстрацию сказанного на основе анализа таблицы:

x1, x2,..., xn	f(x1, x2,..., xn )
00...00	a1
00...01	a2
00...10	a3
...	...
11...11	a2n

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

Рассмотрим основные функции, которые играют важную роль в построении функций алгебры логики и ее приложениях:

1. f = X.

2. f = X (отрицание – инверсия).

3. f = 0.

4. f = 1.

5. f = X v Y (логическое сложение или дизъюнкция).

6. f = X  Y (логическое умножение или конъюнкция).

7. f = X  Y ( импликация).

8. f = X  Y (функция Вебба).

9. f = X  Y (стрелка Пирса).

10. f = X | Y (функция Шеффера).

11. f = X  Y (сложение по модулю 2).

Эти одиннадцать функций алгебры логики позволяют строить новые функции, при этом используется два подхода:

подстановка в функцию новой функции вместо аргументов;
переобозначение аргументов.

Пример. Представить в виде таблицы функцию

f (X1,X2 ) = { ( X1  X2 ) v (X1  X2 ) } = X1 | X2.

Решение.

X1	X2	X1  X2	X1  X2	f
0	0	1	0	1
0	1	0	1	1
1	0	0	1	1
1	1	0	0	0

Пример. Показать, что X1  X2 = X1 v X2 на основе построения и сравнения функций по таблицам истинности.

Решение.

X1	X2	X1  X2	X1	X1 v X2
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	1	0	1

Рассмотрим свойства конъюнкции, дизъюнкции и отрицания.

Коммутативность

x1 & x2 = x2 & x1.

x1 v x2 = x2 v x1.

Ассоциативность

x1 v (x2 v x3) = (x1 v x2) v x3.

x1 & (x2 & x3) = (x1 & x2) & x3.

Дистрибутивность

x1 & (x2 v x3) = (x1 & x2) v ( x1 & x3 ).

x1 v (x2 & x3) = (x1 v x2) & ( x1 v x3 ).

Отметим также важные соотношения:

X v X = X, X & X = X, X v 1 = 1, X & 1 = X,

X v 0 = X, X & 0 = 0, X v X = 1, X & X = 0.

Положим x  = { X , если  = 1; X , если  = 0 } .

Утверждение. Любая функция алгебры логики кроме 0 может быть представлена в форме

f(x 1...xn) =  x1  & x2 ... & xn  (3.1)

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

Определение. Представление функции алгебры логики в виде (3.1) называется ДСНФ - дизъюнктивной совершенной нормальной формой.

Для построения ДСНФ необходимо выполнить следующие шаги:

выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 1;

выписать соответствующие этим наборам конъюнкции, при этом, если аргумент xi входит в данный набор как 1, то он записывается без изменений, если же как 0 , то берется ;

все полученные конъюнкции объединяются под знаком дизъюнкции.

3.6. Булева алгебра. Функциональная полнота

Определение. Алгеброй над множеством логических функций с двумя бинарными операциями, обозначаемыми как логическое умножение & и логическое сложение v и одной унарной операцией ( отрицанием )

называется булевой алгеброй. Будем обозначать ее символом B.

Рассмотрим свойства булевой алгебры.

Замкнутость

для  A и B  B

A v B  B

A & B  B

Коммутативность

A & B = B & A

A v B = B v A

3. Ассоциативность

A v ( B v C) = (A v B) v C

Дистрибутивность

A & ( B v C) = (A & B) v (A & C)

A v ( B & C) = (A v B) & (A v C)

Идемпотентность

A v A = A & A = A.

Булева алгебра содержит элементы 0,1 , такие что для всякого

элемента A  B справедливо:

A v 0 = A, A v 1 = 1

A & 0 = 0, A & 1 = A.

7. Для каждого элемента A  B существует элемент , такой что

A v =1

A & =0.

8. Закон поглощения

A & (A v B) = A v A & B = A.

9. Закон Де Моргана

3.7. Минимизация функций алгебры логики

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

Работа конечного автомата может быть полностью описана с помощью следующей системы функций алгебры логики [7]:

y1= f1 (x1 ... xn )

y2= f2 (x1 ... xn )

...

ym= fm (x1 ... xn )

Здесь Pi = ( X1, X2, ...,Xn ); Qj = ( y1, y2, ...,ym ) - соответственно входное и выходное слово. Работа автомата может быть задана либо в виде конечных таблиц, либо в виде аналитической записи функций fi .

Проблема полноты системы функций эквивалентна проблеме выбора стандартного набора элементов, из которого будет строиться автомат, при этом все функции fi должны быть выражены через базисные функции. Уменьшение числа функций в базисе приводит к уменьшению стандартных элементов, на которых строится схема, однако, при этом увеличивается общее число элементов схемы. Возникает задача о “простейшем” представлении логических функций через систему базисных функций. Для этого используют методы минимизации:

- метод вынесения за скобки;

- метод неопределенных коэффициентов;

- метод с использованием карт Карно;

- метод Мак - Класки;

- метод Блэка.

Рассмотрим метод минимизации совершенной дизъюнктивной нормальной формы (СДНФ) с помощью карт Карно. Карта Карно - это диаграмма, состоящая из 2n квадратов, где n - число переменных. Клетка карты - одна из возможных конъюнкций, входящих в СДНФ. Минимизация на основе карт Карно осуществляется путем локализации на карте прямоугольных областей из числа клеток кратного 2.

Для работы с картой необходимо по таблице истинности составить СДНФ, затем для каждой элементарной конъюнкции проставить 1 в соответствующие клетки карты. Затем единицы объединяются таким образом, чтобы минимизировалось число логических сложений, умножений или отрицаний, что важно для экономного конструирования ЭВМ.

Рассмотрим карты Карно.

Для двух переменных: Для трех переменных:

a a

Для четырех переменных:

c d

Пример. Для логической функции заданной таблицей

x1	x2	x3	f
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	1
0	1	1	1

построить карту Карно и на ее основе минимизировать функцию.

Решение. Построим карту согласно описанным выше правилам.

1 1 f = x1 v x2 & x3

x2 1 1 1

Рассмотрим пример представления простейшей функции картой Карно

c 1 1

c 1 1 d

f = b

1 1 d

1 1

Рассмотрим построение логической схемы для функции вида:

f1 = V2 & V4 v V3 & V1 & V2 v V3 & V4 & V1.

& & & & &

& &

4. Программные средства реализации информационных процессов

Представление вычислительного устройства схемой, состоящей из логических элементов наиболее исследованный вид структурной реализации вычислительных и информационных процессов. Другой вид - реализация программой. Программа вычисляет (реализует) логические функции f(x1, ..., xn) = y, если для любого двоичного набора    1,..., n ) при начальном состоянии элементов памяти x1 = 1 , x2 = 2 ,..., xn = n программа через конечное число шагов останавливается и в ячейке y лежит величина f(1, 2, ..., n ). Если под сложностью схемы, реализующей автомат, обычно понимается число элементов схемы, то под сложностью программ можно понимать:

число команд в тексте программы;

объем промежуточной памяти;

время вычисления программы, которое характеризуется двумя величинами:

Средним временем
Максимальным временем ,

где сумма и максимум берутся по всем 2 наборам, а p - время работы программы на одном наборе .

Рассмотрим 2 типа программ: операторные и бинарные. Операторная программа не содержит условных переходов, порядок ее команд в точности соответствует нумерации элементов в схеме, а система команд соответствует базису схемы. Элементы схемы нумеруются числами 1,..., n таким образом, чтобы на любом пути от входа к выходу номера элементов возрастали. При этом номер 1 получит один из входных элементов, а номер n - выходной элемент.

Поскольку операторная программа не содержит условных переходов, то время ее выполнения на любом наборе одно и то же, отсюда t max = t ср.

Бинарные программы это программы, состоящие из команд типа y =  ;  = {0, 1} и условных переходов.

Замечание. Бинарные программы обладают двумя достоинствами по сравнению с операторными:

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

Пример. Составить для функции f = ( x1 v x2 ) бинарную и операторную программы.

Решение. Воспользуемся языком С++, будем иметь код:

void main()

{

bool f=0, x1,x2 ; // описание типа переменных

cout<<” Enter x1,x2\n”; // вывод на экран текста

cin>> x1>>x2; // ввод переменных

switch (x1) // оператор выбора

{

case 0: switch(x2)

{

case 0: f=1;

case 1: f=0;

}

case 1: f=1;

}

default: f=0;

cout>> f ;

}

Операторная программа пишется в базисе {&,}. Для этого перепишем заданную функцию, используя формулы де Моргана.

void main()

{

bool f, x1,x2 ; // описание типа переменных

bool a,b;

cout<<” Enter x1,x2\n”; // вывод на экран текста

cin>> x1>>x2; // ввод переменных

a= 1-x1; {}

b= a  x2; {}

b= 1 - b; {}

f=b;

cout<<f;

}

5. Технические средства реализации информационных процессов

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

Логический вентиль (вентиль) – это своего рода элемент, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана, открывая или закрывая путь сигналам.

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

Логические функции отрицания, дизъюнкции и конъюнкции реализуют логические схемы, называемые инвертором, дизъюнктором и конъюнктором.

Логическая функция "инверсия", или отрицание, реализуется логической схемой (вентилем), называемой инвертор.

Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение.

Аналогично, если предположить, что на входе инвертора будет напряжение 1 ("истина"), то на выходе инвертора будет сниматься 0 вольт.

Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.1), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0.

Рис. 5.1. Электрический аналог схемы инвертора

Дизъюнкцию реализует логическое устройство (вентиль) называемое дизьюнктор

Дизъюнктор условно изображается схематически электрической цепью вида (рис. 5.2)

Рис. 5.2. Электрический аналог схемы дизъюнктора

Конъюнкцию реализует логическая схема (вентиль), называемая конъюнктором.

Конъюнктор можно условно изобразить схематически электрической цепью вида (рис. 5.3):

Рис. 5.3. Электрический аналог схемы конъюнктора

Схематически инвертор, дизъюнктор и конъюнктор на логических схемах различных устройств можно изображать условно следующим образом (рис. 5.4 – 5.6 ). Есть и другие общепринятые формы условных обозначений.
Условные обозначения вентилей:

Рис. 5.4.Схема инвертора

Рис. 5.5. Схема конъюнктора

Рис. 5.6. Схема дизъюнктора

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

Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в следующий разряд можно изобразить таблицей вида:

x	y	z	p
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида

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

Рис. 5.7. Схема одноразрядного сумматора

Пример. "Черным ящиком" называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода (значениям входных и выходных сигналов). В "черном ящике" находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри "черного ящика". Определим логическую функцию внутри "черного ящика" (рис. 5.8), если операции выполняются с логическими константами для входных последовательностей (поразрядно).

Рис. 5.8. Схема "черного ящика 1"

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

Действительно, в результате "поразрядного" сравнения сигналов (последовательностей значений "истина", "ложь") получаем следующие выражения (последовательности логических констант):

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

Эту задачу решают с помощью методов теоретической информатики (методов булевой алгебры).

Пример. Построим схему для логической функции

Схема, построенная для этой логической функции, приведена на рис. 5.9.

Рис. 5.9. Схема логической функции

Пример. Определим логическую функцию , реализуемую логической схемой вида (рис. 5.10)

Рис. 5.10. Схема искомой функции u

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

6. Алгоритмизация и программирование

"Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики.

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

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

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

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

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

Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, различные языки программирования и др.

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

Рис. 6.1. Структура алгоритмического обеспечения

Основные формы использования алгоритмов – автономное, библиотечное, пакетное.

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

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

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

В качестве языка описания алгоритмов будет использоваться далее язык программирования С++.

Порядок выполнения операций (старшинство операций – по убыванию) в языке С++:

Вычисление выражений в скобках;
Вычисление стандартных функций;
Умножение и деление (обозначаются "*" и "/");
Сложение и вычитание (обозначаются "+" и "–").

Рассмотрим базовые простые команды языка С++ [8-9].

Команда описания главной функции:

< тип > main ()

{

…

}

2. Команда описания неглавной функции:

< тип > <имя функции > ( < передаваемые параметры>)

{

…

}

Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:

cin>>вводимый параметр;

Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:

cout<<выводимый параметр;

Присваивание – команда изменения текущего значения переменной вида:

<идентификатор> = <выражение>;

где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак "=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.

Символ начала блока {.
Символ конца блока }.
Команда вставки комментариев в текст алгоритма имеет вид:

/* комментарий в несколько строк */

// комментарий в одну строку

Комментировать можно любой объект программы. Обычно комментируют переменную, структуру данных, команду, группу команд.

Различают три базовые алгоритмические структуры: следование, ветвление, повторение.

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

<команда – предшественник>;

<команда – преемник>.

Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, кроме этого она включает 2 типа команд - команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Условный оператор имеет вид

if <условие> <команда, выполняемая при выполнении условия>;

else <команда, выполняемая при невыполнении условия>;

Пример. Команда вида

if (х>y) ( если текущее значение х больше текущего значения y )

у = х ;

else x= y; (иначе x=y)

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

Структура повторения типа "пока (while)" записывается в виде:

while <условие продолжения повторения>

{

<повторяемая команда 1>;

<повторяемая команда 2>;

. . .

<повторяемая команда N>;

}

Следующим оператором цикла в языке С++ является оператор for

for(<присваивание начального значения счетчику цикла>; <условие проверки выхода из цикла>; <изменение счетчика цикла>)

{

< операторы цикла>

}

Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.

Пример. Пусть необходимо найти сумму всех нечетных элементов натурального ряда чисел до тех пор, пока эта сумма не превысит значение n.

Функция (программа) имеет вид:

void main()

{

int i=1,n,summa=0;

cout<<"Input n= \n";

cin>>n;

while (summa<=n)

{

summa=summa+i;

i++;

}

cout<<" Summa = "<<summa;

}

Пример. Найти наименьшее общее кратное любых двух целых чисел m, n, найти наибольший их делитель. Программа, содержащая все необходимые подключения к операционной системе Microsoft Visual Studio 2008 C++, будет иметь вид:

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main()

{

int n,m,max,min,nok,nod=1,i;

cout<<"Enter n = ";

cin>>n;

cout<<"\n Enter m = ";

cin>>m;

max=n>m?n:m; // выделение наибольшего числа

min=n<m?n:m; // выделение наименьшего числа

// Поиск НОД

for(i=1;i<=min;i++)

// сравнение остатков от деления на ноль

if((m%i==0)&&(n%i==0))nod=i;

cout<<" \n NOD = "<<nod<<"\n";

// Поиск НОK

for(i=max;i<=m*n;i++)

// сравнение на ноль остатков от деления

if((i%m==0)&&(i%n==0))

{

nok=i;

break; // оператор выхода из цикла

}

cout<<" \n NOK = "<<nok<<"\n";

_getch(); /* функция не закрытия экрана после окончания

программы */

return 0; // оператор возврата в вызывающую программу

}

Рассмотрим примеры алгоритмизации (программирования) задач на языке C++.

Пример. Составим алгоритм и программу вычисления факториала заданного натурального числа n, то есть произведения n! = 1 • 2 • 3 • … • (n – 1)•n c использованием рекуррентной формулы n! = (n – 1)! • n.

Приведем алгоритм решения:

1. Инициализация: n, i=1, fact = 1.

2. fact=fact*i

3. i=i+1

4. Если i <= n переход к п. 2.

5. Печать fact.

6.Конец алгоритма.

Рис. 6.2. Блок – схема алгоритма

Алгоритм, представленный программным кодом имеет вид:

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main()

{

int n,i=1,fact=1;

cout<<"Enter n = ";

cin>>n;

for(i=1;i<=n;i++) fact=fact*i;

cout<<" \n n! = "<<fact<<"\n";

_getch();

return 0;

}

6.2. Данные, типы данных, структуры и обработка

Любая актуализация информации опирается на данные.

Данные– это некоторые сообщения, слова в некотором заданном алфавите.

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

Тип данных характеризует область определения значений данных.

Задаются типы данных простым перечислением значений типа, например как в простых типах данных, либо объединением (структурированием) ранее определенных типов – структурированные типы данных.

Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением:

специальность = (филолог, историк, математик, медик);

студент = (Петров, Николаев, Семенов, Иванова, Петрова);

вуз = (МГУ, РГУ, МГПИ).

Значением типа "студент" может быть Петров.

Пример. Опишем структурированный тип данных "специальность_студента":

специальность_студента=(специальность, студент).

Значением типа "специальность_студента" может быть пара, например, (историк, Семенов).

Для обозначения текущих значений данных используются константы – числовые, текстовые, логические.

Часто в зависимости от задачи рассматривают данные, которые имеют не только "линейную" (как было рассмотрено выше), но и иерархическую структуру.

Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники".

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

Пример. В языке С++ для описания типа данных используются служебные слова: int, float, char, string, bool и др.

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

Пример. Для целого и вещественного типов данных используют операции "=", "+", "–", "*", "/", "<", ">", "<=", ">=".

Для символьного типа данных используют операции: "=", "!=", "<", ">", "<=", ">=".

Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся в соответствии с таблицей ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными).

Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: char, string.

Текстовые (символьные) константы обычно заключают в апострофы.

Пример. Составить программу на языке С++ проверки строки символов на симметрию.

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main()

{

char chislo[50];

int i,m=0,j=0,k;

cout<<"enter number \n";

cin>>chislo;

k=strlen(chislo)/2;

for(i=strlen(chislo)-1;i!=k;i--)

{

if(chislo[i]==chislo[j]) m++; // одноразовое совпадение

j++;

}

if(m==k) printf("symmetry exists");

else cout<<"symmetry does not exist";

getch();

return 0;

}

7. Архитектура ЭВМ. Локальные и глобальные сети.

7.1. Архитектура ЭВМ

Компьютер можно рассматривать как совокупность взаимодействующих простых устройств (конечных автоматов). Рассмотрим такую структуру подробнее.

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

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

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

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

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

Джон фон Нейман предложил ряд принципов, которые легли в основу классической архитектуры компьютера:

Память состоит из однородных ячеек памяти с адресами.
Программа состоит из последовательных команд.
Хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде.
Команды выполняются последовательно, данные извлекаются в соответствии с командами.
Процессор – имеет централизованное управление и доступ к памяти.

Структура ЭВМ фон Неймановской архитектуры приведена на 7.1.

Рис. 7.1. Структура ЭВМ фон Неймановской архитектуры

Арифметико-логическое устройство(АЛУ) выполняет арифметические, логические операции.

Пример. Команды АЛУ – просты: "сравнить два числа", "переслать число", "взять дизъюнкцию" и др.

Устройство управления(УУ) организует работу ЭВМ, в частности это устройство извлекает очередную команду из памяти, расшифровывает команду, выбирает из памяти операнды к расшифрованной команде и передает их АЛУ для выполнения расшифрованной операции, а после выполнения пересылает результат для хранения в память. При этом УУ реагирует на нормальный или аварийный ход выполнения операции.

Совокупность АЛУ и УУ, информационно-управляющих линий называется процессором компьютера (его структура приведена на рис. 10.3; жирная линия – информационное взаимодействие, другая – управляющее).

Рис. 7.2. Структура процессора

Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода.

Пример. Устройствами ввода являются, например, клавиатура, мышь, дисплей, видео камера. Устройствами вывода — дисплей, принтер.

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

Ядро персонального компьютера – системная (материнская плата), на которой размещаются: микропроцессор, микропроцессорная память, интерфейсная система микропроцессора для сопряжения и связи с другими устройствами, генератор тактовых импульсов, контроллеры устройств (схем), интегрированных в материнскую плату, микросхемы ОЗУ и ПЗУ и др.

Другими важными устройствами персонального компьютера являются:

дисковод;
CD-ROM (устройство только для чтения компакт-дисков) или CD-RW (чтение и перезапись);
монитор (дисплей);
видеокарта (видеоадаптер) для обеспечения связи системного блока и монитора;
клавиатура;
принтер;
сканер;
манипулятор-мышь;
звуковая карта (адаптер);
звуковые колонки;
модем и др.

Классификацию компьютеров проводят по быстродействию, технологии использования и др.

Необходимо соблюдать простые санитарно-гигиенические и эргономические правила работы на компьютере, в компьютерном зале:

работа с компьютером не более 4-х часов подряд с 10-минутными перерывами после каждого часа интенсивной работы или после 2-х часов менее интенсивной работы;
расстояние от глаз до поверхности экрана – не менее 0,6 м;
перемещаемость клавиатуры относительно экрана в пределах 0,5-1,0 м;
преимущественно желтый, зеленый, серый или светло-голубой фон дисплея;
температура воздуха в помещении – 15-25 градусов по Цельсию;
относительная влажность помещения – 45-75%;
наличие свободной площади рабочего стола не менее 0,3x1,0 м;
размер экрана по диагонали – не меньше 17 дюймов;
разрешение экрана – не менее 800x600 и др.

7.2. Cеть передачи данных

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

Существуют следующие виды сетей передачи данных:

Телефонные сети — сети, в которых оконечными устройствами являются простые преобразователи сигнала между электрическим и видимым/слышимым.

Компьютерные сети — сети, оконечными устройствами которых являются компьютеры.

По принципу коммутации сети делятся на:

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

7.3. Аппаратные средства сети

Се́рвер (англ. server от to serve — служить) — аппаратное обеспечение, выделенное и/или специализированное для выполнения на нем сервисного программного обеспечения (в том числе серверов тех или иных задач).

На сервере хранится база данных. Сервер по сути является файл-сервером и предоставляет общий доступ к единой БД.

Сервер это выделенный компьютер.

Рис. 7.3. Вид сервера

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

Некоторые сервисные задачи могут выполняться на рабочей станции параллельно с работой пользователя. Такую рабочую станцию условно называют невыделенным сервером.

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

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

Маршрутиза́тор ( ро́утер) — сетевое устройство, пересылающее пакеты данных между различными сегментами сети и принимающее решения на основании информации о топологии сети и определённых правил, заданных администратором.

Маршрутизаторы делятся на программные и аппаратные.

Рис. 7.4. Вид маршрутизатора, используемого на магистральных каналах

Принцип работы

Рис. 7.5. Avaya Маршрутизатор основной (ERS-8600)

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

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

Таблица маршрутизации

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

192.168.64.0/16 [110/49] via 192.168.1.2, 00:34:34, FastEthernet0/0.1

где 192.168.64.0/16 — сеть назначения,

110/- административное расстояние

/49 — метрика маршрута,

192.168.1.2 — адрес следующего маршрутизатора, которому следует

передавать пакеты для сети 192.168.64.0/16,

00:34:34 — время, в течение которого был известен этот маршрут,

FastEthernet0/0.1 — интерфейс маршрутизатора, через который можно

достичь «соседа» 192.168.1.2.

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

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

Коммута́ция — процесс соединения абонентов коммуникационной сети через транзитные узлы.

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

Каждый абонент соединен с коммутаторами индивидуальной линией связи, закрепленной за этим абонентом. Линии связи, протянутые между коммутаторами разделяются несколькими абонентами, то есть используются совместно.

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

В настоящее время коммутаторы используются для прямого подключения к конечным станциям.

Широкое применение коммутаторов значительно повысило эффективность использования сети за счет равномерного распределения полосы пропускания между пользователями и приложениями.

Существует четыре принципиально различные схемы коммутации абонентов в сетях:

Коммутация каналов— организация составного канала через несколько транзитных узлов из нескольких последовательно «соединённых» каналов на время передачи сообщения (оперативная коммутация) или на более длительный срок — время коммутации определяется административно.

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

Коммутация пакетов — разбиение сообщения на «пакеты», которые передаются отдельно. Разница между сообщением и пакетом: размер пакета ограничен технически, сообщения — логически. При этом если маршрут движения пакетов между узлами определён заранее, говорят о виртуальном канале (с установлением соединения).

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

Сетевой концентратор— сетевое устройство, предназначенное для объединения нескольких устройств Ethernet пакетной технологии передачи данных преимущественно локальных компьютерных сетей в общий сегмент сети. Устройства подключаются при помощи витой пары, коаксиального кабеля или оптоволокна.

В настоящее время хабы почти не выпускаются — им на смену пришли сетевые коммутаторы (свитчи), выделяющие каждое подключённое устройство в отдельный сегмент. Сетевые коммутаторы ошибочно называют «интеллектуальными концентраторами».

Рис. 7.6. 4-портовый сетевой концентратор

Мост, сетевой мост - сетевое устройство, предназначенное для объединения сегментов (подсети) компьютерной сети разных топологий и архитектур.

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

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

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

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

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

Некоторые сетевые экраны также позволяют осуществлять трансляцию адресов — динамическую замену внутрисетевых (серых) адресов или портов на внешние, используемые за пределами ЛВС.

Рис. 7.7. Иллюстрация, показывающая расположение файрволла в сети.

7.4. Локальная вычислительная сеть

Локальная вычислительная сеть — компьютерная сеть, покрывающая обычно относительно небольшую территорию или небольшую группу зданий (дом, офис, фирму, институт). Также существуют локальные сети, узлы которых разнесены географически на расстояния более 12 500 км (космические станции и орбитальные центры). Несмотря на такие расстояния, подобные сети всё равно относят к локальным.

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

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

Компьютеры могут соединяться между собой, используя различные среды доступа: медные проводники (витая пара), оптические проводники (оптические кабели) и через радиоканал (беспроводные технологии). Проводные связи устанавливаются через Ethernet, беспроводные — через Wi-Fi, Bluetooth, GPRS и прочие средства. Отдельная локальная вычислительная сеть может иметь шлюзы с другими локальными сетями, а также быть частью глобальной вычислительной сети (например, Интернет) или иметь подключение к ней.

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

Иногда в локальной сети организуются рабочие группы — формальное объединение нескольких компьютеров в группу с единым названием.

Сетевой администратор — человек, ответственный за работу локальной сети или её части. В его обязанности входит обеспечение и контроль физической связи, настройка активного оборудования, настройка общего доступа и предопределённого круга программ, обеспечивающих стабильную работу сети.

Рис. 7.8. Приметрая архитектура ЛВС

Корпоративная сеть передачи данных сети предназначена для организации доступа к центральным информационным ресурсам, размещенным в головном офисе кампании. На рисунке представлена структурная схема предлагаемого технического решения. Для организации обмена данными между удаленными офисами используется сеть Интернет. В случае обмена данными через сеть Интернет необходимо обеспечить технические мероприятия по защите информации, передаваемой по каналам публичной сети. Например, предполагается использование тоннельных протоколов c организацией на основе IPSEC (протоколы шифрования). Центральный офис подключается к сети Интернет с использованием маршрутизатора.

Задачи, выполняемые маршрутизатором:

1. Организация обмена информацией между офисами.

2. Организация базовой безопасности.

3. Трансляция IP - адресов.

Непосредственно к маршрутизатору подключается устройство межсетевой экранирования (МСЭ).

Задачи, выполняемые данным устройством:

1. Фильтрация трафика в соответствии с принятой в кампании политикой безопасности.

2. Предотвращение внешних угроз, поступающих из сети Интернет, при помощи использования систем предотвращения вторжения.

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

Коммутатор предназначен для подключения рабочих станций пользователей к локальной вычислительной сети (ЛВС).

К портам коммутатора подключаются рабочие места пользователей и АРМ администратора.

Функциональные требования к межсетевым экранам должны охватывать следующие сферы:

фильтрация на сетевом уровне;
фильтрация на прикладном уровне;
настройка правил фильтрации и администрирование;
средства сетевой аутентификации;
ведение журналов и учет.

7.5. Топология сети

Сетевая тополо́гия — способ описания конфигурации сети, схема расположения и соединения сетевых устройств.

Сетевая топология может быть:

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

Существует множество способов соединения сетевых устройств. Выделяют 3 базовых топологии:

Шина.
Кольцо.
Звезда.

И дополнительные (производные):

Двойное кольцо.
Решётка.
Дерево и др.

Рис. 7.8. Топология сети:

A — линия; B — решетка; C — звезда; D — кольцо; E — шина; F — дерево.

7.6. Глобальная вычислительная сеть

Глобальная компьютерная сеть, ГКС — компьютерная сеть, охватывающая большие территории и включающая в себя большое число компьютеров.

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

Некоторые ГКС построены исключительно для частных организаций, другие являются средством коммуникации корпоративных ЛВС с сетью Интернет или посредством Интернет с удалёнными сетями, входящими в состав корпоративных. Чаще всего ГКС опирается на выделенные линии, на одном конце которых маршрутизатор подключается к ЛВС, а на другом концентратор связывается с остальными частями ГКС.

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

Отличие глобальной сети от локальной

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

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

7.7. Сетевая модель OSI

Сетевая модель OSI — базовая эталонная модель взаимодействия открытых систем — абстрактная сетевая модель для коммуникаций и разработки сетевых протоколов. Предлагает взгляд на компьютерную сеть с точки зрения измерений. Каждое измерение обслуживает свою часть процесса взаимодействия. Благодаря такой структуре совместная работа сетевого оборудования и программного обеспечения становится гораздо проще и прозрачнее.

В настоящее время основным используемым стеком протоколов является TCP/IP.

Модель OSI
Тип данных	Уровень (layer)	Функции
Данные	7. Прикладной (application)	Доступ к сетевым службам
	6. Представления (presentation)	Представление и кодирование данных
	5. Сеансовый (session)	Управление сеансом связи
Сегменты	4. Транспортный (transport)	Прямая связь между конечными пунктами и надежность
Пакеты	3. Сетевой (network)	Определение маршрута и логическая адресация
Кадры	2. Канальный (data link)	Физическая адресация
Биты	1. Физический (physical)	Работа со средой передачи, сигналами и двоичными данными

Рис. 7.9. Сетевая модель OSI.

7.8. Стек протоколов TCP / IP

Стек протоколов TCP/IP (англ. Transmission Control Protocol/Internet Protocol — протокол управления передачей) — набор сетевых протоколов разных уровней модели сетевого взаимодействия , используемых в сетях. Протоколы работают друг с другом в стеке (англ. stack, стопка) — это означает, что протокол, располагающийся на уровне выше, работает «поверх» нижнего, используя механизмы инкапсуляции. Например, протокол TCP работает поверх протокола IP.

Стек протоколов TCP/IP основан на модели сетевого взаимодействия и включает в себя протоколы четырёх уровней:

прикладного (application),
транспортного (transport),
сетевого (network),
канального (data link).

Протоколы этих уровней полностью реализуют функциональные возможности модели OSI. На стеке протоколов TCP/IP построено всё взаимодействие пользователей в IP-сетях. Стек является независимым от физической среды передачи данных.

Уровни стека TCP/IP

Рассмотрим как традиционно протоколы TCP/IP вписываются в модель OSI:

Распределение протоколов модели TCP/IP по уровням модели OSI
7	Прикладной	напр., HTTP, SMTP, SNMP, FTP, Telnet, SSH, SCP, SMB, NFS, RTSP, BGP
6	Представления	напр., XDR, AFP, TLS, SSL
5	Сеансовый	напр., ISO 8327 / CCITT X.225, RPC, NetBIOS, PPTP, L2TP, ASP
4	Транспортный	напр., TCP, UDP, SCTP, SPX, RTP, ATP, DCCP, GRE
3	Сетевой	напр., IP, PPP, ICMP, IGMP, CLNP, OSPF, RIP, IPX, DDP, ARP, RARP
2	Канальный	напр., Ethernet, Token ring, HDLC, X.25, Frame relay, ISDN, ATM, MPLS
1	Физический	напр., электрические провода, радиосвязь, волоконно-оптические провода, Wi-Fi

Обычно в стеке TCP/IP верхние 3 уровня : прикладной, представительский и сеансовый модели OSI объединяют в один прикладной. Поскольку в таком стеке не предусматривается унифицированный протокол передачи данных, функции по определению типа данных передаются приложению. Упрощенно интерпретацию стека TCP/IP можно представить так:

Распределение протоколов по уровням модели TCP/IP
5	Прикладной «7 уровень»	напр., HTTP, RTP, FTP, DNS (RIP, работающий поверх UDP, и BGP, работающий поверх TCP, являются частью сетевого уровня)
4	Транспортный	напр., TCP, UDP, SCTP, DCCP (протоколы маршрутизации, подобные OSPF, что работают поверх IP, являются частью сетевого уровня)
3	Сетевой	Для TCP/IP это IP (IP) (вспомогательные протоколы, вроде ICMP и IGMP, работают поверх IP, но тоже относятся к сетевому уровню; протокол ARP является самостоятельным вспомогательным протоколом, работающим поверх физического уровня)
2	Канальный	Ethernet, IEEE 802.11 Wireless Ethernet, SLIP, Token Ring, ATM и MPLS
1	Физический	напр., физическая среда и принципы кодирования информации, T1, E1.

Физический уровень

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

Канальный уровень

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

Примеры протоколов канального уровня — Ethernet, IEEE 802.11 Wireless Ethernet, SLIP, Token Ring, ATM и MPLS.

Сетевой уровень

Сетевой уровень изначально разработан для передачи данных из одной (под)сети в другую.

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

Пакеты сетевого протокола IP могут содержать код, указывающий, какой именно протокол следующего уровня нужно использовать, чтобы извлечь данные из пакета. Это число — уникальный IP - номер протокола.

Транспортный уровень

Протоколы транспортного уровня могут решать проблему доставки сообщений («дошло ли сообщение до адресата?»), а также гарантировать правильную последовательность прихода данных. В стеке TCP/IP транспортные протоколы определяют, для какого именно приложения предназначены эти данные.

Протоколы автоматической маршрутизации логически представляются на этом уровне.

TCP — «гарантированный» транспортный механизм с предварительным установлением соединения, предоставляющий приложению надёжный поток данных, дающий уверенность в безошибочности получаемых данных, перезапрашивающий данные в случае потери и устраняющий дублирование данных. TCP позволяет регулировать нагрузку на сеть, а также уменьшать время ожидания данных при передаче на большие расстояния. Более того, TCP гарантирует, что полученные данные были отправлены точно в такой же последовательности.

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

В протоколах TCP и UDP (семейства TCP/IP) порт — идентифицируемый номером системный ресурс, выделяемый приложению, выполняемому на некотором сетевом хосте, для связи с приложениями, выполняемыми на других сетевых хостах (в том числе c другими приложениями на этом же хосте).

Хост (от англ. host — «хозяин, принимающий гостей») — любое устройство, предоставляющее сервисы формата «клиент-сервер» в режиме сервера по каким-либо интерфейсам и уникально определённое на этих интерфейсах. В более частном случае под хостом могут понимать любой компьютер, сервер, подключённый к локальной или глобальной сети.

Прикладной уровень

На прикладном уровне работает большинство сетевых приложений.

Эти программы имеют свои собственные протоколы обмена информацией, например, FTP (передача файлов), SMTP (электронная почта), SSH (безопасное соединение с удалённой машиной), DNS (преобразование символьных имён в IP-адреса) и многие другие.

В массе своей эти протоколы работают поверх TCP или UDP и привязаны к определённому порту, например:

FTP на TCP-порт 20 (для передачи данных) и 21 (для управляющих команд) и т.д.

Эти порты определены Агентством по выделению имен и уникальных параметров протоколов (IANA).

8. Программное обеспечение

8.1. Классификация и основные характеристики ПО

Любой компьютер состоит из технического обеспечения (hardware) и функционирует, решает задачи с помощью программного обеспечения (software).

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

Приведем структуру ПО:

Базовое программное обеспечение (ПО).
1. Системное ПО - программы обеспечения взаимодействия пользователя и компьютера).
  1. Операционные системы (ОС) - программы ОС (отладчики, загрузчики и т.д.).
2. Программы обеспечения связи с устройствами (драйверы).
3. Инструментальное ПО (программы для массовой разработки других программ).
  1. Трансляторы с языков программирования.
  2. Интерфейсные системы – программы обеспечения дружественного интерфейса.
  3. Проблемно-ориентированные инструментальные системы (САПР, АСУ, АРМ и др.).
Прикладное ПО - программы обеспечения решения прикладных задач пользователя.

Автономные программы (программы, не связываемые с другими из прикладного ПО).
Библиотеки программ (программы, организованные по принципу библиотек книг).
Пакеты прикладных программ, ППП (проблемно-ориентированные прикладные системы).
Интегрированные пакеты прикладных программ - системы, состоящие из связываемых ППП).

Специальное (уникальное) ПО - программы, используемые для решения уникальных проблем).

8.2. Структура технического обеспечения

Структура технического обеспечения приведена ниже и также является условной и классифицирует техническое обеспечение только по назначению.

Приведем эту структуру (некоторые блоки могут интегрироваться в другие, например, видеопамять – в блок микропроцессора).

Базовое техническое обеспечение (ТО):
1. Микропроцессор.
2. Постоянная ("вшитая") память – ПЗУ.
3. Оперативная ("адресуемая пользователем") память – ОЗУ.
4. Регистровая память (аппаратная кэш-память).
5. Видеопамять (часто интегрируется в блоке микропроцессора).
6. Блок питания (энергетический блок).
Периферийное ТО:
1. Устройства ввода (клавиатура, мышь, сканер и др.).
2. Устройства вывода (дисплей, принтер и др.).
3. Устройства (накопители) внешней памяти (СD, оптический накопитель, flash и др.).
4. Устройства согласования устройств в сети (модем и др.).
Специализированное ТО (устройства, используемые для решения уникальных проблем).

Охарактеризуем программное обеспечение (ПО) компьютера (компьютерной системы, сети).

Наиболее сложный и важный элемент ПО – это ОС.

8.3.Состав операционной системы и ее основные функции

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

ОС состоит из двух основных частей – управляющих программ и обрабатывающих программ и включает в себя следующие основные программы:

диспетчер – управляющая программа для координации работы различных устройств ЭВМ, планирования использования и распределения машинного времени, аппаратуры между программами, пересылка программ из ВЗУ в ОЗУ и наоборот, распределение данных в памяти, ввод программ в выделенные участки ОЗУ, управление выполнением задачи, принятие решений в аварийных ситуациях, обнаружение и классификация ошибок и др.;
супервизор – управляющая программа для контроля координации используемых ресурсов и последовательности действий процессора;
отладчик – обрабатывающая программа для отладки программы;
редактор связей – программа для формирования непосредственно выполняемой в памяти программы на машинном языке.

Основными функциями ОС являются:

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

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

Файл – именованный структурированный набор однотипных последовательностей данных, обычно хранимый на внешнем носителе и копируемый для работы с ним по мере надобности в ОЗУ.

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

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

Различают следующие ОС:

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

Инструментальная система – это программная среда.

Пример. Рассмотрим инструментальную среду – графический редактор, который позволяет визуализировать графические объекты двумя основными способами: векторно или растрово.

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

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

В этой матрице записывается информация о яркости и цвете кластера изображения (на один пиксель иногда 1-2 байта и более), а сама матрица может иметь размерность 1024x1024 пикселей и более.

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

Изображение в цвете (рисование в цвете) – это манипуляция пикселями этой матрицы. Графические 3D-редакторы изображений позволяют не только конструировать 3D-объекты, но и перемещать их по задаваемой траектории, то есть осуществлять анимацию. Одной из мощных графических сред является пакет 3D-Studio Max фирмы Autodesk. Кроме этого пакета, широко используются графические пакеты:

Microsoft Visio – для работы с деловой и компьютерной графикой;
AutoCAD – для автоматизации проектно-конструкторских работ;
Adobe Photoshop, CorelDraw, PaintBrush, для работы с растровой графикой.

Проблемно-ориентированные инструментальные системы служат для решения достаточно широкого класса задач некоторой профессиональной, проблемной ориентации:

САПР – системы автоматизации проектирования,
АСУ – автоматизированные системы управления,
АРМ – автоматизированные рабочие места,
СУБД – система, обеспечивающая интерфейс программ пользователя и данных из базы данных,
ЭС – экспертные системы, системы накопления, хранения и актуализации опыта, знаний, умений, навыков (экспертных суждений) экспертов и др.

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

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

Пакет прикладных программ (ППП) состоит из следующих обязательных частей:

Описания, представления класса задач, решаемых с помощью ППП;
Комплекса программ, обеспечивающих построение прикладных программ ППП (технологической цепочки);
Комплекса прикладных программ, обеспечивающих решение задач из предметной области ППП;
Входного языка (языка запросов) ППП;
Базы данных для хранения данных, передача их модулям ППП;
Монитора (управляющая программа) ППП, обеспечивающая ввод задания (запроса), его расшифровку и построение технологической цепочки из модулей ППП для поиска ответа.

Функциональная система интегрированного пакета программ состоит не из модулей (как в ППП), а из ППП.

Пример. Наиболее распространенный интегрированный пакет прикладных программ – MS Office (пакет автоматизации работы в офисе). В его ядро входят следующие пакеты: Word – текстовый редактор, Excel – электронная таблица, Access – СУБД, PowerPoint – система презентации и др.

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

Пример. К такому классу ПО можно отнести программную систему управления кораблем "Шатл".

9. Технология программирования

9.1. Организация данных в ЭВМ

Последовательное распределение

С вычислительной точки зрения простейшим представлением [11] конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти.

 d 

Ячейка памяти	S1	S2	S3	…	Sn-1	Sn
Адреса ячеек памяти	g1	g2	g3		gn-1	gn

g2 = g1 + d

g3 = g1 + 2d

…

gn = g1 + (n-1) d

Таким образом, представляется последовательное распределение данных S1, S2,…, Sn, для каждого элемента которой требуется объем памяти d, gi — адрес ячейки.

Такое представление имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов памяти. Во-вторых, существует простое соотношение между номером элемента i и адресом ячейки, в которой хранится Si: gi = g1 + (i-1) d. Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. В-третьих, оно имеет широкий диапазон и включает в себя представление многомерных массивов.

Последовательное распределение имеет значительный недостаток. Оно становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между Si и Si+1 нового элемента требует сдвига Si+1, … Sn вправо на одну позицию, а исключение соответственно — сдвиг влево.

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

Связанное распределение

Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. Если это требование опустить, то можно выполнять операции включения и исключения без передвижения элементов последовательности. Конечно, необходимо сохранять информацию о способе упорядочения элементов, но можно это делать явным образом. В частности, при связанном распределении данных каждому Si поставлен в соответствие указатель Рi, отмечающий ячейку, в которой записаны Si+1 и Pi+1 (т.е. переход на следующую ячейку последовательности). Существует также указатель P0, который указывает на начальную ячейку последовательности, т.е. на ячейку с содержимым S1 и P1.

(INFO) (LINK)

P0=g1	S1	P1=g2		S2	P2=g3	…	Sn-1	Pn-1 =gn		Sn	Pn=
	g1			g2			g n-1			g n

Рис. 9.1. Представление последовательности в виде связанного списка

Каждый элемент списка состоит из поля INFO (содержащего элемент последовательности) и поля LINK (содержащего адрес следующего элемента)

Здесь каждый узел состоит из двух полей. Под узлом понимается одно или несколько последовательных слов в памяти машины, выступающих как единое целое.  — пустой или нулевой указатель. Рассмотрим более употребляемый способ задания списка.

P0	S1			S2		…	Sn-1			Sn

Рис. 9.2. Способ задания списка

Связанное представление данных облегчает операции включения и исключения элемента, если ячейка Si известна. Для этого лишь необходимо, изменить значение некоторых указателей. Например, чтобы исключить элемент S2 из последовательности, изображенной на рис. 9.3, необходимо положить LINK(g1)=LINK(g2). После этой операции элемента S2 в последовательности больше не будет.

P0	S1			S2			S3		…

Рис. 9.3. Исключение элемента из связанного списка

Чтобы в последовательность (рис. 9.4) включить новый элемент S5 после S1, необходимо воспроизвести новый элемент в некоторой ячейке g5 с INFO(g5) = S5 и LINK(g5) = LINK(g1) и присвоить LINK(g1) g5.

P0	S1			S2			S3		…

S5
g5

Рис. 9.4. Включение элемента в связанный список

Также легко осуществляется сцепление последовательностей и разбиение последовательности на части.

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

С помощью связанного распределения достигается большая гибкость, но идет потеря скорости обращения к данным. При последовательном представлении фиксированное соотношение между i и ячейкой Si позволяет, в частности, иметь быстрый и прямой доступ к любому элементу последовательности. В связанном распределении такого соотношения не существует, и доступ ко всем элементам последовательности, кроме первого, не является прямым и эффективным. Кроме того, при связанном представлении приходится тратить память на указатели Pi.

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

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

9.2. Стеки и очереди

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

В обоих случаях операции включения и исключения производятся только на концах последовательности [11].

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

Правило работы со стеком: «Первым пришел — последним ушел».

Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в автоматизации работы с информационными структурами.

Рис. 9.5. Связь между ячейками в стеке

Рис. 9.6. Связь между ячейками в очереди

9.3. Графы

Конечный граф G = (V, E) состоит из конечного множества вершин V = {V1, V2 … Vm} и конечного множества ребер E = {e1, e2 … en}. Каждому ребру соответствует пара вершин.

Если ребро определяется e = (v, w), то говорят, что оно инцидентно вершинам v и w. Графы бывают ориентированными, если ребра — дуги и не ориентированными в противном случае .

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

Граф называется простым, если он не имеет ни петель, ни параллельных ребер.

Представление графа матрицей смежности

Рис. 9.7. Ориентированный граф и его матрица смежности

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

Матрица весов

Граф, в котором ребру (i, j) сопоставлено число wij, называется взвешенным графом, а число wij называется весом ребра (i, j). В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость, надежность и т.д. Простой взвешенный граф может быть представлен своей матрицей весов W = [wij], где wij есть все ребра, соединяющие вершины i и j. Веса несуществующих ребер обычно полагают равными  или 0 в зависимости от приложений.

Список ребер

Иногда более эффективно представлять ребра графа парами вершин. Это представление можно реализовать двумя массивами g = (g1, g2, …, gm) и h = (h1, h2, …, hm).

Каждый элемент в массиве есть метка вершины, а i-е ребро графа выходит из вершины gi и входит в вершину hi. Например, ориентированный граф (рис. 9.7) будет представляться следующим образом:

g = (1, 2, 2, 2, 2, 3, 3, 4, 5, 5, 5, 7, 7)

h = (6, 1, 3, 4, 6, 4, 5, 5, 3, 6, 7, 1, 6)

При этом легко представимы петли и параллельные ребра.

Связность и расстояние

Говорят, что вершины x и y в графе смежны, если существует ребро, соединяющее их. Говорят, что два ребра смежны, если они имеют общую вершину. Путь — это последовательность смежных ребер (v1, v2), (v2, v3) …, в которой все вершины v1,v2, …, vk — различны, исключая возможно, случай v1 = vk. Записывается путь из v1 в vk как (v1, v2, v3, …, vk). Число ребер в пути называется длиной пути. Расстояние от вершины a до вершины b определяется как длина кратчайшего пути (т.е. пути наименьшей длины) из a в b.

Цикл — это путь, в котором первая и последняя вершины совпадают.

Подграф графа G = (V, E) есть граф, вершины и ребра которого принадлежат G.

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

Процедура при этом такова. На каждом шаге выбирается новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжается до тех пор, пока не будет выбрано |v|–1 ребер, образующих подграф Т, где v — число узлов дерева. Этот процесс известен как жадный алгоритм.

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

Прохождение графа начинается с некоторой произвольной вершины а в заданном графе. Пусть (a, b) — ребро с наименьшим весом, инцидентное a; ребро (a, b) включается в дерево. Затем среди всех ребер, инцидентных либо а, либо b, выбирается ребро с наименьшим весом, и оно включается в частично построенный подграф. В результате в подграф добавляется новая вершина, например c. Повторяя процесс, ищем наименьшее ребро, соединяющее a, b или c с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из G не будут включены в подграф.

Примеры. В основе — граф рис. 9.7.

Жадный алгоритм

6 — начало:

 = 1,7

Алгоритм ближайшего соседа

 = 1,7

Рис. 9.8.

9.4. Деревья

Конечное корневое дерево Т формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m  0 поддеревьев Т1, Т2, …, Тm.

Узлы, не имеющие поддеревьев, называют листьями, остальные узлы называются внутренними узлами.

Рис. 9.9. Дерево с 11 узлами

Узлы D, E, F, H, J, K — листья, А — корень, остальные — внутренние.

Посредством деревьев представляются иерархические структуры, поэтому они являются наиболее важными нелинейными структурами данных.

В описании соотношений между узлами дерева будем использовать терминологию генеалогических деревьев. Т.е. говорим, что в дереве (или поддереве) все узлы, являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Далее корень будем именовать отцом корней его поддеревьев, которые в свою очередь будем называть сыновьями корня. Например, на рис. 9.7 узел А является отцом узлов B, G, I; J и K — сыновья I, а C, E и F — братья и т.д.

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

считаются различными.

Определим лес как упорядоченное множество деревьев.

Важной разновидностью деревьев является класс бинарных деревьев. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого Tl и правого Tr.

Бинарные деревья, вообще говоря, не являются подмножеством множества

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

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

10. Базы данных

10.1. Основные понятия

Базы данных – это совокупность определенным образом организованной информации на какую-либо тему (в рамках предметной области).

Например,

База данных книжного фонда библиотеки;
База данных кадрового состава учреждения;
База данных законодательных актов в области уголовного права;
База данных современных песен.

Базы данных бывают:

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

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

База данных — организованная совокупность данных, предназначенная для длительного хранения во внешней памяти ЭВМ и постоянного применения.

Для хранения БД может использоваться как один компьютер, так и множество взаимосвязанных компьютеров.
Если различные части одной базы данных хранятся на множестве компьютеров, объединенных между собой сетью, то такая БД называется распределенной базой данных.

Существует три типа моделей данных:

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

Для взаимодействия пользователя с базами данных используют системы управления данными (СУБД).

К современным СУБД относятся:

Oracle,
MS Access,
MS SQL Server,
Interbase,
MySQL,
IBM DB2.

Принципы построения систем управления баз данных следуют из требований, которым должна удовлетворять организация баз данных:

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

Рис. 10.1. Схема работы с БД

10.2. Модели данных в СУБД

Иерархическая, сетевая и реляционная модели, их достоинства и недостатки.

Реляционные базы данных

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

Одна запись содержит информацию об одном объекте той реальной системы, модель которой представлена в таблице.

Поля — это различные характеристики (иногда говорят — атрибуты) объекта. Значения полей в одной строчке относятся к одному объекту.
Разные поля отличаются именами.

Распределение данных по таблицам

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

информацию.
* Расчетные поля не включаются в таблицы исходных данных.
* Как правило, таблица имеет ключевое поле (ключ).

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

Разработка структуры таблиц

Выбор типа поля

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

Например, с числовыми величинами можно выполнять арифметические операции, а с символьными и логическими — нельзя.

Структура данных определяет многие атрибуты: языки описания данных, средства запросов, физическую организацию данных, свойства и возможности СУБД. В основе представлений моделей данных лежат: иерархическая – деревья; сетевая – графы; реляционная – таблицы. Существуют всевозможные модели, например на инвертированных списках; семантическая модель, основанная на семантических диаграммах; объектно-ориентированные СУБД.

Сначала стали использовать иерархические даталогические модели. Простота организации, наличие заранее заданных связей между сущностями, сходство с физическими моделями данных позволяли добиваться приемлемой производительности иерархических СУБД на медленных ЭВМ с весьма ограниченными объемами памяти. Но, если данные не имели древовидной структуры, то возникала масса сложностей при построении иерархической модели и желании добиться нужной производительности.

Достоинства иерархической модели:

естественность описания иерархических данных;
высокая эффективность работы, быстродействие.

Недостатки иерархической модели:

жесткость структуры, ограниченная реализация, физическая и
логическая независимость;
ассиметрия представления данных, не являющихся иерархическими;
сложность операций корректировки;
в СУБД ИТ для реализации запроса требуется писать программы (СУБД
для программиста).

Сетевые модели также создавались для мало ресурсных ЭВМ. Это достаточно сложные структуры, состоящие из "наборов" – поименованных двухуровневых деревьев. "Наборы" соединяются с помощью "записей-связок", образуя цепочки и т.д. При разработке сетевых моделей было выдумано множество "маленьких хитростей", позволяющих увеличить производительность СУБД, но существенно усложнивших последние. Прикладной программист должен знать массу терминов, изучить несколько внутренних языков СУБД, детально представлять логическую структуру базы данных для осуществления навигации среди различных экземпляров, наборов, записей и т.п. Один из разработчиков операционной системы UNIX сказал "Сетевая база – это самый верный способ потерять данные".

Достоинства сетевой модели:

большая гибкость по сравнению с иерархическими СУБД;
высокая эффективность;
наличие стандартов.

Недостатки сетевой модели:

жесткость структуры;
высокая сложность.

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

Согласно Дейту, реляционная модель состоит из трех частей:

структурной части.
целостной части.
манипуляционной части.

Структурная часть описывает, какие объекты рассматриваются реляционной моделью. Постулируется, что единственной структурой данных, используемой в реляционной модели, являются нормализованные n-арные отношения.

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

Манипуляционная часть описывает два эквивалентных способа манипулирования реляционными данными - реляционную алгебру и реляционное исчисление.

Реляционной называется БД, в которой все данные, доступные пользователю, организованы в виде таблиц и все операции сводятся к операциям над таблицами. Связь между таблицами определяется только значениями данных. Основной оператор – выбор очередной таблицы, строки, столбца. Столбцы – атрибуты; строки – кортежи; значение столбца, строки – домен. Базовые операции – включить кортеж, удалить кортеж, исправить кортеж.

Достоинства реляционной модели:

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

Недостатки реляционной модели:

более низкая эффективность по сравнению с сетевыми и иерархическими моделями;
данные представляются на нескольких таблицах:
данные представляются не в естественном виде,
при работе с этими данными требуется их постоянная сборка.

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

10.3. Основные понятия реляционной модели

Базовые операции: Включить кортеж, удалить кортеж, исправить кортеж.

Известные языки запросов основанные на реляционной алгебре это – ISBL (начало 80x гдов), SQUARE и самый распространенный SQL.

SQL - Structured Query Language.

Язык SQL стал фактически стандартным языком доступа к базам данных. Все СУБД, претендующие на название "реляционные", реализуют тот или иной диалект SQL. Многие нереляционные системы также имеют в настоящее время средства доступа к реляционным данным. Целью стандартизации является переносимость приложений между различными СУБД.

SQL поддерживает такие операции над данными: как чтение данных, запросы; корректировка данных; управление доступом; обеспечение целостности данных;

SQL может быть как встроенным, так и внешним API.

В приложения используется как: в интерактивном режиме; в качестве языка администратора баз данных; язык программирования в архитектуре клиент-сервер; язык шлюзов (средство связи различных СУБД).

Достоинства SQL заключаются в: независимости от конкретных СУБД; переносимости с одной архитектуры ВМ на другу; наличие стандартов; поддержка ведущих компаний; декларативность.

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

В языке порядка 30 основных операторов.

11. Объектно – ориентированное программирование

11.1. Основные положения ООП

Объектно-ориентированное программирование - это новый подход к программированию. В ходе эволюции вычислительной техники и соответствующих операционных сред разрабатывались каждый раз более мощные методы программирования, чем предыдущие. Не останавливаясь на самых ранних методах программирования, сразу перейдем к анализу методов программирования, использующих языки высокого уровня. Язык программирования, легко понимаемый в коротких программах, становился плохо читаемым и неуправляемым, когда дело касалось больших программ. Избавление от неструктурированных программ пришло после изобретения в 1960 году языков структурного программирования. К ним относятся языки Алгол, Паскаль, и Си. Структурное программирование подразумевает точно обозначенные управляющие структуры, программные блоки, отсутствие или, по крайней мере, минимальное использование операторов GOTO, автономные подпрограммы, в которых поддерживается рекурсия и локальные переменные.

Сутью структурного программирования является возможность разбиения программы на составляющие ее элементы. Используя структурное программирование, средний программист может создавать и поддерживать программы свыше 50000 строк длиной. Но и это оказалось недостаточным на современном этапе. Чтобы писать более сложные программы, необходим был новый подход к программированию. В итоге, были разработаны принципы объектно-ориентированного программирования (ООП). ООП аккумулирует лучшие идеи, воплощенные в структурном программировании и сочетает их с мощными новыми концепциями, которые позволяют оптимально организовывать программы. ООП позволяет разложить проблему на связанные между собой задачи. Каждая проблема становится самостоятельным объектом, содержащим свои собственные коды и данные. В этом случае вся процедура в целом упрощается, и программист получает возможность оперировать с гораздо большими по объему программами. Все языки ООП, включая С++, основаны на трех основополагающих концепциях, называемых инкапсуляцией, полиморфизмом и наследованием. Рассмотрим эти концепции.

11.2. Инкапсуляция

Инкапсуляция - это механизм, который объединяет данные и код, и защищает и то и другое от внешнего вмешательства или неправильного использования. В ООП код и данные могут быть объединены вместе; в этом случае говорят, что создается так называемый «черный ящик». Все необходимые данные и коды находятся внутри его, то есть создается объект. Другими словами, объект - это то, что поддерживает инкапсуляцию. Внутри объекта коды и данные могут быть закрытыми (private) или открытыми (public). По умолчанию действует принцип private. Закрытые коды или данные недоступны для тех частей программы, которые существуют вне объекта. В случае public коды и данные доступны для всех частей программы. Характерной чертой является ситуация, когда открытая часть объекта используется для того, чтобы обеспечить контролируемый интерфейс с его закрытой частью. Рассмотрим такое важное понятие как класс.

Класс - это механизм для создания объектов. Синтаксис описания класса на С++ похож на синтаксис описания структуры.

class имя класса {

закрытые функции и переменные класса

public:

открытые функции и переменные класса

} список объектов;

В описании класса список объектов не является обязательным. Функции и переменные, объявленные внутри класса, становятся членами этого класса. По умолчанию, все функции и переменные, объявленные в классе, становятся закрытыми для этого класса. Все функции и переменные, объявленные после слова public, доступны как для членов класса, так и для любой другой части программы, в которой содержится класс.

11.3. Полиморфизм

Полиморфизм - это свойство, которое позволяет одно и то же имя использовать для решения двух или более задач, но технически разных. Целью полиморфизма, применительно к ООП, является использование одного имени для задания общих для класса действий. Выполнение каждого конкретного действия будет определяться типом и/или количеством данных. Например, в языке С++ можно использовать одно имя функции для множества различных действий. Это называется перегрузкой функции. В более общем смысле концепцией полиморфизма является идея «один интерфейс, множество методов». Это означает, что можно создать общий интерфейс для группы близких по смыслу действий. При этом выполнение конкретного действия зависит от данных. Преимуществом полиморфизма является то, что он помогает снижать сложность программ. Выбор же конкретного действия, в зависимости от ситуации, возлагается на компилятор. Полиморфизм может применяться и к функциям, и к операциям.

Остановимся на понятии перегрузка функций. Перегрузка функций не только обеспечивает тот механизм, посредством которого в С++ достигается один из типов полиморфизма, она также формирует то ядро, вокруг которого развивается среда программирования. Перегрузить функцию очень легко: просто объявите и задайте все требуемые варианты. Компилятор автоматически выберет правильный вариант вызова на основании числа или /и типа используемых в функции аргументов. То есть, имеем один интерфейс и множество методов.

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

# include < iostream.h >

// Перегрузка abs() тремя способами

int abs( int n);

long abs( long n);

double abs( double n);

main()

{

cout << ‘’ Абсолютная величина -10:’’ << abs(-10) << ‘’\n’’;

cout << ‘’ Абсолютная величина -10L:’’ << abs(-10L) << ‘’\n’’;

cout << ‘’ Абсолютная величина -10.01:’’ << abs(-10.01) << ‘’\n’’;

return 0;

}

int abs( int n)

{

return n < 0 ? -n : n;

}

long abs(long n)

{

return n < 0 ? -n : n;

}

double abs(double n)

{

return n < 0 ? -n : n; }

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

11.5. Наследование

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

class base { // Задание базового класса

int i;

public:

void set_i(int n);

int get_i();

};

class derived: public base { // Задание производного класса

int j;

public:

void set_j(int n);

int mul();

};

…

main()

{

derived ob;

ob.set_i(10); // загрузка i в base

ob.set_j(4); // загрузка j в derived

cout << ob.mul(); // вывод числа 40

return 0;

}

Отметим, что функция get_i(), которая является членом базового класса, а не производного, вызывается внутри производного класса без какой бы - то ни было связи с каким-либо объектом. Это возможно потому, что открытые члены класса base становятся открытыми членами derived.

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

Литература

1. Казиев В.М. Введение в информатику. www.intuit.ru

2. Коршунов Ю.М. Математические основы кибернетики. - М.: Энергия,

1980. - 423 с.

3. Мельников В.В. Защита информации в компьютерных системах. М.:

Финансы и статистика, 1997.

4. Жельников В. Криптография от папируса до компьютера. М.: АBF, 1996.

5. Грушо А.А., Тимонина Е.Е. Теоретические основы защиты информации.

М.: Яхтсмен, 1996.

6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для

инженера. - М. : Энергия, 1980. - 342с.

7. Поспелов Д.А. Логические методы анализа и синтеза схем.- М.:

Энергия, 1974. - 368 с.

8. Динман М.И. С++. Освой на примерах. – СПб.: БХВ Петербург, 2006. –

384 с.

9. Фридман А.Л. Язык программирования Си++ . Интернет-университет

информационных технологий - ИНТУИТ.ру, 2004.

10. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы

проектирования компиляторов. - М.: Мир, 1979. - 654 с.

11. Ленгсам Й., Огенстайн М., Тененбаум. Структуры данных для

персональных ЭВМ. — М.: Мир, 1989. — 568 с.

12. Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1985.

- 406 с.

PAGE \* MERGEFORMAT 2

EMBED CorelDraw.Graphic.7

1. ВФортунатов ВП
2. Методика построения эвольвентного профиля зубьев
3. на тему- Формування комплексу маркетингу підприємства FRESH Виконала- ст
4. Тема Кредитування підприємств
5. Дипломная работа- Класний керівник у сучасній школі
6. Программирование Уфа 2012 Составитель-
7. На тему- Разработка базы данных
8. Тема- Деревянное зодчество на Руси
9. взрослому столу Можно ли давать ребёнку сосиски варёную колбасу творожные сырки обжаренные котлетки бл
10. Сахар. Первое что нужно сделать людям которые хотят похудеть ~ отказаться от чая и кофе с сахаром.html
11. Реинжиниринговый подход к управлению организационным развитием Новый взгляд на антикризисное управл
12. Коммуникативные особенности поведения в конфликт
13. і. Акселерація лат
14. правовой связи и совместного проживания с нанимателем или собственником жилого помещения; другие родств
15. Проектирование ИС бакалавриат 3 курс Понятие информационной системы
16. Методы организации коллективной мыследеятельности
17. СЛЕДОМ ПЛОСКОСТИ называется прямая по которой данная плоскость пересекается с плоскостью проекций
18. 1 Сущность и содержание доходов и расходов предприятия
19. РЕФЕРАТ Та~ырыбы- Жер за~дарын б~з~аны ~шін жауапкершілік т~рлері
20. А~ это средство получения цельного знания о хозяйственной деятельности знаний о бизнесе понимания деятель

Материалы собраны группой SamZan и находятся в свободном доступе

А		Г	Р		У
Б		Д	С		Ф
В		Е	Т		Х
Г		Ж	У		Ц
Д		З	Ф		Ч
Е		И	Х		Ш
Ж		Й	Ц		Щ
З		К	Ч		Ь
И		Л	Ш		Ы
Й		М	Щ		Ъ
К		Н	Ь		Э
Л		О	Ы		Ю
М		П	Ъ		Я
Н		Р	Э		А
О		С	Ю		Б
П		Т	Я		В

П	Р	И	Е	З	Ж	А	Ю	Д	Н	Е	М
3	1	4	2	3	1	4	2	3	1	4	2
И	П	Е	Р	А	З	Ю	Ж	Е	Д	М	Н

А		Г	Р		У
Б		Д	С		Ф
В		Е	Т		Х
Г		Ж	У		Ц
Д		З	Ф		Ч
Е		И	Х		Ш
Ж		Й	Ц		Щ
З		К	Ч		Ь
И		Л	Ш		Ы
Й		М	Щ		Ъ
К		Н	Ь		Э
Л		О	Ы		Ю
М		П	Ъ		Я
Н		Р	Э		А
О		С	Ю		Б
П		Т	Я		В

П	Р	И	Е	З	Ж	А	Ю	Д	Н	Е	М
3	1	4	2	3	1	4	2	3	1	4	2
И	П	Е	Р	А	З	Ю	Ж	Е	Д	М	Н

Информация ее представление и измерение [3] 2

Поможем написать учебную работу

Выберите тип работы:

Оглавление

1. Информация, ее представление и измерение

2. Общая характеристика процессов сбора, передачи и обработки информации

2.1. Системы счисления и действия в них

2.2. Общая характеристика процессов передачи информации

2.3. Кодирование и шифрование информации

2.4. Компьютерные вирусы

3. Модели решения функциональных и вычислительных задач

3.1. Модели и моделирование

3.2. Основные свойства модели и моделирования

3.3. Классификация видов моделирования

3.4. Компьютерное моделирование

3.5. Функции алгебры логики

3.6. Булева алгебра. Функциональная полнота

3.7. Минимизация функций алгебры логики

4. Программные средства реализации информационных процессов

5. Технические средства реализации информационных процессов

6. Алгоритмизация и программирование

7. Архитектура ЭВМ. Локальные и глобальные сети.

7.1. Архитектура ЭВМ

7.2. Cеть передачи данных

7.3. Аппаратные средства сети

7.4. Локальная вычислительная сеть

7.5. Топология сети

7.6. Глобальная вычислительная сеть

7.7. Сетевая модель OSI

7.8. Стек протоколов TCP / IP

8. Программное обеспечение

8.1. Классификация и основные характеристики ПО

8.2. Структура технического обеспечения

8.3.Состав операционной системы и ее основные функции

9. Технология программирования

9.1. Организация данных в ЭВМ

9.2. Стеки и очереди

9.3. Графы

9.4. Деревья

10. Базы данных

10.1. Основные понятия

10.2. Модели данных в СУБД

10.3. Основные понятия реляционной модели

11. Объектно – ориентированное программирование

11.1. Основные положения ООП

11.2. Инкапсуляция

11.3. Полиморфизм

11.5. Наследование

Литература

А		Г	Р		У
Б		Д	С		Ф
В		Е	Т		Х
Г		Ж	У		Ц
Д		З	Ф		Ч
Е		И	Х		Ш
Ж		Й	Ц		Щ
З		К	Ч		Ь
И		Л	Ш		Ы
Й		М	Щ		Ъ
К		Н	Ь		Э
Л		О	Ы		Ю
М		П	Ъ		Я
Н		Р	Э		А
О		С	Ю		Б
П		Т	Я		В

П	Р	И	Е	З	Ж	А	Ю	Д	Н	Е	М
3	1	4	2	3	1	4	2	3	1	4	2
И	П	Е	Р	А	З	Ю	Ж	Е	Д	М	Н