ДМ 2012 / Инд. задание к самостоятельной работе 2012 (ДМ РБ) / (Л4) Якимов_ДискретнаяМатематика_МУ

31

движется на самый нижний из этажей, на которых нажаты кнопки. Ни одна кнопка не может быть нажата во время движения лифта (x – этаж, на котором нажата кнопка, y – направление, в котором будет двигаться лифт, и число этажей, которое он при этом пройдет без остановки).

14 На рисунке 26 изображена схема N, на которую поступают сигналы от двух импульсных генераторов напряжения V1 и V2. Каждый генератор генерирует положительный или отрицательный импульс с периодом одна микросекунда.

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

Рисунок 26 – Схема устройства с задержками на входе

15 Работа вычислительного устройства, имеющего вход x и выход y, определяется следующими уравнениями:

yi = xi yi−1 xi−1; qi = xi qi−1 ,

где каждая переменная принимает значения 0 или 1; знак обозначает сложение по модулю 2.

16 На рисунке 27 представлена модель нервной сети, где нервное волокно соединено с источником, который генерирует стимулы 0 или 1 в моменты времени ti.

Большой кружок представляет нейрон. Выход нейрона в момент времени ti возбужден, т. е. принимает значение единица, только в том случае, когда разность между числом его возбужденных «возбуждающих входов» (показаны зачерненными маленькими кружками) и числом возбужденных «тормозящих входов» (показаны маленькими кружками) в момент ti = 1 равна или превышает его «порог» (число, записанное внутри большого кружка). При решении принять x = Vвх, y = Vвых.

32

Рисунок 27 – Модель нервной сети

17 На вход автомата могут поступать сигналы R, S и C. На входной сигнал R автомат выдает выходной сигнал 0, на S – выходной сигнал 1 и на C – выходной сигнал, противоположный предыдущему выходному сигналу. Для определенности полагают, что в начальном состоянии автомат помнит «предыдущий» выходной сигнал 0.

18 Автомат имеет две входные шины x1 и x2, на которые в дискретные моменты независимо друг от друга могут поступать сигналы 0 или 1. В автомате вычисляется функция f = x1 x2, а затем определяется, сколько раз с учетом данного момента времени функция f принимала значение 1. Выходной сигнал y может иметь три значения: y = 0,если f = 0; y = 1, если f = 1 и суммарное число случаев, включая данный, когда f равнялась единице, нечетно; y = 2 – в остальных случаях.

19 Автомат управляет светофором на перекрестке дорог «вертикаль- ная–горизонтальная». Считается, что при открытом светофоре (зеленом свете) машины преодолевают перекресток мгновенно. Светофор переключается (мгновенно), если число ожидающих машин с обеих сторон перпендикулярной улицы достигло трех.

20 Автомат Мура, принимая на входе монеты 10; 15 и 20 коп., выдает сигнал П, если значение текущей суммы опущенных монет кратно 50 и не кратно 1 р.; выдает сигнал Р, если сумма кратна 1 р.; во всех остальных случаях выдает сигнал 0.

21 На вход автомата по двум шинам x1 и x2 поступают различные комбинации из нулей и единиц, воспринимаемые как двоичные числа. Автомат выдает сигнал Н , если сумма поступивших чисел нечетная, К – если сумма чисел кратная четырем, и 4 – если сумма чисел четная, но не кратна четырем.

22 Синтезировать автомат, на вход которого могут поступать в любой последовательности и, возможно, с любым числом повторений монеты 1, 2 и 3 коп. Автомат продает билет, если сумма опущенных монет равна трем. В случае превышения суммы автомат возвращает деньги.

23 Построить автомат, на вход которого могут поступать монеты 1, 2 и 3 коп. Автомат выдает сигнал «чет.» (Ч), если сумма опущенных монет четная, и «нечет.» (Н), если нечетная.

33

Список литературы

1 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М. : Айрис-Пресс, 2007. – 176 с. : ил.

2 Гилл, А. Введение в теорию конечных автоматов / А. Гилл. – М. :

Наука, 1966. – 272 с. : ил.

3 Трохимчук, Р. М. Основы дискретной математики. Практикум / Р. М. Трохимчук. – Киев : МАУП, 2004. – 168 с. : ил.

4 Прикладная теория цифровых автоматов / К. Г. Самофалов [и др.]. – Киев : Вища шк., Головное изд-во, 1987. – 375 с. : ил.