So, schönen guten Morgen.
Ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente Algorithmen.
Ich nehme an, dass wir heute ganz durchkommen durch die letzten
Folien, sodass wir nächste Woche nicht mehr den Termin brauchen.
Am nächsten Dienstag bin ich sowieso nicht da.
Wir hätten einen Sondertermin am nächsten Montag machen müssen, den
ich auch schon eingeplant habe.
Aber ich denke, wir kommen heute ganz durch.
Dann haben Sie etwas früher damit Schluss.
Wir haben auch in der Vorlesung ein paar Fragen gestellt.
Wir haben uns mit verteilten Algorithmen beschäftigt.
Ich habe Ihnen einiges über die Probleme, die es gibt bei verteilten
Algorithmen, die Aufgaben, die dort eine Rolle spielen.
Besondere Aufgaben, die nur im Zusammenhang mit verteilten Algorithmen
auftreten, die wir uns genauer angucken.
Wir haben auch ein paar typische Beispiele angeschaut, wo verteilte
Algorithmen eingesetzt werden, eigentlich immer stärker.
Und wir haben dann gesehen, welche Kosten die verteilten Algorithmen
machen, dass sie dort vor allen Dingen die Anzahl der Nachrichten,
auch die Länge der Nachrichten anschauen.
Ich habe ein besonderes Konsensproblem, nämlich die Auswahl oder die
Wahlalgorithmen oder auch Leader Election vorgestellt.
Wir haben dort verschiedene Beispiele betrachtet, insbesondere den
einfachen Algorithmus, bei dem man zunächst hat man gesehen, dass es
nicht möglich ist, einen deterministischen, vollständig verteilten und
symmetrischen Algorithmus zu finden, der tatsächlich ein
Auswahlproblem löst, weil dann alle in der gleichen Art arbeiten
würden.
Es könnte keiner irgendwie ausgewählt werden.
Wenn man die Identität ausnutzt, hatten wir einen einfachen
Algorithmus gesehen, der im schlechtesten Fall quadratische Anzahl von
Nachrichten hat und im besten Fall durchaus weniger.
Wir hatten dann eine Variante betrachtet, einen probabilistischen
Ansatz, wo wir tatsächlich in der Lage sind, ohne Berücksichtigung der
Identität der einzelnen Prozessoren eine Auswahl zu treffen, indem wir
zumindest annehmen, dass die unterschiedliche Seeds haben für einen
Zufallszahlengenerator, über den man dann eine Auswahl trifft.
Wir haben uns anschließend angeschaut, die Möglichkeiten, den Aufwand
für den Nachrichtenaustausch zu reduzieren, indem man den Algorithmus,
den ich zu Anfang vorgestellt habe, etwas modifiziert und immer weiter
optimiert.
Das erste war, dass man sich immer das Minimum der erhaltenen
Nachrichten anschaut.
Das ist ein sehr einfacher Ansatz.
Das zweite war, dass man eine synchrone Arbeitsweise hat, was eine
ziemlich starke Annahme ist.
Aber wenn es synchron ist, kann man Runden zählen und damit die Anzahl
der Nachrichten deutlich reduzieren, weil man auf einmal dann so
vorgeht, dass man die Nachrichten verzögert, also den Versand um
mehrere Runden verzögert, sodass man die Nachrichten, die sich auf
große Zahlen beziehen, länger verzögert, als die Nachrichten, die sich
auf kleine beziehen, sodass die kleinste Zahl, die rumgeschickt wird,
dann am schnellsten rumläuft und gar nicht so viele Nachrichten mit
größeren Zahlen, die sowieso keine Chance haben, ausgewählt zu werden,
dann überhaupt rausgeschickt werden.
Und die dritte Verbesserung war dann, dass man den Inhalt der
Nachricht durch die Zeit kodiert.
Eine interessante Idee, dass man nur noch eine Anfangs- und
Endnachricht schickt und die Zeit dazwischen oder die Anzahl der
Runden dazwischen dann hernimmt als den Wert, der praktisch übertragen
werden sollte.
Und wir kamen dann eben insgesamt auf einen Aufwand, der es erlaubte,
mit O von N Bits, also mit der linearen Anzahl von Bits in einem
synchronen Ring tatsächlich eine Auswahlentscheidung zu treffen, also
runter von der quadratischen Anzahl von Nachrichten, bei dem
allerdings nicht-synchronen Algorithmus, runter auf eine lineare
Anzahl, was schon eine deutliche Verbesserung ist.
Und das, was wir heute machen werden, ist das, was hier steht.
Wir wollen jetzt eine untere Schranke bestimmen für den Aufwand für
das Leader Election Problem in Ringen.
Das wird ein bisschen kompliziert, das ist ein längerer Beweis.
Die Annahmen, die wir machen, sind jetzt wieder, dass wir eine
asynchrone Arbeitsweise haben.
Wir können nicht Runden zählen.
Der Ring ist gerichtet, also genau wie sonst auch.
Wir nehmen an, dass wir hier in einer Richtung Nachrichten schicken
können.
Jeder kennt seine Nachfolger und seinen Vorgänger.
Die Reihenfolge bleibt dadurch erhalten.
Die Prozesse kennen nicht die Größe des Rings.
Das heißt, wenn wir eine untere Schranke machen, machen wir die für
beliebige Ringgrößen.
Die einzelnen Prozessoren wissen nicht, also zu Beginn des Verfahrens
jedenfalls nicht, wie viele Elemente in dem Ring tatsächlich vorhanden
sind.
Dann nehmen wir an, dass die einzelnen Nachrichten nur eine konstante
Anzahl von Prozessnummern speichern können.
Also ich kann nicht alle Identitäten in eine Nachricht reinpacken,
sondern ich kann nur eine oder zwei Nummern dort reinpacken.
Und jede Prozessnummer ist unterschiedlich.
Das heißt, wir haben jeweils log n Bits.
Das heißt, die gesamte Nachrichtengröße ist auch jeweils log n Bits.
Dann ist eine Annahme, dass jeder Prozessor im Prinzip Initiator sein
kann.
Das kann sein, dass alle n Prozesse, die hier eine Wahl ausführen,
dass die alle einen solchen Prozess anstoßen können.
Das spielt später eine Rolle bei der Abschätzung des Aufwandes.
Die Behauptung ist, dass jetzt jeder Algorithmus, der vollständig
verteilt ist und symmetrisch zur Bestimmung des Anführers in einem
Ring der Größe n, im schlechtesten Fall und im Mittel mindestens Omega
n log n Nachrichten braucht.
Und jetzt kommt also schon dann die Idee, wie kann man dafür eine
untere Schranke bestimmen.
Wodurch wird dann das Verhalten eines Prozessors bestimmt?
Dadurch, dass ich habe einen Prozess, der bekommt Nachrichten,
irgendeine Nachricht m, schickt eine Nachricht m' raus.
Die Nachricht m', die er rausschickt, hängt davon ab, in welchem
Zustand der Prozess selber ist und was er bereits alles gesehen hat.
Wie viele Nachrichten bei ihm schon eingetroffen sind.
Zu Beginn ist er in irgendeiner Startkonfiguration, die bestimmt, dass
er jetzt Initiator geworden ist und die Nachricht rausgeschickt hat.
Und die anderen bekommen Nachrichten und werden dadurch angestoßen,
was zu tun.
Und dann kommen weitere Nachrichten und sie werden also diese ganzen
Nachrichten, die sie bekommen, können sie natürlich intern abspeichern
und werden also die Nachrichten, die sie rausschicken, beeinflussen.
Das heißt, die Anfangskonfiguration bestimmt die versandten und
empfangenden Nachrichten und jeweils die versandten bzw.
empfangenden Nachrichten.
Und jetzt wird das charakterisiert dadurch, dass wir mit jeder
Nachricht, die hier verschickt wird, eine Spur hinzufügen, eine Folge
von Prozessnummern.
Das sind alle Prozesse, die diese Nachricht beeinflusst haben.
Also, welche Prozesse haben die Nachricht schon gesehen und dann
weitergeschickt?
Sie erinnern sich, dass wir ja dort einzelne Zahlen durchgeschickt
haben und jetzt bestimmen wir die untere Schranke über Eigenschaften
der Menge möglicher Spuren.
Das heißt, wenn ich weiß, wie viele Spuren ich mindestens brauche,
weiß ich auch etwas über die Mindestzahl an Nachrichten, die
verschickt werden müssen.
Und es ist klar, wenn ich eine Nachricht habe, die meinetwegen hier
eine gewisse Zeit rumgelaufen ist, dann sind alle diese, wenn das hier
Prozesse 1, 2, 3, 4 sind, dann wird die Nachricht, die hier rausgeht,
irgendein M-Strich, wird dann die Spur haben 1, 2, 3, 4.
Es wird aber auch eine Nachricht geben, die hat die Spur nur 1, 2, 3
oder eine, die hat nur die Spur 1, 2 oder eine, die hat nur die Spur
1.
Weil die ja alle erstmal dahin gekommen sein müssen.
Das heißt, wenn ich eine Spur habe, dann sind die ganzen anderen, die
ganzen Präfixe auch Spuren von anderen Nachrichten.
Und darüber werden wir eine untere Schranke ableiten.
Also, das ist die wesentliche Idee.
Wir argumentieren gleich über solche Spuren von Nachrichten, das
heißt, ich kann auch sagen, das sind Traces, die Folgen von Prozessen,
die eine Nachricht beeinflusst haben.
Jetzt kommen eine Reihe Definitionen.
Ich werde immer die wesentlichen, die wir brauchen, dann auf der
jeweiligen Folie nochmal zeigen.
Das eine ist die Menge D.
Eigentlich ist das nicht mnemonisch sinnvoll.
D ist halt einfach so definiert.
Menge aller Folgen von Prozessnummern, ohne Wiederholungen.
Wir nehmen also an, wir haben irgendwie N Prozesse.
Und wenn wir alle Folgen von Prozessnummern ohne Wiederholungen
betrachten, sind das also irgendwelche Folgen S1 bis Sk und jedes Si
ist eine Prozessnummer.
Das heißt, wenn wir so eine Folge haben, dann sind eben alle solche Si
und Sj unterschiedlich da drin.
Es kann eben sein, dass jede einzelne Prozessnummer ist dort auch mit
drin.
Folgende Länge 2, folgende Länge 3, folgende Länge N natürlich auch.
Und jetzt betrachte ich für jede solche Folge von Prozessnummern die
Menge aller zyklischen Verschiebungen.
Wieso spielt das eine Rolle?
Stellen Sie sich vor, Sie haben hier einen solchen Ring.
Nehmen wir mal an, wir haben hier 1, 2, 3, 4, 5, 6 als Nummern.
Dann sind sicherlich mögliche Spuren jetzt, wenn ich mir das anschaue,
was dann auftauchen kann.
Also es wäre eine mögliche Spur, wäre einfach nur die 1.
Oder 1,2.
Oder 1,3.
Oder 1,4.
Oder 1,5.
Oder 1,6.
Das wären also immer länger werdende Spuren.
Es könnte aber auch sein, dass eine Nachricht gar nicht beim Knoten 1
begonnen hat, sondern eine andere die hat begonnen beim Knoten 2.
Und damit die einmal rumläuft, muss natürlich diese Nachricht am Ende
auch noch bei der 1 gewesen sein.
Und das ist jetzt eine zyklische Verschiebung der Folge, die wir
vorher hatten.
Das war hier nur 1,2,3,4, 5,6.
Das haben wir die Folge.
Oder wenn sie beim Knoten 4 angefangen hätte, würde hier stehen 4,5,6,
1,2,3.
Für die Nachrichten, die von irgendeiner Position aus einmal ganz
rumgelaufen sind.
Und wir erinnern uns, bei Leader Election Algorithmen muss natürlich
eine Auswahl darauf basieren, dass Informationen über alle Prozesse,
die beteiligt sind, tatsächlich in eine Nachricht eingeflossen sind.
Denn sonst könnten wir nicht denjenigen bestimmen mit der kleinsten
Identität.
Es müssen alle besucht worden sein.
Das heißt, es muss mindestens eine Nachricht geben, die einmal ganz
rumgelaufen ist.
Und von welcher Stelle aus sie einmal ganz rumgelaufen ist.
Das weiß man da vornherein nicht.
Jeder Prozess kann Initiator sein.
An jeder Stelle könnte eine minimale Prozessnummer stehen.
Ich habe hier eine aufsteigende Reihenfolge gewählt.
Das heißt, ich kann mir also irgendeine Folge von Zahlen hernehmen.
5,1,3,2,4,6 zum Beispiel.
Und auch davon, wenn das eine Folge von Prozessnummern wäre, in
irgendeinem Ring, dann werden eben auch hier die zyklischen
Verschiebungen 3,2,4,6, 5,1, wäre auch eine mögliche Spur durch so
einen Ring.
Die einmal rumläuft.
Jetzt weiß ich aber nicht von vornherein, wie groß meine Ringe sind.
Oder wie groß mein Ring ist.
Es könnte ja sein, dass ich einen Ring habe, der hat nur vier
Elemente.
Und wenn hier irgendwie 2,1,3 zum Beispiel, da wäre sicherlich 4,2,1,3
eine mögliche Spur.
Aber es wäre eben auch 3,4,2,1 eine Spur einer Nachricht, die in dem
Ring ganz rumgelaufen ist.
Die einzelnen Prozesse wissen ja nicht, wie groß die Anzahl der
Teilnehmer ist.
Und die können aus der Spur alleine nicht feststellen, ob das jetzt
schon eine vollständige Nachricht ist oder nicht.
Das merken sie erst, wenn ihre eigene Prozessnummer irgendwann
wiederkommt.
Also, die zyklischen Verschiebungen haben was damit zu tun, dass wir
eine Aussage machen müssen über Ringe beliebiger Größe, deswegen
beliebige Folgenlängen.
Und die zyklischen Verschiebungen, es kann von irgendeiner Stelle aus
eine Nachricht losgelaufen sein.
Zyklische Verschiebungen einer solchen Folge.
Ich schaue mir irgendeine Reihenfolge der Prozesse im Ring an, und
dann können von irgendeiner Stelle aus Nachrichten anfangen, und
daraus entstehen Spuren, die zyklische Verschiebungen dieser einen
Reihenfolge sind.
Und jetzt betrachte ich eine Menge E, die erschöpfend heißt, oder
exhaustive im englischen Original.
Und ich sage, dass diese Menge, es heißt also erschöpfend, wenn sie
erstens präfix abgeschlossen ist.
Das macht auch Sinn in diesem Zusammenhang.
Wenn ich eine Spur betrachte, dann ist jedes Anfangsstück natürlich
auch eine Spur.
Und ich möchte solche Mengen von Spuren haben, die zu solchen
Nachrichten passen, oder solchen Algorithmen passen.
Deswegen, wenn ich das, was vorkommen kann, charakterisieren möchte,
muss ich mit einem mit einer Spur TU auch das T als Spur mit drin
haben in der Menge.
Jeden Präfix.
Und ich sage, dass das E die Menge D, also die Menge D waren ja alle
Folgen von Prozessnummern, zyklisch überdeckt.
Das heißt, wenn ich irgendeine Folge von Prozessnummern habe, aus D,
dann ist mindestens eine zyklische Verschiebung also Cyclic Shift,
deswegen steht das CS, irgendeine zyklische Verschiebung von S ist in
E.
Das heißt, diese Menge E, die muss nicht alle zyklischen
Verschiebungen enthalten, aber soll also jede Spur oder soll praktisch
jeden Ring auch mit charakterisiert haben.
Und über zyklische Verschiebungen habe ich damit auch alle anderen
Folgen dann erreicht.
Also in D sind ja auch diese ganzen zyklischen Verschiebungen einzelne
Folgen von Prozessnummern.
Und jetzt nehme ich irgendeine Nachricht her, jetzt habe ich hier eine
kleine Änderung in der Notation gemacht, um Irritation zu vermeiden.
Die Spur nenne ich jetzt Sigma von M.
Die Spur ist definiert dadurch, dass es der Prozessor, also der Name
des Prozessors ist, oder des Prozesses ist, falls P noch keine
Nachricht bekommen hat, falls also P, Prozess P, eine initiale
Nachricht schickt.
Die erste Nachricht schickt, dann ist das nur eine Spur P. Nur die
Nummer dieses Prozesses.
Und wenn der Prozess schon Nachrichten erhalten hat, dann gibt es eine
Spur S, die bereits mitgeliefert wurde, das ist die Spur der
Nachricht, die man empfangen hat, und da wird einfach das P noch dran
gehängt.
Deswegen haben wir also dann sukzessive, genau wie ich das ja
angedeutet habe, immer Folgen von Prozessnummern.
Das ist also eine ganz naheliegende Art, das zu modellieren.
Und wenn ich jetzt eine solche Spur habe, wenn S eine solche Spur ist,
eine Nachricht, dann nenne ich die Nachricht auch eine S-Nachricht.
Eine Nachricht, die also durch alle Prozesse, die in dieser Folge S
drinstehen, durchgelaufen ist.
Und wenn ich einen Ring durch eine Folge von Prozessnummern
beschreibe, wie hier oben zum Beispiel die 123456, oder hier unten war
es die 4213, dann ist das ein S-Ring.
Also ein 4213-Ring.
Weil dieses S den Ring vollständig charakterisiert.
Diese Begriffe brauchen wir im Folgenden.
Wir brauchen auch zwei Mengen.
Eine Menge P von S und E.
Das ist die Anzahl der Präfixe, also E ist eine Teilmenge von D,
irgendeine Teilmenge von D.
Eine Teilmenge von solchen Spuren.
Die Anzahl der Präfixe einer zyklischen Verschiebung von S.
Ich habe hier irgendeine Folge, meinetwegen die 4213.
Dann ist also jeder Präfix davon 421, 422 und die 4 sind ja solche
Präfixe.
Aber ich muss ja die zyklischen Verschiebungen betrachten.
Die zyklische Verschiebung wäre zum Beispiel jetzt 2134.
Da sind natürlich 213, 21 und 2 auch Präfixe.
Aber von zyklischen Verschiebungen.
Und ich schaue mir an, wie viele solche Präfixe einer zyklischen
Verschiebung von S gibt es in der Menge E.
Das ist die Anzahl der Präfixe von zyklischen Verschiebungen der Folge
S in E.
Das nächste schränkt diese Anzahl ein auf alle Präfixe, die eine feste
Länge K haben.
Also alle Präfixe der Länge 2 oder 3 oder was immer.
Und diese Mengen brauchen wir nachher, um abzuschätzen, wie viele
Nachrichten verschickt worden sein müssen.
Denn die Anzahl der Präfixe sagt mir etwas über die Anzahl der
Nachrichten, die vorgekommen sein müssen.
Weil jeder Präfix einer Spur einer Nachricht entspricht, die geschickt
worden sein muss.
Und jetzt kommt also der Beweisgang.
Wir nehmen uns einen beliebigen Leader Election Algorithmus her.
Wir wollen eine untere Schranke für den schlechtesten Fall für die
Anzahl der Nachrichten hier hernehmen.
Sogar auch für den mittleren Fall.
Jetzt nehmen wir uns her eine Menge EA.
Das sei die Menge aller Folgen S, für die bei Ausführung von A auf
einem S-Ring eine S-Nachricht versandt wird.
Also, ich habe den Algorithmus A.
Beliebiger Leader Election Algorithmus, der kann auf jedem beliebigen
Ring angewandt werden.
Jetzt schaue ich mir irgendeinen beliebigen Ring an und die Folge der
Nummern hier ist S1, S2 und so weiter bis, sagen wir mal, SN.
Damit ein Leader Election Algorithmus zum Ende kommen kann, muss es
mindestens eine Nachricht geben, die einmal ganz rumgelaufen ist.
Und jetzt schaue ich mir eben alle solche Folgen an, die zu Spuren
gehören von Nachrichten, die einmal rumgelaufen sind.
Und einmal rumgelaufen heißt, ich habe einen S-Ring mit einer S
-Nachricht.
Das heißt, es muss in dem Fall, ein S-Ring, hier fange ich an bei S1
bis SK, muss es also eine Nachricht geben, die einmal ganz rumgelaufen
ist.
Das sei die Menge EA.
Und jetzt müssen wir uns ein bisschen Eigenschaften anschauen dieser
Menge EA.
Wir werden nachher argumentieren über die Anzahl der Präfixe von
Spuren S, die in der Menge EA enthalten sind.
Und da betrachte ich dann eben auch, wir werden sehen, dass das EA
eine erschöpfende Menge ist, die also genau für alle relevanten Folgen
zumindest eine zyklische Verschiebung enthält.
Erste Aussage, die wir machen.
Wir betrachten drei Folgen aus D und ein Teilwort S von T und U.
Also wir haben hier drei Folgen.
T und U sind zwei Folgen von Zahlen und S ist eine Teilmenge oder ein
Teilwort, das in beiden Folgen vorkommt.
Jetzt ist die Aussage, wenn bei Ausführung von A auf einem T-Ring, das
ist also hier der T-Ring.
Also wir betrachten jetzt nicht nur die Folgen, sondern die beiden als
Ringe, weil sie ja, wir nehmen an, wir haben jetzt also ein T-Ring
oder auch ein U-Ring.
Wenn bei Ausführung von A auf einem T-Ring eine S-Nachricht verschickt
wird, also eine Nachricht, die hier begonnen hat und bis dahin
gelaufen, also die dort zuerst verschickt wurde und dann bis zu dem
Ende gekommen ist, dann wird bei Ausführung dieses Algorithmus A auf
einem U-Ring eine solche S-Nachricht auch verschickt.
Warum?
Weil der Algorithmus ja nur, also die Nachricht, die eine Spur S hat,
ist ja nur beeinflusst durch genau diese Prozesse, die in der Folge
von S vorkommen und durch nichts anderes, und das kann, da der
Algorithmus ja deterministisch ist, wird er sowohl auf diesem Ring als
auch auf dem Ring die gleiche Nachrichtenfolge produzieren.
Er ist ja durch nichts anderes beeinflusst, er hat noch nichts anderes
von dem Ring gesehen, das was außerhalb von S ist, ist nicht
eingeflossen und deswegen ist eben der ganze Teil, der hier grün und
da grau gekennzeichnet ist, der hat die Nachrichten, die die Spur S
haben, nicht beeinflusst.
Beweis ist eigentlich klar.
Wenn das S1 bis SK ist, der Versand einer S-Nachricht durch Prozess
SK, der verschickt diese S-Nachricht.
Im T-Ring kann nur von den Anfangszuständen der Prozesse S1 bis SK,
die also hier drin sind, die auch dort drin sind, beeinflusst worden
sein und da diese Anfangszustände im T-Ring und im U-Ring identisch
sind, wird auch im U-Ring eine S-Nachricht verschickt.
Also das geht nicht anders.
Und jetzt wird behauptet, diese Menge EA, also die Menge aller Folgen,
für die bei Ausführung von A auf einem S-Ring eine S-Nachricht
verschickt wird, ist eine erschöpfende Teilmenge.
Damit es eine erschöpfende Teilmenge ist, muss das zunächst mal eine
präfix abgeschlossene Menge sein.
Das heißt, wenn A bei Ausführung auf einem S-Ring eine S-Nachricht
verschickt.
Genau, das ist die S-Nachricht.
Ich verschicke bei Ausführung auf einem S-Ring eine S-Nachricht.
Also ich habe hier irgendeinen Ring und da ist jetzt diese S-Nachricht
drin.
Entschuldigung, das muss ich sofort löschen, um Sie nicht zu
irritieren.
Das stimmt ja gar nicht.
Ich behaupte ja folgendes.
Hier steht bei Ausführung auf einem S-Ring.
Das heißt, ich habe einen vollständigen Ring und da ist von dort bis
dort habe ich hier S1 bis SK stehen.
Dann muss natürlich, wenn eine solche Nachricht da rumgelaufen ist,
muss auch für jeden Präfix, muss A auch für jeden Präfix T von S eine
T -Nachricht schicken.
Denn die kann ja nur rumgelaufen sein, wenn für jeden Präfix immer bis
dahin, muss ja auch eine Nachricht verschickt worden sein.
Sonst hätte ja die längere gar nicht entstehen können, die mit der
längeren Spur.
Und wenn ich also einen solchen Präfix T habe, der dort drin ist, dann
wird natürlich auf einem T-Ring, einem kleineren Ring, der diesem
Präfix entspricht, auch eine solche Nachricht verschickt.
Das haben wir gerade beim NEMA vorher gesehen.
Der T-Ring hat ja das T auch als Teil, bei beiden taucht das T auf,
also muss auf einem T-Ring auch eine T-Nachricht verschickt werden.
Also ist das E A, die Menge aller Folgen ist, für die bei Ausführung
von A auf einem entsprechenden Ring eine S-Nachricht versandt wird,
gilt das also auch für diese Spur T.
Das heißt, es gibt einen Ring T.
Diese T-Nachricht wird dann auch auf eine T-Nachricht verschickt.
Also ist das T auch in dem E A mit drin.
Das ist ja die Behauptung, die wir hatten.
Das heißt, jeder Präfix einer solchen Folge, die in E A drin ist, ist
auch wieder in E A drin.
Das nächste, was wir zeigen müssen, ist, dass das E A die Menge D
zyklisch überdeckt.
D waren alle beliebigen Folgen von Prozessnummern, beliebig groß.
Wir betrachten also für ein beliebiges S aus D eine Ausführung von A
auf einem S-Ring.
So, da habe ich also einen S-Ring und
da wird das A ausgeführt.
Da muss aber mindestens ein Prozess eine Nachricht bekommen haben, die
einmal rumgelaufen ist.
Er muss festgestellt haben, wer Leiter ist.
Mindestens ein Prozess stellt fest, wer Leiter ist.
Und er muss deswegen eine Nachricht bekommen haben, die einmal
rumgelaufen ist.
Und das heißt aber, er muss eine Nachricht bekommen haben, deren Spur
die gleiche Länge hat wie die Anzahl, also wie die Größe dieses
Ringes.
Kann von irgendwo losgelaufen sein.
Also ist die Spur von M aus einer zyklischen Verschiebung dieser Folge
S, des S-Ringes.
Ich kann also auch einen Ring beschreiben durch genau diese Spur.
Dann wird nämlich auf einem Sigma-von-M-Ring eine Sigma-von-M
-Nachricht verschickt.
Das steht ja gerade hier, dass eine Sigma-von-M-Nachricht verschickt
wurde.
So, das ist genau diese Aussage.
Also hier jetzt nochmal angedeutet, es ist egal, an welcher Stelle
jetzt so eine Nachricht losgelaufen ist.
Ich kann, wenn das hier losgelaufen ist, an der Stelle, dann, wenn das
hier der Anfangspunkt ist, dann ist es eben ein Sigma-von-M-Ring.
Und eine Nachricht muss dort rumgelaufen sein.
Also das ist halt einmal rum, das heißt, dass es ein Sigma-von-M-Ring
ist.
Und damit ist das Sigma-von-M in Ea mit drin.
Ist aber auch eine zyklische Verschiebung von S.
S kann ja sein, dass das irgendwo an einer anderen Stelle begonnen
hat.
So, jetzt kommt Lemma 3.
Bei Ausführung von A auf einem S-Ring verschickt der Algorithmus A
mindestens so viele Nachrichten wie durch P von S E A gezählt werden.
Also P S E A war die Anzahl der Präfixe von dieser Folge S, die in Ea
enthalten sind.
Also, Menge der Präfixe einer zyklischen, nicht nur die Präfixe von S,
sondern Präfixe von zyklischen Verschiebungen von S.
Das waren die beiden Begriffe hier, das Ea, eben nochmal hier
angegeben, alle Folgen, für die bei Ausführung von A auf dem S-Ring
eine S-Nachricht verschickt wird, also eine Nachricht, die ganz rum
geht.
Und jetzt habe ich in P von S E die Präfixe aller möglichen zyklischen
Verschiebungen von S gezählt.
Das heißt, zu jedem solchen Präfix gehört mindestens eine Nachricht.
Und damit habe ich eben, ist eigentlich schon klar, dass das so sein
muss.
Beweis.
Wenn ich ein beliebiges S habe und T aus Ea Präfix einer zyklischen
Verschiebung R von S ist, also ich habe meinen Ring S, der beginnt
irgendwo hier oben, ich habe den Ring, ich habe das R, das beginnt
irgendwo anders, eine zyklische Verschiebung von R und davon ein
Präfix, dann ist das irgend so ein Abschnitt.
Und dann sendet der Algorithmus auf dem T-Ring, das ist das T, auf
einem T-Ring, eine T-Nachricht, also auch auf dem R-Ring.
Und der R-Ring ist ja mit dem S-Ring identisch, ich gucke mir nur
einen anderen Anfang einer Nachricht an.
Also wird für jedes solche T mindestens eine T-Nachricht auf dem S
-Ring verschickt, das heißt die Zahl der Nachrichten ist mindestens P
von S Ea.
Also das ist relativ einsichtig, wenn man sich die Definition einmal
klar gemacht hat.
Für jeden Präfix einer Charakterisierung der Folgen von Prozessen in
einem Ring, für jeden Präfix muss eine Nachricht verschickt worden
sein, genau die werden gezählt durch P von S Ea.
Und jetzt nutze ich diese Eigenschaften aus, ich habe jetzt eine
endliche Menge von, also ich habe N Prozessidentitäten, N ist also
größer als 0, nicht leer, das sind Prozessnummern, und ich betrachte
alle möglichen Permutationen.
Also ich muss eine Aussage über beliebige Ringe machen können und die
Reihenfolgen der Prozessnummern auf diesem Ring auftauchen, ist ja
völlig beliebig.
Ich muss für jeden Ring etwas sagen, also für alle Permutationen
dieser Prozessnummern.
Und dann ist eben die Behauptung, dass die mittlere Anzahl der
Nachrichten für Leader Election auf einem gerichteten Ring der Größe
N, Omega von N log N ist.
Also mittlere Anzahl der Nachrichten, ich habe jetzt beliebige Ringe,
und für beliebigen Ring sage ich, die mittlere Anzahl der Nachrichten
ist Omega N log N.
Das ist natürlich auch eine untere Schranke für den schlechtesten
Fall.
So, wie können wir das beweisen?
Diese Formeln muss man erstmal jetzt lesen und dann verstehen, was da
steht.
Das hier ist die mittlere Anzahl, also Average, mittlere Anzahl der
Nachrichten, die der Algorithmus A verschickt, auf dieser Menge von
Identitätsnummern, 1 bis N zum Beispiel.
Endliche Anzahl, also N verschiedenen Nummern.
Es gibt in Fakultät verschiedene Permutationen, wenn wir den mittleren
Fall betrachten wollen, dividieren wir also das, was da rauskommt,
durch N-Fakultät.
Und wie viele Nachrichten werden verschickt für jede Permutation?
Wir hatten gesagt, für jede Permutation, also für jeden Ring, ist
dieses P von SEA gerade die Anzahl der Nachrichten, die mindestens
verschickt werden müssen.
Es kann sein, dass viele Nachrichten ganz rumgelaufen sind.
Es muss aber mindestens eine gewesen sein.
Das heißt, dieses P von SEA hat dann genau diese Menge der Nachrichten
gezählt.
Und die entsprechenden Spuren waren hier in dem EA drin.
Also das S definiert ein Ring, und das P von SEA gibt an, wie viele
Nachrichten für diesen Ring verschickt worden sein müssen, mindestens.
Das können wir uns jetzt ein bisschen genauer angucken.
Wir hatten das P definiert, wir hatten aber auch das nochmal
eingeschränkt auf genau diejenigen Präfixe, die die Länge K haben.
Also schauen wir uns jetzt alle Nachrichten der Reihe nach an, die
Spuren der Länge K haben, für K gleich 1 bis N.
Die sind ja alle gezählt, also dieses P von SEA ist natürlich, das
waren alle Nachrichten, jetzt habe ich das aufgeteilt auf die
Nachrichten Länge 1, 2, 3 und so weiter bis N.
Und jetzt kann ich die beiden Summen hier vertauschen.
Ich habe eine Summe für K gleich 1 bis N.
Und betrachte hier die Summe aller Anzahlen von Nachrichten mit einer
Spur der Länge K, die für eine Permutation S verschickt worden sein
müssen.
Einfach nur vertauscht, die beiden Summen.
Nichts Besonderes.
Wenn ich mir jetzt ein S anschaue,
ich habe ein solches S, das läuft hier einmal in einem Ring rum, und
ich betrachte ein Präfix der Länge K, dieses Stück T hier, Länge von T
ist K.
Wie viele Präfixe der Länge K von S?
Für S gibt es ein Präfix der Länge K.
Jetzt kann ich aber zyklische Verschiebungen betrachten.
Das heißt, ich kann dieses T an einer beliebigen Stelle beginnen
lassen.
Ich habe N verschiedene Stellen, also habe ich N verschiedene Präfixe
der Länge K von zyklischen Verschiebungen von S.
Oder wenn ich mir das S hier insgesamt hinmale, dann ist eben jedes
Stück der Länge K ein möglicher Präfix der Länge K für eine zyklische
Verschiebung.
Es gibt genau N verschiedene Präfixe der Länge K von zyklischen
Verschiebungen von S.
Jetzt habe ich aber hier über alle Permutationen das betrachtet.
Also auch hier in dieser Menge
betrachte ich ja alle Permutationen.
Da treten also für jede Permutation N verschiedene Präfixe auf.
Natürlich sind die nicht alle unterschiedlich.
Also wenn ich zum Beispiel K gleich 1 habe, dann werden einfach nur
die einzelnen Prozessnummern gezählt.
Und die treten jeweils N-Fakultät mal auf.
Die treten bei jeder Permutation natürlich auf.
Das heißt, ich habe hier sehr viele Nachrichten gezählt, die sich auf
identische Spuren beziehen.
Das ist eine zu große Abschätzung.
Das muss ich berücksichtigen.
Das heißt, jetzt von diesen N-Fakultät mal N-Vorkommen von Präfixen,
die hier in der Summe sind, werden in dieser Summe alle gezählt, die
auch Elemente von Ea sind.
In Ea sind aber nur die drin,
bei denen ich also eine zyklische Verschiebung habe, oder bei Versand
auf einem entsprechenden Ring auch genau eine solche Nachricht
verschickt wird.
Und diese Menge Ea überdeckt die Menge D zyklisch.
Das hatten wir zu Anfang gesehen.
Das heißt, das Ea enthält für jeden Präfix t der Länge k mindestens
ein Element aus der Menge der zyklischen Verschiebungen von t.
Wie viele zyklische Verschiebungen gibt es für ein Präfix der Länge k?
Genau k verschiedene zyklische Verschiebungen.
Wenn ich also dort mindestens ein Element drin habe, dann heißt das,
ich zähle hier also nicht alle möglichen verschiedenen, sondern ich
habe immer nur ein Element da drin.
Das heißt, das ist größer gleich, dieses n Fakultät mal n, das waren
alle, die gezählt wurden, oder die hier praktisch auftauchten, durch
k, weil ja in dem Ea nur jeweils für solche, also nur immer eines von
dieser zyklischen Verschiebung drin ist.
Ich dividiere durch n, das waren n Fakultät mal n, die hier
aufsummiert wurden.
Ich habe in dem Ea jeweils nur ein Element aus der Menge der
zyklischen Verschiebungen jeweils drin, das heißt, das dividiere ich
jeweils durch k.
Jetzt kann ich das n Fakultät herauskürzen, das n kann ich vorziehen
und ich habe eine Abschätzung, die sagt, das Ganze ist größer gleich n
mal Summe k gleich 1 bis n 1 durch k.
Und diese Summe, k gleich 1 bis n 1 durch k, die haben Sie schon mal
gesehen, als ich die mittlere Anzahl der Vergleiche bei Quicksort
abgeschätzt habe.
Das ist nämlich gerade gleich hn, der entenharmonischen Zahl.
Und wir wissen, dass das hn aus Omega von log n ist, also benötigt man
im Mittel n mal log n Nachrichten.
Und damit ist dieser Satz schon bewiesen.
Etwas kompliziert.
Aber ich denke, man kann es nachvollziehen, wenn man sich diese
Definition der Folgen oder dieser wesentlichen Begriffe dann nochmal
anschaut.
Das waren hier diese Mengen, das e a, die erschöpft die Menge aller
Folgen, für die bei Ausführung von a auf einem s-Ring eine s-Nachricht
versandt wird.
Und dann eben hier diese beiden Zählungen von Präfixen, von zyklischen
Verschiebungen der Folge s oder eben Präfixen der Länge k von
zyklischen Verschiebungen der Folge s.
Und die hatten eben genau etwas immer damit zu tun, die
charakterisieren eben immer gerade, dass ein Anführer gewählt worden
sein kann.
Und ich muss mindestens solche Nachrichten dort drin haben.
Es kann sein, dass ich mehr habe, aber mindestens diese Anzahl muss
enthalten sein.
Das war also unsere Argumentation und damit ist diese untere Schranke
bewiesen.
Haben wir also am Ende nochmal eine untere Schranke bewiesen.
Sie sehen, dass es nicht gerade einfach ist, untere Schranken zu
zeigen, wo man eben über alle beliebigen Algorithmen argumentieren
muss.
So.
Es ist klar, dass das auch eine untere Schranke für den schlechtesten
Fall ist.
Und man kann auch für andere Strukturen, also bidirektionalen Ringen
oder Größe des Ringes bekannt, kann man auch diese untere Schranke
zeigen.
Also für einen Ring ist das eine untere Schranke.
NlogN Nachrichten.
In asynchronen Ringen.
Bei synchronen Ringen, hatten wir gesehen, können wir auf N-Bits
runterkommen.
Durch unsere Techniken die Nachrichten etwas anders zu kodieren.
Und zu verzögern.
Jetzt haben wir aber auch andere Verbindungsnetze.
Also ich habe irgendein beliebiges Netz und irgendwie sind die hier
verbunden.
Ich hatte also hier irgendwelche Nachbarn.
Irgendwie sind die verbunden.
Und jetzt ist die Frage, wie macht man das auf einer beliebigen
Struktur?
Wie kann man dort ein kleinstes Element auswählen?
Das ist im Prinzip die Minimumsbestimmung.
Also Liderelection auf einem solchen beliebigen Netz.
Da ist die Idee, einen sogenannten Echo-Algorithmus zu verwenden.
Was ist ein Echo?
Ich habe hier irgendjemanden stehen, der etwas rausruft und hier ist
irgendeine Wand.
Und das geht also darüber und irgendwann kommt es wieder zurück.
Hier habe ich jetzt einen Prozess, der startet einen Algorithmus, der
möchte also einen Liderelection-Algorithmus anstoßen.
Und der sendet, genau wie beim Ring, eine Nachricht, mit einer Wake-up
-Identifikation dabei.
Denn die anderen wissen ja noch nichts davon, dass er jetzt einen
Liderelection machen möchte.
Und schickt seine Prozessnummer mit.
Wann kommt das Echo?
Dieser Algorithmus läuft so, dass er einen Broadcast macht.
Der schickt eine Nachricht raus.
Der schickt eine Nachricht raus, diese Nachricht nenne ich mal M,
überall an seine Nachbarn.
Und die schicken diese Nachricht weiter an alle Nachbarn, von denen
sie diese Nachricht nicht bekommen haben.
Also M, M, M.
Er hat sie bekommen von diesem Prozess, aber nicht von dem, schickt
dem also diese Nachricht auch nochmal.
Und so läuft das hier durch.
Jeder schickt also die Nachricht,
an alle die, von denen er die Nachricht noch nicht bekommen hat.
Von dem hätte er sie zwischendurch schon bekommen.
Das heißt, dem würde er sie, nee, er würde die nochmal hier
hinschicken.
Aber von dem, von dem er diese Nachricht bekommen hat, direkt, da
schickt er sie nicht zurück.
Und dann gibt es Prozesse, die haben im Prinzip eine Nachricht
bekommen, und haben von allen anderen auch schon die Nachricht
gesehen.
Das heißt, das geht von da aus nicht weiter.
Es gibt keine weiteren Prozesse, die diese Nachricht noch nicht
bekommen haben.
Und die initiieren dann ein Echo.
Und bei dieser Initierung des Echos, da wird die aktuell kleinste
Prozessornummer mitgeschickt.
Das heißt, die kleinste Nummer aus allen empfangenen Nachrichten, sage
ich mal, oder auch Echos, die man bekommen hat, und der eigenen
Nummer.
Man bekommt ja, wenn man eine Nachricht rausgeschickt hat, dann wartet
man, dass hier ein Echo zurückkommt.
Da muss ein Echo zurückkommen.
Der hat hier irgendwann festgestellt, er darf jetzt ein Echo schicken,
er schickt ein Echo zurück, und dann hat der hier ein Echo bekommen.
Es muss aber von dem hier auch ein Echo zurückkommen.
Und entsprechend wird er dann hier ein Echo zurückschicken, von dem
muss er auch ein Echo zurückkriegen.
Das heißt, er wird von allen ein Echo bekommen haben, und schickt dann
dieses Echo weiter an denjenigen, von denen er zuerst die Nachricht
bekommen hat.
Und schickt die kleinste Nummer aus allen empfangenen Echos und der
eigenen Nummer dann zurück.
Und der Initiator bekommt irgendwann von allen Nachbarn ein Echo
zurück, und da steht jeweils die kleinste Nummer drin, die auf dem Weg
des Echos zu diesem Knoten aufgesammelt worden ist.
Und damit hat der Initiator am Ende Informationen über die kleinste
Zahl, die überhaupt im Netz aufgetraut ist.
Das heißt, er kann dann aus allen Echos den Leiter bestimmen und kann
dann in einer weiteren Runde, die er rausschickt,
diese ausgewählten Nummer allen bekannt machen.
Und das wäre dann nochmal ein Broadcast, kein weiteres Echo.
Ich habe hier M, das ist die Anzahl der Kanten.
Bei diesem Verfahren laufen über jede Kante zwei Nachrichten.
Das heißt, ich habe zwei M-Nachrichten.
Jeder Prozess dieser N-Prozesse kann im Prinzip ein Initiator gewesen
sein.
Deswegen habe ich N mal einen solchen Prozess, einen Echo-Algorithmus,
der da abläuft, die praktisch nebenläufig da ablaufen.
Und das Ganze muss zweimal passieren, weil ich auch noch alle
informieren muss darüber.
Deswegen habe ich hier kleiner gleich 2N mal 2M Nachrichten insgesamt.
Das ist also Lead Election in einem beliebigen Verbindungsnetz.
Kann man ein bisschen verbessern, indem man sagt, wenn ich also jetzt
den Algorithmus anstoße, merke ich mir erst mal die eigene Identität,
die eigene Prozessnummer als aktuelles Minimum.
Und wenn der Initiator P von einem anderen eine Nachricht bekommt, ein
Wake -up-Cue oder ein Echo-Cue, dann macht er Folgendes.
Wenn das Cue größer ist als das aktuelle Minimum, dann heißt das, er
hat schon eine Nachricht gesehen, die eine kleinere Nummer hier
verschickt hatte.
Das heißt, er braucht diesen Algorithmus gar nicht weiterzuführen,
sondern stößt selbst einen Echo-Algorithmus an mit seiner eigenen
Nummer.
Also mit dieser Nummer Min, wenn das eine eigene war, falls nicht
schon ein solcher Prozess rausgeschickt worden ist, falls er noch
keinen angestoßen hat.
Wenn das Cue, das er bekommen hat, kleiner ist als dieses Minimum, das
er bisher gesehen hat, beteiligt er sich an diesem Echo-Algorithmus
und setzt sein eigenes Minimum auf diesen kleineren Wert Cue.
Und wenn das Cue gleich dem Minimum ist, dann heißt das, dass es eine
Nachricht, die er bekommt, die sich auf den von ihm selbst
angestoßenen Echo-Algorithmus bezieht, weil das die kleinste Zahl ist,
die er bisher gesehen hat.
Und er hat also dann eine weitere Nachricht bekommen mit diesem
minimalen Wert.
Und wenn ein Prozessor von allen Nachbarn Min-Nachrichten hat,
deswegen den Zähler hochzählen, dann schickt er dieses Echo-Min an den
Vorgänger.
Und damit ist also die Anzahl der Nachrichten etwas reduziert.
Es wird nicht jeder Wake-up oder jeder leaderless-Algorithmus, der
angestoßen ist, tatsächlich ausgeführt, sondern der wird irgendwann
abgebrochen, wenn ein Prozess feststellt, der hier angestoßene
Algorithmus kann gar nicht zum Ziel führen, weil er sich auf größere
Zahlen bezieht, als man selbst schon gesehen hat.
Das heißt, insgesamt wird die Anzahl der Nachrichten reduziert, es
bleiben aber immer noch N mal M Nachrichten übrig.
Darunter kann man nicht kommen, im schlechtesten Fall.
Weil ich im schlechtesten Fall immer noch N Prozesse habe, die einmal
einen solchen Algorithmus angestoßen haben und je nach Verteilung der
Nummern in diesem Netz habe ich dann immer noch insgesamt N mal M
Nachrichten, die dort rumlaufen.
Damit haben wir hier ein Algorithmus für ein beliebiges Netz und jetzt
machen wir noch eine untere Schranke für beliebige Netze.
Wie viel brauche ich mindestens?
Das waren jetzt N mal M für das Verfahren, das ich gerade vorgestellt
habe, für diesen Echo-Algorithmus.
Eine untere Schranke kann ich jetzt auch noch bestimmen, nämlich bei N
Knoten und M Kanten brauche ich mindestens Omega von M Nachrichten.
Also für jede Kante muss eine Nachricht gelaufen sein.
Wenn ich einen Ring habe in dem Netz, dann weiß ich, die untere
Schranke für einen Ring ist N log N.
Das heißt, ich kann nicht besser sein als N log N, aber ich muss
mindestens M Nachrichten rausschicken.
Wenn das M größer ist als N log N, ist das die untere Schranke.
Wenn es kleiner ist als N log N, dann ist N log N die Schranke.
Das erste ist klar, wenn das Netz einen Ring enthält oder sogar ein
Ring ist, dann habe ich nur N Kanten, habe trotzdem untere Schranke N
log N.
Das haben wir schon vorgezeigt.
Und jetzt nehmen wir an, wir haben also ein beliebiges Netz und wir
nehmen an, wir kommen mit weniger als M Nachrichten aus.
Wenn das möglich wäre, dann baue ich mir jetzt einen neuen Graph aus,
in dem ich zeige, der kann dann keinen Anführer bestimmen, keinen
eindeutigen.
Und zwar ist das hier mein Graph G, in dem über eine Kante UV keine
Nachricht geschickt wird.
Ich habe da also eine Kante gehabt von U nach V.
Das ist hier der Anführer, der gewählt wurde.
Jetzt erzeuge ich einen neuen Graphen, in dem ich zwei Kopien von G
mache, das ist also mein Graph insgesamt hier, das ist mein G'.
Zwei Kopien und da, wo vorher nur eine Kante war zwischen U und V,
füge ich jetzt einen neuen Knoten hinzu, W, und ich verbinde diese
beiden Knoten W in den beiden Kopien.
Das heißt, jetzt habe ich einen Graphen insgesamt, der zusammenhängend
ist, und ich habe einen Anführer, also in unzusammelnden Graphen kann
ich natürlich keinen eindeutigen Anführer wählen, das ist klar, muss
zumindest zusammenhängend sein.
Und jetzt lasse ich den Algorithmus laufen, der in dem Graphen G mit
weniger als M Nachrichten ausgekommen ist.
Den kann ich jetzt auch hier drauf laufen lassen.
Da der aber keine Nachricht von U nach V geschickt hatte, der alte
Algorithmus, weder von U nach V oder von V nach U, kann der
Algorithmus, der darauf abläuft, gar nicht merken, dass hier zwischen
U und V ein neuer Knoten jetzt eingefügt wurde.
Das heißt, der kann das gar nicht bemerken, dass hier eine Verbindung
ist zu der Kopie von G, und das heißt, der Algorithmus würde diese
beiden Knoten als Anführer auswählen.
Dann hätte ich zwei Knoten.
Wir würden gar nicht merken, dass das nicht der Anführer ist, nicht
ein eindeutiger Anführer ist für den gesamten Graphen.
Der läuft in beiden Kopien gleichzeitig, hat keine Nachricht über U, V
geschickt, merkt das nicht, damit habe ich einen Widerspruch.
Es kann nicht sein, dass über irgendeine Kante in dem Graphen keine
Nachricht verschickt wurde, die erforderlich war für die Auswahl des
Anführers.
Über jede Kante muss mindestens eine Nachricht geschickt worden sein.
Man kann genau diese Schranke erreichen, ist aber ziemlicher Aufwand.
Das Buch ist bei uns in der Literaturliste drin.
Da ist der Algorithmus angegeben, der im Wesentlichen einen minimalen
Spannbaum für einen Graphen bestimmt und dazu eine Nachricht über jede
Kante schickt.
Aus dem minimalen Spannbaum kann man dann einen Anführer wählen.
Damit haben wir eine untere Schranke, auch für diesen Fall, und sind
damit fertig.
Das ist alles, was ich Ihnen über verteilte Algorithmen erzählen
wollte.
Ich habe ja gesagt, es gibt noch viele verschiedene Probleme, die man
betrachten kann, z.B.
Synchronisation oder auch Uhren-Synchronisation und eine Reihe
weiterer Probleme, aber ich will das dabei belassen, weil ich im
Wesentlichen das nur andeuten wollte, dass man hier eine ganz andere
Art von Problemen betrachten muss.
Wenn ich also jetzt irgendeinen Algorithmus laufen lassen möchte
mit irgendeinem verteilten Algorithmus auf irgendeinem Graphen, da
muss ich sehen, dass ich durch diese typischen Probleme, die durch
verteilte Algorithmen erzeugt werden, nicht in der Ausführung meines
Algorithmus eingeschränkt werde.
Denn diese Probleme, die wir betrachtet haben, das sind alles
Probleme, die was mit dem Overhead zu tun haben bei der Ausführung auf
einem verteilten System.
Also deswegen braucht man dort effiziente Arten, das zu machen und da
habe ich Ihnen einen kleinen Eindruck von gegeben.
Damit sind wir mit dem Teil fertig und ich komme schon zu den letzten
Informationen zu dieser Vorlesung.
Nämlich zu abschließenden Bemerkungen.
War dieser Beweis gerade eben, war das einigermaßen verständlich?
Sie wagen nicht zu antworten.
Bitte?
Ja, das nehme ich an.
Das können Sie nochmal nachsehen.
Insofern hören Sie meine Erklärungen dazu, können Sie sich mehrfach
anhören und dann sollte es eigentlich möglich sein, das mitzukriegen.
Ja, abschließende Bemerkung.
Wir haben viele verschiedene Themen behandelt, die hier so ein
bisschen angedeutet sind.
Achso, richtig.
Die Zeit der Klausur, das ist für Sie auch wichtig, die habe ich noch
nicht.
Heute wird die Anzahl der Teilnehmer wahrscheinlich verschickt, die
Sie angemeldet haben und dann kann ich die Zeit mitteilen.
Also das hier ist nach wie vor offen, Ort ist auch noch offen.
Dann habe ich hier etwas einfach reingeschrieben.
Herr Mauser, stimmt das?
Fragestunde.
Machen Sie am 22.
noch eine Fragestunde oder machen Sie die vorher?
15.7., Fragestunde zu den Themen.
Also meine Mitarbeiter geben dann noch mehr Erläuterungen oder
Hinweise, wie es üblicherweise gefragt wird.
Es wird natürlich alles abgefragt, was wir hier gemacht haben, ist ja
klar.
Aber so die Art der Fragen, ich denke, Sie haben durch die Übungen
einen Hinweis oder wissen sie einigermaßen, welche Art der Fragen man
erwarten kann.
Aber es kommen dann noch ein bisschen mehr Erläuterungen.
Also wenn Sie daran Interesse haben, nehmen Sie das bitte wahr.
Habe ich eigentlich hier in der Vorlesung die Ergebnisse der
Vorlesungsbefragung schon mitgeteilt?
Habe ich, glaube ich, noch gar nicht.
Das könnte ich auch noch mal schnell machen, bevor ich hier... oder
mache ich, nachdem ich durch diese Folien durch bin.
Gehen wir nochmal auf die Vorlesungsbefragung rein.
Die, kann ich gleich sagen, recht gut ausgefallen ist.
Haben 100% Lehrqualitätsindex gekriegt, was mich natürlich freut.
Schauen wir also an, was wir in der Vorlesung alles gemacht haben.
Sie haben daran Interesse, weil Sie auch hoffentlich festgestellt
haben, dass Algorithmik ein zentrales Gebiet der Informatik ist.
Wir müssen sehen, wie wir mit Daten umgehen, wie wir mit Informationen
umgehen.
Wir brauchen Algorithmen und wir müssen sehen, dass wir mit möglichst
geringen Kosten Algorithmen ausführen können.
Wir brauchen immer irgendeine gewisse Zeit.
Die Rechner sind nie schnell genug für die großen Probleme.
Speicher sind nie groß genug.
Ich habe einmal gehört, dass jemand sagte, ach, das ist doch Unsinn,
sich um Beschleunigung von Algorithmen zu kümmern.
Die Rechner werden immer schneller.
Das geschieht ganz von alleine, dass ein Algorithmus schneller
ausgeführt werden kann.
Das ist natürlich naiv, weil wir wissen, wenn wir Algorithmen mit
einer Größenordnung besser ausführen können, dann kann das keine
Beschleunigung des Rechners, was ja nur eine lineare Beschleunigung
wäre, jemals hinbekommen.
Es lohnt sich immer, nach effizienten Lösungen zu suchen und das haben
wir gemacht.
Ich habe versucht, Ihnen das systematisch darzustellen.
Voraussetzung ist natürlich, dass man ein geeignetes Berechnungsmodell
hat, dass man auf einer ausreichend abstrakten Ebene argumentieren
kann über den Aufwand für Algorithmen, damit man möglichst einfach
argumentieren kann.
Dafür haben wir eben die RAM genommen, die zunächst mal sehr
umständlich aussah.
Wir haben die Kostenfunktionen betrachtet, also insbesondere gesehen,
man muss auch darauf achten, kann ich die Einzeloperationen
tatsächlich in konstanter Zeit ausführen?
Oder habe ich in den Einzeloperationen, die hier auftauchen, also bei
arithmetisch -logischen Operationen zum Beispiel, bereits einen
Aufwand, der von der Problemgröße abhängt?
Datenstrukturen haben wir relativ wenig betrachtet, nur so ein
bisschen mal immer gesagt, wie stelle ich unsere Probleme eigentlich
dar?
Wir haben Suchbäume gehabt, Linear Arrays oder auch zweidimensionale
Arrays.
Wir haben Rechnerstrukturen betrachtet, das ist eigentlich das, was
diese Vorlesung auszeichnet, dass wir uns anschauen, wie man
Algorithmen auf unterschiedlichen Rechnertypen ausführen kann, ob man
sie durch Parallelität beschleunigen kann, also die Ausführung oder
die Lösung eines Problems.
Und es ist klar, dass parallele Algorithmen immer größere Bedeutung
erlangen, einfach dadurch, weil wir heutzutage fast nur noch
Parallelrechner mit uns rumtragen.
Also die Smartphones, auf denen Sie gerade rumtippen, die haben mehr
als einen Prozessor, vier, acht oder in Zukunft wahrscheinlich ein
paar Dutzend Prozessoren.
Und die müssen sinnvoll ausgenutzt werden, dazu muss es Möglichkeiten
geben oder muss man wissen, wie man das besser macht.
Also wir bekommen wieder steigende Bedeutung, parallele Algorithmen
wurden intensiv entwickelt in den 70er und 80er Jahren, auch noch ein
bisschen in den 90ern und dann wurde es relativ ruhig um parallele
Algorithmen und sind jetzt aber wieder sehr wichtig geworden.
Welche Themen haben wir behandelt?
Wir haben uns erstmal Probleme hergenommen, algebraische Probleme,
Graph -Probleme, Such- und Sortierverfahren, algorithmische Geometrie
und Data Election, also verteilte Algorithmen-Probleme.
Ich habe Ihnen jeweils gezeigt, wie die Datenstrukturen die Lösung
beeinflussen, das war allerdings immer relativ nachrangig betrachtet
worden, das Wesentliche war zu sehen, wie wir sequenzielle, parallele
Verfahren, Hardware-Algorithmen betrachten können und am Ende jetzt
eben auch verteilte Algorithmen.
Und das ist eben wichtig zu wissen, was habe ich als Rechner
-Infrastruktur zur Verfügung oder was sind meine Anforderungen an ein
Problem, an einen Algorithmus.
Wenn ich eine Aufgabe immer wieder ausführen muss, wie zum Beispiel in
der Signalverarbeitung, die gleiche Aufgabe mit einem möglichst hohen
Durchsatz, dann mache ich das in Hardware.
Und wenn ich Pipelining einsetzen kann, mache ich das auch, wenn es
darauf ankommt, möglichst kurz die Berechnungszeit zu machen, also
wenn Sie suchen nach dem schnellstmöglichen Verfahren, zum Beispiel
Matrizen zu multiplizieren, dann nehmen Sie einen parallelen
Algorithmus.
Sofern Sie in Hardware beliebig investieren können.
Dann können Sie in der kürzesten Zeit multiplizieren.
Wenn Sie einen hohen Durchsatz brauchen, machen Sie es wieder anders.
Das ist das, was ich vermitteln wollte, dass man sich überlegen muss,
wie muss ich einen Algorithmus strukturieren, damit er unter den
Randbedingungen für den Entwurf und die Ausführung der Algorithmen
dann bestmöglich gestaltet werden kann.
Dazu haben wir betrachtet untere und obere Schranken.
Ein paar untere haben wir gezeigt.
Haben auch die schönen Situationen gesehen, dass es Algorithmen oder
Probleme gibt, bei denen wir scharfe untere und obere Schranken
bestimmen können, d.h.
die identisch sind.
Wir können genau die unteren Schranken erreichen, sogar bezüglich der
Konstanten.
Das war beim Horner Schema und beim Sortieren der Fall.
Beim parallelen Sortieren auf zweidimensionalen Feldern.
Und haben dann auch noch gesehen, wie man ganz systematisch
Algorithmen entwerfen kann.
Das war dieser Mapping-Ansatz oder der Ansatz, mit dem man systemische
Algorithmen erzeugt auf zweidimensionalen Feldern durch
Transformationsmatrizen.
Sie haben die klassischen Ansätze, die Weiden und Conquer noch mal
kennengelernt.
Das kennen Sie ja eigentlich schon von der Anfänger-Vorlesung her.
Und wir hatten Sweep-Line betrachtet, das war ja die Reduktion eines
Problems.
In dem Fall zweidimensionales Problem auf eindimensionales Problem.
Und dadurch, dass ich dann eine Folge von eindimensionalen Problemen
betrachte, mit einem gewissen Aufwand, habe ich einen Gewinn gegenüber
einer Problemlösung direkt im zweidimensionalen Bereich.
Das war ein systematischer Ansatz, der bei der Überprüfung der
Schnittpunkte oder dem Suchen von Schnittpunkten von Geraden relevant
war.
Okay, das ist so die Übersicht.
Über das, was ich Ihnen gezeigt habe, ist gar nicht so viel.
Aber ich denke, es hat trotzdem die Vorlesung ganz gut ausgefüllt.
Und ich hoffe, es war nicht zu schwer.
Selbst meine Mitarbeiter sagen mir manchmal, das wäre eine der
schwersten Vorlesungen, die ich halte.
Und ich finde die natürlich einfach.
Aber ich weiß nicht, wie Ihnen das gegangen ist, ob Sie damit gut
zurechtgekommen sind.
Ich hoffe, dass Sie mit zurechtkommen.
Und Sie haben ja die ganzen Aufzeichnungen.
Können Sie immer noch wieder nachlesen.
Rückmeldung nehme ich gerne entgegen.
Wie sieht das aus mit einem weiteren Studium?
Was können Sie noch machen bei mir oder auch bei anderen?
Also was haben wir am Institut?
Da haben wir eine ganze Reihe von Arbeitsgruppen.
Wir beschäftigen uns alle mit Grundlagen und Methoden und mit
Anwendungen in verschiedenen Bereichen.
Ich habe hier natürlich meine Gruppe ein bisschen hervorgehoben
farblich.
Effiziente Algorithmen oder in letzter Zeit überwiegend
Energieinformatik.
Dann haben wir die betrieblichen Informations- und
Kommunikationssysteme bei Oberweis.
Wir haben die wissensbasierten Systeme oder Web-Science jetzt bei
Herrn Studer.
Die habe ich in einen Kasten reingeschrieben, weil Herr Sure Vetter
der vorgezogene Nachfolger von Herrn Studer ist.
Das heißt, der wird das Gebiet wissensbasierte Systeme weiterführen,
was Herr Studer bisher gemacht hat.
Und dann haben wir dreimal NN hier stehen.
Einmal steht hier angewandte technisch-kognitive Systeme.
Da hoffen wir, dass wir zum Wintersemester einen Lehrstudienhaber
haben, der diese Professur ausfüllt.
Das Berufungsverfahren ist fast abgeschlossen.
Da werden nächste Woche noch Verhandlungen geführt und dann hoffen
wir, dass wir sehr schnell eine Entscheidung kriegen.
Hier geht es also um Anwendung der Informatik in einem sehr
technischen Bereich.
Insbesondere zum Beispiel um autonomes Fahren oder autonome Roboter.
Dazu muss ich Kognitionsfähigkeiten haben und muss entsprechend
Technologien dafür entwickeln, Algorithmen für Erkennen der Umgebung
benutzen und dann zum Beispiel Autos sinnvoll steuern, sodass die
nicht einen weißen Laster einfach ignorieren und meinen, das ist ein
hochhängendes Autobahnverkehrsschild.
Das ist etwas, was nicht passieren darf.
So eine wahnsinnige Herausforderung, vor einem weißen Hintergrund ein
weißes Objekt zu erkennen, ist ja fast unmöglich.
Und das sind so Schwierigkeiten, die man da auch lösen muss.
Aber noch viele andere Dinge.
Interessante Dinge.
Dann gibt es eine...
Das hier ist die Nachfolge von Herrn Tai.
Herr Tai hat Service Computing gemacht.
Das haben wir umgewandelt in angewandte technisch-kognitive Systeme.
Dann gibt es eine Professur, da steht jetzt kritische Infrastrukturen.
Das ist die Nachfolge von Herrn Seese, der vor einem Jahr in Ruhestand
gegangen ist.
Und da soll es oder wird es gehen um angewandte Informatik für
kritische Infrastrukturen wie Gesundheitssystemen oder Industrie 4.0
oder Verkehrssysteme, vielleicht auch Energiesystemen.
Aber da haben wir ja schon hier oben die Energieinformatik an meiner
Professur.
Deswegen spielen da die anderen Infrastrukturen eine größere Rolle.
Und es geht vor allen Dingen um Verlässlichkeit, Sicherheit auch von
kritischen Infrastrukturen, aber eben vor allen Dingen um die
Randbedingungen, wie kann ich wirklich Informatik machen in Bereichen,
die wirklich sehr große Anforderungen haben bezüglich Verlässlichkeit
der Ausführungen und so weiter.
Dann wird es demnächst geben, die Professur wird gerade jetzt, also
nächste Woche wird der Ausschreibungstext fertig gemacht.
Dann wird die ausgeschrieben, IT-Sicherheitsmanagement.
Wir haben das Nationale Kompetenzzentrum für angewandte
Sicherheitstechnologien hier in Karlsruhe und wir werden die Professur
von Herrn Studer, die nicht wegfällt, sondern, also der Herr Sure
Vetter hat jetzt ja auch eine Professur und der Herr Sure Vetter
übernimmt im Prinzip die von Herrn Studer und die wird dann
fortgeführt mit einer anderen Ausrichtung, nämlich mit
Sicherheitsmanagement.
Und die wird jetzt ausgeschrieben, also in einem Jahr etwa werden wir
dann hier auch eine neue Arbeitsgruppe haben mit der Thematik.
Und hier steht jetzt noch mein Name, da muss ich da hinschreiben, auch
noch NN dahinter, weil ich jetzt in einem Jahr in Ruhestand gehe.
Und dann wird jetzt zu Beginn des Wintersemesters ausgeschrieben mit
der, nicht genau Energieinformatik, sondern das heißt dann angewandte
Informatik für Energiesysteme, aber ist im Prinzip Energieinformatik.
So, was passiert dann mit den Vorlesungen in meinem Bereich?
Also richtig, FZI.
Am FZI kann man auch noch schöne Sachen machen.
Man kann nicht nur Lehrveranstaltungen machen und in
Forschungsprojekten mitwirken bei uns am AIFB, sondern auch im
Forschungszentrum Informatik.
Wir sind eigentlich alle, die dort stehen, auch Direktoren am
Forschungszentrum Informatik und machen dort angewandte Forschung in
Kooperation mit der Industrie.
Und auch da haben Sie Chancen, sich mit einzubringen, wenn Sie daran
Interesse haben.
Und jetzt noch ein paar Bemerkungen zu Vorlesungen, die angeboten
werden.
Das sieht jetzt ein bisschen schlimm aus hier, weil das ein
Auslaufmodell ist.
Also Sie sehen mich hier als Auslaufmodell.
Effiziente Algorithmen habe ich jetzt zum letzten Mal gelesen.
Als ich das realisiert habe zu Beginn der Vorlesung, ist mir das
richtig schwer gefallen, das tatsächlich zu akzeptieren.
Ich halte diese Vorlesung zum letzten Mal, weil das eigentlich meine
Kernkompetenz ist und ich habe da halt sehr viele Dinge reingesteckt.
Es geht halt um den kostengünstigen Einsatz von Berechnungsressourcen
zur Bearbeitung von Standardaufgaben, Informationsverarbeitung.
Methodisch steht da sehr viel drin.
Dann die Vorlesung Organic Computing, ein Bereich, den ich auch
aufgebaut habe im Laufe meiner Tätigkeit als Hochschullehrer.
Da ist die Vorlesung Organic Computing draus entstanden, die ich auch
letztmalig dieses Semester angeboten habe.
Wenn Sie die noch nicht gemacht haben, können Sie sich nur die
Aufzeichnung noch anschauen und dann hoffen, dass nochmal eine Prüfung
kommt dazu.
Ende nächsten Semester ist ein Semester drauf, mache ich nochmal eine
Prüfung.
Aber dann ist das auch vorbei.
Es sei denn, mein Nachfolger führt diese Vorlesungen fort.
Das weiß ich natürlich nicht.
Oder auch der Nachfolger von Herrn Seese vielleicht, der kritische
Infrastrukturen macht, könnte ja auch solche Vorlesungen weiterführen.
Das weiß man alles noch nicht.
Dann die Vorlesung Algorithms for Internet Applications.
Eine Vorlesung, die ich oft ins Leben gerufen habe, weil ich
feststellte, dass der Begriff Algorithmen oft zur Abschreckung oder
irgendwie abschreckend wirkt auf einige Studierende.
Deswegen habe ich gesagt, hier stellen wir mal die Internetanwendungen
in Vordergrund und schauen uns dann in dem Bereich Algorithmen an.
Die war auch sehr erfolgreich.
Die mache ich das letzte Mal im Winter.
Und da geht es halt um Themen, die Sie hier sehen.
Internetrouting, Suchmaschinen, sichere Kommunikation, ein bisschen
auch noch Energie am Ende.
Aber auch da ist die Frage, ob die jemand so weiterführt oder...
jedenfalls ich werde sie nicht weitermachen.
Dann haben wir die Vorlesung von Herrn Schukla.
Naturspirierte Optimierungsverfahren.
Die läuft jetzt diesem Semester und die wird auch im nächsten
Sommersemester laufen.
Also Herr Schukla ist dann noch am Anfang seiner Karriere als
Hochschullehrer und der macht das noch weiter.
Genauso die Computational Economics, die Vorlesung, war eine Zeitlang
eine Vorlesung, die sowohl gewählt werden konnte als Vorlesung im
Bereich BWL als auch als Vorlesung im Bereich Informatik.
Aber das geht nicht mehr, weil diese Wahlmöglichkeit nur bestand, weil
die Vorlesung von zwei Dozenten gemacht wurde.
Ein Mitarbeiter von Herrn Weinhardt, ein Mitarbeiter von mir.
Es wurden dann zwei unterschiedliche Klausuren angeboten.
Eine Klausur für diejenigen, die als Informatikvorlesung haben wollten
und eine Klausur für diejenigen, die das als BWL-Vorlesung haben
wollten.
Da bei Herrn Weinhardt keiner mehr ist, der dieses Thema bearbeitet.
Hat Herr Schukler das jetzt alleine übernommen und hält die also
weiter, aber die kann nur als Informatikvorlesung gewählt werden.
Und dann steht hier die schöne Vorlesung Smart Energy Distribution,
die ich auch letztmalig in diesem Semester angeboten habe.
Das ist halt der ganze Teil angewandte Informatik für Energiesysteme.
Die Vorlesung wird in anderer Form sicherlich weitergeführt, weil mein
Nachfolger dann angewandte Informatik für Energiesysteme machen wird.
Da wird es Vorlesungen in der Richtung geben, aber nicht genau die
Smart Energy Distribution.
Viele Auslaufsachen.
Sie haben also das Glück gehabt, mich noch letztmalig zu erleben bei
Effizienten Algorithmen.
Und dann haben wir natürlich auch noch Seminare.
Da läuft im Wintersemester ein Seminar über Multiagentensysteme und
ein weiteres Seminar über Energieinformatik.
Im Sommersemester wird es auch noch Seminare geben.
Die mache ich auch noch im nächsten Sommer.
Das läuft eigentlich nur im Wintersemester.
Ein Praktikum zur Sicherheit.
Also sichere Systeme, das ist in Verbindung mit dem Kompetenzzentrum
Castell.
Da werden so praktische Aspekte von Protokollen, von allen möglichen
Anwendungen adressiert.
Und man schaut sich an, wie sicher diese Anwendungen sind.
Wie gut man sie angreifen kann.
Das ist auch eine Aufgabe, bestmöglich möglichst effektiv ein
Verfahren anzugreifen.
Beziehungsweise nachzuweisen, das kann man nicht erfolgreich
angreifen.
Das ist also ein sehr interessantes, aber auch herausforderndes
Praktikum.
Was haben wir noch?
Abschlussarbeiten dürfen Sie gerne noch machen bei mir.
Zu allen Themen der Forschungsgruppe.
Die meisten Arbeiten laufen jetzt im Bereich E-Energy, E-Mobility,
Energieinformatik, im Bereich Organic Computing oder auch evolutionäre
verteilte Optimierung, multikriterielle Optimierung.
Das sind Themen, die bei mir im Augenblick vor allen Dingen laufen.
Auch Organic Computing, könnte man doch was machen.
Da kommen Sie einfach bei uns vorbei und fragen nach, wenn Sie was
machen wollen.
Und ansonsten können Sie natürlich auch im FZI was tun.
Da gibt es auch vielfältige Themen, auch in dem Themenbereich da oben.
Diplomandseminar oder Abschlussarbeiterseminar ist eine regelmäßige
Veranstaltung, wo die Abschlussarbeiter über ihre Arbeiten vortragen.
Es werden Probleme diskutiert, die dort auftauchen.
Und ich sage immer, man soll seine Abschlussarbeit möglichst früh
schreiben, sollte nicht warten, bis man nichts anderes mehr zu tun hat
und sich dann überlegen, wo schreibe ich eigentlich jetzt meine
Arbeit.
Sondern es ist immer sinnvoll, wenn man sein Studium auch so
ausrichtet, dass sich daraus sehr gut eine Arbeit ergibt, weil man
sich durch die Kompetenzen, die man erworben hat, gut vorbereitet hat.
Also das sollte man möglichst früh machen.
Und damit Abschließendes.
Ich hoffe, Sie konnten den Wert der hier vermittelten Inhalte erkennen
und können die sinnvoll nutzen.
Ich kriege natürlich gerne Rückmeldungen.
Ich gehe gleich nochmal auf Rückmeldungen ein.
Nämlich die Evaluation.
Rückmeldungen zur Vorlesung sind auch gerne willkommen, werden aber
nicht mehr umgesetzt in eine neue Auflage der Vorlesung.
Trotzdem höre ich gerne, inwieweit das jetzt eigentlich positiv war
oder nicht.
Ich wünsche Ihnen viel Erfolg in der Klausur und natürlich auch viel
Erfolg in Ihrem weiteren Weg durchs Studium und in den Beruf.
Und das ist dann alles, was ich Ihnen an Vorlesungsinhalten
präsentieren wollte.
Und jetzt suche ich nochmal schnell raus.
Umfrage.
Das hier können wir zur Seite machen.
Auswertungsbericht.
Da sprang die 100.
Bester Lehrqualitätsindex.
Das ist sehr schön.
Jetzt gehen wir auf die Fragen ein.
Was haben Sie alles hier gesagt?
Wie gerne besuchen Sie die Veranstaltung?
Es waren natürlich nur relativ wenige Teilnehmer.
Das ist halt das Bedauerliche, dass die Aufzeichnung dazu führt, dass
nur wenige Studenten präsent sind.
Ist halt nicht zu vermeiden.
Aber Sie besuchen das gerne, was mich freut.
Es ist eine Wahl- oder Wahlpflichtveranstaltung.
Sie haben einerseits regelmäßige Anwesenheit.
Von neun Leuten waren das 55%.
Also fünf Personen waren regelmäßig da.
Heute sind es noch drei da.
Zwei haben wir verloren.
Und dann haben wir hier natürlich Durcharbeiten von Skripten.
Das ist klar, dass das sehr stark hier eine Rolle spielt.
Abstimmung zu anderen Lehrveranstaltungen passt einigermaßen.
Mitarbeit habe ich ein bisschen bedauert.
Ich habe wenig Interaktionen hier angeregt.
Sie hatten mal gesagt, das wird Ihnen damit aufgezeichnet.
Das finde ich einen sehr negativen Aspekt der Aufzeichnung, wenn es
dazu führt, dass wir in der Vorlesung nicht mehr diskutieren.
Eigentlich bringt das Spaß, wenn man Fragen kriegt und darauf
antworten kann.
Aber ist halt so.
Sie haben die Bedeutung der Lehrinhalte erkannt.
Das freut mich auch.
Sie fördert Transfer und Anwendung des Gelernten auf andere Kontexte.
Das haben Sie gut erkannt.
Selbstständige arbeiten auch.
Sie lernen viel.
Das freut mich.
Grüne Ampel, sehr gut.
Anforderungen wurden klar formuliert.
Ich kam offensichtlich häufiger zu einem erkennbaren Ziel.
Ich vermittele Zusammenhänge.
Setze unterstützende Hilfsmittel sinnvoll ein.
Das hoffe ich doch.
Arbeitsmaterialien, Aufzeichnungen sind wie immer hilfreich gewesen.
Notwendiger Arbeitsaufwand.
Das freut mich wirklich.
Der notwendige Arbeitsaufwand ist relativ hoch.
Sie sind hier beim oberen Ende.
Und Sie sagen, das ist angemessen.
Das finde ich gut.
Sehr oft kriegen wir die Antworten, hoher Aufwand, unangemessen.
Aber hier haben Sie eben erkannt, wenn man hier wirklich was
mitkriegen will, muss man sich mehr damit beschäftigen.
Wie ist die Lehrveranstaltung strukturiert?
Das finden Sie auch relativ gut.
Es gibt hier zwei Leute, die das nicht so gut finden, wie sie
strukturiert ist.
Inhaltlicher Anspruch ist eigentlich relativ hoch.
Das ist halt so.
Geschwindigkeit war in Ordnung, Anschaulichkeit war in Ordnung.
Das war alles verfügbar.
Nur wenige schauen sich die Vorlesungsunterlagen vor dem Termin an.
Auch das ist eine Beobachtung, die gilt für deutsche Studierende.
Für Studierende in anderen Ländern ist das unvorstellbar, dass man in
eine Vorlesung reinkommt und hat sich das Skript für die Veranstaltung
noch nicht angeschaut.
Setzt natürlich voraus, dass man auch die Unterlagen hat.
Die stehen immer zur Verfügung.
Es kann hilfreich sein, man kann anders mitarbeiten, wenn man da schon
mal durchgeguckt hat.
Die Note insgesamt ist schön.
Eine 1,78 haben sie hier gegeben.
Das ist sehr nett.
Drei Leute haben hier nur geantwortet, dass es genügend Tutorien gab.
Aber sie waren alle der Meinung, es gibt genügend Tutorien.
Dann zum Raumbedingungen, das war alles perfekt.
Dozent war auch alles perfekt.
Aktuelle Forschung habe ich eigentlich einigermaßen gemacht, aber man
könnte das noch mehr machen.
Das ist eigentlich alles sehr schön.
Haben Sie mich gut bewertet, dafür bin ich Ihnen sehr dankbar.
Es ist doch schön, wenn man am Ende seiner Zeit für so eine Vorlesung
bestätigt bekommt.
War alles perfekt, das ist natürlich gut.
Vorlesung, Internet, natürlich kriegen Sie die Informationen.
Meistens sind im dritten bis vierten Fachsemester, oder das geht ein
bisschen durcheinander, entweder Bachelor oder Masterstudenten.
Es sind überwiegend Wirtschaftsingenieure.
Jetzt schauen wir noch mal, was Sie hier an Einzelsachen gesagt haben.
Hilfsmittel hätten mein Lernen besser unterstützt, wenn klarer Ziele
formuliert werden.
Warum macht man das?
Ich habe mich eigentlich bemüht, das zu tun.
Also wenn das nicht rübergekommen ist, ist es so.
Falls nicht, woran lag es?
An mir.
Gut gefallen hat mir die Vorlesung besonders wegen Doppelbelegung.
Kann ich nicht an der Vorlesung...
Achso, ja, ja, ja.
Deswegen sind die Aufnahmen wirklich super.
Verschiedene Algorithmen, Aufzeichnungen, dass aufgezeichnet wird,
Videoaufzeichnung, das ist immer so das, was hier besonders gesagt
wird.
Das können natürlich nur Leute sagen, die dann total zur Übung gehen,
aber nicht zur Vorlesung, denn ansonsten könnte ich diese Rückmeldung
gar nicht bekommen.
Nicht gefallen hat Ihnen gar nichts.
Was könnte noch verbessert werden?
Zum Teil etwas deutlichere Definitionen, das mag sein.
Manchmal habe ich Sachen etwas vage gelassen, aber in der Regel
versuche ich eigentlich den Detaillierungsgrad zu nehmen, den man
braucht, um ein Konzept darzustellen.
Das finde ich natürlich auch interessant hier, da die Aufzeichnungen
der letzten Jahre online sind, braucht man keine neue Aufzeichnung.
Das kann man argumentieren.
Man macht einmal eine schöne Aufzeichnung, und dann kann man die ja
immer verwenden.
Dann braucht man sich ja gar nicht mehr in den Hörsaal zu stellen.
Das Konzept gibt es ja auch.
Man macht ein Inverted Classroom, das heißt, in der Vorlesung oder
wenn man sich trifft, wird keine Frontalpräsentation gemacht, sondern
man diskutiert.
Und man hat vorher eine Aufzeichnung gemacht und diese Aufzeichnung
bereitgestellt.
Das wäre das, was man hier machen könnte.
Man hat die alten Aufzeichnungen und dann geht man anschließend,
trifft sich und diskutiert über das und spricht über das, was dort
gezeigt wurde.
Das ist aber im Prinzip das, was in den Tutorien gemacht wird.
Wenn man nur Vorlesungen hat und keine Übungen, dann wäre so ein
Inverted Classroom was Sinnvolles.
Aber mit den Übungen ist diese Möglichkeit, darüber zu reden, ja auch
schon ganz gut.
Ich habe das in einigen Vorlesungen genutzt, dass ich mal, wenn ich
nicht da war, gesagt habe, okay, wir haben die Aufzeichnung vom
vorigen Jahr, die kann man dann an der Stelle verwenden.
Aber ich finde es immer etwas anderes, ob ich eine Vorlesung halte und
ich gucke dabei den Studierenden in die interessierten Augen.
Als wenn ich nur vor sehr wenigen etwas erzähle.
Und es ist auch so, dass jedes Jahr eigentlich schon gewisse
Änderungen da sind in der Art, wie ich etwas präsentiere.
Und deswegen mache ich es halt jedes Jahr wieder.
Und das war es.
Das waren die Rückmeldungen.
Also recht positiv habe ich mich gefreut über die Bewertung und damit
sind wir wirklich am Ende der Vorlesung angekommen.
Das war Effiziente Algorithmen.
Ich danke Ihnen für die Aufmerksamkeit und für die Teilnahme.