ALG20 TOK 8.01.2022

Algorithmus, Baumdurchlauf, Compiler, Interpreter...; Cobol, Pascal, C/C++, Java & Co.
Antworten
MagicMike
Mitglied
Mitglied
Beiträge: 10
Registriert: 29.10.20 11:12

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
Neues Mitglied
Neues Mitglied
Beiträge: 9
Registriert: 07.06.21 19:37

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
Neues Mitglied
Neues Mitglied
Beiträge: 2
Registriert: 25.11.21 17:35

war am 05.03.2022 noch ziemlich die gleiche Klausur
Nik28
Neues Mitglied
Neues Mitglied
Beiträge: 4
Registriert: 16.01.23 21:49

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
Neues Mitglied
Neues Mitglied
Beiträge: 7
Registriert: 22.09.23 19:08

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
Antworten