Экзаменационный билет № 28

1. Формальные, фактические параметры Object Pascal.

3. Демультиплексоры – коммутаторы логических сигналов. Общая схема системы передачи информации. В чем различие между детерминированной и недетерминированной машинами Тюринга?

1.

Обмен информацией между подпрограммой и вызывающей её программой осуществляется с помощью механизма передачи параметров.

Переменные, указанные в заголовке подпрограммы называются формальными параметрами или просто параметрами подпрограммы.

Список переменных в операторе вызова подпрограммы – это фактические параметры, или аргументы.

2. Демультиплексор – коммутатор логических сигналов, обеспечивающий передачу информации, поступающей по одному входу, и в соответствии с адресом направляющий в одну из выходных линий. При передачах данных по общему каналу с разделением во времени нужны не только мультиплексоры, но и устройства обратного назначения, распределяющие данные из одного канала между несколькими приемниками информации. Эта задача реализуется демультиплексорами, функционирование которых можно пояснить с помощью рисунок 3.18, а. Демультиплексор имеет один информационный вход n адресующих (управляющих) входов и 2ⁿ выходов. Построение демультиплексора «1>4» на элементах И показано на рисунке 3.18, б. Работа демультиплексора описывается логическими выражениями:

где m_i – минтермы n адресующих переменных.

В условных изображениях демультиплексор обозначается буквами ДМХ (рисунок 3.18, в). Применительно к мультиплексорам и демультиплексорам пользуются также термином «селекторы данных». Функционирование демультиплексора можно заменить таблицей. Например работу демультиплексора с четырьмя выходами (таблица 3.6). При большом числе входов, при необходимости, может быть построено демультиплексорное дерево (рисунок 3.19). Дешифраторы со стробированием (см. рисунок 3.5, а) можно использовать в качестве демультиплексоров. При этом стробирующий вход выполняет функции информационного входа.

Структурная схема системы передачи информации

Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.

В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. Например, X на ленте и состояние 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево.

То есть в отличие от ДМТ, которая имеет единственный «путь вычислений», НМТ имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает.