exorciser.ch

exorciser.ch

Webseiten-Werkzeuge

Sie befinden sich hier: exorciser.ch » Markow Algorithmen » Lab

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
markow:lab [2021/09/21 10:39] – [Breaking Rings] Tscherter, Vincentmarkow:lab [2024/03/03 22:36] (aktuell) – Tscherter, Vincent
Zeile 1: Zeile 1:
 +====== Lab ======
  
 +===== - Unär nach Dezimal =====
 +FIXME ein- und ausgabe. optimieren für anzahl schritte.
 +<code>/αI{10}/Iα/g
 +/αI{9}ω/ω9/
 +/αI{8}ω/ω8/
 +/αI{7}ω/ω7/
 +/αI{6}ω/ω6/
 +/αI{5}ω/ω5/
 +/αI{4}ω/ω4/
 +/αI{3}ω/ω3/
 +/αI{2}ω/ω2/
 +/αI{1}ω/ω1/
 +/αω/ω0/
 +/(I+)ω?/α$1ω/
 +/ω//!</code>
 +
 +===== Breaking Rings =====
 +
 +<code>
 +
 +Input 454665122334
 +Output 111 (drei ringe aufbrechen)
 +
 +Idee: Für jeden Ring entscheiden ob er aufgebrochen werden muss oder nicht. -> Binäres zählen
 +
 +Teilproblem binäres zählen:  10001 -> 10010
 +/1β/β0/
 +/0?β/1/ !
 +/$/β/
 +
 +Teilproblem Ringliste: 454665122334 -> 454665122334χ456123
 +/χ(.*)(.)(.*)\2/χ$1$2$3/
 +/χ/χ/! 
 +/.*/$&χ$&/ 
 +
 +Teilproblem Prüfe Konfiguration: 454665122334:456123:110001 -> CLEAN/CONNECTED
 +hier würde 4, 5 und 3 aufgebrochen. 
 +
 +/γ(.)(.*)ε0/γ$2ε/
 +/γ(.)(.*)ε1/$1γ$2ε/
 +/π(.)(.)(.*)φ(.*)\1(.*)γ/π$3φ$4$1$5γ/
 +/π(.)(.)(.*)φ(.*)\2(.*)γ/π$3φ$4$2$5γ/
 +/πφ.*/CLEAN/!
 +/π.*/CONNECTED/!
 +/(.*):(.*):(.*)/π$1φγ$2ε$3/
 +
 +454665122334:456123B:110001 -> 454665122334:456123B:110001 
 +
 +Ablaufsteuerung:
 +
 +##########################################################
 +
 +Phase A) Initialisierung: 122334 -> 1111ξ122334:1234:0000B
 +
 +/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
 +/(.*)A(.)(.*):/1$1$2A$3:0/ 
 +/(.*):(.*)A:(.*)/$1:$2:$3B/ 
 +/(.*)/ξ$1:A$1:/
 +
 +##########################################################
 +
 +Phase B) Prüfen der Konfiguration
 +Ringe noch verbunden -> Phase C   1111ξ122334:1234:0000B -> 1111ξ122334:1234:0000C
 +Ringe nicht verbunden -> Phase D  1111ξ122334:1234:0101B -> 1111ξ122334:1234:0101D
 +
 +/γ(.)(.*)ε0/γ$2ε/
 +/γ(.)(.*)ε1/$1γ$2ε/
 +/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
 +/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
 +/Bφ.*/D/ 
 +/B.+/C/ 
 +/ξ(.*):(.*):(.*)B/ξ$1:$2:$3B$1φγ$2ε$3/
 +
 +##########################################################
 +
 +Phase C) Binäres zählen & Schluss    1111ξ122334:1234:0011C -> 1111ξ122334:1234:0100B
 +                    falls am ENDE    11ξ122334:1234:1111C -> 11
 +/1C/C0/
 +/ξ.*:C.*//! 
 +/0?C(.*)/1$1B/ 
 +
 +##########################################################
 +
 +Phase D+E) Auswerten     1111ξ122334:1234:0101D -> 11ξ122334:1234:0111C
 +
 +/E(.*)0/E$1/ 
 +/^(1*)(1*)ξ(.*)E\1$/$1ξ$3C/  
 +/E.*/C/ 
 +/([01]*)D/$1E$1/ 
 + 
 +
 +##########################################################
 +
 +/1C/C0/
 +/:C/ all tested /! 
 +/0?C(.*)/1$1B/
 +
 +/γ(.)(.*)ε0/γ$2ε/
 +/γ(.)(.*)ε1/$1γ$2ε/
 +/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
 +/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
 +/Bφ.*/E/ !
 +/B.+/C/
 +/(.*):(.*):(.*)B/$1:$2:$3B$1φγ$2ε$3/
 +
 +/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
 +/A(.)(.*):/$1A$2:0/ 
 +/(.*):(.*)A:(.*)/$1:$2:$3B/  !
 +/(.*)/$1:A$1:/
 +
 +</code>
 +
 +Programm am Schluss
 +<code>/E(.*)0/E$1/ 
 +/^(1*)(1*)ξ(.*)E\1$/$1ξ$3C/  
 +/E.*/C/
 +
 +/([01]*)D/$1E$1/ 
 +
 +/1C/C0/
 +/ξ.*:C.*//! 
 +/0?C(.*)/1$1B/ 
 +
 +/γ(.)(.*)ε0/γ$2ε/
 +/γ(.)(.*)ε1/$1γ$2ε/
 +/B(.)(.)(.*)φ(.*)\1(.*)γ/B$3φ$4$1$5γ/
 +/B(.)(.)(.*)φ(.*)\2(.*)γ/B$3φ$4$2$5γ/
 +/Bφ.*/D/ 
 +/B.+/C/ 
 +/ξ(.*):(.*):(.*)B/ξ$1:$2:$3B$1φγ$2ε$3/
 +
 +/A(.*)(.)(.*)\2(.*):/A$1$2$3$4:/
 +/(.*)A(.)(.*):/1$1$2A$3:0/ 
 +/(.*):(.*)A:(.*)/$1:$2:$3B/  
 +/(.*)/ξ$1:A$1:/
 +</code>
 +
 +===== 1 Marge Intervals (Unary) =====
 +  ; Quelle
 +  : [[code:merge_intervals|]]
 +  ; Eingabe ex.
 +  : <code>I:III,III:IIII,II:IIIIII,III:IIII</code>
 +  ; Ausgabe ex.
 +  : <code>I:IIIIII</code>
 +  ; Lösung
 +  : <code>/(I+)(I+):(I+),\1:(I+)/$1:$4,$1$2:$3/
 +/:(I+)(I*),I*:\1\b/:$1$2/
 +/:(I+)(I*),\1I?:/:/</code>
 +
 +===== 2 Simulation eine Turing Maschine am Beispiel Busy Beaver 3 =====
 +  ; Eingabe
 +  : <code># tape startzustand
 +□
 +# zustandsübergänge
 +q0, □ → q1, 1, R
 +q0, 1 → qf, 1, R
 +q1, □ → q2, □, R
 +q1, 1 → q1, 1, R
 +q2, □ → q2, 1, L
 +q2, 1 → q0, 1, L</code>
 +  ; Ausgabe
 +  : <code>111111</code>
 +  ; Code
 +  : TM Simulator für Markow Algorithmen<code># initialisierung
 +/^#.*\n//gm                                             kommentare entfernen 
 +/^([^τ])(.*)\n([^,]*)/τλ$1$2σ$3\n$3/
 +/\n([^,]*),([^→]*)→([^,]*),([^,]*),(.*)/δ$1ζ$2$4$5$3/g  regeln strukturieren
 +/\s//g                                                  leerschläge entfernen
 +/τλ/τ□λ/                                                blanks links hinzufügen
 +/λσ/λ□σ/                                                blanks rechts vom kopf
 +
 +   1   2    3      4      5      6    
 +/λ(.)(.*)σ([^δ]+)(.*δ\3ζ\1(.)R([^δ]+))/$5λ$2σ$6$4/      r-regel anwenden
 +
 +  1   2  3     4      5       6    7    
 +/(.)λ(.)(.*)σ([^δ]+)(.*δ\4ζ\2(.)L([^δ]+))/λ$1$6$3σ$7$5/ l-regel anwenden
 +
 +/τ□*(.*)λ(.*?)□*σ.*/$1$2/!                              terminieren</code>

Benutzer-Werkzeuge

Seiten-Werkzeuge

Webseiten-Werkzeuge