Fachrat Informatik - Forum

achso! war das letztes semester keine?

Doch, war auch eine.

Doch letztes Sommersemester war das auch eine Kofferklausur. Herr Holm hat damals in der Übung SS09 auch gesagt, dass alle Hilfsmittel erlaubt wären, außer halt elektronische wie Taschenrechner... war also das gleiche wie jetzt bei dieser hier... deshalb kann ich auch nicht verstehen, warum hier einige sagen, das man diese Klausur vom Schwierigkeitsgrad nicht mit der vom SS09 vergleichen könnte...

Vergleichen kann man die Schwierigkeitsgrade: dieses Jahr war extrem viel schwieriger als alle anderen Erné Klausuren, die ich gesehen habe.
Dementsprechend die Redewendung, dass man die Klausuren nicht vergleichbar sind, eben weil sie so verschiedene Ansprüche gestellt haben.

Dito, wenn ich die Aufgabenstellungen wieder vor mir sehen würde.

Eine Aufgabe ist mir wieder eingefallen (glaube ich). War in Aufgabenteil 3 mit den Fixpunktsachen.

Erläutern Sie kurz die Formel

Lösung: Mit halten wir die Fixpunkte in n fest. Übrig bleiben die Permutationen über n-k ohne Fixpunkte (da wir diese ja gerade festgehalten haben). Dies sind genau bzw. viele (wobei D = Dérangement-Zahlen, Anzahl an fixpunktfreien Permutationen).

Quoted from "Nagezahn"

Besteht eigentlich Interesse an Lösungen zu den Klausuraufgaben? Zu einigen könnte ich welche (bzw. Ansätze) beisteuern - natürlich ohne Gewähr.

Ich hätte da Interesse.

Quoted from "Skuld"

Dito, wenn ich die Aufgabenstellungen wieder vor mir sehen würde.

Eine Aufgabe ist mir wieder eingefallen (glaube ich). War in Aufgabenteil 3 mit den Fixpunktsachen.

Erläutern Sie kurz die Formel

Lösung: Mit halten wir die Fixpunkte in n fest. Übrig bleiben die Permutationen über n-k ohne Fixpunkte (da wir diese ja gerade festgehalten haben). Dies sind genau bzw. viele (wobei D = Dérangement-Zahlen, Anzahl an fixpunktfreien Permutationen).

"Juchu", das hab ich auch :/ Hab da zwei Minuten Zeit dran verloren, weil ich zuerst an Stirlingzahl 1. Art dachte...
Die Sache mit den Wörtern aus dem Alphabet, das war Multinomialkoeffizient (5040 als Ergebnis?). Ich mein, das war in Aufgabe 2 eine Teilaufgabe.

Bei Aufgabe 3 kann ich mich an folgendes erinnern:
- zu zeigen: Eine Ordnung ist eine schwache Ordnung gdw transitiv
- Anzahl der schwachen Ordnungen = Anzahl der totalen Quasiordnungen. Zu zeigen, warum das so ist und für n=4 ausrechnen
- gegeben sind 4 Relationen S={(x,y)| x/y}, T={(x,y)|x<y}, U={(x,y)|x!=y}. Welche davon sind schwache Ordnung? (bin mir bei T nicht sicher, ob das "kleiner" oder "echt kleiner" war, die letzte Relation fällt mir auch gerade nicht ein...

Außerdem kann ich noch beisteuern: Aufgabe 4 war das Rad mit n=Anzahl der äußeren Punkte eines Rades, welche ringförmig, sowie paarweise mit einem weiteren Punkt in der Mitte ("Achse") verbunden waren. Eine Frage war nach Eulertour, die andere nach Hamilton (mit Fallunterscheidung), eine weitere Frage war, ob es einen nicht-isomorphen Graphen mit der gleichen Gradfolge gibt und davor glaub ich war noch eine Frage bezüglich der Komplementierung dieses Graphen...

[edit]Muss man texen lernen [/edit]

Jo, Multinomialkoeffizient stimmt, bin mir nicht mehr sicher was das Ergebnis war, aber viel verrechnen kann man sich da ja nicht.

Totale Quasiordnung ist ja definiert durch R reflexiv und transitiv. Glaube man sollte auch zeigen dass wenn R eine schwache Ordnung ist, R komplement dann eine totale Quasiordnung ist. Zeigt man meine ich dadurch, dass wenn von der schwachen Ordnung das Komplement gebildet wird, die Irreflexivität zur Reflexivität wird und in der Aufgabenstellung gegeben war, dass R komplement transitiv ist. Damit sind Reflexivität und Transitivität erfüllt und es ist eine totale Quasiordnung.

Mit den Anzahlen war ich mir nicht ganz sicher, aber habe das durch die Inzidenzmatrizen beschrieben (ganz schnell zum Schluss). Erinnere mich nicht mehr genau wie, bin aber für beide dann auf die gleiche Anzahl gekommen ( wenn ich mich richtig erinnere).

Zu dem "Rad" sollte man bestimmen ob folgendes exisitert bzw. gilt
a) Eulertour
b) Hamilton Pfad
c) irgendwas mit Baum / komplementärzeug (hier war die Fallunterscheidung, nicht bei Hamilton)
d) Hat es einen nicht isomorphen Graphen mit der gleichen Gradfolge

Wenn ich mich richtig erinnere, hat es keine Eulertour, aber einen Hamiltonpfad und außerdem keinen nicht isomoprhen Graphen mit gleicher Gradfolge. Letzteres begründet, indem ich gezeigt habe, dass wenn man einen neuen Knoten einfügt, er den Grad 3 haben muss, seine Nachbarknoten ebenfalls (also muss man ihn zwischen zweien einfügen), und er eine Kante zur Mitte des Rads haben muss, da diese den Grad n (= Anzahl äußerer Knoten) haben muss. Damit ist der entstehende Graph wieder ein solches Rad.

Quoted from "Skuld"

Totale Quasiordnung ist ja definiert durch R reflexiv und transitiv. Glaube man sollte auch zeigen dass wenn R eine schwache Ordnung ist, R komplement dann eine totale Quasiordnung ist. Zeigt man meine ich dadurch, dass wenn von der schwachen Ordnung das Komplement gebildet wird, die Irreflexivität zur Reflexivität wird und in der Aufgabenstellung gegeben war, dass R komplement transitiv ist. Damit sind Reflexivität und Transitivität erfüllt und es ist eine totale Quasiordnung.

Naja, um eine totale Quasiordnung zu sein muss sie natürlich auch total sein. Aber das Komplement einer Antisymmetrischen Relation ist dies ja zwangsläufig (denn bei Antisymmetrie ist entweder (x,y) oder (y,x) oder keins von beiden enthalten => im Komplement ist auf jedenfall eins von beiden)

Ansonsten

1a) Krieg ich nicht mehr komplett zusammen, aber wenn ich mich nicht irre musste man mehrmals Indexshiften, das letzte Glied der Summe abtrennen und die Formel (n über k) = (n-1 über k-1) + (n-1 über k) verwenden

1b) k * (n über k) bedeuted quasi: Wieviele Möglichkeiten gibt es k Elemente aus n auszuwählen, wobei jeweils ein bestimmtes dieser k Elemente "an der Spitze steht" (nenn ich mal so). Bei n * (n-1 über k-1) wählt man zuerst das Element aus, welches "an der Spitze steht" (kann jedes der n Elemente sein) und anschließend stellt man die restlichen k-1 aus den übrigen n-1 zusammen.

1c) Formel aus (b) einsetzen, Indexshift, Binomische Formel liefert das Ergebnis

Quoted from "Alarion"

Quoted from "Skuld"

Totale Quasiordnung ist ja definiert durch R reflexiv und transitiv. Glaube man sollte auch zeigen dass wenn R eine schwache Ordnung ist, R komplement dann eine totale Quasiordnung ist. Zeigt man meine ich dadurch, dass wenn von der schwachen Ordnung das Komplement gebildet wird, die Irreflexivität zur Reflexivität wird und in der Aufgabenstellung gegeben war, dass R komplement transitiv ist. Damit sind Reflexivität und Transitivität erfüllt und es ist eine totale Quasiordnung.

Naja, um eine totale Quasiordnung zu sein muss sie natürlich auch total sein. Aber das Komplement einer Antisymmetrischen Relation ist dies ja zwangsläufig (denn bei Antisymmetrie ist entweder (x,y) oder (y,x) oder keins von beiden enthalten => im Komplement ist auf jedenfall eins von beiden)

Mist, die Totalität hatte ich ganz vergessen. Naja, der Rest stimmt hoffentlich.

Quoted from "Nagezahn"

(Ich wünschte, das wäre mir schon bei der Klausur eingefallen. )

Hah! Geht mir genauso, kaum saß ich im Zug hatt ich die Lösung vor Augen

Quoted from "Nagezahn"

Hamilton: ja, einfach einmal rum und dann in die Mitte.

Meinst du den Weg anzugeben reicht, oder hast du das noch genauer gezeigt? Habe nämlich auch angegeben, dass es diesen Weg gibt, aber nicht weiter ausgeführt.

Quoted from "Nagezahn"

Doch, es gibt nicht-isomorphe Graphen mit gleicher Gradzahl

Mist

Weiß eigentlich jemand wo und wann die Einsicht am Donnerstag stattfindet?

Ich meine mich zu erinnern, dass die gegen Mittag stattfinden soll. Irgendwas von 13-14 Uhr hab ich in der Übung gehört. Bin mir da aber nicht mehr sicher. Denke mal der Termin wird auf dem Notenaushang morgen stehen

Gruß Jan

Ich meine an der Tür von Herrn Holm die Ergebnisse der letzten Klausur hängen gesehen zu haben, also C 402 (siehe auch hier: http://www.iazd.uni-hannover.de/personen.html).

Ist jemand morgen vor Ort wegen Foto? Ich schlage mal eine "Downline" für Interessierte vor (bin morgen leider nicht in Hannover), wo jeweils dem Nachfolger das Foto weiter geschickt wird...

Also:

fragenfrager