So, schönen guten Morgen.
Ich begrüße Sie zur Vorlesung Effiziente Algorithmen im Sommersemester
2013.
Sommer ist rechtzeitig gekommen.
Hoffentlich bleibt er ein bisschen länger als nur ein paar Tage.
Also, mein Name ist Hartmut Schmeck.
Ich bin am Institut für Angewandte Informatik und Formale
Beschreibungsverfahren, AISB.
Sie kennen mich wahrscheinlich aus der Bundesvorlesung.
Außerdem am Institut für Angewandte Informatik im Norden, Campus Nord
und auch im Forschungszentrum Informatik.
Ich möchte Ihnen einiges an organisatorischen Dingen zunächst mal
erzählen, wie so üblich in der ersten Vorlesung.
Also hier nochmal meine Kontaktdaten, mein Bild für diejenigen, die
diese Vorlesung sich nur anhören und nicht hier im Raum erscheinen,
sondern sich die Aufzeichnung anhören und ansehen.
Die üblichen sonstigen Informationen, also hier der Link auf die
Vorlesungsseite im VAB, also im Studierendenportal.
Ich glaube, ich kann es mir ersparen, da jetzt raufzugehen.
Sie kennen die Seiten, die Vorlesungsarbeitsbereiche mit den ganzen
Informationen, die man möglicherweise so braucht.
Termine der Vorlesung sind Ihnen gut bekannt.
Alle, die hier im Raum sind, wissen, dass heute 9.45 bis 11.15 im
Dienstag die Vorlesung geht, im Raum 221.
Und die Übung ist freitags entweder von 9.45 an oder ab 11.30 im Raum
231, also hinten am anderen Ende von diesem Flur.
Die Klausur wird sein, wie üblich, in der ersten vorlesungsfreien
Woche nach Ende der Vorlesungszeit, also am 22.23 bis 24.07.
Und Sie wissen, dass Sie da mitschreiben dürfen und Sie dürfen auch
das am Ende des Wintersemesters machen, aber in der Regel machen Sie
das erst am Ende dieses Semesters.
Die Folien, die ganzen Unterlagen über die Vorlesung sind natürlich
verfügbar im VHB als PDF-Version, sowohl in der Version, die Sie jetzt
zum ersten Mal sehen, dann mit Annotationen, worüber man über den Wert
der Annotationen manchmal streiten kann.
Die mache ich vor allen Dingen, damit etwas passiert auf der Folie.
Natürlich auch, um Dinge weiter zu erläutern, aber auch damit etwas
passiert auf der Folie.
Wenn man sich die Aufzeichnung anschaut, muss man einfach ständig
darauf malen und nicht, was ich hier gemacht habe, gar nicht mit dem
Cursor draufgehen.
Man muss also hier immer irgendwo etwas tun auf der Folie, damit man
sieht, wenn man das anschaut nachher, dass dort irgendetwas gerade,
dass dort irgendetwas hinweist.
Dann haben wir natürlich die aufgezeichneten Vorlesungen.
Auch das kennen Sie.
Wer von Ihnen hat noch nie eine aufgezeichnete Vorlesung benutzt?
Wie?
Aha.
Wir sind neu.
Okay, herzlich willkommen.
Ja, dann vergleichst du die nachher, wo sie herkommt.
Also, aufgezeichnete Vorlesungen, ich zeichne auch mit Camtasia, mit
Frame Grabbing.
Das heißt, alles, was auf dem Bildschirm passiert, ist aufgezeichnet
und man kann es dann abspielen.
Also, nicht nur, was auf dem Bildschirm passiert, auch der Ton wird
aufgezeichnet, wobei ich den Ton nur aufnehme mit dem internen
Mikrofon.
Ich hoffe, dass die Qualität ausreichend ist, denn ich muss nochmal
mit einem anderen Mikrofon experimentieren.
Aber so im Wesentlichen sollte eigentlich die Qualität reichen.
Die Mikrofone im Laptop haben sich auch deutlich verbessert.
Sie können diese Vorlesungen abrufen im Diva Digitalen Video- und
Audioaktiv.
Das mache ich ja seit Jahren.
Und jetzt gibt es seit neuestem, wenn man dann meldet, ich will die
Vorlesungen wieder ins Videoaktiv reinstellen, werde ich gefragt, soll
die Vorlesung auch bei iTunes U erscheinen.
Und ich habe bisher immer gesagt, nein.
Warum bei iTunes U?
iTunes U ist eine proprietäre Plattform, von einer bestimmten Firma
veranstaltet.
Warum soll ich für die Werbung machen?
Warum sollen die die wertvollen Informationen, die ich mir in meiner
Vorlesung anbiete, warum soll Apple davon profitieren, dass Leute auf
deren Seite gehen und dort auf Vorlesungen zugreifen?
Wenn das eine neutrale Plattform wäre, würde ich das ja machen, weil
ich habe es ja auf einer neutralen Plattform einigermaßen neutral.
KIT, Diva, da ist es weltweit verfügbar.
Also warum muss ich auf iTunes U gehen?
Würde von Ihnen jemand das befürworten, dass ich die Vorlesungen auch
auf iTunes U ablege?
War jemand von Ihnen schon mal auf iTunes U und hat sich dort
Vorlesungen angeschaut?
Noch nicht?
Ach, das hat überhaupt keinen Effekt, wenn man da was aufzählt.
Aber es ist so, dass die Fakultät der Informatik sagt, jetzt, das muss
da alles drauf.
Wir müssen also zeigen, dass wir auch präsent sind auf den
wesentlichen Vorlesungsarchiven.
MIT macht das, alle großen Universitäten machen das, dann muss das KIT
das auch machen.
Also ich kann darauf verzichten, bisher.
Wenn das gewünscht wird, kann ich das auch machen, aber ich denke, es
reicht erstmal so.
Hier steht ja etwas zum Abspielen.
Sie können es also runterladen.
Anders als bei vielen anderen Plattformen ist es so, dass wir eben die
Vorlesungen runterladbar machen.
Das heißt, Sie müssen sich nicht nur auf die Streamingversion
verlassen.
Wenn Sie nur die Streamingversion anschauen, müssen Sie halt ständig
dann online sein und das dort anschauen.
Aber Sie können, wenn Sie es runtergeladen haben, das heißt zu
beliebigen Zeiten, in der Geschwindigkeit, die Sie haben wollen, mit
den Einstellungen, die Sie haben wollen, sich anschauen.
Und vor allen Dingen ist es dann sinnvoll, sich den Camtasia-Player
runterzuladen und den zu verwenden.
Warum?
Nicht, weil ich so ein Fan von Camtasia bin, sondern weil dieser
Player eine gewisse Eigenschaft hat, dass man sichtbar scrollen kann.
Es mag sein, dass es auch auf weitere Player mittlerweile gibt, die
das können.
Das ist aus didaktischen Gründen ganz wichtig, aber auch aus
Benutzbarkeitsgründen.
Wenn Sie ein sichtbares Scrolling haben, können Sie halt beliebig
schnell vor und zurück durchlaufen durch die Vorlesungen.
Und das, was Sie entgegenstellen, wo es Sie interessiert, hören Sie
auf und sind genau da drin.
Sie sehen also, wie Sie durchscrollen.
Wenn Sie den normalen Windows-Media-Player nehmen, haben Sie kein
sichtbares Scrolling, dann müssen Sie raten, wo Sie hinspringen.
Wenn Sie die genaue Position kennen, dann können Sie da hinspringen,
weil die kennen Sie normalerweise nicht.
Weil Sie nicht wissen, an welcher Sekunde der Vorlesung irgendetwas
Interessantes drinsteht.
Also das ist einfach sinnvoll, den Camtasia-Player zu nehmen, wegen
dieses sichtbaren Scrollings.
Ansonsten können Sie beliebige andere verwenden.
Dann sollten Sie aber den Codec von TechSmith verwenden, auf den
können Sie sich runterladen.
Warum zeichne ich überhaupt auf?
Damit Sie anschließend mehr Informationen haben über die Vorlesungen.
Sie können das nachbereiten, Sie können in den Tutorien, wenn Sie
Aufgaben bearbeiten, sich kurz was angucken und natürlich können Sie
sich für die Prüfung vorbereiten.
Und für die Personen, die zufällig gleichzeitig eine andere Vorlesung
haben oder irgendetwas anderes Wichtiges zu tun haben, die können dann
sich diese Vorlesung halt auch zu einer anderen Zeit anschauen.
Und deswegen ist dadurch die Überlappung von Vorlesungen nicht mehr
ganz so ein großes Problem, weil man halt auch unabhängig von dem
Vorlesungstermin sich den Inhalt anschauen kann.
Und wenn Sie dann noch intensiv an den Übungen teilnehmen, dann haben
Sie eigentlich die wesentliche Information.
Gut, das war's also zu der Vorlesungstechnik.
Dann, ja, Nukit, Cooperation Tools, also Kooperationswerkzeuge.
Wer hat die schon mal genutzt?
Einige, die in der Grundlagenvorlesung waren, Grundlageninformatik 2.
Ich stelle Sie jetzt ganz kurz vor, ob ich sie tatsächlich nutzen
werde, werden wir sehen.
Hier unten habe ich schon das Feedback-Werkzeug da drin.
Man kann also damit Rückmeldungen geben und auf verschiedene Art und
Weise.
Ich zeige Ihnen gleich, was man alles machen kann.
Das ist ursprünglich mal entwickelt worden in der Notruf-Universität
Karlsruhe.
Ein Projekt, das Mitte des vorigen Jahrzehnts lief hier in Karlsruhe.
Und wir waren damit deutlich eine Zeit voraus, denn erst vor etwa
eineinhalb Jahren war es so, dass die Studenten in meiner Vorlesung
wirklich sagten, ach toll, das nutzen wir.
Weil auf einmal die Smartphones alles verbreitet waren und jeder
Zugriff hatte auf das Netz.
Davor war das immer nur eine eingeschränkte Gruppe von Personen, die
tatsächlich diese Sachen genutzt hat.
So, was kann man damit machen?
Wir haben eine Web-Applikation dafür.
Diese Update für Smartphones ist bereits letztes Jahr verfügbar
gewesen.
Hier sind die Werkzeuge, wenn Sie sich das herunterladen wollen.
Wenn Sie sich die Web-Applikation anschauen wollen, müssen Sie einfach
auf diese URL gehen, die hier angegeben ist.
Oder das QR-Code hier kurz übernehmen in Ihrem Smartphone.
Und dann sehen Sie in der Web-Applikation, dass Sie eine Vorlesung
auswählen können.
Ich klicke jetzt Test.
Da finden Sie eine lange Latte von Vorlesungen mittlerweile, das sich
sehr verbreitet.
Und dann wählen Sie effiziente Algorithmen aus.
Wenn Sie das ausgewählt haben, müssen Sie ein Passwort angeben.
Das Passwort ist, wenn ich mich richtig erinnere...
Ich weiß nicht, ob ich das zu klein geschrieben habe.
Ich meine, das ist F-ALT.
Vielleicht auch mit Großbuchstaben I, Großbuchstaben A.
Das müssen Sie ausprobieren.
Und dann können Sie sich hier praktisch verbinden mit der vorhandenen
Vorlesung.
Und dann können Sie eine Frage stellen.
Sie müssen dazu irgendeinen Namen eintippen, eine beliebige.
Sie können eine Frage eintippen, Sie können die stellen.
Dann wird hier dieses Ausrufezeichen direkt unten gelb.
Dann sehe ich, da ist eine Frage, ich kann darauf eingehen.
Natürlich können Sie in diesem Raum beliebig Fragen stellen.
Sie können einfach Ihre Hand heben und Fragen stellen.
Sie können auch so eine Frage stellen.
Also die Interaktion ist immer möglich.
Wenn Sie das gerne lieber dazu machen wollen, dürfen Sie es auch
machen.
Ist eigentlich in größeren Vorlesungen wichtiger, diese Art.
Dann ist es so, dass Sie sagen können, ob die Vorlesung schneller sein
soll oder langsamer oder so in Ordnung ist.
Und Sie können auch Fragen beantworten, wenn ich Ihnen Fragen stelle.
Das kann ich also nutzen, sofern einige von Ihnen das tatsächlich
machen.
Ich kann die hier auch so fragen, wir können hier auch direkt
interagieren.
Aber ich kann Ihnen so Fragen stellen, dann sieht man sofort, wie das
Abstimmungsverhalten ist.
Und ich kann auch unabhängig von der Zeit der Vorlesung, können wir
die Zeit vereinbaren, zu der ich Fragen stelle.
Zu der also dieses Tool Fragen stellt.
Und dann können Sie darauf antworten.
Das haben wir im letzten Semester der Grundlageninformatik 2 intensiv
genutzt.
Und dort so Umfragen gemacht oder praktisch Testfragen gestellt zur
Vorbereitung auf die Klausur.
Und das war eigentlich ganz erfolgreich.
Das war jetzt hier die Web-Anwendung.
Übrigens gibt es auch natürlich die App.
Bei dem App haben Sie genau die gleichen Funktionen.
Und hier halt in diesem Format.
Lookit-App können Sie sich herunterladen aus dem Web-Store.
Und können dann, wie gesagt, Sie hier einloggen.
Können Ihre Frage hier in einem etwas schöteren Format in die Frage
eintippen.
Können sagen, wie gesagt, ob schneller, langsamer oder was immer.
Und können auch Fragen beantworten.
Und sehen dann auch das Ergebnis dieser ganzen Antwort.
Also wer das nutzen will, nutzen Sie es.
Hat jemand... also vielleicht machen wir das nächstes Mal, dass wir
dann nochmal nachsagen.
Ich werde es jedenfalls immer zu Beginn starten.
Und wer das dann nutzt, kann das gerne machen und kann das hier in der
Folie so noch mit einrichten.
Gut.
Zu den Übungen.
Übungen sind wichtig.
Werden organisiert, in diesem Fall, von Herrn Schubler und Herrn
Vogel.
Beide sitzen da hinten.
Kurz mal Handheben und so.
Also Herr Schubler und Herr Vogel, die werden das beide organisieren.
Dann haben wir noch eine Doktorin.
Das ist Frau Doll.
Die wird also auch mitwirken.
Und die beiden haben also auch Sprechstunden.
Sitzen drüben im Allianzgebäude.
Sind auch per E-Mail erreichbar.
Die Übungen laufen wie üblich.
14-Tägig ist eine einstündige Übung.
Zweistündig ist die Übungsrunde.
Sie müssen sich natürlich irgendwann anmelden.
Sie können in den Übungen die Gelegenheit nutzen, den Stoff
selbstständig zu bearbeiten.
Man lernt vor allen Dingen durch aktive Beschäftigung mit dem Stoff.
Das wissen Sie alle.
Aufgaben bearbeiten ist etwas ganz Wichtiges.
Es ist so, dass jemand, der mal im Ausland war, der weiß, da spielen
die Übungen eine viel größere Rolle.
Da wird viel intensiver erwartet, dass Sie sich aktiv beteiligen.
Während der Vorlesungszeit an dem Stoff mitwirken oder sich
beschäftigen mit dem Inhalt.
Sie bekommen dort direkt jeweils Rückmeldungen für die Bearbeitung der
Aufgaben.
Das machen wir hier auch.
Also die Übungsblätter werden korrigiert.
Sie bekommen dafür dann eine Rückmeldung.
Sie können 20 Punkte erreichen pro Übungsblatt.
Und wenn Sie am Ende erfolgreich waren, d.h.
wenn Sie mindestens 60 Punkte erreicht haben und mindestens 4
Übungsblätter, also keine leeren Aufgabenblätter abgegeben haben,
sondern irgendwas drauf steht, dann bekommen Sie einen Bonus von einer
Notenstufe.
D.h.
Sie bekommen einen mehrfachen Bonus, wenn Sie erfolgreich waren.
Erstmal haben Sie einen Bonus dadurch, dass Sie sich erfolgreich mit
dem Stoff beschäftigt haben.
Das ist der wesentliche Bonus für die Klausur.
Und dann gibt es eben noch obendrauf einen kleinen Anreiz, dass Sie
dann auch noch eine Verbesserung kriegen bei einer bestandenen
Klausur.
Sie müssen erst mal mindestens 4 haben.
Und dann kriegen Sie noch den Bonus obendrauf.
Und ja, wie sehen die Übungen aus?
Sie werden übliche Übungen bekommen, die mit Papier und Bleistift
erledigt werden können.
Und dann vermutlich auch eine Programmieraufgabe, damit Sie bei der
Fulde des effizienten Algorithmen sich auch mal mit effizienten
Programmen beschäftigen.
Ich glaube, das war so ziemlich alles.
Nicht alles.
Sie müssen die Übungsblätter in Zweiergruppen bearbeiten.
Das ist das, was wir uns wünschen.
Wichtig, dass man kooperiert, dass man lernt, in Gruppen zu arbeiten.
Und zwar nicht so, dass der eine was macht und der andere schreibt ab,
sondern dass man wirklich gemeinsam etwas bearbeitet.
Sie werden abgegeben an dem Abgabetag in der Vorlesung, zu Beginn der
Vorlesung.
Dann, was steht hier noch, das erste Übungsblatt am 23.04., nächste
Woche Dienstag.
Erste Übung, dann, wenn die Aufgaben abgegeben und formuliert werden.
Da wird die erste Übung sein.
Es ist noch ein bisschen Zeit mit den Übungsstunden.
Und etwas wollte ich noch sagen.
Es gibt, wie steht der 23.04., der 23.04., der nächste Dienstag, da
muss ich nach München.
Und da muss ich mittags da sein.
Das heißt, ich kann, wenn ich um 9.45 bis 11.15 Uhr die Vorlesung
mache, dann schaffe ich das nicht.
Deswegen würde ich gerne am 23.04.
die Vorlesung machen von 8 bis 9.30 Uhr.
Ja, ich hoffe, dass das für Sie möglich ist.
Ich muss natürlich auch früher aufstehen.
Ich werde Ihnen dann anbieten, nicht in diesem Raum, sondern im 214,
war das, glaube ich.
Also, Raum 214.
Ich habe noch einen weiteren Tag dafür aufgeguckt, wo wir das machen.
Das war im Juni irgendwann.
Vierte, Sechste auch.
Vierte, Sechste ebenfalls.
8 bis 9.30 Uhr.
Raum 214.
Ich denke, das ist besser, als wenn ich die Vorlesung aufbrechen
lasse.
Es ist vielleicht nicht besser, als wenn ich Herrn Schukler gebeten
hätte, die Vorlesung zu halten.
Aber ich bin ja der Dozent, deswegen halte ich die Vorlesung.
Vielleicht muss ich trotzdem bei Herrn Schukler noch mit, das wird
sich zeigen.
Aber in den beiden Tagen muss ich dann im Laufe des Tages weg.
Dann denke ich, geht das auf die Art und Weise, ohne eine wirkliche
Beeinträchtigung der Qualität der Vorlesung.
Außerdem zeichne ich ja auf.
Und diejenigen, denen das zu früh ist, können sich das später
angucken.
So, ich denke, ich habe hierzu die wesentlichen Sachen erzählt.
Und wenn Sie noch Fragen haben, können Sie sie sich stellen im Forum
oder wo auch immer.
Können nichts fragen, können die Mitarbeiter fragen.
Und wenn auch jetzt, hat einer von Ihnen eine Frage.
Ja?
Wir haben keinen geschützten Arbeitsbereich.
Wir haben den normalen Arbeitsbereich.
Das ist ja mit dem Standard Studierendenportal.
Also das Studierendenportal des KIT mit den VABs.
Und die sind dann nicht geschützt.
Anders als bei Iliad, wo man den Vorsitzungsbereich immer schützt und
dort ein Passwort braucht.
Das ist bei dem Studierendenportal etwas vorsichtiger.
Gut.
Dann Zielgruppen.
Sind verschiedenste Studierende, Wirtschaftsingenieure,
Informationswirte, Wirtschaftsmathematiker.
Wer immer da ein Interesse hat, darf hier keines zur Vorlesung kommen.
Fragen wir doch mal, wer alles hier ist.
Wer ist von den Wirtschaftsingenieuren?
Sehr viele.
Fast alle.
Wer ist Informationswirt?
Sie.
Aha.
Gut.
Sehr schön.
Wirtschaftsmathematiker.
Wer hat jetzt noch nicht seine Hand gehoben?
Okay.
Gut.
Damit haben wir also ein sehr einheitliches Spektrum von Teilnehmern.
Aha.
Einer sagt schon, die Geschwindigkeit ist in Ordnung.
Da unten sieht man das Feedback.
Inhaltsübersicht.
Worum wird es gehen in dieser Vorlesung?
Ich werde Ihnen etwas erzählen über effiziente Algorithmen.
Diese Vorlesung ist nicht eine klassische Vorlesung über effiziente
Algorithmen.
Hier schon.
Ich mache das immer so.
Aber ich erzähle einiges über Probleme, die man als Informatiker sich
angucken muss, die häufig bearbeitet werden müssen.
Und erzähle darüber, wie man unterschiedlichste Rechnerstrukturen
nutzen kann, um sie effizient zu lösen.
Das heißt, wir sehen hier erstmal nur die Probleme, nämlich nach einer
Einleitung und Berechnungsmodellen, auf deren Basis wir Aufwand
abschätzen können und sie effizient unterhalten können, mache ich
etwas über algebraische Probleme.
Matrixmodifikation, Ausweitung von Polynomen, schnelle
Projekttransformation.
Das ist etwas, das taucht in ganz vielen Berechnungen auf.
Also algebraische Operationen, Matrixen modifizieren, Lineare
Gleichungssysteme lösen wir, ähnliche Dinge.
Eine der Standardoperationen, die man einfach angucken muss, auch
Ausweitung von Polynomen, also Funktionsapproximation, da haben Sie
Polynome drin, da müssen Sie solche Dinge auch wissen, wie man das
eigentlich schnell machen kann.
Auch schnelle Projekttransformation ist eine ganz wichtige
Standardtechnik.
Wobei das eben nicht Technik ist, schnelle Projekttransformation, das
andere sind Probleme.
Projekttransformation ist auch ein Problem.
Rekurrenzgleichungen, das ist so ein Einschub über gewisse Arten, wie
man Kostenabschätzungen sehr systematisch machen kann.
Dann Sortier- und Suchprobleme, Graphprobleme, geometrische Probleme.
Das sind also unterschiedliche Problemtypen, die Sie auch in anderen
Provisionen kennenlernen.
Und bei all diesen Problemen stelle ich Ihnen vor, etwas, was man
machen kann, auf ganz normalen, ideellen Rechnern, auf
Parallelrechnern, in Hardware, oder auch eben am Ende macht man noch
verteilte Algorithmen.
Beziehungsweise da stelle ich Ihnen einige typische Probleme bei
verteilten Algorithmen vor, insofern das in der Zeit alles so
hinkommt.
Wir sehen, hier sind ein paar Zahlen dahinter, das soll so in etwa den
Umfang andeuten, den ich dafür vorgesehen habe.
Termine müssten maximal 13 sein.
Habe ich jetzt gar nicht nachgezählt, das stimmt aber, glaube ich.
Das ist eine gute Standardannahme.
Und ja, das ist also eine Inhaltsübersicht.
Und wie gesagt, das Wesentliche ist, dass ich nicht nur auf die
klassischen effizienten Algorithmen, auf einfaches Rechnen auf
normalen Rechnern eingehe, sondern auch auf die ganzen
Parallelverarbeitungsverfahren, Parallelalgorithmen.
Literatur gibt es massenhaft.
Das ist ein klassisches Gebiet der Informatik.
Also gibt es ganz viel Literatur darüber, von unterschiedlichsten
Leuten.
Hier von Selim Akil.
Der hat etwas geschrieben über Design Analysis of Parallel Algorithms.
Also da geht es speziell um die Parallelen.
Borodin Munro, von dem habe ich übernommen diese Reihenfolge der
Probleme.
Computational Complexity of Algebraic and Numeric Problems.
Da hat eine sehr schöne Vorlesung, lange Zeit mal gehalten, als ich im
Ausland war.
Und so ein paar Dinge übernimmt man halt von seinen akademischen
Lehrern.
Sedgwick Klasse hat eine Reihe, eine Vielfalt von Büchern geschrieben
über Algorithmen, sehr schön zu lesen, einfach dargestellt.
Es gibt zig verschiedene Varianten, bezogen auf verschiedene
Programmiersprachen oder auch allgemeiner.
Dann ein Klassiker, Donald Knuth, The Art of Computer Programming.
Die Kunst etwas zu programmieren.
Und Donald Knuth hat ein umfassendes Werk geschrieben, das ist ein
sechstwendiges Werk, über so die klassischen Verfahren in der
Informatik.
Wirklich, das ist ein Klassiker, ganz dicke Bücher kann man sich
anschauen und viel draus lernen.
Wirklich, das ist ganz, Sie finden kaum ein anderes Buch, was so
umfassend diese einzelnen Probleme darstellt und wie man sie
bearbeiten kann.
Dann gibt es den Kurt Mehlhorn, Datenstrukturen und Effiziente
Algorithmen, ein Klassiker.
Ottmann Wittmeier.
Ottmann war früher mal hier auch im ASB, Wittmeier auch.
Und die haben auch einen Klassiker über Algorithmen und
Datenstrukturen geschrieben.
Dann ein internationaler Klassiker, Cormen Leiserson-Rivest,
Introduction to Algorithms, ist Standardliteratur für ganz viele
Vorlesungen und Effiziente Algorithmen.
Und dann hier Lang, Hans-Weiner Lang, Algorithmen in Java.
Das ist ein Schüler von mir, der hat sehr viele schöne Algorithmen
entworfen, macht das alles so aus Java.
David Harrell, Algorithmics, ist ein sehr nettes Buch.
Warum ist das nett?
Weil man das einfach nett liest.
Der schreibt das einfach interessant und legt Wert auf die
wesentlichen Ideen, die die Leute hatten, um bestimmte Probleme
sinnvoll zu lösen.
Deswegen liest man das gern.
Das ist einfach nett dargestellt.
Andere schreiben kockend die Algorithmen auf und der schreibt etwas
über die Ideen dahinter.
Und dann gibt es, wie gesagt, viele weitere.
Hier noch eine ganze Reihe von parallelen Algorithmen.
Hier unten der S.Y.
Kung und Leighton, das sind so Klassiker in Bezug auf die
Hardwareimplementierung, hochparallele Implementierung von
Algorithmen.
Der Tom Leighton ist theoretischer Informatiker, hat sehr viel gemacht
mit effizienten Algorithmen.
Und er ist Professor am MIT und hat mit seinen Verfahren irgendwann
sich nette Sachen ausgedacht, mit denen man das Web verbessern kann.
Er hat diese Firma Akamai gegründet.
Er ist inzwischen mehrfacher Milliardär, weil er so effiziente
Verfahren entwickelt hat, mit denen man den Zugang zu Webseiten
deutlich besser organisieren kann.
Die meisten großen Firmen auf der Welt nutzen seine Dienste und Daten
über ihre Webseiten.
Nur, dass Sie mal sehen, theoretische Informatiker können
wirtschaftlich sehr erfolgreich sein, wenn sie ihre klugen Ideen
wirtschaftlich umsetzen.
Und manchmal meinen Leute, das sind theoretische Informatiker, das
sind alles irgendwelche abgehobene Leute, die keine Ahnung von der
Praxis haben.
Das ist keine Sicherheit.
Ich habe auch mal ein Buch geschrieben über Hardwareimplementierung
von Algorithmen.
Wir können noch viele weitere hier aufführen.
Hier unten, also Ingo Wegener hat auch schöne Bücher geschrieben über
effiziente Algorithmen für grundlegende Funktionen.
Ewa Zehntner hat ein dickes Buch geschrieben über ein Thema, das wir
hier in ein, zwei Doppelstunden behandeln werden.
Da geht es um die systematische Erzeugung von Algorithmen aus
mathematischen Problembeschreibungen.
Sie schreiben ein Problem mathematisch auf, in einer Folge von
Gleichungen, und daraus können Sie systematisch Programme ableiten.
Unterschiedlichste Arten, wie Sie ein Programm tatsächlich erstellen.
Insbesondere können Sie parallele Programme daraus ableiten.
Und man kann es also so auffassen als eine Vorlage, um dann
tatsächlich etwas zu programmieren.
Sie können daraus auch direkt Decode erzeugen und können dann auch in
der mathematischen Beschreibung eines Problems effiziente parallele
Versionen von Algorithmen erzeugen.
Das werden Sie auch sehen in einem kleinen Beispiel, wie man das im
Prinzip macht.
Das Buch geht deutlich darüber hinaus.
Es ist eine sehr umfassende Theorie.
Der Art, wie man solche systemischen Systeme entwickelt.
Und das ist sehr trocken geschrieben.
Es ist nicht schön zu lesen, sage ich ganz einfach, aber es ist sehr
umfangreich, also sehr ausführlich.
Da sind die wesentlichen Dinge alle drin.
Deshalb manchmal so ein bisschen trocken, was man da in der Theorie
macht.
So, wenn Sie weiteres Interesse an Literatur haben, Sie finden
massenhaft Literatur zu effizienten Algorithmen.
Ich habe das nicht mehr abgedatet, weil das einfach zu viel ist.
Suchen Sie einfach im Web nach effizienten Algorithmen, Sie finden
massenhaft Literatur.
Das war schon das Organisatorische.
Haben Sie dazu noch irgendwelche wesentlichen Fragen?
Zu den organisatorischen Dingen, grundlegenden Dingen?
Wenn Ihnen gleich noch etwas einfällt, dürfen Sie das gerne gleich
sagen.
Ach, der Erste möchte gerne, dass ich schneller vorgehe.
Das passiert auch sofort.
Das geht sofort los.
So, jetzt...
Einführung.
Ich möchte Ihnen ein bisschen was erzählen, worum es eigentlich geht.
Ich habe so ein kleines Zitat aus dem Vorlesungskommentar, wo nochmal
steht, worum es eigentlich geht in dieser Vorlesung, auf Deutsch und
auf Englisch.
Also, es ist eine Kernaufgabe der Informatik und natürlich auch der
Wirtschaftsingenieure.
Effizienz ist etwas, worum Wirtschaftsingenieure sich immer kümmern.
Ich kann nicht meine Ressourcen bestmöglich einsetzen, genau darum
geht es.
Und die Ressourcen können halt sehr unterschiedlich sein.
Und es geht eben um die systematischen Ansätze für die Analyse, die
effiziente Gestaltung von Algorithmen und Beispiel von
Standardaufgaben, Informationsverarbeitung.
Insbesondere der Einfluss von Datenstrukturen und Rechnerarchitekturen
wird hier angeschaut.
Und jetzt schauen wir uns mal an, worum geht es eigentlich.
Was sind eigentlich die wesentlichen Probleme, die wir uns
normalerweise anschauen?
Informationsverarbeitung wird eingesetzt für verschiedenste Zwecke.
Technisch-wissenschaftliche Berechnungen, Simulation, Visualisierung,
Optimierung, Steuerung.
Ganz viele Aufgaben, die wahrgenommen werden müssen.
Sie müssen halt große technische Systeme simulieren, bevor Sie die
tatsächlich bauen.
Verkehrssimulationen sind wichtig, Simulationen des Energiesystems.
Sie müssen das, was Sie simulieren, visualisieren.
Möglichst dreidimensional, wenn es sinnvoll ist.
Oder Sie müssen etwas optimieren.
Technische Systeme steuern.
Und dann gibt es die ganzen kommerziellen wissenschaftlichen
Anwendungen, wo man Daten hin- und herschiebt, Daten verwaltet.
Gehaltsabrechnungen macht und ähnliche Dinge.
Information sucht.
Data Mining, Data Analytics ist heutzutage eine ganz wichtige Aufgabe.
Und alle möglichen Statistikberechnungen, Wissensextraktion,
Visualisierung.
Zig verschiedene Aufgaben, die vor allen Dingen Aufgaben sind, häufig
auf sehr großen Datenmengen.
Oder eben mit einem großen Berechnungsaufwand.
Und deswegen ist es wichtig, das möglichst effizient hinzuziehen.
Dann haben wir Kommunikation natürlich.
Wir kommunizieren sehr viel.
Wir müssen das sinnvoll organisieren können.
Wir brauchen geeignete Ein- und Ausgabe-Schnittstellen.
Ich muss Dinge aufbereiten.
Das hatte ich ja vorhin schon Visualisierung genannt.
Also grafische Datenverarbeitung ist natürlich auch ganz wichtig.
Dass ich Dinge vernünftig darstelle auf dem Rechner.
Und das werden wir später noch bekommen.
Dass das ein Problem sein kann.
Wenn wir irgendwelche Objekte auf dem Bildschirm darstellen, die
überlassen sich.
Wie macht man das eigentlich?
Wie erkennt man, dass sich verschiedene Objekte überlassen, wenn ich
hin und her bewege?
Muss das richtig dargestellt werden?
Das ist gar nicht so einfach.
Das muss man richtig hinbekommen.
Bei Kommunikation muss man sich immer auch mit Sicherheit
beschäftigen.
Wir müssen sicher kommunizieren können.
Wenn Sie verteilt Unternehmen haben und dort wesentliche
Geschäftsabläufe übers Netz laufen, dann muss das, was dort an
Informationen aufgetauscht wird, sicher sein.
Das heißt, vertraulich bleiben.
Nicht zugreifbar sein durch andere.
Wir müssen erreichen, dass keine Leute über nicht gewollte
Kommunikation in irgendeiner Form etwas beeinflussen können auf ihren
Rechnern.
Also ganze Angriffsszenarien.
Auch alles ganz wichtige Algorithmen.
Also da braucht man überall natürlich auch gesellschaftliche
Verfahren.
Und dann gibt es halt alle möglichen Operationen, die bei diesen
Aufgaben bearbeitet werden müssen.
Also es gibt viele Elementmethoden.
Was sind das?
Wer von Ihnen weiß, was die Elementmethoden sind?
Fragt das jemand?
Fragt keiner.
Also stellen Sie vor, wir wollen eine Tragfläche bauen.
Und jetzt überlegen Sie sich, wie kann ich die gestalten?
Wie ist eigentlich die Oberfläche zu gestalten?
Welche Auswirkungen hat die Bewegung hier?
Also eine Tragfläche.
Welche Auswirkungen hat die auf die Luftströmungen?
Dazu müssen Sie das modellieren.
Und dann macht man das so, dass man hier Gitterpunkte einbaut.
Vorsicht, die Oberfläche wird trianguliert.
Und dann wird das Verhalten dieser Oberfläche, oder die Eigenschaften
der Oberfläche, jeweils an den Punkten simuliert.
In Bezug auf die Punkte in der Nachbarschaft.
Das sind die finiten Elemente.
Sie haben zu jedem Punkt eine endliche Anzahl von Nachbarn.
Und Sie gucken sich das an.
Die Eigenschaften der Nachbarn können daraus die Eigenschaften des
Punktes, den Sie gerade betrachten wollen, die ableiten.
Das sind finite Elemente.
Üblicherweise werden dort Berechnungen gemacht mit sehr großen
Bandmatrizen.
Also eine Anzahl von Bandmatrixen, die wir hier im Band haben.
Das sind Elemente unweit null.
Konstante Anzahl von Diagonalen, der Rest ist null.
Das ist der typische Argus der Datenstruktur, wenn Sie finite Elemente
-Methoden haben.
Ganz wichtig, um bei der Entwicklung von technischen Bauteilen die
Eigenschaften der Bauteile sinnvoll im Rechner simulieren zu können.
Das sind also finite Element-Methoden.
Klassischer Ansatz aus der Mathematik oder auch aus anderen Bereichen.
Modifikation von Matrizen und Vektoren, das hatte ich schon erwähnt.
Sie haben eine Frage?
Ja, natürlich.
Ja, es heißt endlich.
Aber gemeint ist eigentlich auch, dass ich jeweils eine begrenzte Zahl
von Nachbarn habe.
Dann, Approximation von Funktionen.
Auch das ist Ihnen vielleicht bekannt, dass man Funktionen, wenn Sie
irgendeine Funktion berechnen wollen...
So, die sieht jetzt sehr kompliziert aus.
Wenn Sie etwas haben, was so aussieht oder etwas, was so aussieht,
dann ist es schon einfacher.
Noch einfacher ist so eine Funktion.
Sie können die also darstellen durch irgendwelche Gleichungen, durch
Polynome unterschiedlichen Gerades.
Und können dadurch so eine Funktion stiftweise darstellen und
approximieren.
Weil Sie nicht den genauen Verlauf tatsächlich brauchen.
Insbesondere, wenn Sie integral berechnen wollen, wollen Sie häufig
approximieren oder müssen Sie approximieren.
Das macht man mit Polynomen, deswegen braucht man solche Operationen.
Dann müssen Sie, also typische Operationen, gerade wenn Sie große
Datenmengen haben, Sie müssen auf Daten zugreifen können, Sie müssen
darauf schreiben können.
Auch in einer sinnvollen Art und Weise.
Das Thema Big Data ist im Augenblick ein ganz großes Thema oder wird
zu einem der großen Themen im Augenblick in der Informatik.
Riesend Datenmengen, also irgendwelche Terabytes, Petabytes von Daten,
auf denen Sie operieren wollen.
Standardaufgabe für Firmen wie Google oder alle möglichen
Suchmaschinen, die auf riesen Datenmengen irgendwelche Informationen
extrahieren wollen.
Suchanfragen beantworten auf einem Index, der mehrere Milliarden
Elemente enthält.
Also wichtige Operationen suchen, sortieren.
Kennen Sie alles im Prinzip aus der Anfängervorlesung.
Dann Wegesuche in Graphen, Darstellung von Graphen.
Sie kennen die üblichen Verfahren von Dijkstra, Kürze für Wege zu
berechnen in Graphen.
Und das wird in unterschiedlichsten Anwendungen gebraucht.
Und man kann das mit Dijkstra machen, man kann es auch besser machen.
Hier die Arbeitsgruppen von Frau Wagner und Herrn Wanders hier am KIT.
Die haben für Riesengraphen, also wenn es geht um Wegesuche hier im
Straßennetz oder Bahnnetz, da haben die das um mehrere Größenordnungen
wirklich verringert.
Und den Zeitaufwand einfach dadurch, dass die Graphen geeignet
manipulieren, um den Aufwand für die kürzeste Wegesuche deutlich
reduzieren zu können.
Interessantes Problem.
Oder Operationen auf geometrischen Objekten.
Es gibt viele verschiedene interessante Probleme.
Die wollen wir uns später anschauen.
Da haben wir noch eine Punktmenge.
Sie wollen vielleicht hier die konvexe Hülle berechnen.
Konvexe Hülle darum, also der konvexe Bereich auf und um.
Klassisches Problem.
Oder Sie wollen, Sie haben irgendeine, irgendein Gebilde, irgendeine
sehr futuristische Galerie.
Und Sie wollen jetzt sehen, wie viele Wachposten muss ich jetzt unter
Kameras installieren, damit ich jeden Punkt meines Innenraumes
überwachen kann.
Ja, also, wenn Sie hier in die Ecke jemanden stellen, der kann den
Bereich hier irgendwie abdecken.
Da kann er noch dahinten irgendwo hin.
Da kann er umgehen.
Da brauchen Sie hier noch irgendjemanden.
Da vielleicht auch.
Oder da.
Oder wie viele brauchen Sie da eigentlich?
Sie können hier sogie komplexe, solche Galerien, das nennt man Galerie
-Probleme, dass man sich anguckt, was ist die minimale Anzahl von
Wachposten oder von Kameras, um einen Raum vollständig zu überwachen.
Ja, das ist ein praktisches Problem, ein geometrisches Problem.
Oder Sie haben irgendeine Menge von irgendwelchen Geraden, und Sie
wollen feststellen, wo sind eigentlich die Schnittpunkte.
Ja, kann man das effizient machen?
Das sind klassische Algorithmen, mit denen man das effizient macht.
Solche Probleme tauchen auf.
Und jetzt muss man sich angucken, was ist eigentlich die Anforderung,
die wir haben.
Die Anforderung ist natürlich, dass wir möglichst schnell die
Ergebnisse haben wollen, möglichst geringer Zeitbedarf pro Aufgabe.
Manchmal ist uns aber der Zeitbedarf pro Aufgabe gar nicht so wichtig.
Also der Bedarf pro Aufgabe wäre die Dauer für die...
Das sollte gerade sein.
Ups.
Das ist also hier irgendeine Dauer für die Aufführung einer Aufgabe.
Das würde ich dann gut klein haben.
Es kann aber auch sein, dass mich viel mehr interessiert, dass ich in
der Lage bin, eine Berechnung zu machen, dann die nächste, dann die
nächste, dann die nächste, dann die nächste.
Also möglichst hohe Anzahl von Berechnungen gleichzeitig,
beziehungsweise die Frequenz, mit der ich Probleme, Probleminstanzen
bearbeiten kann, möglichst hoch zu haben.
Also möglichst viele Probleme pro Sekunde oder einen hohen Durchsatz
zu erzielen.
Da kann es natürlich etwas länger dauern, bis ich das einzelne Problem
bearbeitet habe.
Hauptsache, der Durchsatz stimmt.
Zum Beispiel bei irgendwelchen Bildsignalverarbeitungsverfahren.
Die Bildwiederholfrequenz, die müssen Sie einhalten.
Es darf aber ruhig ein bisschen länger dauern, bis Sie tatsächlich die
einzelnen Aufgaben erfüllt haben.
Solche Effekte sehen Sie manchmal bei Übertragungen von
Fußballspielen, wenn Sie ein Tor sehen und der Nachbar, der bei
irgendeinem anderen Anbieter gewesen ist, bei dem sind die Daten über
längere Wege gelaufen, da ist das Empfangen und Verarbeiten der Daten
ein etwas längerer Prozess gewesen, der hat dann erst ein paar
Sekunden später das Tor gesehen.
Sie sehen aber trotzdem, dass völlig kontinuierlich der Durchsatz
stimmt, aber der Versatz ist halt etwas größer.
Okay.
Dann möglichst wenig Speicherplatz.
Speicher gibt es zwar sehr viel, trotzdem versucht man immer, das ein
bisschen wenig zu machen.
Wenige Berechnungseinheiten.
Als die noch sehr teuer waren, war das wichtig, aber natürlich will
ich auch möglichst effizient machen.
Je mehr ich einsetze, je mehr kann ich parallelisieren, desto kürzer
wird die Ausführungszeit, aber ich muss sagen, mehrere Prozessoren
einsetzen.
Wir hatten für lange Zeit immer nur einen Prozessor im Rechner.
Heutzutage haben Sie im Rechner, ich habe hier ein 5 oder 6, weiß gar
nicht genau wie viel, einige Prozessoren sind zu den eingekommen.
Sie haben in Ihrem Smartphone 2 oder 4, es gibt heute viele
Prozessorchips, da haben Sie 8 oder 16 oder auch 64 Prozessoren drauf.
Und es wird nicht lange dauern, da haben Sie auch zum typischen
Prozessorboard haben Sie so Größenordnung 100 Prozessoren drauf.
Das heißt, da haben wir auf einmal ein Überangebot an Prozessoren für
die richtigen Aufgaben.
Das ist interessant, wie kann man die Aufgaben eigentlich verteilen,
nur dass die sinnvoll eingesetzt werden.
Hier habe ich noch stehen, wenige Berechnungseinheiten.
Also man muss natürlich sehen, wie die Kosten eigentlich sind.
Wie vorher jetzt die Ausführung einer Operation ist.
Natürlich heißt auch Einsatz von mehreren Prozessoren eventuell, dass
ich höheren Energieaufwand habe.
Wenn ich Energieaufwand reduzieren möchte, das steht hier gar nicht.
Energieaufwand wenig, wollte ich dazu schreiben.
Interessantes Thema, wenig Energie.
Wenn Sie mehr Prozessoren einsetzen, brauchen Sie mehr Energie.
Wenn Sie kürzer arbeiten, geht es hier ein bisschen runter.
Sie müssen aber kommunizieren.
Kommunikation braucht auch Energie.
Wie kann ich erreichen, dass mein Energieaufwand für die Ausführung
von Berechnungen reduziert wird?
Wir steuern heute schöne Prozesse, sodass die Prozesse
energieeffizient ablaufen.
Wenn ich aber dafür viel Aufwand habe für die
Informationsverarbeitung, und dafür viel Energie brauche, muss ich
sehen, dass der Zusatzaufwand an Energieaufwand dafür geringer ist,
als das, was ich einsparen kann.
Also, viele interessante Kostenberechnungen.
Wenige Nachrichten bei verteilten Berechnungen.
Warum ist das so wichtig?
Wenn Sie verteilte Berechnungen machen, haben Sie eine Reihe
Prozessoren.
Und die schicken jetzt hier in irgendein Kommunikationssystem
irgendwelche Nachrichten rein und wollen da irgendwelche Nachrichten
wieder rausholen.
Und das Problem ist, wenn Sie sich anschauen, wie lange es dauert,
eine Nachricht zu verschicken, das ist im Bereich von Millisekunden.
Ihr Rechner arbeitet aber mit mehreren Gigahertz.
Das heißt, wir haben dort mehrere Größenordnungen dazwischen im
Zeitaufwand, um eine Nachricht zu verschicken, beziehungsweise
Operationen lokal auszuführen.
Deswegen wird bei verteilten Berechnungen häufig der Aufwand nur
gezählt in der Anzahl der Nachrichten.
Weil diese Rechnungen, auch die einzelnen Ressourcen, die da sind,
sind gering in Anzahl.
Nicht mit dem Aufwand.
Also Anzahl Nachrichten reduzieren ist wichtig.
Andererseits möchte ich gerne, dass etwas verteilt gerechnet wird.
Also auch so ein Trade-off zwischen Verteilung und Parallelisierung
und lokalem Rechnen.
Natürlich möchte ich weitgehend alle verfügbaren Ressourcen nutzen,
bestmöglich.
Und ich möchte auch meine Aufgaben zuverlässig ausführen.
Es kann ja sein, dass Kommunikation nicht erfolgreich ist.
Es kann sein, dass irgendwelche Prozessoren ausfallen.
Trotzdem soll das Ganze zuverlässig sein.
Da muss ich fehlertolerant arbeiten.
Also wenn ich Störungen tolerieren möchte, natürlich muss ich keine
Fehler in meinen Ergebnissen tolerieren.
Sondern nur Störungen in den Zwischenergebnissen.
Und da muss ich in der Lage sein, solche Störungen zu kompensieren.
Das Thema werde ich in dieser Folge so nicht ansprechen.
Also die ganze Fehler-Toleranz-Überlegung ist aber auch ein wichtiges
Thema.
Dann haben wir hier die Effizienzanalyse.
Insgesamt kann ich angucken, pro Aufgabe.
Sie wollen eine Folge von Zahlen sortieren.
Dann können Sie sich angucken, was kostet das Sortieren.
Die einzelnen Berechnungen.
Oder Sie sagen, ich möchte jetzt 100 Rollen sortieren.
Wie ist der Aufwand für diese 100 Rollen?
Das ist eine akkumulierte Aufwandschätzung für eine Gruppe von
Berechnungen.
Wenn Sie also Pipelineing-Verfahren haben, ist das durchaus wichtig,
sich sowas anzuschauen.
Und dann können Sie auch anschauen, wie Ihre einzelnen Ressourcen
genutzt werden.
Wie effizient werden die eigentlich ausgenutzt?
Sitzen die die meiste Zeit da und drehen Däumchen?
Haben nichts zu tun?
Oder sind die ständig aufgeladen?
Also das ist auch etwas, was uns damit ankommt.
Und dann wollen wir natürlich Probleme durch Algorithmen lösen.
Sie kennen alle Algorithmusbegriffe.
Lagerbekannt.
Das, was ich jetzt hier erzähle, ist sowieso Ihnen allen bekannt.
Aufgrund Lagerinformatik 1, auf Informatik 2, Algorithmenvorlesungen
usw.
Trotzdem muss ich das einmal zu Beginn nochmal wiederholen, damit wir
so ein bisschen eingestimmt sind darauf, was eigentlich hier passiert.
Also was ist ein Algorithmus?
Ein endlich beschriebenes deterministisches Verfahren mit Ein- und
Ausgabe, das ja alle zulässigen Eingaben kombiniert und dessen
Operationen effektiv sind.
Klassische Definition eines Algorithmus.
Und da stehen so einige Dinge, wobei hier etwas steht, das ist
deterministisch.
Da steht nur die Determiniertheit.
Determiniertheit heißt normalerweise, dass Sie bei jeder Ein-, wenn
Sie die gleiche Eingabe machen, kommt die gleiche Ausgabe raus.
Tatsächlich ist es so, dass diese Frage mit deterministisch und
Determiniertheit usw., also deterministisch heißt es normalerweise,
dass jeder Schritt genau vorherbestimmt ist und man immer die gleichen
Berechnungen ausführt, die immer die gleiche Folge von
Einzelberechnungen haben.
Wir betrachten aber heutzutage auch randomisierte Algorithmen.
Also randomisierte Algorithmen, das heißt, Sie müssen ab und zu mal
eine Münze werfen.
Das sind Zufallsentscheidungen.
Und auf einmal können Sie schwierige Probleme deutlich schneller
lösen.
Aber vielleicht nicht exakt.
Vielleicht jedes Mal mit einem anderen Ergebnis.
Oder mit unterschiedlich langen Laufzeiten.
Das heißt, je nachdem, wie gut das war, das Münzenwerfen, wie viel
Glück Sie gehabt haben, haben Sie eine lange Laufzeit oder eine kurze
Laufzeit.
Solche Dinge gibt es.
Randomisierung ist eine ganz wichtige Technik für effiziente
Algorithmen.
Und es gibt auch sowas wie revolutionäre Algorithmen.
Da haben Sie ganz viele Zufallsentscheidungen drin.
Das ist eine Systematik für randomisierte Suche.
Generell sind Arbeiten in sogenannten Meta-Häuserstücken
tüchtlicherweise mit Randomisierung.
Kennen Sie vielleicht aus dem OS-Research oder auch aus der Vorlesung
der Naturspiele-Indoktrinierungsverfahren von Herrn Zuckler und Frau
Mosberg.
Andere Formulierung ist, dass ein Algorithmus eine endliche
Beschreibung der Ausführung einer endlichen Folge von Befehlen auf
einer abstrakten Maschine ist.
Ich muss natürlich wissen, was macht eigentlich jeder Befehl.
Dazu brauche ich irgendeine...
Ich muss es irgendwie definieren können.
Ich brauche also eine Ausführungseinheit, auf der tatsächlich solch
ein Algorithmus ausgeführt werden kann.
Und erst wenn ich weiß, dass das alles vernünftig läuft, weiß ich,
welchen Aufwand ich an den Grundoperationen verursache.
Und dann kann ich etwas sagen darüber, wie lange ein konkretes
Verfahren braucht, dass eine endliche Anzahl von Befehlen für
irgendein Problem ausführt.
Dann habe ich Aussagen für das Zeitverhalten.
Wie viele sind das?
Weder noch.
Beziehungsweise es gibt Varianten von randomisierten Algorithmen, die
sind determiniert.
D.h.
sie geben Ihnen für jede Eingabe garantiert das richtige Ergebnis, das
korrekte Ergebnis.
Es gibt andere randomisierte Algorithmen, aber diese Algorithmen, die
immer das richtige Ergebnis liefern, können sehr unterschiedlich lange
dauern.
Die Aussage über die Laufzeit ist dann eine Aussage über eine
Zufallsvariante.
Also die Laufzeit der Zufallsvariante.
Sie kennen randomisiertes Quicksort.
Da haben Sie immer die richtige sortierte Folge am Ende, aber Sie
können über die Laufzeit nur etwas aussagen, als Sie haben einen
gewissen Erwartungswert für die Laufzeit.
Das kann unterschiedlich sein.
Und es gibt andere Verfahren, wie z.B.
Evolutionäre Algorithmen, die lassen Sie mehrfach laufen und Sie
bekommen jedes Mal eventuell ein anderes Ergebnis.
Weil Sie versuchen, eine gute Lösung für ein Problem zu finden.
Und diese Lösung kann sehr unterschiedlich aussehen.
Es kann sein, dass Sie bei jedem Lauf abhängig von der Art, wie Sie
Zufallsvariante erzeugen, wie die Entscheidungen da laufen, können Sie
unterschiedliche Ergebnisse erzielen.
Es gibt diese verschiedenen Fälle.
Und deterministisch sind Sie garantiert auf keinen Fall, weil Sie eben
Zufallsentscheidungen drin haben.
Es kann Schlucke geben, die deterministisch sind.
Aber durch die Zufallsentscheidungen haben Sie dann halt
unterschiedliche Folgen von Beziehungen.
Ok.
Das, was ich vor allen Dingen hier betrachte, ist die Beziehung.
In dieser Vorlesung geht es mir vor allen Dingen um die Beziehung
zwischen Programmstrukturen und Rechnerstrukturen.
Üblicherweise in Vorlesungen von effizienten Algorithmen wird sehr
viel erzählt über Programmstrukturen und Datenstrukturen.
Auch wichtig.
Aber darauf gehe ich nur am Rande ein.
Das Wesentliche sind mir die verschiedenen Rechnerstrukturen.
Jetzt schauen wir uns das mal an.
Verschiedene Strukturen, die es so gibt, gibt es auch
Programmstrukturen.
Sie können alle programmieren.
Sie wissen, es gibt Strukturen wie irgendwelche Folgen von
Anweisungen, Verzweigungen schleifen, Prozeduraufrufe und ähnliches.
Sie können verschiedenste Dinge dort machen.
Sie können kommunizieren, Sie können Methoden aufrufen.
Das ist so eine typische Programmstruktur.
Rechnerstruktur, wie ist die eigentlich gegeben?
Eigentlich sagt Ihnen der Befehlssatz, der auftreten kann in Ihren
Programmen, welche Struktur dahintersteckt.
Weil Sie ja in den Befehleneinheiten ansprechen können und
entsprechend wird dadurch eigentlich alles definiert.
Sie haben also Prozessorstrukturen, Verbindungsstrukturen.
Also es kann sein, dass Sie einen Rechner haben, die irgendwie mit
einem Baum verbunden sind.
Es kann sein, dass Sie Rechner haben, die mit einem Gitter verbunden
sind.
Ein zweidimensionales Gitter.
Es kann sein, dass Sie darin noch irgendwelche sogenannten Wraparound
-Verbindungen haben.
Wenn Sie das in beiden Ebenen haben, haben Sie Torus.
Und dann gibt es noch viele andere Dinge.
Das klinge ich nachher nochmal drauf ein.
Viele verschiedene Verbindungsstrukturen.
Und je nachdem, wie die verbunden sind, diese Rechner, haben Sie
unterschiedliche Möglichkeiten zu kommunizieren.
Und das heißt, das kann man natürlich ausnutzen, oder muss man
ausnutzen, diese Struktur für eine effiziente Programmierung.
Dann die verschiedenen Datenstrukturen.
Arrays, Records, Listen, Stacks, Warteschlangen, Bäume, Heaps.
Das kennen Sie alles aus den Anführungsvorschlägen.
Das nächste kennen Sie nicht.
Grid-Fi, Segment-Baum, Skip-Tree, Segment-Baum.
Das sind verschiedene Datenstrukturen für geometrische Objekte.
Grid-Fi ähnlich.
Und die anderen kennen Sie eigentlich alle aus den Grundvorlesungen.
Listen, Einfach-Verbunden, Doppel-Verbunden und ähnliches.
Stack, wo Sie eben nur etwas oben drauf geben.
Also Kellerstrukturen, wo Sie etwas oben drauf geben können und wieder
runterholen.
Also hier das ist der Stack, dass Sie da was drauflegen können oder
auch wieder runterholen.
Warteschlange, dass Sie halt da was reinlegen.
Dann haben Sie hier Ihre ganzen Elemente und die kommen dann
irgendwann wieder raus.
Und beim Heap-Halt eine Struktur, bei der Sie immer das Maximum oder
immer das Minimum einer Wurzelnstruktur liegen haben.
Sie kennen das aus Heapsort.
Oder auch aus anderen Verfahren im Bereich der Projekthuslösung.
Wo diese Projektlinge auch ganz stark eingesetzt werden natürlich.
Und dann gibt es diese verschiedensten Rechnerstrukturen.
Turing-Maschine.
Kennen Sie auch aus Grundlagen-Informatik 2 oder auch aus Turing
-Maschine -Informatik 3 in der Informationswörter.
Die heißen nicht mehr so, die heißen anders.
Ah, Sie wissen das gar nicht?
Von wo kommen Sie denn?
Aus der Türkei?
Gut.
Also Turing-Maschine, einfaches theoretisches Berechnungsmodell.
Ganz einfach.
Für Berechnungsüberlegungen wichtig.
Für uns aber nicht.
Random-Access-Machine ist eine typische Register-Maschine.
Ähnlich wie die Von-Neumann-Maschine.
Parallel-Random-Access-Machine ist auch ganz wichtig.
Parallele Varianten von Rechnern.
Hypercube.
Auch wichtig.
Baumrechner.
Ganz kurz.
Hypercube.
Was ist ein Hypercube?
Ein Hyperwürfel.
Wenn Sie einen Hyperwürfel bauen, also einen nulldimensionalen
Hyperwürfel, das ist ein Knoten.
Ein eindimensionaler Hyperwürfel, das sind zwei nulldimensionale
Hyperwürfel verbunden durch eine Kante.
Wenn Sie einen zweidimensionalen Hyperwürfel bauen, nehmen Sie sich
zwei eindimensionale Hyperwürfel und verbinden korrespondierende
Knoten mit jeweils einer Kante.
Wenn Sie einen dreidimensionalen Hyperwürfel bauen, nehmen Sie sich
zwei zweidimensionale Hyperwürfel und verbinden korrespondierende
Elemente mit einer Kante.
Wenn Sie einen vierdimensionalen Hyperwürfel bauen, dann nehmen Sie
entsprechend zwei dreidimensionale Hyperwürfel und verbinden
entsprechend korrespondierende Elemente jeweils mit einer Kante.
Und so weiter.
Dann sind fünfdimensional, sechsdimensional und so weiter.
Das heißt, Sie haben hier entsprechende Dimensionen, viele Nachbarn
und Sie haben dann entsprechend die Knoten auf diese Art und Weise
verbunden.
Interessante Struktur.
Wird sehr intensiv eingesetzt.
Torus habe ich Ihnen hier so angedeutet.
Mesh of Trees lernen Sie noch kennen.
Multi-Core, Many-Core.
Das gibt einfach nur an, dass Sie viele Prozessoreinheiten auf einem
Chip drauf haben, die auf unterschiedliche Art und Weise verbunden
sein können.
Und natürlich haben Sie auch einfach nur das Internet, verteilte
Rechner, also das Grid, Computation Grid, oder einfach, jetzt reden
wir von Cloud Computing, weil das moderner ist.
Das heißt, Sie nutzen irgendwo Rechnerstrukturen.
Vielleicht sind die irgendwie strukturiert.
Das wissen Sie eigentlich gar nicht.
Sie nutzen nur den Service.
Also, und es ist schon völlig klar, wenn wir jetzt davon reden, wir
wollen Algorithmen und wollen Probleme effizient lösen, dann muss ich
doch wissen, was sind eigentlich meine Möglichkeiten, meine Probleme
zu strukturieren.
Programmstrukturen.
Wie kann ich die Daten eigentlich darstellen?
Welche Auswirkungen hat das?
Welche Rechner stehen mir zur Verfügung?
Wie sind die eigentlich verbunden?
Wie wirkt sich das aus, wenn Rechner kommunizieren?
Und wenn ich dann eine Aussage darüber mache, ich habe ein bestimmtes
Problem ganz effizient gelöst, muss ich wissen, auf welcher Basis
denn?
Was ist denn die Rechnerstruktur, was ist die Infrastruktur, die ich
dafür einsetzen kann?
Und entsprechend ist das gar nicht so ein einfaches Problem zu sagen,
ich mache das effizient.
Ich habe nur draufgestellt.
Was sind denn die Annahmen?
Wieso ist das effizient?
Welche Ressourcen stehen zur Verfügung?
Und damit werden wir uns in der Vorlesung intensiver beschäftigen.
Also, es gibt viele verschiedene Entwurfsprinzipien.
Auch das kommt noch dazu.
Ich möchte natürlich möglichst systematisch meine Probleme lösen.
Sie kennen alle die beiden Fonker.
Ich habe das typische Problem, uns Informatikern sind die Probleme
immer zu groß.
Wir teilen die auf.
Irgendwie mehrfach.
Und lösen dann jeweils die Teilprobleme.
Und teilen das gleich auch nochmal irgendwie weiter auf.
Vielleicht irgendwie hier so.
Und dann werden die Dinger entsprechend entweder erstmal aufgeteilt,
in dieser Richtung.
Und anschließend müssen sie kombiniert werden zur Lösung für das
Aufgabenproblem.
Und ich kann die Teilprobleme unabhängig voneinander bearbeiten.
Dynamic Programming macht was anderes.
Da schauen sie sich an, ein großes Problem.
Teilen das in viele kleine Einzelprobleme auf.
Und dann lösen sie die ganzen Einzelprobleme.
Und können ein größeres Problem dadurch lösen, dass sie irgendwie
benachbarte Teilprobleme lösen.
Von benachbarten Teilproblemen sich anschauen.
Daraus die Lösung konstruieren für ein etwas größeres Problem.
Aber diese Dinge sind nicht unabhängig voneinander.
Die sind miteinander vergoben.
Und sie haben dann einen typischen Dynamic Programming Ansatz, der
auch grafisch effizient sein kann.
Sie kennen das aus Grundlagen Informatik 2.
Die Reduktion von Automaten liegt auf die Art und Weise, wenn Sie
feststellen wollten, welche Zustände äquivalent sind.
Das ist ein Dynamic Programming Ansatz.
Oder auch bei dieser Kogel-Yanga-Kazami-Ansatz, um festzustellen, ob
ein Wort ein Element einer kontextfreien Sprache ist.
Auch da hat man einen Dynamic Programming Ansatz gemacht.
Man hat immer kleine Lösungen, aus denen Deformationen über die Lösung
kleiner Probleme dann auf eine einfache oder systematische Art und
Weise die Lösung von größeren Problemen ableiten können.
Branch-and-Bound-Optimierungsverfahren oder Art der Optimierung, wo
man versucht, möglichst frühzeitig festzustellen, dass ein bestimmter
Verzweig der Durchsuchung des Lösungsraumes nicht vielversprechend
ist, sodass ich den abschneiden kann.
Und das ist also ein Verfahren, um exakt zu optimieren.
Greedy-Algorithmen, gierige Algorithmen, solche, bei denen ich
heuristisch immer das Bestmögliche mache.
Also wenn ich ein problemlösendes Handlungsreisen bin und immer zur
nächsten Stadt fahre, dann werde ich vielleicht irgendwann mal alle
Städte besucht haben, aber nicht unbedingt auf dem besten Weg.
Auf dem kürzesten Weg insgesamt.
Aber das ist ein typischer Greedy-Ansatz.
Ich mache lokal das zunächst aufgrund meiner aktuellen Informationen
dort das Bestmögliche.
Scanline-Prinzip kennen Sie überhaupt nicht.
Das hatte ich Ihnen vorhin angedeutet.
Es gibt so Probleme, bei denen man sich interessiert, welche Geraden
Sie schneiden, irgendwelche Probleme.
Das macht man so, dass man einfach systematisch hier über diese Punkte
rüberläuft, von links nach rechts.
Und dadurch im Prinzip ein zweidimensionales Problem auf ein
eindimensionales Problem reduziert.
Die Folge von eindimensionalen Problemen untersuchen muss.
Als wenn man sich im Wesen über so ein zweidimensionales Problem
rüberkriegt.
Und das ist eine Scanline, die einmal rüberläuft.
Und an den interessanten Punkten kann ich sagen, was da passiert und
kann dann das Problem lösen.
MapReduce ist ein Verfahren, das eigentlich auch schon ganz alt ist.
Das macht Folgendes, das ist ein systematischer Ansatz, der ist von
Mitarbeitern von Google ganz stark propagiert worden.
Also Google macht ganz viel MapReduce auf großen Datenmengen.
Man kann das gut beschreiben, wenn Sie, meinetwegen, ein
Klassifikationsproblem haben.
Sie haben also eine riesen Datenmenge und Sie wollen gerne
irgendwelche...
oder haben eine riesen Personendatei.
Und Sie wollen Listen haben von allen Personen, die in einzelnen
Städten gewesen sind.
Sie wollen das nach Städten ordnen.
Sie wollen das nach Namen ordnen.
Und wie macht man das?
Da hat man irgendwie eine Funktion, F, auf irgendeinem Datensatz.
Sagen wir jetzt einfach D.
Und dieser Datensatz, das ist irgendein Record.
Adressdatei.
So, und diese Operation muss jetzt auf ganz vielen Knoten gemacht
werden.
Auf jedem Knoten mache ich ein Mapping.
Überall führe ich die Funktion F auf.
Auf jedem dieser Knoten ist eine Teilmenge meiner Adressdatei drauf.
Jetzt bekomme ich hier irgendwelche Ergebnisse.
Was für Ergebnisse bekomme ich?
Ich bekomme Orte.
Ich bekomme jetzt also hier irgendeine Liste.
Oder einzelne Einträge.
Da ist jeweils ein Ort drauf.
Ich sage mal Location.
Und hier irgendein Name.
Das heißt, ich habe dann für jeden Datensatz den Ort und dahinter
einen Namen.
Ich möchte nachher gerne insgesamt rausbekommen, eine Liste von Orten
mit jeweils den Namen, die dazugehören.
Naja, da muss ich ja nur das, was diese einzelnen Knoten hier
berechnet haben.
Alle produzieren solche Tabellen.
Das muss ich nur geeignet wieder zusammenfügen.
Und das ist das Reduce.
Ich führe jetzt das hier zusammen.
Indem ich erstmal so eine Art Sortieren mache, entsprechend den ersten
Einträgen.
Und das mache ich auch wieder auf irgendwelchen Knoten.
In der Regel weniger als ich vorher hatte bei dem Map.
Und das ist das Reduce.
Und diese Reduce Knoten, die kriegen also hier Informationen aus den
verschiedenen Ergebnissen.
Die müssen alle gleichmäßig zu tun haben.
Und sollen dann am Ende hier diese gewünschte Liste produzieren.
Irgendwann muss da die gewünschte Liste rauskommen, wo ich zu jeder
Location eine Reihe von Namen habe.
Nächste Location und jeder Name und so weiter.
Das Map Reduce programmiert man, indem man einfach nur die Funktion f
angibt.
Und hier diese Reduce Funktion.
Und dann macht das der Rechner.
Eine Riesendatmung.
Das ist ein systematischer Ansatz, um Probleme zu lösen.
Okay.
Sehr aktuelle Thematik.
Diese Hadoop-Rechner.
Hadoop ist ein Rechner, der sowas macht.
Das wird im Cloud Computing oft erwähnt.
Hadoop macht genau dieses Map und Reduce in einer systematischen Art
und Weise.
Kann man aber auf Effizienzgesichtspunkten deutlich besser machen als
das, was Hadoop macht.
Das ist also auch ein interessantes Thema, dem man sich zur Zeit
beschäftigt.
Wonach fragen wir?
Wir fragen nach der Komplexität, nach den Kosten.
Was ist denn das alles?
Das ist die Zeit.
Und was ist die Zeit?
Naja, auf dem einen Rechner dauert das so lange, auf dem anderen
dauert das so lange.
Obwohl die Anzahl der Schritte gleich ist.
Hängt ja davon ab, wie die einzelnen Architekturen aussehen.
Also die Anzahl der Programmschritte ist eine allgemeinere Auskunft
als die CPU-Zeit.
Der Platz will die Anzahl der Speicherzellen.
Dann kann ich mir die Anzahl der Prozessoren anschauen, die ich
maximal brauche.
Ich kann mir anschauen, die Fläche auf dem Siliziumchip, die ich
brauche, um eine Berechnung auszuführen.
Auch das ist ein interessantes Thema.
Das Volumen.
Wie groß ist eigentlich der Würfel, in dem jetzt die ganze
Informationsverarbeitung gemacht wird?
Wie viel Volumen brauche ich mindestens, um ein bestimmtes Problem zu
lösen?
Oder wie ist der Kommunikationsbedarf?
Unterschiedlichste Maße.
Sie kennen eigentlich auf Standardvorlesungen nur die Zeit.
Und gleich noch den Platz.
Ja.
Ich verstehe, das ist einfach die
selbst basierte Bedarfsmöglichkeit?
Ja, natürlich.
Naja, es ist so.
Ich sage, die Anzahl der Nachrichten ist wichtig.
Selbstverständlich versucht man, den Kommunikationsaufwand hinter
Berechnungsaufwand zu verstecken.
Ich versuche normalerweise so zu machen, dass ich mit wenigen
Nachrichten ganz viele sinnvolle Berechnungen antriggern kann.
Und wenn eine Nachricht den Broadcast macht wie viele andere, dann
sind das ja viele einzelne Nachrichten.
Der Kommunikationsaufwand ist ja da.
Ich weiß nicht, ob ich diese Frage richtig verstanden habe.
Ja.
Ja?
Gut.
Wir kommen da später nochmal drauf zurück.
Okay.
Das Ganze ist natürlich abhängig davon, wie groß mein Problem
eigentlich ist.
Wie viel muss ich eigentlich machen?
Habe ich einen riesen Aufwand, wie bei MapReduce, auf irgendwelchen
riesen Datenmengen?
Habe ich eine kleine Liste, die ich sortieren muss, eine große Liste?
Dann ist es so, dass mich das Verhalten im schlechtesten Fall auf den
Mittel interessiert.
Was muss ich maximal aufwenden?
Schlechtester Fall, sogenannte Worst-Case-Execution-Time.
Das ist da die richtige Abschöpfung.
Brauche ich, wenn ich irgendwelche Echtzeitverarbeitungen mache?
Dann muss ich garantieren, dass bestimmte Operationen innerhalb einer
gewissen Zeitschranke erledigt sind.
Dann brauche ich eine Worst-Case-Execution-Time-Analyse für meine
grenzenden Rechnungen.
Häufig reicht uns eine Angabe über das mittlere Verhalten.
Oder ich sage, ich habe eine Gruppe von Berechnungen.
Also verschiedenste Dinge, die ich mir hier angucken muss bei der
Zeitkomplexität.
Bisschen genauer.
Jetzt wird es schon etwas formaler.
Wir schauen uns an.
Die Zeitkomplexität.
Was heißt das?
Berechnungszeit.
Abhängig von der Größe der Elemente.
Zunächst noch haben wir irgendeinen Algorithmus, der auf irgendwelchen
Eingaben etwas macht.
Also meinetwegen ein typisches Beispiel für Sortierverfahren.
Sie haben eure Folge von Elementen.
Kann klein, kann groß sein.
Und jetzt wollen Sie die sortieren.
Dazu brauchen Sie eine Angabe über die Größe dieser Eingabefolge.
Die einzelnen Elemente haben eine konstante Länge.
Der wesentliche Parameter ist die Länge der Liste.
Dann habe ich also eine Größenangabe über die Eingaben.
Und dann gucke ich mir an, die Rechenzeit des Algorithmus A bei
Eingabe von X.
Und die Rechenzeit im schlechtesten Fall wäre dann für Eingaben einer
gewissen Größe.
Die maximale Rechenzeit auf Eingaben, die alle die Größe N haben.
Also alle Folgen der Länge 27 haben irgendeine Rechenzeit.
Und ich gucke mir die maximale Rechenzeit an.
Das wäre also dann die Zeitkomplexität im schlechtesten Fall.
Wenn ich eine Wahrscheinlichkeitsverteilung gegeben habe auf den
Eingaben, dann kann ich Aussagen machen über die mittlere
Zeitkomplexität.
Dazu brauche ich aber Informationen darüber, welche Eingaben sind denn
wahrscheinlich.
Oder wie wahrscheinlich.
Wie ist die Verteilung der Eingaben?
Wenn ich die alle gleich verteilt annehme, habe ich einfache Mittel zu
berechnen.
Aber das ist nicht notwendigerweise der Fall.
Es kann ja sein, dass ich ganz spezielle Verteilungen habe.
Und deswegen ist es also davon abhängig.
Das kann ich genauso machen für alle anderen Maße.
Für Platz, für einfach Speicherzellen und so weiter.
Wir machen das Satz jetzt hier nur aufgeschrieben für die
Zeitkomplexität.
Das Ziel ist natürlich, dass ich Aussagen kriege damit über die
Qualität eines Algorithmus.
Aber allein die Aussage, dieser Algorithmus braucht so viel Zeit.
Anzahl Programmschritte oder ähnliches.
Das sagt mir noch gar nichts.
Ich will ja die Qualität bewerten.
Qualität heißt aber, ich muss das Ganze mit anderen vergleichen
können.
Also Bubble Sort braucht N²-Zeit.
Merge Sort NlogN.
Beides im schlechtesten Fall.
Dann ist offensichtlich Merge Sort besser.
Also halt nur im schlechtesten Fall.
Jetzt bin ich aber auch definitiv noch besser.
Also wenn ich mit unteren Schranken vergleichen kann, Aussagen über
was ich mindestens brauche an Zeit, dann weiß ich ja viel mehr.
Dann kann ich sagen, dieser Algorithmus ist optimal.
Den kann ich gar nicht verbessern.
Das ist der effizientest mögliche Algorithmus für diese
Problemstellung.
Das sind Aussagen über die Qualität.
Vergleich mit anderen Algorithmen oder Vergleich mit einer unteren
Schranke.
Hier ist so ein typisches, eigentlich aus einer Anfängervorlesung,
typisches Beispiel für Bedeutung von Rechenzeit, von Aufwand.
Aber ich will hier einen Aspekt noch mal ganz kurz beleuchten.
Der zeigt, dass das, was man normalerweise so intuitiv anschaut, wie
Abschätzungen der Rechenzeit und Einordnungen, naja, welche
Größenordnung ist das?
Das ist ein Jahresverfahren, das ist NlogN, das ist quadratisch, das
ist exponentiell.
Also A4 ist ja katastrophal, werde ich nie verwenden.
Das Interessante ist halt, sich anzugucken, was passiert eigentlich
für spezielle Problemgrößen.
Also, wenn ich spezielle Problemgröße habe, gucke ich mir an, was
braucht diese vier Algorithmen für diese Problemgröße an Zeit.
Dann nehme ich sie bestmöglich für diese Problemgröße.
Oder ich sage, was ist die maximale Problemgröße für eine Rechenzeit
von einer Sekunde.
Und dann sehen Sie, dass die Konstante hier vor auf einmal ganz viel
ausmacht.
Nämlich der Algorithmus A1, der erlaubt nur Problemgröße 1, während
der quadratische Algorithmus hier erlaubt Problemgröße 10.
Während der exponentielle hat immerhin eine Problemgröße von 9.
Und wenn Sie sich das für eine Minute Rechenzeit anschauen, dann fällt
also der exponentielle deutlich ab.
Dann ist aber immer noch hier mit der quadratischen Laufzeit immer
noch der beste.
Im Bezug auf die maximale Problemgröße, die bearbeitet werden kann.
Das ist das, was ich hier hinweisen wollte.
In meinem speziellen Anwendungsproblem, habe ich dort beliebige
Problemgrößen, für die ich etwas aussagen muss, oder habe ich eine
spezielle Problemgröße, immer die gleiche Problemgröße, und ich muss
dafür das beste Verfahren haben.
Dann spielen diese asymptotischen Aussagen über Größenordnung,
Wachstum n, n log n, n² oder so eigentlich gar keine Rolle.
Sondern dann spielt es eine Rolle, wie es für diese Problemgröße ist,
das bestmögliche Verfahren.
Es ist also tatsächlich so, dass jedes dieser vier Verfahren für das
gleiche Problem, für unterschiedliche Problemgrößen mal optimal sein
kann, bis auf hier den Algorithmus A2, der ist nie der beste für diese
Problemgrößen.
Es ist für jede Problemgröße, irgendeiner der anderen Verfahren,
irgendwo eines der anderen Verfahren besser.
Ja, und das will ich hiermit nur kurz andeuten.
Also hier sehen Sie natürlich für Problemgröße 10, ist der Zeitaufwand
für das exponentielle Verfahren etwa gleich, mit dem für das
Verfahren, das quadratisch ist, mit 10 n² läuft.
Für Problemgröße 25 haben Sie bereits einen Faktor 5400 für die beiden
Verfahren.
Das ist halt das exponentielle Wachstum.
Aber wenn Sie nur an Problemgröße 10 interessiert sind, hätten Sie die
Wahl welcher von den beiden.
Dann könnten Sie sagen, das ist ja völlig exotisch.
Wo habe ich ein Problem, wo es so große Unterschiede hat?
Schauen Sie sich ein einfaches Problem an.
Polynom-Auswertung.
Wir haben ein Polynom, a, i, x hoch i, i gleich 0 bis n, und wollen
das auswerten.
Also dieses Polynom hier, wir haben n plus 1 Koeffizienten, a0 bis an,
wir haben diese x, o, n zu berechnen.
Wenn Sie das naiv machen, von links nach rechts, das einfach
berechnen.
Dann müssen Sie hier an mal x mal x mal x mal x und so weiter machen,
bis Sie hier x, o, n berechnet haben.
Das sind also hier in dem Fall n Multiplikationen.
Dann haben Sie hier n-1 Multiplikationen.
Dann haben Sie als nächstes n-2 Multiplikationen, wenn Sie das Ganze
naiv von links nach rechts aufführen.
So steht es da.
Das sind also dann Summe n, n-1 und so weiter, Multiplikationen, also
n halbe mal n plus 1 Multiplikationen.
Und wir müssen die ganzen Terme aufaddieren, das sind also dann
nochmal n Additionen.
Wenn Sie das Ganze etwas anders machen, und die Gesetze der Arithmetik
ausnutzen, dann können Sie hier einiges ausklammern.
Sie können das hinschreiben als amx plus am-1 mal x plus am-2 mal x
und so weiter plus a1 mal x plus a0.
Einfach nur Gesetze der Arithmetik ausgenutzt.
Und jetzt brauchen Sie hier eine Multiplikation, eine Addition, eine
Multiplikation und so weiter.
Sie haben n Multiplikationen und n Additionen.
2 n Operationen.
Man kann sogar zeigen, das ist optimal.
Wenn ich nichts weiß über diese Komponenten und nichts weiß über die
Variante x vorher.
Dann ist das Ganze tatsächlich optimal.
Ich muss dann...
Es gibt kein Verfahren, das mit weniger als n Multiplikationen und n
Additionen diesen Termen ausrechnet.
Das heißt, hier haben Sie so ein typisches Beispiel für
unterschiedliche Verfahren.
Das eine braucht quadratische Zeit, das andere braucht halt hier
lineare Zeit.
Und das kann sogar optimal nachgewiesen werden.
Das machen wir später nochmal.
Also das sind halt tatsächlich wichtige Vergleiche von Algorithmen.
Und jetzt hatte ich gesagt, wir sind nicht immer an den asymptotischen
Aussagen interessiert.
Manchmal aber schon.
Sie kennen alle diese O-Notationen.
Also groß O von F.
F sei irgendeine Funktion, die praktisch die Größe einer Problemgröße
abbildet.
Auch irgendeine reale Zahl.
Und das O von F ist im Prinzip eine Menge von Funktionen.
Eine Menge von Funktionen G, die nicht stärker wachsen als das F.
Das heißt, das F ist eine obere Schranke für das Wachstum der
Funktionen, die hier in dieser Menge sind.
Obere Schranke heißt, das F von N ist größer gleich dem G von N bis
auf einen konstanten Faktor C ab irgendeiner Problemgröße.
Kann sein, dass im Anfangsbereich das ganz anders aussieht.
Aber irgendwann ist diese Funktion bzw.
ein konstantes Vielfache dieser Funktion F von N größer gleich dem G
von N.
Das heißt, wir haben hier eine obere Schranke für das Wachstum der
Funktionen, die in dieser Menge drin sind.
Also ein typisches Beispiel des Umschreibens O von N².
Damit sind alle Funktionen charakterisiert, die maximal quadratisch
wachsen.
Für Großelten.
Das Ganze können Sie auch anders ausdrücken.
Sie können auch sagen, dass es nicht das Gleiche ist.
Etwas anderes ist es, zu sagen, ich gebe eine Schranke an, die sagt,
diese Funktion F...
oder es sind alle Funktionen drin, die deutlich langsamer wachsen als
das F.
Das F ist deutlich langsamer für großes N.
Heißt, der Limus des Verhältnisses von G von N zu F von N, für N gegen
unendlich, ist gleich 0.
Das heißt, das F von N wächst wesentlich stärker als alle Funktionen,
die in dieser Menge drin sind.
Also zum Beispiel...
Es ist...
Klein n.
Die Funktion, äh, meinetwegen, tausendmal n.
Die ist aus...
Ups.
Kein Point Effect.
Aus...
Klein o von N².
N² wächst wesentlich stärker als jede lineare Funktion.
So.
Das ist das kleine o.
Dann gibt es ein großes Omega, das sind die unteren Schranken.
Eine Funktion, die alle anderen Funktionen enthält, die mindestens so
stark wachsen wie das F.
Untere Schranke.
Und genauso das Klein Omega von F.
Eine Funktion, die deutlich langsamer wächst als alle Funktionen, die
hier drin sind.
Also da ist genau das Verhältnis andersrum.
Das Verhältnis von F von N zu G von N.
Alle Funktionen, die hier drin sind, wachsen deutlich schneller als
diese Funktion F von N.
Und dann gibt es noch das Theta.
Das ist gerade die Menge der Funktionen, die genauso schnell wachsen.
Bis auf konstante Faktoren.
Ab einer gewissen Größe.
Also tot.
Also genauso schnell.
Wachstum ist nach unten und nach oben beschränkt.
Bis auf konstante Faktoren durch die Funktion F.
Also 10 N² ist ein Theta von N².
Das kennen Sie wahrscheinlich alle.
Das Ganze wird häufig etwas lax verwendet.
Häufig wird nicht geschrieben wie aus O von F, sondern wie gleich O
von F, was natürlich falsch ist.
O von F ist eine Menge.
Keine Zahl.
Oder es wird auch manchmal geschrieben O von F gleich O von G, was
auch nicht richtig ist.
Sondern das ist ein Enthaltenseinsaufsagen.
Ein Beispiel hier.
Manchmal schreibt man nebenhin O von N gleich O von N².
Aber natürlich ist das nicht der Fall.
Weil das nur ein Enthaltenseins ist.
Und insbesondere ist natürlich O von N² ungleich O von N.
Da muss man aufpassen, wenn man was liest, diese Abschätzungen gemacht
werden.
Da wird manchmal das Gleichheit verwendet.
Obwohl Gleichheit gar nicht angemessen ist.
Sondern es ist neben dem Enthalten nur ein Eingemein.
Kleinigkeiten.
Sie werden in den Übungen auch damit nochmal beschäftigen müssen, dass
Sie einfach das nochmal rekapitulieren.
Was ist die Ronotation?
Ronotation ist Ihnen im Prinzip allen bekannt.
Davon gehe ich aus.
Vielleicht nicht diese Vielfalt von Begriffen.
Sondern Sie erkennen in der Regel Groß O und noch Groß Omega.
Aber die kleinen vielleicht nicht.
Das ist aber alles da mit drin.
Und jetzt schauen wir uns an die Dinge, die ich vorhin angesprochen
habe.
Komplexität eines Problems.
Vorhin habe ich angesprochen Komplexität eines Algorithmus.
Jetzt möchte ich die Komplexität eines Problems ansprechen.
Also Komplexität des Sortierens.
Nicht Komplexität eines Sortierverfahrens.
Sondern die Komplexität des Sortierens.
Und dann schaue ich mir an.
Erstmal eine untere Schranke.
Für den Zeitaufwand.
Zur Lösung des Problems.
Das ist halt eine untere Schranke.
Wenn die Rechenzeit jedes Algorithmus, der das Problem löst, im
Wachstum von unten beschränkt ist.
Das heißt, die Zeitkomplexität der Algorithmen von A, die das Problem
lösen, wächst mindestens so stark wie das F.
Eine untere Schranke.
Deswegen brauche ich das Omega von F.
Jetzt kommt bei der oberen Schranke genau das Gegenteil.
Das O von F.
Das F ist eine obere Schranke.
Wenn es einen Algorithmus gibt, dessen Laufzeit beschränkt wird nach
oben durch das F, der maximal so stark wächst, wie diese Funktion F.
Das ist halt der wesentliche Unterschied hier.
Obere Schranken durch einen Algorithmus.
Untere Schranken sind Aussagen über alle Algorithmen.
Das dauert ziemlich lange, bis man so eine Aussage hat, bis man alle
Algorithmen angeschaut hat.
Also muss man das irgendwie allgemeiner formulieren.
Wir werden ein paar untere Schranken kennenlernen im Laufe der Folge.
Und das Ganze muss natürlich sich auf die Gleichrechnungsstruktur
beziehen.
Ich muss ja wissen, worauf ich das eigentlich beziehe, wenn ich etwas
von Rechenzeit sage.
Und Anzahl von Schritten.
Das ist natürlich wichtig, sich das klarzumachen.
Es ist auch klar, dass es in der Regel schwierig ist, gute untere
Schranken zu bestimmen, weil ich da eben, wie gesagt, alle möglichen
Algorithmen wieder betrachten muss.
Und ohne Kenntnis unterer Schranken kann ich gar nicht so etwas sagen,
ob ein Algorithmus bestmöglich ist.
Und es gibt Probleme, bei denen wir das tatsächlich machen können.
Ich hatte es schon kurz angedeutet, bei der Polynom-Auswertung können
wir sagen, das Vorner-Schema ist ein optimaler Algorithmus für die
sequenzielle Lösung des Problems, Polynome auszuwerten.
Also dieses mit linearer Zeit 2N-Operationen.
Bei der Matriz-Modifikation, da können wir nichts sagen über
Optimität, weil wir nur eine ganz schlechte untere Schranke haben.
Da kennen wir nur die triviale untere Schranke von N², für die
Modifikation von N², von NxN-Matrizen.
Und die beste hohere Schranke ist irgendwo bei N hoch 2.3, noch was.
Und das Standardverfahren, das wir kennen, ist bei N hoch 3.
Also das werden wir uns nächstes Mal genauer anschauen.
Ja, Zeitmessung, wie mache ich das eigentlich?
Ich kann mich von der Stoppuhr daneben stellen und messen.
Ingenieure machen das auch so.
Wenn die Aussagen machen, wie lange ihr Code gelaufen ist, dann
kriegen sie die Sekundenangaben.
Das ist etwas, was auf dem speziellen Rechner liegt, Spezieller
Rechner, die uns die Problemparameter hat so lange gedauert.
Da können wir das nachvollziehen.
Es gibt aber keine generalisierbare Aussage.
Also, ich muss Angaben über die Laufzeit des Programms haben.
Irgendwie über Anzahl von Operationen.
Und wenn ich weiß, wie groß meine Gefäßausführungszeit ist, kann ich
das dann abschätzen.
Wenn ich aber Zeit wirklich messen will, kann ich natürlich auch
einfach über Anweisungen im Programm messen.
Die lokale Zeit.
Ich habe hier also mein Programm.
Dann habe ich hier einen Punkt und da einen Punkt, wo ich messe.
Hier stoppe ich die Zeit.
C1, C2.
Dann brauche ich nur die Differenz zu bilden und ich weiß, wie lange
dieses Programmstück hier gedauert hat.
Wenn Sie das machen, müssen Sie aufpassen, dass Sie nicht einen zu
kleinen Wert bekommen.
Es wird ja nicht mit einer riesigen Auflösung, also mit der feinsten
möglichen Auflösung, gemessen.
Es wird nicht die Anzahl der Kapsel gemessen, sondern es wird etwas
gröber gemessen.
Und deswegen muss man, wenn man Messungen macht von Programmpro,
irgendwelche einzelnen Anweisungen messen.
Wie lange dauert das eigentlich, eine Addition auszuführen?
Dann müssen Sie die ganz oft machen.
Bevor Sie dann wirklich zählen, müssen Sie also das hier am besten
irgendwie in der Schleife haben, die ganz oft ausgeführt wird.
Und dann messen Sie die Zeit, dann wissen Sie, wie lange dieses
Programmstück tatsächlich gedauert hat.
Das sind alles so Dinge, die man dann macht.
Also zu messenden Code, die Zeitaufgaben einschließen, ist sinnvoll.
Sehr oft ausführen lassen.
Oder Sie nutzen irgendeine Profiling-Option bei der
Programmausführung.
Wenn Sie ein gutes System haben, dann haben Sie in der
Laufzeitumgebung Möglichkeiten, so ein Profiling zu machen und kriegen
genaue Angaben über die Ausführungszeit für bestimmte Teile Ihres
Programms.
Aber das Problem ist, wenn Sie jetzt Programmoptimierung machen und
Sie haben hier etwas eingebaut, wo Sie die gleiche Anweisung
hundertmal ausführen, wird jeder einigermaßen sinnvolle
Programmoptimierer automatisch diese Schleife rausstreifen.
Da muss man aufpassen, dass man nicht durch die Codeoptimierung das,
was man da eingebaut hat, für das Messen von Zeit wieder rausgeworfen
bekommt.
Alternative ist, dass Sie nicht Zeit messen, sondern dass Sie sich das
Rechnungsmodell anschauen und dann auf Basis dieses Rechnungsmodells
die einzelnen Angaben machen über die Anzahl der Berechnungen, die
Anzahl der Schritte, die auf der Abstraktenmaschine gelaufen sind.
Und das ist das, was wir uns im nächsten Kapitel anschauen müssen.
Wir sind schon durch das erste Kapitel durch und können jetzt noch
ganz kurz anfangen mit dem zweiten Kapitel.
Alles in der Einführungsvorlesung.
Das war relativ schnell.
Haben Sie Fragen?
Vielleicht als Vorsorge nach fünf Minuten Zeit.
Irgendwelche Fragen zu dem, was ich Ihnen erzählt habe?
War ein bisschen Stoff auch dabei?
Ich sage nicht, nein, es ist kein Stoff.
Es ist wirklich einfach.
Das Grundlagerstoff, das kennen Sie ja eigentlich alles.
Diese Animation ist eigentlich gar nicht erforderlich.
Hier sehen Sie übrigens nochmal die verschiedenen
Berechnungsstrukturen.
Sie haben auch verschiedene Berechnungsmodelle.
Das hier, was Sie hier unten sehen, ist eine Random Access Machine
oder Registermaschine.
Das hier wäre eine typische baumartige Berechnung.
Das hier ist eine PRAM mit einem gemeinsamen Speicher.
Das hier wäre eine PRAM mit einem verteilten Speicher.
Dieses Bild hier gibt Ihnen an, wie man die Multiplikation von
Matrixen machen kann auf einem zweidimensionalen Prozessorfeld.
Diese Zahlen geben praktisch Matrix-Elemente an, die in dieser
Richtung, in der Richtung und in der Richtung synchron durch das Netz
durchlaufen und dann die Matrix-Multiplikationen ausführen.
Das hier gibt Ihnen an, die Berechnungsstruktur einer schnellen
Projekttransformation bzw.
eines Butterfly-Netzwerkes.
Und das hier unten, das ist ein Mesh of Trees.
Und da sehen Sie angedeutet, dieses Scanline-Prinzip, Sweepline, das
über eine geometrische Objekte hinwegläuft.
Also damit Sie sehen, was da eigentlich steht auf der Titelfolie.
So.
Ein paar Minuten will ich noch nutzen.
Wenn wir uns Berechnungsmodelle anschauen, dann wollen wir natürlich
das möglichst einfach machen.
Und das Modell muss möglichst einfach sein, aber auch komplex genug,
damit es realistische Aussagen erlaubt.
Also technische Details möchte ich rausstreichen.
Und ich will aber etwas sagen über die existierenden Rechner.
Sie kennen den von Neumann-Rechner, der sieht hier ganz ähnlich aus.
Bei der Random Access Machine, das ist also das Standardmodell für
sequenzielle Algorithmen.
Da haben Sie also ein Programm, ein Speicher.
Sie haben ein Arithmetic Logic Unit, eine arithmetisch-logische
Einheit.
Ein Befehlszähler, der Ihnen das aktuelle Befehl angibt.
Ein Register in der ALU.
Da können Sie also irgendeinen Wert rein speichern.
Das Ergebnis kommt da in der Regel rein.
Und Sie haben eine ALU für die arithmetisch-logische Operation.
Und Sie können etwas eingeben, Sie können etwas ausgeben.
Sehr stark vereinfacht.
Keine technischen Details.
Es soll praktisch nur angeben, Sie können hier rechnen.
Und hat ein bisschen Ähnlichkeit mit dem von Neumann-Modell.
Aber die Eigenschaften des von Neumann-Modells spielen ja keine Rolle.
Wir machen hier nur eine Aufwandsschätzung.
Technische Realisierung existiert ja eigentlich nicht im Augenblick.
Was ist hier alles drin?
Da ist das Programm drin.
Das ist einfach eine Folge von Befehlen, irgendwie nummeriert.
Ich habe einen Speicher, der absehbar viele Register enthält.
Unendlich viele Register.
Bei jedem Rechner können Sie beliebige Speicher dazufügen.
Also absehbar und endlich.
Und die Adressen sind wahlfrei, also jedes Element ist wahlfrei
adressierbar.
Das ist Abstraktion von der technischen Realität.
Wenn Sie einen riesen Speicher haben, wo die Daten irgendwo im
virtuellen Adressraum liegen.
Auf der Festplatte oder irgendwo anders, da ist die Zugriffszeit nicht
identisch.
Wir nehmen das aber hier an.
Wir haben random access, wahlfreien Zugriff, immer die gleiche Zeit.
Und wir haben außerdem in jedem Register eine beliebige ganze Zahl
drin.
Können wir rein speichern.
Egal wie groß sie ist, wir können jede beliebige Zahl da rein
speichern.
Zwei, fünf oder sieben.
Aber auch die Zahl drei Millionen irgendwas.
Oder eine riesen Zahl mit 100 Stellen.
Oder 500 oder 1000 oder 8000 Stellen.
Können Sie jeweils in ein Register reinschreiben.
Ist abstrakt.
Abstrakte Annahme.
Muss sehen, ob das realistisch ist.
Und die Belegung des Speichers gibt Ihnen an, welchen Zustand
eigentlich der Rechner gerade hat.
Im Prinzip ist das eine echte Automatik.
Die ganzen Operationen sind Zustandsübergänge.
Ist also eigentlich eine echte Automatik.
Aber wir nennen das die Registermaschine mit bestimmten Eigenschaften.
Und wir haben hier einen Ausgabeblender, das ist ein Einwegblender.
Sie können da nur lesen vom Eingabeband.
Sie können nur schreiben aufs Ausgabeband.
Und die Arbeit geschieht halt innen drin.
Die zentrale Recheneinheit hat einen Befehlszähler, der speichert auch
die aktuellen Befehle.
Sie haben einen Akkumulator.
Hier gibt es davon Berechnungen.
Und wir haben diese Recheneinheit und Befehle aufzuführen.
Und die weiteren Einzelheiten, die Befehle usw.
schauen wir uns nächste Woche an.
Vielen Dank für die Aufmerksamkeit.
Ich hoffe, Sie alle wiederzusehen.
Das war's.