Иерархические структуры данных

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

систематизациях и всевозможных классификациях (рис. 1.5).

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

программа компьютеров, работающих в операционной системе Windows 98):

Пуск • Программы • Стандартные • Калькулятор.

30 Глава 1. Информация и информатика

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

Системные

программы

Служебные

программы

Системы управления

базами данных

т Векторные

редакторы

Adobe Illustrator 8.0 CorelDRAW9.0

Прикладные

программы

Растровые

редакторы

Macromedia

Freehand 8.01

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

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

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

Информационное обеспечение

Прикладные программы. Не прикладные программы

Графические редакторы. Не графические редактор

Текстовые процессоры. Не текстовые процессоры

Текстовый процессор WordPad.Текстовый процессор Word2000

Рис. 1.6. Пример, поясняющий принцип действия метода дихотомии

В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной

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

Понятие о файловой структуре

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

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

(папок), через которые проходит. В качестве разделителя используется символ «\» (обратная косая черта).

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

<имя носителя>\<имя каталога-1>\...\<имя каталога-М>\<собствениое имя файла>

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

С:\АВТ0МАТИЧЕСКИЕАППАРАТЫ\ВЕНЕРА\АТМ0СФЕРА\Результаты исследований

С:\РАДИОЛОКАЦИЯ\ВЕНЕРА\РЕЛЬЕФ\Результаты исследований

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

Единицы измерения данных

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

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

чение представляет рассмотренная выше универсальная кодировка UNICODE). Более крупная единица измерения — килобайт (Кбайт). Условно можно считать,что 1 Кбайт примерно равен 1000 байт. Условность связана с тем, что для вычислительной техники, работающей с двоичными числами, более удобно представление чиселв виде степени двойки и потому на самом деле 1 Кбайт равен 2^^ байт (1024 байт).

Однако всюду, где это не принципиально, с инженерной погрешностью (до 3 %) «забывают» о «лишних» байтах.

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

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

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

1 Мбайт = 1024 Кбайт = 10^^ байт

1 Гбайт = 1024 Мбайт = 10^^ байт

1 Тбайт = 1024 Гбайт = 10^^ байт

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

Единицы хранения данных

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

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

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

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

Методы классификации компьютеров

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

Классификация по назначению

Классификация по назначению — один из наиболее ранних методов классификации. Он связан с тем, как компьютер применяется. По этому принципу различают большие ЭВМ {электронно-вычислительные машины), мини-ЭВМ, микро-ЭВМ и

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

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

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

Группа подготовки данных

Группа системного программирования

Рис. 2.6. Структура современного вычислительного центра на базе большой ЭВМ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классификация по типоразмерам. Персональные компьютеры можно классифицировать по типоразмерам. Так, различают настольные {desktop), портативные (notebook) и карманные (palmtop) модели. Настольные модели распространены наиболее широко. Они являются принадлежностью рабочего места. Эти модели отличаются простотой изменения конфигурации

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

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

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

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

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

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

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

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

на другой и возможность совместной работы разных типов компьютеров с одними и теми же данными. Аппаратная совместимость. По аппаратной совместимости различают так называемые аппаратные платформы. В области персональных компьютеров сегодня наиболее широко распространены две аппаратные платформы — IBM PC vi Apple Macintosh. Кроме них существуют и другие платформы, распространенность которых

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

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

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

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

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

Мини-ЭВМ

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

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

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

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

Микро-ЭВМ

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

вычислительным центрам или специализированным организациям.

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

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

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

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

предварительная подготовка данных.