Differences

This shows you the differences between two versions of the page.

--- kurse:ef05a-2021:turingmaschinen:pruefungsfragen [2021/09/07 13:40] – created Ivo Blöchliger
+++ kurse:ef05a-2021:turingmaschinen:pruefungsfragen [2021/10/20 08:29] (current) – Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Vorstellbare Prüfungsfragen ======
+Der Fragenkatalog ist nicht vollständig.
+  * Definieren Sie, was eine Turing-Maschine ist.
+  * Erklären Sie die Begriffe «unäre», «binäre» und «dezimale» Darstellung von Zahlen.
+  * Erklären Sie die Begriffe «Big-Endian» und «Little-Endian». Erwähnen Sie aus dem Alltag bekannte Beispiele.
+  * Wenn man mit Binärzahlen mit einer beschränkten Anzahl Stellen arbeitet, warum kann 111...11 (lauter Einsen) als eine Darstellung von $-1$ aufgefasst werden?
+{{kurse:ef05a-2021:turingmaschinen:img_20210909_091721574.jpg?333}}
+  * Beschreiben Sie (d.h. liefern Sie eine Zustandsdefinition) eine Turing-Maschine, die
+    * unär 1 addiert.
+    * binär 1 addiert.
+    * unär mit 2 multipliziert.
+    * unär in binär oder umgekehrt umrechnet.
+  * Definieren Sie, was eine «universelle Turing-Maschine (UTM)» ist.
+  * Beschreiben Sie, wie ein Zustand einer TM für eine UTM codiert werden könnte und geben Sie ein Beispiel an.
+  * Beschreiben Sie, was das «Halting Problem» ist und welche praktische Konsequenzen das hat.
+  * Beweisen Sie das «Halting Problem».
+  * Sei $S(n,m)$ die maximale Anzahl Schritte, die eine TM mit $n$ Zuständen und einem Alphabet von $m$ Zeichen, auf einem leeren Band machen kann und am Schluss noch stoppt. Zeigen Sie, dass $S(n,m)$ eine nicht-berechenbare Funktion ist.
+{{kurse:ef05a-2021:turingmaschinen:probepruefung-kommentiert.pdf}}