ALG20 TOK 8.01.2022

[MagicMike]

Hallo zusammen,
in der gestrigen Tok waren folgende Aufgaben gegeben an die ich mich noch erinnern kann.

Teilaufgaben:

- Definieren sie das Mengenproblem
- Was ist Ziel des Flussproblems
- Welche zwei Informationen benötigt man pro Kante
- Was bedeutet O(n)
- Erklären Sie den unterschied zwischen einen Baum und einen Graphen
- Dann war was über Skip-Listen gefragt


Komplexaufgabe 1 ( Thema Sortieralgorithmus)
- Ziel vom Sortieralgorithmus nennen.
- Was bedeutet "stabiles sortieren"
- Gierigen Algorithmus erklären
- Selectionsort erklären
- Es war eine Tabelle gegeben die man anhand vom Selectionsort ausfüllen sollte.
- Schreibzugriffe angeben
- Vergleiche angeben


Komplexaufgabe 2 ( Thema: Floyd Warshall)
- habe ich nicht gemacht

Komplexaufgabe 3 ( Thema: Greedy Algorithmen)
- Das Rundreise problem erklären
- Wie oft sollen die Knoten eines Netzes besucht werden
- Welche von mehreren Rundreisen ist die beste
- Was bedeutet Backtracking
- Wann ist Backtracking keine gute Lösung
- Es war ein Greedy Algorithmus gegeben und man sollte erklären welche Werte im Feld(u.v) stehen
- Es war ein Graph gegeben ( wie in der Online Übung). Man sollte den Algorithmus an den Graphen anwenden.

Das waren die Fragen an die ich mich noch erinnern konnte.

[gemuesetasse]

Hallo,
hatte ALG auch schon geschrieben und vergessen, meinen Mitschrieb hochzuladen. Hänge ihn hier einfach mal dran.

A1
Definition einer Liste
A2
Definition Baum
Was für eine Beziehung bildet ein Baum ab 1:1, 1:m oder n:m
Welche Eigenschaften hat der Wurzelknoten
A3
Terminierend
Worauf kann es ankommen, ob ein Algorithmus terminierend ist
A4
Wie wird Effizienz eines Algorithmus bewertet
Welche Faktoren kann es für die Laufzeit eines Algorithmus geben
Laufzeit wird üblicherweise nicht in Sekunden angegeben, sondern in …?

K1
1. Array definieren
2. Wie und Wo fügt man Element in Array ein
3. Wie geht man vor, wenn man Element entfernen möchte
4. Algorithmus zum löschen gegeben, wie sieht Array nach löschen aus
5. Wie sucht man nach einem bestimmten Element im Array
6. Was ist der Unterschied zwischen Index und Wert(Schlüssel)

K2
1. Was ist ein Heap
2. Was ist ein binärer Heap
3. Ist gegebener Graph Max-Heap oder Min-Heap
4. Wie fügt man Element in Heap ein???
5. Wie kann man Dijkstra mit Heap verbessern
6. ???

K3
1. Was ist Inversionszahl und wie berechnet sie sich
2. Was sagt Inversionszahl über Laufzeit von Sortieralgorithmen aus
3. Inversionszahl berechnen von Zahlenfolge
4. Ist es schneller, ein Array umzusortieren oder ein neues sortiertes Array zu erstellen? Warum?
5. Insertionsort beschreiben
6. Insertionsort durchführen (Tabelle gegeben, 4 Zahlen zu sortieren). Pro Schritt i und k angeben und Anzahl Schreibzugriffe und Vergleiche

[Sam-Bra]

war am 05.03.2022 noch ziemlich die gleiche Klausur

[Nik28]

Hier die Fragen vom 01.04.2023

Detailfragen
- Was ist ein Graph?
- Was ist ein Baum?
- Was ist ein binärer Baum?
- Halteproblem erläutern
- Was ist eine doppelt verkettete Liste?
- Welche Informationen hat ein Element einer doppelt verketteten Liste?
- Was muss beim Entfernen eines Elementes aus einer doppelt verketteten Liste beachtet werden?
- Was ist ein randomisierter Algorithmus?

Komplex 1 - Binärer Suchbaum
- Was ist ein binärer Suchbaum?
- Wieso heisst er Suchbaum?
- Es waren mehrere Bäume gegeben und man musste sagen, welche davon binärer Suchbäume sind
- Es war ein Algorithmus zum Suchen in einem Baum gegeben sowie ein Suchbaum. Man sollte einen Wert im Baum suchen und dabei angeben wie viele Schlüssel-Vergleiche dazu notwendig sind
-.. irgendeiner Frage zu Laufzeit von Suchen in einem Suchbaum
- Hinzufügen eines Elementes zu einem binären Suchbaum mit eigenen Worten erklären

Komplex 2 - Verkettete Listen
- Wieso ist bei einer verketteten Liste nicht der direkte Zugriff auf ein Element möglich?
- Wofür ist das Blindelement?
- Laufzeit der Suche in einer sortierten und unsortierten verketteten Liste miteinander vergleichen
- Es war ein Algorithmus zum Einfügen in eine sortierte verkettete Liste gegeben und man sollte sagen was der Befehl "allokiere" darin bewirkt
- Mit eigenen Worten den Ablauf von Suchen in einer verketteten Liste beschreiben
- Was ist beim Löschen eines Elements zu beachten?


Komplex 3 - Spannbäume und Rundreiseproblem
- Wie oft sollen die einzelnen Knoten beim Rundreiseproblem besucht werden?
- Spannbaum definieren
- Minimaler Spannbaum definieren
- Welche Bedingungen gibt es damit ein Spannbaum zur Lösung des Rundreiseproblems genutzt werden kann?
- Was sagen die kosten eines minimalen Spannbaums bzgl. der Gesamtkosten der kürzesten Rundreise aus?
- Es war der Algorithmus Rundreise-Approximation gegeben. Was bewirkt der Aufruf des Prim-Algorithmus darin?
- Welche Fehlergarantie hat die Rundreise-Approximation?
- Tiefensuche mit eigenen Worten erklären

[Tom03]

Guten Abend, Inhalte der TOK 01.2024:

Allgemeine Fragen:
-Definition Mengenproblem
-Laufzeitvergleich O(n) und O(log n)
-Was sind Skiplisten
-Bei welchem Element startet Suche bei einer Skipliste
-Wie sollte Skipliste aufgebaut sein
-Unterschied Graph und Baum

Komplexaufgaben:
1. Thema Selection-Sort
-Sortierproblem definieren
-Was bringt Sortierung?
-Ablauf des Algos in eigenen Worten
-Tabelle zum Ablauf des Algos ausfüllen
-Wie viele Vergleiche?
-Wie viele Schreiboperationen?


2. Thema Ford-Fulkerson
-nicht gemacht

3. Thema Rundreiseproblem
-Wie oft sollte jeder Knoten besucht werden?
-Auswahl der besten Rundreise
-Definition Backtracking
-warum Backtracking schlecht?
-Es war ein Algo gegeben, bei dem man angeben sollte, was er macht
-Algo anwenden auf Graphen
-bestimmte Variablen des Algos berechnen

[jae_3101]

Hallo zusammen,

anbei die Klausur vom 04.05.24.

Allgemein
T1.1: Was ist eine verkette Liste? 4P
T1.2: Was ist der Unterschied zwischen einer verketteten und doppelt verketteten Liste? 2P
T1.3: Was ist laut Definition der Anker einer verketteten Liste? 2P
T1.4: Nenne den Vorteil einer verketteten Liste gegenüber einem Feld. 4P
T2: Was ist der Unterschied zwischen eine Zyklus und einer Schleife? 8P
T3: Was ist der Unterschied zwischen determiniert und deterministisch? 8P
T4.1: Was ist eine Adjazenzmatrix? Welche Inhalte hat sie? 4P
T4.2: Wozu wird eine Adjazenzmatrix verwendet? 2P
T4.3: Wie kann man eine Adjazenzmatrix abspeichern? 2P
T4.4: Welche Besonderheit zeigt die Adjazenzmatrix eines ungerichteten Graphen? 4P

K1: Binäre Suche
T1.1: Was ist ein Feld? 6P
T1.2: Wie greift man in einem Feld auf ein einzelnes Element zu? 2P
T1.3: Warum funktioniert die Binäre Suche nur in einem Feld und nicht in einer verketteten Liste? 4P
<Hier war der Algorithmus der Binären Suche gegeben. (siehe Algorithmus 4.1 „Binäre Suche im Feld“)>
T2.1: Erklären sie das Prinzip der Binären Suche in Worten. 8P
T2.2: Ist dieser Algorithmus deterministisch? 2P
T2.3: Ist dies ein terminierender Algorithmus? 2P
T2.4: Welche Laufzeit hat dieser Algorithmus im Worst-Case? 2P
T2.5: Vergleiche die Laufzeit mit der Laufzeit einer Suche von vorne nach hinten. 4P
T2.6: Aus der Formel für die Berechnung der Mitte kann sich auch ein Wert wie bspw. 4,5 ergeben. Dies ist kein gültiger Indexwert. Was passiert dann? 2P
T2.7: Suche 14 in: 1, 4, 10, 14, 15, 16, 21, 25, 34 und gib für jede Iteration den Wert von Mitte an. 8P

K2: Mergesort
T1: Erkläre das „teile und herrsche“ Prinzip. 6P
T2: Was ist laut Definition ein rekursiver Algorithmus? 4P
T3: Was sind die zwei Bestandteile eines rekursiven Algorithmus? 8P
<Hier war der Algorithmus des Mergesorts und Mischen gegeben. (siehe Algorithmus 7.1 „Sortieren durch Mischen“ und Algorithmus 7.2 „Verbinden von rekursiv errechneten Lösungen beim Mergesort“)>
T4: Wie wendet Mergesort das Prinzip „teile und herrsche“ konkret auf das Sortieren an? 10P
T5: Wende Mergesort auf 5,3,2 an. Gib an, welche Funktion in welcher Reihenfolge mit welchen Parametern aufgerufen wird. Zuerst wird Mergesort(1,3) aufgerufen. Und dann…? Gib alle Funktionen an, die aufgerufen werden, bis das Feld sortiert wird. 12P

K3: Kürzester Weg
---