TVPS_posobie_13_06_2013

УДК 519.7(07) ББК 22.18(я7)

Б88

Рецензенты:

кафедра информационных технологий БашГУ, зав. кафедрой д-р физ.-мат. наук Болотнов А. М.;

кафедра информационных и полиграфических систем и технологий БГПУ им. М. Акмуллы,

зав. кафедрой д-р физ.-мат. наук Маликов Р. Ф.

Бронштейн Е. М., Зотова О. Ф., Завьялова Е. А.

Б88 Теория вычислительных процессов: учеб. пособие. – Уфа:

УГАТУ, 2012 – 198 с.

ISBN 978-5-4221-0432-1

Содержит конспект лекций, упражнения, вопросы для самоконтроля по темам «Асинхронные процессы», «Сети Петри», «Конечные автоматы», а также перечень терминов, вопросы к экзамену.

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

Табл. 29. Ил. 111. Библиогр.: 5 назв.

УДК 519.7(07) ББК 22.18(я7)

4

Введение

Пособие отражает опыт преподавания авторами дисциплины «Теория вычислительных процессов и структур» студентам специальностей 010503 «Математическое обеспечение и администрирование информационных систем», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» в Уфимском государственном авиационном техническом университете. В основу настоящего издания положен курс лекций доцента кафедры вычислительной математики и кибернетики УГАТУ Тамары Павловны Дворяшиной, который был существенно переработан.

Дисциплина «Теория вычислительных процессов» относится к циклу профессиональных дисциплин при подготовке бакалавров по направлениям «Программная инженерия» и «Математическое обеспечение и администрирование информационных систем». Курс предназначен для теоретической подготовки студентов в области формальных моделей вычислительных процессов и динамических систем, а также для получения практических навыков использования этих моделей при проектировании и разработке программного обеспечения, решении научных и прикладных задач.

В результате изучения дисциплины у студентов формируются следующие общекультурные и профессиональные компетенции:

для направления подготовки бакалавра 010500 «Математическое обеспечение и администрирование информационных систем»:

−фундаментальная подготовка по основам профессиональных знаний (ОК 10);

−самостоятельное построение алгоритма и его анализ (ПК 11);

−навыки разработки моделирующих алгоритмов и реализации их на базе языков и пакетов прикладных программ моделирования (ПК 33).

5

для направления подготовки бакалавра 23100 «Программная инженерия»:

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

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

Пособие состоит из трех больших разделов, в которых рассматриваются основные понятия теории асинхронных процессов, сетей Петри и конечных автоматов. Каждый раздел снабжен вопросами для самопроверки, а также набором упражнений. Также в пособии приводится список вопросов к экзамену/зачету по данной дисциплине.

Желаем успехов в освоении «Теории вычислительных процессов»!

6

1.Асинхронные процессы

Воснову данного раздела положены материалы из книги «Автоматное управление асинхронными процессами в ЭВМ и дискретных системах» под редакцией В. И. Варшавского [1], а также источников [2] и [3], дополненные и переработанные авторами.

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

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

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

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

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

Примерами дискретных динамических систем (ДДС) являются программы, ЭВМ, элементы ЭВМ, сети ЭВМ, производственные системы (конвейеры).

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

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

7

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

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

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

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

Далее рассматриваются понятия дискретной информации и дискретного времени, а также дается определение асинхронного процесса.

Дискретное время

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

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

8

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

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

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

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

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

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

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

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

9

1.2.Понятие асинхронного процесса

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

начальные (инициаторы), они характеризуются тем, что предшествовать инициатору может только инициатор;

конечные (результанты), они характеризуются тем, что следовать за результантом может только результант.

Формально асинхронный процесс это четверка

<S, F, I, R>,

где S ={si} (i , n ) непустое множество ситуаций;

F бинарное отношение непосредственного следования, определенное на множестве S S (F S S);

I множество инициаторов (I S), т.е. таких ситуаций из S, что из sk I, skFsp следует, что sp I. Далее, если это не приводит к недоразумению, инициаторы будем обозначать i1, i2, … .

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

Отношение F можно изобразить орграфом, вершины которого соответствуют ситуациям асинхронного процесса. Дуга исходит из sj и входит в sk, тогда и только тогда, когда sjFsk.

10