Select your language

Suggested languages for you:
Log In Anmelden

Lernmaterialien für Theoretische Informatik an der Hochschule des Bundes für öffentliche Verwaltung

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Theoretische Informatik Kurs an der Hochschule des Bundes für öffentliche Verwaltung zu.

TESTE DEIN WISSEN

Was bedeutet TSP?

Lösung anzeigen
TESTE DEIN WISSEN

Traveling Salesperson



Gibt es im ungerichteten, gewichteten Graphen 𝐺 = (𝑉, 𝐸) eine Rundreise durch den Graphen (in der jeder Knoten, bis auf der Start- und Zielkonten genau einmal vorkommt), so dass die Summe der Kantengewichte der Rundreise kleiner oder gleich der Gewichtsschranke 𝑤 sind?

Lösung ausblenden
TESTE DEIN WISSEN

Fibonacci Suche (nicht unbedingt relevant, aber sollte man kennen)

Lösung anzeigen
TESTE DEIN WISSEN

Anhand der Fibonacci zahlen wird ein soritertes Array durchsucht. (Fibonaccizahlen sind immer die letzten zwei Fibonaccizahlen ergeben die nächste)

Lösung ausblenden
TESTE DEIN WISSEN

Sei A eine sequentielle Datenstruktur mit 𝒏𝒏 Feldern (𝐴𝐴 0 , 𝐴𝐴 1 , … , 𝐴𝐴 𝑛𝑛 − 1 ), die mit Werten aus einer Menge ℳ belegt sind.


Sei 𝑤𝑤 ein Wert aus ℳ.


Wie lautet das Suchproblem?

Lösung anzeigen
TESTE DEIN WISSEN

Es ist Index 𝑖 (0 ≤ 𝑖 ≤ 𝑛 − 1) zu finden, so dass gilt:

𝑤 = A[ 𝑖] oder der Wert None, falls 𝑤 nicht in A existiert

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein Hamiltonkreis (HAM-Cycle)?

Lösung anzeigen
TESTE DEIN WISSEN

Gegeben sei ein Graph G=(V,E). Gibt es einen Hamiltonkreis (Rundreise) durch den Graphen, in dem jeder Knoten (bis auf den Start/Ziel-Knoten) genau einmal vorkommt.

Lösungsmöglichkeit: Ausprobieren


Hamiltonkreis ist mit dem Problem der Sehenwürdigkeiten vergleichbar. Jede Sehenswürdigkeit soll nur einmal besucht werden, denn hier geht es um Knoten

Lösung ausblenden
TESTE DEIN WISSEN

Welche Laufzeitklasse hat der SelectionSort?

Lösung anzeigen
TESTE DEIN WISSEN

O(n^2)

Lösung ausblenden
TESTE DEIN WISSEN

Ein binärer Suchbaum ist ein Binärbaum, bei dem für jeden Knoten des Baumes gilt:

Lösung anzeigen
TESTE DEIN WISSEN

Der jeweilige Wert aller Elemente im am linken Kind gewurzelten Teilbaum sind kleiner als der Knoten



Der jeweilige Wert aller Elemente im am rechten Kind gewurzelten Teilbaum sind größer als der Knoten

Lösung ausblenden
TESTE DEIN WISSEN

Ein Lösungskandidat für das TSP kann in polynomieller Zeit überprüft werden.

Lösung anzeigen
TESTE DEIN WISSEN

Wahr

Lösung ausblenden
TESTE DEIN WISSEN

Sei B = (V,E) ein gewurzelter Baum mit Wurzel w:

Was ist ein Blatt?

Lösung anzeigen
TESTE DEIN WISSEN

Ein Knoten ohne Kinder

Lösung ausblenden
TESTE DEIN WISSEN

Was ist das Einheitskostemaß?

Lösung anzeigen
TESTE DEIN WISSEN

Für jede Anweisung wird ein konstanter Aufwand angenommen. Bei uns zur Vereinfachung erzeugt jede Anweisung den Aufwand 1

Lösung ausblenden
TESTE DEIN WISSEN

In welchem Schritt liegt der Aufwand beim QuickSort?

Lösung anzeigen
TESTE DEIN WISSEN

Divide (Aufteilen)

Lösung ausblenden
TESTE DEIN WISSEN

Was ist der aufwändige Schritt beim MergeSort?

Lösung anzeigen
TESTE DEIN WISSEN

Combine (Zusammenfügen)

Lösung ausblenden
TESTE DEIN WISSEN

Wenn ein Algorithmus nicht-deterministisch ist, liefert er bei wiederholter Ausführung für die gleiche Eingabe stets ein anderes Ergebnis. Wahr oder Falsch?

Lösung anzeigen
TESTE DEIN WISSEN

Falsch

Lösung ausblenden
  • 23803 Karteikarten
  • 629 Studierende
  • 36 Lernmaterialien

Beispielhafte Karteikarten für deinen Theoretische Informatik Kurs an der Hochschule des Bundes für öffentliche Verwaltung - von Kommilitonen auf StudySmarter erstellt!

Q:

Was bedeutet TSP?

A:

Traveling Salesperson



Gibt es im ungerichteten, gewichteten Graphen 𝐺 = (𝑉, 𝐸) eine Rundreise durch den Graphen (in der jeder Knoten, bis auf der Start- und Zielkonten genau einmal vorkommt), so dass die Summe der Kantengewichte der Rundreise kleiner oder gleich der Gewichtsschranke 𝑤 sind?

Q:

Fibonacci Suche (nicht unbedingt relevant, aber sollte man kennen)

A:

Anhand der Fibonacci zahlen wird ein soritertes Array durchsucht. (Fibonaccizahlen sind immer die letzten zwei Fibonaccizahlen ergeben die nächste)

Q:

Sei A eine sequentielle Datenstruktur mit 𝒏𝒏 Feldern (𝐴𝐴 0 , 𝐴𝐴 1 , … , 𝐴𝐴 𝑛𝑛 − 1 ), die mit Werten aus einer Menge ℳ belegt sind.


Sei 𝑤𝑤 ein Wert aus ℳ.


Wie lautet das Suchproblem?

A:

Es ist Index 𝑖 (0 ≤ 𝑖 ≤ 𝑛 − 1) zu finden, so dass gilt:

𝑤 = A[ 𝑖] oder der Wert None, falls 𝑤 nicht in A existiert

Q:

Was ist ein Hamiltonkreis (HAM-Cycle)?

A:

Gegeben sei ein Graph G=(V,E). Gibt es einen Hamiltonkreis (Rundreise) durch den Graphen, in dem jeder Knoten (bis auf den Start/Ziel-Knoten) genau einmal vorkommt.

Lösungsmöglichkeit: Ausprobieren


Hamiltonkreis ist mit dem Problem der Sehenwürdigkeiten vergleichbar. Jede Sehenswürdigkeit soll nur einmal besucht werden, denn hier geht es um Knoten

Q:

Welche Laufzeitklasse hat der SelectionSort?

A:

O(n^2)

Mehr Karteikarten anzeigen
Q:

Ein binärer Suchbaum ist ein Binärbaum, bei dem für jeden Knoten des Baumes gilt:

A:

Der jeweilige Wert aller Elemente im am linken Kind gewurzelten Teilbaum sind kleiner als der Knoten



Der jeweilige Wert aller Elemente im am rechten Kind gewurzelten Teilbaum sind größer als der Knoten

Q:

Ein Lösungskandidat für das TSP kann in polynomieller Zeit überprüft werden.

A:

Wahr

Q:

Sei B = (V,E) ein gewurzelter Baum mit Wurzel w:

Was ist ein Blatt?

A:

Ein Knoten ohne Kinder

Q:

Was ist das Einheitskostemaß?

A:

Für jede Anweisung wird ein konstanter Aufwand angenommen. Bei uns zur Vereinfachung erzeugt jede Anweisung den Aufwand 1

Q:

In welchem Schritt liegt der Aufwand beim QuickSort?

A:

Divide (Aufteilen)

Q:

Was ist der aufwändige Schritt beim MergeSort?

A:

Combine (Zusammenfügen)

Q:

Wenn ein Algorithmus nicht-deterministisch ist, liefert er bei wiederholter Ausführung für die gleiche Eingabe stets ein anderes Ergebnis. Wahr oder Falsch?

A:

Falsch

Theoretische Informatik

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten Theoretische Informatik Kurse im gesamten StudySmarter Universum

Informatik

Hochschule für Polizei Baden-Württemberg

Zum Kurs
Theoretische Physik I

Universität Wien

Zum Kurs
Technische Informatik

Hochschule des Bundes für öffentliche Verwaltung

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Theoretische Informatik
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Theoretische Informatik