Топологическая сортировка.

Топологическая сортировка (ТС) вершин орграфа G заключается в присвоении его вершинам чисел 1, 2,…, | x |, причем должно выполняться следующее условие для орграфов: если имеется дуга (x_i, x_j), то j > i (i  j).

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

4 3

5

1. 2

6

2 4

3

1 6

5

Поиск ведем на множестве узлов графа:

Топологически неотсортированный граф

Топологически отсортированный граф

1 2 3 4 5 6

Топологическая сортировка может быть использована:

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

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

Рассмотрим алгоритм топологической сортировки. Идея его заключается в том, что осуществляется поиск такой вершины, из которой не выходит ни одна дуга. Такой вершине присваивается | x |. Затем эту вершину выбрасывают вместе с дугами и опять осуществляют поиск на | x | - 1, …

Введем массив LABEL размерностью | x |. Он будет обладать следующими свойствами: если вершина не выброшена, то значение LABEL(x)=0; если есть дуга (x_i, x_j), то LABEL(x _j) > LABEL(x _i).

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

 x  X выполнить: (Num(x)=1; LABEL(x)=0;)

C = | x | + 1;

 x  X выполнить: если Num(x)=1, то DM(x);

Процедура DM(v);

начало

Num(V)=0;

 t  M(V) выполнить: если Num(t)=1, то DM(t);

конец;

C = C – 1;

LABEL(V) = C;

Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.

В

регистры

КЭШ

основная

вторичная

архивная

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

память процессора

внешняя память

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

Основными характеристиками устройств внешней памяти являются:

1. емкость;

2. время доступа;

3. скорость передачи данных;

4. форма доступа;

5. экономическая характеристика (стоимость хранения в расчете на одну единицу данных).

Время доступа – длительность интервала времени от момента инициирования операции ввода / вывода, до начала передачи данных. Скорость передачи данных измеряется числом единиц данных, передаваемых между устройствами внешней и основной памяти (1 бод = 1 символ / 1 c). Форма доступа – порядок, в котором можно записывать или читать из устройства внешней памяти. Доступ может быть последовательным, прямым, и т.д. При прямом доступе время доступа не зависит от размерности структуры.

Накопители на магнитных дисках.

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

Р

Таблица размещения файлов

ассмотрим структуру диска:

данные

5 6 7 конец

программа начальной загрузки

корневой каталог файлов

1 2 3 4 5 6 7 8

таблица размещения файлов

Корневой каталог содержит: имя файла, номер первого кластера. Кластер – минимальная порция информации, включающая несколько сегментов.

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

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