Prüfungsteilnehn Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 46 1 1 4 1998 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (nicht vertieft studiert) Einzelprüfung: Algorithmen/Datenstrukt./Progr.-meth. Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 5 Bitte wenden! Herbst 1998 Einzelprüfungsnummer: 46114 \ Seite: 2° Thema Nr. 1 Sämtliche Teilaufgaben sind zu bearbeiten! Aufgabe 1: Eine Geldbörse enthält eine Menge Me von Münzen Mü (mit Wert w{Mü)). (Die Münzen können verschiedene Werte haben.) a) Beschreiben Sie einen Algorithmus, der zu einem Geldbetrag g eine Teilmenge T von Münzen aus Me liefert, deren Wert gerade g beträgt (falls es eine solche Teilmenge T gibt)! b) ist entscheidbar, ob es zu g eine Teilmenge T mit Wert g gibt? (Begründung!) c) Formulieren Sie Ihren Algorithmus aus a) in einer Programmiersprache ihrer Wahi! d) Beschreiben Sie die in a) bzw. c) verwendeten Datenstrukturen! Aufgabe 2: Geben Sie die Grammatik G=(V,T,P,S) mit Variablenmenge V=iS,A,B}, terminalem Zeichenvorrat T=(a,b}, dem Startsymbol S und der Produktionenmenge P= {S+AB ,S+AaBb,$+AaaBbb ,A+aaaA,A+e,B+bbbB,B+el}. a) Welchen Typ hat die Grammatik? b) Bestimmen Sie die von G erzeugte Sprache L(G)! c} Ist L(G) regular? Aufgabe 3: Betrachten Sie die rekursıv definierte Wortcodierungsfunktion code: {a,b}*+N mit code («)=0,code(a)}=1,code(b)=2, x code (wo}=2-code(w)+code(a) (wé {a,b}", ce{a,b}). a) Berechnen Sie code(abb)! b) Zeigen Sie, daß code bijektiv ist! €) Definieren Sie die Umkehrfunktion decode = code! oder geben Sie einen Algorithmus für decode an! d) Berechnen Sie decode( 11}! Herbst 1998 Einzelprüfungsnummer: 46114 Seite: 3 Thema Nr. 2 Sämtliche Teilaufgaben sind zu bearbeiten! Aufgabe 1: Für einen endlichen nicht-leeren Zeichenvorrat Z sei eine Binärcodierung e:Z -{0,L} gegeben. 1.1 Geben Sie eine Datenstruktur (durch Typdefinitionen) an, mit deren Hilfe ein beliebiger Binärcode c im Hinblick auf die folgende Teilaufgabe 1.2 geeignet dargestellt werden kann! 1.2 Schreiben Sie eine Funktionsprozedur fano, mit deren Hilfe festgestellt werden kann, ob ein Binärcode c der Fano-Bedingung genügt! Die Funktionsprozedur fano soll dabei folgender Spezifikation genügen: Eingabeparameter: c vom Typ CODE Resultat: Das Resultat ist vom Typ BOOLEAN und hat den Wert TRUE genau dann, wenn c der Fano-Bedingung genügt. Hinweise: - Der Typ CODE muß in Ihrer Antwort zu 1.1 definiert werden. — Ein Code erfüllt die Fano-Bedingung genau dann, wenn in ihm kein Codewort Anfang eines von ihm verschiedenen Codewortes ist. Aufgabe 2: Zeichenreihen über dem endlichen Alphabet A = (a’,’b’,...,'z’) sollen durch vorwärts und rückwärts verkettete Listen dargestellt werden, für deren Anfang und Ende Anker (Verweise) vorgesehen sind. Die Darstellung der Zeichenreihe zI=’abe’ läßt sich also beispielsweise folgendermaßen graphisch veranschaulichen: ZI: + _ Be- a | u ..- tBeBe 7 | ein u liebig Fortsetzung nächste Seite! Herbst 1998 Einzelprüfungsnummer: 46114 Seite: 4 2.1 Geben Sie eine Datenstruktur mit Hilfe geeigneter Typdefinitionen an, durch die sich die o.a. Darstellung von Zeichenreihen realisieren läßt! 2.2 Wie stellen Sie die leere Zeichenreihe e dar? 2.3 Als Länge einer Zeichenreihe bezeichnet man die Anzahl der Zeichen, die sie enthält, wobei mehrfach vorkommende Zeichen entsprechend ihrer Häufigkeit gezählt werden. Die Länge der leeren Zeichenreihe e ist 0. Schreiben Sie eine Funktionsprozedur laenge, die die Länge einer Zeichenreihe berechnet, also folgender Spezifikation genügt: 2.3.1 Eingabeparameter: zl vom Typ ZEICHENREIHE Hinweis: ZEICHENREIHE muß als Typ in Ihrer Antwort zu 2.1 definiert sein. 2.3.2 Der Funktionswert ist vom Typ INTEGER und ist gleich der Länge von 21. Hinweis: Für die leere Zeichenreihe e soll die in Ihrer Antwort zu 2.2 angegebene Darstellung verwendet werden. 2.4 Schreiben Sie zwei Funktionsprozeduren anfang und teil, die feststellen, ob x Anfangsbzw. Teilzeichenreihe einer Zeichenreihe y ist! Die entsprechenden Spezifikationen lauten: 2.4.1 Eingabeparameter (für beide Funktionsprozeduren):; z,y vom Typ ZEICHENREIHE 2.4.2 Der Funktionswert ist jeweils vom Typ BOOLEAN. Er hat den Wert TRUE für die Funktion anfang bzw. teil genau dann, wenn z Anfangs- bzw. Teilzeichenreihe von yist. Hinweis: Es ist empfehlenswert, erst- die Funktionsprozedur anfang zu schreiben und in der Funktionsprozedur teil die Funktion anfang zu verwenden. Die Funktionsprozedur laenge darf verwendet werden. 2.5 Ein Palindrom ist eine Zeichenreihe, die mit ihrer rückwärts gelesenen identisch ist. Beispiele sind ’otto’, 'reliefpfeiler’, e (leere Zeichenreihe). Schreiben Sie eine Funktionsprozedur pelin, die feststellt, ob eine Zeichenreihe ein Palindrom ist, also folgender Spezifikation genügt: 2.5.1 Eingabeparameter: z1 vom Typ ZEICHENREIHE 2.5.2 Die Funktion ist total, d.h. sie Lefert für jede Eingabe-Zeichenreihe einen eindeutig bestimmten Wert. Der Funktionswert ist vom Typ BOOLEAN und ist genau dann gleich TRUE, wenn zl ein Palindrom ist. Hinweis: In der Funktionsprozedur palin darf die unter 2.3 spezifizierte Funktion laenge verwendet werden. Fortsetzung nächste Seite! Herbst 1998 Einzelprüfungsnummer: 46114 Seite: 5 Aufgabe 3: Gegeben seien die Standard-Rechenstrukturen ZZ der ganzen Zahlen und B, der Wahrheitswerte. Wie üblich seien dabei der Typ der Elemente von Z mit INTEGER und der Typ der Elemente von IB, mit BOOLEAN bezeichnet. Als Operationen sind +, -, », / (partiell!) in Z a, A, Vv in B, sowie die Vergleichsoperationen <,= für Elemente aus Z standardmäßig vorgesehen. Durch Abstützung auf die Rechenstrukturen ZZ und IB, soll die im folgenden spezifizierte Teil-Rechenstruktur Q, der rationalen Zahlen Q vollständig dargestellt werden. 3.1 Geben Sie eine Datenstruktur an, mit deren Hilfe sich jede Zahl aus Q im Hinblick auf die folgenden Teilaufgaben geeignet darstellen läßt! Geben Sie außerdem an, welchen Einschränkungen die Objekte der von Ihnen vorgeschlagenen Datenstruktur genügen sollen, damit sie in) zulässig sind! 3.2 Schreiben Sie Prozeduren für die Multiplikation (mult) und die Division (div) inQ . Diese Prozeduren sollen den folgenden Spezifikationen genügen: 3.2.1 Eingabeparameter: a,b: RATIONAL Dabei dürfen Sie unterstellen, daß die von Ihnen in Ihrer Antwort zu 3.1 angegebenen Einschränkungen für in © zulässige Objekte von a und b erfüllt sind! Bei div dürfen Sie außerdem unterstellen, daß 5 nicht die Null darstellt! 3.2.2 Resultatparameter: VAR c: RATIONAL Der Wert von ce muß nach Ausführung von mult gleich a»5 und nach Ausführung von div gleich a/b sein. Dabei muß dieser Wert jeweils den Zulässigkeitseinschränkungen, die Sie in Ihrer Antwort zu 3.1 formuliert haben, genügen! 3.3 Schreiben Sie eine Funktionsprozedur gr, die feststellt, ob eine Zahl a aus Q größer ist als eine Zahl 5b ausQ ! Dabei soll gr folgender Spezifikation genügen: 3.3.1 Eingabeparameter: a,b: RATIONAL Sie dürfen wieder unterstellen, daß a und b den Zulässigkeitseinschränkungen gemäß 3.1 genügen! 3.3.2 Das Resultat ist vom Typ BOOLEAN und hat den Wert TRUE genau dann, wenn a>bist.