Fragenkatalog zum Selbsttest: ============================= Hiermit kann man seinen eigenen Wissensstand überprüfen. Dabei beachte man aber, dass diese Fragenliste nicht unbedingt die Art Fragen enthält, die in einer Klausur vorkommen können. (Aber in die Richtung geht es bei manchen Fragen schon.) Um einen besseren Eindruck zu bekommen, welche Art von Fragen in einer Klausur vorkommen können, konsultiere man die im Netz hängenden alten Klausuren. Nach dem "#" die jeweilige Skriptseite, wobei sie sich die Numerierung auf das Skript aus dem Sommer 2004 bezieht. Die Fragen sind nach diesen Skriptseiten geordnet. ===================================================== Definiere das "Maxsummenproblem". #05 Erkläre den naiven Algorithmus für das Maxsummenproblem. Welche Laufzeit hat er und warum ist diese so? Welche Operationen zählt man überhaupt bei der Analyse? #05 Beschreibe den "normalen" Algorithmus für das Maxsummenproblem. Welche Laufzeit hat er und warum ist diese so? #06/07 Beschreibe den Divide-and-Conquer-Algorithmus für das Maxsummenproblem. In welche Klassen teilt man die Menge aller Intervalle ein? Welche davon werden rekursiv gelöst, welche direkt? Stelle die Rekursionsgleichung für die Laufzeit auf und löse sie. #07/08 Beschreibe den Ansatz via Dynamischer Programmierung für das Maxsummenproblem. Erkläre die Bedeutung der dabei benutzten Parameter. Erkläre, wie man die "neuen" Parameter aus den "alten" berechnet und begründe, warum dies funktioniert. Welche Laufzeit hat dieser Ansatz und warum ist sie so? #08/09 Was ist das Fazit, das man aus den betrachteten Maxsummenalgorithmen bzw. deren Laufzeiten ziehen kann? #10 Definiere das MAXMIN-Problem. #10 Wieviele Spiele finden beim trivialen Vorgehen beim MAXMIN-Problem statt? #10 Beschreibe die "obere Schranke" für das MAXMIN-Problem: Wie sieht der Turnierplan aus? Wieviele Spiele finden statt? Warum ist die Zahl so, wie sie ist? #11 Beschreibe die untere Schranke für das MAXMIN-Problem: Wie lautet die Schranke? Beweise sie: Erkläre, was Informationseinheiten sind, welche Arten von Spielern gibt es und wieviele Informationseinheiten liefern die jeweiligen Spiele? #12 Warum haben wir das Modell der Registermaschinen betrachtet? #13 Wie ist eine RAM aufgebaut? Welche Art von Befehlen gibt es? #13 Was versteht man unter "uniformem", was unter "logarithmischem" Kostenmaß? #14 Gib ein Beispiel an, bei dem sich uniformes und logarithmisches Kostenmaß gewaltig unterscheiden. (Beweise, dass die Kosten so sind, wie sie sind.) #14 Wie ist die Laufzeit T_P(x) eines RAM-Programms definiert? Wie der Platzbedarf? #15 Wie ist die worst-case-Rechenzeit T_P(n) eines RAM-Programms definiert? Wie ist die Definition, wenn man eine Wahrscheinlichkeitsverteilung über die Inputs hat? #15 Wie sieht der Pseudocode aus für das "Erhöhen eines Binärzählers"? Welche Operationen zählt man bei der average-case-Analyse? #16 Analysiere die durchschnittliche Taktzahl eines Binärzählers mit Hilfe des "Direkten Zählens". #16 Analysiere die durchschnittliche Taktzahl eines Binärzählers mit Hilfe einer Potenzialfunktion. Wie ist die Potenzialfunktion definiert? #17 Analysiere die durchschnittliche Taktzahl eines Binärzählers mit Hilfe der "direkten Analyse". #17 Was sind randomisierte Algorithmen? Für welche Laufzeit interessiert man sich bei diesen? #18 Definiere formal, wann man f=O(g) schreiben kann. Wann ist f=Omega(g)? Wann ist f=Theta(g)? Was besagt f=o(g), was f=klein-omega(g)? #18 Beweise, dass n hoch k = klein-o(2 hoch n) für alle Konstanten k gilt. #19 Wann heißt eine Funktion f "polynomiell beschränkt"? Wann wächst eine Funktion f exponentiell? #20 Analysiere, um wieviel größere Probleme man lösen kann, wenn man sich einen 10fach schnelleren Rechner kauft und das Problem, das man lösen möchte, mit einem Algorithmus gelöst wird, dessen Laufzeit f(n) ist. #21 Was bezeichnet man mit "linearer Suche" in einem Array? Schreibe "binäre Suche" in einem sortierten Array als Pseudocode hin. Welche Invariante gilt bei Ablauf der binären Suche? Gib die worst-case-Laufzeit an und beweise sie. #23 Erkläre, was man unter geometrischer Suche versteht. Welche worst-case-Laufzeit hat diese? Wann sollte man geometrische Suche statt binärer Suche verwenden? #24 Welche Laufzeiten benötigt, zum Beispiel, die Operation "Suchen eines Elements" bei Listen/Arrays? Gib ein paar andere typische Operationen mit ihren Laufzeiten an. Welche Operationen werden von Arrays zum Beispiel nicht unterstützt? #25 Welche Datenstrukturen für Mengen kennst Du? #26 Erkläre, was man unter der Bitvektordarstellung bei Mengen versteht. Erkläre, wie man Mengen mit Listen implementieren kann und analysiere die Laufzeiten für die Operation "Vereinigung" in beiden Fällen. #27 Wie sind gerichtete und ungerichtete Graphen definiert? #28 Wir betrachten allgemeine Graphen G, ungerichtet/gerichtet: Wann heißen zwei Knoten adjazent? Wann heißt ein Knoten w Nachbar eines Knotens v? Wann heißen eine Kante und ein Knoten inzident? Was versteht man unter dem Grad eines Knotens? Was versteht man unter dem Eingangs-/Ausgangsgrad eines Knotens? #28 Was versteht man unter einem Weg der Länge k in einem Graphen G? #28 Wann heißt ein Weg in einem Graphen *einfach*? #28 Wie ist ein "Kreis" definiert, und zwar im ungerichteten Fall? Wie ist ein "Kreis" definiert, und zwar im gerichteten Fall? #28 Wann heißt ein Graph azyklisch? #28 Wann heißt ein ungerichteter Graph zusammenhängend, wann heißt ein gerichteter Graph stark zusammenhängend? #28 Welche Äquivalenzrelation kann man auf Knoten in Graphen definieren, wenn es um den Begriff "Zusammenhang" geht? #28 Was versteht man unter einer Zusammenhangskomponente? Was versteht man unter einer starken Zusammenhangskomponente? #29 Zeichne ein Beispiel für einen gerichteten Graphen und seine starken Zusammenhangskomponenten auf. #29 Welche drei grundlegenden Datenstrukturen gibt es für Graphen? #29 Was versteht man unter einer Inzidenzmatrix, was unter einer Adjazenzmatrix, was unter einer Adjazenzliste? #29 Erkläre Vor- und Nachteile von Inzidenzmatrizen/Adjazenzmatrizen/Adjazenzlisten- Darstellung von Graphen. #29/30 Problem "Topologisches Sortieren": Was ist Eingabe, was wird gesucht? Zeichne ein Beispiel für einen Graphen G und eine topologische Sortierung seiner Knoten. #30 Definiere *formal*, was eine topologische Sortierung ist. #30 Was gibt es in einem kreisfreien gerichteten Graphen immer? #30, Lemma 2.5.3 Beweise, dass es in jedem kreisfreien gerichteten Graphen immer einen Knoten mit Ausgangsgrad 0 gibt. #30 Was ist die Grundidee des Algorithmus für das Topologische Sortieren? #31 Erkläre, wie der Algorithmus für das topologische Sortieren funktioniert. Beweise induktiv, dass er korrekt ist. #31 Beschreibe, wie man den Algorithmus für das topologische Sortieren *implementiert*. Wofür benutzt man den Stack, etc. Analysiere die Laufzeit des Algorithmus. topologische Sortieren. (Wie ist die Laufzeit überhaupt?). #32 Wie ist eine partielle Ordnung definiert, wie eine totale (im Skript auch "vollständig" genannt) Ordnung? #32 Wie kann man eine partielle Ordnung durch einen gerichteten Graphen darstellen? #32 Beweise, dass der Graph, der eine partielle Ordnung darstellt, kreisfrei ist. #32 Gib ein Beispiel an für eine Ordnung, die partiell, aber nicht total/vollständig ist. *Beweise*, dass die Ordnung nicht total/vollständig ist. #33 Wieso kann man partiell geordnete (endliche) Mengen topologisch sortieren? Beschreibe einen Algorithmus dafür. #33 Wie ist ein ungerichteter Baum definiert? #33 Wie ist ein gerichteter Baum definiert? #33 Wann heißt in einem Baum B ein Knoten v "Vater/Elter" von w, wann sind v und w "Geschwister", wann sind sie Nachfolger bzw. Vorgänger voneinander? #34 Wie ist in einem gerichteten Baum ein Blatt definiert? Was versteht man unter den "inneren Knoten"? #34 Wie ist die Tiefe eines Knotens v in einem gerichteten Baum definiert? Wie ist die Tiefe eines gerichteten Baums definiert? #34 Was versteht man unter einem k-ären Baum, was unter einem vollständigen k-ären Baum der Tiefe d? #34 Wieviele Knoten hat ein vollständiger k-ärer Baum der Tiefe d? Beweise Deine Antwort. #34 Welche Durchlaufreihenfolgen für die Knoten eines gerichteten Baumes kennst Du? #35 Erkläre, was man unter Präorder, Postorder bzw. Inorder versteht. Male einen Baum hin und dazu die jeweiligen Ausgaben, die man mit Präorder, Postorder bzw. Inorder bekäme. #35 Beschreibe die Grundidee von DFS für ungerichtete Graphen. Welche Kanten sollen als Tree-, welche als Back-Kanten klassifiziert werden? #37 Was berechnet der Tiefensuchalgorithmus DFS? #37 Beschreibe in Pseudocode, wie der DFS-Algorithmus für ungerichtete Graphen funktioniert. Erläutere dabei insbesondere die benutzten Parameter/Arrays. Wie stellt der Algorithmus fest, ob eine Kante eine B-Kante oder eine T-Kante ist? Wieso benutzt man den zweiten Parameter im Aufruf DFS(v,u)? #37 Wie ist die Laufzeit des DFS-Algorithmus? Zeige, dass die Laufzeit so ist. #37 Zeige, dass jede Kante im ungerichteten Graphen durch den DFS-Algorithmus genau einmal klassifiziert wird. #38 Der DFS-Algorithmus erzeugt für ungerichtete Graphen einen Wald. Wem entsprechen die einzelnen Bäume? #38 Gib in Pseudocode den DFS-Algorithmus für gerichtete Graphen an. Wozu dient der Parameter alpha? #39 Beschreibe, wie bei gerichteten Graphen die Kanten durch den DFS-Algorithmus klassifiziert werden. Erkläre insbesondere, wie der Algorithmus anhand der alpha- und num-Werte die Klassifizierung vornimmt. #39 Erkläre den BFS-Algorithmus. Beschreibe in Pseudocode den Ablauf des Algorithmus. #40 Datenstrukturen für Intervalle: Was ist die Eingabe und welche Operationen sollen durch die Datenstruktur unterstützt werden? Was versteht man unter Preprocessingzeit und Queryzeit? #41 Beschreibe die drei trivialen Datenstrukturen für Intervalle und gib jeweils die worst-case-Laufzeiten für Query/Update bzw. das Preprocessing an. Wie sieht es mit dem Speicherplatz aus? #41 Erkläre, wie die Struktur eines Segmentbaums ist. Wozu korrespondieren die einzelnen Knoten und welche Informationen sind an den jeweiligen Knoten abgespeichert? #42 Zeichne für das Array [-1,3,5,4,16] den zugehörigen Segmentbaum hin. #42 (Skript enthält natürlich für das konkrete Bsp. keine Antwort) Wenn im Segmentbaum ein Knoten das Intervall [l...r] repräsentiert, welche Intervalle werden dann an seinen Kindern repräsentiert (vorausgesetzt, er besitzt welche)? #42 Wie tief ist ein Segmentbaum für ein Array mit n Elementen? Wieviele Knoten besitzt er? #42 Beweise, dass ein Segmentbaum für ein n-elementiges Array genau 2n-1 Knoten besitzt. #42 Erkläre, wie der Segmentbaum aufgebaut wird. ("Preprocessing-Phase"). Welche Laufzeit hat dieser Aufbau und wieso ist sie so? #43 Erkläre mit geeigneter Visualisierung, welche Fälle bei query(i,j) in Segmentbäumen auftreten können. #43 Beschreibe in Pseudocode, wie query(i,j) in Segmentbäumen abgearbeitet wird. #43 (Segmentbäume:) Wann heißen Knoten linksbündig/rechtsbündig/bündig? #44 Gegeben eine query(i,j)-Anfrage an einen Segmentbaum. Wieviele Knoten werden maximal aufgesucht, wenn wir in einem bündigen Knoten sind, an dem ein Baum der Tiefe d hängt? Beweise dies! #44 Gegeben eine query(i,j)-Anfrage an einen Segmentbaum. Wieviele Knoten werden maximal aufgesucht, wenn wir in einem "beliebigen" Knoten sind, an dem ein Baum der Tiefe d hängt? Beweise dies! #44 (Segmentbäume:) Welche Laufzeit hat eine query(i,j)-Anfrage im worst-case? Begründe Deine Antwort. #44 Erkläre, wie eine "update"-Operation im Segmentbaum funktioniert. Wie ist die Laufzeit und warum ist sie so? #45 (Bzw. auf den entsprechenden Folien) Was versteht man unter einer Partition? #45 Welche Operationen soll eine UNION-FIND-Datenstruktur effizient unterstützen? #45 Worauf kommt es bei der Namensgebung für die Mengen bei den UNION-FIND-Datenstrukturen an? #45 Erkläre die erste triviale Datenstruktur für UNION-FIND. Gib die Laufzeiten für UNION und FIND an und begründe sie. Wiederhole das für die zweite triviale Datenstruktur. #45 Erkläre die UNION-FIND-Datenstruktur für schnelle FIND-Befehle. Wie ist die Laufzeit von FIND? Wie ist die Laufzeit von UNION(A,B), wenn A und B Mengen sind, die Kardinalitäten |A| und |B| haben? #46 Welche Laufzeit hat die UNION-FIND-Datenstruktur für die schnellen FIND-Befehle, wenn man m FIND und n-1 UNION-Befehle vorliegen hat? #46 Beweise, dass die n-1 UNION-Befehle bei der UNION-FIND-Datenstruktur für schnelle FINDs mit Laufzeit O(n log n) auskommen. (Stichwort "Buchhaltermethode"). Gib ein Beispiel an, das zeigt, dass die Analyse fast optimal ist. #46 Beschreibe die Datenstruktur, die schnelle UNION-Befehle gestattet. Erkläre, wie man sie mit welchen Arrays implementieren würde. Wie funktionieren UNION- und FIND-Befehle bei dieser Datenstruktur? #47 Beweise, dass die Tiefe bei der baumorientierten Datenstruktur für UNION-FIND durch O(log n) beschränkt ist. #48 Welche Laufzeit haben n-1 UNION- und m FIND-Befehle bei der baumorientierten Datenstruktur ohne Pfadkomprimierung? Beweise Deine Aussage. #48 Erkläre, was man unter Pfadkomprimierung versteht. Wenn man die UNION-FIND-Datenstruktur mit Pfadkomprimierung verwendet, welche Laufzeit hat man dann bei n-1 UNION und m FIND-Befehlen? #49 Wie ist die Zweierturmfunktion definiert? Wie ist die Funktion log* definiert? #49 Gib ein Beispiel, wofür man UNION-FIND-Datenstrukturen verwenden kann. #49 Definiere, was man unter einem Spannbaum versteht. Wie ist das Problem "minimaler Spannbaum" definiert? #50 Beschreibe den Algorithmus von Kruskal. #50 Zeige, dass der Algorithmus von Kruskal einen Spannbaum berechnet, genauer: Zeige, dass die berechnete Kantenmenge einen zusammenhängenden und kreisfreien Graphen bildet. #50 Kernstück des Korrektheitsbeweises von Kruskal ist ein bestimmtes Lemma. Gib die Aussage des Lemmas an. (Entweder in der alten Skriptversion oder in der in der Vorlesung vorgestellten Version!) #51 Beweise das entscheidende Lemma, mit Hilfe dessen die Korrektheit des Algorithmus von Kruskal bewiesen wird. Erkläre, wie sich aus dem Lemma die Korrektheit ergibt. #51/52 Mit welchen Datenstrukturen wird der Algorithmus von Kruskal implementiert? Zu welcher Laufzeit führt dieses Vorgehen? #52 Wie ist eine boolesche Funktion definiert? Gib Beispiele für boolesche Funktionen an. Wie fasst man Funktionen mit m Outputs häufig auch auf? #52 Gib eine Liste von Operationen an, die eine Datenstruktur für boolesche Funktionen unterstützen sollte. #52/53 Erkläre jeweils, was man unter den folgenden Operationen auf einer Datenstruktur für boolesche Funktionen versteht: 1) "Auswertung", 2) "Gleichheitstest", 3) "Synthese". #52 Erkläre jeweils, was man unter den folgenden Operationen auf einer Datenstruktur für boolesche Funktionen versteht: 4) "Erfüllbarkeitstest", 5) "Ersetzung durch Funktionen" bzw. "Ersetzung durch Konstanten". 7) Minimierung. #52 Gegeben sei eine boolesche Funktion f auf Variablen x1 bis xn. a) Gib an, wie die Funktion ("Existenzquantor x1") f definiert ist. b) Gib an, wie die Funktion ("Allquantor x1") f definiert ist. #53 Was versteht man unter Quantifizierung bei booleschen Funktionen und wie ist sie motiviert? #53 Erkläre die "Syntax" eines OBDDs (also die eigentliche Definition)! #53 Erkläre die "Semantik" eines OBDDs (also: wozu wird es verwendet, welche Funktion f stellt es dar?) #53 Gib ein Pi-OBDD an für die Funktion x1 ODER (x2 UND x3), wenn die Variablenordnung Pi=(x1,x3,x4,x2) ist. #54 Wenn OBDDs mit verschiedenen Variablenordnungen die gleiche Funktion f darstellen, sind sie dann immer gleich groß? #54 Wie ist die Größe eines OBDDs definiert? #54 Wie realisiert man die folgenden Operationen auf OBDDs:? Auswertung, Ersetzung durch Konstanten, Erfüllbarkeitstest. #54 Beschreibe, wie Verschmelzungsregel und Eliminationsregel bei OBDDs funktionieren. Male dazu die entsprechenden Bilder hin und gib in Worten an, welches die Voraussetzungen sind und was sich am OBDD ändert. #55 Wie minimiert man algorithmisch OBDDs? Es gibt einen Satz, wann ein OBDD zur Variablenordnung Pi minimal ist. Gib die Aussage des Satzes an. #55/57 Synthese bei OBDDs: Wie wird diese algorithmisch bei OBDDs durchgeführt? Was versteht man unter der Kreuzproduktkonstruktion? #57 Wie erreicht man, dass bei der Synthese im Ergebnis-OBDD keine nicht-erreichbaren Knoten erzeugt werden? #58 Wie sorgt man bei der Syntheseoperation bei OBDDs dafür, dass im Ergebnis-OBDD weder Verschmelzungs- noch Eliminationsregel anwendbar sind? #59/60 Erkläre, wofür unique-table und computed-table bei der OBDD-Synthese benutzt werden und skizziere ihre Funktionsweise. #60 und Extraaufschrieb zur Vorlesung Skizziere in Pseudocode, wie die Syntheseoperation unter Verwendung von unique-table und computed-table abläuft. #Extraaufschrieb zur Vorlesung Wie führt man Gleichheitstest und Quantifizierung bei OBDDs durch? #(steht schon bei der Definition der Operationen auf S. 53) Was versteht man unter einer dynamischen Datei? Was meint man, wenn man von einem "Schlüssel" spricht? #61 Welche Operationen soll die Datenstruktur "Dictionary" unterstützen? #61 Was sollen die Operationen SPLIT/CONCATENATE bei Dictionaries bewirken? #61 Hashfunktionen: Was ist eine Hashfunktion, was versteht man unter dem Universum, was sollte für eine Hashfunktion gelten? #62 Wieso müssen wir auch bei großen Hashtabellen mit Kollisionen leben? #62 Erkläre das Geburtstagsparadoxon und mache eine Analyse, wie groß die Wahrscheinlichkeit ist, bei n Daten aus einem Universum mit M Elementen keine Kollision zu haben. #62 Erkläre, wie die Kollisionsbehandlung bei Hashfunktionen prinzipiell funktioniert. Gib Pseudocode an für Einfügen und Suchen. #63 Hashfunktionen: Wie sehen die test_i aus bei: Linearem Sondieren, Quadratischem Sondieren, Multiplikativem Sondieren. Beweise, dass die Folge der getesteten Zellen bei multiplikativem Sondieren alle Positionen aus {0..M-1} durchläuft. #64 Wie funktioniert Doppeltes Hashing? #65 Was versteht man unter Primärkollisionen, was unter Sekundärkollisionen? #65 Erkläre am Beispiel, warum Lineares Sondieren zu großen Klumpen führt. #65 Analyse ideales Hashing: Wieviele Zellen werden beim idealen Hashing durchschnittlich besucht? Gib den Wert an. #65 Analyse ideales Hashing: Zeige, dass die durchschnittliche Anzahl besuchter Zellen f(n,M) = M+1/(M+1-n) ist. Stelle dazu zunächst die Rekursionsgleichung begründet auf und zeige, dass obige Formel Lösung der Rekursionsgleichung ist. #66 Was versteht man unter der Auslastung einer Tabelle und wie ergibt sich die erwartete Anzahl besuchter Speicherzellen beim geschlossenen Hashing daraus? #siehe Folie 3 der Vorlesung vom 08.06.04 Analysiere die erfolgreiche Suche beim geschlossenen Hashing. Gehe dabei davon aus, dass jedes Element mit gleicher Wahrscheinlichkeit gesucht wird. #66 Bei der Analyse des geschlossenen Hashings kommt die Funktion H(m) vor ("Harmonische Zahl"). Wie ist diese definiert. Durch welche Funktion kann man H(m) abschätzen und mit welcher Methode erhält man diese Abschätzung? #66 und Anhang, S. 153 Welche Hashklasse kommt dem idealen Hashing relativ nah? #66 Erkläre offenes Hashing sowie wie dort die Operationen implementiert werden. Wieviele Vergleiche finden bei erfolglosem/erfolgreicher Suche statt. Führe die Argumente für die Formeln jeweils vor. #67 Welches Variante, die ein Zwischending zwischen geschlossenem und offenem Hashing ist, gibt es? #67 Gib eine korrekte Definition von binären Suchbäumen an. #68 Beschreibe Such- und Einfügeprozedur in binären Suchbäumen. Gib Pseudocode dafür an. #68 und Folien vom 08.06.04 Beschreibe Löschen im binären Suchbaum und beschreibe die drei dabei auftretenden Fälle. #72 In der Vorlesung wollten wir die durchschnittliche Suchzeit in binären Suchbäumen analysieren. Welche Annahmen machen wir dort? Wie ist T(Pi) definiert, wie ist T(n) definiert? #69 Stelle die Rekursionsgleichung für T(n) auf und begründe sie. #70 Aus der Rekursionsgleichung für T(n) haben wir eine Rekursionsgleichung für s(n) gewonnen. Wie war s(n) definiert und wie sieht die Rekursionsgleichung von s(n) aus? #70 Versuche im Ansatz, die Rekursionsgleichung für s(n) zu lösen. Genauer: Zeige, wie man durch iteriertes Einsetzen eine Formel für s(n) bekommt, die "eine Summe von prod_..-Werten" ist. #70/71 (Nur für "Hartgesottene":) Führe die Analyse von s(n) bzw. T(n) bis zum Ende durch. #71 Das Endergebnis der Analyse: Wie groß ist T(n) größenordnungsmäßig, bzw. wie groß ist T(n)/n größenordnungsmäßig? (O-Notation) #71 Was kann man über die durchschnittliche Suchzeit in zufällig konstruierten Bäumen aussagen? Worüber wird dabei der Durchschnitt gebildet? #71 2-3-Bäume: Definition! (Alle 5 Punkte der Definition nennen!) #73 Beweise, dass bei einem 2-3-Baum mit n Schlüsseln und Tiefe d gilt: d=Theta(log n) #73 Erkläre, wie man in einem 2-3-Baum sucht. #74 Wie fügt man in einen 2-3-Baum ein? Erkläre den Algorithmus anhand von schematischen Bildern und erkläre die verschiedenen Fälle, die auftreten können. #75 Wie ist die Rechenzeit einer INSERT-Operation bei 2-3-Bäumen und wieso ist sie so? #75 Wie löscht man in einem 2-3-Baum? Erkläre die drei möglichen Fälle, die dabei auftreten können und wie sie behandelt werden. #76 Wie ist die Laufzeit für das Löschen in einem 2-3-Baum und warum ist sie so? #76 Füge in einen 2-3-Baum nach und nach die Schlüssel A,L,G,O,R,I,T,H ein und male die dabei entstehenden Bäume auf. #77 Betrachte das oberste Bild im Skript auf S. 78 im Skript. Lösche die 12 aus dem Baum und zeichne die in den Zwischenschritten entstehenden Bäume. #78 Was versteht man unter den Operationen CONCATENATE/SPLIT? In welcher Laufzeit kann man diese mit 2-3-Bäumen implementieren? #79 Definiere einen "B-Baum der Ordnung m". 2-3-Bäume sind B-Bäume welcher Ordnung? #82 Wie ist die Tiefe von B-Bäumen der Ordnung m beschränkt? (Größenordnungsmäßig). #82 Beschreibe, wie man in B-Bäumen der Ordnung m einfügt und wie man in ihnen löscht. Gib jeweils die auftretenden Fälle an und wie die Reparaturen durchgeführt werden. #83 Wie ist der Balancegrad eines Knotens definiert? #84 Wie ist ein AVL-Baum definiert? #84 Was kann man über die Tiefe von AVL-Bäumen mit n Schlüsseln aussagen? #84 Beweise, dass die Tiefe von AVL-Bäumen mit n Schlüsseln O(log n) ist: Welche Bedeutung hat der Parameter A(d) im Beweis? Stelle begründet eine Rekursionsgleichung für A(d) auf und schätze A(d) geeignet ab. Wie kommt man von einer Schranke für A(d) auf die Tiefenschranke O(log n)? #84/85 Wie sucht man in einem AVL-Baum? Wie fügt man in einem AVL-Baum ein? Erkläre, wie die Balancegrade aktualisiert werden, wenn man sich an einem Knoten v befindet und man im rechten Teilbaum von v eingefügt hat. #85 Wann muss man beim Einfügen in einen AVL-Baum eine L-Rotation anwenden? Beschreibe diese an einem schematischen Bild. Wann muss man beim Einfügen in einen AVL-Baum eine RL-Rotation anwenden? Beschreibe diese an einem schematischen Bild. #86 Beschreibe an einem der Fälle, wie man den Balancegrad der Knoten nach einer RL-Rotation ausrechnen kann. #86 Einfügen in AVL-Baum: Angenommen, es findet eine Rotation statt. Muss dann weiter nach oben hin aktualisiert werden? #87 Füge in einen anfangs leeren AVL-Baum nacheinander die Schlüssel 4,5,7,2,1,3,6 ein. #87/88 Beschreibe, wie in einem AVL-Baum gelöscht wird. Welche Rotationen können beim Löschen zum Einsatz kommen? Beschreibe diese schematisch. Muss nach einer Rotation nach oben weiter aktualisiert werden? #90 Welche Laufzeit haben SEARCH/INSERT/DELETE in einem AVL-Baum mit n Schlüsseln? Warum ist die Laufzeit so? #90 Wie ist eine Skipliste prinzipiell aufgebaut? Wie groß ist die erwartete Höhe eines Schlüssels in einer Skipliste? #91 Wie sucht man in einer Skipliste? Einfügen: Wie wählt man die Höhe eines einzufügenden Schlüssels? Wie fügt man den Schlüssel ein? Wann muss man die Höhe des Anfangs- bzw. Endblocks aktualisieren? #91/92 Berechne die erwartete Höhe eines Schlüssels. #91 Wie löscht man in einer Skipliste? Wie ergibt sich die Laufzeit? #92 Wie führt man CONCATENATE bzw. SPLIT bei Skiplisten durch? #92 Warum macht man bei Skiplisten keine worst-case-Analyse? #Vorlesung Skiplisten: Wofür stehen H(n) und Z(n)? Gib eine Abschätzung an für E[H(n)] bzw. E[Z(n)]. Beweise diese, genauer: a) Gib (mit Beweis) eine Abschätzung an für die Wahrscheinlichkeit, dass H(n) >= h ist. b) Erkläre, warum man den Erwartungswert von H(n) ausrechnen kann als summe Prob(H(n)>=h). c) Erkläre, wie man von dieser Formel zu der von dir gegebenen Abschätzung kommt. d) Wie sieht das Argument bei E[Z(n)] aus? #93 Welche erwartete Rechenzeit haben die Operationen SEARCH/INSERT/DELETE bei Skiplisten? #93 Bei der Analyse der Skiplistenrechenzeit für INSERT haben wir eine Rückwärtsanalyse gemacht: Was heißt das? Wir haben den Weg dann in zwei Teile zerlegt: Wie genau? Beweise, dass wir "oberhalb der Trennlinie" höchstens zwei "Klötzchen" erwarten. Beweise, dass der Erwartungswert für die Anzahl Schritte in der ersten Phase höchstens O(log n) ist. #94 Das Problem "Sortieren": Was ist Eingabe, was soll Ausgabe sein? #96 Was versteht man unter internem/externem Sortieren? Wann sagt man, dass ein Sortierverfahren "in situ" arbeitet? #96 Was versteht man unter "Adaptivität" bei einem Sortierverfahren? Wann heißt ein Sortierverfahren "stabil"? #96 Erkläre das Sortierverfahren "Insertion Sort". Wieviele wesentliche Vergleiche werden beim Einsortieren des i+1-ten Elements gemacht? #97 Was kann man über die worst-case-Anzahl an wesentlichen Vergleichen bei Insertion Sort aussagen? Wie beweist man das? #97 Wieviele Schiebeoperationen macht Insertion Sort im worst case und im average case? Beweise dies! #98 Wie mischt man zwei bereits aufsteigende Sequenzen a1...ak und b1...bm? ("Merge") (Erklärung bzw. Pseudocode) Wieviele wesentliche Vergleiche macht man dabei höchstens und warum ist das so? #99 und Folien Erkläre Mergesort, dabei darfst Du die Prozedur Merge als gegeben voraussetzen. (Pseudocode!) #99 Stelle die Rekursionsgleichung für die Anzahl wesentlicher Vergleiche von Mergesort auf. Was ist die Lösung dieser Gleichung? Wie löst man so eine Gleichung? #99 und S. 8 für die Lösung der Gleichung Wie ist die worst-case-Laufzeit von Mergesort? #99 Erkläre, wie eine adaptive Version von Mergesort aussehen könnte. #100 Erkläre das prinzipielle Vorgehen von Quicksort. #100 Was soll die Prozedur "partition" bei Quicksort sicherstellen? Welche beiden Invarianten halten wir bei der Implementierung der "Partition"-Prozedur von Quicksort aufrecht? #100 Welche beiden Regeln gibt es beim Versetzen der Zeiger bei der Partitionsprozedur von Quicksort? Was, wenn beide Regeln nicht anwendbar sind? #101 Führe die Partition-Prozedur von Quicksort an einem Beispiel vor. #101 Erkläre Zerlegungsstrategien 1 bis 4 bei Quicksort #101ff Was ist der worst-case für Zerlegungsstrategie 1 bei Quicksort? Wie ist die Laufzeit dann? #102 Wie ist die worst-case-Laufzeit von Quicksort? #102 Wie ist die average-case-Laufzeit von Quicksort? Beweise deine Aussage! Genauer: Stelle mit Begründung die Rekursionsgleichung auf und skizziere, wie wie diese hier "gelöst" haben. #102 Wann tritt der best case bei Quicksort auf und welche Laufzeit hat Quicksort dann? #103 Gib für die Zerlegungsstragie 2 den worst-case an und für den average-case nenne die Laufzeit. #103 Was versteht man unter Clever Quicksort? #104 Wenn wir für die Zerlegungsstrategien 1-4 average-case-Aussagen gemacht haben: Worüber wird dabei jeweils der Durchschnitt gebildet? #101-104 Wie ist ein Heap bzw. Minheap definiert? #104 Wie werden Arrays bei Heapsort gedanklich als Bäume dargestellt? Wenn i die Nummer eines Knotens ist, was ist die Nummer seines linken/rechten Kindes, was die Nummer des Vaters (wenn denn einer existiert)? #104 Was geschieht in der Heap Creation Phase, was in der Heap Selection Phase? #105 Erkläre unter Verwendung der Prozedur in Pseudocode, wie Heap Creation Phase und Selection Phase funktionieren. Gib Erläuterungen dazu. #105 Was muss beim Aufruf von reheap(i,n) an Vorbedingungen gelten, damit reheap an Knoten i die Heapeigenschaft herstellt? #105 Erkläre, wie man reheap implementiert. Und zwar: in der klassischen Variante sowie in den beiden bottom-up-Varianten. #106/107 Beweise die Korrektheit von reheap\\ #107 Wie groß ist die Summe der Tiefen der Bäume, für die in der Heap Creation Phase die Prozedur reheap aufgerufen wird? Beweise Deine Aussage. #107 Wie groß ist die Summe der Tiefen der Bäume, für die in der Heap Selection Phase die Prozedur reheap aufgerufen wird? Beweise Deine Aussage. #108 Wie kann man die worst-case-zahl wesentlicher Vergleiche bei allen Heapsort-Varianten abschätzen? Wieso? #108 Wie sieht die worst-case-Zahl wesentlicher Vergleiche bei der Strategie "bottom-up mit binärer Suche" aus? Gib an, wie man auf diese Zahl kommt. #108 Wie sieht die worst-case-Zahl wesentlicher Vergleiche bei der Strategie "bottom-up mit linearer Suche" aus? (Ohne Beweis!) #108 Wann heißt ein Sortierverfahren "allgemein"? #109 Definiere, was man im Zusammenhang mit Sortieralgorithmen unter einem Entscheidungsbaum versteht. #109 Sei T ein binärer Baum mit N Blättern. Er hat Tiefe mindestens? Er hat eine durchschnittliche Blattiefe von? Beweise Deine Aussagen. #109 Was sagt die untere Schranke für allgemeine Sortierverfahren aus? Beweise sie. #110 Gib für einige der dir bekannten Sortierverfahren eine Liste an mit worst-case, average-case-Anzahlen wesentlicher Vergleiche. #111 Kennst du ein Sortierverfahren, das nicht allgemein ist? #111/112 Erkläre bucketsort. Wie ist die Laufzeit von bucketsort? #112 Erkläre unter Benutzung von bucketsort den verallgemeinerten bucketsort. Beweise seine Korrektheit. Welche Laufzeit hat er? #112 Was versteht man unter dem Auswahlproblem? #113 Beschreibe, wie die Prozedur quickselect funktioniert. Erkläre insbesondere, was die Prozedur macht, wenn "r=k", "rk" ist. #113 Welche Laufzeit hat quickselect im worst case? #113 Wie ist die durchschnittliche Anzahl Vergleiche bei quickselect? Worüber wird der Durchschnitt gebildet? #113 Beweise, dass quickselect im average case höchstens V(n) <= 4n (wesentliche) Vergleiche macht. Genauer: Schreibe hin, mit welcher Wahrscheinlichkeit jeweils Restprobleme welcher Größe übrig bleiben. Stelle dann die Rekursionsgleichung für V(n) begründet auf. Für welches k ist V(n) am größten? (Wenn Du magst, kannst Du auch versuchen, dann induktiv zu beweisen, dass V(n) <= 4n ist.) #114 Wir haben ein Parallelrechnermodell beim Sortieren betrachtet. In welchem Sinne kann man die Vergleiche parallelisieren? #114 Wieviele Vergleiche können auf unserem Parallelrechnermodell (mit unendlich vielen gedachten Prozessoren) maximal gleichzeitig stattfinden? Welche untere Schranke für die Laufzeit für das Sortieren auf Parallelrechnern ergibt sich daraus? #114 Gib in Pseudocode an, wie Batchermerge "BM" funktioniert. (Was ist überhaupt Eingabe der Prozedur BM?) Welches sind die rekursiven Aufrufe, welche Vergleiche finden außerhalb der rekursiven Aufrufe statt? #114/115 Beweise, dass Batchermerge korrekt ist. #115/116 Gib (unter Benutzung von Batchermerge) Pseudocode für Batchersort an. #116 Wie ist die parallele Rechenzeit und die Anzahl gemachter Vergleiche (größenordnungsmäßig) bei a) Batchermerge und b) Batchersort? #116 Stelle die Rekursionsgleichungen auf für die parallele Rechenzeit und die Anzahl gemachter Vergleiche für a) Batchermerge und b) Batchersort. #116 Was versteht man unter einem Vergleichsnetzwerk? Gib dabei zunächst die Definition und dann die "Semantik" des Netzwerks an. #Folie vom 08.07. Wie kann man ein Vergleichsnetzwerk grafisch darstellen? Wie kann man Vergleiche eines Vergleichsnetzwerks "parallelisieren"? #116 Wann heißt ein Vergleichsnetzwerk "Sortiernetzwerk"? Wie kann man Batchersort als Sortiernetzwerk auffassen? #116 bzw. Folie 3 vom 13.07.04 Wie ergibt sich aus einem Sortiernetzwerk die parallele Rechenzeit? #Folie 4 vom 13.07.04 Wie würde man auf Hardwareebene sortieren? #Folie 6/7 vom 13.07.04 Welche Entwurfsmethoden für effiziente Algorithmen fallen Dir ein? #118 Greedyalgorithmen: welche drei Möglichkeiten gibt es im allgemeinen für die von ihnen berechneten Lösungen? #118 Wie ist das Münzwechselproblem formal definiert? #118/119 Wie arbeitet der Greedyalgorithmus für das Münzwechselproblem? Berechnet er stets optimale Lösungen? Falls ja: Beweis, falls nein: Gegenbeispiel! #119 Wie ist das Traveling-Salesman-Problem definiert? Gib jeweils eine anschauliche und eine formale Definition. #119 Wie würde ein Greedyalgorithmus für das Traveling-Salesman-Problem aussehen? #119 Berechnet der Greedyalgorithmus für das Traveling-Salesman-Problem immer eine optimale Lösung? Falls ja: Beweis, falls nein: Gegenbeispiel. #119 Warum kann man bei dem Traveling-Salesman-Problem nicht einfach alle möglichen Touren ausprobieren? #119 Wie ist das Rucksackproblem definiert? Gib jeweils eine anschauliche und eine formale Definition. #120 Wie würde ein Greedyalgorithmus für das Rucksackproblem ablaufen? #120 Beim Greedyalgorithmus für das Rucksackproblem wurden "Effektivitäten" (bzw. auch "Effizienzen" genannt) definiert. Was war das? #120 Berechnet der Greedyalgorithmus für das Rucksackproblem stets optimale Lösungen? Falls ja: Beweis, falls nein: Gegenbeispiel. #120 Wie ist das *verallgemeinerte* Rucksackproblem definiert? #120 Was versteht man unter der Relaxation des Rucksackproblems? #120 Beweise, dass der Greedyalgorithmus für das *verallgemeinerte* Rucksackproblem optimale Lösungen berechnet. (Wie läuft der Greedyalgorithmus für dieses Problem überhaupt ab?) #121 Wie ist das Bin Packing Problem definiert? #121 Fällt Dir eine informatikspezifische Anwendung für das Bin Packing Problem ein? #121 Was versteht man im Zusammenhang mit dem Bin Packing Problem unter Onlinealgorithmen bzw. unter Offlinealgorithmen? #121 Wie läuft der First-Fit-Algorithmus ab? Wie der Best-Fit-Algorithmus. Verwende eine "Pseudocode"-Notation. #121 bzw. Folien 28/29 vom 13.07.2004 Was kann man über die von First Fit bzw. Best Fit berechneten Lösungen aussagen (hinsichtlich ihrer Güte)? #121/122 Beweise, dass First Fit bzw. Best Fit nur "Bepackungen" berechnen, die höchstens doppelt so viele Kisten verwenden wie die optimale Bepackung. #122 Gib ein Beispiel an, wo First Fit/Best Fit (5/3) mal soviele Kisten verwenden wie im Optimum. #122 Wie funktionieren FFD bzw. BFD? #122 Welche der Algorithmen First Fit/Best Fit/BFD/FFD sind Onlinealgorithmen, welche sind Offlinealgorithmen? #122 Welche Aussagen kennst Du betreffend die Güte der von FFD bzw. BFD berechneten Lösungen? #123 Fällt Dir ein Beispiel ein für einen Greedyalgorithmus, der *immer* optimale Lösungen berechnet? #123 Erkläre das Grundprinzip dynamischer Programmierung am Beispiel der Fibonaccizahlen! #123 In welchen Situationen ist typischerweise die Methode der dynamischen Programmierung anwendbar? #123/124 Das Rucksackproblem: wie löst man es mit Hilfe der Dynamischen Programmierung? Genauer: Erkläre, wofür die Zahl F(k,g) steht. Welcher Wert F(*,*) interessiert uns eigentlich? Wie ergeben sich die Werte F(0,g) und F(k,0) ? Gib die Bellmansche Optimalitätsgleichung für F(k,g) an und begründe sie! #124 Wie lange dauert es, das Rucksackproblem mit Hilfe der Dynamischen Programmierung zu lösen? Wie lange dauert es, einen der Einträge in der Tabelle aus den anderen schon bekannten Einträgen zu berechnen? Bitte jeweils mit Begründung! #124 Begründe, warum die Laufzeit für die Dynamische Programmierung beim Rucksackproblem O(n*G) ist. #125 Angenommen, man möchte eine optimale Rucksackbepackung mit Hilfe der Dynamischen Programmierung berechnen und nicht nur den Nutzen dieser. Wie kann man das machen? #124 unten. Bzw. Folie 19 vom 15.07.2004 Ist die Rechenzeit O(n*G) polynomiell? #125 Was versteht man unter einer pseudopolynomiellen Rechenzeit? Wo ist uns eine solche zum ersten Mal über den Weg gelaufen? #125 Bioinformatik, Alignments: Was ist gegeben? Wie kann man die Scorefunktion auf gleich langen Wörtern fortsetzen? #125 Welche typischen Ereignisse passieren in der Evolution DNA-Sequenzen betreffend? #125 Was versteht man unter der Erweiterung einer Sequenz x? Gib ein Beispiel an für eine Erweiterung einer Sequenz. #125 Was versteht man unter der Lückenstrafe? #125 Was versteht man unter einem Alignment zweier Sequenzen x und y? #125 bzw. Folie 25 vom 15.07.04 Wie bewertet man ein Alignment? Was versteht man unter dem Problem, ein optimales (globales) Alignment zu berechnen? #125 Begründe, warum in einem optimalen Alignment keine zwei Leerzeichen untereinander stehen. Wenn zwei Wörter x und y optimal aligned werden, wie lang ist die Länge des optimalen Alignments maximal? Und warum? #125 Berechnung von optimalen Alignments: Wie löst man das mit der Dynamischen Programmierung? Genauer: Wie ist OPT(i,j) definiert? Wie groß ist OPT(i,0) bzw. OPT(0,j)? Stelle die Bellmansche Optimalitätsgleichung für OPT(i,j) auf und begründe, wofür die drei "Fälle" stehen. #126 Wie lange dauert es, mit Hilfe der dynamischen Programmierung optimale Alignments zu berechnen? Bitte mit Begründung! #126 Das Kürzeste-Wege-Problem "APSP": Wie ist es definiert? Was ist Eingabe, was ist Ausgabe? #126 Wie sehen die kleineren Teilprobleme beim APSP aus? Wie ist d_k(i,j) definiert? Wie ergibt sich d_0(i,j) einfach? #126 Gib die bellmansche Optimalitätsgleichung für das APSP an und begründe sie. Wo geht ein, dass alle Kantenkosten c(i,j) >=0 sind? #127 In welcher Laufzeit kann man das APSP-problem lösen? Wieso ist die Laufzeit so? #127 Was versteht man unter dem SSSP-Problem und mit welchem Algorithmus geht man es an? #127 Der Algorithmus von Dijkstra: Was ist Eingabe, was ist gesucht? #127 Algorithmus von Dijkstra: Wie ist ein A-Weg nach j definiert? #127 Was verwaltet der Algorithmus von Dijkstra? #127 Welche drei Invarianten erhält der Algorithmus von Dijkstra aufrecht? Wie wählt man A und die d^*, damit die Invarianten zu Beginn trivialerweise erfüllt sind? #128 Schreibe den Algorithmus von Dijsktra in Pseudocode hin. Zeichne einen kleinen Beispielgraphen auf und wende den Algorithmus von Dijkstra darauf an. #129 Erkläre, wieso die Invarianten I bis III beim Algorithmus von Dijkstra erhalten bleiben. #128 Wo benötigt man beim Korrektheitsbeweis des Algorithmus von Dijkstra, dass die Kantenkosten >=0 sind? #128 Wie kann man beim Algorithmus von Dijkstra nicht nur die Kosten eines billigsten Wegs, sondern einen billigsten Weg selber berechnen? #129 Wie ist die Laufzeit beim Algorithmus von Dijkstra? Es wurden zwei verschiedene Implementierungen vorgeschlagen mit zwei verschiedenen Laufzeiten. Welche ist wann besser? #130 Was versteht man unter einem Branch-and-Bound-Algorithmus? In welcher Situation setzt man einen solchen ein? #130 Welche 5 Module gibt es bei Branch-and-Bound-Algorithmen typischerweise? #131/132 Erkläre, wie Upper-Bound-Modul sowie Lower-Bound-Modul beim Rucksackproblem aussehen. Wie sieht das Branching-Modul aus? #132 Was versteht man unter dem Branch-and-Bound-Baum? #Folien vom 22.7. Das Search-Modul beim Rucksackproblem: Welches Problem sollte man als nächstes zerlegen? Wann stoppt der Algorithmus überhaupt? #133 Schreibe dir das Rucksackproblem-Beispiel aus der Vorlesung oder aus dem Skript auf und löse es mit der Branch-and-Bound-Methode exakt. #133/134 Wenn man "a Teilprobleme der Größe n/b rekursiv löst", Extraarbeit c*n: Wie sieht die Rekursionsgleichung aus. Löse sie für die verschiedenen Fälle a=b, ab. #134/135 Wie berechnet man das Produkt zweier Matrizen mit der Schulmethode? Wieviel arithmetische Operationen sind dabei nötig? (Bitte mit Begründung!) #135 Erkläre, wie man die Schulmethode auch rekursiv umsetzen kann. Welche Laufzeit ergibt sich dabei? #Folien vom 27.07.04 Algorithmus von Strassen: Wie funktioniert er prinzipiell? (Die Formeln auswendig zu wissen ist nicht nötig hier). Stelle die Rekursionsgleichung für die Operationszahl auf und erkläre, wie man sie löst. #136 Wann ist Strassens Algorithmus besser als die Schulmethode? Wie kann man das verbessern? Erkläre den Algorithmus MIX. #137 Ab welchem n schlägt Algorithmus MIX für die Matrixmultiplikation die Schulmethode? #137 Spielbäume: Welche Spiele behandeln wir hierbei? (Zum Beispiel Skat?) #137/138 Spielbäume: Wofür steht ein Knoten? Wann ist ein Knoten Blatt? #138 Wie kann man die Bewertung eines Knotens in einem Spielbaum ausrechnen? Wie funktioniert das an einem MAX-Knoten, wie funktioniert es an einem MIN-Knoten? #138 Spielbäume: Welche Bedingung muss für s^* gelten? #138 Spielbäume: Alpha-beta-pruning: Wann kann man die Auswertung eines Teilbaums beenden? Warum? #138 Führe an einem Beispiel-Spielbaum vor, wie a) die triviale Spielbaumauswertung funktioniert, b) die Auswertung mit alpha-beta-pruning funktioniert. #138/139