마르코프 알고리즘

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2020년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

이론 컴퓨터 과학에서 마르코프 알고리즘은 문법 같은 규칙을 사용하여 기호의 끈에서 작동시키는 문자열 재쓰기 시스템이다.마르코프 알고리즘은 튜링-완전한 것으로 나타났는데, 이는 그것들이 계산의 일반적인 모델로 적합하며 단순한 표기법으로부터 어떠한 수학적 표현도 나타낼 수 있다는 것을 의미한다.마르코프 알고리즘은 소련의 수학자 안드레이 마르코프 주니어의 이름을 따서 명명되었다.

Refal은 마르코프 알고리즘에 기반을 둔 프로그래밍 언어다.null

설명

정상 알고리즘은 언어, 즉 서로 다른 알파벳의 문자열에 적용되도록 의도된 것이다.null

모든 정상 알고리즘의 정의는 알고리즘의 알파벳 정의(이 알파벳 기호의 문자열에 알고리즘이 적용됨)와 그 체계 정의의 두 부분으로 구성된다.정상 알고리즘의 체계는 소위 대체 공식의 유한 순서 집합으로, 각각은 단순하거나 최종적일 수 있다.단순 대체 공식은 $L{\displaystyle }$→ ${\displaystyle D}$ ${\displaystyle L}$과 D {\displaystyle $D}$ 형식의 문자열로 표시되며$,$ 여기서 $L{\displaystyle }$ ${\displaystyle L}$과 $D{\displaystyle }$ ${\displaystyle D}$은 알고리즘의 알파벳(각각각, 공식 대체의 왼쪽과 오른쪽)에서 임의 문자열이다.마찬가지로 최종 대체 공식은 $L{\displaystyle }$ →${\displaystyle \cdot }$ ${\displaystyle D}$ ${\displaystyle L\to \cdot$ D$}$ 형식의 문자열로 표시되며$,$ 여기서 $L{\displaystyle }$ ${\displaystyle L}$과 D ${\displaystyle D}$은 알고리즘의 알파벳에서 임의 문자열 두 개다$$.이는 보조 문자${\displaystyle }$→ ${\displaystyle \to }$ 및${\displaystyle }$→ ${\displaystyle \cdot }$ ${\displaystyle \to \cdot }$이(가) 알고리즘의 알파벳에 속하지$$ 않는다고 가정한다(그렇지 않으면 알고리즘의 알파벳에 없는 왼쪽과 오른쪽의 구분자 역할을 수행할 다른 두 문자를 선택해야 한다).null

${\displaystyle \mathrm{다음}}$은 5자 알파벳 ${\displaystyle \ast }$ ${\displaystyle a}$ b ${\displaystyle c}$ ${\displaystyle *abc}$에서 일반적인 알고리즘 구성의 예다$.$

$\displaystyle \{\put{\put{no}b&ba \to &b&\b&\\\\\\*\to &b*&\\c&\to &c\ac&\to \cdot \end{cd}}\cdot \c>오른쪽.}$

이 알고리즘의 알파벳에 있는$$ 임의 $문자열{\displaystyle }$ V ${\displaystyle V$}에 정규 알고리즘을 적용하는 과정은 다음과 같이 구성되는 이산적인 기본 단계 순서다.$V{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ V$'}$이(가) 알고리즘의 이전 단계에서 얻은 단어(또는 현재 단계가 처음인 경우 원래 $단어{\displaystyle }$ V ${\displaystyle V$라고 가정해 보자.$대체{\displaystyle {}^{}}$ 공식 중 V ${\displaystyle {\prime }^{}}$ ${\$ V$\text{'}\}$에 포함된 왼쪽이 없으면 알고리즘이 종료되고, 그 작업의 결과는 $V{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ V$'}$ 문자열로 간주된다$.$ 그렇지 않으면 왼쪽이 $V{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$}에 포함된 첫 번째 대체 공식이다.$e V'}$이(가) 선택됨$$If the substitution formula is of the form ${\displaystyle L\to \cdot D}$, then out of all of possible representations of the string ${\displaystyle V'}$ of the form ${\displaystyle RLS}$ (where ${\displaystyle R}$ and ${\displaystyle S}$ are arbitrary strings) the one with the shortest ${\displaystyle R}$${\displaystyle R}$이(가) 선택됨.Then the algorithm terminates and the result of its work is considered to be ${\displaystyle RDS}$. However, if this substitution formula is of the form ${\displaystyle L\to D}$, then out of all of the possible representations of the string ${\displaystyle V'}$ of the form of ${\displaystyle RLS}$ the $가장{\displaystyle }$ 짧은 R ${\displaystyle R}$을(를) 가진 R ${\displaystyle RDS}$ $문자열$이 현재 단계의 ${\displaystyle \mathrm{결과}}$로 간주되며$$, 다음 단계에서 추가 처리될 수 있다.null

예를 들어 위에서 설명한 알고리즘을 ${\displaystyle \ast }$ $displaystyle$* $}$ 단어에 적용하는 과정에서$$ ${\displaystyle b}$ ${\displaystyle \ast }$ $displaystyle$ $b*},$ $b{\displaystyle }$ ${\displaystyle \ast }$ $displair$ a$$*}, ${\displaystyle b}$$display$ {\$displa{\displaystyle \},}$ b$display$ {\$displailea$$}$ ${\displaystyle 등}$의$$순서가 $.$$ystyle aba$ $*\},$ b $a{\displaystyle }$ ${\displaystyle \ast }${\$displaystyle baa$ ${\displaystyle a}$ ${\displaystyle \ast }$ ${\$$displaystyle aa$$$$*\},$ $c{\displaystyle }$ ${\displaystyle aac$ $c$ $displaystyle$$$$ac$$$}, c${\displaystyle }$${\displaystyle \{\backslash }$$displaystystyle$$$c$\},$ 이후 알고리즘이 중단된다$.$

다른 예는 아래를 참조하십시오.null

모든 정상 알고리즘은 일부 튜링 기계와 동등하며, 그 반대의 경우도 마찬가지 - 튜링 기계는 어떤 정상 알고리즘과 동등하다.정상적인 알고리즘과 관련하여 공식화된 Church-Turing 논문의 버전을 "정상화의 원리"라고 부른다.

정상 알고리즘은 건설 수학의 많은 부분을 구성하는 편리한 수단임이 입증되었다.더욱이 정상 알고리즘의 정의에는 상징적 정보를 취급하는 것을 목적으로 하는 프로그래밍 언어(예: Refal)에 사용되는 여러 가지 아이디어가 내재되어 있다.null

알고리즘.

규칙(Rules)은 문자열 쌍의 시퀀스로, 대개 패턴 → 교체의 형태로 제시된다.각 규칙은 평범하거나 종료될 수 있다.null

입력 문자열 지정:

1. 입력 문자열에서 패턴을 찾을 수 있는지 확인하려면 위에서 아래로 규칙을 확인하십시오.
2. 아무것도 발견되지 않으면 알고리즘이 중지된다.
3. 하나(또는 그 이상)가 발견된 경우, 첫 번째를 사용하여 입력 문자열에서 일치하는 텍스트의 가장 왼쪽에 있는 텍스트를 대체 텍스트로 바꾸십시오.
4. 방금 적용된 규칙이 종료 규칙이면 알고리즘이 중지된다.
5. 1단계로 이동하십시오.

각 규칙 응용 프로그램 후 검색은 첫 번째 규칙부터 다시 시작한다는 점에 유의하십시오.null

예

다음 예는 마르코프 알고리즘의 기본 작동을 보여준다.null

규칙.

1. "A" -> "사과"
2. "B" -> "가방"
3. "S" -> "쇼핑"
4. "T" -> "더"
5. "가게" -> "오빠"
6. "절대로 사용하지 않는" ->"절제 규칙"

기호 문자열

"T S에서 A의 B를 샀어."

실행

위의 예에 알고리즘을 적용하면 기호 문자열은 다음과 같은 방식으로 변경된다.null

1. "T S에서 A의 B를 샀어."
2. "T S에서 사과 B를 샀어."
3. "T S에서 사과 한 봉지를 샀어."
4. "T샵에서 사과 한 봉지를 샀어."
5. "가게에서 사과 한 봉지를 샀어."
6. "형한테 사과 한 봉지를 샀어."

그러면 알고리즘이 종료된다.null

다른 예

이 규칙들은 더 흥미로운 예를 들어준다.그들은 단항 상대에게 이진수를 다시 쓴다.예를 들어 101은 5개의 연속된 막대로 다시 쓰일 것이다.null

규칙.

1. " 0" -> "0 "
2. "1" -> "0 "
3. "0" -> ""

기호 문자열

"101"

실행

위의 예에 알고리즘을 적용하면 다음 단계를 거쳐 종료된다.null

1. "101"
2. "0 01"
3. "00 1"
4. "00 0 "
5. "00 0 "
6. "000 "
7. "00 "
8. "0 "
9. " "

참고 항목

• Thue(프로그래밍 언어)
• 형식문법

참조

• 카라치올로 디 포리노, A.문자열 처리 언어 및 일반화된 마르코프 알고리즘.기호 조작 언어 및 기법에서 D. G. Bobrow (Ed.), North-Holland Publus.Co, 암스테르담, 네덜란드, 1968 페이지 191-206.
• 안드레이 안드리비치 마르코프(1903~1979) 1960.알고리즘 이론.미국 수학 협회 번역, 시리즈 2, 15, 1-14.

외부 링크

• Yad Studio - Markov 알고리즘 IDE 및 인터프리터(오픈 소스)
• 마르코프 알고리즘 통역사
• 마르코프 알고리즘 통역사
• Rosetta-Code에서 마르코프 알고리즘 인터프리터