border=0

Normaal Markov-algoritme

Wy besjogge koarte diskusje de tredde oanpak om it begryp fan in algoritme te ferklearjen (spesifisearjen). As betsjutting fan betsjutting is it ticht by de ideeën fan Turing, mar hy brûkt ideeën oer elke masines. It algoritme wurdt definiearre troch in permutearingssysteem, wat oanjûn hokker subsydzjes fan tekens moatte makke wurde en yn hokker folchoarder dy permutaasjes folgje moatte. Sa'n oanpak wie foarsteld troch A. A. Markov. Yn it begjin fan 'e jierren 50 waard it begryp fan in normale algoritme ynfierd (Markov sels neamde har algoritme).

Untwerp in alfabet A beskôgje in finite oantal letters (letters). Wy prate in oantal definysjes yn:

In wurd is in finitale fariant fan alfabetyske karakters.

It oantal tekens yn in wurd hjit syn lingte.

In wurd dat lingte nul is leech leech neamd .

It wurd s wurdt in subkategory neamd as q, as q kin fertsjintwurdige wurde yn 'e foarm fan q - rst, dêr't rut ienige wurden binne yn deselde alfabet (ynklusyf lege soenen).

No kinne jo it begryp fan in algoritme definieare (wat net strikt is):

De algoritme yn it alfabet A is in effektyf komputerbere funksje, it domein dêr't in subset fan 'e set fan alle wurden yn it alfabet A is en har wearden binne ek de wurden yn it alfabet A.

Yn Markov's algoritme wurdt de subsydzje fan ien wurd ynstee fan in oar nommen as de elemintêre stap fan 'e algoritme. Tink derom dat yn it alfabet A it orizjinele wurd P konstruearre is , dat it subword P r befettet (yn it algemiene gefal kin der ferskate soart wurden wêze yn it boarne wurd), en der is ek wat wurd P k in itselde alfabet.

De subsydzje is de ferfanging fan 'e earste op subbedwurden fan it oarspronklike wurd Р by it wurd P k . De substansje betsjut ' r → P k .

It algoritme yn dizze foarm fan fertsjintwurdiging is definiearre troch in permutearingssysteem, dat in sekere (list) fan permutaasjes is. As der substitúsjes binne yn dizze list mei lofte dielen dy't yn P opnommen binne, dan wurdt de earste op P brûkt , sadat it giet nei in oar wurd P 1 . In substitútstyl, ensfh., Wurdt wer tapast. It proses wurdt yn twa gefallen beëinige: der waard gjin ferfanging yn 'e list mei it loftsdiel yn P n nommen , of by it ûntfangen fan P n de lêste subsydzje tapast waard.

Sjoch ek:

A.1. Notysje fan probabiliteit

Sa - de wurdearring en de wichtichste ferklearrings.

Foarbyld 4.11

Glossar

Foarbyld 8.2

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info