Brainscape's Knowledge GenomeTM

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


See full index

Informatik Abitur > Algorithmik > Flashcards

Algorithmik Flashcards

1
Q

Welche Arten von Algorithmen gibt es?

A
  • Such- und
  • Sortieralgorithmen
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Welche Arten von Vorgehensweisen gibt es bei Algorithmen?

A
  • rekursiv
  • iterativ
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was ist ein iterativer Algorithmus?

A
  • läuft nur schrittweise ab
  • basiert auf klassischen Schleifen und Vertweigungen
  • läuft linear ab
  • so lange wiederholt, bis zu Lösung des Problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist ein rekursiver Algorithmus?

A
  • ruft sich selbst mit neuen Parametern wieder auf
  • Problem wird in einzelne Teile aufgeteilt
    • Arbeit nur in einzelnen Schritten (Arbeitsteilung)
  • Am Ende eird der jeweilige Teil an die nächst höhere Funktion zurückgegeben
    • bis die Startfunktion wieder erreicht wurde
  • Lösung der Einzelteile ergibt die gesamte Lösung
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist der Rekursionsanker?

A

Verhindert eine Endlosschleife, ist ein Abbruch Statement und beendet die Rekursion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wann wird Rekursion benutzt?

A
  • Wenn ein Problem in mehrere Einzelteile zerteilbar ist und sich auf einen einfachen Fall reduzieren lässt
  • oft für die Suche in nicht-linearen Datenstrukturen (Bäume, Graphen, …)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Wie überprüft man rekursiv ein Palindrom?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Welchem (umgangssprachlichen) Prinzip folgt die Rekursion?

A

Teilen und Herrschen

Das eigentliche Problem wird so lange rekursiv in kleinere und einfachere Teilprobleme zerlegt, bis es beherrschbar wird. Aus den Teillösung wird dann am Ende eine Lösung für das Gesamtproblem rekonstruiert.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist Backtracking?

A
  • Suchalgorithmus
  • Wenn erkannt wird, das eine Teillösung nicht zum Ziel führt, werden die letzten Schritte zurüclgenommen und es werden alternative Wege ausprobiert
  • Es werden so lange verschiedeen Wege probiert, bis der Algorithmus zur Lösung kommt oder alle Möglichkeiten ausgeschöpft sind
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Welchem Prinzip folgt das Backtracking?

A

trial and error

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was ist über die Dauer des Backtrackings zu sagen?

A

Ist durch das zufällige Vorgehen nur schwer einschätzbar.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wie stellt man in einem Flussdiagramm / PAP eine Aktion/Ausführung dar?

A

Mit einem Rechteck

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Wie stellt man in einem Flussdiagramm / PAP eine Verzweigung dar?

A

Mit einer Raute

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Wie stellt man in einem Flussdiagramm / PAP eine Grenzstelle dar?

A

Mit einem Rechteck mit runden Ecken

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Wie stellt man in einem Flussdiagramm / PAP einen Input/Output dar?

A

Mit einem Parallelogramm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wie stellt man in einem Struktogramm eine Anweisung dar?

A

Mit einem Rechteck

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Wie stellt man in einem Struktogramm eine Verzweigung dar?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Wie stellt man in einem Struktogramm eine Mehrfachauswahl dar?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Wie stellt man in einem Struktogramm eine While-Schleife dar?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Wie stellt man in einem Struktogramm eine Do-While-Schleife dar?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Wie stellt man in einem Struktogramm eine For-Schleife dar?

A
22
Q

Wie stellt man in einem Struktogramm einen Methodenaufruf dar?

A
23
Q

Was muss man unbedingt implementieren, damit man einen binären Suchbaum erstellen kann?

A

In der Klasse der Objekte, die gespeichert werden sollen, muss comparableContent implementiert werden

public class kName implements comparableContent {

[…]

}

24
Q

Wann kann man beim Djkstra Algorithmus sicher sein, dass kein kürzere Weg zu einen Knoten G vorhanden ist?

A

Wenn dieser Knoten G aus der Warteschlange gelöscht wurde.

25
Q

Wie läuft der Djkstra Algorithmus ab?

A
  1. Falls die Kantengewichte plus das eigene summierte Kantengewicht kleiner zu einem bestimmten Knoten, als das bereits vorhanden angegebene ist, wird es zu dem Knoten mit “Kantengewicht plus das eigene summierte Kantengewicht” aktualisiert
  2. Die Nachbarknoten werden aufsteigend sortiert in die Warteschlange eingefügt
  3. Ersten Knoten aus der Wartschlange nehmen und Schritt 1 wiederholen, bis die Warteschlange leer ist
26
Q

Erkläre die Methodik des Bubble Sorts

A
  1. Es werden zwei Zahlen miteinander verglichen, wenn die hintere kleiner ist, wenn die beiden Zahlen ausgtauscht, wenn nicht, passiert nichts
  2. es wird ein weiter gegangen und Schrit 1 wiederholt, bis man am Ende der Liste angekommen ist
27
Q

Nenne Best, Average und Worst Case des Bubblesortst

A

Best Case: n

Average Case: n2

Worst Case: n2

28
Q

Nenne Best, Average und Worst Case des Selectionsorts

A

Best Case: n2

Average Case: n2

Worst Case: n2

29
Q

Erkläre die Methodik des Selectionsorts

A
  1. Man sucht die kleinste Zahl aus der Datenmenge und tauscht sie mit der Zahl, an der ersten Stelle
  2. Schritt 1 wiederholt man mit dem Rest der Liste
30
Q

Nenne Best, Average und Worst Case des Insertionsort

A

Best Case: n

Average Case: n2

Worst Case: n2

31
Q

Erkläre die Methodik des Insertionsorts

A

Man nimmt einzeln die Elemente aus der Liste und verlegt sie nach vorne: So lange sie größer sind, als der vorderste Wert und die darauf folgenden Werte, geht man einen Schritt weiter, bis man den Plaz gefunden hat, an dem der Wert eingefügt werden soll.

32
Q

Erkläre die Methodik des Quicksorts

A
33
Q

Nenne Best, Average und Worst Case des Quicksorts

A

Best Case: n*log(n)

Average Case: n*log(n)

Worst Case: n2

34
Q

Erkläre die Methodik des Quicksorts

A
  1. Man nimmt sich ein Pivot-Element
  2. Man packt alle kleineren Werte auf die linke Seite des P-Elements und alle größeren auf die rechte
  3. mit den Teillisten (l und r) fängt man wieder bei Schritt 1 an
35
Q

Nenne Best, Average und Worst Case der linearen Suche

A

Best: 1

Average: n/2

Worst: n

36
Q

Erkläre die Methodik der binären Suche

A
  1. Man vergleicht den Wert mit dem Wert aus der Mitte der Liste
  2. Wenn eigener Wert größer, macht man mit der Mitte der rechten Liste weiter, sonst links
  3. man wiederholt Schritt 2
37
Q

Was ist Hashing?

A

Ein Prinzip zum Speichern von Daten, durch eine Formel wird entschieden, an welche Stelle ein Wert in einem Array gespeichert werden soll.

38
Q

Was sind Vorteile und Nachteile des Hashing?

A

Vorteile

  • prinzipiell ​schnelle Suche
  • möglicherweise hohe Suchaufwand, bei Kollisionen
    • schlechte Hshingformel

Nachteile

  • meist 20-30% mehr Speicher nötig
  • möglicherweise hohe Speicheraufwand, bei Kollisionen
    • schlechte Hshingformel
39
Q

Was macht eine gute Hashfunktion aus?

A

Am Ende modulo n wobei n mindestens die Anzahl der benötigten Speicherstellen beträgt

(zweite Funktion beim doppelten Hashing ausgenommen)

40
Q

Was ist das geschlossene Hashing mit offener Adressierung?

A

Bei einer Kollision wird zwangsweise ein neuer Speicherplatz für den Wert gesucht

41
Q

Erläutere das linerare Sondieren und wieso es schlecht ist

A

Bei einer Kollision, wird der Wert in das nächstmögliche Feld geschrieben

  • kann zu hohen (überdurchschnittlichen) Suchzeiten führen
  • es bilden sich schnell Cluster
42
Q

Erläutere das quadratische Sondierenn und ihre Nachteile

A

Ein quadratische Funktion berechnet bei einer Kollision eine neue Speicherzelle

  • führt bei einer schlechten Hashfunktion auch zu langen Suchezeiten
  • es bilden sog. sekundäre cluster
43
Q

Was sind primäre und sekundäre Cluster

A
  • Primäre bilden sich eng um den Hashwert und bei ihnen gilt, je größer sie werden, desto extrem wahrscheinlicher ist die weitere Clusterbildung
  • Sekundäre Cluster, dessen Werte entfernen sich immer weiter (quadratisch) von dem Hashwert weg und sind deswegen akzeptabler, als primäre Cluster, da keine wirklich großen Cluster enstehen
44
Q

Erläutere das Sondieren durch doppeltes Hashen und dessen Vorteile

A

Man hasht pro Kollision noch einmal, undzwar beim zweiten mal mit einer neuen Hashfunktion

  • kaum Clusterbildung
45
Q

Was ist das offen Hashing mit geschlossener Sondierung?

A

Bei eine Kollision wird ein Array mit den dort hingehörenden Werten erstellt -> 2D-Array

46
Q

Nenne Vor- und Nachteile des Sondierens durch Verkettung

A
  • gute ertwartbare Suchzeit
  • Listenoperationen sind langsam
47
Q

Erkläre das Prinzip der Nebenläufigkeit

A
  • Mehrere Aufgaben werden parallel ausgeführt
48
Q

Was ist ein Thread?

A

eine Reihe von Aufgaben, die parallel zu anderen Aufträgen abgearbeitet werden

49
Q

Was ist eine echte Nebenläufigkeit?

A
  • Zwei oder mehrere Aufträge können unabhängig voneinander bearbeitet werden -> Mehrkernprozessoren
  • oft genutzt bei Netzwerken mehrerer Rechner
50
Q

Was ist die scheinbare Nebenläufigkeit?

A

Nach einer Zeit wird der eine Prozess schlafen gelegt und ein anderer fortgeführt

Es sieht so aus, als wenn die Prozesse nebenher laufen, obwohl in Realität in Bruchteilen einer Sekunde zwischen den einzelnen Threads gewechselt wird, sodass kurz an einem Auftrag gearbeitet wird und dann zum nächsten gegangen wird.

Informatik Abitur (9 decks)

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