Математическая модель цифрового устройства работы светофора

 

Министерство образования и науки Российской Федерации

ГОУ ВПО "Северо-кавказский государственный технический университет"

Факультет информационных технологий и телекоммуникаций

Кафедра прикладной математики и компьютерных технологий

Курсовая работа

По предмету Математическое программирование

Тема Математическая модель цифрового устройства работы светофора

Ставрополь, 2011 г

Содержание

1. Введение

2. Конечный автомат

3. Схема и математическая модель работы светофора

Математическая модель

4. Работа модели в Visual basic

5. Вывод

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

1. Введение

Цель работы заключается в создании математической и компьютерной модели работы светофора с датчиком. Рассматривается скоростное шоссе с плотным авто-трафиком. Проблема заключается в том что на шоссе нет дорожного перехода, а если поставить светофор то будут возникать большие скопления автомобилей. В качестве решения предложено установить светофор для пешеходного перехода с платформой датчиком, который включает красный свет автомобилям в случае появления пешехода. Плюсом модели является то, что в случае отсутствия пешеходов не возникает заторов, так как автомобилям все время горит зеленый свет.

2. Конечный автомат

Конечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

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

где:- конечное множество состояний автомата;- начальное (стартовое) состояние автомата ();- множество заключительных (или допускающих) состояний, таких что ;

? - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

? - заданное отображение множества во множество подмножеств Q:

(иногда ? называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово "принимается" автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово "отвергается".

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а нагрузка - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

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

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом:

,

где:- множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата.

Существует теорема, гласящая, что "Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали" (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо?льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Автома?тное программи?рование - это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата.

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

Определяющими для автоматного программирования являются следующие особенности:

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

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

Полностью выполнение кода в автоматном стиле представляет собой цикл (возможно, неявный) шагов автомата.

Название автоматное программирование оправдывается ещё и тем, что стиль мышления (восприятия процесса исполнения) при программировании в этой технике практически точно воспроизводит стиль мышления при составлении формальных автоматов (таких как машина Тьюринга, автомат Маркова и др.)

сфетофор visual basic модель

3. Схема и математическая модель работы светофора

Мы имеем граф-схему работы светофора:

0

1

1

0

Графическая модель дороги

Зеленый свет светофора для автомобилей горит 60 секунд после чего происходит проверка датчика (нажат/не нажат 1/0), если датчик нажат то включается красный на 30 секунд после чего опять зеленый на 60 секунд. Далее если датчик не нажат то светофор продолжает гореть зеленым до следующей проверки датчика.

Математическая модель

Математическая модель состоит из двух автоматов G и W, где G-автомат управляющий светофором, а W-автомат, отражающий наличие или отсутствие пешеходов.

Временный сигнал отсутствует x1=0 в течении 60 секунд и появляется x1=1 в течении 30 секунд.

Красный сигнал светофора z=1 включается когда x1=1

Датчики это x2, при срабатывании x2=1, в остальное время x2=0

:= {q2/x1w2, q3/x1w1},= {q1/^x1},= {q1/^x1},:= {w2/^x2},= {w1/x2},

4. Работа модели в Visual basic

Общий текст программы имеет вид:Explicitnum1 As IntegerfirstTime As DatelastTime As DatenewTime As DatedeltaLastTime As LongdeltaFirstTime As LongsensorColor As LongtimerColor As LongResetNewProtocol ()= Time= firstTime= firstTime. DrawWidth = 1. Line (58, 460) - (422, 514), &H8000000F, BF. ScaleMode = 3. DrawWidth = 5. Line (60, 470) - (420, 470), RGB (0, 0, 0). Line (60, 487) - (420, 487), RGB (0, 0, 0). Line (60, 504) - (420, 504), RGB (0, 0, 0)SubDrawNewProtocol ()tmpTimeBegin As LongtmpTimeEnd As Long= DateDiff ("s", firstTime, lastTime)= DateDiff ("s", firstTime, newTime). DrawWidth = 1. Line (60 + 4 * tmpTimeEnd, 460) - (60 + 4 * tmpTimeEnd, 514), RGB (128, 128, 128). DrawWidth = 3. Line (60 + 4 * tmpTimeBegin, 470) - (60 + 4 * tmpTimeEnd, 470), s2. FillColor. Line (60 + 4 * tmpTimeBegin, 487) - (60 + 4 * tmpTimeEnd, 487), sensorColor. Line (60 + 4 * tmpTimeBegin, 504) - (60 + 4 * tmpTimeEnd, 504), timerColorSubEventNewProtocol (timeEvent As Date)= DateDiff ("s", firstTime, timeEvent)deltaFirstTime > 90 Then= newTime= timeEvent= DateDiff ("s", lastTime, timeEvent)IfSubprotocol (text As String). text = Str (DateDiff ("s", firstTime, Time)) + ": " + text + vbCrLf + Text1. textSubSub Command1_Click ()txtGreen. text <= 0 Or txtGreen. text > 60 Then"неправильное число"m1IftxtRed. text <= 0 Or txtRed. text > 30 Then"неправильное числ"m1If= Time= firstTime= firstTime("Начало работы"). Locked = True. Locked = True. BackColor = &H8000000A. BackColor = &H8000000A. Visible = False. Visible = True. Visible = False. Visible = True= RGB (0, 200, 0). Interval = txtGreen. text * 1000. Interval = txtRed. text * 1000("Включен таймер зелёного"). Enabled = True. Visible = False. Visible = True:Subsemag ()(Time). FillColor = &HFF&. FillColor = &HFF&. FillColor = &HFF00&. FillColor = &HFF00&("Зажёгся зелёный")Subsemar ()(Time). FillColor = &HFF&. FillColor = &HFF&. FillColor = &HFF00&. FillColor = &HFF00&("Зажёгся красный")SubSub Command2_Click ()= 0. Locked = False. Locked = False. BackColor = &H80000005. BackColor = &H80000005. Enabled = False. Enabled = False. Visible = False. Visible = False. Visible = True. Caption = "Датчики отжаты (давить левой кнопкой мыши)". Visible = False= RGB (200, 200, 0). FillColor = &H808080. FillColor = &H808080. FillColor = &H808080. FillColor = &H808080. Visible = True. Visible = False("Конец работы")SubSub Command3_Click (). text = ""SubSub Form_Load (). Hide. Show. Interval = 500= RGB (200, 200, 0)SubSub Image1_Click ()SubSub shd1_Click ()(Time)= 1. Visible = False. Visible = False. Visible = True. Caption = "Дорожный переход (есть пешеходы)"("Датчики нажаты")= RGB (200, 0, 200)SubSub shd2_Click ()(Time)= 0. Visible = False. Visible = False. Visible = True. Caption = "Датчики отжаты (давить левой кнопкой мыши)"("Датчики отжаты")= RGB (200, 200, 0)SubSub t1_Timer ()(Time). Enabled = Falsenum1 = 1 ThenIf. Enabled = True= RGB (200, 0, 0)("Включен таймер красного")SubSub t2_Timer ()(Time). Enabled = Falses1. FillColor = &HFF& Then. Enabled = True. Enabled = TrueIf= RGB (0, 200, 0)("Включен таймер зелёного")SubSub t3_Timer (). Hide. Show. Interval = 0Sub

Окно программы

5. Вывод

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

По результатам компьютерной модели видно следующее:

Время горения красного и зеленого сокращено чтобы нагляднее видеть изменения:

В графе Светофор зеленым цветом обозначается зеленый свет светофора и красным - красный свет светофора.

В графе датчик желтый - датчик неактивен, а фиолетовый - активен (есть пешеход).

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

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

1. Иванов В.Т. Математическое моделирование. Модели прогнозирования. (Методические указания для самостоятельной работы по курсу ЦИПС) - Уфа, 1988.

. Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1998.

. Математическое моделирование: Пер. с англ. / Под ред. Дж. Эндрюса, Р. Мак-Лоуна. - М.: Мир, 1979.

. Кондаков В.М. Математическое программирование. Элементы линейной алгебры и линейного программирования. - Пермь: Из-во ЛГУ, 1992.

. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1993.

. Белошапка В.К. Информационное моделирование в примерах и задачах. - Омск: Из-во ОГПИ, 1992.

Министерство образования и науки Российской Федерации ГОУ ВПО "Северо-кавказский государственный технический университет" Факультет информационн

Больше работ по теме: