So, schönen guten Tag.
Begrüße Sie zur Vorlesung Grundla... äh, nicht Grundlage.
Das ist lange vorbei.
Also, fange ich nochmal an.
Begrüße Sie zur Vorlesung Effiziente Algorithmen im Sommersemester
2010.
Ich weiß gar nicht, warum das hier zu Anfang animiert ist.
Sollte gar nicht sein.
Also, wir sind im Sommersemester.
Der Raum hier ist eigentlich groß genug.
Hat eigentlich auch genügend Stühle und Tische, aber die sind aus
irgendeinem Grund verschwunden.
Ich weiß nicht, wo die geblieben sind.
Das ist etwas, was wir bearbeiten müssen, dass das hier wieder
ordentlich gemacht wird, denn der hat eine gewisse Kapazität, und die
brauchen wir natürlich.
Das kann nicht sein, dass hier einfach Tische verschwunden sind.
Das werden wir klären.
Also, in Zukunft werden hier genügend Tische sein, damit Sie alle
sitzen können.
Und beziehungsweise muss auch keiner stehen im Augenblick, aber hinten
auf der Fensterbank zu sitzen, ist vielleicht auch nicht gerade das
Angenehmste.
So, also, ich freue mich, dass Sie hier zu dieser Vorlesung gekommen
sind.
Also, da habe ich ja eine Sache bei der Überarbeitung vergessen.
Das darf ja gar nicht mehr auftauchen.
University Karlsruhe, die gibt es ja nicht mehr.
Ich nenne nur noch das KIT.
Also, worum geht es?
Ich halte Ihnen diese Vorlesung.
Sie wissen, dass ich mich immer mit Bild hier ablichte auf den Folien,
weil es immer Studenten gibt, die nicht in der Vorlesung sind, sondern
erst irgendwann später sich die Vorlesung anschauen oder anhören.
Sie wissen, dass wir eben diese Vorlesung hier aufzeichnen.
Also, auch jetzt wird die Vorlesung aufgezeichnet.
Deswegen habe ich hier mein Mikrofon am Ohr.
Ich habe das jetzt mit einem Bluetooth-Mikrofon gemacht, damit ich
nicht am Kabel hänge und die Druckqualität einigermaßen ist.
Ich hoffe, das funktioniert.
Gestern hat es funktioniert in einer anderen Vorlesung.
Also, kurze organisatorische Dinge.
Sie wissen, denke ich, wo ich sitze.
Sie haben mich schon in einer anderen Vorlesung erlebt.
Wer hat noch nie bei mir in eine Vorlesung gehört?
Einige.
Aha, was studieren Sie?
Wirtschaftsingenieur.
In welchem Semester?
Im sechsten Semester.
Achso, dann kann ich doch sagen, im sechsten Semester.
Ja, im vordersten Semester.
Da haben Sie Vorlesungen bei Frau Mostagim oder Herrn Branke gehört.
Genau, richtig.
Deswegen haben Sie mich noch nicht erlebt.
Herzlich willkommen.
Jetzt kommen Sie in den Genuss, mich auch mal zu hören.
Und zu sehen.
Also, Sie wissen, dass wir für die Vorlesung einen
Vorlesungsarbeitsbereich haben.
Ich denke, da braucht man sich nicht groß drauf einzuziehen.
Da sind alle Informationen zur Vorlesung drin.
Und in diesem Vorlesungsarbeitsbereich sind also insbesondere dann zur
Verfügung alle Vorlesungsfolien.
Auch hier an den Mittelfolien.
Sie wissen, dass ich immer etwas reinschreibe in die Folien.
Also, ich mache manchmal nur so eine Unterstreichung.
Manchmal male ich auch etwas dazu, was inhaltlich sinnvoll ist.
Und, ja, dann steht da noch drin, alles Mögliche über Links auf
interessante weitere Dinge.
Die Vorlesungsaufzeichnungen werden dort auch verlinkt.
Sie stehen nicht direkt im Studierendenportal, weil die Umfänge der
Vorlesungsaufzeichnungen zu groß sind.
Das sind also Größenordnung 50 MB pro aufgezeichnete Vorlesung.
Deswegen sind da nur Links auf den...
Das steht hier gar nicht drauf, wo die eigentlich liegen.
Das sind Links auf das DIVA.
Sie kennen das digitale Video- und Audioarchiv der
Universitätsbibliothek.
Oder der KIT-Bibliothek.
Und dort sind alle Vorlesungen von mir aufgezeichnet.
Beziehungsweise sind dort verfügbar in verschiedenen Formaten.
Meister des AVI-Dateien.
Das ist das, was für Sie wesentlich ist.
Es gibt auch Streaming-Versionen.
Eine Streaming-Version einer Vorlesung ist eigentlich relativ
unbrauchbar.
Weil der einzige Zweck, warum Sie solche aufgezeichneten Vorlesungen
verwenden, ist ja, dass Sie sich das anschließend nochmal anschauen.
Dass man sich das in Tutorien nochmal ansehen kann.
Oder wenn man Aufgaben bearbeiten will.
Wenn man sich zur Prüfung vorbereitet.
Es gibt ja niemanden, der Vorlesungen von vorne bis hinten neu anhört.
Es sei denn, er war nicht in der Vorlesung.
Das gibt es natürlich auch.
Dass Leute gar nicht in die Vorlesung gehen, sondern sich das nur zu
Hause anhören.
Wenn Sie darauf verzichten wollen, direkt interaktiv hier in der
Vorlesung mitzumachen.
Soweit also Interaktion möglich ist.
Was sich aber eigentlich normalerweise möglich sein sollte.
Dann ist es so, dass man diese aufgezeichneten Vorlesungen am besten
abspielen kann mit dem Camtasia-Player.
Das ist ein feilsitzbarer Player.
Es gibt viele Player, mit denen Sie solche Dateien abspielen können.
Aber der große Vorteil des Camtasia-Players ist, dass Sie ein
sichtbares Scrolling haben.
Das heißt, Sie können beliebig da durchlaufen.
Also im beschleunigten Modus.
In der Geschwindigkeit, wie Sie diesen T-Radar bewegen.
Und Sie können an der Stelle halten, die Sie dort sehen, die Sie
interessiert.
Und dort mal kurz reinhören, wenn Sie das mit anderen Playern machen.
Da sehen Sie nicht, wohin Sie gerade links scrollen in der Datei.
Und dann müssen Sie halt raten, wo Sie gerade einsteigen wollen.
Das macht überhaupt keinen Sinn.
Also die sind eigentlich unbrauchbar für solche Zwecke.
Die kann man brauchen, wenn man einen vollständigen Film sich angucken
will.
Aber nicht für Zwecke des E-Mails.
Und deswegen sollten Sie den Camtasia-Player nehmen.
Oder irgendeinen anderen, der Ihnen so ein sichtbares Scrolling
anbietet.
Es gibt durchaus auch andere.
Wenn Sie einen anderen nehmen, dann müssen Sie den dazugehörigen Codec
von TechSmith verwenden.
TechSmith ist die Firma, die Camtasia anbietet.
Und den müssen Sie halt auf Ihrem Rechner einmal installieren.
Und dann haben Sie die Möglichkeit, die Sachen sich auch in den
richtigen Farben, mit der richtigen Auflösung anzuschauen.
Gut, das dazu.
Was habe ich noch alles drauf?
Vorlesungstermine sind Ihnen bekannt, Übungstermine hoffentlich auch.
Freitags, 11.30 Uhr bis 13.00 Uhr.
Die Klausur ist natürlich auch wichtig, wird wie immer bei uns am ARFB
in der Woche nach Vorlesungsende stattfinden.
Voraussichtlich am Dienstag oder Mittwoch, eventuell am Montag.
Da wird man sehen, wie viele Anmeldungen da sind, wie sich die
verteilen.
Wir nutzen ja diese drei Tage, Montag bis Mittwoch, in der Regel
vollständig aus.
Das also zu diesen einführenden, organisatorischen Dingen.
Noch mal zum VAB, da sind die Links auf die aufgezeichneten
Vorlesungen.
Dann sind natürlich auch drauf die Übungsblätter.
Und es ist dort die Möglichkeit, im Forum irgendwelche Fragen zu
stellen, Dinge zu diskutieren.
Nutzen Sie das Forum.
Es wird also von uns ständig beobachtet.
Wir geben Rückmeldungen übers Forum.
Ich werde auch, wenn ich per E-Mail, Sie können mich also gerne per E
-Mail auch anmelden, wenn ich da irgendwelche Fragen kriege, die von
allgemeinem Interesse sind, werde ich die auch eher im Forum
beantworten als direkt per E-Mail, weil das dann für eine größere
Anzahl von Personen eine sinnvolle Information sein kann.
Gut, das kurz dazu.
Dann gibt es natürlich noch eine weitere Person, die hier eine Rolle
spielt, nämlich der Herr Schukla.
Er sitzt hier vorne, Sie können mich einmal kurz erheben und sich
zeigen.
Das ist also Herr Schukla, der diese Übungen zur Vorlesung betreuen
wird.
Er sitzt auch drüben im Allianzgebäude am Grundplatz, hat
Dienstagnachmittag seine Sprechstunde und ist per E-Mail mit dem
üblichen Format erreichbar, das Sie ja auch alle kennen.
Ich kann nur immer wiederholen, dass ich davon ausgehe, wenn ich eine
E -Mail bekomme, dass das E-Mails sind von KIT-Studenten, E-Mails von
irgendwelchen Personen, die bei BMX oder ähnlichen Providern einen E
-Mail -Account haben.
Die gehören ja nicht zur Uni, deswegen weiß ich nicht, was ich darauf
antworten soll.
Es ist ja klar, dass jemand, der hier studiert, auch die KIT-Adresse
verwendet.
Man ist ja stolz darauf, dass man hier studiert und wird es nach außen
immer verwenden, wenn man kommuniziert, ich bin Student am KIT.
Man kann nichts Besseres verkünden in der Welt, als dass man hier
Student ist und hier an einer Elite-Universität zum
Wirtschaftsingenieur oder zu einer anderen Fachkraft ausgebildet wird.
Und warum sollte man verkünden, dass man für GMX oder für Web.de oder
für Google vielleicht sogar noch...
Das sind ganz andere Dinge, die ja irrelevant sind.
So, zu den Übungen.
Weitere Informationen.
Eventuell, müssen wir gucken, es sind relativ viele Studenten da.
Wir haben schon einen Tutor.
Informationen zum Tutor sind im VHB, werden dort also bereitgestellt.
Also nicht eventuell, sondern tatsächlich ein Tutor.
Übungen sind 14-tägig, wie Sie wissen.
Und der Sinn ist, dass Sie sich aktiv mit dem Stoff beschäftigen.
Mit Stoff der Vorlesung, um den besser zu verstehen.
Wir wünschen natürlich eine aktive Teilnahme an den Übungen.
Sie wissen, dass man etwas lernt, wenn man sich konstruktiv mit dem
Stoff beschäftigt.
Ansonsten wird es halt, würde ich lesen, ist es schwierig, etwas über
Algorithmen zu verstehen.
Beginn der Gruppen.
Es wird sicherlich dann zwei Gruppen geben.
Oder auch mehr, müssen wir gucken, wann die beginnen werden.
Das werden wir alles noch bereitstellen.
Das erste Übungsblatt wird es am nächsten Dienstag geben.
Und die Abgabe ist dann eine Woche später.
Die Übungsblätter, die Besprechung am nächsten Dienstag.
Wenn es Änderungen gibt, kriegen Sie das alles mit, über VAB oder auch
hier in der Vorlesung.
Es ist klar, dass Sie die Übungsblätter möglichst in Zweiergruppen
bearbeiten.
Teamarbeit ist immer wichtig, Aufgabenteilung auch.
Das ist Standard, Kooperation muss man lernen.
Abgabe zu Beginn der Vorlesung, das ist auch sinnvoll.
Die Übungsblätter werden korrigiert, auch das ist wichtig.
Anders als bei den Übungen, die wir bei Grundlageninformatik 2 und
auch 1 machen, wo Sie nur Anwesenheitsübungen machen, werden Sie hier
Aufgaben zu Hause bearbeiten, die wir dann korrigieren, wo Sie Punkte
bekommen.
Und für erfolgreiche Bearbeitung, das heißt mindestens 60% der Punkte,
bekommen Sie dann einen Bonus für erfolgreiche Teilnahme an den
Übungen, der eine Notenstufe beträgt, sofern Sie eine Klausur oder die
Klausur am Ende bestanden haben.
Es ist auch so, dass wir durch die Umstellung auch Bachelor und Master
in der Lage sind, jetzt auch ein bisschen mehr die Bewertung Ihrer
Leistungen in einer Vorlesung auch etwas differenzierter zu machen.
Das ist hier eine kleine Differenzierung, dass ich also sage, die
erfolgreiche Mitwirkung oder Teilnahme an den Übungen wird bewertet
durch so eine Notenstufe.
Man könnte sich auch auf ein amerikanisches System umstellen mit
Midterm -Exam und all solchen Sachen, das will ich aber im Augenblick
gar nicht.
Kann man aber darüber diskutieren, ob man andere Systeme einführen
möchte, wäre auch ein Thema, das man im Forum gerne ansprechen darf.
Rechnerübungen müssen wir schauen, ob wir das machen.
Eigentlich ist es bei einer Vorlesung über Algorithmen, über
effiziente Algorithmen sehr sinnvoll, konkret etwas zu programmieren.
Sie können es aber auch so machen.
Vermutlich wird es mindestens eine Programmieraufgabe geben.
Das wird Ihnen auch mitgeteilt.
Sie sollten also immer die Infos im Vorlesungsarbeitsbereich beachten.
Und ansonsten gibt es ja auch hier Informationen zu den
organisatorischen Dingen.
Für wen halte ich die Vorlesung?
Die Vorlesung natürlich für Wirtschaftsingenieure, aber auch für
Informationswirte.
Da gibt es einmal ein Blog-Algorithmen für die Leute, die im
Diplomstudiengang sind.
Wer von Ihnen studiert in einem Diplomstudiengang?
Ah, sind noch welche.
Welcher Diplomstudiengang?
Wirtschaftsingenieurwesen.
Auch.
Okay.
Wer von Ihnen ist Bachelorstudent?
Ah, sehr viele.
Wer von Ihnen ist Masterstudent?
Keiner.
Welcher?
Informationswirtschaft.
Okay.
Dann sind Sie in irgendeinem Modul...
Wir haben so viele verschiedene...
Sehr schön.
Das heißt, Sie sind auch in der Vordesung Organic Computing mit drin.
Ja.
Okay.
Gut.
Also, es gibt ja verschiedenste Module, die wir in letzter Zeit für
diese neuen Studiengänge alle einrichten mussten.
Ich habe da die Vordesung Effiziente Algorithmen in diesem Modul drin.
Also, wer von Ihnen ist Informationswirt?
Welchen?
Bitte mal.
Nur einer.
Zwei.
Aha.
Sie sind Bachelorstudent.
Aha.
Gut.
Und die anderen sind also alles Wirtschaftsingenieure.
Das ist auch sehr schön, dass Sie alle diese Vordesung interessieren.
Oder sind auch Wirtschaftsmathematiker dabei?
Keiner.
Wer ist jetzt noch nicht aufgerufen worden mit seinem Studiengang?
Wer macht irgendwas anderes?
Die technischen Volkswirte habe ich gar nicht erwähnt.
Ist anscheinend noch keiner dabei?
Offensichtlich nicht.
Okay.
Gut.
Ansonsten sind Sie vielleicht irgendwie virtuell dabei.
Hören Sie die Vorlesung später an.
Es dürfen also beliebig Leute hier mitmachen.
Worum geht es eigentlich inhaltlich?
Es geht um verschiedenste Themen, verschiedenste Standardprobleme der
Informationsverarbeitung.
Und natürlich haben Sie in der Vorlesung Grundlageninformatik I schon
einiges über Algorithmen gehört.
Aber noch nicht so sehr viel.
Ein bisschen was über die Analyse von Algorithmen, Aufwandsabschätzung
und solche Dinge.
Und ich muss natürlich, wenn ich Ihnen über effiziente Algorithmen
etwas erzählen will, Ihnen etwas darüber sagen, wie wir eigentlich die
Effizienz bewerten wollen.
Das heißt, ich muss Ihnen zu Anfang etwas erzählen, natürlich zur
Einleitung einige Dinge, dann über Berechnungsmodelle.
Das heißt, was ist eigentlich die Basis für die Abschätzung des
Aufwandes in einem Algorithmus?
Da gibt es halt viele verschiedene, nicht nur ein Modell.
Es gibt nicht nur das Zählen von zum Beispiel irgendwelchen
wesentlichen Befehlen in Programmen, also wie arithmetische
Operationen und Ähnliches.
Es gibt noch deutlich mehr.
Aber diese arithmetischen Operationen spielen natürlich eine
wesentliche Rolle bei algebraischen Problemen.
Das sind Probleme, mit denen Sie als Wirtschaftsingenieure sehr viel
zu tun haben.
Nämlich, Sie werden viele statistische Berechnungen machen und im
Bereich Finance da gibt es sehr viele mathematische Untersuchungen.
Sie wissen, dass Mathematik und mathematische Probleme für einen
Wirtschaftsingenieur sehr wichtig sind.
Und dort treten halt viele Standardprobleme auf, wie zum Beispiel
irgendwelche linearen Abbildungen.
Manchmal müssen Sie über Dritten multiplizieren.
Und das sind schwierige Aufgaben, aufwendige Verfahren.
Da muss man sehen, dass man die möglichst effizient macht.
Das werde ich Ihnen berichten.
Ihnen zeigen, wie man das macht.
Und ich zeichne Ihnen diese Probleme und will anhand der Lösungen
dieser Probleme Ihnen Prinzipien vermitteln, wie man solche Probleme
löst.
Bei diesen Prinzipien werden Sie feststellen, dass es nicht nur um das
einfache Lösen von diesen Problemen auf einem Standard-Laptop oder PC
geht, sondern auch darum, wie man den auf dem Parallelrechner löst
oder vielleicht sogar in Hardware.
Also auf sehr unterschiedlicher Art und Weise.
Sie wissen, dass man heutzutage immer stärker Parallelrechner zur
Verfügung hat.
Da muss man auch wissen, wie man mit denen sinnvoll umgeht, wie man
sie ausnutzt.
Algebraische Probleme sind also zum Beispiel Matrixmultiplikation,
Auswertung von Polynomen, schnelle Fourier-Transformation, eine
klassische Operation, die auch zeigen kann, nochmal ein
Entwurfsprinzip für Algorithmen.
Dann habe ich also an einem Bereich Ihnen bei den dritten
Kapitelsachen gezeigt.
Algebraische Probleme.
Und kommen danach zu den Sortier- und Suchproblemen, die Sie häufig,
wenn Sie also sich anschauen, Standardlehrbücher über effiziente
Algorithmen, dann finden Sie die als erstes.
Das sind auch die, die Sie in der Vorlesung Grundlagen der Informatik
1 als erstes vorgesetzt bekommen haben, die Sortier- und Suchprobleme,
weil die so einfach sind.
Die sind so einfach zu verstehen, sind aber auch richtig.
Denn wir müssen ganz oft Daten sortieren.
In vielen Anwendungen, gerade so im informationellen Bereich, hat man
oft das Problem, dass man irgendwas sucht.
Im Internet sucht man sehr viel.
Da gehe ich nur sehr wenig drauf ein.
In dieser Vorlesung gehe ich in anderen Vorlesungen drauf ein, auf
Suche von Informationen im Internet.
Aber überhaupt das Sortieren von Daten ist ein wichtiges Problem und
auch das zeige ich Ihnen auf verschiedenen Rechnerstrukturen.
Das ist das, was mich immer interessiert dabei.
Wie kann man in verschiedener Art und Weise solche Probleme sinnvoll,
effizient lösen.
Dann werde ich kurz auf Graph-Probleme eingehen.
Die lernen Sie auch kennen in Vorlesungen aus dem Bereich of Racist
Research.
Aber ich gehe da also relativ kurz drauf ein.
Und dann werde ich noch etwas aus dem Bereich algorithmische Geometrie
ansprechen.
Wir haben ja sehr viel heutzutage so grafische Datenverarbeitung.
Sie müssen irgendwelche Objekte anordnen auf dem Bildschirm, müssen
wissen, welche überschneiden sich eigentlich, wie kann man das
sinnvoll machen.
Da werde ich Ihnen einiges zu algorithmischer Geometrie erzählen und
das Ganze dann zusammenfassen.
Das wird so in etwa in 14 Terminen erledigt sein.
Vielleicht, je nachdem wie wir hier vorankommen, kann es sein, dass
ich da an irgendeiner Stelle noch etwas ausweiten kann.
Es gibt so viele interessante Probleme, die man noch ansprechen kann,
dass ich da also beliebig noch weiteren Stoff einbauen könnte.
Das müssen wir sehen, wie wir das hinbekommen.
Das sind maximal 14 Termine.
Da schließe ich den Dienstag nach Kingston ein.
Hier steht eventuell müssen zwei Termine verlegt werden.
Das stimmt eigentlich gar nicht.
Denn Herr Schufler kann mich ja vertreten.
Ich bin also einmal an einem Dienstag nicht da.
Da bin ich in den USA.
Aber ansonsten bin ich eigentlich nach jetziger Planung Dienstags fast
immer auch wirklich in der Vorlesung da.
Stimmt nicht ganz, aber wie gesagt.
Herr Schufler ist auch da, der kann mich vertreten.
Literatur gibt es massenhaft.
Also effiziente Algorithmen ist ein klassisches Thema der Informatik.
Da finden Sie wahnsinnig viel Literatur.
Und ich habe hier einfach so eine Liste aufgeführt, die habe ich jetzt
gar nicht aktualisiert für die diesjährige Vorlesung.
Sie finden hier sehr viel.
Das sind einfach klassische Sachen.
Aber einige Dinge finden Sie nicht unbedingt in jeder Auflistung über
effiziente Algorithmen.
Zum Beispiel hier das Buch von Selim Akil.
Der beschäftigt sich insbesondere mit Parallelalgorithmen.
Sie dürfen gerne reinkommen.
Da gehe ich auf seine Sachen ein.
Der Borodin und Ian Munro ist jemand, der mich geprägt hat, weil ich
bei ihm Vorlesungen gehört habe vor sehr vielen Jahren.
Und der hat halt auch diese Aufteilung in Algebraische und Numerische
und diese Suchsortierprobleme so gemacht, wie ich Ihnen das auch hier
vorstelle.
Insofern hat er mich etwas geprägt.
Der hat ein sehr schönes Buch geschrieben über effiziente Algorithmen
im Algebraischen Bereich.
Dann ein klassisches Buch von Sedgwick oder eine Buchfamilie kann man
sagen.
Sedgwick hat ja viele Bücher geschrieben über Algorithmen, die sehr
gut lesbar sind, sehr praktisch, sehr angewandt geschrieben sind.
Und vor allen Dingen finden Sie diese Bücher in verschiedenen
Variationen, Algorithmen in Java, Algorithmen in C, Algorithmen in C++
usw.
Eine Vielfalt von Büchern auf Deutsch, auf Englisch, was immer Ihnen
gefällt, können Sie sich anschauen, kann man sehr schön lesen, sehr
angewandt.
Also ein recht interessantes Buch, das man sich gern mal zu Gemüde
führen kann.
Dann ein Klassiker ist natürlich die Reihe von Büchern von Donald
Knuth.
The Art of Computer Programming, der hat ein mehrbändiges Werk
geschrieben, eigentlich das Standardwerk über Algorithmen.
Gibt es auch ab und zu wieder in neuen Auflagen.
Ich habe hier gar keine Jahreszahl hingeschrieben, das ist schon
relativ alt, aber sehr umfassend.
Da steht unheimlich viel Wichtiges drin.
Dann gibt es Bücher von Mehlhorn, von Ottmann und Wittmeier.
Also immer so ein bisschen in dem Titel variiert.
Einer nennt das Datenstruktur und effiziente Algorithmen, der andere
Algorithmen und Datenstrukturen.
Ein Klassiker, international, ist das Buch von Corman, Leiserson,
Rivest, Introduction to Algorithms, MIT Press.
Ein dicker Wälzer, wo auch sehr sehr viel drin steht, kann ich Ihnen
auch sehr empfehlen.
Gibt es auch in der deutschen Version, aber die englischen sind auch
so gut lesbar.
Kann ich auch wirklich sehr empfehlen.
Hans-Werner Lang hat ein Buch geschrieben über Algorithmen in Java,
ein nettes kleines Büchlein.
Hans-Werner Lang ist ein Doktorand von mir gewesen, von langer Zeit.
Hat also dieses Buch speziell für Anwendungen in Java, aber auch auf
Parallelrechnern geschrieben.
Und dann dieses Buch von Harel, das kann ich zu jedem Buch hier was
erzählen.
Das Buch von Harel, David Harel, hat ein Buch geschrieben über
Algorithmics.
Algorithmics ist ein Buch, das einfach lesenswert ist.
Das betreibt einen sehr interessanten Ziel.
Das betreibt etwas darüber, warum man das macht.
Warum man das so macht und nicht anders.
Das betreibt einen so hinter die Uhr.
Warum wirft man Algorithmus in dieser Art und nicht anders?
Was sind so die faszinierenden Probleme?
Das ist einfach nett zu lesen.
Also wenn Sie sich mal in die UB setzen und da das Buch ausleihen,
lesen Sie da ein bisschen drin rum.
Wenn es Ihnen gefällt, kaufen Sie sich das.
Es ist nett, sich damit zu beschäftigen und zu sehen, was sind
eigentlich so die wesentlichen Ideen hinter Algorithmen.
Das ist einfach eine andere Art, als so etwas trocken aufzuschreiben
über den Entwurf von Algorithmen.
Dann habe ich hier einige Bücher über parallele Algorithmen.
Ich will jetzt nicht alle aufführen.
S.Y.
Kung hier, der hat was über VLSI Rank Processes geschrieben.
Auch wichtig, da geht es also um Parallelalgorithmen.
Das Thema parallele Algorithmen war sehr aktiv.
Sie sehen das hier auch an den Jahreszahlen in den 80er und Anfang der
90er Jahre noch.
Und da ist unheimlich viel gemacht worden.
Also das ging los in den 70er Jahren mit Parallelrechnern.
Das Dumme war, dass die Parallelrechner nicht so schnell sich
entwickelt haben, wie die einzelnen Prozessoren.
Beziehungsweise eben die Prozessorentwicklung, die hat dermaßen die
Leistungsfähigkeit der Einzelprozessoren verbessert, dass es sich
einfach nicht lohnte, für die Industrie umzusteigen auf
Parallelrechner und dort aufwendig neue Algorithmen zu entwickeln oder
umzusetzen.
Die haben einfach ihre Standardalgorithmen auf Einfachprozessoren oder
auch irgendwie Farmen von Prozessoren ausgeführt.
Und deswegen sind so die ganzen Parallelalgorithmen auf
zweidimensionalen Feldern so ein bisschen in den Hintergrund geraten.
Und die meisten Firmen, die Parallelrechner angeboten haben, sind
leider vom Markt verschwunden.
Ist so gewesen.
Und deswegen wurde das ziemlich lange auch an den Unis... Thomas hat
es gemacht, diese Parallelrechner, Parallelalgorithmen.
Ich habe das immer durchgehalten.
Ich habe von Anfang an immer oder durchgehend immer etwas über
Parallelalgorithmen erzählt.
Und das macht auch Sinn.
Denn heutzutage ist es so, dass sie immer stärker sogenannte Multicore
-Prozessoren bekommen.
Das heißt, sie haben jetzt schon in ihren Laptops normalerweise
mindestens zwei Prozessoren drin oder zwei Cores drin.
Auf normalen Desktops haben sie heutzutage ungefähr vier bis acht.
Und sie werden in wenigen Jahren in ihren normalen Rechnern, die sie
mit sich umtragen, Dutzende von Prozessoren haben oder sogar Hunderte.
Und in etwas leistungsfähigeren Rechnern wird man wirklich mehrere
hundert Prozessoren haben.
Vielleicht sogar tausend.
Das heißt, Parallelverarbeitung wird zukünftig der Standard sein.
Aber man muss wissen, wie man mit Parallelrechnern sinnvoll umgehen
kann.
Und deswegen ist es ganz wichtig, dass man sich nicht nur damit
beschäftigt, wie kann ich ein Problem sequenziell lösen, wie kann ich
dafür ein kleines Java-Programm schreiben.
Sondern man muss wissen, was kann ich eigentlich sinnvoll mit solchen
parallelen Strukturen machen.
Und das ist eigentlich das, was ich Ihnen in dieser Vorlesung auch
vermitteln möchte, wie man Probleme eben sinnvoll auf
unterschiedlichen Rechnerstrukturen löst.
Und damit erzähle ich Ihnen etwas, was sehr viel zu tun hat oder sehr
relevant ist für das, was man jetzt mit Many- und Many-Core
-Architekturen zukünftig machen wird.
Dazu gibt es noch ein weiteres sehr gutes Buch von Leighton.
Der hat ein Buch geschrieben über parallele Algorithmen und
Architekturen, auch in Standardwerken.
Viele klassische Algorithmen und Parallelrechner sind auch drin, die
gelten zu den typischen Architekturen von Parallelrechnern.
Man wird vermutlich alle diese Bücher umschreiben für jetzt die neuen
Many - und Many-Core-Architekturen.
Aber im Prinzip werden die Verfahren alle übertragen auf diese neuen
Strukturen von hochparallelen Rechnern.
Ich habe auch mal ein Buch geschrieben über Analyse von VLSI
-Algorithmen.
Und da gibt es ein schönes Buch von Herrn Vollmer, der hier an der
Fakultät für Informatik gewesen ist, jetzt emeritiert ist, Modelle der
Parallelverarbeitung.
Und noch ein paar weitere.
Es gibt ein sehr schönes Buch auch von Ingo Wegener, der leider schon
gestorben ist als junger Mann.
Effiziente Algorithmen für grundlegende Funktionen, ein sehr
grundlagenorientiertes Buch, auch nett zu lesen.
Und Herr Zehntner hat in seiner Habir-Schrift, die als Buch
veröffentlicht wurde, etwas geschrieben zu dem Entwurf systemischer
Systeme.
Sie werden später verstehen, was das ist.
Da geht es insbesondere darum, wie man Algorithmen mit mathematischen
Methoden entwickelt.
Also ausgehend von einer Problembeschreibung, mathematisch formuliert
als irgendein Gleichungssystem, können Sie durch algebraische
Transformationen daraus Programme erzeugen auf unterschiedlichen
Rechnerstrukturen.
Das werde ich Ihnen auch in Ansätzen vorstellen.
Ist ein sehr umfassendes Buch, sehr gut dargestellt.
Und auch die Techniken wird man insbesondere für automatisierte
Algorithmenentwürfe zukünftig noch sehr intensiv nutzen.
Also, das zu den grundlegenden orientatorischen Dingen.
Vielleicht nochmal zu dem, was ich Ihnen eigentlich vermitteln möchte.
Die Prinzipien, wie man Algorithmen entwickelt.
Das ist ein Thema, das ist gerade hier in Karlsruhe unheimlich, nicht
unheimlich, sondern ganz toll, sehr wichtig, sehr aktuell, weil wir
hier eigentlich die Hochprog haben, des Themas Algorithmen, also
Algorithm Engineering.
Das heißt, ingenieurmäßiger Entwurf von Algorithmen ist ein Thema, das
ist hier gerade in Karlsruhe sehr stark geprägt.
Insbesondere durch Frau Wagner, Herrn Sanders, auch durch mich, obwohl
ich nicht in dem Forschungsprogramm da drin bin.
Es gibt also ein großes Schwerpunktprogramm der DFG über Algorithm
Engineering.
Und da sind die Deutschen weltweit die führenden Forschungsgruppen.
Also nicht nur jetzt hier in Karlsruhe, auch in Saarbrücken, Gruppe um
Mehlhorn, Leute um Lengauer usw.
Das sind eine ganze Reihe Leute, die das Thema systematischer,
ingenieurmäßiger Entwurf von Algorithmen weltweit eigentlich am
stärksten dominieren und damit etwas machen, was die Algorithmen
wirklich sehr viel stärker mit den Anwendungen in Verbindung bringt,
was man früher bei den mehr theoretisch ausgerichteten
Untersuchungsalgorithmen nicht so sehr getan hat.
Gut, das will ich jetzt beibehalten und möchte dann weitergehen zur
Einführung in die Vorlesung.
Gibt es von Ihnen zu organisatorischen Dingen noch Fragen?
Also ich rede manchmal etwas schnell und viel.
Wenn das zu viel ist und Sie Fragen haben, melden Sie sich einfach.
Ich gehe gerne auf Fragen von Ihnen ein.
Es sind nicht zu viele Hörer da, also dann kann man das alles machen.
Lassen Sie also jetzt uns hier kommen zu dieser Vorlesung.
Worum geht es?
Ich habe Ihnen nochmal kurz den Vorlesungskommentar aufgelegt.
Also zum Inhalt.
Es geht um Kernaufgaben von Wirtschaftsingenieuren und
Informationswirten.
Es geht um systematische Ansätze für die Analyse und effiziente
Gestaltung von Algorithmen.
Und das mache ich halt am Beispiel von Standardaufgaben der
Informationsverarbeitung.
Und daran zeige ich Ihnen halt so diese systematischen Ansätze, mit
denen man einfach generell Algorithmen entwerfen kann.
Und worauf ich eben Wert lege, ist einerseits der Einfluss von
Datenstrukturen, das ist klassisch.
Worauf ich auch immer Wert lege, ist der Einfluss der
Rechnerarchitekturen.
Das ist nicht ganz so klassisch, aber mindestens so wichtig, dass man
weiß, welche Rolle spielen eigentlich die verschiedenen Möglichkeiten,
Rechnerinfrastrukturen zu nutzen für die Gestaltung der Algorithmen.
Und das kann also bis runtergehen in die Umsetzung von Algorithmen in
Hardware.
Auch das kann man machen.
Algorithmen kann man nicht nur als Java-Programm schreiben oder als C-
oder C++-Programm.
Sondern man kann einen Algorithmus auch als Schallkreis
implementieren, in Mikroelektronik, um dafür zu sorgen, dass die sehr
effizient ausgeführt werden können.
Sie können sich vorstellen, dass die Anforderungen an die Gestaltung
der Algorithmen sehr unterschiedlich sein werden, je nachdem, ob man
ihn in Java oder in Hardware implementiert.
Lassen Sie uns gucken, was so die Standardaufgaben der
Informationsverarbeitung eigentlich sind.
Bei technisch-wissenschaftlichen Berechnungen wichtig sind
Simulationen.
Was simuliere ich?
Zum Beispiel simuliert man irgendwelche Crash-Tests von Automobilen.
Da müssen Sie das Verhalten von Materialien simulieren durch
irgendwelche Systeme von Differenzialgleichungen und ähnliche Dinge.
Also da ist einiges zu tun.
Das, was dort bei so Crash-Tests passiert, wollen Sie visualisieren.
Wenn Sie irgendwelche großen Datenmengen haben, Sie wollen riesen
Datenmengen, Sie machen irgendwelche Untersuchungen, Tests, das
Verhalten Ihrer Algorithmen wollen Sie untersuchen, oder Sie haben
irgendwelche Untersuchungen von irgendwelchen menschlichen Verhalten,
haben riesen Datenmengen, wollen jetzt etwas sehen da drin, dann
müssen Sie Strukturen in solchen großen Datenmengen geeignet
visualisieren.
Also eines der Herausforderungen für die Informatik, nicht nur für die
Informatik, dass man riesige Datenmengen untersucht und mit denen muss
man umgehen.
Umgehen heißt, ich muss Strukturen erkennen können, ich muss
Komplexität reduzieren und Struktur erkennen heißt, ich muss
Strukturen visualisieren.
Das ist also ganz wichtig, etwas darzustellen, optisch.
Auch das erfordert sicherlich effiziente Algorithmen.
Optimierung kennen Sie aus verschiedenen Bereichen, eine
Standardaufgabe der Wirtschaftsingenieure.
Steuerung von Systemen, auch wichtig, wenn ich z.B.
ein autonomes Fahrzeug fahren lassen will, muss das auch effizient
passieren, insbesondere muss ich dort die Flugzeit steuern können.
Das heißt, ich habe ganz klare Zeitanforderungen an die Ausführung von
irgendwelchen Funktionen.
Bei der Steuerung irgendwelcher technischer Bereiche.
Kommerziell, betriebswirtschaftlich, da kommt es meistens auf Echtzeit
nicht so sehr an.
Es sei denn, Sie haben irgendwelche Börsenanwendungen, wo diese Kunden
genau handeln müssen.
Wenn Sie allgemein nur Datenverwaltung, Erhebung, Suche machen, ist
das eine andere Art der Anforderung an die Algorithmen, die ausgeführt
werden müssen.
Wenn Sie Statistikuntersuchungen machen oder Wissen extrahieren, auch
dort müssen Sie etwas visualisieren, aber die Verfahren, die Sie
anwenden, sind andere als bei den technisch-wissenschaftlichen
Berechnungen.
Obwohl die Komplexität der Probleme dort in ähnlichen Größenordnung
liegt wie bei den technisch-wissenschaftlichen Berechnungen.
Dann geht es natürlich um Kommunikation.
Wir können heute nicht mehr vernünftig arbeiten ohne Kommunikation.
In allen Bereichen wird kommuniziert, zwischen allen möglichen
Geräten.
Dazu braucht man geeignete Schnittstellen, um Informationen hin- und
herzuschieben.
Wir brauchen grafische Datenverarbeitung, das hat etwas mit
Visualisierung zu tun, also mit Darstellung von Informationen.
Das ist auch Kommunikation.
Und wenn wir über Kommunikation reden, müssen wir auch über
Sicherheitsmechanismen reden.
Auch dort gibt es eine ganze Vielfalt von Algorithmen, die dort
sinnvoll ausgeführt werden müssen.
Also wenn wir über z.B.
Rechnen in der Cloud reden, also Cloud Computing, das geht nur mit
Kommunikation.
Da werden Daten durch die Welt geschoben, irgendwohin, wo sie gar
nicht wissen, wo sie landen, in einen virtuellen, rechnenden Raum.
Und sie müssen dafür sorgen, dass das alles sicher passiert.
Viele interessante Herausforderungen an den Algorithmen, die man dort
einsetzen kann.
Und die Operationen, die man ausführt, sind halt sehr unterschiedlich.
Bei technisch-wissenschaftlichen Berechnungen braucht man sogenannte
Finite -Element-Methoden.
Da braucht man im Rechner dann sehr viel Matrix-Multiplikation und
ähnliches.
Also Modifikation von Matrizen, Vektoren, Lineartransformation sind
Standardaufgaben, die man erledigen muss.
Die man effizient erledigen muss.
Approximation von Funktionen, auch eine wichtige Geschichte.
Darauf gehe ich nicht weiter ein in dieser Vorlesung.
Also wie Sie jetzt in der numerischen Mathematik irgendwelche
Funktionen approximieren können, wie Sie Integrale approximieren
können.
Da gibt es auch eine Vielfalt von verschiedenen Algorithmen,
unterschiedlichen Anforderungen an die Genauigkeit.
Auswertung von Polynomen ist was Wichtiges.
Polynomen approximieren häufig irgendwelche Funktionen.
Und Sie müssen Funktionen manchmal an vielen Stellen auswerten.
Da muss das effizient geschehen, damit werden wir uns auch in der
Vorlesung beschäftigen.
Dann wollen Sie auf Daten zugreifen, lesend, schreibend, suchend und
ähnliches.
Sie wollen sortieren.
Sie müssen in Graphen Wege suchen.
Auch ein Punkt, wo hier die Karlsruhe, gerade Frau Wagner und Herr
Sanders international Spitze sind, das ist die Wegesuche in Graphen.
Also Sie kennen alle den Dijkstra-Algorithmus, nehme ich jedenfalls
an, wo es um kürzeste Wege geht in Graphen.
Die können mit ihren Verfahren dafür sorgen, dass also die Suche
kürzester Wege in großen Graphen, wie zum Beispiel dem Straßennetz von
Deutschland oder Europa oder auch weltweit, so in der Komplexität
reduziert werden kann, dass Sie um etwa Faktor 3 Millionen schneller
sind als der Dijkstra-Algorithmus in praktischen Anwendungen.
Wenn Sie Standard Dijkstra aufanwenden, Dijkstra ist ein sehr gutes
Verfahren, aber wird halt einfach zu viele Dinge berücksichtigen, die
unnötig sind.
Und durch die eigene Vorverarbeitung kann man dafür sorgen, dass man
wirklich um Faktor 3 Millionen schneller ist.
Was natürlich für Echtzeitanwendungen bei meinetwegen
Navigationssystemen unheimlich wichtig ist, wenn Sie alle möglichen
Anfragen haben von Leuten, die ein Online-Navigationssystem haben, das
auf aktualisierte Informationen ständig zugreift, in dem aktuellen
Straßennetz, dann brauchen Sie sehr schnelle Bearbeitungszeiten für
das Finden über der kürzesten Wende und das leisten eben diese
effizienten Algorithmen.
Sortieren ist ein Problem, das kennen Sie alle.
Sortieren vielleicht auch ständig zu Hause die Dinge auf Ihrem
Schreibtisch, aber vielleicht auch im Rechner.
Und sortieren, da gibt es ständig irgendwelche Challenges, das haben
Sie vielleicht gelesen, auch wieder Peter Sanders mit seiner Gruppe
hat da gezeigt, dass er der Weltbeste ist im Sortieren von
Riesendatenmengen.
Also Riesendatenmengen heißt, Terabyte Daten, die sortiert werden
müssen, innerhalb einer Stunde zu weisen.
Und das ist eine wahnsinnige Herausforderung.
Also wer kann am schnellsten zum Beispiel ein Terabyte Daten
sortieren?
Egal mit welchen Ressourcen.
Oder was ist die größte Menge an Daten, die innerhalb einer Stunde
sortiert werden können?
Das sind so internationale Challenges, die natürlich praktische
Auswirkungen haben, gerade im Zusammenhang mit diesen
Riesendatenmengen, die wir in der vernetzten Welt heutzutage
bearbeiten müssen.
Gut, Darstellung von Graphen, Operation auf geometrischen Objekten.
Sie sehen, es gibt eine Vielfalt von Problemen, die man sich anschauen
kann.
Was sind eigentlich die Anforderungen an die Algorithmen, die wir hier
uns anschauen?
Wir wollen natürlich in möglichst kurzer Zeit etwas machen.
Also wir wollen natürlich, wenn ich sage, möglichst effizient, dann
heißt das, wir wollen die Ressourcen, die zur Verfügung stehen,
bestmöglich ausnutzen.
Das ist Effizienz.
Und die Ressourcen bestmöglich ausnutzen heißt, möglichst wenig Zeit,
das ist der Kostenfaktor Zeitbedarf.
Geringer Zeitbedarf pro Aufgabe ist manchmal sehr wichtig, dass Sie
eine Aufgabe sehr schnell erledigen.
Weil wenn Sie zum Beispiel daran denken, dass Sie irgendwelche
Signalverarbeitungen oder Bildverarbeitungen machen müssen, im
Fernsehen irgendwelche Bilder bearbeiten, Sie müssen dafür sorgen,
dass bei Live-Übertragungen im Fernsehen das Bild eines Politikers
durch einen anderen ersetzt wird.
Typische Aufgabe.
Kann man heutzutage machen, in Echtzeit, das sehen Sie gar nicht.
Man hat damit angefangen, dass man irgendwelche Plakate, ob bei
irgendwelchen Autorennen oder Sportveranstaltungen, je nachdem in
welches Land die übertragen werden, in Echtzeit einfach ersetzt durch
die länderspezifischen, also ziellandspezifischen Werbung.
Das kann man alles machen, aber das heißt, Sie brauchen dafür eine
gewisse Zeit.
Und in Echtzeit heißt, Sie dürfen das nicht merken, dass das Bild dann
irgendwie wackelt.
Das heißt, Sie brauchen einen hohen Durchsatz, Sie brauchen also so
etwas, es darf durchaus die einzelne Zeit für die Bearbeitung eines
Frames etwas dauern, aber die Frequenz, mit der Sie die einzelnen
Frames bearbeiten, die muss kurz sein.
Das heißt, Sie brauchen dort einen hohen Durchsatz.
Hoher Durchsatz heißt, viele Aufgaben pro Zeiteinheit müssen erledigt
werden.
Und das ist eine ganz andere Anforderung.
Ich muss Pipelining machen können.
In kurzen Zeitabständen mit einer hohen Frequenz Daten bearbeiten.
Dann wenig Speicherplatz.
Wir haben zwar immer mehr Speicherplatz, also Sie können jetzt bei
Aldi einen Rechner kaufen mit 1,5 Terabyte Festplatte.
Der Hauptspeicher ist noch nicht ganz so groß, aber der liegt auch
inzwischen in relativ großen Dimensionen, 3, 4 oder noch mehr
Gigabyte.
Da müssen Sie nur aufpassen, dass Sie den noch adressieren können.
Deswegen kriegen Sie heute keine, die über 4 Gigabyte hinausgehen.
Es sei denn, Sie haben 4 mit Rechner, dann macht das Sinn, darüber
hinaus zu gehen.
Ansonsten macht das keinen Sinn.
Also, Sie müssen beim Speicherplatz durchaus aufpassen.
Es ist ja nicht so, dass wir mit der wachsenden Größe von Speicher,
der uns zur Verfügung steht, automatisch viel mehr Platz haben für
unsere Berechnungen.
Das Phänomen ist ja, dass alle Anwender, alle Hersteller von
interessanter Software, sofort wissen, wie sie den Platz ausnutzen.
Und insbesondere die Betriebssystemhersteller wissen, wie sie sofort 1
Terabyte oder Gigabyte Daten, erstmal Gigabyte reicht ja schon,
Gigabyte Platz auf der Platte brauchen, nur für Betriebssysteme oder
Ähnliches.
Oder auch mehr als ein Gigabyte.
Also, Speicherplatz ist oft ein Problem.
Insbesondere, wenn Sie nicht auf dem Großrechner arbeiten oder auf
Ihrem Laptop, sondern wenn Sie vielleicht hier auf dem kleinen
Rechner, hier auf diesem kleinen Mikrofon, irgendwas machen müssen
oder Sie haben irgendeinen RFID-Chip oder Sie haben einfach
eingebettete Systeme, bei denen Sie wirklich nur sehr wenig
Speicherplatz zur Verfügung haben.
Dann müssen Sie mit wenig Speicherplatz auskommen.
Auf Ihrer Karte, der KIT-Karte, ist ein gewisser Rechner drin, auf den
EC -Karten, den Bankkarten, Geldkarten sind Chips drauf, die haben
wenig Speicherplatz, wenig Prozessorleistung, mit denen müssen Sie
effizient umgehen können.
Sie wissen, dass da irgendein fluger Programmierer dafür gesorgt
hatte, dass man, ganz tolle Idee gewesen, es reicht ja, wenn man die
Gültigkeit einer Karte überprüfen will, dass man ja nur die letzte
Ziffer anguckt, weil man ja immer nur von einem Jahr zum nächsten nur
die letzte Ziffer verändert.
Und dem war nicht aufgefallen oder den Leuten, die das Programm
abgenommen haben, dass sich bei dem Wechsel von 9 auf 10 nicht nur die
letzte Ziffer ändert und dass dummerweise 0 kleiner ist als 9, sodass
eine Karte, die im Jahr 10 gültig ist, leider bei dem Vergleich von 9
mit 0 nicht mehr gültig ist.
Deswegen hatten wir die ganzen Probleme mit den EC-Karten zu Beginn
dieses Jahres, weil der Übergang von 9 auf 10 nicht vernünftig gemacht
wurde.
Warum wurde es nicht richtig gemacht?
Weil jemand effizient programmieren wollte und wenig Speicherplatz für
die Abspeicherung der Jahreszahl verwenden wollte.
Nur eine Ziffer.
Das ist einfach Dummheit, sowas zu machen, aber sehr effizient.
Da hat jemand versucht, mit wenig Speicherplatz etwas zu machen oder
mit wenig Aufwand, aber hat nicht bedacht, dass man eben auch
funktionale Anforderungen hat, die erfüllt werden müssen.
Dann haben wir hier wenige Berechnungseinheiten.
Wir haben zwar viele Rechner zur Verfügung, aber man muss natürlich
sehen, dass man das auf möglichst wenig oder nicht unnötig Rechner
verwendet.
Ich möchte wenige Nachrichten austauschen bei verteilten Berechnungen,
wenn Sie im Workstation-Cluster rechnen und Sie tauschen dort
Informationen aus.
Das dauert, um mehrere Größenordnungen länger eine Nachricht zwischen
Rechnern zu schicken.
Das wissen Sie, als auf dem Rechner selber eine Operation auszuführen.
Sie können also Millionen Operationen ausführen in der gleichen Zeit,
in der Sie eine Nachricht von einem Rechner zum anderen schicken.
Deswegen muss man sich genau überlegen, wie viele Nachrichten brauche
ich eigentlich?
Wie viele Nachrichten muss ich verschicken?
Viele Nachrichten, viel Kommunikation, kostet sehr viel Zeit.
Und da kann man sehr viel mehr lokal wahrscheinlich machen.
Also, es geht um eine weitgehende Nutzung der verfügbaren Ressourcen
und natürlich auch um eine zuverlässige Ausführung von Aufgaben, auch
bei Auftreten von Störungen.
Auch das ist wichtig.
Ein Bereich, wo wir uns damit also zur Zeit sehr beschäftigen, ist zum
Beispiel bei dem Einsatz von Informationsverarbeitung im
Energiesystem.
Das ist modernes Management im Energiesystem, ist ohne Informatik
zukünftig nicht mehr möglich.
Das muss aber zuverlässig sein.
Und Sie wollen also auch, wenn irgendwo Störungen auftreten, wenn
Komponenten ausfallen, eine Solarzelle nicht mehr arbeitet oder wer
weiß, was da passiert.
Das muss vernünftig passieren.
Ist ein Standard, auch eine Standardaufgabe.
Und wenn Sie jetzt Effizienz analysieren, sind wir die Frage, wie
mache ich das?
Ich kann das machen pro Aufgabe.
Ich möchte eine Folge sortieren und schaue mir an, wie lange dauerte,
wie ist der Aufwand für diese eine Aufgabe?
Wenn ich aber eine Million Folgen sortieren muss, dann interessiert es
mich nicht, wie viel Aufwand ich für eine Instanz habe, sondern wie
viel ich für eine Million Aufgaben brauche.
Das heißt, ich habe dann andere Sichtweise auf den Aufwand.
Also es kann sein für einzelne Berechnungen, für Gruppen von
Berechnungen.
Es kann auch sein, dass ich mir anschaue, wie gut die einzelnen
Ressourcen ausgenutzt werden.
Das heißt, ich habe sehr viele verschiedene Arten, wie ich die
Effizienz eigentlich bewerte.
Die erste Effizienz der Ausnutzung einer Recheneinheit, also zum
Beispiel, wenn Sie Finanzdienstleister sind und alle möglichen
Services anbieten für irgendwelche Kunden und Sie schauen nur darauf,
wie gut Ihre Rechner ausgelastet sind, wie effizient die arbeiten.
Dann können Sie einen großen Fehler machen, wenn dafür die
Antwortzeiten bei den Kunden runtergehen.
Also der Kunde wird eine andere Sicht haben auf die Effizienz der
Berechnungen, als derjenige, der einen IT-Betrieb organisiert in einer
Firma.
Das heißt, auch da muss man gucken, was sind eigentlich die richtigen
Arten, wie ich jetzt eine Effizienzanalyse mache.
Sie sehen schon Vielfalt von Themen, die wir gar nicht alle bearbeiten
können.
Wenn wir jetzt auf den Algorithmusbegriff zurückkommen, wir wollen
Probleme durch Algorithmen lösen, das steht ja hinter allem dahinter.
Wir können nicht nur sagen, ich möchte ein Problem lösen, ich möchte
sortieren, sondern wie mache ich das eigentlich?
Dann kennen Sie aus der Grundlagenvorlesung den intuitiven
Algorithmusbegriff, ein endlich beschriebenes, deterministisches
Verfahren mit Ein- und Ausgabe, das für alle zulässigen Eingaben
terminiert und dessen Operationen effektiv sind.
Also Sie haben hier irgendwie Eingabe, Verarbeitung und Ausgabe und
das Ganze soll für jede zulässige Eingabe terminieren und die
Operation soll effektiv sein.
Da steht hier also einiges an wichtigen Sachen drin.
Die Definitheit der Beschreibung ist ganz wichtig.
Sie können nur etwas machen, was wirklich auf endlich vielen Blättern
Papier auch aufschreibbar ist.
Die Operationen müssen effektiv sein, müssen natürlich ausführbar
sein, dürfen nicht unentscheidbar sein oder ähnliches.
Die Ausführung muss terminieren.
Da legen wir schon drauf Wert.
Normalerweise jedenfalls.
Es gibt auch Anwendungen, wo wir Wert darauf legen, dass die
Ausführung nicht terminiert, weil wir eine kontinuierliche Überwachung
meinetwegen brauchen.
Betriebssystem soll bitte nicht terminieren.
Das soll immer weiterlaufen.
Das Scheduling von Prozessoren soll immer weiterlaufen.
Aber die einzelne Aufgabe innerhalb des Schedulings soll natürlich
ausgeführt werden.
Determiniertheit ist durchaus wichtig.
Aber es ist so, dass Determiniertheit heißt, es soll immer die gleiche
Antwort erzeugt werden aus einer Eingabe.
Ich mache hier irgendeine Eingabe, dann soll auch wirklich die gleiche
Antwort rauskommen.
Das ist nicht immer der Fall heutzutage, sondern Sie haben auch etwas,
was zum Beispiel randomisiert abläuft.
Da sind wir also meiner Gruppe auch Experten in der Ausführung
randomisierter Operationen, randomisierte Algorithmen, insbesondere
bei der Optimierung, kann man randomisierte Verfahren einsetzen,
systematische randomisierte Suche, zum Beispiel evolutionäre
Algorithmen, Ameisen-Algorithmen, Simulation Dealing, Particle Form
Optimization oder ähnliches.
Das sind zufallsgesteuerte Algorithmen.
Und da haben Sie keinen Weg mit jeder Eingabe die gleiche Ausgabe.
Sondern da haben Sie, je nach Zufallszahlen, die Sie erzeugen,
eventuell unterschiedliche Ausgaben.
Sie wollen eine möglichst gute Lösung haben.
Die kann aber unterschiedlich sein, je nachdem, welche Folge von
Zufallszahlen Sie erzeugt haben.
Also randomisierte Algorithmen sind ein wichtiger Bereich.
Insbesondere hat man gezeigt, dass man durch Randomisierung schwierige
Probleme deutlich schneller lösen kann, als wenn man sie nicht
randomisiert betrachtet.
Man kann sogar randomisierte Algorithmen entwerfen, bei denen ich
sogar die Determiniertheit drin habe.
Das heißt, es kommt immer das gleiche, richtige Ergebnis raus.
Aber die Laufzeit ist irgendwie nicht ganz sicher vorherbestimmt,
sondern die Laufzeit kann irgendwie probabilistisch abgeschätzt
werden.
Unterschiedlichste Dinge, die mit randomisierten Algorithmen zu tun
haben, die ich hier aber bei der einfachen Definition eines
Algorithmus normalerweise ausblende.
Die andere Formulierung eines Algorithmus-Betriebes ist, dass ich eine
endliche Beschreibung der Ausführung einer endlichen Folge von
Befehlen auf einer abstrakten Maschine mir anschaue.
Das heißt, ich muss mir anschauen, was sind eigentlich diese
abstrakten Maschinen.
Das hatte ich schon gesagt, die können sehr unterschiedlich aussehen.
Und ich muss mit so etwas irgendwie sinnvoll umgehen können.
Und dazu gehören einerseits die Programmstrukturen.
Wie kann ich das Programm eigentlich formulieren, die Strukturen
darstellen?
Dann muss ich die Daten, auf denen ich arbeiten will, geeignet
darstellen.
Je nachdem, welche Struktur ich verwende, werde ich unterschiedliche
Möglichkeiten haben, mit diesen Daten umzugehen, wird
unterschiedlichen Aufwand verursachen.
Und ich habe unterschiedliche Rechnerstrukturen.
Und diese Dinge haben Einfluss aufeinander.
Je nachdem, sagte ich schon, welche Datenstrukturen Sie verwenden, ob
Sie eine Array oder eine Liste haben oder einen Baum, haben Sie
unterschiedliche Zugriffsmöglichkeiten.
Das heißt, der Zeitaufwand für Standardoperationen ist sehr
unterschiedlich.
Je nachdem, welchen Rechner Sie haben, kann der Zeitaufwand für die
Ausführung von komplexeren Problemen sehr unterschiedlich sein.
Gut, also Strukturen und Algorithmen, schauen wir uns
Programmstrukturen einmal an.
Was sind so die typischen Strukturen?
Kennen Sie alle?
Elementare Anweisungen, Folgen von Anweisungen, Verzweigungen, also If
-Then -Else und Ähnliches oder Case Statements oder was immer Sie
verwenden wollen für Verzweigungen, Schleifen, While, For, Repeat oder
was immer, Prozedur, Funktionsaufrufe, Methoden, Definitionen,
Rekursionen, sinnvolle Strukturen, Objekte, Objekterzeugung, ja
überhaupt, Methoden, Definitionen ist eigentlich Methoden nur ein
anderes Wort für Prozeduren, aber halt in einem etwas anderen
Entwurfszusammenhang.
Kommunikationsoperationen, typische...
Sie finden jetzt zum Beispiel, also Google behauptet, sie hätten etwas
Neues erfunden, indem sie das, was sie Map-Reduce nennen, ein uraltes
Prinzip, das sie neu entdeckt haben, bei dem man einfach Daten
systematisch verteilt und Operationen systematisch auf viele
Einzelrechner verteilt und also große Datenmengen verteilt und dann
die Ergebnisse wieder zurückholt, ist ein uraltes Prinzip der
Informatik, was Google jetzt Map-Reduce nennt und sagt, das wäre eine
ganz tolle neue Idee und die Leute sind alle ganz begeistert.
Ja, aber es ist ein uraltes Prinzip der Informatik, es ist nichts
Neues, das hat man immer schon gemacht.
Aber Map-Reduce ist etwas oder sie wollen irgendeinen Broadcast
machen, das wäre eine Kommunikationsoperation.
Oder sie wollen einfach nur eine Nachricht schicken an irgendjemand
anderen.
Auch wichtige Operationen, die man in Programmen verwenden kann.
Datenstrukturen gibt es alle möglichen, die kennen Sie zum Teil
natürlich auch.
Sie kennen Arrays, Sie kennen vielleicht Records, Sie kennen natürlich
Objekte ganz generell.
Dann kennen Sie spezielle Strukturen wie Listen, Stack oder Queue mit
unterschiedlichen Anforderungen.
Ein Baum, ein Heap, alle diese Strukturen sollten Ihnen bekannt sein.
Sie wissen, dass Sie unterschiedliche typische Operationen haben, mit
denen man darauf zugreifen kann.
Wir werden ein paar von denen auch genauer angucken, aber das steht
nicht im Vordergrund meiner Vorlesung.
Datenstrukturen sind nur am Rande von Bedeutung.
Grid-File, Segmentbaum ist etwas, was man braucht für gerade im
Bereich algorithmischer Geometrie.
Skip-Tree, spezieller Baum, den man bei effizientem Zugriff auf große
Datenmengen verwendet.
Alternative zu einem typischen Baum.
Interfaces sind auch wichtig.
Wie definiere ich eigentlich die Interface für den Zugriff auf
irgendeine Funktion, auf irgendeinen Anwendungsbereich?
Ich könnte das noch weiter fortführen, aber ich denke, das zeigt
schon, was man dort macht.
Rechnerstruktur, wie wird die eigentlich beschrieben?
Ich habe einen Befehlssatz.
Ein Befehlssatz beschreibt eigentlich die Architektur eines Rechners.
Der IBM 360 Befehlssatz sagt genau, was für eine Architektur Sie
haben.
Das ist die IBM-Architektur, bestimmter Prozessor mit bestimmtem
Befehlssatz.
Oder Intel-Architektur, x86-Architektur, klassischer Befehlssatz.
Dieser Befehlssatz charakterisiert die Art, wie wir über Befehle dafür
sorgen können, dass Operationen auf dem Rechner ausgeführt werden
können.
Die Prozessorstruktur ist natürlich noch etwas anderes.
Wie sehen eigentlich Steuerwerk, Rechenwerk, Speicherwerk aus in den
einzelnen Strukturen?
Erinnern Sie sich vielleicht an Grundleitende Informatik 2, dass man
dort sehr interessante Sachen machen kann, wie Pipelining und
Parallelverarbeitung und ähnliche Dinge.
Das spielt ja alles eine Rolle.
Und Verbindungsstrukturen spielen auch eine Rolle, die halt
unterschiedlich sein können.
Und die Beispiele hier sind also das klassische Beispiel die Turing
-Maschine.
Ist natürlich keine praktische Relevanz, weil niemand rechnet mit
einer Turing-Maschine, sondern ein mathematisches Modell, sehr
einfach, abstrakt.
Die Random-Axis-Maschine ist die übliche, oder sehr ähnlich wie der
von Neumann-Rechner.
Da haben Sie halt einfach nur so Ihren Prozessor, Sie haben Ihr
Rechenwerk, also die Processing-Einheit, Sie haben die
Kontrolleinheit, Sie haben noch einen Speicher.
Das ist so die Random-Axis-Machine.
Sie können wahlfrei auf den Speicher zugreifen, Sie können irgendwo
etwas ausführen, Sie können das Ganze steuern.
Das ist so eine Random-Axis-Maschine.
Wahlfreier Zugriff auf Speicherbereiche ist wichtig.
Geht bei der Turing-Maschine nicht, da haben Sie ja die sequentielle
Band, wenn Sie sich falsch erinnern.
Dann gibt es eine PRAM, das ist also eine Parallel Random-Axis
-Maschine.
PRAM heißt also, ich habe dann nicht nur eine solchen Rechner, sondern
ich habe dann viele solche Rechner.
Und diese vielen Rechner, die sind dann irgendwie verbunden mit einem
Verbindungsnetz.
Da geht man normalerweise davon aus, dass ich von jedem Prozessor
beliebig auf irgendeine Speicherzelle in diesem großen Speicher
zugreifen kann.
Ich hatte Ihnen dafür auch im Grundlagen der Informatik 2 ein bisschen
was erzählt, über so Parallel-Rechner-Strukturen, erinnern Sie sich
vielleicht an SIMD, MIMD und solche Dinge.
Da tauchten diese Strukturen auch auf.
Die PRAM ist also das allgemeine Modell für Parallelverarbeitung.
Hypercube, was ist eine Hypercube?
Eine Hypercube ist ein Hyperwürfel, ein beliebig dimensionaler Würfel.
Was ist ein nulldimensionaler Würfel?
Ein nulldimensionaler Würfel ist einfach nur ein Punkt.
Ein Prozessor ist ein nulldimensionaler Würfel.
Eine Random Access Machine ist ein nulldimensionaler Würfel.
Ein eindimensionaler Würfel, den bekomme ich indem ich zwei
nulldimensionale nehme und sie durch eine Kante verbinde.
Ein zweidimensionaler Würfel, den bekomme ich, indem ich zwei
eindimensionale Würfel nehme...
und entsprechende Prozessoren durch eine Kante verbinde.
Einen dreidimensionalen Würfel bekomme ich, indem ich zwei solche
zweidimensionalen Würfel nehme...
und entsprechende Knoten verbinde.
Einen vierdimensionalen Würfel bekomme ich, indem ich zwei solche
dreidimensionale Würfel nehme...
und entsprechende Knoten verbinde.
Also da muss ich dann die verbinden, die verbinden, die, die, die, die
und so weiter.
Die muss ich alle verbinden.
Dann habe ich einen vierdimensionalen Würfel.
Und so können Sie beliebig dimensionale Würfel malen.
Das sind Hyperwürfel, d.h.
in einem eindimensionalen Hypercube haben Sie n Verbindungen...
von jedem Knoten zu, also jeder Knoten n Nachbarn.
Dann haben Sie zwei hoch n Prozessoren in einem eindimensionalen
Hypercube.
Interessante Rechnerstruktur.
Wenn Sie die Anzahl der Knoten anschauen, haben Sie logarithmische
Abstand, logarithmische Pfade zwischen jedem.
Also maximal Abstand ist logarithmisch in der Anzahl der Knoten
zwischen den einzelnen Knoten in so einem Hyperwürfel.
Sie können sich aber vorstellen, dass es nicht so einfach ist, die
tatsächlich in der Fläche auch anzuordnen...
weil die Leitungen sehr lang werden da drin.
Sie haben schon gesehen, dass ich auf einmal lange Leitungen malen
wollte.
D.h.
davor hätte ich alles relativ klein und kompakt machen können.
Beim vierdimensionalen Würfel wird es schon etwas umfangreicher,
länger usw.
Dann gibt es Baumrechner.
Baumrechner sind etwas ganz Einfaches.
Da habe ich also einfach nur irgendwie sowas.
Und das Problem ist, dass ich dann irgendwo immer hier den Engpass an
der Wurzel habe.
Dann gibt es die schönen gitterverbundenen Felder.
Die sind also auch ganz nett.
Das ist also eine klassische Struktur, die man natürlich sehr schön
aufmalen kann.
Weil ich halt hier einfach nur ein zweidimensionales Feld habe.
Jeweils die nächsten Nachbarschaftsverbindungen hier drin.
Und das ist dann also mein zweidimensionales Feld.
Das ist also ein gitterverbundenes Feld.
Jetzt kann man daraus auch noch einen Torus machen.
Ein Torus heißt, also wenn ich ein Blatt Papier nehme, ich falte das
zu einem Zylinder.
Zu einem Zylinder falten heißt, ich male hier überall die Verbinde
einfach, oben und unten.
Dann habe ich daraus einen Zylinder gemacht.
Kein zweidimensionales Feld mehr, sondern ich habe das jetzt einfach
zusammengefaltet.
Das mache ich daraus einen Torus, indem ich jetzt das noch wieder
zusammenfüge.
Also muss ich das hier auch noch verbinden.
Dann habe ich die Seiten auch noch verbunden, dann habe ich daraus
einen Torus gemacht.
Sie haben eine Frage?
Vielleicht auch andersherum.
Gitterverbunden heißt nur, ich habe eine Vierer-Nachbarschaft.
Ich könnte ja auch hier eine Achter-Nachbarschaft machen.
Das wäre nicht das typische gitterverbundene Feld.
Ein gitterverbundenes Feld hat eine Vierer-Nachbarschaft.
Jeder Prozessor ist mit seinen Nachbarn im Norden, Osten, Süden,
Westen verbunden.
Man kann natürlich neben solchen zweidimensionalen Feldern auch andere
Nachbarschaften noch einbauen.
Wenn ich an einem gitterverbundenen Feld rede, dann rede ich immer von
der Vierer-Nachbarschaft.
Man kann das aber auch mit einer Achter-Nachbarschaft machen.
Man kann auch noch zu anderen Nachbarn etwas hinmalen an Verbindungen.
Das wäre dann aber nicht das klassische gitterverbundene Feld.
Und der Torus, wie gesagt, ist so eine Struktur, bei der ich einfach
durch diese sogenannten Wrap-Arounds dafür gesorgt habe, dass ich im
Prinzip keine zu weit entfernten Knoten habe.
Und vor allen Dingen ist es in einem Torus egal, an welcher Stelle ich
mich befinde.
Die Nachbarschaft ist immer gleich.
Also die Abstände zu meinen Nachbarn um mich herum sind immer gleich.
Wenn Sie keinen Torus haben, sondern nur ein gitterverbundenes Feld,
dann wäre eben ein Prozessor am Rand, ohne diese Wrap-Arounds, ein
bisschen abseits, weil er nur zwei direkte Nachbarn hätte.
Und insofern, die Randprozessoren wären etwas benachteiligt, im Torus
sind sie nicht benachteiligt.
Und es ist eine einfache Aufgabe, über sich zu überlegen, wie man so
einen Torus zweidimensional darstellen kann, und Sie haben nur
konstante Kantenlängen.
Eine ganz einfache Aufgabe, da muss man sich nur überlegen, wie man
das geeignet macht.
Das sieht so aus, wenn Sie sich dieses Bild anschauen, dann sieht das
so aus, als wenn Sie hier ganz lange Verbindungen brauchen.
Sie haben ein N-mal-N-Feld, machen da ein Torus draus, dann sieht das
so aus, als bräuchten Sie Leitungen, die hier ganz rumlaufen.
Vom N-mal-N-Feld Länge Größenordnung N haben.
Brauchen Sie nicht, Sie können das mit konstanten Leitungslängen
machen.
Da kann man sich leicht überlegen, wie man dann die Verbindungen malen
muss.
Dann überkreuzen sich zwar ein paar Leitungen, aber sich überkreuzende
Leitungen sind nicht so schlimm.
Kleine Denksportaufgabe nebenbei.
Mesh of Trees ist etwas, da hat man ein Gitter von Bäumen.
Da gehe ich auch nochmal später drauf ein, will ich nicht jetzt
machen.
Dann Multicore, Manicore habe ich schon erwähnt.
Das sind einfach eben heutzutage die Rechner, bei denen man sehr sehr
viele Prozessoren anbieten kann auf einem Prozessorboard.
Sie kennen vielleicht alle die Playstation 3, die hat den
Zeltprozessor.
Auf die bin ich ja auch in der Grundlage in Formatik 2 vorliegen
eingegangen.
Mit einer bestimmten Struktur.
Die heutigen weiterentwickelten Multicore, Manicore-Architekturen
sehen dann auch ein bisschen anders aus.
Sind nicht notwendigerweise gitterverbundene Felder, werden aber
überwiegend doch auf dieser Struktur hinauslaufen.
Weil sie ja in irgendeiner Art und Weise kommunizieren müssen.
Und die gitterverbundenen Felder sind einfach die, was den Zeitaufwand
für die einzelnen Operationen angeht, schon sehr effizienten
Verbindungen.
Also man hat auch andere Verbindungsstrukturen.
Das wäre Thema für eine eigene Vorlesung, Verbindungsstrukturen in
Parallelrechner.
Und dann hier am Ende Internet, The Grid und Clouds.
Bei Clouds wissen sie gar nicht über die physikalischen Strukturen, da
haben sie nur logische, virtuelle Strukturen.
Aber die müssen auch irgendwie realisiert werden.
Auch das ist eine interessante Aufgabe.
Wie kann ich virtuelle Informationsverarbeitungsstrukturen sinnvoll
auf die reale Welt abbilden, sodass gewisse Leistungsanforderungen
auch erfüllt werden können.
Eine der Aufgaben, die jetzt eben von vielen Leuten bearbeitet werden.
Was ich andeuten will durch diese Folie ist einfach, wir sind in einer
sehr sehr vielfältigen Welt, wenn wir uns mit effizienten Algorithmen
beschäftigen.
Das kann man nicht reduzieren auf Algorithmen auf Random Access
Machines.
Das wäre viel zu kurz gedacht.
Und ich muss Ihnen diese Vielfalt von Möglichkeiten irgendwie nahe
bringen und Ihnen zeigen, wie man da systematisch vorgeht.
Gut, also.
Entwurf und Analyse von Algorithmen, da gibt es einige Prinzipien, die
haben Sie schon kennengelernt.
Sie haben insbesondere einiges kennengelernt bei Grundlagen in
Informatik 1 und auch bei Horizons Research Vorlesungen über Divide
and Conquer.
Klassisches Prinzip, Sie wollen ein großes Problem.
Die typische Vorgehensweise der Informatiker ist ja, dass sie sagen,
große Probleme sind uns zu schwer, wir machen sie kleiner.
Und lösen die kleinen Probleme und fügen sie wieder zusammen.
Und Sie wissen, dass das nicht erst die Informatiker erfunden haben,
sondern ganz andere Leute, die von Divide and Conquer geredet haben.
Alles ein uraltes Prinzip.
Dynamic Programming, auch ein altes Prinzip, kennen Sie.
Sie erinnern sich an die Reduktion von Automaten oder an die
Überprüfung der Zugehörigkeit von Wörtern zu kontextfreien Sprachen.
Das waren die Dynamic Programming Ansätze.
Branch and Bound kennen Sie, viele Verfahren aus dem Operations
Research.
Greedy Algorithmen, typische Heuristiken, bei denen man gierig die
nächstbeste Lösung wählt.
Nicht unbedingt optimal, aber trotzdem häufig ganz gut.
Typischer Entwurfsprinzip, mit dem man Heuristiken sehr sinnvoll
entwerfen kann.
Scanline Prinzip, etwas was man bei geometrischen Algorithmen
entwickelt.
Also es gibt viele verschiedene Entwurfsprinzipien.
Es gibt die Analyse-Methoden.
Da frage ich nach der Effizienz, also nach der Zeit.
Wie frage ich nach der Zeit?
Ich kann mich mit der Stoppuhr daneben setzen.
Ich hatte vorhin gesagt, Sortier-Challenges sind in der Art, wie viele
Daten kann ich in einer Stunde sortieren.
Egal welcher Rechner und so weiter.
Da sitze ich mit der Stoppuhr und zähle und messe einfach.
Aber normalerweise will ich ja allgemeine, generalisierbare Aussagen
machen.
Und dann muss ich also etwas sagen über die Anzahl der
Programmschritte, über die CPU-Zeit.
Ich will etwas über den Platz sagen.
Nicht eigentlich so viele Transistoren oder so viel Quadratzentimeter,
sondern so viele Speicherzellen meinetwegen.
Die Anzahl der Prozessoren kann eine Rolle spielen.
Diese Lithiumfläche auf dem Paulus-E-Chip, warum ist das so relevant?
Stellen Sie sich vor, Sie haben hier eine Reihe von Prozessoren und
die wollen miteinander kommunizieren.
Die haben Sie jetzt so schön angeordnet, linear.
Jetzt wollen die miteinander kommunizieren.
Da wollen also die nächsten Nachbarn hier direkt miteinander
kommunizieren.
Jetzt wollen vielleicht auch die übernächsten direkt miteinander
verbunden sein.
Das kann man ja auch noch hinkriegen.
Jetzt wollen auch noch die jeweils mit ihrem dritten Nachbarn
kommunizieren können.
Das geht natürlich auch noch.
Und so weiter.
Und noch mit dem vierten.
Und noch irgendwie.
Und noch irgendwie etwas.
Sie wollen jetzt für jede Kommunikation eine eigene Datenverbindung
haben.
Jeder mit jedem.
Sie haben also jetzt hier eine lineare Anzahl von Prozessoren und
wollen eine Verbindung jeder mit jedem haben.
Dann brauchen Sie quadratischen Platz.
Das heißt, Sie haben zwar eine effiziente Darstellung Ihrer
Prozessoren, aber für die Kommunikation brauchen Sie nicht linearen
Platz, sondern quadratischen Platz in der Anzahl der Prozessoren, die
miteinander kommunizieren wollen.
Das heißt, die Fläche auf einem Siliziumchip, wo Sie halt nicht
beliebig viele Leitungen übereinander anordnen können, da können Sie
nicht so ein dickes Bündel irgendwo durchlegen, sondern da müssen Sie
nicht schön, Sie können vielleicht drei, vier Leitungen übereinander
machen, da müssen Sie die nebeneinander legen.
Da haben Sie halt einfach sehr viel Fläche auf einem Chip, die nur für
Kommunikation draufgeht.
Und das gleiche können Sie dann mit auf Volumen übertragen.
Wenn Sie also in die dritte Dimension gehen, brauchen Sie eben auch
bestimmtes Volumen für Ihre Berechnungen.
Und dieses Volumen ist nicht nur durch die Anzahl der Prozessoren
bestimmt, sondern auch durch die Kommunikationsstruktur.
Dann der Kommunikationsbedarf.
Wenn Sie verteilte Algorithmen anschauen, dann zählt man häufig
überhaupt nicht die Anzahl der Operationen, die in einem Rechner
ausgeführt werden, also die Anzahl der Rechenoperationen, sondern Sie
zählen die Anzahl der Nachrichten, die ausgetauscht werden.
Weil das den Zeitaufwand im Wesentlichen bestimmt.
Das wäre dann der Kommunikationsbedarf als Komplexitätsmaß bei
verteilten Algorithmen.
Ich werde verteilte Algorithmen in dieser Vorlesung nicht behandeln,
das ist wieder eine eigene Vorlesung.
Aber trotzdem ist es richtig zu wissen, dass es eben diese anderen
Dinge noch gibt.
Dann ist das Ganze abhängig von der Größe der Eingabe.
Sie haben also, ist klar, wenn Sie eine Folge der Länge bis drin
haben, brauchen Sie weniger Zeit, als wenn Sie eine Folge der Länge
drei Millionen haben.
Und Sie schauen sich an, das Verhalten im schlechtesten Fall und im
Mittel, oder auch einen amortisierten Aufwand über eine ganze Folge
und eine ganze Menge von Berechnungen.
Das heißt, manchmal müssen Sie wirklich etwas sagen können über den
schlechtesten Fall.
Wenn Sie Aussagen machen über das Verhalten Ihrer Funktion, die Sie im
Airbus verwenden, in irgendeinem modernen Flugzeug, dann brauchen Sie
eine Worst-Case-Analyse.
Sie müssen wissen, dass die Worst-Case-Execution-Time, diese Analyse
WCET abgekürzt, ist da die Standard-Analyse-Methode für Echtzeit
-Anwendungen.
Da müssen Sie wissen, innerhalb welcher Zeit kann ich, egal unter
welchen Bedingungen, garantiert eine Antwort erwarten.
Für viele Anwendungen reicht es aber aus, wenn wir ein mittleres
Verhalten kennen, da brauchen wir nicht die Worst-Case-Execution-Time.
Und insbesondere ist es eben häufig so, dass wir zwar Algorithmen
haben, die im schlechtesten Fall sehr lange dauern, aber so im Mittel
recht gut sind.
Klassisches Beispiel ist Quicksort, wo Sie im schlechtesten Fall
quadratische Zeit brauchen, aber es heißt nicht umsonst Quicksort,
weil Sie halt bei einer vernünftigen Streuung Ihrer sortierenden
Folgen da mit NlogN hinkommen, also deutlich schneller.
Also im Mittel können Sie manchmal ein deutlich besseres Verhalten
haben und das kann eben dann auch wichtig sein, wenn die
Ausführungsdauer für eine Berechnung nicht ganz so relevant ist.
Gut, wenn wir uns jetzt auf die Zeit nochmal genauer konzentrieren.
Was heißt das, dass wir über Zeiten reden?
Wir haben also einen Algorithmus und der hat irgendeine Eingabemenge
x, irgendeine Menge.
Und jetzt habe ich hier irgendein Element drin und ich habe jetzt eine
Größenangabe.
Ich sage, die Problemgröße spielt eine Rolle.
Ich habe also eine Funktion, die gibt mir die Größe der Elemente von x
an.
Jetzt habe ich also irgendeine Eingabe x, dann sei also ta von x die
Rechenzeit von a bei Eingabe von x.
Folge der Länge 17 hat irgendwie so und so viele Millisekunden.
Und ich kann jetzt sagen, ich möchte nicht nur eine bestimmte Folge
mir angucken, sondern ich möchte das für Folge einer bestimmten Größe
machen.
Dann schaue ich mir also an, die Rechenzeit eines Algorithmus a bei
Anwendung auf Eingaben der Größe n.
Also, das ist das Maximum aller Zeiten des Algorithmus auf
irgendwelchen Eingaben, die die Größe n haben.
Das ist dann die Zeitkomplexität von a im schlechtesten Fall.
Kennen Sie alles?
Haben Sie in der Grundlage Informatik 1 schon mal gelernt?
Ich muss nur wiederholen, dass wir sagen, das ist tatsächlich die
Worst Case Execution Time.
Und wenn ich jetzt etwas über den mittleren Fall sagen möchte, dann
muss ich natürlich wissen, wie sind eigentlich meine Eingaben
verteilt.
Über den mittleren Fall kann ich nur was aussagen, also den
Erwartungswert der Zeit, wenn ich etwas weiß, wie die Eingaben
verteilt sind.
Das weiß ich häufig leider gar nicht.
Deswegen macht man meist eine Annahme, dass die irgendwie gleich
verteilt sind.
Dann ist es einfach das arithmetische Mittel.
Aber im Prinzip ist es der Erwartungswert aller dieser Zeiten des
Algorithmus für Eingaben einer festen Größe n.
Das ist die mittlere Zeitkomplexität dieses Algorithmus.
Und Sie wissen, dass das manchmal etwas schwieriger ist, etwas über
die mittlere Zeitkomplexität auszusagen.
Ich weiß nicht, ob Sie das überhaupt systematisch analysiert haben.
Wir werden das in der Vorlesung an ein paar Beispielen aber durchaus
machen.
Das können Sie natürlich genauso jetzt für die Platzkomplexität machen
usw.
Das geht nicht nur für die Zeitkomplexität.
Da können Sie genauso gut die Platz eines Algorithmus A für eine
Eingabe X machen oder für alle Eingaben einer gewissen Größe usw.
Was wollen wir jetzt damit erreichen, wenn wir so eine Aussage machen?
Wir machen eine Kostenabschätzung.
Wir wollen eine Aussage über die Qualität eines Algorithmus haben.
Wie gut ist der eigentlich?
Wenn ein Algorithmus irgendwelche Kosten hat, ist das erstmal ein
nicht bewerteter Begriff.
Ich habe bestimmte Kosten.
Ob der gut ist, kann ich nur sagen, wenn ich weiß, ob er besser oder
schlechter als ein anderer ist.
Also ich mache einen Vergleich mit anderen Algorithmen, die das
gleiche Problem lösen.
Oder ich kenne irgendwelche unteren Schranken für den Aufwand.
Wenn ich untere Schranken kenne, dann kann ich aber sagen, dies ist
der bestmögliche Algorithmus.
Das ist natürlich das, was ich gerne möchte.
Dann kann ich nämlich meinem Arbeitgeber, wenn der sagt, mach mal den
Algorithmus schneller, sagen, nein, geht nicht.
Der ist bestmöglich.
Und das heißt, so etwas ist ganz wichtig, dann habe ich eine absolute
Aussage über die Qualität des Algorithmus.
Das geht nicht besser.
Wir haben das bei vielen Problemen so, dass wir es bis auf konstante
Faktoren angeben können.
Manchmal können wir sogar Algorithmen angeben, die sind, da ist die
untere Schranke sogar bezüglich des konstanten Faktors identisch mit
der oberen Schranke.
Das heißt, wir können Algorithmen angeben, die sind sogar im Bezug auf
den konstanten Faktor optimal.
Das sind seltene Fälle, aber es passiert.
Es gibt andere Fälle, wo wir große Abstände haben zwischen der unteren
Schranke und den bekannten oberen Schranken, also Algorithmen, die das
Problem lösen.
Das heißt, wenn wir etwas sagen wollen über die Qualität eines
Algorithmus, müssen wir Vergleiche anstellen können, entweder mit
anderen Algorithmen, die das gleiche Problem lösen, oder mit unteren
Schranken.
So, kurzes Beispiel.
Typische Tabelle zeigt man eigentlich in so einer der ersten
Vorlesungen zu irgendwie Programmieren oder Algorithmen.
Schauen wir uns einfach an, vier verschiedene Algorithmen, die haben
verschiedene Rechenzeiten.
Kann ich also abschätzen hier meinetwegen TA von n.
Also bei Ausführung auf Problem der Größe n seien so und so viele
Millisekunden erforderlich.
Der erste hat hier 1000 n Millisekunden, der zweite 200 n log n, der
dritte 10 n Quadrat und der letzte 2 hoch n.
Niemand von Ihnen würde wahrscheinlich den letzten verwenden.
A4, 2 hoch n, exponentielles Verhalten, das ist ja schrecklich.
Jetzt sagen Sie mir nicht, das ist ein Beispiel, das niemand so jemals
verwenden wird.
Sie brauchen nur in die Literatur zu schauen, zum Beispiel für die
Berechnung von Fibonacci Zahlen.
Da finden Sie Algorithmen, die haben wirklich exponentielle
Laufzeitunterschiede.
Je nachdem, wie clever Sie diese Algorithmen formulieren.
Aber trotzdem ist das hier ein fiktives Beispiel.
Was ich daran zeigen möchte, ist Folgendes.
Wir schauen uns einfach mal an, die maximale Größe eines Problems, das
sich mit diesen Algorithmen in einer vorgegebenen Rechenzeit ausführen
kann.
Wenn ich eine Sekunde zur Verfügung habe, dann braucht dieser hier mit
1.000 n, der braucht halt 1.000 n Zeit, das heißt die Größe darf 1
sein.
Der hier unten mit 2 hoch n, der kann eine Größe von 9 in einer
Sekunde berechnen.
2 hoch 9 Millisekunden, das kommt gerade hin.
Das sind also weniger als 1.000 Millisekunden, also weniger als eine
Sekunde.
Das heißt, der ist besser.
Und der mit der quadratischen Laufzeit, der ist in dem Fall der Beste.
Der kann bis zur Größe von 10 etwas machen.
Der mit n log n hat hier eine Größe von 3.
Wenn wir jetzt eine Minute zur Verfügung stellen, dann ist auch dann
noch nicht mal der lineare besser, dann ist der hier mit der
quadratischen Laufzeit immer noch besser als die anderen.
Und der mit der exponentiellen Laufzeit fällt natürlich sofort ab.
Das ist ganz klar.
Und wenn wir eine Stunde zur Verfügung haben, dann gewinnt natürlich
derjenige mit der linearen Laufzeit.
Und wir haben also dann natürlich auch hier bei dem mit n log n
besseres Verhalten als bei dem, der quadratische Laufzeit hat.
Und der exponentielle ist natürlich einfach ganz schlecht,
grottenschlecht.
Und das wird natürlich umso klarer, je größer die Zahl ist.
Was ich halt deutlich machen will, ist einfach nur, es gibt Bereiche,
Problemgrößenbereiche, in denen jeder dieser Algorithmen optimal ist.
Wenn Sie praktisch einen Algorithmus einsetzen, wissen Sie manchmal,
ich habe Probleme, die sind nur in dem Größenbereich.
Und dann ist Ihnen das asymptotische Verhalten eines Algorithmus
völlig egal.
Es kommt darauf an, wie kann der Probleme dieser Größenordnung
besonders gut lösen.
Da müssen Sie auf die konstanten Faktoren gucken, dann reicht es
nicht, nur so Größenordnungsabschätzungen zu machen wie n log n oder n
oder n² oder 2on.
Da müssen Sie schauen, wie sehen die konstanten Faktoren aus und erst
dann wissen Sie etwas, wie realistisch ein Algorithmus eingesetzt
werden kann.
Das sind Sachen, die macht man in Algorithm Engineering zum Beispiel.
Da schaut man sich die konkrete Komplexität der einzelnen Probleme an
für realistische Problemgrößenbereiche.
Und nicht nur asymptotisch, wie man das in der klassischen Algorithmie
gemacht hat.
Natürlich habe ich immer noch die Bedeutung des Verhaltens für große n
hier zu betrachten.
Ich weiß nicht, warum hier so ein Zwischenraum ist.
Das ist irgendwie ein Darstellungsproblem.
Also für große n habe ich natürlich klare Unterschiede.
Dieser Algorithmus A3 ist natürlich 5400 mal schneller als der
Algorithmus A4 bei Größenordnung 25.
Also das ist klar, exponentielle Laufzeit ist etwas Schlechtes, wenn
ich in der Problemgröße hochgehe.
Und noch ein kurzes Beispiel dafür, dass ich tatsächlich Beispiele
finde, wo ich solche Laufzeitunterschiede habe.
Ich hatte Fibonacci-Zahlen genannt.
Anderes einfaches Beispiel, Auswertung eines Polynoms.
Ich möchte also hier so ein Polynom auswerten, d.h.
berechnen, welchen Wert das hat.
Polynom ist eine Summe a i x hoch i.
Und d.h.
wenn ich das jetzt von links nach rechts auswerte, würde ich an mal x
mal x mal x mal x mal x und so weiter machen, bis ich x hoch n habe.
Dann plus a n minus 1 mal x und so weiter.
Ich könnte es strikt von links nach rechts hier auswerten und würde
auf eine quadratische Anzahl von Multiplikationen kommen.
Ja, strikt von links nach rechts ausgewertet.
Ich könnte aber auch das Problem anders aufschreiben.
Ich könnte die Gesetze der Arithmetik anwenden, ausklammern und hätte
dann hier stehen a n mal x plus a n minus 1 in Klammern mal x plus a n
minus 2 in Klammern mal x und so weiter.
Und wenn Sie das von links nach rechts auswerten, dann haben Sie n
Multiplikationen und n Additionen.
Das heißt, nur durch eine Anwendung der Gesetze der Arithmetik haben
Sie hier einfach Dinge ausgeklammert, Distributivgesetz angewandt und
Sie können auf diese Art und Weise eine Reduktion von einem
quadratischen Algorithmus auf einen linearen Algorithmus machen.
Und dieser ist übrigens mit n Multiplikationen und n Additionen
optimal.
Tatsächlich, diese 2n arithmetischen Operationen sind optimal.
Man braucht auch 2n arithmetische Operationen, n Multiplikationen und
n Additionen, um beliebige solche Polynome auszuwerten.
Das werden wir später noch lernen, dass das tatsächlich so ist.
Das geht nicht besser.
Dieser einfache Algorithmus ist tatsächlich nachweisbar optimal.
Okay, das ist also nur um zu zeigen, man muss sich genauer anschauen,
wie sind Algorithmen strukturiert, was die Problemgröße ist, wie ich
etwas anschaue.
Und ich habe tatsächlich für gewisse Probleme Algorithmen, die um
Größenordnungen voneinander unterschieden sein können.
Sie wissen, was ein asymptotischer Aufwand ist.
Bei diesem Beispiel hier unten habe ich je nach Verfahren O von n
Quadrat oder O von n arithmetische Operationen.
Diese Notation für die asymptotischen Aussagen, die kennen Sie aus
Grundleitung 1 oder auch aus anderen Vorlesungen aus der Mathematik.
Wir wollen also so Aussagen machen über das Wachstum von Funktionen.
Also irgendeine Funktion f soll das Wachstum charakterisieren für
viele andere Funktionen.
Das heißt, ich habe meinetwegen hier irgendeine Funktion, die wächst
irgendwie so.
Und jede andere Funktion, die in einer Art wächst, die ab einer
bestimmten Stelle, also ab irgendeinem n, habe ich für alle größeren n
höchstens so großes Wachstum dieser Funktion g wie eine Konstante mal
dieser Funktion f.
Das heißt, ich habe eine obere Schranke für das Wachstum der
Funktionen, Konstante mal diesem f.
Also in dem Beispiel Groß O von n heißt das, wenn eine Folge in Groß O
von n oder wenn eine Funktion in Groß O von n liegt, dann wächst sie
nicht schneller ab irgendeiner Schranke als meinetwegen 17 mal n.
Ich muss also eine Konstante c geben, sodass ich ab einer bestimmten
Stelle tatsächlich diese Wachstumsbeschränkung nach oben habe.
Das ist Groß O.
Klein O ist deutlich stärker.
Das heißt, dass f ist eine ganz starke Beschränkung.
Also meine Funktionen, die in Klein O von f liegen, wachsen wesentlich
langsamer als die Funktion f.
Das heißt, das Verhältnis von g von n und f von n ist eine Nullfolge
für wachsendes n.
Das f von n wächst deutlich schneller als das g von n.
Nicht nur durch einen konstanten Faktor unterschieden, dann wäre es
irgendein c, sondern das ist 0.
Das heißt, f von n wächst deutlich schneller als g von n.
Das Ganze kann ich auch andersrum machen.
Für untere Schranken, dann habe ich halt einfach das c mal f von n als
untere Schranke.
Das heißt, da sind alle Funktionen drin, die mindestens so stark
wachsen wie eine Konstante mal f.
Also mindestens linear oder mindestens quadratisch.
Und Klein Omega von f entsprechen Funktionen, die wesentlich schneller
wachsen als diese Funktion f.
Das f ist also eine untere Schranke.
Und wir wissen, dass die Funktionen, die da drin liegen, wesentlich
schneller wachsen als dieses f.
Dann gibt es noch das Theta von f, das beides zusammenfasst.
Wenn also eine Funktion in Groß-O und Groß-Omega ist, dann ist sie
auch ein Theta.
Das heißt, das Wachstum der Funktion ist nach unten und oben
beschränkt durch diese Funktion f.
Bis auf einen konstanten Faktor.
Das kann man so ausdrücken, wie es hier steht.
Andere Beschreibung von Groß-Theta von f ist einfach der Durchschnitt
von Groß-O von f und Groß-Omega von f.
Und dann gibt es dazu noch eine ganze Reihe laxer Schreibweisen.
Eigentlich müsste man schreiben, die Funktion liegt in Groß-O von f.
Man schreibt aber oft g gleich Groß-O von f.
Das ist natürlich falsch.
Das ist keine Gleichheit, das ist ein Element einer Menge, das g.
Trotzdem schreibt man das manchmal so.
Oder Sie schreiben Groß-O von f.
Es müsste eigentlich Groß-O von f enthalten in Groß-O von g sein.
Tatsächlich finden Sie Groß-O von f gleich Groß-O von g. Dieses sollte
eigentlich da drüben stehen.
Das ist irgendwie verrutscht.
Sie können also hinschreiben Groß-O von n gleich Groß-O von n².
Was das Enthaltensein angeht, ist es richtig.
Groß-O von n ist enthalten in Groß-O von n².
Aber es ist natürlich Groß-O von n² ungleich Groß-O von n.
Das ist einfach laxe Schreibweise.
Das macht man manchmal so, dass man da in Gleichheit hinschreibt.
Aber das ist einfach verkehrt.
Man müsste eigentlich immer diese Notation nehmen oder die Notation.
Ich werde versuchen, mich daran zu halten.
Sie finden häufig einfach da ein Gleichheitszeichen drin.
Das stimmt halt einfach.
Sie kennen alle diese Notationen.
Wahrscheinlich haben Sie im Wesentlichen nur mit Groß-O gearbeitet.
Weniger mit Groß-Omega.
Wenig vielleicht mit Klein-O und Klein-Omega.
Wird manchmal in der Mathematik auch angewandt.
Vor allen Dingen in der Informatik.
Und wenn wir die Komplexität einer Funktion oder eines Problems jetzt
anschauen wollen, dann reden wir halt nicht mehr von Komplexität eines
Algorithmus, sondern von Komplexität eines Problems.
Das heißt, dann haben wir irgendein Problem und irgendeine untere
Schranke für die Zeitkomplexität, würde dann sagen, dass alle
Algorithmen, die das Problem lösen, eine Zeitkomplexität haben, die in
Omega von f liegt.
Das heißt, die Funktion, die den Zeitaufwand beschreibt für den
Algorithmus A, wächst mindestens so stark wie die Funktion f.
Also, Auswertung von Polynomen.
Die untere Schranke dafür ist Omega von n, also ist eine lineare
Funktion in n.
Wir brauchen lineare Zeit, um auf sequentiellen Rechnern die Polynome
auszuwerten.
Und die obere Schranke für die Zeitkomplexität wäre dann gerade eine
Aussage für einen Algorithmus.
Das heißt, ein Algorithmus, der das Problem löst, der kann durch f
nach oben abgeschätzt werden.
Beispiel Matrixmultiplikation wächst mit O von n hoch 3.
Das heißt, wenn Sie n mal n Matrizen multiplizieren, brauchen Sie n
hoch 3 arithmetische Operationen.
Also ist eine obere Schranke n hoch 3.
Eine untere Schranke in dem Fall ist n².
Großer Unterschied zwischen unterer und oberer Schrank.
Das werden wir später noch genauer kennenlernen.
Und es ist natürlich wichtig, dass A und B dabei bezogen sind auf die
gleiche Rechnerstruktur.
Sie können natürlich etwas aussagen, ich sagte gerade,
Matrixmultiplikation hat eine untere Schranke von n².
Ich kann aber Matrizen in logarithmischer Zeit multiplizieren, wenn
ich die geeignete Rechnerstruktur habe.
Wenn ich viele Operationen parallel machen kann, dann geht das auch in
logarithmischer Zeit.
Aber eben nicht auf einem sequentiellen Rechner.
Wenn ich die Anzahl der Operationen zähle, brauche ich auch auf dem
Parallelrechner Größenordnung, also mindestens n², meistens n hoch 3
Operationen.
Diese Aussagen müssen sich immer beziehen auf die gleiche
Rechnerstruktur, damit man auch sinnvolle Aussagen dabei hinbekommt.
Es ist offensichtlich, dass es schwierig ist, untere Schranken zu
bestimmen, weil man da Aussagen machen muss über beliebige
Algorithmen, insbesondere beliebige Algorithmen mit Papier.
Und das ist aber das, was ich eigentlich haben möchte.
An wenigen Problemen werde ich Ihnen zeigen, dass man da vernünftige
Aussagen hinbekommt.
Aber wir werden in der Regel nur Algorithmen vergleichen und sagen,
der ist besser als ein anderer.
Und es ist offensichtlich, dass ohne Kenntnis unterer Schranken eben
keine Aussagen möglich sind.
Ob ein Algorithmus optimal ist, ob es nicht noch besser geht, das geht
nur, wenn ich untere Schranken kenne.
Und damit sind wir für heute am Ende.
Ich werde Ihnen also nächstes Mal noch ein bisschen was über
Zeitmessung erzählen und dann kommen wir nächstes Mal vor allen Dingen
auf die Berechnungsmodelle, um ein bisschen mehr über
Kostenabschätzung machen zu können.
Vielen Dank.