Algorithmen und Datenstrukturen 1 - SS 2024
48 Questions
1 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Was passiert bei einer linearen Suche in einem nicht sortierten Array?

  • Es wird nur die erste Zelle inspiziert.
  • Die Suche erfolgt rekursiv.
  • Bis zu n Zellen werden inspiziert. (correct)
  • Es wird kein Element gefunden.

Wann ist die Binärsuche anwendbar?

  • Wenn das Array absteigend sortiert ist.
  • Wenn das Array zufällig sortiert ist.
  • Wenn das Array aufsteigend sortiert ist. (correct)
  • Wenn das Array unsortiert ist.

Welche Bedingung muss erfüllt sein, damit die Binärsuche abbricht?

  • x wurde in der rechten Hälfte nicht gefunden.
  • A[mitte] ist kleiner als x.
  • oben < unten. (correct)
  • x wurde in der linken Hälfte nicht gefunden.

Was wird in der rekursiven Ausführung von Binärsuche(unten, oben) gemacht, wenn A[mitte] != x?

<p>Es wird die linke oder rechte Hälfte des Arrays durchsucht. (C)</p> Signup and view all the answers

Was wird bei einem Induktionsanfang d = 0 in der Binärsuche dargestellt?

<p>oben ist gleich unten. (B)</p> Signup and view all the answers

Wie wird das mittlere Element im Array in der Binärsuche berechnet?

<p>mittlere Element = (unten + oben) / 2. (B)</p> Signup and view all the answers

In welcher Situation berechnet sich d = oben − unten + 1 als 0?

<p>Wenn oben kleiner ist als unten. (C)</p> Signup and view all the answers

Welche Rückgabewerte sind in der Binärsuche zu erwarten?

<p>Nur die Position des Wertes oder eine Fehlermeldung. (B)</p> Signup and view all the answers

Wie viele Zellen werden maximal in der Binärsuche in einem Array mit n = 2k − 1 inspiziert?

<p>k (A)</p> Signup and view all the answers

Was ist die rekursive Definition von T(n) für n = 2k − 1?

<p>T(n) = T(n/2) + 1 (D)</p> Signup and view all the answers

Wie viele Zahlen müssen in der Binärsuche maximal inspiziert werden?

<p>k (B)</p> Signup and view all the answers

Welche Aussage über die Laufzeit von Binärsuche im Vergleich zur linearen Suche ist korrekt?

<p>Lineare Suche ist langsamer als Binärsuche. (C)</p> Signup and view all the answers

Was beschreibt der Logarithmus loga(x)?

<p>Die Basis a hoch z ist gleich x. (D)</p> Signup and view all the answers

Was ist 4log2(n) gleich?

<p>n^2 (A)</p> Signup and view all the answers

Wie wird die Laufzeit eines Programms in Bezug auf die Eingabelänge gemessen?

<p>Es hängt von der Problemstellung ab. (C)</p> Signup and view all the answers

Was ist die Induktionsannahme für die Rekursion in Bezug auf T(n)?

<p>T(2k) = k (D)</p> Signup and view all the answers

Was ist die Laufzeit der geschachtelten for-Schleifen?

<p>Kubisch (B)</p> Signup and view all the answers

Welche Rekursionsgleichung beschreibt die Laufzeit einer while-Schleife, die n halbiert?

<p>T(n) ≤ T(n/2) + 1 + c (A)</p> Signup and view all the answers

Welche Laufzeit ergibt sich für die gegebene while-Schleife mit n/2?

<p>Θ(log2 n) (C)</p> Signup and view all the answers

Wie viele Iterationen sind maximal in der while-Schleife mit n/2?

<p>1 + ⌊log2 n⌋ (B)</p> Signup and view all the answers

Was ist die Laufzeit der zweiten while-Schleife, die n nicht verändert?

<p>Θ(log log n) (D)</p> Signup and view all the answers

Was geschieht in der while-Schleife, die n entsprechend seiner Parität verändert?

<p>n wechselt zwischen 3n + 1 und n/2 (B)</p> Signup and view all the answers

Welches Problem tritt bei der Analyse der Laufzeit der letzten while-Schleife auf?

<p>Es ist nicht bekannt, ob sie für jede Eingabe terminiert (D)</p> Signup and view all the answers

Welches Mastertheorem wird bei der Analyse der while-Schleife n/2 angewendet?

<p>Fall 2 (C)</p> Signup and view all the answers

Was ist die worst-case Laufzeit eines Programms?

<p>Die größte Laufzeit auf einer Eingabe der Länge n. (D)</p> Signup and view all the answers

Für welche Art von Rechner wird die Laufzeitmessung empfohlen?

<p>Auf einem abstrakten Rechner mit Registern zur Speicherung. (C)</p> Signup and view all the answers

Warum wird empfohlen, Pseudocode zur Darstellung von Algorithmen zu verwenden?

<p>Weil Pseudocode von Maschinen unabhängig ist. (A)</p> Signup and view all the answers

Was bedeutet es, dass die Laufzeitschätzung bis auf einen konstanten Faktor exakt ist?

<p>Die Schätzung kann nur leicht variieren, aber nicht stark abweichen. (A)</p> Signup and view all the answers

Welches Merkmal hat ein Algorithmus, der in Pseudocode formuliert ist?

<p>Er ist eine präzise definierte Rechenvorschrift. (D)</p> Signup and view all the answers

Welche der folgenden Aussagen über Laufzeitmessung ist korrekt?

<p>Laufzeit kann unabhängig von der verwendeten Programmiersprache berechnet werden. (D)</p> Signup and view all the answers

Was bezeichnet die Eingabelänge eines Algorithmus?

<p>Die Länge der Eingabe in Bezug auf die Schlüsseldaten. (B)</p> Signup and view all the answers

Welcher von diesen Punkten beschreibt am besten die Funktion ZeitP(n)?

<p>Die größte Laufzeit eines Programms für eine spezifische Eingabelänge. (C)</p> Signup and view all the answers

Wie viele Gitterpunkte befinden sich unterhalb der Hauptdiagonale?

<p>n^2 - n Gitterpunkte (B)</p> Signup and view all the answers

Welche der folgenden Formeln beschreibt die geometrische Reihe?

<p>$\sum_{i=0}^{n} a_i = \frac{a^{n+1} - 1}{a - 1},\ a \neq 1$ (D)</p> Signup and view all the answers

Was ist der Induktionsanfang für die vollständige Induktion?

<p>$P_0: \sum_{i=0}^{0} a_i = 1$ (B)</p> Signup and view all the answers

Was zeigt man im Induktionsschritt von n auf n + 1?

<p>$\sum_{i=0}^{n} a_i + a^{n+1} = \frac{a^{n+2} - 1}{a - 1}$ (B)</p> Signup and view all the answers

Was ist die Formel für die Summe der ersten n natürlichen Zahlen?

<p>$\frac{n(n+1)}{2}$ (C)</p> Signup and view all the answers

Welche Aussage über die geometrische Reihe ist korrekt?

<p>Sie ist auch für $a &lt; 1$ gültig. (B)</p> Signup and view all the answers

Was ist das Ergebnis der Formel $\frac{a^{n+1} - 1}{a - 1}$, wenn $a = 2$ für n = 3?

<p>15 (A)</p> Signup and view all the answers

Welcher Ausdruck ist gleich $a^{n+1} - 1$?

<p>$\sum_{i=0}^{n} a^i$ (B)</p> Signup and view all the answers

Was ist die korrekte Reihenfolge des asymptotischen Wachstums für die Funktionen f(n) = n^(1.1) / log(n), g(n) = n log^3(n) und h(n) = 2^(log2(n))?

<p>h, g, f (A)</p> Signup and view all the answers

Welche der folgenden Aussagen über die Funktion f(n) = n + 10 ist korrekt?

<p>f(n + 10) = O(f(n)) (C)</p> Signup and view all the answers

Was gilt für die Funktionen f(n) = 0.3 * √n - log(n) und g(n) = 10 * n^0.2?

<p>f(n) = ω(g(n)) (A), f(n) = Θ(g(n)) (B)</p> Signup and view all the answers

Welche der folgenden Eigenschaften beschreibt korrekt das Verhalten von n^b mit 0 < b < 1?

<p>n^b = o(n) (C)</p> Signup and view all the answers

Was beschreibt die Beziehung zwischen n^k und a^n für jedes a > 1?

<p>n^k = o(a^n) (B)</p> Signup and view all the answers

Welche der folgenden Aussagen trifft auf die Funktion f(n) = n * log(n) + 4 * n^2 zu?

<p>f(n) = O(n^2) (C)</p> Signup and view all the answers

Was gilt im Allgemeinen für log_a(n), wenn a > 1?

<p>log_a(n) = o(n) (D)</p> Signup and view all the answers

Welche der folgenden Funktionen geht schneller gegen unendlich?

<p>n^2 (A)</p> Signup and view all the answers

Flashcards

Geometrische Reihe Formel

Die Formel zur Berechnung der Summe einer geometrischen Reihe lautet: Σ(i=0 bis n) ai = (an+1 - 1) / (a - 1), wenn a ≠ 1.

Induktionsanfang

Der Induktionsanfang ist der erste Schritt bei einem Beweis durch vollständige Induktion. Hier wird die Formel für den Basisfall (n=0) überprüft.

Induktionsschritt

Der Induktionsschritt zeigt, dass wenn die Formel für ein Wert n gilt, sie auch für n+1 gilt.

Vollständige Induktion

Ein Beweisverfahren, bei dem man zuerst den Basisfall zeigt und dann zeigt, dass wenn die Aussage für n wahr ist, sie auch für n+1 wahr ist.

Signup and view all the flashcards

Geometrische Reihe

Eine Reihe, deren Terme durch eine Konstante multipliziert werden, um die nächsten Terme zu erhalten.

Signup and view all the flashcards

Formel für a_n

Für a_n in der geometrischen Reihe gilt: a_n = a^n, wobei a die Basis und n der Term ist.

Signup and view all the flashcards

Summierung geometrischer Reihe

Die Summe der ersten n Terme einer geometrischen Reihe wird durch die Formel (an+1 - 1) / (a - 1) berechnet, wenn a ungleich 1 ist.

Signup and view all the flashcards

a ≠ 1 Bedingung

Die Bedingung a ≠ 1 ist essentiell für die Gültigkeit der Formel für die geometrische Reihe, da der Nenner sonst null wäre.

Signup and view all the flashcards

Binärsuche

Eine Methode zur Suche nach einem Element in einem sortierten Array. Sie reduziert die Suchzeit durch wiederholtes Halbieren des Suchbereichs.

Signup and view all the flashcards

Sortierte Arrays

Arrays, in denen die Elemente in aufsteigender Reihenfolge angeordnet sind.

Signup and view all the flashcards

Lineare Suche

Eine Suche, die alle Elemente eines Arrays nacheinander durchläuft, um das gesuchte Element zu finden.

Signup and view all the flashcards

Korrektheit der Binärsuche

Die Methode findet das richtige Element, wenn es im Array vorhanden ist und gibt korrekterweise an, dass es nicht vorhanden ist, wenn dies der Fall ist.

Signup and view all the flashcards

Rekursion

Eine Methode, bei der die Funktion sich selbst aufruft, mit veränderten Parametern.

Signup and view all the flashcards

Suchraum

Der Teil des Arrays, in dem das gesuchte Element gesucht wird.

Signup and view all the flashcards

Mitte

Der Mittelpunkt des aktuellen Suchraums; der Index des Elements der Mitte des nach Möglichkeit verbleibenden Arrayabschnitts.

Signup and view all the flashcards

Induktionsanfang (d = 0)

Der Fall, in dem der Suchraum leer ist; die Suche bricht sofort ab mit der Aussage,"Element nicht gefunden".

Signup and view all the flashcards

Eingabelänge

Die Anzahl der Elemente, die ein Algorithmus als Eingabe erhält.

Signup and view all the flashcards

Worst-Case Laufzeit

Die längstmögliche Zeit, die ein Algorithmus für eine bestimmte Eingabelänge benötigt.

Signup and view all the flashcards

Abstrakter Rechner

Ein theoretisches Modell eines Rechners, das die grundlegenden Operationen eines realen Computers vereinfacht.

Signup and view all the flashcards

Bis auf einen konstanten Faktor

Die Laufzeit eines Algorithmus wird als konstant angesehen, wenn der Faktor, um den sich die Laufzeit auf zwei verschiedenen Rechnern unterscheidet, immer gleich ist.

Signup and view all the flashcards

Pseudocode

Eine informelle Beschreibung eines Algorithmus, die für Menschen lesbar ist.

Signup and view all the flashcards

Assembler Sprache

Eine Programmiersprache, die direkt von der CPU verarbeitet wird.

Signup and view all the flashcards

C++ Befehle

Anweisungen in der Programmiersprache C++, die von einem Compiler in Maschinencode übersetzt werden.

Signup and view all the flashcards

Algorithmus

Eine präzise Rechenvorschrift, die beschreibt, wie eine Aufgabe in einer endlichen Anzahl von Schritten gelöst werden kann.

Signup and view all the flashcards

Binärsuche: Maximale Anzahl inspizierter Zellen

In einem Array mit n=2k-1 Zellen ist die maximale Anzahl an Zellen, die bei einer Binärsuche betrachtet werden, k.

Signup and view all the flashcards

Rekursive Definition von T(n)

T(n) beschreibt die maximale Anzahl inspizierter Zellen bei der Binärsuche in einem Array mit n Zellen. Sie wird rekursiv definiert als: T(0) = 0 und T(n) = T(n-1)/2 + 1.

Signup and view all the flashcards

Induktionsbeweis für T(2k-1) = k

Der Beweis wird mit vollständiger Induktion geführt. Der Induktionsanfang zeigt T(2⁰-1) = T(0) = 0. Der Induktionsschritt zeigt, dass T(2k+1-1) = T(2k-1) + 1 = k + 1 gilt, wenn man annimmt, dass T(2k-1) = k gilt.

Signup and view all the flashcards

Eingabelänge: Skalierung von Programmen

Die Eingabelänge beschreibt die Größe der Eingabe, die ein Programm verarbeitet. Die Skalierung eines Programms beschreibt, wie stark die Laufzeit bei vergrößerter Eingabelänge ansteigt.

Signup and view all the flashcards

Logarithmus: Definition

Der Logarithmus von x zur Basis a, geschrieben als loga(x), ist die Zahl z, für die gilt: az = x. Anders gesagt: Die Potenz, auf die die Basis a erhoben werden muss, um x zu erhalten, ist der Logarithmus.

Signup and view all the flashcards

Logarithmus: Rechenregeln

Es gelten folgende Rechenregeln für Logarithmen: aloga(x) = x, loga(x * y) = loga(x) + loga(y), loga(x^y) = y * loga(x), loga(x) = (loga(b)) * (logb(x)).

Signup and view all the flashcards

4log2(n) vereinfachen

4log2(n) = n².

Signup and view all the flashcards

bloga(x) vereinfachen

bloga(x) = xloga(b).

Signup and view all the flashcards

Asymptotische Notation

Eine Methode, um das Wachstum von Funktionen für große Eingaben zu vergleichen. Sie beschreibt, wie schnell eine Funktion wächst im Vergleich zu anderen Funktionen.

Signup and view all the flashcards

o(n)

Beschreibt eine Funktion, die langsamer wächst als eine lineare Funktion. Das heißt, für große Eingaben wird die Funktion kleiner als ein Vielfaches von n.

Signup and view all the flashcards

Ω(n)

Beschreibt eine Funktion, die mindestens so schnell wächst wie eine lineare Funktion. Für große Eingaben ist die Funktion größer als ein Vielfaches von n.

Signup and view all the flashcards

Θ(n)

Beschreibt eine Funktion, die im gleichen Maße wächst wie eine lineare Funktion. Für große Eingaben verhält sich die Funktion wie ein Vielfaches von n.

Signup and view all the flashcards

f(n) = O(g(n))

Funktion f wächst höchstens so schnell wie Funktion g. Für große Eingaben ist f(n) kleiner oder gleich einem Vielfachen von g(n).

Signup and view all the flashcards

f(n) = o(g(n))

Funktion f wächst langsamer als Funktion g. Für große Eingaben ist f(n) kleiner als jedes Vielfache von g(n).

Signup and view all the flashcards

f(n) = Ω(g(n))

Funktion f wächst mindestens so schnell wie Funktion g. Für große Eingaben ist f(n) größer oder gleich einem Vielfachen von g(n).

Signup and view all the flashcards

f(n) = ω(g(n))

Funktion f wächst schneller als Funktion g. Für große Eingaben ist f(n) größer als jedes Vielfache von g(n).

Signup and view all the flashcards

Geschachtelte for-Schleifen

Mehrere for-Schleifen, die innerhalb voneinander ausgeführt werden. Jede innere Schleife wird für jeden Durchlauf der äußeren Schleife vollständig ausgeführt.

Signup and view all the flashcards

Kubische Laufzeit

Die Laufzeit eines Algorithmus wächst proportional zur dritten Potenz des Eingabegrößen. Sie ist also deutlich langsamer als lineare oder quadratische Laufzeiten.

Signup and view all the flashcards

Laufzeit einer While-Schleife

Die Anzahl der Schritte, die eine While-Schleife ausführt, um zu terminieren.

Signup and view all the flashcards

Rekursionsgleichung

Eine Gleichung, die die Laufzeit eines Algorithmus als Funktion seiner Eingangsgröße und seiner rekursiven Aufrufe definiert.

Signup and view all the flashcards

Master-Theorem

Ein Theorem, das die asymptotische Laufzeit einer rekursiven Funktion basierend auf ihren Rekursionsbeziehungen und den Kosten für die Basisfälle bestimmt.

Signup and view all the flashcards

Logarithmische Laufzeit

Die Laufzeit eines Algorithmus wächst proportional zum Logarithmus der Eingabegröße. Der Algorithmus wird also schneller mit größerer Eingabe.

Signup and view all the flashcards

Beispiel: While-Schleife mit √n

Eine While-Schleife, die die Eingabe in jedem Schritt durch die Quadratwurzel dividiert.

Signup and view all the flashcards

Θ(log(log(n)))

Die asymptotische Laufzeit der While-Schleife mit √n. Die Laufzeit wächst sehr langsam, viel langsamer als logarithmisch.

Signup and view all the flashcards

Study Notes

Algorithmen und Datenstrukturen 1 - Sommersemester 2024

  • Veranstaltung: Algorithmen und Datenstrukturen 1
  • Semester: Sommersemester 2024
  • Dozent: Ulrich Meyer
  • Datum der Präsentation: 30. April 2024

Wer ist wer?

  • Dozent (Vorlesungen): Ulrich Meyer, [email protected], Raum R 304, RMS 11-15
  • Übungskoordination: Alex Schickedanz, Daniel Allendorf, [email protected], Räume R312 und R311, RMS 11-15
  • Tutoren: Amelia Linek, Anastasia Navodkina, Arne Gideon, Arne Riester, Boris Senatov, Elias Meinecke, Gerome Stiller, Hoai Vy Nguyen, Jannis Achtnich, Joshua Kannenberg, Lukas Geis, Paul Dallwig, Sebastian Beckmann, Viktor Rieß, Zeno Weil

Webseite für Umfragen

  • Umfrage-URL: https://aeffm.de/vote
  • Für Umfragen während der Veranstaltung ein Browserfenster öffnen.

Studiengang

  • (A) Informatik Bachelor
  • (B) Bioinformatik
  • (C) Wirtschaftsinformatik
  • (D) Informatik als Nebenfach
  • (E) Informatik Lehramt
  • (F) Sonstiges

Fachsemester

  • (i) i-tes Fachsemester
  • (A=1, B=2,...)

Besuchte Vorlesung (ALGO1 / Datenstrukturen)

  • (i) i-ter Besuch

Thema der Veranstaltung

  • abstrakte Datentypen und Datenstrukturen
  • Operationen auf Datensätzen z.B. Einfügen, Entfernen von Schlüsseln nach Alter
  • häufig auftretende Strukturen
    • Stack (Kellerspeicher)
    • Queue (Warteschlange)
    • Heap (Prioritätswarteschlange)

Effiziente Datenstrukturen

  • Entwürfe für effiziente Datenstrukturen - Graphen
    • Zusammenhangskomponenten
    • Minimale Spannbäume
    • Kürzeste Wege

Weitere Entwurfsmethoden für Algorithmen

  • Greedy (z.B. Ablaufplanung)
  • Divide & Conquer (z.B. Sortieren)
  • Dynamische Programmierung (z.B. Paarweises Alignment)

Aufbau der Veranstaltung

  • Diskrete Modellierung (bzw. Vorkurs)
    • Vollständige Induktion
    • Allgemeine Beweismethoden
    • Beweistechniken, Induktion und Rekursion
    • Asymptotik und Laufzeitanalyse
  • Grundlagen der Programmierung 1
    • Kenntnisse der elementaren Datenstrukturen
  • Lineare Algebra und Analysis
    • Logarithmen
    • Grenzwerte
    • Asymptotische Notation

Literatur

  • Skripte und Folien auf der Webseite der Veranstaltung

  • T.H. Cormen et al., „Introduction to Algorithms",

  • M. T. Goodrich et al., „Data Structures and Algorithms in C++“,

  • M. Dietzfelbinger et al., „Algorithmen und Datenstrukturen, die Grundwerkzeuge“,

  • R. Sedgewick, „Algorithmen in C++“,

  • J. Kleinberg and E. Tardos, „Algorithm Design“

  • Literatur im Semesterapparat „Algorithmen und Datenstrukturen 1“ in der Bibliothek (1. Stock, Robert-Mayer Strasse 11-15)

Übungsbetrieb

  • Anmeldung bis Donnerstag, 18.04. im AUGE-System
  • Übungsblätter (PDF) jeden Montag auf der Webseite
  • Abgabe der Lösungen (PDF) nach einer Woche im SAP-System
  • Link für Abgabe nach Anmeldung per E-Mail
  • Übungsgruppen ab Donnerstag, 25.04.
  • Ausgabe 0. Übungsblatt ohne Abgabe, Diskussion am 25.04.
  • Ausgabe 1. Übungsblatt Montag, 22.04. (Abgabe bis 29.04. 23:55, Diskussion ab 02.05.)
  • Übungsaufgaben sollten mit anderen besprochen werden, Lösungen selbstständig aufschreiben

Klausur

  • Hauptklausur: Montag, 29. Juli 2024, voraussichtlich ab 9:00 Uhr
  • Zweitklausur: Mittwoch, 25. September 2024, voraussichtlich ab 9:00 Uhr
  • Übungspunkte zählen (10 %) zur Klausur
  • Bestehen der Klausur (i.d.R. ≥ 50%) Voraussetzung für Bestehen der Veranstaltung
  • Endnote basiert auf Gesamtpunktzahl aus Klausur und Übungen

Weitere Informationen

  • Vor- und Nachbereitung der Vorlesungen
  • Teilnahme am Übungsbetrieb
  • Teamarbeit vs. Einzelkämpfer
  • Studienrichtlinien beachten
  • Sprechstunde per E-Mail vereinbaren
  • Fragen, Kommentare, Antworten für Interaktion

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Algorithmen und Datenstrukturen 1 Sommersemester 2024 PDF

Description

Dieses Quiz behandelt die Grundlagen von Algorithmen und Datenstrukturen, wie sie im Sommersemester 2024 in der Vorlesung von Ulrich Meyer präsentiert werden. Es wird den Teilnehmern helfen, sich auf die Prüfungen vorzubereiten und ihr Wissen über die behandelten Themen zu vertiefen.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser