So, einen schönen guten Morgen.
Etwas leise heute.
Letztes Mal ging es ja um reguläre Ausdrücke.
Im Laufe der Vorlesung haben wir ja insgesamt drei Charakterisierungen
von regulären Sprachen.
Einmal Maschine, also indischer Akzeptor.
Das erkennt diese... kann reguläre Sprachen erkennen.
Zweitens diese regulären Ausdrücke.
Damit können wir die Sprache selber beschreiben.
Das ist ein Ausdruck mit diesen Operatoren.
Drittens die rechtslineare Grammatik.
Also als Grammatik dann.
Wir hatten die kontextfreien Grammatiken kennengelernt.
Die können ein bisschen mehr als die regulären Ausdrücke.
Deswegen muss man ein bisschen mehr einschränken bei den
rechtslinearen Grammatiken.
Deswegen haben sie auch einen anderen Namen.
Und zwar, was man einschränkt...
Bei einer Grammatik gibt es nicht so viele Möglichkeiten.
Man könnte versetzen, die Nicht-Terminalsymbole sind wenig oder so.
Aber das ist nicht gut.
Deswegen, was man einschränkt, sind die Produktionen.
Und die sollen eine bestimmte Gestalt haben.
Es gibt zwei Möglichkeiten.
Nicht-Terminalsymbol produziert irgendwas.
Das waren die Produktionen.
Und dieses Irgendwas an der rechten Seite, bei den kontextfreien
Grammatiken, da dürfen wir beliebig viele Nicht-Terminale und beliebig
viele Terminale produzieren.
Bis auf endlich viele.
Und jetzt?
Entweder produzieren wir ein Wort aus Terminalsymbolen, also gar keine
Nicht -Terminalsymbole.
Oder wenn wir eine Nicht-Terminale produzieren wollen, dann dürfen wir
Terminale nur vor diesem Nicht-Terminale produzieren.
Und es darf nur diese einzige Nicht-Terminale produziert werden.
Nur eine Nicht-Terminale.
Bei den kontextfreien Grammatiken, da können wir S, Y, S und so weiter
machen.
Das dürfen wir nicht mehr.
Das ist wirklich eine Einschränkung.
Deswegen müssen diese Grammatiken einen anderen Namen haben.
Und man sieht auch, dass weniger Sprachen als die kontextfreien
Grammatiken produzieren.
Nichtsdestotrotz kann man schon vernünftige Sprachen damit erzeugen.
Zum Beispiel letztes Mal habe ich von Festkommazahlen erzählt.
Zum Beispiel bei einer Premiersprache ein Floatwert irgendwo in meinem
Programm, das ich schon vorgegeben habe, will oder muss.
Das kann man auch jetzt mit einer rechtslinearen Grammatik
spezifizieren.
Am Anfang habe ich ein Vorzeichen und dann habe ich Ziffern erzeugen,
so eine Zahl.
Das ist mindestens eine Ziffer und dann vielleicht ein Punkt noch und
dann Ziffern am Ende.
Das entspricht einem regulären Ausdruck auch.
Das haben wir letztes Mal gesehen.
Zum Namen linear, also rechtslinear, weil ich immer diese Nicht
-Terminale rechts stehen habe.
Also immer Terminale und dann ganz rechts am Ende eine Nicht
-Terminale.
Aber warum auch linear?
Woher kommt dieser Name?
Da kann man sich überlegen, zum Beispiel diese Grammatik hier aus S
ein B und dann das Groß A produziert und dann aus Groß A sozusagen
beliebig viele As produziert werden können.
Aber mindestens ein A.
Das ist, was man da mit dem Groß A produziert.
Das entspricht dem regulären Ausdruck B A Stern A.
Also B ein B am Anfang und dann beliebig viele As, aber mindestens
eins.
Und dann, wir hatten bei den kontextfreien Grammatiken die
Ableitungsbäume kennengelernt.
Kann man auch bei diesen Grammatiken zeichnen, natürlich.
Und hier zum Beispiel für ein längeres Wort, B und dann viermal das A,
kann man den Ableitungsbaum zeichnen.
Dann merkt man, es gibt immer wieder nur ein Nicht-Terminalsymbol.
Es gibt so einen Pfad da in diesem Baum,
bis auf die Terminalsymbole.
Und dann die Terminalsymbole werden immer links erzeugt, aber nicht
nach rechts.
Am Ende ist man ganz rechts bei einem A und dann muss man aufhören.
Dann hat man diesen Pfad.
Und ein Pfad sieht wie eine Linie A aus.
So könnte man das sich vorstellen.
Deswegen Linie A.
Dann habe ich auch gesagt, diese Charakterisierung der regulären
Sprachen.
Und man sieht, dass diese regulären Sprachen nicht ganz erfundene
Dinge sind, weil es gibt nämlich drei verschiedene Charakterisierungen
für dieselbe Klasse.
Das muss eine wichtige Klasse von Sprachen sein.
Also theoretisch betrachtet.
Und man kann zwischen diesen verschiedenen Charakterisierungen, also
einmal ein regulärer Ausdruck, ein Ausdruck beschrieben, als eine
Maschine, die eine Sprache akzeptiert, und als eine Grammatik, die
Wörter erzeugt, also hin und her wechseln.
Für dieselbe Sprache kann man eine von den drei haben, beziehungsweise
alle drei haben, wenn man will.
Man kann hin und her gehen.
Es gibt Konstruktionen, die man durchführen kann, um von einem zu dem
anderen zu gehen.
Das ist zum Beispiel interessant, wenn wir, wie letztes Mal habe ich
erzählt, ich habe einen regulären Ausdruck gegeben.
Zum Beispiel in meinem Programm, die Nutzeingabe soll sowieso sein.
Oder ich will nach einem Muster im Text suchen.
Aber wenn ich ein Wort irgendwo in meinem Text habe, ist es schwierig
zu hantieren mit diesen ganzen Operatoren im regulären Ausdruck.
Deswegen mache ich diesen Übergang von Ausdruck zu Akzeptor.
Und der Akzeptor ist ganz einfach.
Das nimmt ein Zeichen nach dem anderen.
Da kann ich ganz plump das Wort reinstecken.
Dann schauen wir, ob dieser Akzeptor das akzeptiert oder nicht.
Deswegen ist es nützlich, dass man diese Konstruktionen hat, wo man
von einem Typ von Beschreibung von dieser Sprache zum anderen
wechselt.
Dann habe ich auch ein paar Beispiele für solche Übersetzungen.
Zum einen habe ich zum Beispiel einen Akzeptor da.
Und ich will eine rechtslineare Grammatik dafür finden.
Wie könnte das denn gehen?
Könnte das vielleicht kompliziert sein?
Naja, es gibt eine ganz allgemeine und ganz einfache Konstruktion.
Nämlich, ich nehme als Nicht-Terminal-Symbole die Zustände selber von
dem Automaten.
Das darf ich.
Es gibt ähnlich viele und es gibt mindestens einen Zustand.
Das darf ich durchaus als Nicht-Terminale nehmen.
Das ist nicht verboten.
Und mein Startsymbol ist dann der Startzustand.
Start und Staat passen gut zusammen.
Und dann, was noch fehlt bei dem Automaten, es gibt noch Übergänge.
Also ich komme von einem Zustand zum nächsten und dabei lese ich ein
Symbol.
Und dann habe ich in meiner Grammatik eben auch, also aus einem
Zustand habe ich ein Symbol gelesen und dann in einem anderen Zustand
gewechselt.
Das ist eine Art Simulation von dem ähnlichen Akzeptor, was ich da
habe.
Und ich merke mir immer diesen Zustand und dann produziere ich
Symbole, soweit ich die lese, in Anführungszeichen.
Und ich muss dann irgendwann mal aufhören.
Also der ähnliche Akzeptor wird auch aufhören, weil man nur ähnlich
viele Eingabesymbolen haben darf.
Und das beschreibe ich in meiner Grammatik eben als Entfernen von
diesem Zustand.
Dann wird auch dieser Zustand gelöscht.
Dann stehen nur Terminalsymbole da am Ende.
Und löschen ist das leere Wort produzieren.
Und das darf ich nur bei akzeptierenden Zuständen machen.
Also der Automat wird nur anhalten und akzeptieren, wenn das Wort in
der Sprache war.
Und deswegen darf ich nur an diesen Stellen dann aufhören.
Dann habe ich natürlich auch ein Beispiel dafür.
Links hatten wir ja diese, ich glaube ich habe das schon ein paar Mal
in der Übung wieder benutzt, dasselbe Beispiel.
Das ist der Akzeptor zu der Sprache von Wörtern, die ungerade viele
A's in den Wörtern vorkommen.
Dann beliebig viele B's, egal wo man die haben will.
Und dann kann man diese Konstruktion anwenden.
Dann habe ich zwei Nicht-Terminalsymbole, A0 ist mein Startsymbol.
Und als diese Zeichen gelesen werden, dann wechsle ich auch die Nicht
-Terminalsymbole.
Und da habe ich immer mehr gemerkt, was für einen Zustand der Automat
gerade hat.
Und nur A1 ist akzeptierend, deswegen nur daraus darf ich das leere
Wort dann erzeugen.
Es gibt auch den Rückweg, aber das ist im Allgemeinen ein bisschen
komplizierter.
Nämlich, weil bei den rechtslinearen Grammatiken, da dürften wir
beliebig viele Terminalsymbole auf einmal produzieren.
Und bei den ähnlichen Akzeptoren, da können wir leider nicht beliebig
viele Symbole auf einmal lesen.
Wir können nur ein Symbol auf jeden Übergang dann lesen.
Das ist die Einschränkung.
Und deswegen hier schränke ich noch meine Grammatik mehr ein, sodass
das Ganze noch passt.
Man kann sich später überlegen, ob diese Grammatiken immer noch
äquivalent zu den ursprünglichen rechtslinearen Grammatiken fahren.
Das sind die.
Am Ende werde ich noch ein bisschen dazu sagen.
Aber nehmen wir an, wir haben eine solche Grammatik.
Aus einem Nicht-Terminal darf ich nur das leere Wort produzieren, also
gar kein Nicht-Terminalsymbol.
Oder aus diesem X darf ich genau ein Terminalsymbol und dann ein Nicht
-Terminalsymbol erzeugen.
Wirklich eingeschränkt.
Und wenn man das hat, kann man diese gleiche Konstruktion von eben
dann rückwärts anwenden.
Dann habe ich aus Nicht-Terminalsymbolen Zustände gemacht.
Aus dem Startsymbol mache ich meinen Startzustand.
Und aus diesem Produktion X produziere ich TY.
Das ist wie ein Zustandswechsel, wobei ich T lese.
Und X produziert das leere Wort, sodass X ein akzeptierender Zustand
sein muss.
So wird das interpretiert.
Und man kann zeigen, dass...
Natürlich wird dieser Akzeptor die gleiche Sprache wie diese Grammatik
akzeptieren.
Das ist einfach die Grammatik als Akzeptor irgendwie dargestellt.
Und was fehlt hier ist, dass man noch zeigen kann, dass jede
rechtslineare Grammatik auch von dieser Form sein kann.
Wie könnte das gehen?
Ich werde jetzt nur die Idee sagen.
Nehmen wir mal an, wir haben dann viele Terminalsymbole aus dem X
produziert.
Was mache ich?
Mehr Nicht-Terminalsymbole.
Also ich habe zum Beispiel A, B, C, D.
Das ich produzieren will aus dem X, nicht nur das leere Wort.
Dann produziere ich aus X dann A, X, A und dann aus X, A dann B, X, B
und dann so weiter.
Dann kann ich mit mehr Nicht-Terminalsymbolen dann auch dasselbe
Verhalten haben.
Und dann am Ende zu dieser Form übergehen.
Das lasse ich einfach so stehen, will ich nicht jetzt im großen Detail
betrachten.
So viel dazu.
Es gibt dann hier andere Überlegungen.
Wir hatten Reichssignal gesehen, weil das Nicht-Terminal immer ganz
reich stand.
Man kann sich auch überlegen, was passiert, wenn ich jetzt nicht
fordere, dass das Nicht-Terminal dann ganz rechts, sondern ganz links
steht.
Bei dieser zweiten Art von Produktion.
Dann kann ich natürlich damit auch Sprachen erzeugen.
Genauso wie bei den kontextfreien Grammatiken, wie man vertraut ist.
Und zum Beispiel habe ich diese Grammatik da ganz unten.
Und wenn ich die anwende und ein paar Wörter produziere, dann merke
ich, dass sind einfach A's und B's nacheinander vertauscht, sozusagen.
Und man darf bei einem B oder einem A anfangen, muss aber bei einem B
aufhören.
Man ahnt, das sieht regulär aus.
Könnte man auch mit einer rechtslinearen Grammatik erzeugt haben.
Das ist nicht nur regulär, man könnte noch die rechtslineare Grammatik
dafür finden.
Nämlich, wie ich gesagt habe, am Anfang steht vielleicht ein B und
dann produziere ich A, B's.
Dann habe ich immer solche Wörter.
Und man kann sich dann im Allgemeinen überlegen, können dann diese
linkslinearen Grammatiken mehr oder weniger als die rechtslinearen
Grammatiken?
Und Bauchgefühl, Symmetriegründen, warum sollen die mehr oder weniger
können?
Die dürfen durchaus dasselbe können.
Und dann eben, wenn man das jetzt beweisen will, muss man sich schon
Gedanken darüber machen, wie jetzt von einem zu dem anderen kommt.
Also, wie könnte das gehen?
Der erste Versuch, den man hat, naja, ich habe Produktion bei einer
rechtslinearen Grammatik.
Vielleicht drehe ich einfach alles, was produziert wird, um.
Dann habe ich aus X dann ein umgedrehtes Wort produziert.
Und dann habe ich, wenn ich jetzt dieses Y ganz am Ende erzeuge, bei
einer rechtslinearen Grammatik, dann wird das ganz links sein.
Dann habe ich automatisch eine Grammatik, die linkslinear ist.
Aber ich habe jetzt die Wörter alle umgedreht, das ist alles jetzt in
der falschen Reihenfolge.
Ich wollte es doch anders haben.
Aber das habe ich erst mal.
Vielleicht kann ich jetzt das anwenden, wenn ich noch das alles
umdrehen kann.
Wie könnte das gehen?
Letztes Mal hatten wir etwas ganz Nützliches gesehen.
Aber jetzt ganz Schritt für Schritt gesehen.
Ich fange bei einer rechtslinearen Grammatik an, so wie z.B.
links zu sehen ist.
Dann habe ich einen regulären Ausdruck dafür.
Das ist diese Charakterisierung, das man jetzt voraussetzt.
Dann mache ich diesen Weg.
Und ich habe nach der letzten Übung, wenn ich einen regulären Ausdruck
habe, wenn ich den geschickt spiegle, wobei ich bei den Operatoren
aufpassen muss, dann bekomme ich die Sprache, die das Spiegelbild von
dieser Sprache ist.
Von der Sprache, die diesem regulären Ausdruck entspricht.
Dieser reguläre Ausdruck erzeugt dieselbe Sprache wie mein GR am
Anfang.
Deswegen habe ich mit einem regulären Ausdruck jetzt das Umkehrbild
von der Sprache, von dieser Grammatik.
Und ich kann wieder diese Charakterisierung anwenden.
Also ich habe einen regulären Ausdruck, deswegen habe ich eine
rechtslineare Grammatik dafür.
Man muss jetzt Konstruktion nach Konstruktion anwenden, das wird
langsam kompliziert.
Ich habe jetzt eine rechtslineare Grammatik für diesen Ausdruck.
Und das heißt, ich habe eine rechtslineare Grammatik, die das
Umkehrbild von der Sprache, von der ersten Grammatik GR erzeugt.
Das heißt, ich kann mit einer, jetzt habe ich gerade auch gezeigt,
nebenbei, wenn ich eine rechtslineare Grammatik habe, dann finde ich
auch eine rechtslineare Grammatik, die das Umkehrbild der Sprache, von
dieser ersten Grammatik erzeugt.
Und dann kann ich, wenn jetzt alles schon verdreht ist, dann kann ich
jetzt diese Konstruktion für die linkslineare Grammatik anwenden.
Dann habe ich alles verdreht nochmal, aber zweimal spiegeln ist eben
die Identität.
Und deswegen wird das Spiegelbild von der Sprache wieder die Sprache
von der Grammatik GR sein.
Und dann habe ich jetzt eine linkslineare Grammatik, die dieselbe
Sprache wie dieses GR erzeugt.
Und jetzt, wenn man rechtslineare und linkslineare vertauscht und auch
bei der Konstruktion dann wieder dieses Umtauschen verwendet, kann man
auch das Gleiche zeigen.
Also von einer linkslinearen Grammatik ausgegangen, finde ich auch
eine rechtslineare Grammatik, die dieselbe Sprache erzeugt.
Und dann sind die äquivalent.
Die erzeugen die gleiche Klasse von Sprachen.
So, das wäre es dann für die letzte Übung.
Vielen Dank für die Aufmerksamkeit und noch viel Erfolg bei der
Vorbereitung auf die Klausur.
Und ja, alles Gute.
Ja, schönen guten Tag.
Herzlich willkommen zur letzten Vorlesung Grundbegriffe der
Informatik.
Wir hatten am Mittwoch noch angefangen mit Halbordnungen.
Da will ich Ihnen jetzt zumindest noch ein bisschen mehr sagen.
Dann werden wir was überspringen.
Dann erzähle ich Ihnen noch ein bisschen was zu totalen Ordnungen oder
Ordnungen.
Und das machen wir dann so, dass am Ende noch ein bisschen Zeit
bleibt, um ein paar Worte zur Klausur zu sagen.
Also Halbordnungen.
Hier oben steht nochmal die Definition.
Eine binäre Relation auf eine Menge M heißt Halbordnung, wenn sie
reflexiv, antisymmetrisch und transitiv ist.
Reflexiv und transitiv ist, denke ich, schon hinreichend vertraut.
Antisymmetrie ist hier nochmal für Mengeninklusion hingeschrieben.
Also Mengeninklusion ist eine Halbordnung.
Wenn A kleiner gleich B ist und B kleiner gleich A, also jetzt bei
Mengen, wenn A Teilmenge von B ist und B Teilmenge von A, dann ist A
gleich B.
Dann ist das in Wirklichkeit das Gleiche.
Und Halbordnungen heißen Halbordnungen, weil noch nicht alles geordnet
ist im Allgemeinen.
Also Sie können so eine Situation haben, wie hier bei den Mengen.
Weder ist eine Menge A Teilmenge von einer Menge B, noch umgekehrt.
Es gibt so unvergleichbare Elemente.
Das kann man im Allgemeinen haben.
So, wenn man sich Halbordnungen hinmalt, dann häufig, so die
Relationen als gerichtete Graphen zumindest andeutet, dann
üblicherweise man malt nicht alle Pfeile, die gelten.
Wegen Reflexivität an jedem Knoten ist eine Schlinge.
Das weiß man sowieso, wenn es um Halbordnungen geht.
So Pfeile, die sich ergeben durch Pfade auf Umwegen, die muss man auch
nicht extra hinmalen.
Man weiß ja, es soll transitiv sein.
Das kann man rekonstruieren.
Und deswegen typischerweise, was man dann nur hinmalt, ist das
Hasediagramm.
Also man lässt die Schlingen weg und man lässt das weg, was man durch
Transitivität sozusagen rekonstruieren kann.
Also hier, dass die leere Menge Teilmenge der Menge ABC ist, ist klar.
Da ist jetzt nicht extra ein Pfeil hingemalt, aber man sieht ja, man
kommt auf irgendeinen Weg von unten nach oben zum Beispiel.
Das nennt man das Hasediagramm.
Also da lässt man nur Dinge weg, die man sowieso wieder rekonstruieren
kann durch Bilden der reflexiv-transitiven Hülle.
Und wenn ich Ihnen jetzt irgendwelche Bilder hinmale und suggeriere,
das ist eine Halbordnung, dann auch immer, das sind nur Ausschnitte
von Hasediagrammen.
Den Rest müssen Sie sich dazu denken, so reflexiv und transitiv.
Ja, und dann gucken wir uns mal noch zumindest so ein paar Begriffe
an, weil die wichtig sind und weil es zum Teil auch wichtig ist, dass
man die nicht durcheinander bringt.
Das Erste, stellen Sie sich vor, Sie haben eine Halbordnung und eine
Teilmenge und hier links in dem Bild die Knoten, das seien jetzt mal
nur die aus der Teilmenge.
Und es gibt so ein paar Ordnungsrelationen.
Und wenn zwischen zwei Knoten hier, also meinetwegen hier ganz unten,
die beiden untersten Knoten, zwischen denen ist kein Pfeil und es gibt
auch keinen Pfad auf Umwegen von dem einen zu dem anderen.
Das heißt, die beiden sind tatsächlich hier ganz unten, die sind
unvergleichbar.
Aber zum Beispiel das unterste, jedes von den beiden untersten steht
in Relation zu dem obersten, da gibt es auch keinen Pfeil, aber das
ergibt sich ja durch Transitivität.
Und in so einer Situation sagt man, dass ein Element, also wenn das
hier nur eine Teilmenge T ist, der ganzen Menge M, dass ein Element
ein maximales Element dieser Teilmenge ist.
x ist maximal, wenn es kein y gibt, sodass x kleiner gleich y ist,
aber eben nicht gleich x, sondern was anderes und immer noch in T ist.
Also mit anderen Worten, die maximalen Elemente sind die in ihrer
Teilmenge, wo oben drüber in der Teilmenge nichts mehr kommt.
Da oben geht es nicht weiter.
Diese beiden sind maximale Elemente.
Und analog minimale Elemente sind Elemente mit der Eigenschaft, es
gibt kein x ist minimal, wenn es kein anderes y gibt, mit y kleiner
gleich x.
Also hier unten die beiden, das sind die minimalen Elemente dieser
Teilmenge.
Und wie Sie sehen, eine Menge kann mehrere maximale oder minimale
Elemente haben.
Es kann auch manchmal nur eins geben.
Es gibt auch Halbordnungen und Teilmengen, da haben Sie gar keine
maximalen oder minimalen Elemente.
Hier erst nochmal, also eines der Standardbeispiele für Halbordnungen
sind ja hier so die Teilmengen einer Menge geordnet durch Inklusion.
Und wenn das hier die Teilmenge ist, dann sehen Sie, dass es zwei
maximale Elemente gibt, A, B und B, C.
Es gibt hier oberhalb kein weiteres Element in der Teilmenge und es
gibt genau ein minimales Element jetzt in diesem Beispiel, die leere
Menge.
Von minimalen und maximalen Elementen bitte sorgfältig immer
unterscheiden, das ist im Allgemeinen was anderes, sogenannte kleinste
und größte Elemente einer Teilmenge.
Ein Element x heißt kleinstes Element einer Teilmenge, wenn für alle
anderen y in der Teilmenge gilt, dass x kleiner gleich y ist.
Und ein x heißt größtes Element, wenn alle y aus der Teilmenge kleiner
gleich x sind.
Jetzt versuchen Sie schon mal kurz zu überlegen, wo jetzt der
Unterschied zu minimalen und maximalen Elementen ist.
Nehmen wir wieder diese gleiche Teilmenge von dem Beispiel eben mit
den fünf Teilmengen von A, B, C.
Wie sieht das jetzt hier aus?
Wer sieht ein größtes Element?
Keiner.
Das ist gut, es gibt nämlich keins.
Es gibt ein kleinstes Element hier unten, die leere Menge, die ist
kleinstes Element.
Und was war die Definition von kleinstes Element?
Kleinstes Element, für alle anderen und auch erst sich selbst wegen
Reflexivität, dieses Element ist kleiner gleich jedem anderen.
Das ist etwas anderes als da drunter kommt nichts mehr.
Das sieht man hier bei den Elementen da oben, die waren größte
Elemente, A, B und B, C, drüber kommt nichts mehr.
Aber für keins von diesen Elementen gilt, alles andere ist unterhalb
kleiner gleich dem.
A, B ist nicht Teilmenge von B, C und B, C ist nicht Teilmenge von A,
B.
Deswegen keins von den beiden ist das größte Element, aber beide sind
maximal.
Oben drüber kommt nichts mehr.
So und ganz besonders vorsichtig, jetzt haben Sie vielleicht etwas in
Ihrem Hinterkopf, die Hoffnung will ich Ihnen gleich wieder nehmen,
ganz besonders aufpassen müssen Sie bei unendlichen Halbordnungen.
Da können Sie so Dinge haben, dass Sie genau ein, genau ein minimales
Element haben, aber das ist nicht das kleinste Element.
Nehmen Sie diese Halbordnung, da ist also hier nach oben und unten
unendlich irgendwelche Elemente, also vor die ganzen Zahlen geordnet
durch kleiner gleich.
Hier links, ganz rechts diese ganze Kette und dann bei einem Element
hängt da noch so eins unten drunter dran.
Ist eine Halbordnung.
Also das ist ein Hass, wenn Sie das als Hassediagramm auffassen,
kriegen Sie daraus eine Halbordnung.
Dieses Element hier ist minimal, es hängt nichts drunter, aber das ist
nicht das kleinste Element.
Es gibt beliebig viele Elemente, die nicht oberhalb dieses minimalen
Elementes liegen.
Also nie durcheinander bringen, bitte.
Wo auch immer das mal vorkommen kann.
Wenn Sie sich jetzt diese kleinsten und größten Elemente angucken,
dann stellt man aber jedenfalls fest, es gibt nie zwei davon.
Also es kann schon zwei größte geben, Entschuldigung, zwei maximale
Elemente geben, aber nie zwei größte und auch nie zwei kleinste.
Es kann mehrere minimale geben, aber nie zwei kleinste.
Warum nicht?
Also stellen Sie sich vor, Sie haben X1 und Sie haben X2 und das sind
kleinste Elemente.
Dann nach Definition von was ist ein kleinstes Element, wenn X1
kleinstes Element ist, dann ist X1 kleiner gleich X2.
Und wenn X2 angeblich auch kleinstes Element ist, dann natürlich ist
X2 kleiner gleich jedem Element, also X2 ist auch kleiner gleich X1
und dann haben Sie X1 kleiner gleich X2, X2 kleiner gleich X1 und dann
sagt Ihnen die Antisymmetrie, die von jeder Halbordnung erfüllt wird,
naja, das ist das Gleiche.
Eindeutig.
Also kleinste und größte Elemente sind immer eindeutig, maximale und
minimale im Allgemeinen nicht.
So, bis jetzt haben wir nur geredet über Elemente innerhalb von so
einer Teilmenge von der ganzen Menge.
Da gab es Elemente ganz oben, die maximalen, wenn man Glück hat ein
größtes, alles andere war unterhalb.
Und jetzt kann es sein, dass Sie Teilmengen haben, die haben noch
nicht mal ein maximales, geschweige denn ein größtes Element,
aber unter Umständen, also in der Teilmenge finden Sie kein größtes
Element, aber vielleicht in der ganzen Menge, die größer sein kann,
vielleicht oben drüber finden Sie dann doch noch was.
Und sowas nennt man dann eine obere Schranke bzw.
analog unten eine untere Schranke.
Also Sie haben eine Teilmenge einer großen halbgeordneten Menge M und
ein Element X aus M und das darf jetzt halt außerhalb der Teilmenge T
liegen.
So ein Element M heißt obere Schranke von T, also alle Elemente in T,
wenn alle Elemente Y in T kleiner gleich X sind.
Es kann sein, dass Sie so ein Y nicht in T drin haben, aber außerhalb
oben drüber.
Und eine untere Schranke ist ein Element mit der Eigenschaft X ist
kleiner gleich Y für jedes Y aus der Teilmenge.
Hier nochmal das Hasse-Diagramm von der ganzen Halbordnung, alle
Teilmengen der Menge ABC.
Und jetzt betrachten wir mal als erstes die Teilmenge, die nur aus den
drei, die Teilmenge der Potenzmenge von M, also die drei Teilmengen,
leere Menge, die Menge, die A enthält, die Menge, die B enthält und
sonst nichts.
Die hat, wie man sieht, zwei maximale Elemente A und B.
Aber kein größtes Element.
Aber, also hier jetzt nochmal die drei roten, das sind die Elemente,
die zu T dazugehören.
Aber Sie finden, also es hat kein größtes Element, es ist kein Element
in der Menge, sodass alle in der Menge kleiner gleich diesem Element
sind.
Aber außerhalb finden Sie zum Beispiel A, B und A, B, C und die haben
die Eigenschaft, dass alle Elemente, die hier unten rot sind, die zu
der Teilmenge T gehören, die sind kleiner gleich, also enthalten in A,
B und erst recht enthalten in A, B, C.
Also hier haben Sie zwei obere Schranken und beide liegen außerhalb
dieser Menge T.
Aber zum Beispiel B, C ist keine obere Schranke, weil nämlich A nicht
Teilmenge von B, C ist.
Und wenn Sie die andere Teilmenge nehmen, jetzt noch ein Element dazu,
nämlich A, B, dann haben Sie jetzt hier eine Teilmenge, die hat eine
obere Schranke, die ist sogar in der Menge drin, das ist nicht
verboten.
Aber immer noch, das ist nicht die einzige obere Schranke da, das A,
B, C ist auch noch obere Schranke, alle roten sind kleiner gleich A,
B, C.
Gut, dann hat man untere und obere Schranken und also Sie können
Halbordnungen haben, da gibt es auch sowas nicht.
Stellen Sie sich vor, das hier ist die ganze Halbordnung, ein Element
und zwei, die größer sind, aber unvergleichbar.
Sie haben nur die drei Elemente, die ganze Menge, da finden Sie keine
obere Schranke.
Es gibt nichts, was hier über allem drüber ist.
Das ist schon die ganze Menge.
Das kann durchaus sein.
Und wenn Sie zum Beispiel die nicht negativen ganzen Zahlen nehmen und
kleiner gleich, also kleiner gleich auf Zahlen ist eine Halbordnung.
X ist kleiner gleich X, wenn X kleiner gleich Y und Y kleiner gleich
X, dann ist X gleich Y und Transitivität gilt auch.
Wenn Sie die Menge nehmen und dann zum Beispiel die ganze Menge hat
keine obere Schranke, also es gibt kein Element, das größer gleich
allen nicht negativen ganzen Zahlen ist.
Das gilt auch sogar zum Beispiel, wenn Sie nur die geraden Zahlen
nehmen, das ist eine echte Teilmenge.
Die Menge der geraden Zahlen hat keine obere Schranke in den nicht
negativen ganzen Zahlen.
Es gibt keine Zahl, die größer gleich jeder geraden Zahl ist.
Gerade Zahlen werden beliebig groß.
Wenn Sie sowas haben wollen, dann müssten Sie künstlich die Menge
erweitern, so ein künstliches Element unendlich und definieren, dass
das größer ist als alle anderen oder so etwas.
Kann man natürlich machen, hat man andere Halbordnungen.
Also ist dann was anderes als das hier.
Und tatsächlich macht man solche Sachen manchmal so künstlich noch
irgendwelche Elemente dazu.
Ja, und dann zeige ich Ihnen noch diese Folie und dann setzen wir aber
gleich zu einem, vielleicht auch noch nicht, nein, noch nicht ganz zu
einem Sprung an.
Also jetzt haben Sie eine Halbordnung, Sie haben eine Teilmenge.
Wenn Sie Glück haben, hat die Teilmenge obere Schranken.
Das ist schon mal nett.
Wenn Sie noch mehr Glück haben, in Anführungszeichen, dann enthält die
Menge der oberen Schranken ein kleinstes Element.
Wenn das so ist, also wenn die Menge aller oberen Schranken einer
Teilmenge ein kleinstes Element enthält, dann nennt man das das
Supremum dieser Teilmenge und schreibt dann hier sowas, was aussieht
wie ein eckiges, großes Vereinigungszeichen.
Salopp gesagt.
Und analog als Infimum bezeichnet man, wenn es denn existiert, das
größte Element aller unteren Schranken einer Teilmenge und schreibt
dann sowas, was aussieht wie ein großes Durchschnittszeichen.
Und tatsächlich, sowas muss nicht existieren im Allgemeinen, aber wenn
Sie dieses Standardbeispiel nehmen, Teilmengen einer großen
Grundmenge, geordnet durch Inklusion, dann das Supremum existiert
immer, dann nehmen Sie einfach alle Teilmengen, die Sie interessieren
und vereinigen die.
Da haben Sie was, was offensichtlich jede von den Teilmengen als
Teilmenge enthält.
Ja,
also die Schreibweise mit diesem eckigen Ding kommt daher, dass das
eine große Vereinigung ist, wenn Sie dieses Beispiel Teilmengen einer
Grundmenge betrachten.
Und jetzt nehmen wir mal als Grundmenge die Menge aller Wörter über
irgendeinem Alphabet, also A, B, Stern meinetwegen, und dann als M,
als die Elemente in der Halbordnung, die Teilmengen von M', also mit
anderen Worten formale Sprachen.
Und jetzt betrachten wir mal diese formalen Sprachen hier, L0, L1, L2,
L3, also Teilmengen von M', also Elemente von M, Elemente der
Potenzmenge.
Und zwar meinetwegen, also L0 ist nur das leere Wort, L1 ist das leere
Wort und AB, L2 ist das leere Wort und AB und A²B² und im Allgemeinen
LI sind alle A hoch J, B hoch J und der Exponent ist irgendwas kleiner
gleich I.
Da haben Sie jetzt für jedes I so eine formale Sprache, jede dieser
formalen Sprachen ist endlich, enthält I plus 1 Wörter.
Da haben Sie also jetzt in diesem großen Bildchen von der ganzen
Halbordnung haben Sie jetzt so ein paar Punkte, die formale Sprachen,
die Teilmenge von A, B, Stern sind.
Und jetzt können Sie sich fragen, was ist das Supremum und die
Behauptung ist, das Supremum aller dieser Mengen, das ist einfach die
Vereinigung aller dieser Mengen und die Vereinigung dieser Mengen, das
ist dann die Menge aller Wörter der Bauart A hoch J, B hoch J.
Alle zusammen, das sind unendlich viele.
Also da sehen Sie, dass das Supremum offensichtlich irgendwie anders
ist als jede dieser Teilmengen dieser formalen Sprachen, die man da
betrachtet.
Das ist etwas außerhalb sozusagen dieser Teilmenge.
Ja genau und das existiert hier, die Vereinigung, das ist das
Supremum.
Also erstens offensichtlich, es ist eine obere Schranke, weil diese
Mengen da natürlich alle Teilmenge sind, man vereinigt die ja.
Da muss man sich noch überlegen, das ist auch die kleinste obere
Schranke.
Naja, das ist jetzt dann auch kein ganz großes Hexenwerk, aber das
lassen wir mal einfach weg.
So und jetzt hören wir gleich mit Halbordnungen auf.
Ein Begriff, der dann noch wichtig wird, ist, dass man so etwas hat
wie zum Beispiel solche aufsteigenden Ketten, also so X0, X1, X2, so
Folgen mit der Eigenschaft Xi ist immer kleiner gleich Xi plus 1.
Und dann fängt man an, sich Halbordnungen anzugucken, wo zum Beispiel
solche Ketten jedenfalls immer ein Supremum haben und dann guckt man
sich Abbildungen von solchen Halbordnungen auf solche Halbordnungen
an.
Und wenn die dann noch schöne Eigenschaften haben, dann ist man an
einer Stelle, wo man was hat, was man benutzen kann, um zu definieren,
zum Beispiel die Semantik von Programmiersprachen.
Das kann man auf verschiedene Arten und Weisen machen.
Also was ist die Bedeutung von einem Java Programm?
Und insbesondere, was ist die Bedeutung von einer Weilschleife?
Und Sie erinnern sich an das Halteproblem, man weiß immer gar nicht
genau, wie lange das läuft und so.
Und eine Möglichkeit, dann festzulegen, was ist die Bedeutung einer
Weilschleife, ist so eine besonders schöne Abbildung von einer
besonders schönen Halbordnung auf sich selber anzugucken und da etwas
zu tun.
So, was genau, können Sie ja mal auf den Folien, die ich jetzt
überspringe, nachgucken, wenn Sie es interessiert, so als Andeutung.
Ein bisschen was wird auch bewiesen, aber das überspringe ich jetzt
einfach mal.
Oder?
Wie geht das weiter?
Ja, ich überspringe es.
Ja,
man braucht dann noch ein paar Begriffe, um an die Stelle zu kommen,
wo ein schöner Satz steht, der einem sagt, so eine Abbildung hat immer
eine schöne Eigenschaft.
So.
Das lassen wir mal weg.
Das frage ich Sie dann nur in der Klausur.
Nein, Scherz natürlich nicht.
Ja, zur Klausur sage ich gleich noch was.
Aber vorher gucken wir uns noch so ein bisschen totale Ordnungen an.
Was ist eine totale Ordnung?
Das ist eine Halbordnung, die zusätzlich die Eigenschaft hat, dass es
nicht sowas gibt, wie wir in den Bildern immer hatten, so Elemente,
die nicht miteinander vergleichbar sind.
Weder ist x kleiner gleich y, noch ist y kleiner gleich x.
Das ist bei totalen Ordnungen einfach verboten.
Also jede totale Ordnung ist eine Halbordnung mit der zusätzlichen
Eigenschaft, für alle x und y aus der Grundmenge gilt.
Also x steht in Relation zu y oder y steht in Relation zu x.
Eins von beiden gilt auf jeden Fall.
So.
Und das führt dann also dazu, dass in irgendeinem Sinne die Elemente
so strikt so geordnet sind.
Also da gibt es nicht so Dinge wie in dem Bildchen bisher, wo da was
zusammenführt.
Und jetzt gehe ich nochmal zu den Halbordnungen hier zurück.
Wo haben wir denn ein Bild von einer Halbordnung?
Sie sehen, man braucht noch ein bisschen was.
Hier sowas, ja.
Also so Elemente, die nicht in Beziehung zueinander stehen.
Das gibt es nicht bei totalen Ordnungen.
Und das heißt, solange Ihre Grundmenge nur endlich viele Elemente
enthält, ist das alles völlig übersichtlich.
Da gibt es ein kleinstes Element und dann ein zweitkleinstes, drittes,
viertes, fünftes.
Und nach endlich vielen Schritten sind Sie beim größten Element.
Aber es sagt ja keiner, dass... Ach, jetzt habe ich im falschen
Foliensatz geblättert.
Das ist dumm.
Dann blättern wir jetzt wieder.
Außerdem ist jetzt irgendwas völlig verkehrt.
Also blättern wir hier.
Also wenn Sie es interessiert, gucken Sie sich dann mal diesen
Fixpunktsatz zu Hause noch an.
Der Beweis ist kein Hexenwerk.
Man braucht halt so ein bisschen Voraussetzungen.
Hier noch eine stetige Abbildung auf einer vollständigen Halbordnung
ist nett, ist einfach, ist verblüffend.
Hübsche Sache.
Also totale Ordnungen.
Es gibt keine unvergleichbaren Elemente.
Also zum Beispiel die nicht negativen ganzen Zahlen mit kleiner
gleich.
Ist eine totale Ordnung, wenn Sie zwei Zahlen haben.
Also erstens ist es eine Halbordnung, reflexiv, transitiv,
antisymmetrisch.
Und wenn Sie zwei Zahlen haben, ist auch klar, eine von beiden ist
kleiner gleich der andere.
Oder Sie können irgendwie Paare von ganzen Zahlen nehmen.
Also jetzt kariertes Papier, zweidimensional.
So die Punkten mit ganzzahligen Koordinaten, die können Sie auch total
ordnen.
Total.
Indem Sie sagen, naja, also ich gucke halt primär auf die erste
Komponente.
Also wenn Sie jetzt zwei Paare haben, X1, X2, Y1, Y2.
Ich gucke primär auf die erste Komponente und vergleiche erstmal X1
mit Y1.
Und wenn X1 kleiner ist als Y1, dann ist dieses Paar kleiner gleich
dem anderen.
Mit anderen Worten so.
Ja, was ist jetzt die X-Achse?
Stellen Sie sich vor, die X-Achse läuft horizontal.
Punkte, die in irgendeiner Spalte weiter links sind, sind kleiner als
Punkte, die in einer Spalte irgendwo weiter rechts sind.
Egal wie hoch.
Weiter links, kleiner als weiter rechts.
Und dann innerhalb der gleichen Spalte ordnen Sie die halt so.
Sie gucken auf die zweiten Komponenten.
Und wenn X2 kleiner gleich Y2 ist, dann sagen Sie, da gilt auch die
Beziehung.
Also innerhalb einer Spalte, die, wenn Y nach oben wächst, die
Elemente weiter unten sind kleiner als die Elemente weiter oben.
So.
Oder Sie nehmen die Menge aller Wörter, meinetwegen jetzt hier einfach
halber mal über dem Alphabet A, B und sortieren die so wie im
Wörterbuch.
Also so, wie das jedenfalls die Europäer in diesem Hörsaal für
selbstverständlich halten.
Aber halten Sie sich nicht für das Zentrum der Welt, wenn Sie meinen,
das ist ja trivial.
Also erstens zeige ich Ihnen gleich, das ist gar nicht so trivial.
Und zweitens dürfen Sie sich mal Gedanken darüber machen, wie man denn
wohl in einem japanischen chinesischen Wörterbuch dort die ganzen
Schriftzeichen der Reihe nach sortiert.
Und wenn Sie es nicht wissen, bevor ich mal bei den meisten ausgehe,
dann versuchen Sie mal rauszufinden, wie die das machen.
Muss man ja auch irgendwie festlegen.
Also wenn Sie ein Wörterbuch haben wollen, von japanisch nach deutsch
oder so.
Irgendwie müssen Sie die japanischen Wörter ja in irgendeiner
Reihenfolge da reinschreiben in das Wörterbuch.
Wie macht man das denn, damit man das hinterher irgendwie wieder
findet?
So.
Okay.
Aber also so wie in europäischen Wörterbüchern und klein a und klein b
haben wir hoffentlich in vielen europäischen Sprachen.
Gut.
Das ist auch eine totale Ordnung.
Also Sie sind sich alle völlig sicher, wenn ich Ihnen zwei Wörter
gebe, Sie können mir sagen, welches zuerst im Wörterbuch kommt.
Jedenfalls, wenn wir nur a´s und b´s haben.
Randbemerkungen.
Schwieriger wird es schon wieder bei Umlauten.
Die Standardregel für Deutsch sieht zum Beispiel für das Ö einen
anderen Punkt vor in der Reihenfolge als im Schwedischen.
Also es ist nicht alles trivial, aber bei a´s und b´s sind wir uns
doch hoffentlich einig.
Und ja, also versuchen wir uns mal einer totalen Ordnung auf Wörtern.
Das erste, das habe ich Ihnen das letzte Mal schon gezeigt, das ist
erst mal nur eine Halbordnung.
Das ist keine totale Ordnung.
Nämlich w1 ist kleiner gleich p2 in dieser Halbordnung mit Index p wie
Präfix.
Ja, wenn w1 Präfix von w2 ist.
Also b1 ist kleiner gleich w2.
Genau dann, wenn es ein u gibt, so dass w1 u gleich w2 ist.
Das ist eine Halbordnung, kann man sich überlegen.
Also natürlich ist das reflexiv.
Jedes Wort ist Präfix von sich selber.
Das ist auch transitiv.
Wenn w1 Anfangsstück von w2 ist und w2 ist Anfangsstück von w3, dann
ist auch w1 Anfangsstück von w3.
Und antisymmetrisch ist es auch, wenn w1 Anfangsstück ist von w2, also
die Länge kleiner gleich der von w2 ist und umgekehrt auch, dann sind
die also gleich lang und eins ist Anfangsstück vom anderen.
Das muss das gleiche Wort sein.
Das ist eine Halbordnung, aber also zwei Wörter gleicher Länge, zum
Beispiel das Wort einfach nur a und das Wort b.
Da ist keins Präfix vom anderen.
Die sind unvergleichbar in dieser einfachen Halbordnung.
So, das will man jetzt noch beseitigen.
Und wie beseitigt man das?
Also insbesondere für einzelne Buchstaben muss man sich irgendwas
ausdenken und dann legt man halt einfach willkürlich irgendwas fest.
Ja, a ist kleiner gleich b.
Und wie das dann mit dem ö ist, kommt halt darauf an, in welcher
Sprache Sie gucken.
Aber bei a und b sind wir uns irgendwie einig, hoffe ich.
Also man sagt dann noch willkürlich a kommt vor b und benutzt das
dann, um den Rest auch noch irgendwie festzulegen.
Und da hat man mehrere Möglichkeiten.
Da gibt es etwas, das heißt Lexikografische Ordnung erster Art.
Das ist das, was Sie aus dem Wörterbuch kennen.
Und es gibt auch noch etwas, das heißt Lexikografische Ordnung zweiter
Art.
Das ist eigentlich viel hübscher.
Also für Informatiker.
So.
Nehmen Sie diese drei Wörter.
Milchstraße, Milch und Milchreis.
In welcher Reihenfolge stehen die in einem Wörterbuch?
Wer ist dafür?
Nein, ich frage nicht.
Also es ist als erstes kommt Milch, weil das Präfix von den beiden
anderen ist.
Also das macht man dann sowieso so irgendwie.
Und die beiden anderen Milchreis und Milchstraße.
Na ja, da ist keines Präfix vom anderen.
Die haben so ein gemeinsames Anfangsstück und dann gibt es irgendeine
Stelle.
Der sechste Buchstabe, der ist verschieden.
In einem Fall ist es ein R, in anderen Fall ein S.
Und dann sagt man ja, ich habe ja willkürlich festgelegt, R kommt vor
S und deswegen kommt jetzt auch Milchreis vor Milchstraße.
So macht man das.
Also was man tut ist, man sucht ein möglichst langes gemeinsames
Präfix.
Also wir haben zwei Wörter, W1 und W2.
Und man sucht ein längstes Präfix, ein längstes Wort, das Präfix von
beiden ist, sowohl von W1 als auch von W2.
Und dann sollte man sich erstmal klarmachen, dass sowas immer
existiert.
Also erstens gibt es überhaupt immer ein gemeinsames Präfix von zwei
Wörtern.
Wer ist für Ja?
Hand hoch.
Haben zwei Wörter immer mindestens ein gemeinsames Präfix?
Wer ist für Nein?
Denken Sie nochmal kurz nach und erinnern Sie sich an das leere Wort.
Das leere Wort ist immer Präfix von zwei Wörtern.
Also eins gibt es schon mal immer.
Das ist schön.
Die Länge von so einem gemeinsamen Präfix ist offensichtlich höchstens
so lang wie jedes von den beiden Wörtern, also höchstens so lang wie
das kürzere von den beiden.
Also die Länge ist immer klein-leicht das Minimum der beiden Längen.
Und nachdem Längen immer nur ganze Zahlen sein können, gibt es auch
eine maximale Länge.
Und das ist alles diskret.
Und das heißt, es gibt auch wirklich bei den gemeinsamen Präfixen
welche mit maximaler Länge.
Es gibt eine größte Länge, sodass Sie noch gemeinsame Präfixe finden.
Es kann Ihnen nicht passieren, dass Sie ein Präfix, gemeinsame Präfixe
der Länge 2, 2,5, 2,9, 2,99, 2,999, 2,999 finden.
Ja, die Längen gibt es nicht.
Also es gibt eine maximale, es gibt eine größte gemeinsame Länge.
Und wenn die Länge feststeht, dann das Präfix ist auch eindeutig
festgelegt.
Also es gibt tatsächlich immer das maximal lange gemeinsame Präfix.
Eindeutig.
Und was ist da der Fall?
Also erstens, wenn das längste gemeinsame Präfix so lang ist wie die
Länge des kürzeren der beiden Wörter oder dergleichen.
Naja, also es kann sein, dass V gleich W1 ist und W1 ist echt kürzer
als W2 oder die beiden W1 und W2 haben gleiche Länge und V hat auch
diese Länge.
Dann muss wohl W1 gleich W2 sein, wenn V genauso lang ist und es ist
gemeinsames Stück und andersrum W1 ist echt länger als W2 und W2 ist
das Präfix, wenn die Länge von V gleich dem Minimum der Längen ist.
Ja und dann definiert man einfach, also wenn man hier ein Wort wie W1
hat und das gemeinsame Präfix ist das W1 und weil es gemeinsames
Präfix ist, ist es auch Präfix von W2 mit anderen Worten W1 ist Präfix
von W2.
Dann definiert man halt W1 kommt vor W2.
Wenn die Längen gleich sind, dann offensichtlich muss W1 gleich W2
sein und dann können sie definieren, W1 kommt vor W2 und W2 kommt vor
W1.
Das ist das Gleiche.
Also Antisymmetrie ist kein Problem.
Und wenn W1 länger ist, dann sagen sie halt W2 kommt vor W1.
So ist das im Wörterbuch.
Das ist der erste Fall und der zweite Fall ist ja, das längste
gemeinsame Präfix ist echt kürzer als beide Wörter.
Kürzer als W1 und kürzer als W2.
Das sieht dann also irgendwie so aus.
Da gibt es also so ein gemeinsames Anfangsstück und dann gibt es eine
Stelle, da unterscheiden sich diese beiden Wörter W1 und W2.
Sowas muss es geben.
Sonst wäre, wenn das das gleiche Symbol wäre, wäre es ja noch bei dem
gemeinsamen Präfix dabei.
Ja, und wie sortiert man jetzt die Wörter W1 und W2?
Naja, man guckt diese beiden Symbole X und Y an und sagt, wie habe ich
es denn für die einzelnen Symbole definiert?
Und wenn X vor Y kommt, dann sage ich W1 kommt vor W2 und wenn Y vor X
kommt, dann sage ich W2 kommt vor W1.
Das ist das, was man im Wörterbuch macht.
Also erst so.
Und wozu führt das dann?
Ja,
hier steht das jetzt nochmal, was ich gerade schon gesagt habe.
Also das nennt man lexikografische Ordnung erster Art.
Also zum Beispiel Klaus kommt vor Klausur, weil Klaus ein Präfix von
dem längeren Wort Klausur ist.
Und Klausur kommt vor Übung, weil die erste Stelle, wo sich die Wörter
unterscheiden, das ist jetzt hier halt gleich der erste Buchstabe, da
kommt halt K, da steht einmal K, einmal Ü und K kommt vor Ü, behaupte
ich.
Also kommt im Wörterbuch dann Klausur vor Übung.
Gut.
Und wenn Sie so ein Wörterbuch haben, wo einfach nur endlich viele
Wörter drinstehen, dann ist das sehr hilfreich, weil das das Buch
handlich macht.
Und was dann passiert ist, es stehen halt als erstes alle Wörter drin,
die mit A anfangen und dann kommen alle Wörter, die mit B anfangen und
dann kommen alle Wörter, die mit C anfangen.
Und bei den Wörtern, also erst alle Wörter mit A, dann das Wort
meinetwegen B und dann die Wörter, die mit B anfangen.
Und bei den Wörtern, die mit A anfangen, halt erst die, die an der
zweiten Stelle, also abgesehen von dem Wort A alleine, erst die
Wörter, die an der zweiten Stelle ein A haben und danach Wörter, die
an der zweiten Stelle ein B haben.
Und genauso bei den Wörtern, die mit B anfangen, erst die, die an der
zweiten Stelle ein A haben, dann die, die an der zweiten Stelle ein B
haben.
Und bei denen dann halt erst die, die nach B, A, A an der vierten
Stelle ein A haben vor denen, die nach B, A, A an der vierten Stelle
ein B haben.
Und so können Sie, wenn ich Ihnen da endlich viele Wörter gebe, können
Sie die in die richtige Reihenfolge bringen.
Total simpel, mehr oder weniger.
Jedenfalls, wenn man es 20 Jahre gewohnt ist.
Gut.
Aber A, B, Stern enthält ja unendlich viele Wörter.
Und das heißt, also Sie haben da das leere Wort, das kommt vor dem
Wort, das aus einem A besteht.
Das kommt vor dem Wort, das aus zwei A's besteht.
Ein A ist Präfix von zwei A's.
Das kommt vor dem Wort mit drei A's, denn zwei A's sind Präfix von
drei A's.
Drei A's sind Präfix von vier A's.
Da können Sie der Reihe nach erstmal alle Wörter hinschreiben, die nur
aus A's bestehen, der Länge nach sortiert.
Und da haben Sie da so eine Kette.
Ja, eins ist kleiner gleich dem nächsten.
Und da haben Sie also schon unendlich viele Wörter.
Die bestehen alle nur aus A's.
Sie haben noch kein Wort hingeschrieben, das B's enthält.
Also wenn Sie alle Wörter überhaupt aus A, B, Stern ins Wörterbuch
schreiben würden, also schon die Wörter nur mit A's, würden unendlich
viele Seiten füllen.
Und Sie hätten noch kein Wort mit B gefunden, müssen Sie weit
blättern.
So, da haben Sie hier also einen Haufen Wörter und jetzt kann man sich
fragen, gibt es Wörter, das ist also eine Teilmenge von Wörtern, jetzt
können Sie sich fragen, hat diese Teilmenge ein Supremum?
Also überhaupt erstmal obere Schranken.
Also gibt es Wörter, die im Wörterbuch nach allen Wörtern kommen, die
nur aus A's bestehen?
Antwort, ja, jedes Wort, das ein B enthält, kommt danach.
Egal, welches Wort Sie nehmen, also meinetwegen B, A, A, B kommt
sicher nach den Wörtern, die mit A anfangen, weil es schon am ersten
Buchstaben hakt.
Und wenn Sie das Wort A, was nehmen wir denn mal, steht hier kein
Wort.
Stellen Sie sich vor, A hoch 7 B ist auch eine obere Schranke, denn
also die kurzen Wörter sind alle Präfix von A hoch 7 B und dann
irgendwann sind Sie bei A hoch 8 und wenn Sie das mit A hoch 7 B
vergleichen, haben Sie an der achten Stelle ein A statt eines Bs.
Dann kommt das Wort mit den acht A's vor dem Wort mit A hoch 7 B und
noch mehr A's, es bleibt dabei.
Also alle Wörter, die mindestens ein B enthalten, sind größer als
jedes Wort, das nur A's enthält.
Also alle Wörter, die ein B enthalten, sind obere Schranke für diese
Teilmenge aller Wörter, die nur A's enthält.
Aber, und jetzt wird es richtig komisch, diese Menge der oberen
Schranken, diese Menge aller Wörter, die größer sind als alle Wörter
nur aus A's, unter denen gibt es kein Kleinstes.
Also B zum Beispiel ist eine obere Schranke für die Wörter nur aus
A's, B kommt sicher dahinter.
Aber vor B, noch vor B, hier steht das Relationszeichen jetzt
umgekehrt, kommt das Wort A B, weil es nämlich mit A anfängt und nicht
mit B und das ist auch eine obere Schranke für die Wörter, die nur A's
enthalten, weil ein B drin ist.
Und vor A B kommt aber A A B und vor A A B kommt aber A A A B und
allgemein vor jedem Wort W, vor jedem Wort W, das irgendein B enthält,
kommt das Wort, wo Sie so viele A's hinschreiben, wie Buchstaben in B
sind und hintendran noch ein B.
Dann haben Sie garantiert, hier ein A, wo in W ein B steht, kommt das
echt vorher.
Das heißt, bei den Wörtern, die ein B enthalten, da können Sie immer
noch welche finden, die vorher kommen und vorher kommen und vorher
kommen und immer noch ein B halten und immer noch ein B haben, das B
ist nur immer weiter hinten.
Und dann haben Sie da so eine absteigende Kette und die hat kein
kleinstes Element.
Also, wenn Sie sich jetzt diese Wörter alle nochmal so im Wörterbuch
jetzt übereinander vorstellen, da kommen erst einmal abzählbar
unendlich viele Wörter nur aus A's, unendlich viele.
Pünktchen, Pünktchen, Pünktchen, das hört nie auf.
Und von unten, also die Wörter, die hinterher kommen mit B's nach
oben, das hört nie auf.
Und Sie können das noch ein bisschen weiter spinnen, nehmen Sie irgend
zwei Wörter, Sie werden feststellen, zwischen diesen beiden Wörtern,
von dem, das vorher kommt, haben Sie eine unendlich aufsteigende Kette
und von dem, das dahinter kommt, eine unendlich absteigende Kette und
die treffen sich nirgends.
Diese Ordnung ist total komisch, wenn Sie anfangen, darüber
nachzudenken, dass Sie unendlich viele Wörter haben und die alle
ordnen.
Das ist total merkwürdig.
Also insbesondere, Sie können hier nicht in irgendeinem natürlichen
Sinne davon reden, immer von einem Wort zum nächsten zu, also Sie
kommen von...
also nehmen wir mal an, Sie könnten immer davon reden, dass Sie von
einem Wort zum nächsten kommen, in irgendeinem Sinne, Sie werden nie
zu allen kommen, wenn Sie da in dieser Ordnung sich irgendwie
fortbewegen.
Egal, wo Sie anfangen, immer, Sie haben gleich so unendliche
aufsteigende und absteigende Ketten.
Nicht schön.
Deswegen, wenn man jetzt in einem Algorithmus irgendwie Wörter
durchgehen muss, sortiert man die lieber in eine andere Reihenfolge,
das heißt dann manchmal lexikografische Ordnung zweiter Art und da
sagt man also primäres Ordnungskriterium überhaupt ist erstmal, ich
gucke mir die Länge der Wörter an.
Und wenn zwei Wörter unterschiedlich lang sind, das kürzere kommt
zuerst.
Egal, was da drin steht an Buchstaben.
Kurze Wörter zuerst.
Also erst das leere Wort, Epsilon, dann die Wörter der Länge 1, A und
B, dann die Wörter der Länge 2, dann die Wörter der Länge 3, dann die
Wörter der Länge 4.
Und wenn zwei Wörter gleich lang sind, ja dann nehme ich die Ordnung
von eben zum Beispiel.
Und für Wörter gleicher Länge, da haben Sie aber immer nur endlich
viele und die sortieren Sie dann halt in der naheliegenden Art und
Weise.
Und dann haben Sie hier für jede Wortlänge ja immer nur endlich viele
Wörter und das heißt, Sie haben da überhaupt keine komischen
aufsteigenden Ketten ohne Supremum oder irgendetwas.
Wenn Sie irgendein Wort hinschreiben, dann kann ich Ihnen sofort
sagen, wie viele Wörter vorher kommen.
Interpretieren Sie die A´s und B´s.
Haben wir dyadische Zahldarstellungen gehabt?
Haben wir nicht gehabt.
Also man kann dann leicht aus dem Wort die Nummer ausrechnen.
Das wievielte Wort in der Reihenfolge das ist.
Und hier können Sie die Wörter durchnummerieren und jedes, Sie kommen
zu jedem Wort und jedes Wort kriegt eine Nummer ganz naheliegend.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, blablabla.
Bei der lexikografischen Ordnung erster Art, wenn Sie irgendwie
anfangen durchzunummerieren, da kommen Sie nie zu den Wörtern mit
einem B.
Da kommen Sie gar nicht hin.
Bei der hier schon.
Da kommen Sie zu jedem Wort nach endlich vielen Schritten garantiert.
Viel schöner für einen Informatiker.
Gut.
Ja, das muss man sich natürlich alles nochmal im Ernstfall.
Dann sollte man sich das mal genau angucken und überlegen, wo da noch
Behauptungen sind, die man dann vielleicht mal beweisen sollte.
Da muss man schon noch hier und da ein bisschen was tun.
Aber das sind alles keine besonders komischen Beweise oder so.
Das kann man alles in Ruhe hinschreiben.
Schritt für Schritt nichts, was die Welt bewegt.
So.
Und das war es, was ich Ihnen noch zu totalen Ordnungen sagen wollte.
Also totale Ordnungen sind Halbordnungen, wo es zusätzlich niemals
unvergleichbare Elemente gibt.
Das wird Ihnen an verschiedenen Stellen wieder über den Weg laufen,
Halbordnungen und Ordnungen.
Wie gesagt, zum Beispiel bei Semantik von Programmiersprachen, wenn
man es denn so definiert.
Was ist die Bedeutung einer Weilschleife, sozusagen ohne darüber zu
reden, wie oft die durchlaufen wird?
Da kann man mit schönen Ergebnissen zu Halbordnungen was machen oder
im Zusammenhang mit Testmustern, was auch immer das sein mag.
Was Sie sich klarmachen sollten zumindestens ist, also sobald man
unendlich viele Elemente hat, also selbst wenn es eine totale Ordnung
ist, die totale Ordnung kann ganz komische Eigenschaften haben, wie
eben gesehen bei lexikografischer Ordnung erster Art.
Das liegt halt daran, also bei unendlich vielen Elementen, also man
denkt ja immer so, man hat sich irgendwie dran gewöhnt, aber seien Sie
vorsichtig, es gibt da kuriose Konstruktionen.
Also man sollte schon wissen, die Definition von Halbordnung, totaler
Ordnung und dann im Zweifelsfall von irgendetwas nachrechnen können,
ja, das hat diese Eigenschaften, das ist eine Halbordnung, so was
sollte man schon mal können, vielleicht auch in der Klausur.
Womit ich bei dem letzten Teil für heute bin.
Noch ein paar Anmerkungen zu den Prüfungen, ein paar Anmerkungen
werden Sie vielleicht schon mal irgendwo gesehen, gehört, gelesen
haben, aber ein paar vielleicht auch noch nicht.
Das ist so grob chronologisch sortiert.
Also fangen wir an mit jetzt.
Jetzt stehen Sie vor der Aufgabe, zwei Prüfungen zu machen.
Also Sie sollten den Übungsschein erwerben und irgendwann eine Klausur
schreiben und bestehen.
Also jedenfalls die meisten von Ihnen.
Manche von Ihnen brauchen keinen Übungsschein, brauchen nur die
Klausur.
Aber zum Beispiel Bachelor Informatik oder so, die brauchen auf jeden
Fall beides.
Um es nochmal ganz deutlich zu sagen, Sie können die Klausur
schreiben, ohne den Übungsschein zu haben, so wie Sie auch den
Übungsschein machen konnten, ohne die Klausur schon bestanden zu
haben.
Also keins hat irgendwie Auswirkungen auf das andere.
Also es ist auch nicht so wie manchmal in anderen Vorlesungen.
Wenn Sie besonders viele Aufgaben in den Hausaufgaben, wenn Sie
besonders viele Punkte in den Hausaufgaben geschafft haben, dann
kriegen Sie bei der Klausur irgendwie ein, zwei, drei Punkte geschenkt
oder eine Notenstufe besser oder so etwas.
Das machen wir nicht.
Was müssen Sie tun, um die Prüfung zu bestehen?
Beim Übungsschein, wie gesagt, bei den Blättern 1 bis 6, Sie sollten
50 minus X1 Prozent aller Punkte haben und das X1 haben wir irgendwann
schon mal kommuniziert.
In Prozent weiß ich es nicht.
Und bei den Blättern 7 bis 12, jetzt müssen Sie auch 50 minus
irgendein X2 Prozent von Punkten haben und wir versprechen, dass das
X2 größer gleich 0 ist, nicht kleiner 0.
Und wahrscheinlich wird es auch wieder echt größer 0 werden.
Aber wie groß wir es machen, das sehen wir dann, wenn wir alle Punkte
haben und uns das so ein bisschen angeguckt haben.
Und bei der Klausur genau das Gleiche.
Sie haben die Klausur bestanden, wenn Sie mindestens 50 minus Y
Prozent aller erreichbaren Punkte erreicht haben.
Und wie groß das Y, also auch, wir versprechen wieder, Y ist größer
gleich 0 und garantiert nicht negativ.
Und wie groß wir das Y dann genau wählen, da guckt man sich dann auch
hinterher die Klausurergebnisse an.
Es kommt halt vor, ich erinnere mich, ich glaube, das war bei der
allerersten Klausur 2008.
Da habe ich in die Klausur eine Aufgabe reingemacht mit der Idee, ach,
da ist eine leichte Aufgabe, da kann man leicht noch zwei, drei Punkte
kriegen ohne viel Aufwand und so.
Und dann haben wir uns die Klausurergebnisse angeguckt und dann war
halt die durchschnittliche Punktzahl in dieser ganz einfachen Aufgabe,
wo man leicht ein paar Punkte noch erwerben konnte, 0,5 oder 4 oder
irgendwie sowas.
Die Aufgabe wurde offensichtlich ganz anders empfunden als von mir.
Und dann sagt man halt, ja, okay, also das war wohl falsch gestellt
oder falsche Erwartungen oder was auch immer.
Ich meine, wenn 90 Prozent der Leute irgendwie große Probleme mit
einer Aufgabe haben, dann liegt es wahrscheinlich doch nicht an den 90
Prozent, sondern an der Aufgabe.
Also wir behalten uns vor, da irgendwie etwas großzügig zu sein.
Aber Sie haben keinen Rechtsanspruch auf irgendetwas natürlich.
Gut.
Damit ich hinterher irgendwo eintragen kann, dass Sie die Prüfung
geschafft haben, müssen Sie sich für die Prüfung angemeldet haben.
Für den Übungsschein müssen Sie sich bis spätestens 26.
Februar 23.59 Uhr angemeldet haben.
Sie können sich davon auch wieder abmelden, aber das ist völlig
sinnlos, weil Übungsschein können Sie probieren, so oft Sie wollen.
Also Sie können natürlich da mal spaßhalber Abmeldungen versuchen, so
üben.
Wie geht das denn?
Aber vergessen Sie nicht, sich wieder anzumelden.
Ja, ja, wissen Sie, wir haben ja auch so unsere Erfahrungen.
Also auch mit dem Anmelden, ja.
Seien Sie vorsichtig.
Irgendwie ein bis zwei Personen pro Jahr kommen hinterher und sagen,
ich habe gedacht, ich habe mich angemeldet, aber dann habe ich
gesehen, da hätte ich ja noch ein zweites Mal irgendwo hinklicken
müssen und deswegen bin ich jetzt leider doch nicht angemeldet.
Und können Sie bitte noch...
Also bitte melden Sie sich selbst an, ja.
So, für die Klausur auch.
Die Klausur zur Erinnerung am 18.
März ab 14 Uhr.
Zum Ablauf, da habe ich... Upsa, wo bin ich jetzt?
Hier.
Für die Klausur müssen Sie sich anmelden.
Anmeldeende ist 11.
März 23.59 Uhr.
Für die Klausur wollen Sie sich vielleicht auch wieder abmelden.
Also die darf man halt nicht beliebig oft schreiben, sondern nur
zweimal.
Abmelden im Online-System geht bis 18.
März 0 Uhr 1.
Das ist eine Minute länger, als die Prüfungsordnung vorschreibt.
Da bin ich ganz großzügig.
Also bis Mitternacht vor der Klausur können Sie sich abmelden.
Aber wenn Sie sich früher abmelden, ist es schön für uns, weil wir
dann besser planen können.
Da ist eine Frage.
Oh, der 18.
März ist ein Mittwoch.
Das ist ganz schlecht.
Es kommt davon, wenn man Folien aus einem früheren Jahr kopiert.
Also die Klausur ist am 18.
März.
Das Rote stimmt, hoffe ich.
Aber es ist kein Dienstag.
Ja, es ist ein Mittwoch.
Mittwoch.
Dienstag ist falsch.
Sehen Sie, Leute machen Fehler, auch wir.
Womit wir gleich zur nächsten Folie kommen.
War da gerade noch eine Meldung irgendwo?
Nein.
So, also abmelden.
Online noch abmelden können Sie sich bis 18.
März 0 Uhr 1.
Danach können Sie sich auch noch abmelden.
Also die einzige andere Möglichkeit bitte.
Kommen Sie in einen der Hörsäle, wo die Klausur stattfinden wird,
vorzugsweise in den Hörsaal, in dem Sie geschrieben hätten und füllen
Sie einen Zettel aus, dass Sie sich abmelden und dann sind Sie auch
abgemeldet.
Und wer abgemeldet ist, nimmt nicht teil, kriegt keine Note, hat
keinen Versuch gemacht.
Es kann natürlich sein, dass Sie aus gesundheitlichen Gründen, die
erst irgendwie nach dem 18.
März 0 Uhr 1 eintreten, nicht zur Klausur erscheinen können.
Da hatten wir auch schon Fälle mit dem Fahrrad auf dem Weg zur Klausur
verunfallt oder eine Viertelstunde Nasenbluten schon im Hörsaal und
zwar so viel, wie ich das noch nie gesehen habe vorher.
Das war wirklich schlimm.
Also wenn sowas der Fall ist oder wenn Sie halt einfach krank zu Hause
im Bett liegen, besorgen Sie sich einen Attest vom Arzt, dass Sie
krank waren und bringen Sie das vorbei, aber bitte nicht fünf Wochen
später, sondern sobald Sie wieder laufen können.
Ich hoffe, das ist vorher okay und dann sind Sie halt auch abgemeldet.
Aktueller Stand von heute früh für die Klausur haben sich 713 Leute
angemeldet für den Übungsschein 668.
Mal sehen, wie viel das noch wird.
So, was dann?
Demnächst, falls Sie es noch nicht getan haben, gucken Sie, also wenn
Sie der Meinung sind, Sie gehören zu den 700, ich weiß nicht wie viel
und haben sich schon angemeldet, gucken Sie nochmal nach, ob Sie
wirklich angemeldet sind.
Wie gesagt, man macht mal einen Fehler und technische Systeme sind in
der Regel auch nicht fehlerfrei.
Meister Geier, schauen Sie nochmal nach, ob es stimmt, dass Sie
wirklich angemeldet sind.
Wenn Sie nicht angemeldet sind, dann kann ich in dem System nicht
eintragen, dass Sie den Übungsschein geschafft haben und ich kann auch
nicht eintragen, welche Note Sie haben.
Und wenn Sie nicht angemeldet sind, Sie werden die Klausur nicht
mitschreiben.
Sie dürfen noch nicht mal kommen und sagen, ich bin zwar nicht
angemeldet, aber eigentlich hätte ich mich anmelden können und ich
schreibe jetzt mal mit und so.
Ohne Anmeldung haben Sie keinen Sitzplatz zugewiesen bekommen und Sie
werden ohne Anmeldung nicht mitschreiben.
Machen Sie das bitte rechtzeitig.
Die Erfahrung zeigt, in einem Fall geht dann doch noch kurzfristig
irgendwas schief.
Also bitte rechtzeitig anmelden.
Und dann sind wir sozusagen unmittelbar vor der Klausur, mehr oder
weniger nahe vor der Klausur.
Wie Sie gerade gesehen haben, es schreiben nicht ganz wenig Leute mit,
dafür braucht man eine ganze Reihe Hörsäle.
Mal sehen, ob wir dieses Jahr mit zehn auskommen.
Letztes Jahr waren es, glaube ich, 15, aber das lag unter anderem
daran, dass ein großer kurzfristig nicht verfügbar war und dann wurden
die Leute aufgeteilt in mehrere kleine und so.
Gut, also ein Haufen Hörsäle und dann darf man sich nicht aussuchen,
wo man hingeht.
Sonst kommen alle hierher, dann habe ich hier 300 Leute, geht nicht.
Sondern wir legen das fest, wer in welchem Hörsaal schreibt und wie
die Aufteilung ist.
Das werden wir dann auf Ilyas Kund tun und eine E-Mail an alle Ilyas
Kursteilnehmer schicken, wo drinsteht, mit welcher Matrikelnummer man
wo, in welchem Hörsaal sich einzufinden.
Und gucken Sie, dass Sie das rechtzeitig wissen.
Und wenn Sie gelesen haben, in welchem Hörsaal Sie schreiben sollen,
dann als zweites finden Sie heraus, wo dieser Hörsaal ist.
Bei den Hörsälen, die wir letztes Jahr kurzfristig gekriegt haben,
waren welche dabei, von denen hatte ich keine Ahnung, habe ich noch
nie gehört gehabt.
Waren irgendwo da drüben im Chemieturm, aber nicht unten, sondern
irgendwo oben, ich weiß nicht, wie viel den Stock.
Und dann seien Sie rechtzeitig am richtigen Hörsaal.
Rechtzeitig heißt nach 20 Minuten vor der Klausur oder so was, 13.40
Uhr ist, glaube ich, eine ganz gute Zeit.
Wenn die Aufteilung auf Hörsäle aus irgendwelchen Gründen so ist, dass
Sie den Eindruck haben, Sie wissen nicht, wohin Sie gehen sollen.
Also wahrscheinlich im Wesentlichen, es wird Intervalle von
Matrikelnummern geben.
Und wenn wir einen Fehler machen, dann sind die Intervalle so, dass
dazwischen eine Lücke ist.
Und wenn Sie Pech haben, haben Sie dann womöglich, wenn wir was falsch
machen, eine Matrikelnummer, die in keinem Intervall ist.
Dann bitte gleich laut schreiend zu mir kommen und sagen, in welchen
Hörsaal soll ich denn gehen?
Diese Aufteilung in die Hörsäle werden wir aber relativ kurz vor der
Klausur machen.
Damit Hypothese sich schon noch wieder möglichst viele, die sich
abmelden wollen, auch wirklich abgemeldet haben.
Damit wir mit möglichst wenig hypothetischen Teilnehmern arbeiten
müssen, damit wir möglichst wenig Hörsäle brauchen und möglichst wenig
Aufsichtspersonal.
Ich meine, jeder Hörsaal heißt zwei bis drei Leute, die jetzt über
zwei Stunden sich die Beine in den Bauch stehen.
Je weniger, umso besser.
Und wenn Sie dann am richtigen Hörsaal hoffentlich sind, toi toi toi,
dann werden Sie da eine Liste finden an der Tür, wo genau dran steht,
wer mit welchem Namen wo im Hörsaal sitzt.
Da haben Sie dann kleine Zettel.
Also da werden dann irgendwie Sitze gekennzeichnet sein, wo jemand
sitzt.
Das wird nur maximal jeder dritte Platz sein und nur in jeder zweiten
Reihe in jedem Hörsaal.
Und da müssen Sie halt den richtigen Hörsaal finden.
Die Plätze sind typischerweise durchnummeriert.
Da vorne links mit 1 geht es an und dann 2, 3, 4, 5 bis der ganz erste
Reihe rechts.
Und dann in der übernächsten Reihe von rechts nach links zurück und
dann wieder in der fünften von links nach rechts, so
Schlangenlinienform.
Da müssen Sie mit binärer Suche oder sonst irgendwas Ihren Platz
finden.
Und wenn Sie Ihren Namen nicht auf der Liste an der Hörsaaltür finden,
dann es werden Leute hier sein, natürlich, die dann Aufsicht führen in
der Klausur.
Dann gehen Sie dahin und sagen, ich finde meinen Platz nicht.
Und dann machen die irgendwas mit Ihnen, also sagen entweder ja,
nichts Schlimmes.
Gehen Sie in den Hörsaal nebenan eine Etage höher, irgendwie so, wenn
Sie Benz und Daimler verwechselt haben oder sowas.
Und aber bevor Sie die, bevor Sie da quer über den halben Campus
rennen müssen, um den richtigen Hörsaal noch zu erwischen, dann wird
man Ihnen vielleicht sagen, ja, da ist noch ein freier Platz.
Setzen Sie sich dahin.
So, dann fängt die Klausur an.
Ach so, nein, dann irgendwann.
Also ist klar, wo sind die Sitzplätze?
Und jeder hat hoffentlich seinen Platz gefunden und setzt sich dahin
und hat aber vorher bitte folgende Dinge getan.
Wichtig.
Erstens Handys ausschalten komplett.
Handys, die während der Klausur klingeln, werden nicht sehr freundlich
behandelt.
Sie haben bitte keine Jacken, keine Taschen, irgendetwas an Ihrem
Platz.
Das stapelt sich alles hier vorne so in den jeweiligen Hörsälen oder
am Rand.
Sie dürfen nicht irgendwelche Zettel, wie das in manchen Klausuren der
Fall ist, bei sich haben.
So ein DIN A4 Blatt beliebig klein beschrieben, Vorder- und Rückseite
mit irgendetwas.
Sowas dürfen Sie nicht benutzen.
Wörterbücher bitte auch nicht, denn da müssen wir kontrollieren, was
in den Wörterbüchern drin steht.
Wie sollen wir das machen?
Überhaupt auch nicht nur keine Handys, sondern überhaupt nichts, was
Strom verbraucht.
Es gibt ja auch mittlerweile Handys, die sind als Armbanduhr getarnt.
Das bitte auch nicht.
Komplett aus, weg.
Was Sie haben, ist ein Stift.
Den dürfen Sie bitte selber mitbringen.
Schreiben Sie nicht mit Rot und nicht mit Grün.
Das machen wir.
Was zu essen, was zu trinken und ganz wichtig, das hätte ich hier
vielleicht auch nochmal mit hinschreiben sollen.
Auf jeden Fall bitte Studierendenausweis mitbringen.
Und noch irgendeinen anderen Ausweis.
Kann nicht schaden.
Und dann um 14 Uhr fängt also hier jemand an zu erzählen.
Ja.
Also mit welcher Sorte Stift darf man schreiben?
Also bitte nicht mit Bleistift.
Kugelschreiber oder Füller ist mir recht.
Sie werden zwar hinterher irgendwann nochmal die Klausur in die Finger
kriegen, aber dann dürfen Sie keine Stifte in der Nähe haben oder so.
Also Veränderungen sollten dann hoffentlich ausgeschlossen sein.
So 14 Uhr geht's los.
Dann sagt erst jemand mal schönen guten Tag, erzählt Ihnen nochmal
genau, wie das jetzt alles abläuft.
Dann werden die Klausuren ausgeteilt, kriegt jeder ein Exemplar.
Dann werden die Klausuraufgaben nochmal durchgegangen, irgendwie
vorgelesen, soweit man das vorlesen kann.
Und dann geht es los.
Das wird dann also tendenziell so um 14 Uhr 15 plus minus irgendetwas
sein.
Und ab da haben Sie dann 120 Minuten Zeit.
Und ab da dann genau 120 Minuten später müssen Sie alle spätestens den
Stift aus der Hand legen.
Gucken Sie sich die alten Klausuren an.
Das sind immer so irgendwas zwischen 5 und 8 Aufgaben für irgendeine
Definition von Aufgabe.
Es gibt irgendeine Anzahl Punkte.
Also wir geben uns keine Mühe.
Es gibt auch Klausuren, da gibt es jedes Mal genau 60 Punkte oder
genau 120 Punkte oder genau 100 Punkte oder irgend sowas.
Die Mühe machen wir uns nicht.
Es gibt einfach Punkte.
Üblicherweise ist die Punktzahl irgendwo zwischen 40 und 50.
Und wie gesagt, wir versprechen 50 Prozent reichen, vielleicht auch
ein bisschen weniger.
So, am Ende werden die Klausuren...
Ah, Papier.
Ja, also Sie kriegen, also wenn Sie die Klausur kriegen, dann ist das
ein Stapel Papier mit so sieben bis acht Blättern.
Und auch als abgesehen vom Deckblatt, wo vorne drauf irgendwie Sie
dann Ihren Namen schreiben und die Punktzahlen draufgeschrieben
werden.
Grob gesagt auf jedem Blatt eine Aufgabe und Sie haben dann den Rest
der Seite, wo die Aufgabe steht und die nächste Seite und hintendran
wahrscheinlich nochmal ein Blatt, das total leer ist, um da Ihre
Lösungen hinzuschreiben.
Und wenn Sie mehr Papier brauchen, dann melden Sie sich bei der
Klausur, dann kriegen Sie noch zehn Blätter, die Sie vollschreiben
können, wenn Sie unbedingt wollen.
Also Papier haben wir, müssen Sie nicht mitbringen.
So, und dann wird das also alles wieder eingesammelt und gezählt und
wenn sichergestellt ist, dass so viele Klausuren eingesammelt wurden,
wie Teilnehmer im Hörsaal waren.
Ja, ich habe auch schon mal erlebt, dass jemand nicht abgegeben hat
und dann hinterher kam, oh, ich habe vergessen abzugeben.
Also dann wird eingesammelt und dann sind erst mal wir dran mit
Korrektur.
Am 18.
März ist die Klausur, nach der Klausur an dem gleichen Tag fangen wir
nicht mehr an mit korrigieren.
Da bin ich froh, wenn ich den Formalkram noch erledigt kriege.
Und dann, das ist also Mittwoch, die Klausur haben wir gelernt,
Mittwoch, dann Donnerstag, Freitag.
Im Wesentlichen werden wir uns erst mal zu jeder Aufgabe irgendwie 50
Klausuren, 50 Lösungen oder sowas angucken und schauen, was passiert
ist und so einen groben Rahmen aufschreiben, wie wir denken, wie man
das korrigieren sollte, was so die Standardfehler waren.
Und dann in der Woche drauf mit mehr Leuten werden wir dann versuchen,
diese Klausuren möglichst schnell zu korrigieren.
Wenn es so läuft wie letztes Jahr, aber das ist kein Versprechen, dann
sind wir am Ende der nächsten Woche.
Das wäre dann also der 27.
März fertig.
Aber vielleicht schaffen wir es auch nicht ganz.
Aber ich hoffe, dass wir bis Ende März fertig sind mit dem
Korrigieren.
Und ja, also haben Sie Verständnis bei 700 Klausuren oder wie viel das
am Ende dann auch sein werden.
Es dauert halt einfach ein bisschen.
So, dann werden wir in dem Online-System, wo sich praktisch alle
angemeldet haben, die vorläufigen Ergebnisse veröffentlichen.
Also da sieht dann jeder sein vorläufiges Ergebnis.
Und dann kommt die Klausur Einsicht.
Oh, jetzt muss ich aber noch ein bisschen Gas geben.
Klausur Einsicht heißt, wir werden sie grob aufteilen nochmal nach
Matrikelnummern in Gruppen und dann sagen, wird es so zwei,
zweieinhalb Tage, drei Tage geben, wer wann kommen kann zur Klausur
Einsicht.
Das sind also immer so Gruppen von, keine Ahnung, 20, 25 Leuten.
Und dann können Sie nochmal angucken, was Sie in der Klausur
aufgeschrieben haben, wie das korrigiert worden ist.
Sie können nochmal kontrollieren, ob wir alle Punkte richtig
zusammengezählt haben, ob wir auch nicht irgendwo was übersehen haben.
Sie können auch noch anfangen, mit uns zu diskutieren, ob man nicht
hier und da vielleicht doch einen halben Punkt mehr, weil dann hätte
man gerade noch eine bessere Note und so.
Und die ersten, für die es Klausur Einsicht geben wird, sind die, die
die Klausur zum zweiten Mal schreiben, damit die rechtzeitig wissen,
ob sie es bestanden haben oder nicht.
Und damit dann rechtzeitig die, die es auch zum zweiten Mal nicht
geschafft haben, wissen, dass eine mündliche Prüfung auf sie zukommt.
Und dann kennen wir mit denen dann alles Weitere.
Und wie gesagt, also wir legen grob fest, wann Sie zur Klausur
Einsicht kommen sollten.
Die Alternative ist, wir sagen einfach hier morgen ab neun.
Das gibt es auch bei vielen Klausuren.
Und dann haben Sie halt spätestens halb zehn eine Schlange auf dem
Gang, die, wenn es dumm läuft, irgendwann 30, 40, 50 Leute lang ist.
Das ist für Sie totale Zeitverschwendung.
Das ist für Sie irgendwann blöd, weil die Luft auf dem Gang total
schlecht wird.
Und das ist für uns total blöd, weil wir ständig den Stress haben,
dass alle Plätze voll sind und man hat nicht wirklich Ruhe, nochmal
mit dem einen oder anderen irgendwas ein bisschen detaillierter zu
besprechen.
Ja, deswegen so ein bisschen eingeteilt, damit nicht so große
Wartezeiten sind und für uns das zwischendurch auch mal ein bisschen
entspannt ist.
Jo, das ist aber auch die letzte dieser Folien.
Was kommt dran?
Naja, bin ich schon hier und da gefragt worden.
Also das, was in der Vorlesung dran war mit den bekannten Ausnahmen.
Also wir werden dieses Kapitel über Dokumente, wir werden keinen
fragen, wie ist die Syntax, um in LaTeX eine Aufzählungsliste
hinzuschreiben oder irgendwie etwas.
Da ist noch eine Frage, ja?
Ah, wann ist die Klausureinsicht?
Also erstens, nachdem sie korrigiert wurde.
Das heißt also ganz banal, wir sind dann wahrscheinlich Anfang April.
Und zweitens aber ja, schon möglichst bald.
Also ich weiß jetzt nicht mehr, wie das letztes Mal war.
Also für die Wiederholer, das würde ich auf jeden Fall Anfang April
machen, weil man dann ja auch die mündlichen Prüfungen möglichst noch
vor dem nächsten Vorlesungszeit machen will.
Jetzt sage ich mal pauschal nicht rechtsverbindlich erste April Hälfte
oder sowas, aber so ganz grob.
Ja, also wie man Dokumente hinschreibt in LaTeX oder HTML, muss keiner
wissen.
Das, was wir jetzt zum Beispiel heute ganz zum Schluss gemacht haben.
Also Sie haben überwiegend...
Das, was wir heute gemacht haben, da hat keiner mehr ein Tutorium
dazu.
Zudem, was wir letzten Mittwoch gemacht haben, haben einige auch schon
kein Tutorium mehr gehabt, wenn das schon am Montag oder Dienstag war.
Also das sind Themen, da werden wir jetzt nicht massiv drauf rumreiten
in der Klausur.
Natürlich die Definition von Äquivalenzrelation.
Also die taucht in mindestens drei Kapiteln auf.
Also das sollten Sie schon wissen, was das ist.
Ja, das ist ein fundamentaler Begriff.
Ansonsten orientieren Sie sich so ein bisschen an den Aufgaben, die
ich so in früheren Jahren gestellt habe und vielleicht tendenziell
eher nicht die Aufgaben von 2008 und 2009.
Ich weiß gar nicht mehr, was ich da suche.
Keine Ahnung, müsste ich mir vielleicht selber mal anschauen.
Aber so was in den letzten Jahren halt so üblicherweise drankam.
Das ist jedenfalls ein Anhaltspunkt.
Wir haben noch keine Klausuraufgaben gemacht.
Ich kann Ihnen noch nicht sagen irgendwie, was kommt dran, was kommt
nichts dran.
Wird auch für uns noch eine Überraschung sein.
Ah, eine Sache noch genau.
Falls Sie schon im dritten Semester sind, Orientierungsprüfung und da
irgendwelche Probleme haben, vielleicht auch mit dem Übungsschein,
kommen Sie vorbei, dass wir uns das nochmal angucken.
So, das war's.
Schönen Dank, dass Sie bis zum Ende da waren.
Ich wünsche Ihnen viel Erfolg bei den Prüfungen, die jetzt dann so auf
Sie zukommen.
Dankeschön.