683
правки
Категория:Теория автоматов: различия между версиями
Материал из WikiGrapp
Категория:Теория автоматов (посмотреть исходный код)
Версия от 18:46, 23 ноября 2010
, 23 ноября 2010нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
В [[дискретная математика|дискретной математике]], разделе [[информатика|информатики]], '''теория автоматов''' изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать. | В [[дискретная математика|дискретной математике]], разделе [[информатика|информатики]], '''теория автоматов''' изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать. | ||
Теория автоматов наиболее тесно связана с [[теория алгоритмов|теорией алгоритмов]]. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного [[алгоритм| алгоритма]]. Эти преобразования возможны с помощью технических и/или программных средств. Автомат можно представить как | Теория автоматов наиболее тесно связана с [[теория алгоритмов|теорией алгоритмов]]. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного [[алгоритм| алгоритма]]. Эти преобразования возможны с помощью технических и/или программных средств. Автомат можно представить как некоторый [[Преобразователь|преобразователь]], который перерабатывает входные сигналы в выходные и который может иметь некоторые внутренние состояния. | ||
При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]]. | При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]]. | ||
| Строка 10: | Строка 10: | ||
Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем. | Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем. | ||
Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]](игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]]. | Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]] (игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]]. | ||
[[Категория:Теория вычислений]] | |||
