Конспект лекций архитектура аппаратных средств. 10.-Конспекты-лекций.-ОП.02-Арх-итектура-аппаратных-средств.-09.. Конспекты лекций по дисциплине
 Скачать 0.6 Mb.
|
|
ключ-значение, а коллекция таких элементов называется словарем. Каждый объект можно найти с помощью его ключа. Существует несколько структур, основанных на хешировании, но наиболее часто используется хеш-таблица, которая обычно реализуется с помощью массивов. Производительность структуры зависит от трех факторов: функция хеширования; размер хеш-таблицы; метод обработки коллизий. Вот иллюстрация того, как хэш отображается в массиве. Индекс вычисляется с помощью хеш-функции. Часто задаваемые вопросы о хеш-таблицах Найти симметричные пары. Определить, является ли массив подмножеством другого массива. Проверить, являются ли массивы непересекающимися. Теперь вы знаете 8 основных структур данных любого языка программирования. Можете смело отправляться на IT-собеседование. Контрольные вопросы: 1. Каие типы данных бывают?; 2. Что такое Массив (Array)? 3. Что такое Стек (Stack)? 4. Что такое Очередь (Queue)? 5. Что такое Связный список (Linked List)? 6. Что такое Дерево (Tree)? 7. Что такое Граф (Graph)? ЛЕКЦИЯ 3 Системы счисления. Непозиционные и позиционные системы счисления. Свойства позиционных систем счисления. План. 1. Контрольный опрос 2. Системы счисления 3. Непозиционные и позиционные системы счисления 4. Свойства систем счисления Система счисления — это способ записи (представления) чисел. Что под этим подразумевается? Например, вы видите перед собой несколько деревьев. Ваша задача — их посчитать. Для этого можно — загибать пальцы, делать зарубки на камне (одно дерево — один палец\зарубка) или сопоставить 10 деревьям какой-нибудь предмет, например, камень, а единичному экземпляру — палочку и выкладывать их на землю по мере подсчета. В первом случае число представляется, как строка из загнутых пальцев или зарубок, во втором — композиция камней и палочек, где слева — камни, а справа — палочки Системы счисления подразделяются на позиционные и непозиционные, а позиционные, в свою очередь, — на однородные и смешанные. Непозиционная — самая древняя, в ней каждая цифра числа имеет величину, не зависящую от её позиции (разряда). То есть, если у вас 5 черточек — то число тоже равно 5, поскольку каждой черточке, независимо от её места в строке, соответствует всего 1 один предмет. Позиционная система — значение каждой цифры зависит от её позиции (разряда) в числе. Например, привычная для нас 10-я система счисления — позиционная. Рассмотрим число 453. Цифра 4 обозначает количество сотен и соответствует числу 400, 5 — кол-во десяток и аналогично значению 50, а 3 — единиц и значению 3. Как видим — чем больше разряд — тем значение выше. Итоговое число можно представить, как сумму 400+50+3=453. Однородная система — для всех разрядов (позиций) числа набор допустимых символов (цифр) одинаков. В качестве примера возьмем упоминавшуюся ранее 10-ю систему. При записи числа в однородной 10-й системе вы можете использовать в каждом разряде исключительно одну цифру от 0 до 9, таким образом, допускается число 450 (1-й разряд — 0, 2-й — 5, 3-й — 4), а 4F5 — нет, поскольку символ F не входит в набор цифр от 0 до 9. Смешанная система — в каждом разряде (позиции) числа набор допустимых символов (цифр) может отличаться от наборов других разрядов. Яркий пример — система измерения времени. В разряде секунд и минут возможно 60 различных символов (от «00» до «59»), в разряде часов – 24 разных символа (от «00» до «23»), в разряде суток – 365 и т. д. Непозиционные системы Как только люди научились считать — возникла потребность записи чисел. В начале все было просто — зарубка или черточка на какой-нибудь поверхности соответствовала одному предмету, например, одному фрукту. Так появилась первая система счисления — единичная. Единичная система счисления Число в этой системе счисления представляет собой строку из черточек (палочек), количество которых равно значению данного числа. Таким образом, урожай из 100 фиников будет равен числу, состоящему из 100 черточек. Но эта система обладает явными неудобствами — чем больше число — тем длиннее строка из палочек. Помимо этого, можно легко ошибиться при записи числа, добавив случайно лишнюю палочку или, наоборот, не дописав. Для удобства, люди стали группировать палочки по 3, 5, 10 штук. При этом, каждой группе соответствовал определенный знак или предмет. Изначально для подсчета использовались пальцы рук, поэтому первые знаки появились для групп из 5 и 10 штук (единиц). Все это позволило создать более удобные системы записи чисел. Римская система Римская система не сильно отличается от египетской. В ней для обозначения чисел 1, 5, 10, 50, 100, 500 и 1000 используются заглавные латинские буквы I, V, X, L, C, D и M соответственно. Число в римской системе счисления — это набор стоящих подряд цифр. Методы определения значения числа: 1. Значение числа равно сумме значений его цифр. Например, число 32 в римской системе счисления имеет вид XXXII=(X+X+X)+(I+I)=30+2=32 2. Если слева от большей цифры стоит меньшая, то значение равно разности между большей и меньшей цифрами. При этом, левая цифра может быть меньше правой максимум на один порядок: так, перед L(50) и С(100) из «младших» может стоять только X(10), перед D(500) и M(1000) — только C(100), перед V(5) — только I(1); число 444 в рассматриваемой системе счисления будет записано в виде CDXLIV = (D-C)+(L-X)+(V-I) = 400+40+4=444. 3. Значение равно сумме значений групп и цифр, не подходящих под 1 и 2 пункты. Помимо цифирных, существуют и буквенные (алфавитные) системы счисления, вот некоторые из них: 1) Славянская 2) Греческая (ионийская) Позиционные системы счисления Как упоминалось выше — первые предпосылки к появлению позиционной системы возникли в древнем Вавилоне. В Индии система приняла форму позиционной десятичной нумерации с применением нуля, а у индусов эту систему чисел заимствовали арабы, от которых её переняли европейцы. По каким-то причинам, в Европе за этой системой закрепилось название “арабская”. Десятичная система счисления Это одна из самых распространенных систем счисления. Именно её мы используем, когда называем цену товара и произносим номер автобуса. В каждом разряде (позиции) может использоваться только одна цифра из диапазона от 0 до 9. Основанием системы является число 10. Для примера возьмем число 503. Если бы это число было записано в непозиционной системе, то его значение равнялось 5+0+3 = 8. Но у нас — позиционная система и значит каждую цифру числа необходимо умножить на основание системы, в данном случае число “10”, возведенное в степень, равную номеру разряда. Получается, значение равно 5*10 2 + 0*10 1 + 3*10 0 = 500+0+3 = 503. Чтобы избежать путаницы при одновременной работе с несколькими системами счисления основание указывается в качестве нижнего индекса. Таким образом, 503 = 503 10 Помимо десятичной системы, отдельного внимания заслуживают 2-, 8-, 16-ая системы. Двоичная система счисления Эта система, в основном, используется в вычислительной технике. Почему не стали использовать привычную нам 10-ю? Первую вычислительную машину создал Блез Паскаль, использовавший в ней десятичную систему, которая оказалась неудобной в современных электронных машинах, поскольку требовалось производство устройств, способных работать в 10 состояниях, что увеличивало их цену и итоговые размеры машины. Этих недостатков лишены элементы, работающие в 2-ой системе. Тем не менее, рассматриваемая система была создана за долго до изобретения вычислительных машин и уходит “корнями” в цивилизацию Инков, где использовались кипу — сложные верёвочные сплетения и узелки. Двоичная позиционная система счисления имеет основание 2 и использует для записи числа 2 символа (цифры): 0 и 1. В каждом разряде допустима только одна цифра — либо 0, либо 1. Примером может служить число 101. Оно аналогично числу 5 в десятичной системе счисления. Для того, чтобы перевести из 2-й в 10-ю необходимо умножить каждую цифру двоичного числа на основание “2”, возведенное в степень, равную разряду. Таким образом, число 101 2 = 1*2 2 + 0*2 1 + 1*2 0 = 4+0+1 = 5 10 Хорошо, для машин 2-я система счисления удобнее, но мы ведь часто видим, используем на компьютере числа в 10-й системе. Как же тогда машина определяет какую цифру вводит пользователь? Как переводит число из одной системы в другую, ведь в её распоряжении всего 2 символа — 0 и 1? Чтобы компьютер мог работать с двоичными числами (кодами), необходимо чтобы они где-то хранились. Для хранения каждой отдельной цифры применяется триггер, представляющий собой электронную схему. Он может находится в 2-х состояниях, одно из которых соответствует нулю, другое — единице. Для запоминания отдельного числа используется регистр — группа триггеров, число которых соответствует количеству разрядов в двоичном числе. А совокупность регистров — это оперативная память. Число, содержащееся в регистре — машинное слово. Арифметические и логические операции со словами осуществляет арифметико-логическое устройство (АЛУ). Для упрощения доступа к регистрам их нумеруют. Номер называется адресом регистра. Например, если необходимо сложить 2 числа — достаточно указать номера ячеек (регистров), в которых они находятся, а не сами числа. Адреса записываются в 8- и 16-ричной системах (о них будет рассказано ниже), поскольку переход от них к двоичной системе и обратно осуществляется достаточно просто. Для перевода из 2-й в 8-ю число необходимо разбить на группы по 3 разряда справа налево, а для перехода к 16-ой — по 4. Если в крайней левой группе цифр не достает разрядов, то они заполняются слева нулями, которые называются ведущими. В качестве примера возьмем число 101100 2 . В восьмеричной — это 101 100 = 54 8 , а в шестнадцатеричной — 0010 1100 = 2С 16 . Отлично, но почему на экране мы видим десятичные числа и буквы? При нажатии на клавишу в компьютер передаётся определённая последовательность электрических импульсов, причём каждому символу соответствует своя последовательность электрических импульсов (нулей и единиц). Программа драйвер клавиатуры и экрана обращается к кодовой таблице символов (например, Unicode, позволяющая закодировать 65536 символов), определяет какому символу соответствует полученный код и отображает его на экране. Таким образом, тексты и числа хранятся в памяти компьютера в двоичном коде, а программным способом преобразуются в изображения на экране. Восьмеричная система счисления 8-я система счисления, как и двоичная, часто применяется в цифровой технике. Имеет основание 8 и использует для записи числа цифры от 0 до 7. Пример восьмеричного числа: 254. Для перевода в 10-ю систему необходимо каждый разряд исходного числа умножить на 8 n , где n — это номер разряда. Получается, что 254 8 = 2*8 2 + 5*8 1 + 4*8 0 = 128+40+4 = 172 10 Шестнадцатеричная система счисления Шестнадцатеричная система широко используется в современных компьютерах, например при помощи неё указывается цвет: #FFFFFF — белый цвет. Рассматриваемая система имеет основание 16 и использует для записи числа: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B. C, D, E, F, где буквы равны 10, 11, 12, 13, 14, 15 соответственно. В качестве примера возьмем число 4F5 16 . Для перевода в восьмеричную систему — сначала преобразуем шестнадцатеричное число в двоичное, а затем, разбив на группы по 3 разряда, в восьмеричное. Чтобы преобразовать число в 2-е необходимо каждую цифру представить в виде 4-х разрядного двоичного числа. 4F5 16 = (100 1111 101) 2 . Но в 1 и 3 группах не достает разряда, поэтому заполним каждый ведущими нулями: 0100 1111 0101. Теперь необходимо разделить полученное число на группы по 3 цифры справа налево: 0100 1111 0101 = 010 011 110 101. Переведем каждую двоичную группу в восьмеричную систему, умножив каждый разряд на 2 n , где n — номер разряда: (0*2 2 +1*2 1 +0*2 0 ) (0*2 2 +1*2 1 +1*2 0 ) (1*2 2 +1*2 1 +0*2 0 ) (1*2 2 +0*2 1 +1*2 0 ) = 2365 8 Помимо рассмотренных позиционных систем счисления, существуют и другие, например: 1) Троичная 2) Четверичная 3) Двенадцатеричная Позиционные системы подразделяются на однородные и смешанные. Однородные позиционные системы счисления Определение, данное в начале статьи, достаточно полно описывает однородные системы, поэтому уточнение — излишне. Смешанные системы счисления К уже приведенному определению можно добавить теорему: “если P=Q n (P,Q,n – целые положительные числа, при этом P и Q — основания), то запись любого числа в смешанной (P-Q)-ой системе счисления тождественно совпадает с записью этого же числа в системе счисления с основанием Q.” Опираясь на теорему, можно сформулировать правила перевода из P-й в Q-ю системы и наоборот: 1. Для перевода из Q-й в P-ю, необходимо число в Q-й системе, разбить на группы по n цифр, начиная с правой цифры, и каждую группу заменить одной цифрой в P- й системе. 2. Для перевода из P-й в Q-ю, необходимо каждую цифру числа в P-й системе перевести в Q-ю и заполнить недостающие разряды ведущими нулями, за исключением левого, так, чтобы каждое число в системе с основанием Q состояло из n цифр. Яркий пример — перевод из двоичной системы счисления в восьмеричную. Возьмем двоичное число 10011110 2 , для перевода в восьмеричное — разобьем его справа налево на группы по 3 цифры: 010 011 110, теперь умножим каждый разряд на 2 n , где n — номер разряда, 010 011 110 = (0*2 2 +1*2 1 +0*2 0 ) (0*2 2 +1*2 1 +1*2 0 ) (1*2 2 +1*2 1 +0*2 0 ) = 236 8 Получается, что 10011110 2 = 236 8 . Для однозначности изображения двоично- восьмеричного числа его разбивают на тройки: 236 8 = (10 011 110) 2-8 Смешанными системами счисления также являются, например: 1)Факториальная 2) Фибоначчиева Контрольные вопросы: 1. Зачем нужны системы счисления? 2. Какие системы счисления вы знаете? 3. Как переводить числа из одной системы счисления в другую? ЛЕКЦИЯ 4 Логические операции и базовые элементы компьютера. Винтили. Таблицы истинности. План. 1. Контрольный опрос 4. Логические операции 5. базовые элементы компьютера. 6. Таблицы истинности. Высказывание - это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)). Логические операции - мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий. Логическое выражение - устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0). Сложное логическое выражение - логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций. Логические операции и таблицы истинности 1) Логическое умножение или конъюнкция: Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложенное выражение ложно. Обозначение: F = A & B. Таблица истинности для конъюнкции A B F 1 1 1 1 0 0 0 1 0 0 0 0 2) Логическое сложение или дизъюнкция: Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженbя ложны. Обозначение: F = A v B. Таблица истинности для дизъюнкции A B F 1 1 1 1 0 1 0 1 1 0 0 0 3) Логическое отрицание или инверсия: Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Обозначение: F = ¬A. Таблица истинности для инверсии A ¬ А 1 0 0 1 4) Логическое следование или импликация: Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием. «A → B» истинно, если из А может следовать B. Обозначение: F = A → B. Таблица истинности для импликации A B F 1 1 1 1 0 0 0 1 0 0 0 1 5) Логическая равнозначность или эквивалентность: Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность. «A ↔ B» истинно тогда и только тогда, когда А и B равны. Обозначение: F = A ↔ B. Таблица истинности для эквивалентности A B F 1 1 0 1 0 1 0 1 1 0 0 0 6) Операция XOR (исключающие или) «A ⊕ B» истинно тогда, когда истинно А или B, но не оба одновременно. Эту операцию также называют "сложение по модулю два". Обозначение: F = A ⊕ B. A B F 1 1 0 1 0 1 0 1 1 0 0 0 Порядок выполнения логических операций в сложном логическом выражении 1. Инверсия; 2. Конъюнкция; 3. Дизъюнкция; 4. Импликация; 5. Эквивалентность. Для изменения указанного порядка выполнения логических операций используются скобки. Таблицы истинности можно составить и для произвольной логической функции F(a, b, c…). В общем случае таблицы истинности имеют размер 2 N строк комбинаций для N независимых логических переменных. Поскольку таблица истинности выражения состоит из строк со всеми возможными комбинациями значений переменных, она полностью определяет значение выражения. Законы алгебры логики Те, кому лень учить эти законы, должны вспомнить алгебру, где знание нескольких способов преобразования позволяет решать очень сложные уравнения. Строго говоря, это не законы, а теоремы. Но их доказательство не входит в программу изучения. Впрочем, доказательство обычно основывается на построении полной таблицы истинности. Замечание. Знаки алгебры логики намеренно заменены на сложение и умножение. № Для ИЛИ, \/ Для И, & Примечание 1 A \/ 0 = A A & 1 = A Ничего не меняется при действии, константы удаляются 2 A \/ 1 = 1 A & 0 = 0 Удаляются переменные, так как их оценивание не имеет смысла 3 A \/ B = B \/ A AB = BA Переместительный (коммутативности) 4 A \/ ¬A = 1 Один из операторов всегда 1 (закон исключения третьего) 5 A & ¬A = 0 Один из операторов всегда 0 (закон непротиворечия) 6 A \/ A = A A & A = A Идемпотентности (NB! Вместо A можно подставить составное выражение!) 7 ¬¬А = A Двойное отрицание 8 (A \/ B) \/ C = A \/ ( B \/ C) (A /\ B) /\ C = A /\ (B /\ C) Ассоциативный 9 (A \/ B)&C=(A&C)\ /(B&C) (A&B) \/ C = (A \/ C)& (B \/ C) Дистрибутивный 1 0 (A \/ B)&(¬A \/ B) = B (A&B) \/ (¬A&B) = B Склеивания 1 1 ¬(A \/ B) = ¬A &¬B ¬(A&B) = ¬A \/ ¬B Правило де Моргана 1 2 A \/ (A&C) = A A&(A \/ C) = A Поглощение 1 3 A→B = ¬A \/ B и A→B = ¬B→¬A Снятие (замена) импликации 1 4 1) A↔B = (A&B) \/ (¬A&¬B) 2) A↔B = (A \/ ¬B)&(¬A \/ B) Снятие (замена) эквивалентности |