Вопросы для экзамена по информатике 1 сем. 1. Что такое информация Варианты определения данного понятия и их
 Скачать 2.31 Mb.
|
|
61.Четырехразрядный параллельный регистр на D-триггерах: УГО, внутреннее устройство, выполняемые функции. • условное гос обозначение: • внутреннее устройство: • выполняемые функции: Регистры сдвига могут выполнять функции хранения и преобразования информации. Они могут быть использованы для построения умножителей и делителей чисел двоичной системы счисления, т. к. сдвиг двоичного числа влево на один разряд соответствует умножению его на два, а сдвиг вправо - делению на два. 62. Четырехразрядный регистр с последовательными приемом и выдачей на D- триггерах, с выбором направления сдвига: УГО, внутреннее устройство, варианты использования • условное гос обозначение:? • варианты использования: ? 63.Четырехразрядный регистр с параллельно- последовательным приемом и выдачей, реализующий сдвиг вправо: УГО, внутреннее устройство, варианты использования. • условное гос обозначение:? • внутреннее устройство: 64 .Универсальный сдвиговый регистр: УГО, внутреннее устройство (на примере одного разряда), варианты использования. • условное гос обозначение: • внутреннее устройство: • варианты использования: 65.Счетчики: определение, основные параметры, классификация. Счетчик - это цифровой автомат, реализованный на триггерах. Предназначен для счета входных импульсов и хранения их количества в виде двоичного числа Основные параметры: Модуль счета 𝑀 – максимальное количество единичных импульсов, которое может быть сосчитано счетчиком. Счетчик обнуляется, когда приходит -ый импульс. Шаг счета – приращение значения счетчика при приходе очередного импульса. Направление счета – в сторону увеличения или уменьшения значений. Классификация: По модулю счета: o Двоичные o Двоично-десятичные o С постоянным модулем счета o С переменным модулем счета По шагу счета: 1,2... 𝐾 < 𝑀 По направлению счета: o Суммирующие o Вычитающие o Реверсивные По способу организации межразрядных связей: Счетчики с последовательным переносом (асинхронные счетчики), в которых переключение триггеров разрядных схем осуществляется последовательно один за другим; Счетчики с параллельным переносом (синхронные счетчики), в которых переключение всех триггеров разрядных схем осуществляется одновременно по сигналу синхронизации; Счетчики с комбинированным последовательно- параллельным переносом, при котором используются различные комбинации способов переноса. 66.Счетчики: трехразрядный суммирующий двоичный счетчик на Т-триггерах с последовательным переносом, его таблица истинности, УГО, функциональная схема достоинства и недостатки. Q0(t) Q1(t) Q0(t) 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 : + счетчиков с последовательным переносом: простота схемы; наращивание разрядности осуществляется подключением нужного количества триггеров к выходу последнего триггера. - : Сравнительно низкое быстродействие, т. к. триггеры последовательно срабатывают один за другим;из – за накопления временных сдвигов на выходах таких счетчиков могут появляться кратковременные ложные импульсы. 67.Счетчики: трехразрядный суммирующий двоичный счетчик на Т-триггерах с ускоренным переносом, его таблица истинности, УГО, функциональная схема достоинства и недостатки. Таблица истинности: Q0(t) Q1(t) Q0(t) 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 ▪ УГО ▪ функциональная схема: ▪ достоинства и недостатки: ▪ Достоинства: o Легок в построении ▪ Недостатки o Требуется шифратор и дешифратор 68.Синтез оптимальных счетчиков с требуемым модулем, шагом и направлением на D-триггерах. МДНФ 𝑎𝑏𝑑 ̅̅̅̅̅ + 𝑎𝑏𝑐 ̅̅̅̅̅ + acd 𝑏𝑑̅ + 𝑏𝑐̅ + 𝑎𝑏 ̅̅̅𝑐𝑑 с𝑑̅ + с̅𝑑 69.Быстрый синтез С помощью преобразователя кодов 70. Основы алгоритмизации. Понятие алгоритма, свойства алгоритмов. Алгоритм - это конечная последовательность правил по преобразованию исходных данных задачи в конечный результат Свойства алгоритма • Дискретность. Алгоритм- последовательность, состоящая из конечного числа команд. Вычислительный процесс должен быть разбит на последовательность раздельных шагов. • Понятность. Алгоритм должен быть записан на языке исполнителя. • Детерминированность. Алгоритм должен четко и понятно описывать вычислительный процесс. • Результативность. Алгоритм применим к допустимым исходным данным, если с его помощью можно получить результат за конечное число шагов. • Массовость. Применимость алгоритма к огромному множеству исходных данных. • Корректность. Для всех допустимых исходных данных алгоритм позволяет получить правильный результат и ни для каких исходных данных не дает неправильный результат. • Эффективность, надежность 71. Основы алгоритмизации. Понятие алгоритма, правила построения блок- схем. 72. Основы алгоритмизации. Алгоритм поиска максимума и минимума. Минимум: min=A[0] i=1 ПОКА (i алгоритмизации. Принцип структурного программирования Дейкстры. • Следует отказаться от использования оператора безусловного перехода. • Любая программа строится на основе трех базовых конструкций: действие, условие, цикл. • Базовые конструкции могут быть вложены друг друга в произвольной форме и неограниченном количестве. • Повторяющиеся фрагменты желательно оформлять в виде подпрограмм. • Логически законченные группы инструкций желательно объединять в блоки. • Все перечисленные конструкции должны иметь один вход и один выход. • Разработка программы ведется пошагово, используя метод «сверху-вниз». 74. Основы алгоритмизации. Алгоритм сортировки «Пузырек». i=0 ПОКА (i А[i]=A[j] A[j]=врем j=j+1 i=i+1 75. Основы алгоритмизации. Алгоритм быстрой сортировки Хоара. Обобщенный алгоритм быстрой сортировки: • Выбирается опорный элемент. • Производится разделение массива: • Выбираются два индекса l и r в которые заносятся значения левой и правой границ массива. • Индекс l увеличивается пока l-ый элемент не будет больше или равен опорному. • Индекс r уменьшается пока r-ый элемент не будет меньше или равен опорному. • Если l равен r, то операция разделения закончена. Иначе возвращаемся к шагу 2.2. • Рекурсивно упорядочиваются полученные в результате разделения подмассивы. База рекурсии – пустой массив или массив из одного элемента. procedure Qsort(var x: array of integer;l,r:Integer) ; var p,i,j,temp:Integer; begin p:=x[(r - ((r - l) div 2))]; i:=l;j:=r; while (i <= j) do begin while (x[i] < p) do inc(i); while (x[i] < p) do Dec(j); if (i <= j) then begin temp:= x[i]; x[i] := x[j]; x[j] := temp; inc(i); Dec(j); end; if (i < r) then qSort(x,i, r); if (l < j) then qSort(x,l, j); end; end; 76. Основы алгоритмизации. Рекурсия – назначение, виды, примеры организации. Рекурсией называется вызов функцией самой себя с некоторым изменением входных параметров. Главным условием для использования рекурсии в функциях является наличие базы рекурсии – то есть значения, которое зависит только от входного параметра и позволяет выйти из рекурсии. Еще одним ограничивающим фактором применения простой рекурсии является объем специальной области памяти, где хранится контекст и адреса возврата при вызове функций. При большой глубине рекурсии эта память может быть переполнена, что приведет к ошибке выполнения программы. Вид. хвостовая(бесконечная)-для ее работы нужно, чтобы рекурсивный вызов был последним в теле рекурсивной ф-ции, и чтобы компилятор умели обнаруживать подобный вызов 77. Основы алгоритмизации. Проверка вводимых данных – типичные ошибки и методы борьбы с ними. • Все операнды функций, имеющих ограничения на область допустимых значений (ОДЗ), должны в обязательном порядке проверяться на соответствие ОДЗ. • Память данных и команд в современных ЭВМ в большинстве случаем не разделена и слабо защищена от попадания в чужую область памяти. • Так, объявив массив на 5 элементов можно попытаться обратиться к 6, 10, -5 элементам попав в чужую область памяти и исказив как данные, так и программные коды. • Аналогичные ошибки бывают при копировании данных: • Запрос пользователю: Введите имя • Скопировать в строку введенное имя • При этом размер копируемой области памяти в большинстве случаев определяется длинной введенной строки, без учета размера строки получателя, что приведет к переполнению, если пользователь ввел очень большое имя. • При любых операциях с массивами и памятью необходимо контролировать выход индексных переменных за границы. • При копировании блоков памяти необходимо проверять как размер копируемого блока, так и размер области получателя выбирая минимальное из них или отказываясь от копирования при превышении допустимого объема. • Как уже упоминалось знаковые и беззнаковые переменные это разная интерпретация одних и тех же значений разрядной сетки числа. • Нельзя использовать в одном выражении знаковые и беззнаковые переменные, так как это может привести к непредсказуемой их интерпретации и ошибкам, как следствие того, что знаковое число воспринимается как большое беззнаковое и наоборот. • Перед вычислениями знаковые и беззнаковые числа должны быть принудительно приведены к одной форме. |