Информатика_Ч1

рn рn-1 … р1 р0 р-1 р-2 ...,

где рi – цифры P-ичной системы. Требуется найти запись этого же числа в системе с основанием Q:

qn qn-1 … q1 q0 q-1 q-2...,

где qi – цифры P-ичной системы.

Перевод Q → P. Задача сводится к вычислению полинома вида

Х = qnQn + qn-1Qn-1 +…+q1Q1 + q0Q0 + q-1Q-1 +…+ q-mQ-m. (2.4)

Для получения P-ичного изображения (2.4) необходимо все цифры qi и число Q заменить P-ичными изображениями и выполнить арифметические операции в P-ичной системе счисления.

Пример. Перевести х = 3718 в десятичную систему счисления. Запишем число 3718 в виде х = 3 · 82 + 7 · 81 + 1 · 80 и выполним все

необходимые действия в десятичной системе:

х = 3 · 64 + 7 · 8 + 1 = 192 + 56 + 1 = 249.

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

N = qs qs-1 … q1 q0,

где qi – искомые цифры Q-ичной системы. Для определения q0 разделим обе части равенства

N = q Q s + q	s-1	Q s-1 +…+q	Q1	+ q	0	(2.5)
s		1

на число Q, причем в левой части произведем деление, пользуясь правилами P-ичной арифметики, а правую часть перепишем в виде

N/Q = qsQ s-1 + q-1Q s-2 + …+ q1 + q0 /Q.

Приравнивая между собой полученные целые и дробные части (учитывая, что qi < Q), получим:

[N/Q] = qsQ s-1 + q-1Q s-2 + …+ q1,

[N/Q] = q0 /Q.

Таким образом, младший коэффициент q0 в разложении (2.5) определяется соотношением

q0=Q[N/Q].

41

Положим

N1 = [N/Q] =qsQs-1 + q-1Qs-2 +…+q1.

Тогда N1 будет целым числом и к нему можно применить ту же самую процедуру для определения следующего коэффциента q1 и т. д.

Таким образом, при условии, что N0 = N, перевод чисел с использованием Р-ичной арифметики осуществляется по следующим реккурентным формулам:

qi = Q[Ni / Q],

(2.6)

Ni+1 = [Ni / Q], (i = 0, 1, 2, …).

Этот процесс продолжается до тех пор, пока не будет получено

Ni+1 = 0.

Пример. Привести число N = 47 в двоичную систему. Применяя формулы (2.6) при Q = 2, имеем:

47:2=23(1); 23:2=11(1); 11:2=5(1); 5:2=2(1); 2:2=1(0); 1:2= 0(1).

Поскольку числа нуль и единица в обеих системах счисления обозначаются одинаковыми цифрами 0 и 1, то в процессе деления сразу получим двоичные изображения искомых цифр: N = 1011112.

Форматы представления и преобразования информации

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

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

При кодировании ставятся следующие цели: –удобство физической реализации; –удобство восприятия; –высокая скорость передачи и обработки;

42

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

мации.

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

Рассмотрим способы представления информации в ЭВМ. Для записи, хранения и выдачи по запросу информации, обрабатываемой с помощью ЭВМ, предназначено ЗУ (память) ЭВМ. Напоминаем, что в памяти ЭВМ информация записывается в виде цифрового двоичного кода. Это объясняется тем, что электронные схемы ЗУ строятся из элементов, которые могут находиться только в одном из двух устойчивых состояний, интерпретируемых как 0 или 1. Ячейки, хранящие по одному биту информации, объединяются в группы, называемые машинными словами.

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

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

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

ния числа с плавающей запятой отводится 32 двоичных разряда, из которых один двоичный разряд хранит знак числа, 8 разрядов отводятся под порядок и 23 под мантиссу. Тогда возможный допустимый диапазон значений 3,4 · 10-38… 3,4 · 10+38.

Представление символьной информации в ЭВМ. Символьная информация в памяти ЭВМ также представлена в двоичном коде. Например, можно обозначить каждую букву числом, соответствующим ее порядковому номеру в алфавите: А – 01, Б – 02 и т. д. В алфавит можно включить другие символы, например знаки препинания, спецсимволы, и также присвоить им какие-либо номера. При таком

43

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

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

В настоящее время существует несколько широко распространенных схем кодировки, например код BCD и его модификация EBCDIC, код ASCII и его отечественная модификация KOI-8R, дополненная буквами русского алфавита, кодировка ANSI, принятая в операционной системе Windows.

2.3. Способы разработки алгоритмов

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

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

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

иискусство специалиста.

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

44

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

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

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

45

ГЛАВА 3 ПЕРСОНАЛЬНЫЕ ЭВМ

3.1. Из истории создания персональных компьютеров

Появление в 1975 г. в США первого серийного персонального компьютера (персональной ЭВМ – ПЭВМ) вызвало революционный переворот во всех областях человече-

ской деятельности.

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

Основой ПЭВМ является микропроцессор (МП). Развитие микропроцессорной техники и технологии определило смену поколений ПЭВМ:

–первое поколение (1975 – 1980 гг.) – на базе 8-разрядного МП;

–второе поколение (1981 – 1985 гг.) – на базе 16-разрядного МП;

–третье поколение (1986 – 1992 гг.) – на базе 32-разрядного МП;

–четвертое поколение (с 1993 г.) – на базе 64-разрядного МП. Большую роль в развитии ПЭВМ сыграло появление компьютера

IBM PC, произведенного корпорацией IBM на базе процессора Intel 8086 в 1981 г. Этот персональный компьютер занял ведущее место на рынке ПЭВМ. Его основное преимущество – «открытая архитектура», благодаря которой пользователи могут расширять возможности приобретенной ПЭВМ, добавляя различные периферийные устройства и модернизируя компьютер.

В дальнейшем другие фирмы стали создавать компьютеры, совместимые с IBM PC. IBM PC стал по сути стандартом класса ПЭВМ. В настоящее время около 85 % всех продаваемых ПЭВМ базируется на архитектуре IBM PC.

46

3.2. Структура ПЭВМ

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

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

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

вшине управления – числом управляющих сигналов, используемых в ПЭВМ.

Системный блок. Являясь главным в ПЭВМ, этот блок включает

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

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

47

определенный номер – адрес порта. Через порты пользователь может управлять ВУ, используя команды ввода-вывода.

	23		Манипуляторы		Телефонная линия
					22
		3
6	5
	2	4	19	20	21
7
			1
8	10	11	12	13	14
	15	16	17	18

	К другим
	вычислительным
9	системам
24

Рис. 19. Структура персонального компьютера:

1 – системная магистраль (шина); 2 – постоянная память; 3 – память экрана; 4 – оперативная память; 5 – схемы управления шиной; 6 – АЛУ; 7 – регистры; 8 – УУ; 9 – интерфейс клавиатуры; 10–12 – контроллеры; 13 – параллельный интерфейс; 14 – сетевой адаптер; 15 – НГМД; 16 – НЖМД; 17 – НМЛ; 18 – ПУ; 19 – интерфейс манипуляторов; 20 – интерфейсы других внешних устройств; 21 – последовательный интерфейс; 22 – модем;

23 – дисплей; 24 – клавиатура

Микропроцессор. Ядром любой ПЭВМ является центральный микропроцессор, который выполняет функции обработки информации и управления работой всех блоков ПЭВМ. Конструктивно МП выполнен на одном кристалле (на одной СБИС), иначе говоря, «чипе».

Всостав МП входят:

–устройство управления (УУ);

48

–арифметико-логическое устройство (АЛУ);

–внутренняя регистровая память (ВРП);

–кэш-память и ряд других устройств.

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

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

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

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

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

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

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

3.3. Внешние устройства ПЭВМ

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

49

няться в ее составе. Внешние устройства обеспечивают хранение больших объемов данных и взаимодействие пользователя с ПЭВМ.

Конструктивно каждая модель ПЭВМ имеет так называемый базовый набор внешних устройств – клавиатуру, ручной манипулятор (мышь или другие), дисплей, накопитель на жестком магнитном диске (НЖМД) и накопитель на гибком магнитном диске (НГМД), составляющий вместе с системным блоком «базовую конфигурацию» этой модели. При необходимости к ПЭВМ могут подключаться также дополнительные внешние устройства: принтер, сканер и пр.

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

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

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

Накопители на гибких магнитных дисках (НГМД). Служат для хранения программ и данных небольшого объема и удобны для переноса информации с одной ЭВМ на другую. Носитель информации – гиб-

50