Редактирование: Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 123: Строка 123:
 
является начальным, а второе {{---}} заключительным.  В нашем примере <tex>1</tex> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
 
является начальным, а второе {{---}} заключительным.  В нашем примере <tex>1</tex> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
  
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В каждом уравнении в худшем случае может быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>. Кроме того, в алгоритме на каждом шаге мы упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то по приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.
+
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В каждом уравнении в худшем случае может быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: