vse-bilearivkty_001

9. Арифметические операции в позиционных системах счисления

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

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

Число единиц какого либо разряд, объединяемых в единицу более старшего разряда, называются основанием позиционной системы счисления. Если количество таких цифр равно Р, то система счисления называется Р-численной. Основания ПСС (позиционной системы счисления) совпадает с количеством цифр, используемых для записи чисел в этой системе счисления

Запись произвольного числа х в Р-численной ПСС основывается на представление этого числа в виде многочлена

Арифметические действия над числами в любой ПСС производтся по тем же правилам, что и в десятичной ПСС

10.Перевод отрицательных чисел в двоичной системе

Алгоритм

1)Модуль отрицательного числа представляем прямым рядом в двоичных разрядах

2)Значение всех бит инвертировать: все 0 заменить на 1, а 1 на 0 ( так получается К разрядный обратный код числа)

3)К полученному обратному подкоду прибавляем единицу

Пример: получить 8и разрядный двоичный код числа -52 00110100число | | в прямом коде

11001011число -52 в обратном коде

11001100число -52 в дополнительном коде

11. Представление чисел в компьютере

Как как как компьютер может различать только 0 и 1 состояния бита, то он работает в системе счисления с основанием 2

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

Целые положительные числа (числа без знака)

Целые числа со знаком

Вещественные нормальные числа

Такие числа можно представлять и в 8й и в 16й системе счисления

12. Представление логических данных, основные понятия

Представлен двумя значениями: истина и ложь. Широко применяется в логических выражениях и выражениях отношения. Здесь есть одна проблема, она связана с машинным представлением логических значений "истина" и "ложь". Дело в том, что в ЭВМ, как правило, нет стандартных представлений логических величин. В ПК минимальная порция информации, обрабатываемая командами, - это байт, в связи с чем на одну логическую переменную обычно и отводят один байт. Но с другой стороны, для представления логического значения достаточно одного бита. Возникает вопрос: как заполнить 8 битов байта, если нужен только 1 бит? Это можно сделать по-разному, каждый может выбрать свой способ заполнения байта, поэтому и нет какого-то одного, стандартного способа представления логических величин. Рассмотрим только некоторые:

13.Законы логики

"Законы логики"

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

Закон тождества. Всякое высказывание тождественно самому себе: А = А

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А — истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: A & ¬A = 0

Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: A v ¬A = 1

Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание: ¬ ¬A = A

Кроме логических законов, важное значение для выполнения преобразований логических выражений имеют правила алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.

Законы Моргана: ¬(A v B)= ¬А & ¬В ¬(A & B)= ¬А v ¬В

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

Логическое умножение	Логическое сложение
A & B = B & A	A v B = A v B

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

Логическое умножение	Логическое сложение
(A & B) & C = A & (B & C)	(A v B) v C = A v (B v C)

Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:

Дистрибутивность умножения	Дистрибутивность сложения
относительно умножения	относительно сложения
(a x b) + (a x c) = a x (b + c)
(A & B) v (A & C) = A & (B v C)	(A v B) & (A v C) = A v (B & C)

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

(А &. В) v (A & ¬В).

Воспользуемся правилом дистрибутивности и вынесем за скобки А:

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

По закону исключенного третьего В v ¬В = 1, следовательно:

А & (В v ¬B) = А &. 1 = А.

14.Базовые логические схемы. Логические элементы ЭВМ

Логические элементы ЭВМ

Логический элемент «И»

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

Логический элемент «ИЛИ»

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

Логический элемент «НЕ»

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

Базовые логические элементы "И", "ИЛИ", "НЕ".

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

Создателем алгебры логики является английский математик Джордж Буль (19 век), в честь которого она названа булевой алгеброй высказываний.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Например, предложение «6 – четное число» - высказывание, так как оно истинное. Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: 1 и

0.

Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и др. (называемые также вентилями), а также триггер.

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

Работу логических элементов описывают с помощью таблиц истинности.

Базовые логические элементы И, ИЛИ, НЕ

Схема И реализует конъюнкцию (логическое умножение) двух или более логических значений.

Эл. схема

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

х	y	х и у

0 0 0

0 1 0

1 0 0

1 1 1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет нуль, на выходе также будет нуль.

Связь между выходом z этой схемы и входами х и у описывается соотношением z = х ^ у (читается как «х и у»).

Операция конъюнкции на функциональных схемах обозначается знаком & (читается как «амперсэнд»), являющимся сокращенной записью английского слова and.

Схема ИЛИ реализует дизъюнкцию (логическое сложение) двух или более логических значений.

Эл. схема

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

х		y		х или у
0		0		0
0		1		1
1		0		10
1		1		1

Когда хотя бы на одном входе схемы ИЛИ будет единица, на ее выходе также будет единица. Знак «1» на схеме — от устаревшего обозначения дизъюнкции как «>=!» (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами х и у описывается соотношением z = х или у.

Схема НЕ (инвертор) реализует операцию отрицания.

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

	х		не х
	0		1
	1		0

15. Структуры данных: массивы, деревья, связный список

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

.

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

Линейный массив. Адрес(элемент(index)) = размер_ячейки * index.

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

Связанный список.

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

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

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

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

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

прямой или префиксный {узел, левое поддерево, правое поддерево};

обратный или постфиксный {левое поддерево, правое поддерево, узел};

симметричный или инфиксный {левое поддерево, узел, правое поддерево};

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

Двоичное (бинарное) дерево.