Übungsblätter zur Vorlesung Digitale Informationsverarbeitung

(Magister)

Wintersemester 2002/03 - Serie 2

1. Geben Sie eine Turing-Maschine an (Angabe der Zustandsmenge, der Überführungsfunktion in tabellarischer Form usw.), die folgendes leistet: Angewendet auf einen nicht leeren Eingabestring aus Nullen und Einsen läuft sie diesen ab und schreibt nach Erreichen des Endes eine 1 falls der String mindestens zwei aufeinanderfolgende Einsen enthielt. Sonst Ausgabe 0. (4 Pkte.)
2. Schreiben Sie ein Programm für eine Turing-Maschine, die angewendet auf eine nicht leere Zeichenkette der Form 000...0 nach dem Ende der Zeichenkette eine 1 schreibt, wenn die Anzahl der Zeichen durch drei teilbar ist und 0 sonst. (4 Pkte.)
3. Schreiben Sie while-Programme  gemäß der in der Vorlesung gegebenen Definition (s. Folien zum Kap. Berechenbarkeit) zur Realisierung der im folgenden angegebenen Funktionen. Dabei sollen die Variablen x1 und x2 mit den Eingaben und x0 mit den Ausgabewerten belegt werden. Diese können jeweils natürliche Zahlen sein. 
• PLUS(i,j) zur Addition zweier natürlicher Zahlen i und j (1 Pkt.)
• Analog MINUS(i,j) für die Subtraktion  (1 Pkt.)
• GREATER(i,j) gibt 1 aus falls i>j und 0 sonst  (2 Pkte.)
• Unter Verwendung dieser Funktionen und dem in der Vorlesung gegebenen while-Programm zur Multiplikation schreiben Sie ein while-Programm zur Bestimmung der Wurzel aus einer Zahl a, wobei a eine Quadratzahl sein soll (2 Pkte.)
  
4. Schreiben Sie ein while Programm, das die Fakultät n! = 1 2 3 ... n einer natürlichen Zahl n > 0 berechnet. Es darf das in der Vorlesung eingeführte while Programm für die Multiplikation zweier natürlicher Zahlen (s. Folien) verwendet werden. (4 Pkte.) 
5. Geben Sie eine C Funktion int isprime(int n) {...} an, die testet ob eine natürliche Zahl n eine Primzahl ist oder nicht. Rückgabewert der Funktion ist 1 falls ja und 0 sonst. Testen Sie Ihre Implementierung an selbstgewählten Beispielen. ( 6 Pkte.)