Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithmen, Datenstrukturen und Programmiersprachen > Algorithmenentwurf > Flashcards

Algorithmenentwurf Flashcards

Indunkion, Iteration, Rekursion, Methoden des Algorithmen-Entwurfs, Korrektheit und Verifikation, Effizienz und Komplexität von Algorithmen

1
Q

Welche Herangehensweisen, wie Befehlsfolgen organisiert sind, gibt es?

1

A
  • Iterativ
  • Rekursiv
  • Induktiv
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was sind Iterative Algorithmen?

1

A
  • for (i = 1; i<= n; i++) (…)
  • Mithilfe von Iterationen
  • zB For-Schleife
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was sind Rekursive Algorithmen?

1

A
  • Rufen sich selbst auf, um Problem zu Lösen
  • Art von Schleife
  • Meist weniger effizient, da wiederholt gleiche Methode aufgerufen und Kontext gespeichert werden muss
  • def Fakultaet(item n):
    if n == 0 then return 1
    else return Fakultaet(n-1) x n
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was sind induktive Algorithmen?

1

A
  • oft in Beweisführung
  • Problem in Teilprobleme zerlegt
  • allgemeine Regel wird aus Basisfall und wiederholbaren Schlussfolgerungen abgeleitet
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Welche sind die wesentlichen Paradigmen, nach denen Algorithmen entworfen werden?

2

A
  • Greedy
  • Divide and Conquer
  • Dynamic Programming
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Was ist das Greedy-Paradigma?

2

A
  • jeder Schritt: lokal beste Entscheidung
  • wählt Option, die momentan am vorteilhaftesten erscheint (ohne langfristige Konsequenz zu berücksichtigen)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Nenne Beispiele für Greedy-Algorithmen

2

A
  • Dijkstra-Algorithmus
  • Kruskal-Algorithmus
  • Prim-Algorithmus
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist das Divide and Conquer Paradigma?

2

A
  • Problem wird in Teilprobleme zerlegt und isoliert
  • zB Liste in zwei Hälften geteilt und getrennt sortiert / nach etwas durchsucht; Später Vergleich der Ergebnisse
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist die dynamische Programmierung?

2

A
  • Extremfall von Divide and Conquer
  • Teilprobleme werden Reihenfolge nach gelöst (zunehmende Größe)
  • Ergebnisse werden abgespeichert undw iederverwendet
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was ist der Unterschied zwischen Greedy-Algorithmus und dynamischer Programmierung?

2

A
  • Greedy: immer Verbindung zu Knoten der momentan am nächsten liegt
  • Dynamisch: immer globales Problem wird betrachtet, nicht lokal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was sind mögliche Fehlerquellen in Algorithmen?

3

A
  • Sprach- o. Syntaxfehler
  • Logische o. semantische Fehler
  • Endlosschleifen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was sind Sprach- oder Syntaxfehler?

A
  • Code entspricht nicht Regeln der Grammatik o. Programmiersprache
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was sind logische o. semantische Fehler?

3

A
  • falsche Verwendung eines Ausdrucks
  • Programm läuft, aber nicht erwartetes Ergebnis
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Was sind Endlosschleifen?

3

A
  • Nicht terminierende Schleifen
  • unpräzise / fehlerhafte Definition des Abbruchkriteriums
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Was ist die Vor- und Nachbedingung?

3

A
  • Zustand der Daten vor und nach Ausführung des Algorithmus
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Was sind Theorem-Beweiser?

3

A
  • Theorem-Beweiser basieren auf Algorithmen
  • Hilft, mathematische Sätze (halb-)automatisch zu beweisen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Was bedeutet “Total Korrekt”?

3

A
  • Korrekt: Algorithmus produziert Ausgabe
  • Terminierung: Algorithmus hält garantiert nach endlich vielen Schritten an
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Was ist Backtesting?

3

A
  • Algorithmenkontrolle
  • Funktionalität und Leistunsfähigkeit wird überprüft
  • Bewertung von Algorithmen
20
Q

Was ist die Definition des Ziels der Laufzeitbestimmung?

4

A
  • Finden einer oberen asymptotischen Grenze, der sich die Laufzeit des Algorithmus in Abhängigkeit zur Berechnung notwendiger Rechenschritte annähert
21
Q

Was bedeutet “obere asymptotische Grenze”?

4

A
  • Maximale Laufzeit, die nicht überschritten werden kann
22
Q

Was zeigt die Asymptotische Analyse?

4

A
  • wie sich Laufzeit mit Größe der Eingabedaten verhält
  • also: Worst-Case, wenn Eingabegröße sehr groß wird
23
Q

Warum ist die Laufzeitanalyse wichtig?

4

A
  • Um zu wissen, wie Algorithmus mit größeren Datenmengen skalieren wird
24
Q

Welche Arten der Komplexität gibt es?

4

A
  • Zeitkomplexität
  • Platzkomplexität
25
Q

Was ist Zeitkomplexität?

4

A
  • Ausführungsdauer
26
Q

Was ist Platzkomplexität?

4

A
  • Speicherplatzbedarf
27
Q

Was ist die O-Notation?

4

A
  • Notation zur Beschreibung von asymptotischem Verhalten
  • O(1), O(n), O(n^2)
28
Q

Was ist O(1)?

4

A
  • Aufwand immer konstant
  • verändert sich nicht mit Eingabemenge
  • immer gleiche Zeit und gleichen Speicherverbrauch
29
Q

Was ist O(n)?

4

A
  • Aufwand steigt linear mit Eingabemente
  • verdoppelte Eingabemenge = verdoppelter Aufwand
30
Q

Was ist O(n^2)?

4

A
  • Aufwand wächst quadratisch zur Eingabemenge
  • zB zwei vernestete For-Schleifen (bei drei For-Schleifen: O(n^3)
31
Q

Welche Laufzeiten von Algorithmen gibt es?

4

A
  • Doppelt logarithmisch
  • logarithmisch
  • linear
  • quasi-linear
  • quadratisch
  • exponentiell
32
Q

log(log(n))

4

A

doppelt logarithmisch

33
Q

log(n)

4

A

logarithmisch

34
Q

n

4

A

linear

35
Q

n x log(n)

4

A

quasi-linear

36
Q

n ^ 2

4

A

quadratisch

37
Q

2 ^ n

4

A

exponentiell

38
Q

Was ist P und NP?

4

A
  • Komplexitätsklassen
39
Q

Was ist Determinismus in der Informatik?

4

A
  • wenn Wirkung und Reihenfolge der Einzelschritte eindeutig festgelegt wird
40
Q

Was ist nominelle Zeit?

4

A
  • theoretische Laufzeit eines Algorithmus unter idealisierten Bedingungen
  • abstrakte, modellierte Zeit für Lösung eines Problems
41
Q

Gib ein Beispiel für “nominelle Zeit”?

4

A

Ein Algorithmus hat nominell eine Laufzeit von O(n^2), auch wenn er in der Praxis aufgrund von Optimierungen schneller ausgeführt werden kann

42
Q

Definiere P

4

A
  • Polynominale Zeitkomplexität
  • Laufzeit: O(n^k)
  • Klasse der Probleme für die Computer schnell korrekte Lösung berechnen kann
43
Q

Definiere NP

4

A
  • Nichtdeterministische polynominale Zeitkomplexität
  • zur Problemlösung: nichtdeterministischen Algorithmus
  • wie Zahlenschloss: korrekte Lösung evtl schwer findbar; Richtige Lösung schnell überprüfbar
44
Q

Was ist die Turingmaschine?

4

A
  • theoretisches Konzept
  • Band mit Feldern in denen Eingangsdaten abgelegt sind
  • wenn Funktion durch TM berechenbar ist: “Turing-berechenbar” / “berechenbar
  • vor Allem für Entscheidungsprobleme (ja/nein)
45
Q

Aus was besteht die Turingmaschine?

4

A
  • Unendliches Band (Speicher, kann beschrieben werden)
  • Lesekopf (liest / schreibt Symbole auf Band)
  • Zustandstabelle (Regeln bestimmen was Maschine abhängig von Zustand und gelesenem Symbol tun soll)
46
Q

Was hat die Turingmaschine mit einem Algorithmus zu tun?

4

A
  • theoretische Darstellung eines Algorithmus
  • Wenn Problem mit Turingmaschine lösbar ist = dann theoretisch auch mit einem Computer(-algorithmus)

Algorithmen, Datenstrukturen und Programmiersprachen (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions