Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 66 1 1 5 2021 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft) Einzelprüfung: Algorithmen und Datenstrukturen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 17 Bitte wenden! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Teilaufgabe I: Theoretische Informatik Aufgabe 1 (Reguläre Sprachen und Endliche Automaten) [54 PUNKTE] Im Folgenden bezeichnet a’ = a: --a und e steht für das leere Wort (d.h. insbesondere a = e). i-mal Die Menge No = {0,1,2,...} ist die Menge aller nicht-negativer Ganzzahlen. Die Sprachen Lı,..., Li2 seien definiert als: Ly = {a?” |n E No} Ls = {a®|n€ No} Ly = {at |neN,n>1} Ig ={a?"|nENon>1} Le = {a"|nENo,n> 1} Lio = {a" | n € No, n ist Primzahl} LI; = {a |n E No} I, ={a"|nENon>2} 7, =9 Ig={a" |neENon>1} Lg = {a?™**|nENo} Ly = {e} a) Ordnen Sie jedem der folgenden nichtdeterministischen endlichen Automaten N,, j = 1,...,6, (die alle über dem Alphabet D = {a} arbeiten) jeweils eine der Sprachen L;€ {L,,...,Lıa} zu, sodass L, genau die von N, akzeptierte Sprache ist. a me eH) a a me CI KIEL I Hp: a a a u. 05050 a a Fortsetzung nachste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 3 b) Zeigen Sie für eine der Sprachen Lı,..., Lı2, dass diese nicht regulär ist. c) Konstruieren Sie für den folgenden nichtdeterministischen endlichen Automaten (der Worte über dem Alphabet U = {a,b} verarbeitet) einen äquivalenten deterministischen endlichen Automaten mithilfe der Potenzmengenkonstruktion. Zeichnen Sie dabei nur die vom Start- zustand erreichbaren Zustände. Erläutern Sie Ihr Vorgehen. Aufgabe 2 (CYK-Algorithmus) [15 PUNKTE] Sei G = (V,D, P,S) eine kontextfreie Grammatik mit Variablen V = {$, A,B,C, D}, Terminal- zeichen D = {a,b,c}, Produktionen P={S->AD|CC|e, A-a, B-b, C>CCle, D-SB|CB} und Startsymbol 5. Führen Sie den Algorithmus von Cocke, Younger und Kasami (CYK- Algorithmus) für G und das Wort aaaccbbb aus. Liegt aaacchbb in der durch G erzeugten Sprache? Erläutern Sie Ihr Vorgehen und den Ablauf des CYK-Algorithmus. Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 4 Aufgabe 3 (Disjunktives Postsches Korrespondenzproblem) (29 PUNKTE| Das Postsche Korrespondenzproblem und das disjunktive Postsche Korrespondenzproblem sind definiert als: Postsches Korrespondenzproblem (PCP) Eine Instanz des Postschen Korrespondenzproblems (PCP) besteht aus einer endlichen Folge K von Wortpaaren K = (21,41),---, (2k, Ye) Mit 2;,y; € Lt, wobei U ein Alphabet mit |x| > 1 ist. Das Entscheidungsproblem ist die Frage, ob es eine Folge von Indizes iı,...,ö mit i; € {1,...,k} und m > 0 gibt, sodass 2), ...2i,, = Yar «+ -Yim Gilt. ‚Im Disjunktives Postsches Korrespondenzproblem (DPCP) Eine Instanz des Disjunktiven Postschen Korrespondenzproblems (DPCP) besteht aus einer endlichen Folge K von Worttripeln K = (21, Yı, 21), - - - , (&k, Yk, 2x) mit 2, 9,2; € D*, wobei x ein Alphabet mit |%| > 1 ist. Das Entscheidungsproblem ist die Frage, ob es eine Folge von Indizes i1,...,im mit i; € {l,...,k} und m > 0 gibt, sodass mindestens eine der Gleichungen z;, ...Zin = Yin -: - Yim OGEY Ui, ... Li, = Ziq.» Zig, OUET Yi, --- Yim = Ziq +++ Zin gilt. a) Sei & = {a,b} und K = (ab, b, a), (a,b, b), (b, b, ab) eine DPCP-Instanz. i) Geben Sie eine Folge iı,...,is von Indizes mit i; € {1,2,3} an, die keine Lösung für K ist. Begründen Sie, warum die Folge keine Lösung ist. ii) Geben Sie eine Folge von Indizes an, die eine Lösung für K ist. Begründen Sie, warum die Folge eine Lösung ist. b) Sie dürfen als bekannt annehmen, dass PCP unentscheidbar ist. Zeigen Sie die Unentscheid- barkeit von DPCP, indem Sie PCP auf DPCP reduzieren. Aufgabe 4 (NP-Vollständigkeit) [22 PUNKTE] Eine 3-CNF ist eine Menge von Klauseln, wobei jede Klausel eine Menge aus 0, 1, 2 oder 3 Literalen ist und kein Literal sowohl positiv als auch negativ in derselben Klausel vorkommt. Ein positives Literal ist eine aussagenlogische Variable x;. Ein negatives Literal ist eine negierte aussagenlogische Variable -7;. Z. B. ist F = {{x1, v2, 3}, (41, 22}, {7x1 }} eine 3-CNF. Eine 3-CNF, in der genau die Variablen I{zı,...,2„} vorkommen, ist erfüllbar, wenn es eine Belegung B: {zı,...,2%n} — {0,1} gibt, sodass in jeder Klausel für mindestens ein Literal L gilt: B(L) =1. Dabei gilt 1, wenn B(z;) =0 B(=z;) = 0, wenn B(x,)=1 Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 5 Die 3-CNF F ist erfüllbar, was z.B. die Belegung B mit B(xzı) = 0,B(x2) = 1 und B(z;) =1 bezeugt. Die Entscheidungsprobleme 3-CNF-SAT und GENAU-3-CNF-SAT sind in gegeben/gefragt- Notation wie folgt definiert: 3-CNF-SAT gegeben: Eine 3-CNF F gefragt: Gibt es eine Belegung B, die F erfüllt? GENAU-3-CNF-SAT gegeben: Eine 3-CNF F, wobei jede Klausel aus genau 3 (paarweise verschiedenen) Lite- ralen besteht. gefragt: Gibt es eine Belegung B, die F erfüllt? a) Zeigen Sie, dass 3-CNF-SAT in Polynomialzeit auf GENAU-3-CNF-SAT reduziert werden kann. (Dies wird oft als 3-CNF-SAT <, GENAU-3-CNF-SAT notiert.) b) Zeigen Sie, dass GENAU-3-CNF-SAT NP-vollstandig ist. Dabei dürfen Sie als bekannt an- nehmen, dass 3-CNF-SAT NP-vollständig ist. Die Resultate aus Aufgabenteil a) dürfen verwendet werden. c) Welche Schlussfolgerungen würden sich jeweils für das berühmte offene P Z N P-Problem ergeben, wenn Sie die folgenden Aussagen zeigen könnten? i) GENAU-3-CNF-SAT kann in der Zeit O((k + m) - log.(k + m)) für jede 3-CNF mit k Klauseln und m paarweise verschiedenen Variablen gelöst werden. ii) Jede deterministische Turingmaschine, die GENAU-3-CNF-SAT löst, benötigt im Worst-Case N(2”) Schritte (als untere Schranke), wobei n die Anzahl der Klauseln in der Eingabe ist. iii) Es gibt eine deterministische Turingmaschine, die 3-CNF-SAT im Worst-Case in O(2”) Schritten (als obere Schranke) löst, wobei n die Anzahl der Klauseln in der Eingabe ist. Fortsetzung nächste Seite! Frühjahr 2021 Teilaufgabe II: Algorithmen Aufgabe 1 (Sortieren) Einzelprüfungsnummer: 66115 Seite: 6 [26 PUNKTE| a) Geben Sie für folgende Sortierverfahren jeweils zwei Felder A und B an, so dass das jeweilige Sortierverfahren angewendet auf A seine Best-Case-Laufzeit und angewendet auf B seine Worst-Case-Laufzeit erreicht. (Wir messen die Laufzeit durch die Anzahl der Vergleiche zwischen Elementen der Eingabe.) Dabei soll das Feld A die Zahlen 1,2,...,7 genau einmal enthalten; das Feld B ebenso. Sie bestimmen also nur die Reihenfolge der Zahlen. Wenden Sie als Beleg für Ihre Aussagen das jeweilige Sortierverfahren auf die Felder A und B an und geben Sie nach jedem größeren Schritt des Algorithmus den Inhalt der Felder an. Geben Sie außerdem für jedes Verfahren asymptotische Best- und Worst-Case-Laufzeit für ein Feld der Länge n an. Die im Pseudocode verwendete Unterroutine Swap (A,i,j) vertauscht im Feld A die jeweiligen Elemente mit den Indizes i und j miteinander. i) Insertionsort ii) Standardversion von Quicksort (Pseudocode s.u., Feldindizes beginnen bei 1), bei der das letzte Element eines Teilfeldes als Pivot-Element gewählt wird. iii) QuicksortVar: Variante von Quicksort, bei der immer das mittlere Element eines Teil- feldes als Pivot-Element gewählt wird (Pseudocode s.u., nur eine Zeile neu). Bei einem Aufruf von PartitionVar auf ein Teilfeld Al£..r] wird also erst mithilfe der Unterroutine Swap A[|(€+r —1)/2|] mit Afr] vertauscht. Quicksort(A, 2 = 1,r = A.length) if 2 2 den Aufbau eines schwach zusam- menhängenden Graphen G, mit n Knoten, bei dem die Breitensuche ®(n) mal gestartet werden muss, bis alle Knoten markiert sind. b) Welche asymptotische Laufzeit in Abhängigkeit von der Anzahl der Knoten (n) und von _ der Anzahl der Kanten (m) hat die Breitensuche über alle Neustarts zusammen? Beachten Sie, dass die Markierungen nicht gelöscht werden. Geben Sie die Laufzeit in 8-Notation an. Begründen Sie Ihre Antwort. Aufgabe 4 (Kürzeste-Wege-Bäume und minimale Spannbäume) [16 PUNKTE] Die Algorithmen von Dijkstra und Jarník-Prim gehen ähnlich vor. Beide berechnen, ausgehend von einem Startknoten, einen Baum. Allerdings berechnet der Algorithmus von Dijkstra einen Kürzesten-Wege-Baum, während der Algorithmus von Jarník-Prim einen minimalen Spannbaum berechnet. a) Geben Sie einen ungerichteten gewichteten Graphen G mit höchstens fünf Knoten und einen Startknoten s von G an, so dass Dijkstra(G,s) und Jarník-Prim(G,s) ausgehend von s verschiedene Bäume in G liefern. Geben Sie beide Bäume an. b) Geben Sie eine unendlich große Menge von Graphen an, auf denen der Algorithmus von Jarník-Prim asymptotisch schneller ist als der Algorithmus von Kruskal, der ebenfalls mini- male Spannbäume berechnet. Hinweis: Für einen Graphen mit n Knoten und m Kanten benötigt Jarník-Prim O(m+nlogn) Zeit, Kruskal O(mlogm) Zeit. Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 8 c) Sei Z die Menge der zusammenhängenden Graphen und G € Z. Sein die Anzahl der Knoten von G und m die Anzahl der Kanten von G. Entscheiden Sie mit Begründung, ob logm € O(log n) gilt. Aufgabe 5 (Projektplanung) [24 PUNKTE] Sie sind Projektleiter und sollen einen Projektplan aufstellen. In der nächsten Zeit sind eine Menge A von Aufgaben zu erledigen, wobei Sie wissen, dass die Erledigung jeder Aufgabe a in A eine gewisse Anzahl £(a) Stunden benötigt. Außerdem hängen manche Aufgaben von anderen Aufgaben ab. Sie haben also zu jeder Aufgabe a eine (möglicherweise leere) Menge N(a) C A von Aufgaben, die erst erledigt werden können, wenn a abgeschlossen ist. Zusätzlich gibt es für jede Aufgabe a’ € N(a) eine Zeitdauer w(a, a’), die Sie nach der Erledigung von a warten müssen, bis Sie a’ beginnen können. a) Modellieren Sie das Problem graphentheoretisch. Beantworten Sie folgende Fragestellungen aus graphentheoretischer Sicht. b) Wovon hängt es ab, ob es einen Projektplan gibt, der von vorne bis hinten abgearbeitet werden kann? c) Wie können Sie einen solchen Projektplan berechnen, d. h. wie können Sie eine Reihenfolge der Aufgaben ermitteln, bei der alle Abhängigkeiten berücksichtigt sind? d) Angenommen, Sie haben eine sinnvolle Reihenfolge aı,a>,...,Q, der Aufgaben in A gefun- den — geben Sie einen Algorithmus an, der berechnet, wie viele Stunden es dauert, Ihren Projektplan auszuführen. Ihr Algorithmus soll für © = 2,3,...,n die Startzeit s; und die Endzeit e; der Aufgabe a; berechnen. Für die erste Aufgabe a, gelte sı = 0 und eı = £(a,). Aufgabe 6 (Sondierfolgen für Hashing mit offener Adressierung) [22 PUNKTE] Eine Sondierfolge s(k,i) liefert für einen Schlüssel k aus einem Universum U und Versuchsnum- mern ö = 0,1,...,m— 1 eine Folge von Indizes für eine Hashtabelle T/0...m — 1]. Mithilfe ei- ner Sondierfolge wird beim Hashing mit offener Adressierung z. B. beim Einfügen eines neuen Schlüssels k nach einem noch nicht benützten Tabelleneintrag gesucht. Seien h und h’ zwei ver- schiedene Hashfunktionen, die U auf {0,1,...,m — 1} abbilden. Beantworten Sie die folgenden Fragen und geben Sie an, um welche Art von Sondieren es sich jeweils handelt. a) Was ist problematisch an der Sondierfolge s(k,i) = (h(k) + 25) mod m, wobei m = 1023 die Größe der Hashtabelle ist? b) Was ist problematisch an der Sondierfolge s(k,£) = (h(k)+i(i+1)) mod m, wobei m = 1024 die Größe der Hashtabelle ist? c) Was ist vorteilhaft an der Sondierfolge s(k,i) = (h(k) +i- h’(k)) mod m, wobei m die Größe der Hashtabelle ist? Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 9 d) Sei h(k) = k mod 6 und h’(k) = k? mod 6. Fügen Sie die Schlüssel 14, 9, 8, 3, 2 nacheinander in eine Hashtabelle der Größe 7 ein. Verwenden Sie die Sondierfolge s(k,i) = (h(k) +i- h’(k)) mod 7 und offene Adressierung. Notieren Sie die Indizes der Tabellenfelder und vermerken Sie neben jedem Feld die erfolg- losen Sondierungen. -10- Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 10 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Teilaufgabe I: Theoretische Informatik Aufgabe 1 (Reguläre Sprachen) [30 PUNKTE]| a) Sei Ly, = {w € {a,b,c}* | w enthält genau zweimal den Buchstaben a und der vorletzte Buchstabe ist ein c}. Geben Sie einen regulären Ausdruck für die Sprache L, an. b) Konstruieren Sie einen deterministischen endlichen Automaten für die Sprache La: La = {w € {a,b}* | w enthält genau einmal das Teilwort aab} . c) SeiN= {1,2,3,...} die Menge der strikt positiven natürlichen Zahlen. Sei Ls = {#0 #a?#---a-i#a# | n,i1,...,in EN und es existiert 7 € N mit 1; =n+1} eine Sprache über Alphabet {#, a}. So ist z.B. #a#aaa# € L; (da das Teilwort a? = aaa vorkommt) und #a#ta#a#a# ¢ L3 (da das Teilwort a° = aaaaa nicht vorkommt). Beweisen Sie, dass L3 nicht regulär ist. Aufgabe 2 (Kontextfreie Sprachen) [30 PUNKTE] a) Zeigen Sie, dass die Sprache Lı = {wwıwwz | w, wı, wa € {a,b,c}* und 2|w| > |wı| + |wa]} nicht kontextfrei ist. b) Betrachten Sie die Aussage Seien Lı,..., Im beliebige kontextfreie Sprachen. Dann ist (\j_, Li immer eine entscheidbare Sprache. Entscheiden Sie, ob diese Aussage wahr ist oder nicht und begründen Sie Ihre Antwort. c) Sei No = {0,1,2,...} die Menge der nicht negativen natürlichen Zahlen. Es ist bekannt, dass L = {a"b"c" | n € N} keine kontextfreie Sprache ist. Ist die Komplementsprache Ls = {a, b,c}* \ L kontextfrei? Begründen Sie Ihre Antwort. Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 11 Aufgabe 3 (Entscheidbarkeit) [30 PUNKTE] Wir betrachten eine Gödelisierung von Turingmaschinen und bezeichnen mit M„ die Turingma- schine, die gemäß der Kodierung des Binärworts w kodiert wird. Außerdem bezeichnen wir mit Mu(x) die Ausgabe der Maschine M, bei Eingabe x. Sie dürfen davon ausgehen, dass x immer ein Binärstring ist. Der bekannte Satz von Rice sagt: Sei S eine Menge berechenbarer Funktionen mit @ 4 S #4 R, wobei R die Menge aller berechenbaren Funktionen ist. Dann ist die Sprache {w | fi, € S} unentscheidbar. Hier ist fixz,, die von M, berechnete Funktion. Zeigen Sie für jede der nachfolgenden Sprachen über dem Alphabet {0,1} entweder, dass sie entscheidbar ist, oder zeigen Sie mit Hilfe des Satzes von Rice, dass sie unentscheidbar ist. Geben Sie beim Beweis der Unentscheidbarkeit die Menge S der berechenbaren Funktionen an, auf die Sie den Satz von Rice anwenden. Wir bezeichnen die Länge der Eingabe x mit |z|. a) {w | M, akzeptiert die Binarkodierungen der Primzahlen (und lehnt alles andere ab)} b) {w | es gibt eine Hingabe x, so dass M,„(x) das Symbol 1 enthält} c) {w | M„(x) hält für jedes x mit |x| < 1000 nach höchstens 100 Schritten an} d) {w | M, hat für jede Eingabe dieselbe Ausgabe} e) {w | die Menge der Eingaben, die von M,, akzeptiert werden, ist endlich} Aufgabe 4 (Komplexität) [30 PUNKTE] Betrachten Sie die folgenden Probleme: CLIQUE Gegeben: Ein ungerichteter Graph G = (V, E), eine Zahlk E N Frage: Gibt es eine Menge S C V mit |S| = k, sodass für alle Knoten u$veV gilt, dass {u,v} eine Kante in E ist? ALMOSTCLIQUE Gegeben: Ein ungerichteter Graph G = (V, E), eine Zahl k e N Frage: Gibt es eine Menge S C V mit |S| = k, sodass die Anzahl der Kanten zwischen Knoten in S genau ke) — 1 ist? Zeigen Sie, dass das Problem ALMOSTCLIQUE NP-vollständig ist. Nutzen Sie dafür die NP- Vollständigkeit von CLIQUE. Hinweis: Die Anzahl der Kanten einer k-Clique sind AD, Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 12 Teilaufgabe II: Algorithmen Aufgabe 1 (O-Notation) [24 PUNKTE] a) Sortieren Sie die unten angegebenen Funktionen der O-Klassen O(a), O(b), O(c), O(d) und O(e) beziiglich ihrer Teilmengenbeziehungen. Nutzen Sie ausschließlich die echte Teilmenge € sowie die Gleichheit = für die Beziehung zwischen den Mengen. Folgendes Beispiel illustriert diese Schreibweise für einige Funktionen fı bis fs. (Diese haben nichts mit den unten angegebenen Funktionen a bis e zu tun.) O(fa) S O(fs) = O(fs) S O(f1) = O(f2) Die von Ihnen anzugebenden Teilmengenbeziehungen miissen weder bewiesen noch be- gründet werden. a(n) = 3n? + Yan e b(n) = 3!%z{r) e c(n) = 37! e d(n) =n? — logy n™® e e(n) = 2"/? Gegeben seien drei Funktionen f,9,k: N— R$. Wir definieren die Funktion (f +9): Ny + Ron f(n) + 9(n). Beweisen Sie die folgenden Aussagen formal nach den Definitionen der O-Notation oder widerlegen Sie sie. (i) fe O(h)Ag € O(h) > f+g € OA). (ii) f € O(h) Ag € O(h) > f +g € O(h). Bestimmen Sie eine asymptotische Lösung (in O-Schreibweise) für die folgende Rekursions- gleichung: n n T(n)=3- T(z) +5 Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 13 Aufgabe 2 (Implementierung) [19 PUNKTE] Gegeben sei die folgende Java-Implementierung einer doppelt-verketteten Liste. class DoubleLinkedList { private Item head; public DoubleLinkedList () f head = null; } public Item append(Object val) { if (head == null) { head = new Item(val, null, null); head.prev = head; head.next head; } else { Item iten new Item(val, head.prev, head); head.prev.next = iten; head.prev = iten; } return head.prev; } public Item search(Object val) { // } public void delete(Object val) { // } class Item { private Object val; private Item prev; private Item next; public Item(Object val, Item prev, Item next) { this.val = val; this.prev = prev; this.next next; a) Skizzieren Sie den Zustand der Datenstruktur nach Aufruf der folgenden Befehlssequenz. Um Variablen mit Zeigern auf Objekte darzustellen, können Sie mit dem Variablennamen beschriftete Pfeile verwenden. Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 14 DoubleLinkedList list = new DoubleLinkedList (); list.append("a"); list.append("b"); list.append("c"); Implementieren Sie in der Klasse DoubleLinkedList die Methode search, die zu einem gegebenen Wert das Item der Liste mit dem entsprechenden Wert, oder null falls der Wert nicht in der Liste enthalten ist, zurückgibt. Implementieren Sie in der Klasse DoubleLinkedList die Methode delete, die das erste Vorkommen eines Wertes aus der Liste entfernt. Ist der Wert nicht in der Liste enthalten, terminiert die Methode „stillschweigend“, d. h. ohne Änderung der Liste und ohne Fehler- meldung. Sie dürfen die Methode search aus Teilaufgabe b) verwenden, auch wenn Sie sie nicht implementiert haben. Beschreiben Sie die notwendigen Änderungen an der Datenstruktur und an den bisherigen Implementierungen, um eine Methode size, die die Anzahl der enthaltenen Items zurück gibt, mit Laufzeit O(1) zu realisieren. Aufgabe 3 (Binärbäume) [20 PUNKTE] a) Betrachten Sie folgenden Binérbaum T. Geben Sie die Schlüssel der Knoten in der Reihenfolge an, wie sie von einem Preorder- Durchlauf (= TreeWalk) von T ausgegeben werden. Betrachten Sie folgende Sequenz als Ergebnis eines Preorder-Durchlaufs eines binären Such- baumes T. Zeichnen Sie T und erklären Sie, wie Sie zu Ihrer Schlussfolgerung gelangen. [8,7,4,2,1,3,5,6,10,9,11] Hinweis: Welcher Schlüssel ist die Wurzel von 7’? Welche Knoten sind in seinem linken /rech- ten Teilbaum gespeichert? Welche Schlüssel sind die Wurzeln der jeweiligen Teilbäume? Anstelle von sortierten Zahlen soll ein Baum nun verwendet werden, um relative Positions- angaben zu speichern. Jeder Baumknoten enthält eine Beschriftung und einen Wert (vgl. Abb. 1), der die ganzzahlige relative Verschiebung in horizontaler Richtung gegenüber sei- nem Elternknoten angibt. Die zu berechnenden Koordinaten für einen Knoten ergeben sich Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 15 aus seiner Tiefe im Baum als y-Wert und aus der Summe aller Verschiebungen auf dem Pfad zur Wurzel als x-Wert. Das Ergebnis der Berechnung ist in Abb. 2 visualisiert. Geben Sie einen Algorithmus mit linearer Laufzeit in Pseudo-Code oder einer objektorientierten Programmiersprache Ihrer Wahl an. Der Algorithmus erhält den Zeiger auf die Wurzel ei- nes Baumes als Eingabe und soll Tupel mit den berechneten Koordination aller Knoten des Baums in der Form (Beschriftung, x, y) zurück- oder ausgeben. Ca? 1D x DI Er D aD Ce’, OD Abb. 1 Abb.2. Aufgabe 4 (TripleSort) 40 PUNKTE] Im folgenden ist ein Algorithmus in Pseudocode gegeben, der die Zahlen in einem gegebenen Array sortieren soll. ı TripleSort(int[] A, int £, int r) 2 n=r—-t+l 3 if n = 2 then 4 min = min(Alf], Alr]) 5 maa = max(A[é], A[r]) 6 AL = min 7 Alr] = maz 8 else if n > 2 then 8 d=|3] 10 TripleSort(A, &,r—d) 11 TripleSort (A, +d, r) 12 | TripleSort (A, é, r—d) a) Führen Sie den Algorithmus auf dem absteigend sortierten Array A = [6,5,4,3,2,1] mit £=1undr= 6 aus. Geben Sie für jeden Aufruf die Rekursionstiefe, die Parameter und den Zustand des Arrays vor bzw. nach dem Aufruf an. Sie können hier z. B. eine Tabelle mit den Spalten Tiefe, £, r, A[1], A[2], ..., A[6] und zwei Zeilen je Aufruf (eine für davor und eine für danach) verwenden. Bereiche, die vom aktuellen Aufruf nicht betrachtet oder verändert werden, müssen Sie nicht erneut angeben. Rekursive Aufrufe von tripleSort, bei denen der Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 16 zu sortierende Bereich drei Elemente oder weniger enthält, können Sie direkt lösen. Damit kann Ihre Antwort das folgende Format haben: tl e}r | Aly apa | als) | alg Ais} | als less [ala 2 | 1 3124| . 5 4 3 . . 3/2)4] . 3 4 5 . . (direkt sortiert) b) Wie muss die Eingabe für den Algorithmus im Allgemeinen aussehen, sodass (im initialen Aufruf) der dritte rekursive Aufruf von TripleSort in Zeile 12 keine Anderung bewirkt? c) Beweisen Sie die Korrektheit des Algorithmus. Hinweis: Wo befinden sich die an größten Werte nach dem ersten rekursiven Aufruf? d) Bestimmen Sie die asymptotische Laufzeit des Algorithmus in Abhangigkeit von n = r—£+1. Aufgabe 5 (Hashing) [17 PUNKTE] a) Nennen Sie zwei wünschenswerte Eigenschaften von Hashfunktionen. b) Wie viele Elemente können bei Verkettung und wie viele Elemente können bei offener Adres- sierung in einer Hashtabelle mit m Zeilen gespeichert werden? c) Angenommen, in einer Hashtabelle der Größe m sind alle Einträge (mit mindestens einem Wert) belegt und insgesamt n Werte abgespeichert. Geben Sie in Abhängigkeit von m und n an, wie viele Elemente bei der Suche nach einem nicht enthaltenen Wert besucht werden müssen. Sie dürfen annehmen, dass jeder Wert mit gleicher Wahrscheinlichkeit und unabhängig von anderen Werten auf jeden der m Plätze abgebildet wird (einfaches gleichmäßiges Hashing). d) Betrachten Sie die folgende Hashtabelle mit der Hashfunktion h(x) = x mod 11. Hierbei steht @ für eine Zelle, in der kein Wert hinterlegt ist. Index 2] OD 1 | s| 7 wert | 11 | so) a 16 | 28 | 18 | 0 | 0| 3 Führen Sie nun die folgenden Operationen mit offener Adressierung mit linearem Sondieren aus und geben Sie den Zustand der Datenstruktur nach jedem Schritt an. Werden für eine Operation mehrere Zellen betrachtet, aber nicht modifiziert, so geben Sie deren Indizes in der betrachteten Reihenfolge an. Fortsetzung nächste Seite! Frühjahr 2021 Einzelprüfungsnummer: 66115 Seite: 17 i) Insert 7 ii) Insert 20 iii) Delete 18 iv) Search 7 v) Insert 5