Информатика конспект лекций_2012

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

Это значит, что сделан точный перевод. В противном случае перевод осуществляется до заданной точности.

Пример 17. Перевести правильную десятичную дробь 0.1875D в двоичную СС.

Решение.

Результат перевода: 0.1875D = 0.0011В.

Обычно перевод дробей из одной СС в другую производят приближенно.

Пример 18. Переведем 0,73410 = N8
Решение.
0,734			0,872		0,976		0,808
8			8		8		8
					7,808	6,464	и т.д.
	5,872			6,976

Результат перевода: 0,73410 ≈0,56768 ≈ 0,5688

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

Пример 19. Самостоятельно перевести десятичное число 9.625D в двоичную СС.

30

Замечание. Для перевода шестнадцатеричного числа в десятичное число: 1) можно вначале шестнадцатеричное число перевести в двоичное, а затем двоичное представить в виде суммы по формуле (1); 2) можно также представить число в виде полинома (по формуле (1)), подставить в него известные коэффициенты и вычислить сумму.

Пример 20. Перевести шестнадцатеричное число 2Е5.АН в десятичную СС.

Решение.

1. 2E5.A16 = 1011100101.1012 = 1·29 + 0·28 + 1·27 + 1·26 + 1·25 + + 0·24 + 0·23 + 1·22 + 0·21 + 1·20 + 1·2-1 + 0·2-2 + 1·2-3 = 512 + 128 +

+ 64 + 32 + 4 + + 1 + 1/2 + 1/8 = 741+5/8 = 741.625.

2.

31

ЛЕКЦИЯ 5. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ

В отличие от аналоговых электронных устройств, в цифровых устройствах (ЦУ) входные и выходные сигналы могут принимать ограниченное количество состояний. В соответствии с логическим соглашением (ГОСТ 2.743-82), в зависимости от конкретной физической реализации элементов ЦУ более положительному значению физической величины, «H»-уровень, соответствует состояние «логическая 1», а менее положительному значению, «L-уровень, – логический 0". Такое соглашение называется положительной логикой. Обратное соотношение называется отрицательной логикой. В ГОСТе 19480 - 89 даны наименования, определения и условные обозначения основных параметров и характеристик цифровых микросхем.

Теоретической основой проектирования ЦУ является алгебра логики, или булева алгебра, оперирующая логическими переменными. Для логических переменных, принимающих только два значения, существуют 4 основных операции.

Операция логическое «И» (AND), конъюнкция, или логическое умножение, обозначается * или /\. Операция логическое «ИЛИ» (OR), дизъюнкция, или логическое сложение, обозначается + или \/. Операция логическое «НЕ» (NOT), изменение значения, инверсия, или отрицание, обозначается чертой над логическим выражением. Иногда в тексте инверсия обозначается знаком «~». Операция эквивалентности обозначается «=».

Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно.

Утверждение – суждение, которое требуется доказать или опровергнуть.

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

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

Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0).

32

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

Логические операции и таблицы истинности

	A	B	F
	0	0	0
	1	1	1
	1	0	0
	0	1	0

F = A & B

Логическое умножение КОНЪЮНКЦИЯ − это новое сложное выражение, которое будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

	A	B	F
	1	1	1
	1	0	1
	0	1	1
	0	0	0

F = A+ B

Логическое сложение ДИЗЪЮНКЦИЯ – это новое сложное выражение, которое будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ.

	A	не А	Логическое отрицание ИНВЕРСИЯ – если ис-
			ходное выражение истинно, то результат отрицания
	1	1
			будет ложным, и наоборот, если исходное выражение
	1	0
			ложно, то результат отрицания будет истинным.

Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

	A	B	F
	1	1	1
	1	0	0
	0	1	1
	0	0	1

Логическое следование ИМПЛИКАЦИЯ – связывает два простых логических выражения, из которых первое является условием (А), а второе (В) – следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом «следовательно» и выражается словами

ЕСЛИ …, ТО …

33

	A	B	F		Логическая равнозначность ЭКВИВАЛЕНТ –
1		1	1		НОСТЬ – определяет результат сравнения двух про-
					стых логических выражений А и В. Результатом ЭК-
1		0	0
					ВИВАЛЕНТНОСТИ является новое логическое вы-
0		1	0
					ражение, которое будет истинным тогда и только то-
0		0	1		гда, когда оба исходных выражения одновременно

истинны или ложны. Обозначается символом «эквивалентность».

Порядок выполнения логических операций в сложном логическом выражении следующий:

1.Инверсия.

2.Конъюнкция.

3.Дизъюнкция.

4.Импликация.

5.Эквивалентность.

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

Построение таблиц истинности для сложных выражений: Количество строк = 2n + две строки для заголовка (n – количе-

ство простых высказываний).

Количество столбцов = количество переменных + количество логических операций.

При построении таблицы надо учесть все возможные сочетания логических значений 0 и 1 исходных выражений. Затем – определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.

Пример. Составить таблицу истинности сложного логического выражения D = не A & (B + C) (табл. 3).

А, В, С – три простых высказывания, поэтому:

-количество строк = 23 + 2 = 10 (n = 3, так как на входе три элемента А, В, С);

-количество столбцов: 1) А; 2) В; 3) С; 4) не A – это инверсия А

(обозначим Е); 5) B + C – это операция дизъюнкции (обозначим F);

6)D = не A & ( B + C ), т.е. D = E & F – это операция конъюнкции.

34

Таблица 3

Таблица истинности логического выражения

D = не A & (B + C)

А	В	С	E = не А (не 1)	F = В+С (2+3)	D = E&F (4*5)
1	1	1	0	1	0
1	1	0	0	1	0
1	o	1	0	1	0
1	o	0	0	0	0
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	1	1
0	0	0	1	0	0

Основные законы логики:

А= А – закон тождества;

А& A = 0 – закон непротиворечия;

A A = 1 – закон исключенного третьего;

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

Свойства констант:			= 1
		0				1 = 0
	А 0			= А	А & 0 = 0
	А 1			= 1	А & 1 = 1

Законы идемпотентности: А А = А А & А = A

Законы коммутативности: А В = В А А & В = В & А

Законы ассоциативности: А (В С) = (А В) С А & (В & С) = (А & В) & С

Законы дистрибутивности: А (В & С) = (А В) & (А С)

А & (В С) = (А & В) (А& С) Законы поглощения: А (А & В) = А

А & (А В) = А

Законы де Моргана:

=

&

A B

A

B

=

A & B

A

B

35

ЛЕКЦИЯ 6. ОСНОВЫ ТЕОРИИ ГРАФОВ

Прежде, чем определить понятие конечного графа в наиболее общей форме, представим себе на плоскости (или в вещественном аффинном пространстве произвольной размерности k) некоторое конечное множество V точек и конечный набор Х линий, соединяющих некоторые пары точек из V. Указанной геометрической конфигурацией описывается, например, схема автомобильных дорог, связывающих города некоторой области (рис. 3).

Рис. 3. Пример схемы автодорог

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

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

рами и петлями (или псевдограф) G = (V, X).

Псевдограф без петель называется графом с кратными ребрами (или мультиграфом), а если в наборе Х ни одна пара не встречается

36

более одного раза, то мультиграф G = (V, X) называется графом. Если пары в наборе Х являются упорядоченными, то граф называется ориентированным (кратко – орграфом). Ребра орграфа называются дугами. Если пары в наборе Х являются неупорядоченными, то граф называется неориентированным графом (или просто графом). Ребра в неориентированном графе (в отличие от дуг в орграфе) будем обозначать {v, w}. Неориентированные графы будем обозначать буквой G или G с индексами (например, G0, G1,...), а орграфы – буквой D или D с индексами (например, D0, D1,...). Кроме того, договоримся обозначать вершины буквами v, u, w (без индексов или с индексами), а ребра и дуги – буквами x, у, z (без индексов или с индексами).

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

Пример 1. Пусть V = {v1, v2, v3, v4}, X = {x1 = (v1, v2), x2 = (v1, v2), x3

= (v2, v2), x4 = (v2, v3)}. Тогда D = (V, X) – ориентированный псевдограф, изображение которого приведено на рис. 4.

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

Пример 2. Пусть V = { v1, v2, v3, v4, v5}, X = { x1 = {v1, v2},

x2 = {v2, v3}, x3= {v2, v4}, x4 = {v3, v4}}. Тогда G = (V, X)− неориенти-

рованный граф (или просто граф), изображение которого дано на рис. 5.

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

37

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

Рис. 5. Неориентированный граф

Смежность, инцидентность, степени

Если x = {v, w} – ребро графа, то вершины v, w называются концами ребра х; в этом случае также говорят, что ребро соединяет вершины v, w.

Если х = (v, w) – дуга орграфа, то вершина v называется началом, а вершина w-концом дуги х; в этом случае также говорят, что дуга х исходит из вершины v и заходит в вершину w.

Если вершина v является концом (началом или концом) ребра (дуги) х, то говорят, что v и х инцидентны.

Вершины v, w графа G = (V, X) называются смежными, если {v, w} X. Два ребра называются смежными, если они имеют общую вершину.

Степенью вершины v графа G называется число δ (v) ребер графа G, инцидентных вершине v. Вершина графа, имеющая степень 0,

называется изолированной, а степень 1 – висячей.

Замечание 1. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, в δ (v) равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Полустепенью исхода (захода) вершины v орграфа D называется

число δ+(v) (δ−(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

38

Замечание 2. В случае ориентированного псевдографа вклад каж-

дой петли, инцидентной некоторой вершине v, равен 1, как в δ+(v), так и в δ−(v).

Пример 3. 1. В графе G (см. пример 2) концами ребра х1 являются вершины v1, v2; вершина v2 инцидентна ребрам х1, х2, х3; степень вер-

шины v2 равна 3, т. е. δ (v2) = 3; вершины v1, v2, смежные, ребра х1, х2 смежные; вершина v1 висячая; вершина v5 изолированная.

2. В ориентированном псевдографе (см. пример 1) дуга х1 исходит из вершины v1 и заходит в вершину v2; вершина v2 инцидентна дугам

х1, х2, х3, х4; δ+(v) = 2, δ−(v) = 3.

Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).

Утверждение 1. Для любого псевдографа G выполняется равенство ∑δ(v)= 2m(G) .

v V

Это равенство является очевидным следствием того, что вклад каждого ребра в сумму из его левой части равен 2.

Приведем также соответствующее утверждение для орграфа. Утверждение 2. Для любого ориентированного псевдографа D

выполняется равенство ∑δ +(v)=	∑δ −(v)= m(D) . Его доказатель-
v V	v V
ство очевидно.

Маршруты, пути

Введем понятие маршрута для графа G = (V, X) (и соответственно понятие пути для орграфа D = (V, X)). Последовательность

v1х1v2х2v3... хkvk + 1, где k ≥ 1, vi V, (i = 1,..., k +1, xj X, j = 1,..., k), в ко-

торой чередуются вершины и ребра (дуги) и для каждого j = 1,..., k

ребро (дуга) xj имеет вид {vj, vj+1} ((vj, vj+1)), называется маршрутом, соединяющим вершины v1, vk+1 (путем из v1 в vk+1). При этом v1 назы-

вается начальной, vk+1 – конечной вершинами маршрута (пути), а остальные вершины – внутренними. Одна и та же вершина может одновременно оказаться начальной, конечной и внутренней. Последовательность вершин в маршруте определяет ориентацию ребер, входящих в маршрут,. Заметим в этой связи, что ориентацию некоторого ребра х = {v,w} всегда можно указать при его записи как пары вершин. Например, запись {v, w} указывает на то, что ребро х ориентировано от вершины v к вершине w.

39