Математическая модель цифрового устройства работы светофора
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
ГОУ ВПО "Северо-кавказский государственный технический университет"
Факультет информационных технологий и телекоммуникаций
Кафедра прикладной математики и компьютерных технологий
Курсовая работа
По предмету Математическое программирование
Тема Математическая модель цифрового устройства работы светофора
Ставрополь, 2011 г
Содержание
1. Введение
2. Конечный автомат
3. Схема и математическая модель работы светофора
Математическая модель
4. Работа модели в Visual basic
5. Вывод
6. Список литературы
1. Введение
Цель работы заключается в создании математической и компьютерной модели работы светофора с датчиком. Рассматривается скоростное шоссе с плотным авто-трафиком. Проблема заключается в том что на шоссе нет дорожного перехода, а если поставить светофор то будут возникать большие скопления автомобилей. В качестве решения предложено установить светофор для пешеходного перехода с платформой датчиком, который включает красный свет автомобилям в случае появления пешехода. Плюсом модели является то, что в случае отсутствия пешеходов не возникает заторов, так как автомобилям все время горит зеленый свет.
2. Конечный автомат
Конечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:
где:- конечное множество состояний автомата;- начальное (стартовое) состояние автомата ();- множество заключительных (или допускающих) состояний, таких что ;
? - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
? - заданное отображение множества во множество подмножеств Q:
(иногда ? называют функцией переходов автомата).
Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово "принимается" автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово "отвергается".
Конечные автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей.
Другие способы описания
Диаграмма состояний (или иногда граф переходов) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а нагрузка - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов - табличное представление функции ?. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу - один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.
Детерминированность
Конечные автоматы подразделяются на детерминированные и недетерминированные.
Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:
Если рассмотреть случай, когда автомат задан следующим образом:
,
где:- множество стартовых состояний автомата, такое что ;
Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата.
Существует теорема, гласящая, что "Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали" (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.
В силу последних двух замечаний, несмотря на бо?льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.
Автома?тное программи?рование - это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата.
В зависимос