Огромное количество эффективных алгоритмов на строках и структур данных для быстрых операций с ними (в том числе бор) были разработаны, когда биологам потребовалось анализировать цепочки ДНК колоссальной длины.
Если уж сортировать «тьюринговые трясины» по важности, то надо начинать с основных — математических, на которых всё строилось, а потом уж добавлять в список новомодную эзотерику вроде Brainfuck.
В таком случае это будут:
машина Тьюринга (машину Поста знаю, конечно, но популярности она не приобрела);
лямбда-исчисление Черча;
рекурсивные функции Черча;
нормальные алгоритмы Маркова.
Во «второй эшелон» попадут-таки машина Поста, блок-схема Поста, комбинаторное исчисление Шейнфинкеля, и, если уж добавлять современные «эзотерические языки программирования» в список — Brainfuck со товарищи.
И, будьте добры, не называйте «тьюринговы трясины» эзотерическими системами. Это сейчас BF и ему подобные — эзотерические языки программирования на фоне современных высокоуровневых, а машина Тьюринга и эквивалентные ей создавались не чувство юмора программиста потешить, а математически понятие вычислимости и алгоритмистики исследовать, это совершенно разные вещи.
В перле внутрь регулярок можно куски перлового кода совать, так они Тьюринг-«полными» получаются :)
Боюсь даже подумать, чтобы мне когда-нибудь пришлось разбирать творение какого-нибудь оголтелого фаната регулярок с использованием таких наворотов.
Реализовать разбор на регулярных выражениях сделать нельзя, так как языки программирования не являются регулярными
Теоретически — вы правы.
На практике синтаксические возможности современных регулярных выражений намного превышают класс регулярных языков. Например, с помощью backreferences можно построить выражение, которое опишет язык, не относящийся ни к регулярным, ни даже к контекстно-свободным (большинство языков программирования, тем не менее, контекстно-свободные — описываются BNF). Вообще, движок регулярок давно уже никто не реализовывает с помощью ДКА, там давно перебор. Я и не припомню сейчас движок «чистых» регулярок, с ДКА внутри. В Tcl/Tk такое осталось, кажется, но не уверен.
Ну это в комментах обсуждалось. Для рандомизированной версии вообще трудно указать оценку сложности, можно ориентироваться только на практические тесты. А они хорошие.
Вот именно!
Это два разных варианта реализации одной и той же функции Unite.
В одной нам нужно хранить массив Rank — мы пользуемся им при принятии решения о переподвешивании.
В другой мы принимаем это решение случайным образом, а значит, массив Rank в ней нам не нужен.
Я привел обе реализации, потому что первая является классической, для неё доказана оценка скорости O(α(N)), а вторую проще писать, а на практике она работает почти так же быстро.
В принципе там есть исходник, однако я не против объяснить и здесь.
У вас есть два элемента, X и Y. Вы стандартными операциями Find нашли корни их деревьев: пускай это RX и RY. Чтобы слить два дерева, достаточно один из корней подвесить к другому непосредственным сыном, то есть сделать просто либо P[RX] = Y, либо P[RY] = X. Встает вопрос, какой из двух вариантов выбирать?
В стандартной реализации для этого используется массив рангов, и мы выбираем вариант из принципа «дерево меньшей высоты подвешивать к дереву большей высоты». Однако можно обойтись и без этого. Просто принимаем решение случайно: каждый раз генерируем местным rand() случайное целое число от 0 до 1. Если это 0, подвешиваем RY к RX, если же 1 — то RX к RY.
Время работы такой реализации в среднем оценить достаточно проблемно. Однако если её действительно написать и протестировать на многих разнообразных данных, окажется, что она почти не уступает варианту с рангами.
Нет, просто именно такой способ обеспечивает наилучшую скорость работы. Можно хранить списками, можно настоящими множествами (set<T>), но тогда в любом случае какая-нибудь из операций окажется O(log2 N), O(N) и т.д. — слишком медленно.
Седжвик ещё.
E-maxx, разумеется.
Тысячи их.
Эта статья, в свою очередь, тоже замечательна.
Стоит упомянуть здесь одну из лучших книг по строковым алгоритмам и структурам данных, связанным с ними:
Дэн Гасфилд, «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»
Редко сейчас встретишь в «Алгоритмах» настолько качественный материал.
В таком случае это будут:
Во «второй эшелон» попадут-таки машина Поста, блок-схема Поста, комбинаторное исчисление Шейнфинкеля, и, если уж добавлять современные «эзотерические языки программирования» в список — Brainfuck со товарищи.
И, будьте добры, не называйте «тьюринговы трясины» эзотерическими системами. Это сейчас BF и ему подобные — эзотерические языки программирования на фоне современных высокоуровневых, а машина Тьюринга и эквивалентные ей создавались не чувство юмора программиста потешить, а математически понятие вычислимости и алгоритмистики исследовать, это совершенно разные вещи.
Как-то так.
Боюсь даже подумать, чтобы мне когда-нибудь пришлось разбирать творение какого-нибудь оголтелого фаната регулярок с использованием таких наворотов.
Теоретически — вы правы.
На практике синтаксические возможности современных регулярных выражений намного превышают класс регулярных языков. Например, с помощью backreferences можно построить выражение, которое опишет язык, не относящийся ни к регулярным, ни даже к контекстно-свободным (большинство языков программирования, тем не менее, контекстно-свободные — описываются BNF). Вообще, движок регулярок давно уже никто не реализовывает с помощью ДКА, там давно перебор. Я и не припомню сейчас движок «чистых» регулярок, с ДКА внутри. В Tcl/Tk такое осталось, кажется, но не уверен.
Это два разных варианта реализации одной и той же функции Unite.
В одной нам нужно хранить массив Rank — мы пользуемся им при принятии решения о переподвешивании.
В другой мы принимаем это решение случайным образом, а значит, массив Rank в ней нам не нужен.
Я привел обе реализации, потому что первая является классической, для неё доказана оценка скорости O(α(N)), а вторую проще писать, а на практике она работает почти так же быстро.
У вас есть два элемента, X и Y. Вы стандартными операциями Find нашли корни их деревьев: пускай это RX и RY. Чтобы слить два дерева, достаточно один из корней подвесить к другому непосредственным сыном, то есть сделать просто либо
P[RX] = Y, либоP[RY] = X. Встает вопрос, какой из двух вариантов выбирать?В стандартной реализации для этого используется массив рангов, и мы выбираем вариант из принципа «дерево меньшей высоты подвешивать к дереву большей высоты». Однако можно обойтись и без этого. Просто принимаем решение случайно: каждый раз генерируем местным
rand()случайное целое число от 0 до 1. Если это 0, подвешиваем RY к RX, если же 1 — то RX к RY.Время работы такой реализации в среднем оценить достаточно проблемно. Однако если её действительно написать и протестировать на многих разнообразных данных, окажется, что она почти не уступает варианту с рангами.