1 Algorithmen und Datenstrukturen Sommersemester 2014 Nachname: Vorname: Matrikelnummer: Note: Prof. Dr. Letschert L¨osungen bitte auf eigene Bl¨atter eintragen! Geben Sie auf jedem Blatt Ihren Namen und Ihre Matrikelnummer an. Aufgabe 1 (3*5 = 15 Punkte) 1. Beschreiben Sie kurz und in eigenen Worten das Sortier-Verfahren Selection–Sort. Geben Sie dazu die Schritte an, die bei der Sortierung eines Arrays mit den Zahlen 5,2,4,3,1 ausgef¨uhrt werden. 2. Beschreiben Sie kurz und in eigenen Worten das Sortier-Verfahren Insertion–Sort. Geben Sie dazu die Schritte an, die bei der Sortierung eines Arrays mit den Zahlen 5,2,4,3,1 ausgef¨uhrt werden. 3. Definieren Sie in Java eine statische Methode, die ein beliebig großes Feld von int-Werten aufsteigend sortiert und dabei den Algorithmus Selection–Sort verwendet. Aufgabe 2 (5*5 = 25 Punkte) Die Menge L der Listen von ganzen Zahlen kann induktiv definiert werden: • Basis: Die leere Liste ist ein Element von L. • Induktion: Ist l eine Liste von ganzen Zahlen, also ein Element von L, dann ist auch i · l (l mit vorgesetzter ganzer Zahl i) in L. Aufgabe: 1. Implementieren Sie in Java (statische Methode mit Argument vom Typ List<Integer>) einen Algorithmus, der die Summe der Zahlen einer so definierten Liste berechnet und der rekursiv u¨ ber diese (!) Struktur von L definiert ist. 2. Statt als Objekte vom Typ List<Integer> k¨onnen die Listen auch mit folgendem Typ selbst definiert werden: interface L {} class Empty implements L {} class Node implements L { private int first; private L rest; public Node(int first, L rest) { this.first = first; this.rest = rest; } } Erweitern Sie diese Definitionen derart, dass die Summe einer Liste mit Hilfe einer polymorphen Methode sum berechnet wird. 3. Handelt es sich bei der Berechnung der Summe der Listen-Elemente um einen Reduziere-und-Herrsche– Algorithmus: in beiden Varianten (Teilaufgabe 1 und 2), in einer der beiden Varianten, oder in keiner? 2 4. Erweitern Sie das Interface und seine Implementierungen von Teilaufgabe 2 um eine Methode, mit der der Mittelwert der Listenelemente berechnet werden kann. 5. Handelt es sich bei Ihrer Berechnung des Mittelwerts um einen Reduziere-und-Herrsche–Algorithmus? Aufgabe 3 (4*5 = 20 Punkte) 1. Was genau bedeutet die Aussage “Algorithmus A hat eine Laufzeit von T (n) = 5 ∗ n2 + 7n + 3”? 2. Was genau bedeutet die Aussage “Algorithmus A hat die Laufzeitkomplexit¨at O(n2 )”? 3. Warum ist die Aussage “Algorithmus A hat die Laufzeitkomplexit¨at O(n2 + 7n + 3)” unsinnig? 4. Warum ist die Aussage “Algorithmus A ist NP-vollst¨andig” unsinnig? Aufgabe 4 (6*5 = 30 Punkte) 1. Handelt es sich bei dem Konzept “Graph” um eine Datenstruktur oder um einen Datentyp? Begr¨unden Sie Ihre Antwort kurz. (Ein bis zwei S¨atze reichen.) 2. Wenn das n-Dame–Problem mit einem Algorithmus gel¨ost wird, der auf dem Prinzip der ersch¨opfenden Suche beruht, wie viele kombinatorische Objekte m¨ussen dann bei einem Schachbrett mit 4 × 4 Feldern untersucht werden? Erl¨autern Sie den Wert kurz. 3. Welche Problemstellungen eignen sich f¨ur Algorithmen nach dem Backtracking–Verfahren. Ist das n-DameProblem ein solches Problem? 4. Das n–Dame–Problem ist NP-vollst¨andig. Was genau bedeutet das: welche Kriterien m¨ussen NP-vollst¨andige Probleme erf¨ullen? 5. Welche Datentypen (Interfaces) der Java-API haben eine implementierende Klasse, die die Datenstruktur Baum verwendet? 6. Welche Datentypen / Problemstellungen k¨onnen mit der Datenstruktur Baum gut gel¨ost werden und welche Alternative zu B¨aumen wird ebenfalls sehr oft f¨ur diese Problemstellung eingesetzt? Aufgabe 5 (5 + 5 = 10 Punkte) Eine Priorit¨atswarteschlange ist eine Warteschlange, in die Objekte eingef¨ugt und nach ihrer “Priorit¨at” entnommen werden. Sie hat zwei Operationen • add : Ein Element einf¨ugen • remove: Das Element mit der h¨ochsten Priorit¨at herausholen. Priorit¨aten sind eine Eigenschaft der in der Schlange gespeicherten Elemente. Die Eigenschaft eine Priorit¨at zu haben, kann auf vielerlei Arten von den Elementen realisiert und von der Priorit¨atswarteschlange gefordert werden. Priorit¨at kann beispielsweise als Vergleichbarkeit interpretiert werden, und Vergleichbarkeit kann dann zur Laufzeit gepr¨uft werden: public interface PriorityQueue<E> { /** * Fuegt ein Element in die Queue ein. * @param e das einzufuegende Element * @throws ClassCastException falls e nicht mit den anderen Elementen der Queue verglichen werden kann. * * @throws NullPointerException falls e == null */ 3 void add(E e); /** * Entnimmt ein Element aus der Queue. * @return das kleinste Element entsprechend der Ordnung der Elemente von E. * @throws NoSuchElementException falls die Queue leer ist. */ E remove() throws NoSuchElementException; } Eine triviale Implementierung mit einer Priorit¨at die der nat¨urlichen Ordnung der Elemente entspricht, kann mit einer Cast-Operation und einem Methodenaufruf realisiert werden: import import import import import java.util.Collections; java.util.Comparator; java.util.LinkedList; java.util.List; java.util.NoSuchElementException; public class ListPriorityQueue<E> implements PriorityQueue<E> { private List<E> store = new LinkedList<>(); @Override public void add(E e) throws ClassCastException, NullPointerException { store.add(e); Collections.sort(store, new Comparator<E>() { @Override public int compare(E o1, E o2) { // HIER ERGAENZEN ! return ( ( ...?????... )o1 ) . ?????(o2); } }); } @Override public E remove() throws NoSuchElementException { E e = store.remove(0); return e; } } 1. Welcher Cast und welcher Methodenaufruf sind hier notwendig / m¨oglich um das gew¨unschte Verhalten zu erreichen? 2. Eine Nutzung mit Objekten einer Klasse wie class Blub{} wird dann nat¨urlich eine Exception werfen. Besser w¨are es, wenn Klassen wie Blub gar nicht erst als generischer Parameter verwendet werden k¨onnen und darum add nie die ClassCastException werfen wird. Modifizieren Sie das Interface PriorityQueue und die Implementierung ListPriorityQueue entsprechend.