Вопросы для экзамена по информатике 1 сем. 1. Что такое информация Варианты определения данного понятия и их
 Скачать 2.31 Mb.
|
|
19.Правила выполнения арифметических операций для чисел с плавающей точкой. Примеры. • Сложение и вычитание: сначала производится выравнивание порядков (меньший по модулю порядок числа увеличивается до величины большего, а мантисса уменьшается в такое же количество порядков), а затем происходит сложение и вычитание мантисс. Пример 0.1*2 5 и 0.1*2 3 + 0.100*2 5 0.001*2 5 –выравнивание порядка 0.101*2 5 - 0.100*2 5 0.001*2 5 0.011*2 5 -нормализация 0.11*2 4 • Умножение: порядки складываются, мантисы перемножаются. 0.1*2 5 0.1*2 3 0.01*2 8 -нормализация 0.1*2 7 • Деление: из порядка делимого вычитается порядок делителя, а мантисса делится на мантиссу делителя. 0.1*2 5 0.1*2 3 1*2 2 -нормализация 0.1*2 3 В конце арифметических действий производится нормализация результата. 20. Представление чисел с плавающей точкой в соответствии со стандартом IEEE754: общие правила представления мантиссы, общие правила представления порядка. • Представление мантиссы В записи числа используется нормализованная мантисса. Стандарт определяет мантиссу следующим образом : она состоит из неяного бита, который всегда равен 1,двоичной точки и остальных разрядов..Получается, что мантисса охватывает диапазон чисел [1, 2). Мантисса представляется в прямом коде. • Представление порядка Порядок числа записывается в смещенном коде, т.е., к нему прибавляется фиксированное число, чтобы порядок был всегда неотрицательным. Это упрощает выполнения операций над порядками, избавляет от знакового разряда порядка. Истинный порядок может быть как положительным, так и отрицательным. Все доступные разряды порядка разделяются поровну между его положительными и отрицательными значениями. При выполнении арифметических операций процессор учитывает сдвиг. Одна комбинация резервируется для специальных нужд. Сдвиг порядка определяется по формуле 2 n-1 -1, где n-порядок (экспонента) 21. Представление чисел с плавающей точкой в соответствии со стандартом IEEE754: формат половинной точности. Всего разрядов 16 Порядок 5 бит Сдвиг порядка 2 5-1 -1=15 22. Представление чисел с плавающей точкой в соответствии со стандартом IEEE754: формат одинарной точности. Всего разрядов 32 Порядок 8 бит Сдвиг порядка 2 8-1 -1=127 23. Алгоритмы перевода чисел из 10ой системы в форматы стандарта IEEE754 и наоборот. 1. Перевести число из K-ичной системы счисления в двоичную (прямой код) 2. Представить двоичной число в нормализованной форме 3. Рассчитать смещенный порядок числа: (𝑛 + 𝑚) 2 , где 𝑚 – смещение, зависящее от формата хранения. 4. Разместить знак, порядок и мантиссу в соответствующие разряды сетки. 5. Разбить полученное число на тетрады и записать полученные двоичные разряды в виде числа в 16-ичной системе. 24. Базовые устройства схемотехники: понятие комбинационной схемы и цифрового автомата, классификация комбинационных схем и простых цифровых автоматов. Комбинационные схемы — это устройства без памяти, принимающие на вход и возвращающие на выходе информационные сигналы в соответствии с их задачей и внутренним устройством. Набор выходных сигналов однозначно определяется набором входных. Цифровой автомат – это логическое устройство, осуществляющее хранение, обработку и получение информации в соответствии с некоторым алгоритмом. Среди комбинационных схем выделяют: • Элементы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, ИСКЛ-ИЛИ • Мультиплексоры и демультиплексоры • Шифраторы • и дешифраторы • Компараторы • Комбинационные сумматоры Простые цифровые автоматы: • Триггеры • Счетчики • Регистры 25. Основы алгебры логики: логическая переменная и логическая функция, способы задания логической функции. Логическая переменная – это переменная, способная хранить значение из множества: ложь, истина. Логическая функция – это функция от набора логических переменных, возвращающая значения на множестве {истина, ложь}. Способы задания логических функций: • Словесный – простое описание функции словами («возвращает Истину, когда две из трех истинны») • Табличный – для каждого набора входных переменных указывается значение функции • Аналитический – функция задается логическим выражением • Векторный – для каждого набора входных переменных в ряд записываются значения функции. • Графический – изображается циклограмма (временная диаграмма). При этом предполагается, что наборы значений подаются на вход устройства в порядке, задаваемом таблицей истинности. • Схемотехнический – задается комбинационная схема (как в Логисиме), которая реализует эту функци 26. Логические функции от двух переменных: названия, таблицы истинности, УГО. 𝒙 𝟏 𝒙 𝟐 𝒇 𝟎 𝒇 𝟏 𝒇 𝟐 𝒇 𝟑 𝒇 𝟒 𝒇 𝟓 𝒇 𝟔 𝒇 𝟕 𝒇 𝟖 𝒇 𝟗 𝒇 𝟏𝟎 𝒇 𝟏𝟏 𝒇 𝟏𝟐 𝒇 𝟏𝟑 𝒇 𝟏𝟒 𝒇 𝟏𝟓 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Заметим, что уникальных функций всего 8. Каждой соответствует инверсированная пара, иными словами: 𝑓 𝑖 = 𝑓 15−𝑖 ̅̅̅̅̅̅, 𝑖 ∈ [0,15]. F 1 (x 1 ,x 2 ) – конъюнкция Элементарная логическая функция (логическое произведение, И). Конъюнкция истинна тогда и только тогда, когда все ее аргументы истинны. F 7 (x 1 ,x 2 ) – дизъюнкция Элементарная логическая функция (логическое сложение, ИЛИ). Дизъюнкция истинна, если хотя бы один ее аргумент истинен. F 6 (x 1 ,x 2 ) – строгая дизъюнкция Сложение по модулю 2, исключающее ИЛИ. Обозначение: ⊕. F 8 (x 1 ,x 2 ) – Элемент Вебба (стрелка Пирса) Реализует функцию ИЛИ-НЕ. Является базисным элементом, т.е. только через ИЛИ-НЕ можно реализовать любую логическую функцию. Возвращает истину, когда все аргументы ложны. Обозначение: ↑. F 14 (x 1 ,x 2 ) – Функция штрих Шеффера Реализует функцию И-НЕ. Является базисным элементом, т.е. только через И-НЕ можно реализовать любую функцию. Обозначение: |. Прочие функции от двух переменных • F 13 – импликация ( 𝑥 1 → 𝑥 2 ) • F 2 – отрицание импликации • F 11 – обратная импликация ( 𝑥 2 → 𝑥 1 ) • F 4 – отрицание обратной импликации • F 12 – отрицание первого аргумента • F 9 – отрицание М2 • F 12 – отрицание второго аргумента 27. Основные понятия алгебры логики: конъюнкт, дизъюнкт, совершенный конъюнкт, совершенный дизъюнкт, минтерм, макстерм, дизъюнктивная форма, конъюнктивная форма. Конъюнкт – конъюнкция некоторых переменных или их отрицаний. Дизъюнкт – дизъюнкция некоторых переменных или их отрицаний. Если конъюнкт (дизъюнкт) состоит из всех переменных функции или их отрицаний, где каждая переменная участвует лишь единожды, то такой конъюнкт (дизъюнкт) называется совершенным. Минтерм– это логическая функция, принимающая значение истина только на одном наборе значений своих аргументов. Формальная запись минтерма – это конъюнкция всех аргументов функции, взятых с отрицанием или без него. Среди множества функций от K переменных есть 2^K минтермов. Минтерм – это совершенный конъюнкт. Макстер – это логическая функция, принимающая значение ложь только на одном наборе значений своих аргументов. Формальная запись макстерама – это дизъюнкция всех аргументов функции, взятых с отрицанием или без него. Среди множества функций от K переменных есть 2^K макстермов. Макстерм – это совершенный дизъюнкт. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конечного числа конъюнктов. Конъюнктивная нормальная форма (КНФ) – конъюнкция конечного числа дизъюнктов 28. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма. Определение. Методы построения. Совершенная ДНФ (СДНФ) – дизъюнкция совершенных конъюнктов (т.е. минтермов). Любая логическая функция, не являющаяся логическим нулем, имеет только одну СДНФ. Совершенная КНФ (СКНФ) – конъюнкция совершенных дизъюнктов (т.е. макстермов). Любая логическая функция, не являющаяся логической единицей, имеет только одну СКНФ. Построение СДНФ по таблице истинности Выписать совершенные конъюнкции и связать их через дизъюнкцию. Построение СКНФ по таблице истинности Выписать совершенные дизъюнкции и связать их через конъюнкцию. 29. Основные логические законы и правила преобразования логических формул. Коммутативный Ассоциативный 𝑋𝑌 = 𝑌𝑋, 𝑋(𝑌𝑍) = (𝑋𝑌)𝑍, 𝑋 + 𝑌 = 𝑌 + 𝑋 𝑋 + (𝑌 + 𝑍) = (𝑋 + 𝑌) + 𝑍 Дистрибутивный Закон двойного отрицания 𝑋(𝑌 + 𝑍) = 𝑋𝑌 + 𝑋𝑍 𝑋̅̅ = 𝑋, 𝑋 + 𝑌𝑍 = (𝑋 + 𝑌)(𝑋 + 𝑍) Закон идемпотентности Правило склеивания 𝑋𝑋 = 𝑋, (𝑋 + 𝑌)(𝑋 + 𝑌̅) = 𝑋 𝑋 + 𝑋 = 𝑋 𝑋𝑌 + 𝑋𝑌̅ = 𝑋, Правило свертки Правило поглощения 𝑋(𝑋̅ + 𝑌) = 𝑋𝑌, 𝑋(𝑋 + 𝑌) = 𝑋 𝑋 + 𝑋̅𝑌 = 𝑋 + 𝑌 𝑋 + 𝑋𝑌 = 𝑋 Законы де Моргана 𝑋|𝑌 = 𝑋𝑌 ̅̅̅̅ = 𝑋̅ + 𝑌̅, 𝑋̅ + 𝑌̅ ̅̅̅̅̅̅̅̅ = 𝑋𝑌, 𝑋 ↑ 𝑌 = 𝑋 + 𝑌 ̅̅̅̅̅̅̅̅ = 𝑋̅𝑌̅ 𝑋 ̅̅̅𝑌̅ ̅̅̅̅̅ = 𝑋 + 𝑌 Правило раскрытия импликации 𝑋 → 𝑌 = 𝑋̅ + 𝑌 Правила раскрытия эквивалентности 𝑋 ≡ 𝑌 = (𝑋 → 𝑌)(𝑌 → 𝑋), 𝑋 ≡ 𝑌 = 𝑋𝑌 + 𝑋̅𝑌̅ Правило раскрытия строгой дизъюнкции 𝑋𝑌 = 𝑋̅𝑌 + 𝑋𝑌̅ 30. Минимизация логических функций: цель минимизации, понятие МДНФ и МКНФ, минимизация методом эквивалентных логических преобразований. Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное ее представление в виде нормальной формы минимальной сложности – минимальной дизъюнктивной нормальной формы (МДНФ) или минимальной конъюнктивной нормальной формы (МКНФ). Минимальная дизъюнктивная нормальная форма – это дизъюнкция минимального числа конъюнкций переменных, взятых с отрицанием или без. Минимальная конъюнктивная нормальная форма – это конъюнкция минимального числа дизъюнкций переменных, взятых с отрицанием или без. Метод эквивалентных логических преобразований заключается в упрощении аналитической формы записи логической функции с помощью законов логики. Например, найдем МДНФ, имея СДНФ некоторой функции: 𝐹 𝐴,𝐵,𝐶 СДНФ = 𝐴̅𝐵𝐶 + 𝐴𝐵̅𝐶 + 𝐴𝐵𝐶̅ + 𝐴𝐵𝐶 = 𝐴̅𝐵𝐶 + 𝐴𝐵̅𝐶 + 𝐴𝐵 = 𝐵(𝐴̅𝐶 + 𝐴) + 𝐴𝐵̅𝐶 = 𝐵(𝐴 + 𝐶) + 𝐴𝐵̅𝐶 = 𝐴𝐵 + 𝐵𝐶 + 𝐴𝐵̅𝐶 = 𝐴𝐵 + 𝐶(𝐵 + 𝐴𝐵̅) = 𝐴𝐵 + 𝐶(𝐴 + 𝐵) = 𝐴𝐵 + 𝐴𝐶 + 𝐵𝐶 31. Минимизация логических функций методом диаграмм Вейча: идея метода, понятие интервала логической функции, формы интервалов, правила выделения интервалов, правила построения диаграммы с целью получения МДНФ функции от 3-х переменных, алгоритм минимизации. Графический способ минимизации логических функций. Работает на основе операций склеивания и поглощения. Представляет собой особым образом переупорядоченную таблицу истинности. В диаграмме Вейча ячейки таблицы истинности сгруппированы таким образом, что переход из одной ячейки в другую по вертикали или горизонтали связан с изменением значения только одной переменной. В результате этого наборы, между которыми возможно склеивание, получаются сгруппированными вместе и их легко заметить. Метод Вейча подходит для минимизации функций до 7 переменных. При большем количестве теряются достоинства метода. Интервал логической функции от 𝐾 переменных – это такое множество наборов значений переменных, что: • Значение функции на этом множестве постоянно; Мощность (величина, размер интервала) этого множества равна 2 𝑁 , 𝑁 ≤ 𝐾; • 𝑁 является количеством переменных, которые упрощаются на этом множестве, а оставшихся ( 𝐾 − 𝑁) переменных достаточно для описания логической функции на данном множестве; • Если 𝑁 > 0, то каждый следующий набор отличается от предыдущего значением только одной переменной. Правила выделения интервалов: • Необходимо стараться выделить максимально большие интервалы; • Каждый новый интервал должен содержать хотя бы одно значение, принадлежащее только ему; • Необходимо выделить минимально возможное количество интервалов. Диаграмма МДНФ для 3 переменных: 𝑦 𝑦̅ 𝑥 𝑓(110) 𝑓(111) 𝑓(101) 𝑓(100) 𝑥̅ 𝑓(010) 𝑓(011) 𝑓(001) 𝑓(000) 𝑧̅ 𝑧 𝑧̅ Алгоритм минимизации: 1. Нарисовать исходную таблицу диаграммы и сделать ее разметку в зависимости от количества переменных функции. 2. Заполнить таблицу значениями функции с учетом цели минимизации (удобно выписывать только 1 для МДНФ и только 0 для МКНФ). 3. Выделить контурами интервалы из единиц (МДНФ) или нулей (МКНФ), соблюдая описанные выше правила. 4. Выписать формулу МДНФ (МКНФ), для чего: a. Для каждого интервала выписать конъюнкт (дизъюнкт), в который будут входить только те переменные или их отрицания, которые сохраняют свое значение на интервале. Остальные переменные упростятся. b. Соединить выписанные конъюнкты (дизъюнкты) через дизъюнкцию (конъюнкцию). - 32.с целью получения МДНФ функции от 4-х переменных, алгоритм минимизации. То же, что вопрос 31, кроме таблицы: 𝑏 𝑏̅ 𝑎 𝑓(1100) 𝑓(1101) 𝑓(1001) 𝑓(1000) 𝑐̅ 𝑓(1110) 𝑓(1111) 𝑓(1011) 𝑓(1010) 𝑐 𝑎̅ 𝑓(0110) 𝑓(0111) 𝑓(0011) 𝑓(0010) 𝑓(0100) 𝑓(0101) 𝑓(0001) 𝑓(0000) 𝑐̅ 𝑑̅ 𝑑 𝑑̅ 33.МКНФ функции от 3-х переменных, алгоритм минимизации. То же, что вопрос 31, кроме таблицы: 𝑦 𝑦̅ 𝑥 𝑓(001) 𝑓(000) 𝑓(010) 𝑓(001) 𝑥̅ 𝑓(101) 𝑓(100) 𝑓(110) 𝑓(111) 𝑧̅ 𝑧 𝑧̅ 34.МКНФ функции от 4-х переменных, алгоритм минимизации. То же, что вопрос 31, кроме таблицы: 𝑏 𝑏̅ 𝑎 𝑓(0011) 𝑓(0010) 𝑓(0110) 𝑓(0111) 𝑐̅ 𝑓(0001) 𝑓(0000) 𝑓(0100) 𝑓(0101) 𝑐 𝑎̅ 𝑓(1001) 𝑓(1000) 𝑓(1100) 𝑓(1101) 𝑓(1011) 𝑓(1010) 𝑓(1110) 𝑓(1111) 𝑐̅ 𝑑̅ 𝑑 𝑑̅ 35.Минимизация частично определенных функций при помощи диаграмм Вейча. В некоторых задачах нам известно, что определенные входные комбинации никогда не возникнут. В таком случае неопределенные значения интерпретируются так, как удобно. Для МДНФ все неопределенности считаем равными 1, для МКНФ – 0. При этом не ставим себе целью покрыть интервалами неопределенные значения, используем их только для поиска больших интервалов единиц (нулей). 36.Приведение минимизированной логической функции к базису «ИЛИ-НЕ». (МДНФ к базису ИЛИ-НЕ) 𝐅 МДНФ = 𝐚𝐜̅ + 𝐛𝐜̅𝐝̅ + 𝐛𝐜𝐝 + 𝐚̅𝐛̅𝐜 + 𝐚̅𝐛̅𝐝 = 𝐚̅ + 𝐜 ̅̅̅̅̅̅̅ + 𝐛̅ + 𝐜 + 𝐝 ̅̅̅̅̅̅̅̅̅̅̅̅ + 𝐛̅ + 𝐜̅ + 𝐝̅ ̅̅̅̅̅̅̅̅̅̅̅̅ + 𝐚 + 𝐛 + 𝐜̅ ̅̅̅̅̅̅̅̅̅̅̅̅ +𝐚 + 𝐛 + 𝐝̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (МКНФ к базису ИЛИ-НЕ) 𝑭 МКНФ = (𝒂 ̅ + 𝒃 + 𝒄̅)(𝒃 ̅ + 𝒄̅ + 𝒅)(𝒂 + 𝒃 + 𝒄 + 𝒅) (𝐚 + 𝐛̅ + 𝐜 + 𝐝̅) = ( 𝒂 ̅ + 𝒃 + 𝒄 ̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ + ( 𝒃 ̅ + 𝒄 ̅ + 𝒅 ) + ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (𝐚 + 𝐛 + 𝐜 + 𝐝) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ + (𝐚 + 𝐛̅ + 𝐜 + 𝐝̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ 37.Приведение минимизированной логической функции к базису «И-НЕ». (МДНФ к базису И-НЕ) F МДНФ = ac̅ + bc̅d̅ + bcd + a̅b̅c + a̅b̅d = = ac̅ ̅ ∗ bc̅d̅ ̅̅̅̅̅ ∗ bcd ̅̅̅̅̅ ∗ a̅b̅c ̅̅̅̅̅ ∗ a̅b̅d ̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (МКНФ к базису И-НЕ) 𝐅 МКНФ = (𝐚̅ + 𝐛 + 𝐜̅)(𝐛̅ + 𝐜̅ + 𝐝)(𝐚 + 𝐛 + 𝐜 + 𝐝) (𝐚 + 𝐚̅ + 𝐜 + 𝐝̅) = 𝐚𝐛̅𝐜 ̅̅̅̅̅ ∗ 𝐛𝐜𝐝̅ ̅̅̅̅̅ ∗ 𝐚̅𝐛̅𝐜̅𝐝̅ ̅̅̅̅̅̅̅ ∗ 𝐚̅𝐛𝐜̅𝐝 ̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ 38. Дешифраторы: определение, УГО, области применения, функциональная схема на примере дешифратора 2-4. Дешифратор – комбинационная схема, обладающая -адресными входами, одним разрешающим входом и 2 𝑛 выходами. На адресные входы подается двоичное число, которое в своем десятичном представлении задает номер выхода, на котором формируется значащий сигнал. Предназначена для преобразования 𝑛-разрядного двоичного кода в унитарный двоичный код разрядности 2 𝑛 В унитарном коде только один разряд из множества может принимать значение 1 (или 0). Это означает, что двоичное число (в своем десятичном представлении) задает номер того выхода, на котором появится 1 (или 0, если выходы инверсные). УГО-Условное графическое обозначение Области применения: • В составе схем управления другими устройствами для последовательной подачи разрешающих сигналов; • В составе схем преобразователей кодов; • Для реализации логических функций. Функциональная схема на примере |