Дискретное время. Дискретная информация

Сборник ответов

К экзамену «Теория вычислительных процессов»

· Версия от 12.01.2015 15:25

· Вопросы 1 – 46 из 56

· Отсутствует доказательство свойств редукции к вопросу 11. Поэтому у кого оно есть - неплохо было бы дополнить

Раздел 1. Асинхронные процессы (АП)

Понятие дискретной динамической системы.

Динамическая система − это математическая абстракция, которая используется для описания и изучения систем, эволюционирующих с течением времени.

Динамическая система представляет собой математическую модель некоторого объекта, процесса или явления.

Она, в частности, может быть представлена как система, обладающая состоянием (находящаяся в некоторой ситуации). При таком подходе, динамическая система описывает (в целом) динамику некоторого процесса, а именно: процесс перехода системы из одного состояния в другое. Таким образом, динамическая система

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

Различают динамические системы с дискретным временем и системы с непрерывным временем. В системах с дискретным временем поведение системы описывается последовательностью состояний. В системах с непрерывным временем состояние системы определено для каждого момента времени (положительного числа).

Параллелизм означает возможность одновременного выполнения действий, переходов в нескольких подсистемах динамической системы.

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

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

Дискретное время. Дискретная информация.

В дискретном устройстве могут быть выделены каналы, через которые оно осуществляет обмен информацией с внешней средой. Информация поступает через входные каналы, перерабатывается

устройством в соответствии с его назначением, после чего результат выдается через выходные каналы. При этом результат определяется не только входными воздействиями (текущими), но и текущим состоянием устройства, которое в процессе функционирования может

меняться.

Работа различных дискретных устройств осуществляется тактами. На каждом такте под действием входного воздействия протекает переходный процесс, связанный с изменением внутреннего состояния и выдачей выходной информации. Лишь после завершения этого процесса может быть подано следующее воздействие, относящееся к следующему такту.

В одних случаях тактность обеспечивается специальным устройством – генератором синхронизирующих импульсов. При этом длительность такта определяется временем протекания самого

длительного переходного процесса.

В других случаях новый такт начинается сразу после получения сигнала о завершении переходного процесса, относящегося к предыдущему такту. Это повышает быстродействие устройства, но требует дополнительных аппаратных затрат.

Пусть t=0, 1, 2, … – начальные моменты времени тактов (единицы измерения для времени не существенны). Ноль соответствует началу работы. Далее при рассмотрении АП будем считать, что процесс, относящийся к такту t – подача входного воздействия, изменение состояния, выдача выходного воздействия –происходит мгновенно в момент времени t.

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

Каждому значению можно поставить в соответствие некоторый символ (букву). Множество букв называется алфавитом. В этом случае информацию называют словесной. Последовательность букв

алфавита называется словом.

Непрерывную информацию можно с любой степенью точности в том или ином смысле аппроксимировать дискретной, а дискретную представить в виде словарной.

Наиболее часто используются дискретные устройства, осуществляющие переработку слов над алфавитом {0, 1}.

Поиск по сайту: