Aufgabe 2 (Deutsch) - Prof. Dr. Diedrich Wolter PDF

Preview

Summary

Prof. Dr. Diedrich Wolter...

Description

AI-AuD-B: Übungsblatt 2 (Bonuspunkte: 2) Diedrich Wolter [email protected]

Michael Sioutis [email protected]

Otto-Friedrich-Universität Bamberg — 20. April

Einführung An dieser Aufgabe üben Sie, grundlegende Komplexitätsanalysen durchzuführen, einfache Algorithmen konkret zu definieren und zu analysieren, und Sie erhalten einen tieferen Einblick in die Rekursion. i

Info: Jede Aufgabe hat eine 1 Woche Frist ab dem Zeitpunkt der Bekanntgabe. Ihre Antworten sollten Ihre eigene Anstrengung darstellen. Es ist natürlich in Ordnung, die Übungen zu besprechen und gemeinsam mit anderen Studierenden Lösungen zu finden, aber Sie müssen Ihre Lösungen separat ausarbeiten und einreichen. Es ist eine gute akademische Praxis, Mitarbeiter anzuerkennen. Wenn Sie also mit anderen zusammengearbeitet haben, geben Sie bitte deren Namen an.

1 Asymptotische Komplexität Aufgabe 1 Betrachten Sie die folgende Liste von Funktionen, die die Laufzeit von Algorithmen darstellen: 1. c · n2 , wobei c eine Konstante ist, so dass c > 1 000 ist 2.

n! n

3. 2 · 3n 4. log2 n7 5. 3 · 2n 6. log2 n49 7. 10 · n2 +

1 2

· n3

Ordnen Sie die oben genannten Funktionen entsprechend ihrer asymptotischen Komplexität (O Notation) von der niedrigsten zur höchsten Komplexität! Wenn Sie eine Funktion f vor Funktion g anordnen, dann soll es f ∈ O(g) bedeuten. Geben Sie auch Funktionen an, wenn es Funktionen f und g gibt, die asymptotisch äquivalent sind, d.h., wenn sowohl f ∈ O(g) als auch g ∈ O(f ) gilt! (20% der Punkte)

1

Aufgabe 2 Beweisen oder widerlegen Sie folgende Aussagen: • 5 · n2 + n · log2 nn ∈ O(n2 ) • (n + a)b ∈ Θ(nb ) für alle natürlichen Zahlen a, b > 0 (20% der Punkte)

2 Suche in Zeichenketten Aufgabe 3 Schreiben Sie einen iterativen Algorithmus für das Finden einer Übereinstimmung von Teilzeichenfolgen in zwei Zeichenfolgen (Zeichenarrays) A und B ! Gegeben zwei Zeichenfolgen, A mit der Länge n und B mit der Länge m, soll der Algorithmus −1 zurückgeben, wenn B keine Teilzeichenfolge von A ist, andernfalls die Startposition des ersten Zeichens von B in A. Wenn beispielsweise A = “Rechtsschutzversicherungsgesellschaften” und B = “versicherung”, soll der Algorithmus die Zahl 13 zurückgeben. Sie dürfen die Methoden length() und charAt() verwenden, um auf Zeichen in einer Zeichenfolge zuzugreifen. Gehen Sie wie folgt vor: a) Schreiben Sie die Idee Ihres Algorithmus auf. b) Identifizieren und notieren Sie alle relevanten speziellen Eingabefälle für Ihren Algorithmus (falls vorhanden). c) Entwickeln und notieren Sie den Algorithmus im Pseudocode (beachten Sie etwaige Sonderfälle). d) Analysieren Sie die asymptotische Komplexität Ihres Algorithmus (O-Notation) und zählen Sie die Anzahl der Elementaroperationen, die für den schlechtesten und besten Fall erforderlich sind. (30% der Punkte)

3 Taytonym-Identifizierung Aufgabe 4 Schreiben Sie einen rekursiven Algorithmus, um festzustellen, ob eine Zeichenfolge A aus genau zwei identischen Teilen besteht, z. B. “soso”. Gegeben eine Zeichenfolge A mit der Länge n soll der Algorithmus False zurückgeben, wenn A kein Taytonym ist, und ansonsten True. Wenn beispielsweise A = “bisonbison” ist, sollte der Algorithmus True zurückgeben, und wenn A = “acatcat”, False. Sie dürfen die Methoden length() und charAt() verwenden, um auf Zeichen in einer Zeichenfolge zuzugreifen. Gehen Sie wie folgt vor: a) Schreiben Sie die Idee Ihres Algorithmus auf. b) Identifizieren und notieren Sie alle relevanten speziellen Eingabefälle für Ihren Algorithmus (falls vorhanden). c) Entwickeln und notieren Sie den Algorithmus im Pseudocode (beachten Sie sich um etwaige Sonderfälle). d) Analysieren Sie die asymptotische Komplexität Ihres Algorithmus (O-Notation) und zählen Sie die Anzahl der Elementaroperationen, die für den schlechtesten und besten Fall erforderlich sind. (30% der Punkte)

2...