Algorithmentheorie: Quizfragen und Übungen für Informatik-Studierende

Question 1

Nenne die wichtigsten Phasen im Algorithmendesign-Prozess.

Accepted Answer

Problemerkennung, Algorithmusentwurf, Analyse, Implementierung, Testen

Answer

Analyse, Problemerkennung, Algorithmusentwurf, Implementierung, Testen

Answer

Implementierung, Problemerkennung, Analyse, Algorithmusentwurf, Testen

Question 2

Welche Aussage beschreibt eine Heuristik am besten?

Accepted Answer

Eine Methode, die eine schnelle, aber nicht unbedingt perfekte Lösung liefert.

Answer

Ein Algorithmus, der immer die beste Lösung findet.

Answer

Ein Programm, das für alle Eingaben das gleiche Ergebnis liefert.

Answer

Eine Technik, die garantiert, dass ein Algorithmus in kurzer Zeit läuft.

Question 3

Welcher der folgenden Datentypen wird verwendet, um eine Sammlung von **eindeutigen** Elementen zu speichern?

Accepted Answer

Menge

Answer

Liste

Answer

Tabelle

Answer

Baum

Question 4

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Bestimmen, ob ein Graph einen Hamilton-Kreis enthält

Answer

Bestimmen, ob eine Zahl gerade ist

Answer

Berechnen des kürzesten Pfads in einem gewichteten Graphen

Answer

Bestimmen, ob eine Zeichenkette ein Palindrom ist

Question 5

Was ist der Zweck eines Approximationsalgorithmus?

Accepted Answer

Eine näherungsweise Lösung für ein NP-hartes Problem zu finden

Answer

Eine optimale Lösung für ein NP-vollständiges Problem zu finden

Answer

Die Laufzeit eines Algorithmus zu reduzieren

Answer

Den Speicherverbrauch eines Algorithmus zu reduzieren

Question 6

Was ist die asymptotische Laufzeitkomplexität des Bubble-Sort-Algorithmus?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(n^3)

Question 7

Erläutere die Vorzüge und Einschränkungen von Heuristiken bei der Bewältigung komplexer Probleme.

Accepted Answer

Heuristiken sind hilfreich, wenn ein exakter Algorithmus für die Problemlösung zu viel Zeit benötigen würde und eine annähernde Lösung ausreicht.

Answer

Heuristiken garantieren stets optimale Lösungen.

Answer

Heuristiken sind ausschließlich für unkomplizierte Probleme geeignet.

Answer

Heuristiken sind durchweg schneller als präzise Algorithmen.

Question 8

Welcher der folgenden Algorithmen ist NP-vollständig und befasst sich mit Zahlentheorieproblemen?

Accepted Answer

Faktorisierung

Answer

Bubblesort

Answer

Primzahltest

Answer

Gauß-Elimination

Question 9

Welcher der folgenden Algorithmen lässt sich nicht in polynomialer Zeit lösen?

Accepted Answer

Hamiltonkreisproblem

Answer

Dijkstras Algorithmus

Answer

Quicksort

Question 10

Erläutere, warum Heuristiken trotz ihrer Einschränkungen in der Praxis wertvolle Hilfsmittel sein können. Nenne konkrete Beispiele für Situationen, in denen der Einsatz von Heuristiken sinnvoll ist.

Accepted Answer

Heuristiken sind besonders nützlich, wenn die Suche nach einer exakten Lösung zu zeitaufwendig wäre.

Answer

Heuristiken liefern immer optimale Ergebnisse.

Answer

Heuristiken sind nur für triviale Probleme geeignet.

Answer

Heuristiken ersetzen stets exakte Algorithmen.

Question 11

Welcher Algorithmus ist ein NP-vollständiges Problem?

Accepted Answer

SAT

Answer

Dijkstra

Answer

Merge Sort

Answer

Binäre Suche

Question 12

Welche Laufzeitkomplexität hat im Allgemeinen ein Algorithmus, der eine sortierte Liste durchsucht?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(2^n)

Answer

O(n^2)

Question 13

Welche Eigenschaft ist charakteristisch für NP-vollständige Probleme?

Accepted Answer

Sie sind im Allgemeinen nicht in polynomialer Zeit lösbar.

Answer

Sie haben eine lineare Laufzeitkomplexität.

Answer

Sie sind immer leicht lösbar.

Question 14

Welche Heuristik wird häufig zur Lösung des Rucksackproblems eingesetzt?

Accepted Answer

Greedy

Answer

backtracking

Answer

2-Opt

Answer

Dijkstra

Question 15

Welche Laufzeitkomplexität hat im Allgemeinen ein Algorithmus, der eine Binärbaumsuche durchführt?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(2^n)

Question 16

Welcher der folgenden Algorithmen ist ein bekanntes NP-vollständiges Problem?

Accepted Answer

Hamiltonkreisproblem

Answer

Bubblesort

Answer

Primfaktorzerlegung

Answer

Dijkstra-Algorithmus

Question 17

Was ist eine wesentliche Eigenschaft von Approximationsalgorithmen?

Accepted Answer

Sie liefern eine Lösung, die nicht immer exakt ist.

Answer

Sie garantieren immer eine optimale Lösung.

Answer

Sie sind immer effizienter als exakte Algorithmen.

Answer

Sie können nur für bestimmte Problemklassen eingesetzt werden.

Question 18

Welche der folgenden Heuristiken eignet sich besonders für das Rucksackproblem?

Accepted Answer

Greedy-Algorithmus

Answer

Zweige-und-Schranken-Verfahren

Answer

Monte-Carlo-Simulation

Answer

Dynamische Programmierung

Question 19

Welche Technik dient der Reduzierung des Speicherbedarfs eines Algorithmus?

Accepted Answer

Memoization

Answer

Garbage Collection

Answer

Virtuelle Speicherverwaltung

Answer

Paging

Question 20

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

3-SAT

Answer

Lineare Regression

Answer

Primzahltest

Answer

Sortierung

Question 21

Was ist eine Heuristik?

Accepted Answer

Ein Verfahren, das keine optimale Lösung garantiert, aber oft gute Ergebnisse liefert

Answer

Eine Datenstruktur zur Speicherung von Daten

Answer

Ein Algorithmus, der immer die optimale Lösung findet

Question 22

Welcher der folgenden Algorithmen ist ein Approximationsalgorithmus?

Accepted Answer

Der Greedy-Algorithmus für die k-Färbung

Answer

Quicksort-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Bayes'scher Klassifikator

Question 23

Welcher der folgenden Algorithmen ist ein Approximationsalgorithmus?

Accepted Answer

Der Algorithmus von Christofides für das Problem des Handlungsreisenden

Answer

Der Algorithmus von Dijkstra für das Problem der kürzesten Verbindung

Answer

Der Algorithmus von Floyd-Warshall für das Problem der allgegenwärtigen kürzesten Verbindungen

Question 24

Welche der folgenden Heuristiken wird zur Lösung des Problems der Jobplanung verwendet?

Accepted Answer

Die längste Aufgabe zuerst (LPT)-Heuristik

Answer

Die höchste Priorität zuerst (HPF)-Heuristik

Answer

Die geringste Slack-Zeit zuerst (EST)-Heuristik

Answer

Die kürzeste Aufgabe zuerst (SPT)-Heuristik

Question 25

Welche der folgenden Aussagen über Algorithmen mit exponentieller Zeitkomplexität ist korrekt?

Accepted Answer

Ihre Laufzeit wächst so schnell, dass sie für große Eingaben unpraktisch werden.

Answer

Sie sind immer schneller als Algorithmen mit polynomieller Zeitkomplexität.

Answer

Sie können Probleme lösen, die von Algorithmen mit polynomieller Zeitkomplexität nicht gelöst werden können.

Question 26

Welcher der folgenden Ansätze wird verwendet, um die Komplexität von Algorithmen zu reduzieren?

Accepted Answer

Vereinfachung des Problems

Answer

Verwendung eines langsamen Computers

Answer

Erhöhung der Datengröße

Answer

Ignorieren der asymptotischen Analyse

Question 27

Welche der folgenden Datenstrukturen wird in einem Algorithmus zum Finden des kürzesten Weges verwendet?

Accepted Answer

Warteschlange

Answer

Stapel

Answer

Hash-Tabelle

Answer

Baum

Question 28

Welche der folgenden Aussagen über rekursive Algorithmen ist falsch?

Accepted Answer

Sie sind immer effizienter als iterative Algorithmen.

Answer

Sie können zu Stapelüberläufen führen.

Answer

Sie können leicht zu verstehen und zu implementieren sein.