Lesson_1 Intro

Question 1

Was ist ein Algorithmus?

Answer 1

Ein Algorithmus ist eine in der Beschreibung und Ausführung endliche, deterministische und effektive Vorschrift zur Lösung eines Problems, die effizient sein sollte.

Question 2

Was besagt die Church-Turing-These?

Answer 2

Die Church-Turing-These besagt, dass die Klasse der Turing-berechenbaren Funktionen mit der Klasse der intuitiv berechenbaren Funktionen übereinstimmt. Sie ist weder beweisbar noch widerlegbar.

Question 3

Was sind die Beurteilungskriterien für Algorithmen?

Answer 3

• Korrektheit: Der Algorithmus muss das richtige Ergebnis liefern.
• Eindeutigkeit: Bei gleicher Eingabe sollte die gleiche Lösung produziert werden.
• Laufzeit: Die Zeit, die ein Algorithmus benötigt, um zu einem Ergebnis zu kommen.
• Speicherbedarf: Der Speicher, den ein Algorithmus zur Ausführung benötigt.

Question 4

Welche Faktoren beeinflussen die Effizienz eines Algorithmus?

Answer 4

• Laufzeit (abhängig von der Problemgröße)
• Speicherbedarf
• Art der Eingabe

Question 5

Was bedeutet „Berechenbarkeit“ in der Informatik?

Answer 5

Berechenbarkeit beschreibt, ob ein Problem algorithmisch gelöst werden kann, also ob eine Lösung existiert und wie man zu dieser Lösung kommt.

Question 6

Welche Arten von Problemen sind nach der Church-Turing-These nicht berechenbar?

Answer 6

Nach der Church-Turing-These gibt es Probleme wie das Halteproblem, das nicht berechenbar ist.

Question 7

Welche Bedeutung hat die Landau-Notation für die Analyse von Algorithmen?

Answer 7

Die Landau-Notation (z.B. O(n)) gibt an, wie sich die Laufzeit eines Algorithmus asymptotisch verhält, wenn die Eingabegröße (n) gegen unendlich geht.

Question 8

Was ist der Unterschied zwischen der Landau-Notation O(n) und der Tilde-Notation ∼ f(n)?

Answer 8

Die Landau-Notation ignoriert konstante Faktoren und niedrige Ordnungsterme. Die Tilde-Notation bezieht den konstanten Faktor des führenden Terms mit ein.

Question 9

Was bedeutet O(1)?

Answer 9

O(1) bezeichnet eine konstante Laufzeit, unabhängig von der Eingabegröße.

Question 10

Nenne ein Beispiel für einen Algorithmus mit quadratischer Komplexität O(n²).

Answer 10

Ein Beispiel ist Bubble Sort, wo alle Paare von Elementen miteinander verglichen werden.

Question 11

Was sind die Eigenschaften von MergeSort?

Answer 11

MergeSort ist ein rekursiver, stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) und basiert auf dem Divide-and-Conquer-Prinzip.

Question 12

Wann ist ein Sortieralgorithmus stabil?

Answer 12

Ein Sortieralgorithmus ist stabil, wenn er die relative Reihenfolge von Elementen mit gleichen Werten beibehält.

Question 13

Welche Aufgaben können mit Graphenalgorithmen gelöst werden?

Answer 13

• Kürzeste Wege (Dijkstra)
• Minimale Spannbäume (Kruskal, Prim)
• Durchsuchen von Graphen (DFS, BFS)

Question 14

Was ist der Unterschied zwischen Tiefensuche (DFS) und Breitensuche (BFS)?

Answer 14

DFS durchsucht einen Graphen in die Tiefe, während BFS in der Breite arbeitet.

Question 15

Was ist eine Hashfunktion und wofür wird sie verwendet?

Answer 15

Eine Hashfunktion wandelt eine Eingabe (Schlüssel) in einen Hashwert um, verwendet für schnelle Datensuche in Hash-Tabellen.

Question 16

Was ist ein Greedy-Algorithmus?

Answer 16

Ein Greedy-Algorithmus trifft immer die lokal beste Entscheidung, um eine globale Lösung zu finden. Er funktioniert gut bei Problemen mit der Greedy-Eigenschaft.

Question 17

Welche Komplexität hat die naive Matrizenmultiplikation?

Answer 17

Die naive Matrizenmultiplikation hat eine Zeitkomplexität von O(n³).

Question 18

Was versteht man unter der Laufzeitkomplexität eines Algorithmus?

Answer 18

Unter der Laufzeitkomplexität eines Algorithmus versteht man die Anzahl der Schritte, die der Algorithmus im schlimmsten Fall benötigt, um eine Eingabe mit einer bestimmten Länge 𝑛 n zu bearbeiten.

Question 19

Was ist der Insertion Sort Algorithmus?

Answer 19

Der Insertion Sort ist ein einfacher, stabiler Sortieralgorithmus, der das zu sortierende ** Array in zwei Teile unterteilt: einen sortierten und einen unsortierten Teil. Elemente aus dem unsortierten Teil** werden nacheinander entnommen und in den sortierten Teil an der richtigen Position eingefügt.

Question 20

Wie lautet die Laufzeitkomplexität des Insertion Sort im besten Fall?

Answer 20

Die Laufzeitkomplexität im besten Fall beträgt 𝑂(𝑛), da der Algorithmus nur dann optimal arbeitet, wenn die Eingabedaten bereits vollständig sortiert sind und keine Verschiebungen erforderlich sind.

Question 21

Wie lautet die Laufzeitkomplexität des Insertion Sort im schlechtesten Fall?

Answer 21

Die Laufzeitkomplexität im schlechtesten Fall beträgt 𝑂(𝑛2), da jedes Element im schlimmsten Fall an die erste Position verschoben werden muss, was viele Vergleiche und Verschiebungen erfordert.

Question 22

Wie funktioniert der Bubble Sort Algorithmus?

Answer 22

Bubble Sort vergleicht benachbarte Elemente eines Arrays und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Dieser Prozess wird wiederholt, bis keine Vertauschungen mehr nötig sind, was bedeutet, dass das Array sortiert ist.

Question 23

Wie lautet die Laufzeitkomplexität von Bubble Sort?

Answer 23

• im besten Fall O(n)
• im schlimmsten Fall O(n2)

Question 24

Was ist der Unterschied zwischen Bubble Sort und Insertion Sort?

Answer 24

Bubble Sort vergleicht und vertauscht benachbarte Elemente, während Insertion Sort Elemente in die richtige Position im bereits sortierten Teil des Arrays einfügt. Insertion Sort ist oft effizienter bei teilweise sortierten Arrays, während Bubble Sort jedes Mal die gleichen Vergleiche durchführt, unabhängig vom Zustand des Arrays.

Question 25

Was ist der Merge Sort Algorithmus?

Answer 25

Merge Sort ist ein Divide-and-Conquer-Algorithmus, der ein Array wiederholt in zwei Hälften teilt, die einzelnen Hälften rekursiv sortiert und dann die sortierten Hälften zu einem vollständig sortierten Array zusammenführt.

Question 26

Wie funktioniert der Merge Sort Algorithmus?

Answer 26

Merge Sort teilt das Array in zwei Hälften, sortiert jede Hälfte rekursiv und führt die beiden sortierten Hälften schließlich zusammen. Der Zusammenführungsprozess kombiniert die beiden Teilarrays zu einem sortierten Gesamtarray, indem die kleinsten Elemente der Teilarrays verglichen und nacheinander in ein neues Array eingefügt werden.

Question 27

Wie lautet die Laufzeitkomplexität von Merge Sort im besten, schlechtesten und durchschnittlichen Fall?

Answer 27

Die Laufzeitkomplexität von Merge Sort beträgt in allen Fällen O(nlogn), da das Array immer in zwei Hälften geteilt und dann die sortierten Hälften zusammengeführt werden, unabhängig von der Reihenfolge der Eingabe.