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.</p> Signup and view all the answers

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

    <p>oben ist gleich unten.</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.</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.</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.</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</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</p> Signup and view all the answers

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

    <p>k</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.</p> Signup and view all the answers

    Was beschreibt der Logarithmus loga(x)?

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

    Was ist 4log2(n) gleich?

    <p>n^2</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.</p> Signup and view all the answers

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

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

    Was ist die Laufzeit der geschachtelten for-Schleifen?

    <p>Kubisch</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</p> Signup and view all the answers

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

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

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

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

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

    <p>Θ(log log n)</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</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</p> Signup and view all the answers

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

    <p>Fall 2</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.</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.</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.</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.</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.</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.</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.</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.</p> Signup and view all the answers

    Wie viele Gitterpunkte befinden sich unterhalb der Hauptdiagonale?

    <p>n^2 - n Gitterpunkte</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$</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$</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}$</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}$</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.</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</p> Signup and view all the answers

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

    <p>$\sum_{i=0}^{n} a^i$</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</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))</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))</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)</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)</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)</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)</p> Signup and view all the answers

    Welche der folgenden Funktionen geht schneller gegen unendlich?

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

    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