Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
А где же объяснение, как это работает?
Обычная грамматика, все просто и понятно. Есть набор правил. В любом варианте Вам можно выбрать только одно следующее правило. И так пока не разберете все выражение.
Сначала подумал так же, что и правда, чего объяснять — грамматика же! Однако зайдя на википедию и почитав, понял, что такого алгоритма я еще на практике не реализовывал. Поэтому присоединяюсь к комментарию верхнего уровня — было бы неплохо добавить описание работы алгоритма на основе данных правил грамматики, пусть статья будет законченной(гуглить я умею).
Ну, алгоритм не читал, но сам много задачек решил в унарной системе на алгоритме Маркова, постараюь объяснить примерно, как обычно (и вроде бы здесь так же) это выполняется:
Сначала, собственно, добавляем разделить в конце слова предложения (например, "=" ), потом начинается анализ каждого символа слева, что нибудь с ним делается, исходя из условаия (читай: на что — нибудь заменяется) и переносится вправо, при этом ставится флаг на отработанной цифре. Флаг — это доп. символ справа от цифры ("*" например). А перенос осуществляется банальной заменой |* на *|.
Ну а условия осуществляютяс расстановкой разнообразных флагов (символов).
Сначала, собственно, добавляем разделить в конце слова предложения (например, "=" ), потом начинается анализ каждого символа слева, что нибудь с ним делается, исходя из условаия (читай: на что — нибудь заменяется) и переносится вправо, при этом ставится флаг на отработанной цифре. Флаг — это доп. символ справа от цифры ("*" например). А перенос осуществляется банальной заменой |* на *|.
Ну а условия осуществляютяс расстановкой разнообразных флагов (символов).
Итак, анализируем слева направо. Немного запутался с переносами — все же мы только заменяем текущую анализируемую позицию или еще и переносим на правый конец? Что еще не понятно — как определяется сколько символов под читающей головкой анализировать? С помощью условий? Например:
h* на oh
h% на h
h на «пустая строка»
Читаем символ, если это h, читаем еще один символ, анализируем его и если это не * и не %, возвращаем его обратно на входную ленту? И правильно ли я понимаю, что во входной алфавит входят все три варианта — h*, h% и h?
Понимаете, хочется формального описания, с грамматиками я знаком и суть я и так схватил. Поэтому автору плюсанул в карму, подождем пока, может дополнит статью.
h* на oh
h% на h
h на «пустая строка»
Читаем символ, если это h, читаем еще один символ, анализируем его и если это не * и не %, возвращаем его обратно на входную ленту? И правильно ли я понимаю, что во входной алфавит входят все три варианта — h*, h% и h?
Понимаете, хочется формального описания, с грамматиками я знаком и суть я и так схватил. Поэтому автору плюсанул в карму, подождем пока, может дополнит статью.
Как определять сколько символов под читающей головкой анализировать?
Допустим, есть эмулятор маркова, который заменяет по грамматике, в которой правила описываются видом AA -> BB
Он каждый ход просматривает все инструкции сверху и ищет во ВСЕЙ строке первое совпадение с левой частью инструкции. Тоесть ищет AA и заменяет его на BB. Допустим входное слово ppAApp, после прохождения оно станет понятное дело ppBBpp.
Насчет переносов. Это уже сам алгоритм, ничего Марков сам не переносит. Просто это фишка, например для сохранения каких-либо значений, их обычно переносят вправо за какой либо разделитель. Перенос делается в цикле, начало переноса определяется флагом (нарпимер *) а конец — концом строки.
Главное это порядок инструкций, ведь Марков каждый шаг все инструкции проверяет заново.
Входной алфавит — это один набор символов, а дополнительные (терминальные) символы в инструкции нужны только для саомго алгоритма.
Если я не так вас понял, прошу извинить.
Допустим, есть эмулятор маркова, который заменяет по грамматике, в которой правила описываются видом AA -> BB
Он каждый ход просматривает все инструкции сверху и ищет во ВСЕЙ строке первое совпадение с левой частью инструкции. Тоесть ищет AA и заменяет его на BB. Допустим входное слово ppAApp, после прохождения оно станет понятное дело ppBBpp.
Насчет переносов. Это уже сам алгоритм, ничего Марков сам не переносит. Просто это фишка, например для сохранения каких-либо значений, их обычно переносят вправо за какой либо разделитель. Перенос делается в цикле, начало переноса определяется флагом (нарпимер *) а конец — концом строки.
Главное это порядок инструкций, ведь Марков каждый шаг все инструкции проверяет заново.
Входной алфавит — это один набор символов, а дополнительные (терминальные) символы в инструкции нужны только для саомго алгоритма.
Если я не так вас понял, прошу извинить.
Вы правильно меня поняли, спасибо за разъяснения! Мой кругозор расширен!
В теории алгоритм достаточно простой, на практике же, как мне кажется, нехорошо, что непонятно сколько символов надо анализировать+сложность составления правил в нужном порядке. Интересно, где он применяется в реальной жизни? Или только академический интерес?
В теории алгоритм достаточно простой, на практике же, как мне кажется, нехорошо, что непонятно сколько символов надо анализировать+сложность составления правил в нужном порядке. Интересно, где он применяется в реальной жизни? Или только академический интерес?
Никто и не говорит, что описание здесь излишне. Грамматика понятна тем, кто с ней работал. Тем же кто интересуется, необходимо описание на человеческом языке. Поднимите кармы автору, чтобы он подправил статью. Будет хороший мануал для начинающих.
В блоге «Ненормальное программирование» нормальный алгоритм Маркова — это нормально или ненормально?..
Ваш вопрос не совсем нормальный, ненормальность нормальности алгоритма Маркова заключается в ненормальном программировании для нормальных нужд, где использование нормальных или ненормальных принципов полностью отвечает нормальности автора, а так же степени ненормальности руоводства, поставившего кажущуюся с виду нормальную задачу. Вот такие дела.
А где пошаговая реализация преобразования?
Экстремалы. Надо с чего-нибудь попроще начинать, например, с двоичного умножения. Десятичная система это бессмысленное усложнение.
Выглядит как машина Тьюринга, вид сбоку. По крайней мере, представление числа в виде последовательности из N «палочек» сильно напоминает университетские упражнения: «А сейчас, дети, пишем программу для перемножения двух чисел».
не удивительно, нам в курсе Теории Алгоритмов и то и то давали :)
Ну да – машина Тьюринга, нормальные алгорифмы Маркова, лямбда-исчисление Чёрча – все друг другу эквивалентны, и это довольно легко доказывается. Причём доказательство конструктивное.
Так что как минимум составить запись "программы" в любой из этих систем, зная запись в другой, довольно несложно. Интересной является задачка типа регэксп-гольфа – составить самую короткую запись алгоритма.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||/||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| = 3.1415
250077 шагов
250077 шагов
>… упорядоченный набор продукций (замен подстрок). Продукции могут быть как и обыкновенными…
Таким псевдорусским можно мозг выносить и без Маркова
Таким псевдорусским можно мозг выносить и без Маркова
Автор, спасибо. Надо бы как-нибудь прочитать про цепи Маркова.
На правах автора хотелось бы попробовать ответить на большинство комментариев сразу.
Если есть надобность расширить описание как это происходит с удовольствием сделаю это.
А где пошаговая реализация преобразования? -> Я подумал что очень много текста осилит далеко не каждый и пытался сделать этот пост максимально лаконичным.
К исходной строке вначале тоже ничего добавлять не нужно.
Зачем может быть нужно такое программирование в реальной жизни — задачи сложного символьного интегрирования и дифференциирования в системах компьютерной алгербы(как разработчику одной из таких систем приходится сталкиваться).
Остается открым вопрос, есть ли сильные духом кто попробует выполнить задание из P.P.S поста?
Если есть надобность расширить описание как это происходит с удовольствием сделаю это.
А где пошаговая реализация преобразования? -> Я подумал что очень много текста осилит далеко не каждый и пытался сделать этот пост максимально лаконичным.
К исходной строке вначале тоже ничего добавлять не нужно.
Зачем может быть нужно такое программирование в реальной жизни — задачи сложного символьного интегрирования и дифференциирования в системах компьютерной алгербы(как разработчику одной из таких систем приходится сталкиваться).
Остается открым вопрос, есть ли сильные духом кто попробует выполнить задание из P.P.S поста?
Онлайн интерпретатор, если кто искал.
Это кажется тот самый Марков, который после Октябрьской Революции (переворота), когда у него из прихожей похитили галоши, писал Ленину, что теперь вследствие этого не может посещать ВУЗ и учить студентов математике. Вождь Мирового Пролетариата не прошел мимо простого профессора и немедленно отвлекись от наступления Юденича и писем к Американским рабочим, тут же написал мандат на возврат галош профессору. И тот же самый матрос, который обчистил профессорскую прихожую, пожал плечами и обчистил соседнюю, вернув галоши Маркову. При этом обе они оказались на одну ногу, о чем профессор немедленно снова писал Вождю. У того видно с Юденичем было совсем неотложно, да и Американское рабочие ждать уже больше не могли, и он на письмо Маркова не ответил. Кажется это подтвердило справедливость Марковских цепочек, а его самого избавило от многих неприятностей в будущем, которым подверглись другие математики, которые не переписывались лично с Ильичом.
экспериментальным путем было выявлено, что лучше "_ на 0.FIN", чем "_ на .FIN"
codepad.org/3v0Mw0c9
реализация на Хаскеле \(^^)/
что порождает сразу такие забавные примеры, как:
markov_bin2un = markov bin2unD
markov_div_un = markov un_divD
markov_div_bin x y = markov_div_un ( markov_bin2un x ++ "/" ++ markov_bin2un y )
*Main> markov_bin2un «1111»
"|||||||||||||||"
*Main> markov_div_un "||/|||"
«0.6666»
*Main> markov_div_bin «11» «111»
«0.4285»
codepad.org/3v0Mw0c9
реализация на Хаскеле \(^^)/
что порождает сразу такие забавные примеры, как:
markov_bin2un = markov bin2unD
markov_div_un = markov un_divD
markov_div_bin x y = markov_div_un ( markov_bin2un x ++ "/" ++ markov_bin2un y )
*Main> markov_bin2un «1111»
"|||||||||||||||"
*Main> markov_div_un "||/|||"
«0.6666»
*Main> markov_div_bin «11» «111»
«0.4285»
У меня получилась 41 команда. Последовательность действий такая: 1) переводим числитель в десятичную с/с; 2) приписываем к нему справа 4 нуля; 3) переводим его обратно в унарную с/с; 4) выполняем целочисленое деление в унарной с/с; 5) переводим результат в десятичную с/с (с правильной установкой точки). Шаги 1 и 5 выполняются одними и теми же командами. Сам алгоритм:
Выполняется, правда, подольше, но автором задача наискорейшего выполнения и не ставилась :)
/ :: AB
|A :: A|
A :: X
0| :: 1
1| :: 2
.....
8| :: 9
9| :: |0
.| :: |.
X| :: X1
B :: 0000CD
1* :: 0
2* :: 1
.....
9* :: 8
0* :: *9
X0 :: X
XC :: [empty]
C :: *C|
+P :: |+
P| :: |P
|D| :: DP
DP :: D|+
D| :: Z
Z| :: Z
ZP :: Z
Z+ :: X0.0000|Q
Q+ :: |Q
Q :: [empty]
X. :: 0. [FIN]
X :: [empty] [FIN] Выполняется, правда, подольше, но автором задача наискорейшего выполнения и не ставилась :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нормальный алгоритм Маркова для деления чисел