Высшее образование

Б.В. Соболь, А.Б. Галин, Ю.В. Панов, Е.В. Рашидова, Н.Н. Садовой

Информатика

Учебник

Издание третье, дополненное и переработанное

Ростов-на-Дону

«Феникс»

2007

УДК 004(075.8) ББК 32.81я73. КТК21

И 74

Рецензенты:

кафедра «Информационные системы в строительстве» РГСУ, доктор технических наук, профессор РГУ А. В. Аграновский

И 74 Информатика : учебник/ Б.В. Соболь [и др.]-Изд. 3-е, дополн. и перераб. — Ростов н/Д: Феникс, 2007. — 446 [1] с.-(Высшее образование).

I5ВN 978-5-222-12081-1

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

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

УДК 004(075.8)

I5ВN 978-5-222-12081-1 ББК 32.81я73

Соболь Б.В., Галин А.Б., Панов Ю.В.,

Рашидова Е.В., Садовой Н.Н., 2007

^> Оформление, изд-во «Феникс», 2007

прЕписловиЕ

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

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

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

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

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

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

Авторы

список сокрАШЕний

АВМ — аналоговая вычислительная машина

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

АО — аппаратное обеспечение

АПС — аппаратно-программные средства

АЦП — аналогово-цифровой преобразователь

БД — база данных

БИС — большая интегральная схема

ВЗУ — внешнее запоминающее устройство

ГВС — глобальные вычислительные сети

ДНФ — дизъюнктивная нормальная форма

ЖКИ — жидкокристаллические индикаторы

ИС — информационная система

КНФ — конъюнктивная нормальная форма

КС — компьютерная система

ЛВС — локальные вычислительные сети

НСД — несанкционированный доступ

ОЗУ — оперативное запоминающее устройство

ООП — объектно-ориентированное проектирование

ОС — операционная система

ПЗУ — постоянное запоминающее устройство

ПО — программное обеспечение

ППЗУ — перепрограммируемые ПЗУ

ППО — прикладное программное обеспечение

ППП — пакет прикладных программ

РОН — регистры общего назначения

СА — сетевой адаптер

САУ — система автоматического управления

СБИС — сверхбольшая интегральная схема

СВТ — средства вычислительной техники

СУБД — система управления базой данных

ФС — файловая система

ФСА — функциональная структура алгоритма

ЦАП — цифро-аналоговый преобразователь

ЦВМ — цифровая вычислительная машина

ЦП — центральный процессор

ЭВМ — электронная вычислительная машина

ЭЛТ — электронно-лучевая трубка

АОР (Ассе1ега1ес] СгарЫсз Рог!) — локальная шина видеоконтрол­лера

САЗЕ (Сотри1ег-А1с1ес1 Зойдуаге Еп§теегш§) — автоматизирован­ные системы проектирования программных средств

СО (Сотрас! О1§1с) — оптический компакт-диск

СО-К (СО-КесойаЫе) — оптический компакт-диск с однократ­ной записью

СО-К\У (СО-Ке^п1аЫе) — оптический компакт-диск с много­кратной записью

С18С (Сотр1ех 1п$1шс(юп 5е1 Сотри1ег) — полная система ко­манд переменной длины

СМУК — модель представления светоотражающих графических

объектов

БОЕ (Оупатю Оа1а ЕхсЬап^е) — динамический обмен данных

ООоЗ (О151пЪи1ес1 ОоЗ) — ОоЗ атака, проводимая в определен­ное время

ВоЗ (Оепу-оГ-ЗепЛсе) — атака на отказ в обслуживании ООЗ (О18К ОрегаПп^ Зу81ет) — дисковая операционная система ф! (йо18 рег 1псН) — количество точек на дюйм ОКАМ (Оупагшс КАМ) — ОЗУ динамического типа

ОУО (О1§йа1 Уег8а111е О181с) — компакт-диск с высокой плотнос­тью записи

РКАМ (Реггое1ес1пс КАМ) — ферроэлектрическая память с про­извольным доступом

НТМЬ (Нурег Тех1 Маг1шр Ьап§иа§е) — универсальный язык раз­метки гипертекста

НТТР (Нурег1ех1 ТгапзГег Рго1осо1) — протокол передачи гипер­текста

1Р (1п1егпе1 Рго1осо1) — маршрутный протокол Интернет

18О (1п1егпа1:юпа1 ОщатгаНоп Гог 8*апс1агсН2а{юп) — Международ­ная организация по стандартизации

ЬСО (Цщш<1 Сгу8*а1 О18р1ау) — жидкокристаллические индика­торы

ЬЕР (1Л§№ Егш88юп Р1а8Ис8) — самоизлучающие мониторы

М8 (М1сго8ой) Майкрософт — фирма-производитель программ­ного обеспечения

ОЬЕ (ОЬ|ес1 Ь1п1с1п§ апй ЕтЪесШт^) — принцип внедрения и свя­зывания объектов

ОМТ(ОЬ|ес1 Мос1еНп§ ТесЬп^^ие) — технология объектного моде­лирования

ОО8Е (ОЬ]ес1-Опеп1ес1 5ой\уаге Еп§1пеепп§) — объектно-ориен­тированная разработка программного обеспечения

О81 (Мойе! оГОреп 8у81ет 1п1егсоппес1юп8) — модель взаимодей­ствия открытых систем

РС (Регзопа! Сотри1ег) — персональный компьютер

РС1 (РепрЬега! СотропеШ: 1п1егсоппес1) — общая шина настоль­ных компьютеров

РСМС1А (Регзопа! Сотри1ег Метогу Саге! 1п1егпаИопа1

А88ос1а1юп) — общая шина переносных компьютеров

РОР (Р1а8та О18р1ау Рапе18) — плазменные мониторы

РЬ/1 (Рго§гатт1п§ Ьап§иа§е Опе) — язык программирования

(ПЛ/1)

РРМ (Ра§е Рег М1пи1е) — количество страниц в минуту

КАМ (Капйот Ассезз Метогу) — память со свободным доступом

КСВ (Ней Сгееп В1ие) — модель представления светоизлучающих

графических объектов

К15С (КесЗисес! [пз^гисНоп 5е1 Сотри1ег) — сокращенный набор

команд фиксированной длины

КОМ (Кеас! Оп1у Метогу) — память только для чтения

5МТР (5йпр1е МаП ТгашГег РгоЮсо!) — простой протокол пере­сылки почты

8КАМ (5иию НАМ) — ОЗУ статического типа

5ТР (5Ые1с1ес1 Т\У181ес1 Ра1г) — экранированная витая пара

ТРТ (ТЫп Р\\т Тгап8181ог) — жидкокристаллический экран с тон­копленочным транзистором

ТСР (Тгап8Ш18810П СоШго! РгоЮсо!) — транспортный протокол

Интернет

УМЬ (ип1Пес1 Мос1еНп§ Ьап§иа§е) — унифицированный язык мо­делирования

1ЖЬ (итГогт Яеяоигсс Ьоса1ог) — унифицированный указатель

ресурса

УТР (ип8Ню1с1сс1 Т\У1$1ей Ра1г) — неэкранированная витая пара

\УУ51\УУС (\У1па1 Уои 5ее 18 \УНа1 Уои Се1) — принцип «что видишь

(на экране), то и получишь (при печати на листе)»

\У\У\У (\Уог1с1 \У1с1е \УсЬ ) — Всемирная паутина

. информации, информатика, информационные технологии

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

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

Начиная с XVII в. объем научной информации удваивался, при­мерно, каждые 20 лет, в настоящее время он удваивается в 5—6 лет и тенденция ускорения сохраняется. Одной из важнейших проблем человечества наших дней является лавинообразный рост потока ин­формации в любой отрасли жизнедеятельности. Подсчитано, что со­временный специалист должен тратить около 80 % своего рабочего времени, чтобы уследить за всеми новыми работами в его области деятельности.

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

1.1. Информация

1,1,1, Понятие инсрорллаиии

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

Как известно, в материальном мире все физические объекты, ок­ружающие нас, являются либо телами, либо полями. Физические объекты, взаимодействуя друг с другом, порождают сигналы различных типов. В общем случае любой сигнал — это изменяющийся во време­ни физический процесс. Такой процесс может содержать различные характеристики. Характеристика, которая используется для представ­ления данных, называется параметром сигнала. Если параметр сигна­ла принимает ряд последовательных значений и их конечное число, то сигнал называется дискретным. Если параметр сигнала — непрерыв­ная во времени функция, то сигнал называется непрерывным.

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

10

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

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

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

Из вышесказанного следует, что информация не является ста­тическим объектом, она появляется и существует в момент слияния методов и данных, все прочее время она находится в форме данных. Момент слияния данных и методов называется информационным про­цессом (рис. 1.1).

Рис. 1.1. Формирование информации

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

Таким образом, первичная информация может существовать в виде

11

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

1,1,2, СВойстВа инсрормаиии

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

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

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

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

12

информации может характеризоваться вероятностью, например, мож­но сказать, что при бросании монеты с вероятностью 50 % выпадет герб.

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

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

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

1,1,3, Понятие количество инсрормоиии

Свойство полноты информации негласно предполагает, что име­ется возможность измерять количество информации. Какое количество информации содержится в данной книге, какое количество инфор­мации в популярной песенке? Что содержит больше информации: роман «Война и мир» или сообщение, полученное в письме от това­рища? Ответы на подобные вопросы не просты и не однозначны, так как во всякой информации присутствует субъективная компонента. А возможно ли вообще объективно измерить количество информа­ции? Важнейшим результатом теории информации является вывод о том, что в определенных, весьма широких условиях, можно, пренебре­гая качественными особенностями информации, выразить ее количество числом, а следовательно, сравнивать количество информации, содер­жащейся в различных группах данных.

13

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

Рассмотрим пример: дома осенним утром, старушка предполо­жила, что могут быть осадки, а могут и не быть, а если будут, то в форме снега или в форме дождя, т.е. «бабушка надвое сказала — то ли будет, то ли нет, то ли дождик, то ли снег». Затем, выглянув в окно, увидела пасмурное небо и с большой вероятностью предполо­жила — осадки будут, т.е., получив информацию, снизила количество вариантов выбора. Далее, взглянув на наружный термометр, она уви­дела, что температура отрицательная, значит, осадки следует ожидать в виде снега. Таким образом, получив последние данные о темпера­туре, бабушка получила полную информацию о предстоящей погоде и исключила все, кроме одного, варианты выбора.

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

За единицу информации принимается один бит (англ. Ы1 — Ыпагу йщИ — двоичная цифра). Это количество информации, при котором неопределенность, т.е. количество вариантов выбора, умень­шается вдвое или, другими словами, это ответ на вопрос, требующий односложного разрешения — да или нет.

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

Широко используются еще более крупные производные едини­цы информации:

1 Килобайт (Кбайт) = 1024 байт = 2¹⁰ байт, 1 Мегабайт (Мбайт) = 1024 Кбайт = 2²⁰ байт, 1 Гигабайт (Гбайт) = 1024 Мбайт = 2³⁰ байт, 1 Терабайт (Тбайт) - 1024 Гбайт = 2⁴⁰ байт.

14

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

1,1,4, информационные проиессы

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

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

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

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

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

15

1,1,5. инсрорллаиия В жизни челоВечестВа

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

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

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

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

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

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

16

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

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

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

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

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

17

Развитие мировых информационных ресурсов позволило:

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

• сформировать мировой и внутригосударственный рынок инфор­ мационных услуг;

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

1.2. ЛреЭмет и структура информатики

Термин информатика получил распространение с середины 80-х гг. прошлого века. Он состоит из корня тГогт — «информация» и суффикса таИс8 — «наука о...». Таким образом, информатика — это наука об информации. В англоязычных странах термин не прижил­ся, информатика там называется Сотри1ег 8с1епсе — наука о компь­ютерах.

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

Информатика — это наука, изучающая:

• методы реализации информационных процессов средствами вычис­ лительной техники (СВТ);

• состав, структуру, общие принципы функционирования СЕТ;

• принципы управления СВТ.

Из определения следует, что информатика — прикладная наука, использующая научные достижения многих наук. Кроме того, инфор­матика - практическая наука, которая не только занимается описа-

18

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

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

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

• форматы представления данных (предполагается, что одни и те же данные могут быть представлены разными способами);

• теоретические проблемы сжатия данных;

• структуры данных, т.е. способы хранения с целью удобного дос­ тупа к данным.

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

• основы построения элементов цифровых устройств;

• основные принципы функционирования цифровых вычисли­ тельных устройств;

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

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

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

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

• средства взаимодействия аппаратного и программного обеспече­ ния;

19

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

• программное обеспечение СВТ (ПО).

Обобщая сказанное, можно предложить следующую структурную схему (рис. 1.2):

Рис. 1.2. Структура информатики

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

Вторая глава посвящена аппаратному обеспечению информаци­онных процессов. В ней рассматриваются вопросы синтеза цифро-

20

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

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

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

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

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

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

21

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

Обобщая сказанное, можно предложить следующую структуру программного обеспечения (рис. 1.3).

Рис. 1.3. Классификация программного обеспечения

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

22

ные продукты многих фирм стали объединять в себе программные элементы из разных классов. Например, операционная система \Мпёо\У8, являясь комплексом системных программ, в своем составе содержит блок служебных программ (дефрагментация, проверка, очи­стка диска и др.), а также текстовый процессор \УогёРас1, графичес­кий редактор Рат1, которые принадлежат классу прикладных про­грамм.

1,3. Представление (кодирование) Эаннын

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

Подготовка данных для обработки на компьютере (представле­ние данных) в информатике имеет свою специфику, связанную с электроникой. Например, мы хотим проводить расчеты на компью­тере. При этом нам придется закодировать цифры, которыми запи­саны числа. На первый взгляд, представляется вполне естественным кодировать цифру ноль состоянием электронной схемы, где напря­жение на некотором элементе будет равно 0 вольт, цифру единица — 1 вольт, двойку — 2 вольт и т.д., девятку — 9 вольт. Для записи каж­дого разряда числа в этом случае потребуется элемент электронной схемы, имеющий десять состояний. Однако элементная база элект­ронных схем имеет разброс параметров, что может привести к появ­лению напряжения, скажем, 3,5 вольт, а оно может быть истолкова-

23

но и как тройка и как четверка, т.е. потребуется на уровне электрон­ных схем «объяснить» компьютеру, где заканчивается тройка, а где начинается четверка. Кроме того, придется создавать весьма непро­стые электронные элементы для производства арифметических опе­раций с числами, т.е. на схемном уровне должны быть созданы таб­лица умножения — 10 х 10 = 100 схем и таблица сложения — тоже 100 схем. Для электроники 40-х гг. (время, когда появились первые вычислительные машины) это была непосильная задача. Еще слож­нее выглядела бы задача обработки текстов, ведь русский алфавит со­держит 33 буквы. Очевидно, такой путь построения вычислительных систем не состоятелен.

В то же время весьма просто реализовались электронные схе­мы с двумя устойчивыми состояниями: есть ток — 1, нет тока — О, есть электрическое (магнитное) поле — 1, нет — 0. Взгляды создате­лей вычислительной техники были обращены на двоичное кодирова­ние как универсальную форму представления данных для дальнейшей обработки их средствами вычислительной техники. Предполагается, что данные располагаются в некоторых ячейках, представляющих упорядоченную совокупность из двоичных разрядов, а каждый раз­ряд может временно содержать одно из состояний — 0 или 1. Тогда группой из двух двоичных разрядов (двух бит) можно закодировать 2² = 4 различные комбинации кодов (00, 01, 10, 11); аналогично, три бита дадут 2³ = 8 комбинаций, восемь бит или 1 байт — 2⁸ = 256 и т.д.

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

1.3.1, Представление чисел В ЗВоичном коЗе

Существуют различные способы записи чисел, например: мож­но записать число в виде текста — сто двадцать три; римской систе­ме счисления — СХХ1П; арабской — 123.

24

Системы счисления

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

Числа записываются с помощью символов, и по количеству сим­волов, используемых для записи числа, системы счисления подраз­деляются на позиционные и непозиционные. Если для записи числа используется бесконечное множество символов, то система счисле­ния называется непозиционной. Примером непозиционной системы счисления может служить римская. Например, для записи числа один используется буква I, два и три выглядят как совокупности симво­лов II, III, но для записи числа пять выбирается новый символ V, шесть — VI, десять — вводится символ X, сто — С, тысяча — Ми т.д. Бесконечный ряд чисел потребует бесконечного числа символов для записи чисел. Кроме того, такой способ записи чисел приводит к очень сложным правилам арифметики.

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

В повседневной жизни мы пользуемся десятичной позиционной системой счисления, я = 10, т.е. используется 10 цифр: 0123456 789.

Рассмотрим правила записи чисел в позиционной десятичной системе счисления. Числа от 0 до 9 записываются цифрами, для за­писи следующего числа цифры не существует, поэтому вместо 9 пи­шут 0, но левее нуля образуется еще один разряд, называемый стар­шим, где записывается (прибавляется) 1, в результате получается 10. Затем пойдут числа 11, 12, но на 19 опять младший разряд запол­нится и мы его снова заменим на 0, а старший разряд увеличим на 1, получим 20. Далее по аналогии 30, 40 ... 90, 91, 92 ... до 99. Здесь заполненными оказываются два разряда сразу; чтобы получить сле­дующее число, мы заменяем оба на 0, а в старшем разряде, теперь уже третьем, поставим 1 (т.е. получим число 100) и т.д. Очевидно, что, используя конечное число цифр, можно записать любое сколь угод-

25

но большое число. Заметим также, что производство арифметичес­ких действий в десятичной системе счисления весьма просто.

а в общем виде это правило запишется так:

Число в позиционной системе счисления с основанием ^ может быть представлено в виде полинома по степеням ц. Например, в де­сятичной системе мы имеем число

Здесь Х_(ч) — запись числа в системе счисления с основанием я; х. — натуральные числа меньше я, т.е. цифры; п — число разрядов целой части; т — число разрядов дробной части.

Записывая слева направо цифры числа, мы получим закодиро­ванную запись числа в я-ичной системе счисления:

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

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

Но запись числа в двоичной системе счисления длиннее записи

26

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

Восьмеричная система счисления имеет восемь цифр: 01234 567. Шестнадцатеричная — шестнадцать, причем первые 10 цифр совпадают по написанию с цифрами десятичной системы счисления, а для обозначения оставшихся шести цифр применяются большие латинские буквы, т.е. для шестнадцатеричной системы счисления получим набор цифр: 0123456789АВСОЕЕ

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

231_<10)= 11100111₍₂₎=347₍₈₎=Е7₍₁₆₎.

27

Запишем начало натурального ряда в десятичной, двоичной, восьмеричной и шестнадцатеричной системах счисления.

Преобразование чисел из оЗной системы счисление В Зругую

Так как десятичная система для нас удобна и привычна, все арифметические действия мы делаем в ней, и преобразование чисел из произвольной недесятичной (я *10) системы в десятичную удоб­но выполнять на основе разложения по степеням ц, например:

Преобразование из десятичной в прочие системы счисления про­водится с помощью правил умножения и деления. При этом целая и дробная части переводятся отдельно.

Рассмотрим алгоритм на примере перевода десятичного числа 231 в двоичную систему (совершенно аналогичен перевод из деся­тичной системы в любую я-ичную). Разделим число на два (основа­ние системы): нацело 231 : 2 = 115 и остаток 1, т.е. можно записать 231 = 115x2'+ 1 х 2°.

Число 115 (такой двоичной цифры нет) тоже может быть раз-

28

делено нацело на 2, т.е. 115 : 2 = 57 и остаток 1. По аналогии запи­шем

231 = (57 х 2 + 1) х 2 + 1 = 57 х 2² 4- 1 х I¹ + 1 х 2°;

аналогично продолжим процесс дальше:

57 : 2 = 28, остаток 1; 231 = ((28 х2+1)х2+1)х2+1 = 28х х 2³ + 1 х 2² + 1 х 2¹ + 1 х 2°.

28 : 2 = 14, остаток 0; 231 = (((14 х 2 + 0) х 2 +1) х 2 + 1) х 2 + + 1 = 14 х 2⁴ + 1 х 2² + 1 х 2¹ + 1 х 2°.

14 : 2 = 7, остаток 0; 231=((((7 х 2 + 0) х 2 + 0) х 2 + 1) х 2 + 1)х х2+ 1 = 7х2⁵ + 1 х2²+ 1 х2' + 1 х 2°.

7:2 = 3, остаток 1; 231 = (((((3 х2 + 1)х2 + 0)х2 + 0)х2 + + 1)х2+ 1)х2 + 1 = 3х2⁶ + 1 х2⁵+ 1 х2²+ 1 х 2¹ + 1 х 2°.

3:2= 1; остаток 1; далее процесс продолжать нельзя, так как 1 не делится нацело на 2.

231 = ((((((1 х2+1)х2+1)х2 + 0)х2 + 0)х2+1)х2+1)х х 2 + 1 = 1 х 2⁷ + 1 х 2⁶ + 1 х 2⁵ + 1 х 2² + 1 х 2¹ + 1 х 2°.

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

231 = 1 х2⁷+ 1 х2⁶+ 1 х 2⁵+ 0 х 2⁴+ 0 х 2³+ 1 х2²+ 1 х 2¹+ + 1x2°= 11100111^.

Эти выкладки можно сократить, записав процесс деления сле­дующим образом:

231

231₍₁₀₎=11100111₍₂₎

29

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

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

Умножим его на 2, т.е. 0,8125 х 2 = 1,625 или 0,8125 = (1 + 0,625) х х2"¹ = 1x2-' + 0,625х2-¹.

Аналогично 0,625 = (1 + 0,25) х 2~¹ или

0,8125 = 1 х 2'¹ + (1 + 0,25) х 2'¹ х 2~^] = 1 х 2~^] + 1 х 2~² + + 0,25 х 2~², но 0,25 = 0,5 х 2~^].

0,8125 = 1 х 2-¹ + (1 + 0,5 х 2~¹) х 2'¹ х 2~' = 1 х 2~^! + 1 х 2~² + + 0,5 х 2~³ , но 0,5 = 1 х 2~¹.

0,8125 = 1 х 2'¹ + 1 х 2-²+ 1 х 2-¹ х 2'³ = 1 х 2-' + 1 х 2-²+ 1 х 2~⁴.

В итоге получаем, что 0,8125₍₁₀₎ = 1 х 2'¹ + 1 х 2~² + 1 х 2~⁴ = = 0,1101₍₂₎. Сокращая выкладки, получим правило (алгоритм) после­довательного умножения',

0	8125
	2
1	625
	2
1	250
	2
0	5
	2
1	0

Попутно заметим, что в десятичной системе счисления правиль­ная дробь переводится в десятичную дробь в конечном виде только в том случае, если ее знаменатель в качестве множителей имеет толь-

30

ко степени двоек и пятерок, т.е. дробь имеет вид _{т п} . Все же ос-

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

Если ведутся приближенные вычисления, то последний разряд является сомнительным, и для обеспечения в приближенных вычис­лениях одинаковой точности в двоичной и десятичной записях чис­ла без бесконечных дробей, достаточно взять число двоичных разря­дов в (1о§₂10 ~ 3,3) 4 раза больше, чем десятичных.

Между двоичной системой счисления, с одной стороны* и восьмеричной и шестнадцатеричной (заметим, 8 и 16 — есть третья и четвертая степени двойки) — с другой, существует связь, позволя­ющая легко переводить числа из одной системы в другую. Рассмот­рим на примере:

231,8125_(|0)= 11100111, 1101₍₂₎= 1 х 2⁷+ 1 х 2⁶ + 1 х 2⁵ + 1 х 2² + + 1 х 2' + 1 х 2°+ 1 х 2-¹ + 1 х 2'²+1 х 2Л

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

(1 х 2³ + 1 х 2² + 1 х 2¹ + 0 х 2°) х 2⁴ + (1 х 2³ + 1 х 2² + 1 х 2¹ + + 1 х 2°) + (1 х 2³ + 1 х 2² + 0 х 2¹ + 1 х 2°) х 2-⁴ = (1 х 2³ + 1 х 2² + + 1 х 2¹ + 0) х 16¹ + (1 х 2² + 1 х 2¹ + 1 х 2°) х 16° + (1 х 2³ +1 х 2² + + 0 х 2¹ + 1 х 2°) х 16-' = 14 х 16' + 7 х 16° + 13 х 16'¹ = Е7.П

(16)

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

Аналогичное правило для восьмеричной системы читатель вы­ведет сам.

31

Представление чисел В ЭВоичном коЭе

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

Действительное число многообразно в своих «потребительских свойствах». Числа могут быть целые точные, дробные точные, раци­ональные, иррациональные, дробные приближенные, числа могут быть положительными и отрицательными. Числа могут быть «кар­ликами», например, масса атома, «гигантами», например, масса Зем­ли, реальными, например, количество студентов в группе, возраст, рост. И каждое из перечисленных чисел потребует для оптимального представления в памяти свое количество байтов.

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

Целые числа. Целые положительные числа от 0 до 255 можно представить непосредственно в двоичной системе счисления (двоич­ном коде). Такие числа будут занимать один байт в памяти компью­тера.

Число	Двоичный код числа
0	0000 0000
1	00000001
2	00000010
3	00000011
• • •	• • •
255	1111 1111

32

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

Если нужны и отрицательные числа, то знак числа может быть закодирован отдельным битом, обычно это старший бит; ноль ин­терпретируется как плюс, единица как минус. В таком случае одним байтом может быть закодированы целые числа в интервале от —127 до +127, причем двоичная арифметика будет несколько усложнена, так как в этом случае существуют два кода, изображающих число ноль 0000 0000 и 1000 0000, и в компьютерах на аппаратном уровне это потребуется предусмотреть. Рассмотренный способ представ­ления целых чисел называется прямым кодом. Положение с отрица­тельными числами несколько упрощается, если использовать, так на­зываемый, дополнительный код. В дополнительном коде положитель­ные числа совпадают с положительными числами в прямом ко­де, отрицательные же числа получаются в результате вычитания из 1 0000 0000 соответствующего положительного числа. Например, чис­ло —3 получит код 1 0000 0000 00000011 1111 1101

В дополнительном коде хорошо реализуется арифметика, так как каждый последующий код получается из предыдущего прибав­лением единицы с точностью до бита в девятом разряде. Например, э — .$ э &~ ^ ^/* 0000 0101 1111 1101

1 0000 0010, т.е., отбрасывая подчеркнутый старший разряд, получим 2.

Аналогично целые числа от 0 да 65536 и целые числа от —32768 до 32767 в двоичной (шестнадцатеричной) системе счисления пред­ставляются в двухбайтовых ячейках. Существуют представления це­лых чисел и в четырехбайтовых ячейках.

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

2. Информатика

О о

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

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

X = т • д^р,

где т — мантисса числа;

Я — основание системы счисления;

р — целое число, называемое порядком.

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

То есть число 4235,25 может быть записано в одном из видов:

4235,25 = 423,525-10¹= 42,3525-10² = 4,23525-10³ = 0,423525-10⁴.

Очевидно, такое представление не однозначно. Если мантисса 1 / я < |т| < я (0,1 < |т| < 1 для десятичной системы счисления), то представление числа становится однозначным, а такая форма назы­вается нормализованной. Если «плавающая» точка расположена в ман­тиссе перед первой значащей цифрой, то при фиксированном коли­честве разрядов, отведенных под мантиссу, обеспечивается запись максимального количества значащих цифр числа, т.е. максимальная точность.

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

32 31 30

24 23 22 21

\

Смещенный порядок

Мантисса

Знак мантиссы

34

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

Порядок числа может быть как положительным, так и отрица­тельным. Чтобы отразить это в двоичной форме, величина порядка представляется в виде суммы истинного порядка и константы, рав­ной абсолютной величине максимального по модулю отрицательно­го порядка, называемой смещением. Например, если порядок может принимать значения от —128 до 127 (8 бит), тогда, выбрав в каче­стве смещения 128, можно представить диапазон значений порядка от 0 (-128+128, порядок + смещение) до 255 (127+128),

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

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

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

Вещественные числа в памяти компьютера, в зависимости от требуемой точности (количества разрядов мантиссы) и диапазона значений (количества разрядов порядка), занимают от четырех до десяти байтов. Например, четырехбайтовое вещественное число име­ет 23 разряда мантиссы (что соответствует точности числа 7—8 деся­тичных знаков) и 8 разрядов порядка (обеспечивающих диапазон значений 10^±38). Если вещественное число занимает десять байтов, то мантиссе отводится 65 разрядов, а порядку — 14 разрядов. Это обес­печивает точность 19—20 десятичных знаков мантиссы и диапазон значений 10^±4931.

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

35

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

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

1.3,2, ЛреЭстоВление символьный

и текстоВын Эаннын В ЭВоичном коЭе

Для передачи информации между собой люди используют знаки и символы. Начав с простейших условных жестов, человек создал це­лый мир знаков, где главным средством общения стал язык (т.е. речь и письменность). Слово есть минимальная первичная единица язы­ка, представляющая собой специальный набор символов и служащая для наименования понятий, предметов, действий и т.п. Следующим по сложности элементом языка является предложение — конструкция, выражающая законченную мысль. На основе предложений строится текст. Текст (от лат. 1ехШ8 — ткань, соединение) - высказывание, выходящее за рамки предложения и представляющее собой единое и целое, наделенное внутренней структурой и организацией в соот­ветствии с правилами языка.

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

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

36

ных (звуков, изображений и др.). Кодом называется уникальное без­знаковое целое двоичное число, поставленное в соответствие неко­торому символу. Под алфавитом компьютерной системы понимают совокупность вводимых и отображаемых символов. Алфавит компь­ютерной системы включает в себя арабские цифры, буквы латинс­кого алфавита, знаки препинания, специальные символы и знаки, буквы национального алфавита, символы псевдографики — растры, прямоугольники, одинарные и двойные рамки, стрелки. Первона­чально для хранения кода одного символа отвели 1 байт (8 битов), что позволяло закодировать алфавит из 256 различных символов. Система, в которой каждому символу алфавита поставлен в соответ­ствие уникальный код, называется кодовой таблицей. Разные произ­водители средств вычислительной техники создавали для одного и того же алфавита символов свои кодовые таблицы. Это приводило к тому, что символы, набранные с помощью одной таблицы кодов, отображались неверно при использовании другой таблицы. Для ре­шения проблемы многообразия кодовых таблиц в 1981 г. Институт стандартизации США принял стандарт кодовой таблицы, получив­шей название А8СП (Атепсап 81апс1агс1 Соёе оГ 1пГогта1юп 1п1егсЬап§е — американский стандартный код информационного об­мена). Эту таблицу использовали программные продукты, работаю­щие под управлением операционной системы М8-ОО8, разработан­ной компанией МюгоБой по заказу крупной фирмы — производителя персональных компьютеров 1ВМ (1п1егпа1юпа1 Визшезд МасЫпе). Широкое распространение персональных компьютеров фирмы 1ВМ привело к тому, что стандарт А8СП приобрел статус международ­ного.

В таблице А8СП содержится 256 символов и их кодов. Таблица состоит из двух частей: основной и расширенной. Основная часть (символы с кодами от 0 до 127 включительно) является базовой, она в соответствии с принятым стандартом не может быть изменена. В нее вошли: управляющие символы (им соответствуют коды с 1 по 31), арабские цифры, буквы латинского алфавита, знаки препинания, специальные символы (табл. 1.1).

Расширенная часть (символы с кодами от 128 до 255) отдана национальным алфавитам, символам псевдографики и некоторым специальным символам. В соответствии с утвержденными стандар-

37

Тоблииа 1.1. Базовая часть таблииы коЭоВ О/СИ

Код		Код		Код		Код		Код		Код		Код		Код
32	пробел	44	>	56	8	68	о	80	Р	92	\	104	Ь	116	1
33	! •	45	_	57	9	69	Е	81	0	93	]	105	» 1	117	и
34	*•	46	•	58	• •	70	Р	82	В	94	.л.	106	• 3	118	V
35	«	47	/	59	• *	71	6	83	8	95	~	107	1<	119	«
36	$	48	0	60	<	72	Н	84	Т	96		108	1	120	X
37	•/,	49	1	61	—	73	I	85	и	97	а	109	т	121	У
38	&	50	2	62	>	74	и	86	V	98	Ь	110	п	122	2
39	У	51	3	63	7 •	75	К	87	И	99	с	111	0	123	{
40	(	52	4	64	@	76	1	88	К	100	с!	112	Р	124	1
41	)	53	5	65	я	77	М	89	V	101	е	113	д	125	}
42	*	54	6	66	в	78	N	90	г	102	?	114	г	126	Л"
43	-1-	55	7	67	с	79	0	91	[	103	9	115	5	127	и

тами эта часть таблицы изменяется в зависимости от национально­го алфавита той страны, где она используется, и способа кодирова­ния. Именно поэтому, при наименовании программ, документов и других объектов желательно использовать латинские буквы, содержа­щиеся в основной, неизменяемой части таблицы, так как русскоязыч­ные имена при несоответствии таблиц кодирования будут неверно отображаться. Например, операционная система \ЭДпс1о\У!5 поддержи­вает большое число расширенных таблиц для различных нацио­нальных алфавитов. В России наиболее распространенной кодовой таблицей алфавита русского языка является «латиница \ЭДпс1о\У5 1251» (табл. 1.2).

В качестве другого примера рассмотрим расширенную таблицу «ГОСТ—альтернативная» (табл. 1.3), на смену которой пришла «ла­тиница Щпёоте 1251».

Во многих странах Азии 256 кодов явно не хватило для кодиро­вания их национальных алфавитов. В 1991 г. производители про­граммных продуктов и организации, утверждающие стандарты, при­шли к соглашению о выработке единого стандарта. Этот стандарт построен по 16 битной схеме кодирования и получил название УМ1СООЕ. Он позволяет закодировать 2¹⁶= 65536 символов, кото­рых достаточно для кодирования всех национальных алфавитов в одной таблице. Так как каждый символ этой кодировки занимает два байта (вместо одного, как раньше), все текстовые документы, пред-

38

Таблииа 1.2. Расширенная таблииа «латинииа Ш|пс1ошу 1251»

39

Таблииа 1.3. Расширенная таблииа «ГОСТ-альтернатиВная»

ставленные в 1Ж1ССЮЕ, стали длиннее в два раза. Современный уровень технических средств нивелирует этот недостаток 1Ж1ССЮЕ.

Текстовые строки. Текстовая (символьная) строка — это конеч­ная последовательность символов. Это может быть осмысленный текст или произвольный набор, короткое слово или целая книга. Длина символьной строки — это количество символов в ней. Запи­сывается в память символьная строка двумя способами: либо число, обозначающее длину текста, затем текст, либо текст, затем — разде­литель строк.

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

1.3.3. Представление зВукоВын Эаннын В ЭВоичном коЗе

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

Во время оцифровки сигнал дискретизируется по времени и по уровню (рис. 1.5.). Дискретизация по времени выполняется следую­щим образом: весь период времени Т разбивается на малые

40

Рис. 1.4. Схема обработки звукового сигнала

X I

Рис. 1.5. Схема дискретизации звукового сигнала

интервалы времени А1, точками I,, 1₂, ... 1_п. Предполагается, что в течение интервала А1 уровень сигнала изменяется незначительно и может с некоторым допущением считаться постоянным. Величина v = 1/Л1 называется частотой дискретизации. Она измеряется в гер­цах (Гц) — количество измерений в течение секунды.

41

Дискретизация по уровню называется квантованием и выполня­ется так: область изменения сигнала от самого малого значения X

гшп

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

Точками Х„ Х₂, ... Х_п. X, = Х^ + АХ • (I - 1).

Каждый квант связывается с его порядковым номером, т.е. це­лым числом, которое легко может быть представлено в двоичной системе счисления. Если сигнал после дискретизации по времени (напомним, его принимаем за постоянную величину) попадает в про­межуток Х_м < X < X, то ему в соответствие ставится код 1.

Возникают две задачи:

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

— вторая: с какой точностью надо измерять сигнал, чтобы полу­ чить при воспроизведении звук удовлетворительного качества. Ответ на первую задачу дает теорема Найквиста, которая утвер­ ждает, что, если сигнал оцифрован с частотой v, то высшая «слыши­ мая» частота будет не более у/2. Вторая задача решается подбором числа уровней так, чтобы звук не имел высокого уровня шума и «электронного» оттенка звучания (точнее, это характеризуется уров­ нем нелинейных искажений). Попутно заметим, что число уровней берется как 2^П. Чтобы измерение занимало целое число байт; v вы­ бирают п = 8 или п = 16, т.е. каждое измерение занимает один или два байта.

Высокое качество воспроизведения получается в формате лазер­ного аудиодиска при следующих параметрах оцифровки: частота дис­кретизации — 44,1 кгц, квантование — 16 бит, т.е. Ах = (Х_тах— Х_т._п)/ 2¹⁶. Таким образом, 1 с стереозвука займет 2 байт • 44100байт/с • • 2 кан • 1 с = 176 400 байт дисковой памяти. Качество звука при этом получается очень высоким.

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

1 байт • 8000 байт/с • 1 с = 8000 байт.

42

1.3,4, Представление графический Заннын В ЭВоичном коЭе

Есть два основных способа представления изображений.

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

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

Модель КСВ. Чтобы оцифровать цвет, его необходимо измерить. Немецкий ученый Грасман сформулировал три закона смешения цве­тов:

1. закон трехмерности — любой цвет может быть представлен ком­ бинацией трех основных цветов;

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

3. закон аддитивности — цвет смеси зависит только от цвета состав­ ляющих.

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

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

голубой (Суап = В + С), дополняющий красного;

пурпурный (Ма§еп1а = К + В), дополняющий зеленого;

желтый (Уе11о\у = К + О), дополняющий синего.

43

Но так как цветные красители по отражающим свойствам не одинаковы, то для повышения контрастности применяется еще чер­ный (Ыас1с). Модель СМУК названа по первым буквам слов Суап, Ма§еп1а, УеПолу и последней букве слова ЫасК. Так как цвета вычи­таются, модель называется субстрактивной.

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

Если для кодирования яркости каждой точки использовать по одному байту (8 бит) на каждый из трех цветов (всего 3 • 8 = 24 бита), то система обеспечит представление 2²⁴« 16,7 млн распознаваемых цветов, что близко цветовосприятию человеческого зрения. Режим представления цветной графики двоичным кодом из 24 разрядов на­зывается полноцветным или Тше Со1ог. Очевидно, графические дан­ные, также как и звуковые, занимают очень большие объемы на но­сителях. Например, скромный по современным меркам экран монитора имеет растр 800 х 600 точек, изображение, представлен­ное в режиме Тте Со1ог, займет 800 х 600 х 3 = 1 440 000 байт.

В случае, когда не требуется высокое качество отображения цве­та, применяют режим НщН Со1ог, который кодирует одну точку рас­тра двумя байтами (16 разрядов дают 2¹⁶ ~ 65,5 тысячи цветов).

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

1,3.5, Понятие сжатия инсрормаиии

Еще одна проблема, тесно связанная с моделями представления информации, — сжатие информации.

При хранении и передаче данных по каналам связи объем ин-

44

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

Разработаны и применяются два типа алгоритмов сжатия: сжа­тие с изменением структуры данных (оно происходит без потери дан­ных) и сжатие с частичной потерей данных. Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмена и Лемпеля-Зива). Алгоритмы второго типа не позволяют полностью вос­становить оригинал и применяются для хранения графики или зву­ка; для текстов, чисел или программ они неприменимы.

1.4. Структуры Эаннын

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

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

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

Если элементы списка одной длины, структура называется век­тором данных, разделители не требуются. При длине одного элемен­та - и, зная номер элемента — п, его начало определяется соотно­шением с! (п—1).

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

45

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

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

с! [М(т - 1) + (п - 1)].

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

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

Иерархическую структуру образуют, например, почтовые адре­са (рис. 1.6).

Россия

Краснодарский край

Ростовская область

^^

Ставропольский край

Большая Садовая

Семикаракорский район

*^

Ворошиловский

Ростов Красносулинский

район

Буденновский

Белокалитвинский район

Рис. 1.6. Пример иерархической структуры данных

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

Россия\Ростовская область\Ростов\ул. Большая Садовая\д. 1.

46

Линейная и табличная структуры более просты, чем иерархичес­кая структура, но если в линейной структуре появляется новый эле­мент, то упорядоченность сбивается. Например, если в списке сту­дентов появляется новый человек, то расположенный по алфавиту список нарушается.

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

1.5. Хранение Эаннын

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

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

Имя файла состоит из некоторого набора символов и для боль-

47

шинства файловых систем может содержать до 256 знаков. Имя фай­ла может быть дополнено расширением, которое определяет тип ин­формации, хранящейся в файле. Расширение содержит от одного до трех символов и отделяется от имени точкой. Большинство программ при создании файла автоматически добавляют к имени свое уникаль­ное расширение, которое помогает им в дальнейшем опознавать «свои» файлы. Например, файлы, созданные программой мгсгобой \Уогс1, имеют расширение .с!ос, расширение .х!§ добавляет программа М1сго8ой Ехсе1.

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

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

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

Для удобства работы файлы объединяют в группы, их имена рас-

48

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

1.6. Математические осноВы информатики

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

1.6.1. Плгебра Высказываний (булеВа алгебра)

Основные понятия

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о кото­ром можно сказать, истинно оно или ложно (третьего не дано). Вы­сказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозна­чим 1). Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» все­гда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержа­тельная часть высказываний, а только их истинность. Два высказы­вания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

49

Логические операиии

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

Операцией отрицания А называют высказывание А (или -А, го­ворят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «зав­тра будет снег», то А «завтра НЕ будет снега», истинность одного

утверждения автоматически означает ложность второго. Отрица­ние — унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ. Это правило можно записать в виде следующей таблицы:

А	А
0	1
1	0

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, ког­да истинны оба высказывания, записывается С == А л В или С = А & В (при этом говорят С равно А и В). Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ши­рина шкафа меньше ширины двери И высота шкафа меньше высо­ты двери», т.е. данная операция применяется, если два высказыва­ния связываются союзом И.

Таблица истинности этой операции, как следует из определения, имеет вид

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

50

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = А v В (при этом говорят: С равно А ИЛИ В). Пример такой операции следующий: пусть вы­сказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на трол­лейбусе», событие С «студент добрался домой на автобусе ИЛИ трол­лейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ.

Таблица истинности такой операции следующая:

А	В	АуВ
0	0	0
0	1	1
1	0	1
1	1	1

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, кото­рое ложно только тогда, когда посылка истинна, а заключение лож­но, записывается С = А —> В (при этом говорят: из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В —> А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

А	В	А->В
0	0	1
0	1	1
1	0	0
1	1	1

Импликация имеет следующие свойства: А-»В *В -> А А-> А= 1

51

0->А= 1 1 -» А = А А-» 1 = 1

А-> 0 = А

Эквиваленцией двух высказываний А и В является новое выска­зывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А <-» В (.С = А = В). Примером такой операции может быть любое выска­зывание типа: событие А равносильно событию В.

Таблица истинности:

А	В	А«->В
0	0	1
0	1	0
1	0	0
1	1	1

Эквиваленция имеет следующие свойства: А<-> В = В<-»А

А <-> В = В <-» А

А*-» 1 =А

А<-»0 = А

Логические Выражения. ПораЭок логический операиий

С помощью логических операций из простых высказываний (ло­гических переменных и констант) можно построить логические вы­ражения, которые также называются булевскими функциями. Напри­мер, С = (( А v В) -> В) v А.

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

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

52

Зависимости межЭу логическими операииами

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

1. А = А закон двойного отрицания

2. А&В = В&А коммутативный закон для конъюнкции

3. АVВ = ВVА коммутативный закон для дизъюнкции

4. (А & В) & С = А & (В & С) ассоциативный закон для конъ­ юнкции

5. (АVВ)VС = АV(ВVС) ассоциативный закон для дизъ­ юнкции

6. А & (В v С) = (А & В) v (А & С) дистрибутивные законы

7. А v (В & С) = (А v В) & (А v С)

8. А&В = А v В законы де Моргана

9. АVВ = А & В

10. А & А = А закон идемпотенции для конъюнкции

11. А v А = А закон идемпотенции для дизъюнкции

12. А & 1 = А закон единицы для конъюнкции

13. А & 0 = 0 закон нуля для конъюнкции

14. А v 1 = 1 закон единицы для дизъюнкции

15. А v 0 = А закон нуля для дизъюнкции

16. А v А = 1 закон исключения третьего

17. А & А = О закон противоречия

18. А -> В = А v В

19. А <-» В = (А -> В) & (В -> А) = ( А v В) & ( А v В ) =

= (А&В^(А & В)

20. А v (А & В) = А законы поглощения

21. А & (А v В) = А

53

22. А & ( А v В) = А & В

23. АV (А & В) = АV В

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

Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид А1 v А2 v ... v Ап, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например:

В = ( А1 & А2 & АЗ) v (А4 & А5).

Вторая — конъюнктивная нормальная форма (КНФ), имеет вид А1 л А2 а ... а Ап, где каждое из составляющих есть дизъюнк­ция простых высказываний и их отрицаний, например:

В = ( А1 v А2 v АЗ) & (А4 v А5) & А6.

Табличное и алгебраическое булеВскин срункиий

Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения: 0 и 1, следовательно, п аргументов могут принимать 2" раз­личных наборов. Пусть, например, булевская функция имеет три ар­гумента: Х_р Х₂, Х₃. Общее число наборов 2³ = 8; зададим таблицу ис­тинности функции, указав для каждого набора значение функции.

№	X,	Х2	Х3	Р
1	0	0	0	0
2	0	0	1	1
3	0	1	0	0
4	0	1	1	1
5	1	0	0	0
6	1	0	1	1
7	1	1	0	0
8	1	1	1	1

54

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

Х₁ &Х₂&Х₃), все элементы соединим знаками дизъюнкции, для рассматриваемого примера получим Р(Х,, Х₂, Х₃) = (X! &Х₂ &Х₃) v

v (Х!&Х₂&Х₃) v (Х,&Х₂&Х₃) v (Х,&Х₂&Х₃).

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

Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму Р(Х,,Х₂,Х₃) =

& ХХХ & ХХуХ & X ^Х~ ^Х кото-

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

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

1.6.2. Элементы теории множеств

Множеством называется любое объединение определенных впол­не различимых объектов; их может и не быть вообще. Можно гово­рить о множестве точек на отрезке [0,1], множестве студентов в груп­пе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку. Объек­ты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается 0. Множество, состоящее из конечного числа эле­ментов, называется конечным, в противном случае — бесконечным.

Задать множество можно перечислением его элементов. Напри­мер, множество образованное из п элементов а,, а₂, ..., а_п , обознача­ется А = {а,, а₂, ..., а_п}; пишется а е А (говорится «элемент а при-

55

надлежит множеству А»), если а является элементом множества А, в противном случае а ё А.

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

Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт А = В.

Множество А₁ называется подмножеством А (записывается А₁сА), если все элементы множества А₁ являются элементами А.

Для множеств определены следующие операции: объединение, пересечение, дополнение.

Объединением множеств А и В (записывается АиВ) называется множество, состоящее из элементов как одного, так и второго мно­жества. Например, А и В — множества точек, принадлежащих неко­торым двум кругам, имеющим общие точки, тогда объединением АиВ будет фигура, состоящая из общих точек.

Пересечением множеств АиВ (записывается АпВ) называется множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно.

Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обо­значается А = В-А (рис. 1.7).

Рис. 1.7. Операции надмножествами

56

1.6.3. Элементы теории гросроВ Основные понятия

Граф задается парой множеств: множества Е, называемого мно­жеством вершин, и множества II, называемого множеством ребер. Ребро и е II есть пара (е., е.), где е., е. е Е , указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро ие II инцидентно вершинам е., е.. Если порядок ребер не имеет значения, т.е. и = (е., е.) = (е., е.), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро и = (е., е.) называется ориентированным ребром или дугой. Вершина е. — назы­вается началом дуги, е. — конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом.

Граф С(Е,Ц) называется конечным, если множество Е вершин конечно.

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

1 ^ ^г ~"Г 7. Р(^е;), где п — количество вершин в графе.

-"^

Рис. 1.8. Ориентированный граф

57

Рассмотрим граф, изображенный на рис. 1.8.

Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер II = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Ребро (5, 3) — является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных сте­пеней для каждой вершины:

р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2;р = (3 + 2 + 3 + + 2 + 2) / 2 = 6.

Важным в теории графов является понятие части графа С(Е,11), который обозначается С'(Е',11') с С(Е,11).

Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа Е' с Е II⁷ с II.

Многие задачи на графах состоят в определении частей графа с заданными свойствами.

Часть графа С'(Е',11') с 6(Е,11) называется подграфом графа 6(Е,11), если Е' с Е , а подмножество II^х с II образовано только реб­рами, инцидентными вершинам множества Е'.

Рис. 1.9. Полный граф

58

Полным графом называется граф С(Е,11), у которого каждая вер­шина ее Е соединена ребрами с остальными вершинами (рис. 1.9).

грасроВ

Маршрутом графа С называется последовательность ребер 8 = = (и_р и₂, ... и_п), в которой каждые два соседних ребра имеют общую вершину, т.е. и,= (е,, е₂); и₂= (е₂, е₃); ... и_п= (е_п, е_п+1). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.

Две вершины е. и е. называются связанными, если существует мар-

^1а $

шрут из е. в е..

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

Рис. 1.10. Компоненты связанности графа

Простой цепью, или простым путем, называется маршрут, в ко­тором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна верши­на не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следу­ющий граф имеет цикл 3 = (1, 2, 3, 5, 4, 1) (рис. 1.11).

59

Рис. 1.11. Цикл в графе

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

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

Задание графа

Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Анали­тическое задание состоит в задании элементов множества вершин Е = {е_р е₂, ... е_п} и множества ребер II = (и_р и₂, ... и_т}.

Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица А размерностью п х п называется матрицей смежности графа С(Е,11), если ее элементы образованы по правилу: элемент матрицы а.= т, если вершины ей е. соединены т ребрами, и а..= 0, если эти верши-

60

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

Матрица А размерностью п х т называется матрицей инцидент­ности графа С(Е,11), если ее элементы образованы по правилу: элемент матрицы Ь.. = 1, если вершина е. инцидентна ребру и. и Ь.. = 0 в про­тивном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.

Построим матрицы смежности и инцидентности для графа, изображенного на рис. 1.12.

а

Рис. 1.12. Пример графа Матрица смежности будет состоять из пяти строк и пяти столбцов.

	1	2	3	4	5
1	0	1	0	1	0
2	1	0	1	1	5
3	0	1	0	0	1
4	1	1	0	0	1
5	0	0	1	1	0

Матрица инцидентности будет состоять из пяти строк и шести столбцов.

	а	Ь	с	с!	е	Г
1	1	1	0	0	0	0
2	1	0	1	0	1	0
3	0	0	1	1	0	0
4	0	1	0	0	1	1
5	0	0	0	1	0	1

61