А) граф g; б) остов графа g; в) другой остов графа g

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

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

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

На рисунке 3.8 показан граф, который является ориентированным деревом с корнем в вершине х₁. Из приведенного определения следует, что ориентированное дерево с п вершинами имеет n-1 дуг и связно. Также очевидно, что не всякий ориентированный граф содержит основное ориентированное дерево. Это подтверждает граф, изображенный на рисунке 3.9.

Рисунок 3.9. Ориентированное дерево

Рисунок 3.10. Граф без ориентированного основного графа

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

Обратно, если Т= (X, В) - ориентированное дерево, то Т = (X, В), где В — множество дуг дерева Т без учета их ориентации, является неориентированным деревом.

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

Контрольные вопросы

1. Что называется множеством?

2. Назовите виды множества.

3. Из чего состоит множества?

4. Охарактеризуйте основные операции над множествами.

5. В каком году был создан аппарат алгебры логики и кем?

6. Что является основным понятием булевой алгебры и дайте его определение?

7. Из чего состоит аппарат булевой алгебры, как формальной математической системы?

8. Охарактеризуйте основные базовые операции булевой алгебры.

9. Какие таблицы истинности Вы знаете?

10. Дайте характеристику аксиомам алгебры логики.

11. Что называется булевой функцией?

12. Чем может быть представлена булевая функция?

13. Приведите формулы логики булевых функций.

14. Дать понятие «графу».

15. Назовите виды графов и дайте их определения.

16. Как определяется число ребер графа?

17. Дайте определения понятиям: «маршрут», «компонента связности», «путь», «цикл», «эйлеровый цикл», «гамильтовый цикл».

18. Как задается граф?

19. Что называется деревом?

20. Какие бывают деревья? Покажите их графически.

Тема 4. Основные понятия архитектуры эвм

4.1. Представление данных в компьютере

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

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

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

Рис. 4.1. Структурные единицы информации

Поле длиной 8 бит называется байтом. Байт, как правило, является минимальной (неделимой) единицей информации, с которой оперирует ЭВМ. Все остальные единицы информации являются его производными (рис. 4.1).

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

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

Байт 0	Байт 1	Байт 2	Байт 3	Байт 4	Байт 5	Байт 6	Байт 7
Полуслово		Полуслово		Полуслово		Полуслово
Слово				Слово
Двойное слово

Рис. 4.2. Форматы единиц информации, обрабатываемых в ЭВМ

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

Последовательность полей, байтов или слов, имеющих одинаковый смысл, образуют массив. Группа массивов может объединяться в сегмент. Количество информации в больших массивах оценивается с помощью производных единиц, кратных количеству байтов в степени числа два (1К байт=1024 байт=2¹⁰ байт; 1М байт= 1048576 байт = =2²⁰ байт).