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

УДК

ББК

Рекомендовано в качестве учебного пособия редакционно-издательским
советом МГУПИ

Рецензенты:

к.т.н., профессор Степанова Т.А.

Родина Н.В. Информатика: Учебное пособие, часть 2. – М.: МГУПИ, 2009. - 104 с.

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

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

Табл. 4. Ил. 17. Библиограф.: 14 назв.

Учебное пособие предназначено для студентов 1 курса специальности 230101 «Вычислительные машины, комплексы, системы и сети».

.

ã Родина Н.В., 2009

ã МГУПИ

Содержание

1 Передача информации….……....…….……..………….……….....….….…… 4

1.1 Общая схема передачи информации в линии связи….….…...…….…… 4

1.2 Характеристики канала связи…….….……….….…….…....…...……..…7

1.3 Влияние шумов на пропускную способность канала….……....……….10

1.4 Обеспечение надежности передачи информации….……...….....…....…12

1.4.1 Коды, обнаруживающие ошибку….…...……….………...…..….. 13

1.4.2 Коды, исправляющие одиночную ошибку…....…........…..…….... 15

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

1.6 Связь компьютеров по телефонным линиям….….…..….…..…....…..... 21

2 Поколения ЭВМ. Основные устройства компьютера…..………..….……..24

2.1 Поколения электронных вычислительных машин……….……….……24

2.2 Компьютер как формальный исполнитель алгоритмов (программ)......31

2.3 Основные устройства компьютера и их функции ……………....…...… 33

3 Структура программного обеспечения компьютера………………...……. 36

3.1 Классификация программного обеспечения……...…..…..……….....….36

3.2 Системное программное обеспечение ЭВМ…….……..………………..38

3.3 Прикладное программное обеспечение ЭВМ….……………..….…….. 42

4 Хранение информации в ОЗУ……….…………..……….…..…….…....…. 46

4.1 Классификация данных….……..…..….…….……….……….…………. 46

4.2 Представление элементарных данных в ОЗУ.….……….……….…….. 48

4.3 Структуры данных и их представление в ОЗУ.………….…….….……50

5 Хранение информации на внешних запоминающих устройствах. Файловые структуры……………………………………………………….…….…………56

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

5.2 Представление данных на внешних носителях….…...…..….………... 60

5.3 Роль операционной системы…….…….….……….…..……..…………. 63

6 Основы алгоритмизации…………….….………….…………………………65

6.1 Понятие алгоритма. Свойства алгоритма ………………..…..…....…… 65

6.2 Символьная форма представления алгоритма…………..…..…….…… 67

6.3 Графическая форма представления алгоритма……………….….…….. 71

6.4 Структурная теорема….….….…….………….…….……….……..……. 74

6.5 Основные подходы к разработке алгоритмов….……...…..……..…….. 77

6.6 Проверка правильности программы ………..….….……..……..……… 78

7 Вычислительные сети: начальные сведения…….….…….……….….……. 81

7.1 Классификация вычислительных сетей….…...….….………….....…....81

7.2 Локальные вычислительные сети (ЛВС)….….….…..……...…….….… 83

7.3 Организация обмена информацией в ЛВС….……..…..….……………. 87

7.4 Методы доступа в ЛВС (управление правом отправки сообщения).... 89

8 Глобальные вычислительные сети……………….………..………….….…..91

8.1 Электронная почта….…….….……..…….…….….…..……..…………. 91

8.3 Всемирная паутина World Wide Web …..…......…..…….…..….….……94

8.4 Общие вопросы безопасности.….….…….………..……...….….….….. 97

Список использованных источников ……...…....…..…...….…....…..…...…. 104

1 Передача информации

1.1 Общая схема передачи информации в линии связи

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

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

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

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

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

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

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

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

В общем случае при преобразовании выходящие сигналы не полностью воспроизводят все особенности сообщения на входе, а лишь его существенные стороны, то есть, при преобразовании часть информации теряется. Например, полоса пропускания частот при телефонной связи от 300 до 3400 Гц, в то время как частоты, воспринимаемые человеческим ухом, лежат в интервале 16 – 20 000 Гц.

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

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

Таблица 1.1 Примеры каналов связи

Канал связи	Среда	Носитель сообщения	Процесс, используемый для передачи
Почта, курьеры	Среда обитания человека	Бумага	Механическое перемещение носителя
Телефон, компьютерные сети	Проводник	Электрический ток	Перемещение электрических зарядов
Радио, телевидение	Электромагнитное поле	Электромагнитные волны	Распространение электромагнитных волн
Зрение	Электромагнитное поле	Световые волны	Распространение световых волн
Слух	Воздух	Звуковые волны	Распространение звуковых волн
Обоняние, вкус	Воздух, пища	Химические вещества	Химические реакции
Осязание	Поверхность кожи	Объект, воздействующий на органы осязания	Теплопередача, давление

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

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

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

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

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

Понятие линии связи объединяет все элементы схемы от источника до приемника информации.

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

1.2 Характеристики канала связи

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

Любой преобразователь, работа которого основана на использовании колебаний (электрических или механически) может формировать и пропускать сигналы из ограниченной области частот (например, радио – весь спектр разделен на диапазоны – УКВ, ДВ, СВ и т.п.)

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

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

Если параметр меняется синусоидально, то за один период колебания Т сигнал будет иметь одно максимальное значение и одно минимальное (рисунок 1.2). Обозначим максимальное значение «1» (импульс) и минимальное значение «0» (пауза).

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

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

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

Следовательно, u_m определяет длительность элементарного сигнала t₀, используемого для передачи сообщения.

Если с передачей одного импульса связано количество информации I_имп, а передается оно за время t₀, то очевидно, отношение I_имп /t₀будет отражать среднее количество информации, передаваемое по каналу за единицу времени.

Эта величина называется пропускной способностьюканала С= I_имп /t₀. Так как единицей измерения информации I является бит, а t₀ - секунды, то единицей измерения С будет бит/с (раньше называлось бод). Производными единицами являются:

1К бит/с = 10³ бит/с,

1М бит/с = 10⁶ бит/с,

1Г бит/с = 10⁹ бит/с.

Величину I_имп можно установить из следующих соображений. Если первичный алфавит содержит N знаков с вероятностью появления p_i, то среднее количество информации на знак алфавита

Если для представления знаков используется двоичный код длиной К⁽²⁾, то , откуда С = .

Пример 1. Первичный алфавит состоит из 3-х знаков с вероятностными характеристиками p₁ = 0,2, p₂ = 0,7, p₃ = 0,1 соответственно. Для передачи используется равномерный двоичный код. Частота тактового генератора 500 Гц. Какова пропускная способность канала?

N = 3, I_ср = 1,16 бит

K ³ log₂N = 2 (2 двоичных разряда на знак)

/с

Пусть за время t передано количество информации I. Величина, характеризующая быстроту передачи информации – скорость передачи информации–J = I/t.

Размерностью J, как и С, является бит/с.

Поскольку t₀ - минимальная длительность сигнала, то, очевидно, С соответствует максимальной скорости передачи информации по данной линии связи, то есть J £ C.

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

1.3 Влияние шумов на пропускную способность канала

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

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

Иная ситуация в реальном канале: из-за шумов при передаче может вместо 1 на выходе быть получен 0, и наоборот. Пусть вероятности таких искажений и для 0, и для единицы равны p_1®0 = p_0®1 = p. Тогда вероятность того, что исходный сигнал придет без искажений, очевидно равна (1-p). Следовательно, при распознавании сигнала возникает неопределенность, которая может быть охарактеризована средней энтропией

H = .

Эта неопределенность приведет к уменьшению количества информации, содержащейся в сигнале, на величину H, то есть (I_имп)’ = I_имп – H.

Следовательно, пропускная способность реального канала С_R:

Для двоичного кода сигнала I_имп = 1 бит, следовательно, при p = 0,5
C_R = 0. Это означает, что в данном случае на приемном конце линии связи с одинаковой вероятностью получаются 0 и 1, независимо от того, что за сигнал на входе, так что передача информации по такой линии оказывается вообще невозможной (рисунок 1.3).

Максимальное значение C_R достигает при p = 0 (отсутствие помех), а также при p = 1! (просто это такие помехи, которые каждый входящий сигнал 1 переводят в 0 и наоборот, что не мешает распознавать, какой сигнал был послан).

В остальных случаях C_R < C.

Пример 2. Каково отношение C_R/C, если средняя частота появления ошибки при передаче по линии с шумом составляет 1 ошибочный знак на 100 переданных, в случае использования двоичного кодирования?

р = 1/100; так как двоичный код, то I_имп = 1 бит.

Следовательно , то есть пропускная способность снизилась на 8%.

Влияние шумов определяется также соотношением мощности сигнала и мощности помех.

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

,

где

N_s – средняя мощность сигнала, а N_n – средняя мощность помех

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

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

1.4 Обеспечение надежности передачи информации

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

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

Вторая теорема Шеннона относится к реальным каналам связи и гласит следующее:

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

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

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

Возможны 2 различные ситуации (задачи) такого кодирования:

- кодирование обеспечивает только установление факта искажения информации – в этом случае исправление производится путем ее повторной передачи;

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

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

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

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

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

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

1.4.1 Коды, обнаруживающие ошибку

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

Например, для передачи слова «лето» можно передавать «лл ее тт оо».

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

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

Недостаток такого способа обеспечения надежности состоит в том, что избыточность сообщения оказывается очень большой – очевидно, L=2.

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

Например, для информационного байта 01010100 бит четности будет иметь значение «1», а для байта 11011011 – «0».

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

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

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

.

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

Поэтому обычно k_i = 8 или 16, и, следовательно, L = 1,125 и (1,0625).

Сегодня использование контрольных разрядов четности в оперативной памяти компьютера довольно распространено. Хотя говорилось, что ячейка памяти машин состоит из 8 битов, на самом деле она состоит из девяти битов, один из которых используется в качестве контрольного бита. Каждый раз, когда 8-битовый код передается в запоминающую схему, схема добавляет контрольный бит четности и сохраняет получившийся 9-битовый код. Если код уже был получен, схема проверяет его на четность. Если в нем нет ошибки, память убирает контрольный бит и возвращает 8-битовый код. В противном случае память возвращает восемь информационных битов с предупреждением о том, что возвращенный код может не совпадать с исходным кодом, помещенным в память.

1.4.2 Коды, исправляющие одиночную ошибку

По аналогии с предыдущим пунктом можно было бы предложить простой способ установления ошибки – передавать каждый символ трижды, например «лллееетттооо», тогда при получении сообщения «лвлееетттооо», ясно, что ошибка буква в и ее надо заменить на «л». Конечно, при этом предполагается, что вероятность появления парной ошибки невелика. Избыточность L = 3, что слишком много.

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

Так, для кодов приведенных в таблице 1.2, расстояние Хемминга между символами А и Б равно 4, а расстояние Хемминга между Б и В равно 3.

Таблица 1.2 Пример кодовой таблицы

Символ	Код	Символ	Код
А Б В Г		Д Е Ж З

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

Кроме того, если появится ошибка в коде, можно понять, как выглядел исходный код. Расстояние Хемминга между исходным кодом и измененным будет равно 1, а между ним и другими допустимыми кодами – по меньшей мере, 2.

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

Например, предположим, получен код 010100. Если сравнить его с другими кодами, то получим следующую таблицу расстояний (таблица 1.3).

Символ	Код символа	Расстояние между полученным кодом и кодом символа
А Б В Г Д Е Ж З

Таблица 1.3 Расстояние по Хеммингу

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

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12

7 6 5 4 3 2 1 0

Каждый проверочный бит контролирует определенные информационные биты:

1 - 1, 3, 5, 7, 9, 11 …;

2 - 2, 3, 6, 7, 10, 11, 14, 15…;

4 - 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23…;

8 - 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26… .

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

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

Пример 4.

1 2 3 4 5 6 7 8 9 10 11 12

Анализируем состояние контрольных битов

Бит 1 (1,3, 5, 7, 9, 11) – неверно, то есть ошибка находится в нечетном бите.

Бит 2 (2, 3, 6, 7, 10, 11) – верно, то есть ошибка не в 3-м, 7, 11 бите, а в 5 или 9.

Бит 4 (4, 5, 6, 7, 12) – неверно, то есть ошибка – в 5 бите.

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

Номер бита, содержащего ошибку, 5 – равен сумме номеров контрольных битов, указавших на ее существование (1 и 4) – это не случайное совпадение, а общее свойство кодов Хемминга.