Computer Science, 2016-04-06

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Elke Pulvermüller
Date: 
Wed, 2016-04-06

Formalia

Modulprüfung: Info A, Software Engineering
Fachsemester: 7
Wiederholungsprüfung? nein
Note: 2.3
Bereiche nach Zeit: ungefähr 10/15

Vorbereitung

Info A: Skript, Vorlesungsvideos, Karteikarten
SWE: Skript, YouTube Videos (für bestimmte Abläufe)

Wie lauteten die Fragen im einzelnen?

Info A

Da doch häufig die gleichen Fragen gestellt werden, nehme ich es mir heute mal raus simple Antworten nur in Stichpunkten zu verfassen und verweise da auf die zahlreichen Protokolle vor mir. Neue Punkte oder Stellen an denen ich Abzüge erhalten habe schreibe ich natürlich aus.

Rekursion was ist denn das?

- Methoden dürfen in der Deklaration ihres Rumpfes den eigenen Namen verwenden (rekursiver Aufruf)
- Parameter werden dabei so verändert, dass Problemgröße schrumpft
- nach mehrmaligem Aufrufen ist das Problem quasi nicht mehr existent
- Programm bricht ab (Rekursions Anker)

Wie wird das in den Türmen von Hanoi benutzt?

- 3 Plätze —> Start, Zwischen,Ziel)
- N Scheiben in aufsteigender Größe
- Ziel: Alle Scheiben von Start nach Ziel
- Zwei Regeln: Immer nur eine Scheibe zur Zeit verlegen & keine größere Scheibe auf einer kleineren zum liegen kommen lassen.
- Lösung:
1. rekursiv n-1 Scheiben von Start über Ziel nach Zwischen legen
2. n-te Scheibe auf Ziel legen
3. wieder rekursiv n-1 Scheiben von Zwischen über Start nach Ziel bringen

Und was ist die Laufzeit bzw Rekursionsgleichung?

Schritte 1 und 3, also der rekursive Teil des Verlegens von n-1 Scheiben, gehen in jeweils immer n-1 Schritten und das Verlegen der n-tn Scheibe in konstanter Zeit. Das resultiert in einer exponentiellen Laufzeit.

Schreiben Sie das, was Sie gesagt haben einmal schön auf.

Ich etwas verwirrt schreibe erst einmal 2*(n-1)+1.
Vornberger: Ich möchte ein f(n) da irgendwo sehen.
Also ich noch mal fix ein f(n) = 2*f(n-1)+1 dazu gedichtet.
Vornberger: Also was ist das jetzt?
Ich wusste ja nur irgendwie, dass es in exponentieller Laufzeit mit 2^n-1 enden sollte, konnte aber nicht anhand der Gleichnung vor mir erklären warum. Also musste ich eine Tabelle zeichnen und Werte einsetzen. Beim Einsetzen habe ich mich leider zweimal verrechnet und bin deshalb nicht mehr auf die 2^n-1 gekommen.

Rekursion wird ja noch bei Sortieralgorithmen verwendet. Erklären sie mal Quicksort.

- n Daten unsortiert in einem Array
- Privotelement ungefähr in der Mitte
- Alle Elemente < Pivotelement in die vordere Hälfte tauschen
- alle die > Pivot sind in die hintere Hälfte packen.
- rekursive Aufrufe vorne und hinten, fertig.

Und die Laufzeit?

n*log(n)

Ist das immer so?

Nein, nur für den Best und Average Case. Im Worst Case O(n^2).

Wie kommt der zustande?

- Pivot schlecht gewählt, es ist immer größtes oder kleines Element
- man hat erst Aufruf mit n-1, dann n-2 und so weiter also exponentiell.

Nun zu ungerichteten und auch noch gewichteten Graphen. Was gibt es denn da?

Matching, Mimimalen Spannbaum, Chinese Postman
(Vornberger unterbricht)

Sagen Sie mal was zum Spanning Tree

Gesucht: Teilmenge von Kanten die alle Knoten möglichst billig miteinander verbindet
Vorgehen:
- Wald aus n einzelnen Knoten
- Heap mit allen gewichteten Kanten (billigste immer oben drin)
- immer eine Kante rausnehmen und gucken ob man zwei Knoten verbinden kann oder ob ein Kreis entsteht. Dann wäre eine Kante zu viel.
- dazu führt man Variable chef ein
- erst jeder Knoten sein eigener chef, wenn zusammengefügt bekommt der eine Knoten den chef vom anderen zugewiesen
- es können lange Ketten entstehen, dann kann man Technik des Path Halving benutzen:
- man betrachtet immer Großvater und halbiert so die Kette

Sie haben eben noch den Chinese Postman genannt. Wie funktioniert der?

Gesucht: Billigste Kantenrundreise, die alle Kanten einmal besucht.
Vorgehen:
Entweder man hat einen Eulergraph. Das bedeutet jeder Knoten hat einen geraden Grad. Damit kann man dann einfach durchlaufen und sicher sein, dass man von jedem Knoten mit einer noch unbesuchten Kante wieder wegkommt.
Wenn man keinen Eulergraph hat:
Man möchte wieder einen Eulergraph draus machen, deshalb:
- betrachte Knoten mit ungeradem Grad
- suche zwischen ihnen mit Floyd die kürzesten Wege (also All Pairs Shortest Path)
- danach Minimal Cost Matching und
- bei diesen dann Kanten verdoppeln bis wieder Eulergraph

Oke, was ist denn ein Heap?

-Def. (Binärer Baum, vollständig(+Bedeutung von Vollständigkeit), hat Schlüssel(vater<=söhne))

Was kann der Heap besonders gut?

- heapempty also sagen, ob er leer ist in konstanter Zeit
- get_min also das Minimum ausgeben auch in konstanter Zeit
- beide Methoden müssen nur einmal in die Wurzel greifen
- insert und delete_min haben eine Laufzeit von log(n) weil man noch tauschen muss um Vater-Sohn Beziehnungen wieder herstellen zu können

Wie macht man das mit dem Einfügen und Löschen?

Beim Löschen löscht man die Wurzel, dann muss der kleineste Knoten hochrutschen. Beim Einfügen kommt das Element hinten dran und muss auch an die richtige Stelle rutschen.

Wie würden Sie mit einem Heap sortieren?

Ich nehme ein unsortiertes Array
(Vornberger unterbricht)

Warum ein Array?

Das bietet sich an weil man durch die Vollständigkeit des Heaps weiß, wo der Vater und die Söhne eines Knotens liegen.

Wo liegen denn die Söhne eines Knotens?

Der Linke Sohn bei 2i+2, der rechte bei 2i+1.

Oke und wie sortieren Sie jetzt?

Man nimmt immer das kleinste Element raus und schreibt es ganz hinten ins Array. Dafür kommt dann das letzte Blatt vom Heap in die Wurzel und wird so lange mit seinen kleinsten Söhnen getauscht bis die Schlüsselbeziehungen wieder stimmen.

Wenn der Heap jetzt aussieht wie Kraut und Rüben, also alles da so unsortiert drin liegt. Wie stellen Sie den Heap wieder her?

Ich hab nicht ganz gerafft, wieso ein Heap überhaupt so aussehen kann und hab deshalb nur geantwortet: Naja man tauscht wieder jeden Vater mit seinem kleinsten Sohn bis alles wieder in Ordnung ist.
Vornberger: Ja aber wo fangen Sie denn damit an?
Unten.
Vornberger: Und wieso?
Naja weil man von oben evtl.noch öfter tauschen müsste wenn der kleinste Sohn ganz unten steht.

Worauf können Sie sich denn verlassen?

(Ich hatte keine Ahnung was er hören wollte) Jeder Vater ist kleiner als sein Sohn.
Das hat ihm noch nicht ganz gereicht aber ich wusste auch nicht weiter, also blieb es dabei.
Später habe ich noch mal gefragt was er meinte und er wollte hören, dass wenn man ganz hinten anfängt und ebenenweise hoch geht, sich immer darauf verlassen kann, dass alle Söhne größer sind als der jeweilige Vater. Also hat vermutlich das Vorgehen gefehlt oder so, keine Ahnung.

Software Engineering

Hier ging es richtig chaotisch zur Sache. Ich habe die meisten ihrer Fragen leider nicht verstanden bzw. wusste nicht was sie meinte. Dem Rat der Info B Protokollen folgend habe ich dann einfach immer alles gesagt, was mir eingefallen ist. Meistens hat sie dann einfach genickt und irgendwas von dem Gesagten wieder aufgegriffen. Ich erinnere mich von meinen Redeschwällen deshalb aber leider meistens nur an die Dinge, die sie dann wieder aufgegriffen hat.

Was sind Modulkriterien, die man überprüfen sollte?

(Ich bin mir nicht ganz sicher ob sie "überprüfen" gesagt hat, da kam zumindest noch was nach "Was sind Modulkriterien", das meines Erachtens ein bisschen komisch klang. Als ich dann trotzdem einfach die Kriterien aufgezählt habe, war sie relativ zufrieden)
Sie sollten eine vernünftige Relation an Tiefen- und Breitenstruktur haben, eine möglichst enge Bindung vorweisen und möglichst wenig Kopplung zu anderen Modulen haben.
Außerdem sind die Modulgröße und die Modulanzahl zueinander gegenläuftige Größen.

Können Sie das etwas näher erläutern?

(Es gibt dafür eine Grafik, die die Gegenläufigkeit visualisiert. Die habe ich ihr aufgemalt, konnte mich aber dann aber leider doch nicht so 100% an die komplette Beschriftung erinnern.)

Wie würden Sie denn die Modulgröße und Anzahl jetzt in Relation setzen?

??? (Ich habe das so interpretiert, dass sie es etwas genauer haben wollte)
Naja, Module sollten möglichst immer nur eine Prozedur exportieren, deshalb auch relativ klein bleiben. Demnach steigt dann aber auch deren Anzahl.

Was ist denn wünschenswert?

??? Ich zeige auf die Grafik und markiere den Punkt, wo zwei gegenläufige Kurven ihren Schnittpunkt haben und am tiefsten sind und sage dass sowohl die Anzahl als auch die Modulgröße möglichst klein bleiben sollten (das war eher geraten). Es ging aber zumindest weiter.

Oke, kommen wir zum Konfigurationsmanagement. Wie funktioniert das?

(Ich habe daraus interpretiert, das sie hören wollte, wofür man das braucht und wie es grob funktioniert, weil Konfigurationsmanagement eben doch eines von sieben Kapiteln der ganzen Vorlesung war, also ziemlich viel dazu im Skipt steht)
Das Konfigurationsmanagement wird immer gebraucht wenn mehrere Menschen an einer Sache/Objekt arbeiten. Damit immer alle auf die aktuellste Version zugreifen können, keine Arbeit doppelt oder anders machen, man weiterhin die gleiche Zielverfolgung hat und Fehler schneller beseitigen kann benutzt man eben Werkzeuge wie SVN und GIT, die die Zusammenarbeit im Team erleichtern sollen.

Ja, und wie sieht das dann aus?

??? Wieder keine Ahnung was sie hören wollte. Diesmal hab ich aber nachgefragt. Meinen Sie jetzt welche Strukturen es gibt um etwas in ein Repository zu schieben (angefangen die Workflows mit integration manager zu skizzieren) oder nach welchem Prinzip Dateien geändert werden also lock-modify-unlock und so? Oder eher wie man innerhalb von SVN und GIT arbeitet?

Ja, weiter zum Repository und was Sie haben es eben Workflow genannt haben.

Das hat nur medium geholfen aber ich dachte mir es ist sinnvoll von SVN und GIT zu sprechen, wie dort Dateien geändert werden (Zustände und Befehle) und was die Unterschiede sind. Sie hat glücklich geguckt und genickt aber dann kam

Eigentlich wollte ich was von Build-Werkzeugen hören.

Joa da haben wir in der Vorlesung ANT, MAKE und MAVEN besprochen.

Wie sieht denn eine Make file aus?

Keine Ahnung.

Oke noch mal zu den Modulkopplungen. Welche kennen Sie denn da? Können Sie da eine Reihenfolge wiedergeben?

Die Kopplung zwischen zwei Modulen spiegelt die Abhängigkeit der beiden wieder und sollte deshalb eben möglichst lose sein.
Das wird erreicht mit einer Datenkopplung oder Stempelkopplung. Etwas enger ist dann schon die Steuerkopplung gefolgt von der eher weniger wünschenswerten Externen Kopplung bis hin zur Inhaltskopplung.

Ja, wie sieht es denn aus wenn eine Daten- oder Stempelkopplung vorliegt?

Bei der Datenkopplung ruft das eine Modul das andere anhand von primitiven Datentypen auf. Bei der Stempelkopplung passiert das mit kompexen Datentypen.

Und bei der Inhaltskopplung?

Da basiert das eine Modul auf der Implementation des anderen.

Was heißt das?

?? Dass das eine Modul vollständig abhängig ist von dem anderen, da es ohne das andere Modul bzw dessen Implementation nicht funktioniert.

Können Sie ein Beispiel nennen?

Nein. (Etwas dämlich aber naja)

Kommen wir zu den Vorgehensmodellen. Welche kennen Sie da?

Code-and-Fix (das normale für uns, ein Programmierer, keine große Organisation drum herum, alles im Kopf des Programmierers), das Wasserfall Modell (sequentielles Modell, für Projekte mit wenig Projektrisiko und klarem Vorgehen weil nicht gut im Umgang mit Problemen oder Anforderungsänderungen), das V-Modell (auch sequentiell mit mit dem Schwerpunkt auf Qualität), inkrementelle und evolutionäre Vorgehen

Was ist das?

inkrementell: Aufteilung eines Gesamtsystems in Teile und dann Erarbeitung dieser einzelnen Teile
evolutionär: Schrittweise Erweiterung eines Prototypens zu etwas großem.

Was kennen Sie noch für Modelle?

Die Agilen Modelle

Welche gibt es da?

Das Extreme Programming

Erklären Sie das doch mal.

Für kleine Teams geeigent, fordert ein hohes Maß an Disziplin

(Ich glaube die Zeit wurde eng deshalb hat sie mich unterbrochen)

Es gibt so zwei Iterationen, die ineinander verzahnt sind, welche sind das?

Keine Ahnung.

Was musste schriftlich gelöst werden?

Info A

Laufzeit von Türme von Hanoi mit Wertetabelle.

SWE

Nichts. Habe selbstständig versucht so etwas zu erklären.

Wie war der Ablauf?

Vornberger hatte klar im Kopf was er hören wollte und was er als nächstes fragen wollte.
Frau Pulvermüller wusste leider nicht dass ich in Software Engineering geprüft werden wollte und nicht in Info B.
Das hat meines Erachtens zu etwas wirren Fragen geführt (oder ich war zu schlecht vorbereitet um alle direkt richtig zu verstehen). Diese Hälfte hat zumindest gefühlt ewig gedauert und ich hab mich bei vielen Fragen einfach um Kopf und Kragen geredet. Frau Pulvermüller hat meistens gelächelt und genickt auch wenn sie wahrscheinlich eigentlich etwas anderes meinte mit ihrer Frage, was sie trotzdem nur einmal gesagt hat.

Bewertung und Begründung

2,3 weil ich ein paar mal passen musste.

Zum Verhalten der Prüfer

Beide sehr freundlich. Vornberger war nachdem ich mich beim simplen Einsetzen bei der Wertetabelle verrechnet habe etwas weniger freundlich und hat mich anschließend öfter etwas ruppiger unterbrochen. Insgesamt und am Ende war er aber wieder recht freundlich. Frau Pulvermüller war sehr freundlich auch wenn ich sie leider oft nicht verstanden habe.