Bachelorprüfung Praktische Informatik

Hier die Fragen:

Datenstrukturen:

Was sind die vier Schritte, mit denen eine Laufzeit abstrahiert wird?

(Keine Unterscheidung der Art der Elementaroperationen, Aufteilung der Menge aller Eingaben in Komplexitätsklassen (hier wollte er auch erwähnt haben, dass nicht nur die Kardinalität der Eingabe eine Art der Bildung der Komplexitätsklasse ist, sondern z.B. auch der Umfang des Ergebnisses), Untersuchung jeder Komplexitätsklasse auf Best, Worst und Average Case, Weglassen von multiplikativen und additiven Konstanten -> O-Notation)

Warum macht man vorwiegend worst case Analysen und nicht Durchschnittsanalysen?

(Durchschnittsanalysen sind wg. der Berücksichtigung der Wahrscheinlichkeiten schwieriger, obere Schranken für die Komplexität sind interessant, Abschätzung des maximalen Aufwands an Speicher und Rechenleistung)

Schreiben Sie die formale Definition der O-Notation auf!

(Hier hat er mich erwischt ;) Die Definition steht unter Def. 1.6 in KE1)

Welche verschiedenen Arten von Sortierverfahren kennen Sie?

(Einfache Sortierverfahren: Selection/Insert Sort, Divide and Conquer-Verfahren: MergeSort, QuickSort, Heap- und Baumsortieren, Sortieren für einschränkte Eingabemengen: Radixsort, Bucketsort)

Was ist ein allgemeines Sortierverfahren?

(Ein Sortierverfahren, bei denen die Eingabedaten bis auf die Vergleichbarkeit keine Beschränkungen haben. Bei beschränkten Eingabedaten können Algorithmen mit schnellerer Laufzeit als O(n log n) realisiert werden, z.B. Bucket-/Radixsort)

Erläutern Sie das Divide-and-Conquer-Verfahren!

(Divide, Conquer, Mergeschritte erklärt)

Wie funktioniert das beim MergeSort?

(MergeSort als DAC-Algorithmus erklärt)

Welche Komplexität hat der Merge-Schritt beim MergeSort?

Was ist ein Graph?

(Erklärt, dass ein Graph aus Knoten, die Objekte repräsentieren, besteht und Kanten die Beziehungen zwischen Knoten erklären. Erklärt, was gerichtete und ungerichtete Kanten sind)

Schreiben Sie die formale Definition eines Graphen auf!

G = <V,E>
E = { (v,w) | v,w Element von V } oder einfacher: E = V x V

Welche Speicherdarstellungen für einen Graphen kennen Sie?

(Erklärt, die Adjazenzmatrix und Adjazenzlisten aussehen)

Wenn Sie sich die Struktur der Adjazenzliste vor Augen halten, welche andere Datenstruktur sieht ähnlich aus?

(Die Behälter für offenes Hashing)

Betriebssysteme und Rechnernetze:

Warum sollte man auf die Idee kommen, zwei Prozesse miteinander zu synchronisieren?

(Vermeiden des konkurrierenden Zugriffs auf Betriebsmittel (hier wollte er mutual exclusion hören), Parallele Bearbeitung eines Problems)

Welche Synchronisationsmechanismen kennen Sie und wie funktionieren Sie?

(Habe Synchronisationsvariablen und Semaphoren mit Vor- und Nachteilen erklärt)

Wie funktioniert ein Token-Ring?

(Das Konzept von Token, Konnektor und deren Durchläufe durch den Ring erklärt. Die Erklärung der Fehlerbehandlung (Monitorstation) war nicht verlangt)
 

Herr Güting ist ein sehr angenehmer und liebenswürdiger Mensch, fast ein wenig drollig. Auf jeden Fall hat er eine sehr ruhige und entspannte Art und hetzt einen nicht während der Prüfung. Wenn man nicht weiß, worauf er hinauswill, sollte man unbedingt nachfragen; er hilft einem dann so gut es geht, auf die richtige Spur zu kommen. Die Benotung ist sehr fair (und eigentlich besser, als ich es erwartet hätte). Als Prüfer in jedem Fall zu empfehlen!