Обсуждение:Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
== Содержание ==
+
: {{tick}} Текущий алгоритм асимптотически корректен, но если под классами понимать пары <подмножество состояний, символ, по которому проводилось разбиение>, то можно сделать его эффективнее. Нужно переписать то, что есть, с учетом данного изменения.
Алгоритм похож на правильный, но понять его очень сложно, текст не особо связный. Хочется пример для наглядности. И очень хочется список литературы.
+
: {{tick}} Несколько подробнее расписать время работы алгоритма.
:Алгоритм сам по себе сложный. Текст попробую еще поменять, но из псевдокода и так все понятно. Могу добавить пример как с помощью сплиттера происходит деление блока. Список литературы добавлен.
+
--[[Участник:Sementry|Мейнстер Д.]] 23:15, 8 декабря 2012 (GST)
 
 
Вот пример автомата
 
количество состояний - 2, терминальных - 1 (вершина №0), мощность алфавита - 1.  
 
переходы:
 
0 <math>\to</math> 0
 
1 <math>\to</math> 1
 
Этот автомат ведь эквивалентен автомату только с вершиной 0, а алгоритм этого не скажет.
 
 
 
Алгоритм не правильный. При небольших исправлениях он даст верный результат, но работает за <tex>O(|\Sigma| * n ^ 2)</tex>. По второму источнику ("D. Gries. Describing an algorithm by Hopcroft.") можно составить представление как алгоритм за <tex>O(|\Sigma| * n \log {n})</tex> должен работать. --[[Участник:Dmitriy D.|Dmitriy D.]] 01:53, 29 октября 2012 (GST)
 
:Правильный же. Только тут треш в статье, алгоритмы, приведенные в разделах "простой алгоритм" и "алгоритм Хопкрофта" отличаются ровно ничем.
 
 
 
== Оформление ==
 
Больше всего претензий. Понимания не только не добавляет, но и отнимает остатки. Пунктуация — аут полный, запятых практически нет. Ну ладно, это работа для гнома. Слово "сплиттер" пишется так, как его пишу я, а не как его пишешь ты. Разность множеств обозначается не тире, а backslash'ем. Зато вместо минусов надо ставить нормальное тире (пока Кирилл не видит, это его любимая мозоль). Там еще пара орфографических ошибок есть, но пока забьем.
 
:Исправил "сплиттер", минусы и разность множеств. С письменным русским языком большие проблемы, так что надеюсь на гнома)
 
 
 
 
 
Влад, имхо, это стоит расписать подлиннее и поподробнее. Алёна.
 

Версия 22:15, 8 декабря 2012

Текущий алгоритм асимптотически корректен, но если под классами понимать пары <подмножество состояний, символ, по которому проводилось разбиение>, то можно сделать его эффективнее. Нужно переписать то, что есть, с учетом данного изменения.
Несколько подробнее расписать время работы алгоритма.

--Мейнстер Д. 23:15, 8 декабря 2012 (GST)