Трансформаторы: различия между версиями
>Comrade Che Нет описания правки |
|||
| Строка 2: | Строка 2: | ||
Трансформаторы подразделяются на два враждующих между собой лагеря. | Трансформаторы подразделяются на два враждующих между собой лагеря. | ||
---- | ---- | ||
| Строка 37: | Строка 35: | ||
Автомат строился в лоб из регулярного выражения, описывающего поведение Шоквэйва, оттого количество состояний в автомате было невероятно велико(длина регулярного выражения была порядка нескольких миллионов знаков), поэтому начались исследования в области минимизации автоматов. Однако квадратичная сложность минимизации не давала шансов рождению Шоквэйва. Большой удачей было то, что автомат был детерминированным изначально. В итоге Джон Хопкрофт предложил алгоритм, который и по сей день считается лучшим(сложность <math>nlogn</math>). Тогда и появился на свет Шоквэйв. | Автомат строился в лоб из регулярного выражения, описывающего поведение Шоквэйва, оттого количество состояний в автомате было невероятно велико(длина регулярного выражения была порядка нескольких миллионов знаков), поэтому начались исследования в области минимизации автоматов. Однако квадратичная сложность минимизации не давала шансов рождению Шоквэйва. Большой удачей было то, что автомат был детерминированным изначально. В итоге Джон Хопкрофт предложил алгоритм, который и по сей день считается лучшим(сложность <math>nlogn</math>). Тогда и появился на свет Шоквэйв. | ||
[[Категория:Техника]] | |||
[[Категория:Оружие]] | |||
[[Категория:Как страшно жить]] | |||