So, schönen guten Tag.
Ich begrüße Sie zur Vorlesung Effiziente Algorithmen.
Ich bin ganz begeistert, natürlich darüber, dass Sie alle da sind.
Ich bin aber auch begeistert darüber, dass ich tatsächlich richtig
aufzeichnen kann.
Wir hatten gestern einen seltsamen Effekt, dass auf einmal bei
Software, die wir seit Jahren standardmäßig nutzen zum Aufzeichnen der
Vorlesung, Camtasia, auf einmal die Maussteuerung der Control Panels
nicht mehr funktioniert, das Ding nicht mehr darauf anspricht.
Und auf allen Rechnern mit allen Versionen, irgendein Update von
Windows muss dazu geführt haben, dass auf einmal dort irgendwas nicht
mehr funktioniert.
Aber ein findiger Mitarbeiter hat das hingekriegt, dass man über
gewisse Tastensteuerungen doch noch irgendwie Zugriff bekommt auf die
Control Panels, sodass tatsächlich das Mikrofon hoffentlich auch
wirklich tatsächlich aufgenommen wird und auch in der richtigen Art
und Weise.
Das war alles etwas schwierig.
Gestern konnte ich also meine Vorlesung Organic Computing nicht
erfolgreich aufnehmen.
Ich hoffe, dass es heute besser ist.
Also ich begrüße Sie nochmal zur Vorlesung Effiziente Algorithmen,
Sommersemester 2015.
Sie sehen hier auf der Eingangsfolie eine ganze Reihe von Dingen, mit
denen wir uns in dieser Vorlesung beschäftigen werden.
Also Sie sehen hier einerseits etwas, was Sie alle im Prinzip kennen
aus einführenden Vorlesungen, so etwas wie eine Von-Neumann-Maschine,
was hier aber ein Random Access Machine ist.
Dann sehen Sie hier etwas, wo man solche Maschinen nebeneinander
parallel drin hat.
P steht für Processing, Verbindungsnetz und M für Memory.
Also hier haben wir mehrere solche Verarbeitungseinheiten so
verbunden.
Hier haben wir eine andere Art der Verbindung.
Hier sehen Sie gewisse Berechnungsstrukturen baumförmig.
Hier sehen Sie ein Rechnernetz, in das Daten aus verschiedenen
Richtungen reinlaufen, durchlaufen.
Solche Dinge werden Sie kennenlernen.
Sogenannte systolische Algorithmen.
Hier sehen Sie ein Verbindungsnetz, das die Grundlage ist für die
schnelle Fourier-Transformation.
Auch die werden Sie kennenlernen.
Und hier sehen Sie noch eine interessante Struktur.
Das ist ein Mesh of Trees.
Also Sie werden viele verschiedene Verbindungsstrukturen von Rechnern
kennenlernen, die man nutzen kann effizient für Berechnungen.
Und hier sehen Sie noch etwas, das hat zu tun mit algorithmischer
Geometrie, wo man in der Lage sein möchte, Überschneidungen von
irgendwelchen Graden, da sehen Sie hier so einen Überschneidungspunkt,
solche Punkte zu identifizieren, wenn Sie eine Menge von Graden haben,
festzustellen, welche überschneiden sich an welchen Punkten.
So etwas braucht man, wenn man irgendwelche grafischen Darstellungen
machen möchte von irgendwelchen geometrischen Objekten.
Da müssen Sie wissen, welche Objekte sind im Vordergrund, welche sind
im Hintergrund.
Wie kann ich solche Schnittpunkte geeignet verwenden, um bei der
grafischen Darstellung sinnvolle Dinge zu machen.
Es gibt eine Vielfalt von Themen, mit denen wir uns beschäftigen
werden.
Ich habe das im Weiteren noch genauer ausgedrückt.
Zunächst einmal, bevor wir anfangen mit diesen Dingen, möchte ich ein
paar organisatorische Dinge Ihnen vorstellen.
Zunächst einmal mich selbst.
Sie kennen mich, Hartmut Schmeck.
Ich sitze drüben im Allianz-Gebäude am Kronplatz und habe gewisse
Sprechstunden.
Dienstags, also heute nach der Vorlesung.
Sie können mich per E-Mail erreichen.
Und wir haben natürlich nach wie vor einen Vorlesungs-Arbeitsbereich.
Hier sehen Sie die URL.
Ich will da jetzt gar nicht rauf gehen direkt.
Sie wissen, wie diese Ilias-Umgebungen aussehen.
Was mich sehr stört, ist, wenn man auf das Vorlesungsverzeichnis geht
und auf die Vorlesung, dann gibt es dort einen Link und da steht ein
Ilias -Kurs öffnen.
Da niemand einen Ilias-Kurs hören möchte hier bei mir, sondern eine
Vorlesung über effiziente Algorithmen, wird niemand auf die Idee
kommen, einen Ilias-Kurs zu öffnen, wenn er einen Vorlesungs
-Arbeitsbereich haben möchte.
Also das ist eine völlig unsinnige Beschreibung eines Links, weil man
dort zu dem Bereich kommen möchte, wo Unterlagen für die Vorlesung
abgelegt sind.
Man möchte keinen Kurs über Ilias belegen.
Also insofern ist das etwas seltsam.
Leider mussten wir uns auf dieses System umstellen.
Wir hatten früher ein schönes Studierendenportal, das war früher
Studium.edu, wo wir Vorlesungs-Arbeitsbereiche auf einer anderen Basis
angeboten haben.
Die technologische Basis dafür wird aber nicht länger vom SCC
unterstützt, sondern es wurde entschieden, auf Ilias umzusteigen.
Das ist leider ein altes System, das nicht den heutigen Anforderungen
entspricht für Menüführung und all diese Dinge.
Aber wir haben nun mal dieses System übernommen.
Es funktioniert auch einigermaßen, aber es ist sicherlich nicht das
nachhaltige System, das wir auf ewige Zeiten verwenden werden.
Das wird auch irgendwann wieder verändert werden.
Auf jeden Fall haben wir dort die Informationen zur Vorlesung alle
dargestellt.
Sie werden sich da irgendwie zurechtfinden können.
Sie kennen das aus anderen Vorlesungen und werden damit hoffentlich
sinnvoll umgehen können.
Die Vorlesung findet statt, hier heute zu dieser Zeit, in diesem Raum,
Raum 221.
Die, die hier sind, wissen das.
Die, die nicht da sind, werden vielleicht auch sonst nicht kommen,
sondern sich die Vorlesungen aufgezeichnet anhören.
Die Übungen sind freitagsvormittags im Raum 231.
Und am Ende der Vorlesung gibt es natürlich eine Klausur, wie üblich
an einem dieser drei Tage, die dort angegeben sind, wie üblich die
ersten drei Tage nach Ende der Vorlesungszeit, Montag, Dienstag oder
Mittwoch.
Die Unterlagen zur Vorlesung sind, wie üblich, das Skript, zum Teil
mit Annotationen, wobei die Annotationen im Wesentlichen dazu dienen,
manchmal bei den Evaluationen wird das manchmal etwas kritisiert, dass
die Annotationen, wenn ich so etwas unterstreiche, die Übungen sind im
Raum 231, warum muss das unterstrichen werden?
Ich unterstreiche häufig Dinge auf einer Folie aus folgendem Grund.
Die Vorlesung wird ja aufgezeichnet.
Und wenn man eine aufgezeichnete Vorlesung sich später wieder
anschaut, dann muss irgendwie die Aufmerksamkeit beim Anschauen auf
die Punkte gelenkt werden, um die es gerade geht.
Und deswegen arbeite ich mit dem Stift und annotiere solche Dinge.
Manchmal schreibe ich auch Dinge rein, um die Vorlesungen genauer,
oder um Dinge genauer zu erläutern.
Aber manchmal mache ich eben wirklich nur Dinge, dass ich einfach
etwas anstreiche und das sieht dann nachher so aus, als wären da nur
Dinge wahllos unterstrichen, wenn man sich die annotierten Folien als
PDF anschaut.
Wenn man sich aber die Aufzeichnung nochmal anschaut, das abspiegelt,
dann sieht man, dass das durchaus Sinn macht, da ab und zu etwas zu
sehen auf dem Bildschirm.
Das heißt, da versuche ich wirklich die Aufmerksamkeit des Betrachters
genau auf den Punkt auf der Folie zu lenken.
Ich mache das ja auch nicht so, wie das in einigen anderen Portalen
gemacht wird, dass man bei einer aufgezeichneten Vorlesung ein Bild
des Dozenten mit dabei hat.
So ein Videobild des Dozenten bringt eigentlich überhaupt nichts, das
lenkt nur ab von dem Inhalt.
Und das Wesentliche ist der Ton und der Inhalt der Folien.
Deswegen meine Person, wie ich aussehe, ist völlig irrelevant.
Wenn man das sehen möchte, kann man sich hier das eine Bild anschauen
oder mich in der Live-Vorlesung erleben.
Was ich immer noch sehr schön finde, dass ich Sie direkt sehe und
Rückmeldungen direkt sehe.
Also ich finde das sehr schön, Vorlesungen zu erhalten, wobei man sich
darüber streiten kann, was eigentlich heutzutage die beste Art der
Wissensvermittlung, der Vermittlung von Fähigkeiten ist.
Ob Vorlesungen das richtige sind in einer Zeit, wo man eigentlich
nichts vorlesen muss, sondern wo alles aufgeschriebene Wissen für
jeden verfügbar ist.
Früher war das nicht so, da war das aufgeschriebene Wissen nur für die
Dozenten verfügbar, für die Professoren.
Und sie mussten das vorlesen, damit die Studenten das erfahren
konnten.
Das ist der Grund für eine Vorlesung gewesen.
Und heute können Sie das alles selbst irgendwo sich zusammensuchen.
Wo die Frage ist, wie erwerben Sie die Fähigkeiten, dann immer noch
entsprechend damit sinnvoll umzugehen.
Also das sind aber Fragen, die wir hier nicht in der Vorlesung
intensivieren werden.
Das ist keine Vorlesung über Lernstrategien, sondern über effiziente
Algorithmen.
Okay, die Vorlesungen sind aufgezeichnet.
Sie sind abspielbar mit verschiedenen Wiedergabesoftware-Paketen.
Unter anderem mit dem Camtasia Player, der insbesondere das sichtbare
Scrolling unterstützt.
Nur dann macht es Sinn, so eine aufgezeichnete Vorlesung anzuschauen,
wenn Sie da schnell durchlaufen können und sehen können, wo Sie gerade
sind.
Ein anderer Punkt ist, dass man manchmal gerne folgenden Effekt haben
möchte, der von VLC angeboten wird.
Da möchte man gerne in der Lage sein, die Geschwindigkeit der
Vorlesung zu variieren.
Das ist ein sehr nettes Feature, dass man dann in der Lage ist, eine
Vorlesung irgendwie so 1,5 oder vielleicht auch nur 1,3-fache
Geschwindigkeit, doppelte Geschwindigkeit, das wäre schwierig, dann
hören Sie nicht mehr viel.
Aber man kann also die Geschwindigkeit erhöhen.
Und das Gute ist, dass dadurch die Stimme nicht zu einer Mikke-Maus
-Stimme geht, sondern die Tonhöhe bleibt gleich.
Es werden Dinge dort einfach rausgenommen, sodass man den Ton oder die
Geschwindigkeit der Wiedergabe dadurch erhöht.
Und das ist für einige durchaus interessant, eine 1,5-stündige
Vorlesung in einer Stunde zu hören und ab und zu mal das Ganze
vielleicht zu verlangsamen, um intensiver Dinge zu machen.
Also die Flexibilität solcher aufgezeichneten Vorlesungen ist schon
recht gut.
Und insbesondere, wenn man eben etwas nachbereiten will oder sie
vorbereiten will auf die Prüfung, dann macht es sehr viel Sinn, durch
einige Dinge schnell durchzulaufen und durch andere ein bisschen
intensiver.
Also das war sehr viel Erläuterung zu dieser Thematik.
Ganz kurz will ich hinweisen auf die Nuke-Tools.
Ich mache sie jetzt nicht auf.
Wenn Sie möchten, dass ich die Nuke-Tools... also wer hat die Nuke
-Tools noch nicht selbst erlebt?
Sie kennen die alle aus der Grundlagenvorlesung.
Und wenn Sie möchten, dass ich das hier laufen lasse, damit Sie
Feedback geben können auf elektronische Art und Weise, mache ich das
gerne.
Dann schicken Sie uns bitte eine Mail, sagen Sie uns das im Forum oder
irgendwie machen Sie sich bemerkbar.
Dann werde ich das hier auch tatsächlich starten.
Dann sehe ich hier Ihr Feedback.
Ansonsten ist der Raum relativ klein und ich kann direkt eigentlich
Rückmeldung von Ihnen bekommen.
Das ist mir eigentlich mindestens so lieb wie diese elektronische Art
und Weise, wobei die natürlich auch einige Vorteile hat.
Aber das will ich jetzt auch nicht zu sehr vertiefen.
Ich habe die Folien hier nochmal drin.
Für jemanden, der das noch nicht gesehen hat, der kann sich das kurz
angucken.
Aber ich werde hier nicht weiter darauf eingehen jetzt.
Sie kennen das aus der Grundlagenvorlesung.
Zu den Übungen ist zu sagen, das macht mein Mitarbeiter Herr Braun.
Er sitzt dort hinten und wird also die Übungen betreuen.
Er hat keine feste Sprechstunde angeben wollen, sondern sagt, das
macht er nach Vereinbarung.
Je nachdem, wie stark er dann von Ihnen überlaufen wird, wird das
vielleicht doch irgendwann kanalisieren auf eine bestimmte Zeit.
Aber im Augenblick macht er das also sehr flexibel.
Sie können ihn per E-Mail erreichen.
Und zu den Übungen gibt es eine ganze Reihe von Informationen, die Sie
eigentlich im Wesentlichen auch so erwarten werden.
Übungen sind 14-tägig, wie üblich.
Freitags hatte ich schon gesagt.
Sie können dort eben den Stoff der Vorlesung intensiver sich
anschauen.
Man lernt durch aktive, selbstständige Bearbeitung von Themen, die mit
dem Stoff der Vorlesung zu tun haben.
Das ist die beste Art, etwas zu lernen.
Nur durch Anhören lernt man sehr wenig.
Früher meinte man, durch Mitschreiben lernt man durch die Hand.
Das ist auch was Wahres dran.
Aber da wir Ihnen alles anbieten, bis zu der aufgezeichneten
Vorlesung, ist es ganz wichtig, dass Sie sich selbst auch intensiv mit
dem Stoff beschäftigen.
Das geht in den Übungen.
Und deswegen ist es wirklich wichtig, dass Sie das auch versuchen, das
dort selbst zu machen.
Wir erwarten, dass Sie aktiv dort teilnehmen.
Wir wünschen uns das sehr.
Wir freuen uns, wenn Sie aktiv an den Übungen teilnehmen und nicht nur
da sitzen und zuhören, was der Tutor sagt.
Das ist eigentlich nicht angemessen für eine Universität, dass man nur
zuhört.
Also dieser Frontalstil für eine Vorlesung ist eigentlich... das kann
man in der Vorlesung machen, aber in Übungen muss da mehr Interaktion
tatsächlich erfolgen.
Die Organisation der Gruppen, die Termine stehen alle im
Vorlesungsarbeitsbereich, also auf dieser Ilias-Plattform.
Die Anmeldung kann ab heute bis in einer Woche erfolgen.
Also eine Woche lang steht das offen über YouSubscribe.
Der Link ist hier angegeben in der PDF-Version, können Sie
draufklicken.
Das ist also die übliche Umgebung für Anmeldungen für diese Vorlesung.
Wie üblich erwarten wir, dass Sie die Aufgaben in Zweiergruppen
bearbeiten.
Man muss es lernen, gemeinsam zu arbeiten, nicht nur alleine.
Auch eine wichtige Fähigkeit, die man erwerben muss im Studium, das
wissen Sie alles.
Die Vorlesungsblätter geben Sie bitte hier in der Vorlesung ab,
Dienstags.
Und jetzt die Frage, wenn wir Leute haben, die im wesentlichen
Dienstags gar nicht da sind, wie die das machen.
Aber, Herr Braun, wie machen wir das?
Per E-Mail ist auch in Ordnung.
Bitte?
Aha.
Also, per E-Mail...
auch...
okay.
So.
Gut, geht also auch.
Übungsblätter werden korrigiert.
Also, wir machen hier nicht diese Art, wie wir das in einigen
Grundvorlesungen machen, dass Sie Anwesenheitsübungen machen, wo Sie
direkt in der Übung Aufgaben bearbeiten, sondern Sie geben die
Aufgaben ab.
Sie werden korrigiert.
Sie können Punkte dafür bekommen.
Sie können jeweils 20 Punkte erreichen pro Übungsblatt.
Und es gibt insgesamt 5, also können Sie 100 Punkte bekommen, wenn Sie
alles perfekt gemacht haben.
Das Ganze geht am 21.04.
los.
Da wird das erste Übungsblatt ausgeteilt.
Erste Übung ist dann erst am 8.05.
Ist ja Freitag.
Der erste 5.
ist ein Feiertag.
Deswegen geht das erst am 8.05.
Eine Woche vorher macht keinen Sinn.
Das wäre der 24.
Das ist Ende nächster Woche.
Da kann man noch nicht wirklich was tun, wenn das erste Übungsblatt
erst am 21.04.
rauskommt.
Dann wichtig.
Ich gebe immer einen Bonus für erfolgreiche Mitwirkung in den Übungen.
Über den Bonus, den Sie bekommen, dadurch, dass Sie sich intensiv mit
dem Stoff beschäftigen, können Sie noch einen weiteren Bonus bekommen,
dadurch, dass Sie erfolgreich mitgewirkt haben in den Übungen,
mindestens 60 Punkte erreicht haben von mindestens 4 Übungsblättern.
Das heißt, Sie sollen nicht nach 3 Übungsblättern mit jeweils 20
Punkten aufhören und sagen, der Rest interessiert mich nicht, sondern
wir möchten schon, dass Sie mindestens 4 Mal abgegeben haben,
möglichst natürlich 5 Mal, und dabei dann insgesamt mindestens 60
Punkte erreicht haben.
Dann bekommen Sie den Bonus von einer Notenstufe, also ein bisschen
anderes System, als Sie das aus anderen Vorlesungen kennen, wo wir
eine Bonusklausur machen, wo auch die erfolgreiche Mitwirkung an den
Übungen im Prinzip abgeprüft wird, aber hier eben über die Korrektur
der Aufgaben.
Es wird auch Übungen geben, die ein bisschen praktischer sind, also
mindestens eine, eventuell zwei Programmieraufgaben werden dabei sein.
Das werden Sie alles in den Übungen dann erfahren.
Und die wesentlichen Informationen finden Sie alle im
Vorlesungsarbeitsbereich beziehungsweise in dem Portal Iliads.
Gibt es zu diesen Punkten irgendwie Rückfragen oder ist alles soweit
klar?
Sie haben eine Frage.
Das sind zwei Blöcke, das ist eine Wiederholung der gleichen Übung,
nur unterschiedliche Tutoren natürlich.
Oder haben wir einen Tutor?
Einen Tutor.
Ist das beidesmal der gleiche Tutor dann?
Okay.
Also, das ist dann der Unterschied.
Noch eine Frage.
Die sind schon online.
Der Kurs ist auch offen.
Der sollte offen sein.
Bitte?
Das gibt es doch nicht.
Herr Braun.
Aber sofort.
Da hatten wir...
Neulich war der Link auch gar nicht da.
Aber das ist ja ein Ding, dass der nicht offen ist.
Der wird sofort offen gemacht.
Also das ist doch klar.
Ich ging davon aus, dass alles offen ist.
Wie gesagt, wir sind dabei, das umzustellen.
Wir waren bisher auf dem Studierendenportal.
In den anderen Vorlesungen war das schon im letzten Semester erfolgt.
Dann ist da irgendein Häkchen vergessen worden.
Das muss man irgendwo beim Anlegen aufmachen, dass da der Beitritt,
also Anmeldung ermöglicht ist.
Das tut mir leid.
Aber das wird korrigiert.
Es stehen die Folien, die ich heute und nächstes Mal vorstelle, die
stehen schon drauf.
Also das ist schon da.
Noch eine Frage.
Nicht der Fall.
Zielgruppen.
Wer ist hier Wirtschaftsingenieur?
Fast alle.
Wer ist kein Wirtschaftsingenieur?
Was sind Sie?
Informationswirt?
Informatiker?
Wie können Sie die Vorlesung als Informatiker mit anrechnen?
Gar nicht?
Ja, nur heute.
Oder wollen Sie noch länger?
Sie können gerne auch länger dabei sein.
Ich freue mich drüber.
Denn so eine Vorlesung dieser Art wird Ihnen in der Informatik nicht
angeboten.
Die Themen werden zum Teil in anderen Vorlesungen angeboten, aber eine
ganze Reihe Themen finden Sie nur hier bei mir.
Also insofern ist das sehr interessant für einen Informatiker, das
auch mitzumachen.
Dann waren noch ein paar andere.
Wer war noch nicht Wirtschaftsingenieur?
Informationswirt war einer.
Und noch jemand, der was anderes ist?
Niemand.
Dann auch kein Wirtschaftsmathematiker.
Und so weiter.
Können noch andere Leute sein.
Inhaltsübersicht.
Hier sehen Sie eine ganze Reihe von Themen, die für einen Informatiker
zum Teil schon abgehandelt sind, aber auch nur zum Teil.
Das wird zum Teil in Informatik 2 gemacht.
Hier geht es also zunächst einmal darum, dass wir uns darüber
unterhalten, wie man überhaupt Algorithmen bewertet.
Was es eigentlich heißt, Algorithmen zu entwickeln.
Da geht es um alle möglichen Probleme.
Bisschen Rekurrenzbleichungen, Sortieren, Suchprobleme, Graphprobleme,
geometrische Probleme, verteilte Algorithmen und eine Zusammenfassung
am Ende.
Das kommt so insgesamt auf so 12 bis 14 Vorlesungsstunden hin.
Und das sind maximal 14 Termine, einschließlich Dienstag nach
Pfingsten.
Der ist nicht frei, sondern da halte ich die Vorlesung.
Am 19.05.
muss ich sehen, wie ich das mache.
Da bin ich nicht da.
Da wird die Vorlesung entweder als aufgezeichnete Vorlesung Ihnen
bereitgestellt aus dem Vorjahr oder wir lassen den einen Termin
einfach ausfallen.
Das muss ich noch entscheiden, je nachdem, wie ich mit dem Stoff
vorankomme.
Das kann ich aber gleich rein...
Ich kann das...
Ich werde Ihnen das später noch einmal mitteilen.
Literatur gibt es wahnsinnig viel zu dieser Thematik, zu effizienten
Algorithmen.
Ich habe hier eine ganze Reihe Sachen aufgeführt, wo Sie schon sehen,
es geht hier nicht um so klassische Einführung effizienter
Algorithmen, sondern es fängt hier gleich an mit dem Buch von Erkel
über Design and the Lasers of Parallel Algorithms.
Also parallele Algorithmen spielen hier eine große Rolle.
Ich lege Wert auf parallele Algorithmen, parallele Rechnerstrukturen.
Und dieses Buch von Borodin-Monroe ist ein Buch, das sehr stark den
Aufbau dieser Vorlesung beeinflusst hat.
Ich habe bei dem selber Vorlesungen gehört, bei dem Ian Monroe vor
langer Zeit und fand das eine sehr sinnvolle Art, das aufzubauen.
Deswegen fange ich auch immer mit den algebraischen Problemen an.
Häufig wird mit Such- und Sortierproblemen angefangen.
Ich mache das auf diese Art und Weise.
Dann gibt es ein sehr schönes Buch von Sedgwick, der hat viele Bücher
geschrieben über Algorithmen, Standardwerk, gibt es in immer neuen
Auflagen.
Der schreibt in einer sehr interessanten Art und Weise, sehr
anwendungsorientiert.
Und gibt es also auf viele verschiedene Arten, auch für verschiedene
Sprachen, ein gutes Buch, das man sich angucken kann.
Donald Knuth hat in seiner Reihe von Büchern, The Art of Computer
Programming, eigentlich das Standardwerk international für Algorithmen
geschrieben.
Sehr umfangreich, sehr ausführlich, ist ein bisschen alt, aber er hat
dort wirklich sehr, sehr viele Standardalgorithmen aufgeführt.
Und das ist also wert, da mal reinzugucken.
Dann gibt es hier die Bücher aus, einige Standardbücher aus
Deutschland, von Mehlhorn, Datenstrukturen und effiziente Algorithmen.
Ottmann, Wittmeier, Algorithmen und Datenstrukturen.
Die machen aber nur sequenzielle Algorithmen.
Korman, Leisers & Rivest ist auch ein internationales Standardwerk für
Algorithmen.
Introduction to Algorithms, gibt es auch immer in neuen Auflagen.
Ein dickes Buch, sehr wertvoll.
Das ist eigentlich international mittlerweile neben Donald Knuth, der
mehr so ein Repository ist für Algorithmen, ist Korman, Leisers &
Rivest eigentlich das Standardwerk für Einführung in Algorithmen.
Die wird sich in einer großen Bandbreite abdeckt.
Dann hier Hans-Werner Lang, Algorithmen in Java, auch ein nettes Buch.
Dann David Harrell, Algorithmics, ist ein besonderes Buch.
David Harrell schreibt nämlich dort über Algorithmen in einer Art,
dass man Ideen bekommt.
Er versucht zu vermitteln, welche Ideen und Motivationen hinter
bestimmten Algorithmen stecken.
Und das ist eigentlich sehr interessant zu lesen.
Das ist eigentlich mehr so ein beschreibendes Buch, auch sehr viele
formale Dinge drin, aber es ist nett zu lesen, dass er das beschreibt,
die Algorithmen das in einer ganz anderen Art und Weise, als es zum
Beispiel Leisers & Rivest machen.
Und dann gibt es noch eine ganze Reihe weiterer Sachen, eine ganze
Reihe Bücher über parallele Algorithmen, über insbesondere hier etwas
auch von SY-Kung, VLSI Array Processors, speziell für gitterverbundene
Rechner, Reihe oder viele Algorithmen für Mesh-Connected Arrays.
Das ist im Prinzip etwas, was wir heutzutage auf Many-Core oder Multi
-Core -Architekturen zur Verfügung haben.
Sie sehen ja an den Jahreszahlen relativ alte Bücher, aber die sind
immer noch bezüglich der Algorithmen sehr aktuell.
Dann haben wir hier von Leighton ein interessantes Buch über
Introduction to Parallel Algorithms and Architectures, Arrays, Trees,
Hypercubes, ein paar Dinge.
Daraus werden Sie auch kennenlernen.
Und von mir finden Sie auch ein Buch über VLSI-Algorithmen, da geht es
um Algorithmen, die man direkt in Hardware implementiert.
Sie finden etwas von Herrn Vollmer über Modelle der
Parallelverarbeitung usw.
Am Ende hier zehntner Entwurf systolischer Systeme.
Da geht es darum, wie Sie aus mathematischen Beschreibungen von
Problemen, meinetwegen Matrix-Multiplikation oder Matrix-Vector
-Multiplikation oder im Wesentlichen solche Algorithmen, die Sie
meinetwegen über mehrfach geschachtelte Schleifen in Programmen
formulieren, also iterative Algorithmen oder eben auch Probleme, die
Sie in rekursiven Gleichungen beschreiben können, also mathematisch
definierte Probleme, wie Sie die systematisch abbilden können auf
parallele Algorithmen, auf unterschiedliche Architekturen durch
mathematische Transformationen.
Da werden also auch über mathematische Transformationen Algorithmen
erzeugt und insofern sind dort sehr wichtige Konzepte drin für den
systematischen Entwurf, automatisierten Entwurf von parallelen
Algorithmen zur Ausnutzung der verfügbaren parallelen Infrastrukturen.
Okay, es gibt viele weitere Bücher, ich habe das nicht aktualisiert,
jetzt mit neuen Auflagen und Ähnlichem, aber es ist einfach ein
Gebiet, in dem sehr viele Autoren sich tummeln und es ist halt eines
der Kerngebiete der Informatik, auch sehr relevant für
Wirtschaftsingenieure, weil es ja bei Wirtschaftsingenieuren darum
geht, Ressourcen bestmöglich einzusetzen für den Zweck, für den sie da
sind.
Und das machen wir halt bei effizienten Algorithmen.
Okay, das ist schon alles zur Organisation, zur Einführung, also zu
den ersten Dingen, die ich erzählen wollte und jetzt kann ich schon
beginnen mit dem ersten Kapitel.
Sie dürfen gerne zwischendurch nochmal wieder Fragen stellen.
Sie dürfen sowieso ständig zwischendurch Fragen stellen, wenn Sie das
möchten.
Gibt es Fragen nochmal zum Organisatorischen?
Nicht der Fall.
Gut, dann machen wir es gleich hier weiter.
Wir kommen also jetzt zur Einführung und ich habe hier nochmal kurz
zitiert, folgendes Kommentar, das steht eigentlich drin, was die
Motivation ist.
Es geht um den Entwurf möglichst kostengünstiger Systeme.
Das machen Wirtschaftsingenieure, Informationswirte, Informatiker
natürlich auch.
Und was ich hier mache ist, dass ich für eine Reihe von
Standardaufgaben, Informationsverarbeitung, Algorithmen präsentiere
mit Bezug auf unterschiedliche Rechnerstrukturen.
Wir haben unterschiedlichste Arten von Rechnungsressourcen zur
Verfügung und sollten die bestmöglich einsetzen können.
Und deswegen lege ich immer Wert darauf, dass man sich anschaut für
bestimmte Probleme, wie mache ich das auf einer Einprozessoranlage,
Mehrprozessor oder sogar direkt in Hardware.
Okay, das ist also diese Motivation.
Die kennen Sie aus dem Votersens-Verzeichnis.
Und lassen Sie mich kurz darauf eingehen, welche Standardaufgaben wir
für die Informationsverarbeitung eigentlich haben, mit denen man sich
beschäftigen müsste.
Es gibt viele technisch-wissenschaftliche Berechnungen, Simulationen.
Wenn Sie
irgendwelche Stabilität von Fahrzeugen untersuchen wollen, wollen Sie
nicht gerne die Fahrzeuge direkt ineinander krachen lassen, sondern
wollen das simulieren.
Dazu müssen Sie also Dinge simulieren können.
Irgendwelche technischen Systeme.
Sie wollen Dinge visualisieren können.
Sie wollen virtuellen Entwurf machen von irgendwelchen schönen
technischen Objekten.
Sie wollen Systeme optimieren oder auch steuern.
Dann gibt es die kommerziell-betriebswirtschaftlichen Anwendungen,
Datenverwaltung, Erhebung, Suche, wobei wir hier heutzutage ja schon
jetzt als besonders buzzword heute oft von Big Data oder Smart Data
sprechen.
Also auch Data Analytics hat damit sehr viel zu tun, dass wir in der
Lage sind, Informationen aus großen Datenmengen zu bekommen.
Statistiken machen über irgendwelche großen Datenmengen, ist ein
typisches betriebswirtschaftliches Thema.
Wissensextraktion, auch hier Visualisierung von Datenräumen, ist ein
ganz wichtiges Thema.
Wie finde ich mich eigentlich zurecht in solchen Datenmengen?
Gibt es vielfältige Anwendungen dafür.
Kommunikation auch wichtige Aufgabe der Informationsverarbeitung.
Wie kann ich eigentlich sinnvoll Informationen strukturieren?
Wie kann ich Dinge grafisch machen?
Sie müssen schon wieder gehen.
Ja, okay.
Grafische Datenverarbeitung ist wichtig.
Sicherheitsmechanismen.
Sicherheit ist ein Thema, das immer wichtiger wird in allen Aspekten
der Informationsverarbeitung.
Wir haben heute das Stichwort Cybersecurity.
Wird im Augenblick an allen möglichen Stellen behandelt, auch hier
beim KIT.
Wir haben das Kompetenzzentrum für angewandte Sicherheitstechnologien,
Castell.
Also Sicherheit, vielfältig vernetzter System, ist ein ganz wichtiges
Thema.
Wie macht man das Ganze?
Was für Operationen brauchen wir?
Zum Beispiel Finite Element Methoden.
Wo braucht man die?
Das sind Methoden, um zum Beispiel irgendwas zu simulieren.
Stellen Sie sich vor, Sie wollen eine Tragfläche simulieren und sehen,
wie dort die Strömungsverhältnisse sind.
Dazu müssen Sie so eine Oberfläche simulieren können.
Das heißt, Sie legen dann zum Beispiel irgendwelche Gitter da drauf.
Häufig sind das irgendwelche Triangulationen.
Also irgendeine Gitterstruktur und Sie haben die ganze Oberfläche
dadurch im Prinzip digitalisiert.
Und Finite Element Methoden, weil Sie das Verhalten an einem
bestimmten Punkt ermitteln können, dadurch, dass Sie endlich viele
Elemente in der Umgebung sich anschauen, also eine begrenzte Zahl von
benachbarten Punkten und das Zusammenwirken der Informationen auf
diesen verschiedenen Punkten gibt Ihnen dann die Effekte, die Sie auf
der gesamten Tragfläche in dem Fall gerne haben möchten.
Also Finite Element Methoden sind ein ganz wichtiges Werkzeug für den
Ingenieur, der irgendwelche interessanten Bauteile entwickeln und
bewerten möchte.
Also dann hier, Multiplikation von Matrizen und Vektoren.
Standardaufgabe, die braucht man an allen möglichen Stellen, wenn Sie
irgendwelche Gleichungssysteme bearbeiten wollen.
Also Matrizenmultiplikation ist der Benchmark für Leistungsfähigkeit
von Rechnern, weil also Matrizmultiplikation in der einfachen Art und
Weise hat kubischen Aufwand.
n hoch 3, wenn Sie n kreuz n Matrizen haben.
Das dauert sehr lange, wenn Sie Matrizen nicht haben.
Man kann versuchen, das möglichst stark zu beschleunigen.
Und die Leistungsfähigkeit von Rechnern, wie gesagt, wird oft daran
gemessen, wie gut sind die in der Lage, Matrizmultiplikation
auszuführen.
Einfach weil diese Matrizmultiplikationen auftauchen in ganz, ganz
vielen ingenieurwissenschaftlichen, technisch-wissenschaftlichen
Aufgabenstellungen.
Genauso Approximation von Funktionen, auch wichtig.
Auswertung von Polynomen.
Wenn Sie eine Funktion approximieren, wird das häufig durch ein
Polynom gemacht.
Dann müssen Sie das an vielen Stellen auswerten können.
Das heißt, Sie müssen das möglichst effizient machen können.
Sie müssen auf Daten zugreifen können.
Sie wollen Informationen suchen.
Sie wollen Sachen sortieren.
Sie wollen vielleicht Wege suchen in Graphen.
Diese ganzen Fragen der Navigation in großen Netzwerken.
Die Navis in unseren Autos sind üblicherweise nicht gerade sehr...
oder viele sind nicht intelligent, weil sie häufig den Effekt haben,
sie haben eine Route ausgerechnet oder sich dafür entschieden und dann
weichen sie als Fahrer davon ab und die einfachen Systeme, die
versuchen, sie auf den kürzesten Wege zurückzubringen zu dieser vorher
berechneten Route und nicht von einem neuen Punkt aus die bestmögliche
Verbindung zu suchen, weil das nämlich zu aufwendig ist.
Hier am KIT sind Verfahren entwickelt worden, wie man das deutlich
effizienter machen kann, besser machen kann, dass man tatsächlich
immer auch bei Abweichungen von dem vorgegebenen Pfad dann wieder
optimale Lösungen findet.
Und das ist also ein ganz wichtiges Thema, die Wegesuche in Grafen in
einer möglichst effizienten Art und Weise, um kürzeste Wege zu finden.
Das ist ein Thema, bei dem man gerade bei großen Grafen eben noch
einiges algorithmisch machen kann.
Wo hier auch gerade am KIT sehr viel gemacht wurde, insbesondere von
den Kollegen Sanders und Wagner.
Darstellung von Grafen, auch ein wichtiges Thema.
Sie wollen so typische Darstellungen.
Sie haben eine Linie oder so etwas und Sie haben eine Reihe von
Strecken oder eine Reihe von Stationen.
Sie können das einfach als Folge von Stationen aufmalen und dann
wissen Sie, wie Ihre Linie ist, also wie die fährt.
Will man aber häufig so nicht haben, sondern Sie möchten irgendwie das
so angeordnet haben, dass Sie sehen, auch geometrisch zugeordnet, wo
läuft diese Linie eigentlich längs?
Welche Strecke dauert wie lange?
Sie wollen also die Entfernung irgendwie sinnvoll darstellen können.
Sie wollen eigentlich eher irgendetwas haben, was vielleicht so
irgendwie eine Struktur einer Stadt auch widerspiegelt.
Es gibt sehr interessante Darstellungen von Netzplänen vom
öffentlichen Nahverkehr, unter unterschiedlichen Anforderungen
gezeichnet.
Also eine Aufgabe, bei der es geht, Grafen sinnvoll zu visualisieren.
Auch ein interessantes Thema.
Grafvisualisierung oder Grafzeichnen werde ich hier nicht machen in
der Vorlesung, aber ich will nur einfach darstellen, was es alles für
interessante Probleme gibt.
Operation auf geometrischen Objekten.
Ich hatte schon kurz erwähnt, dass man gerne rausfinden oder in der
Lage sein möchte, festzustellen, wenn ich eine Reihe von Linien habe,
welche überschneiden sich an welchen Punkten, das möglichst effizient
zu machen.
Das hat vor vielen Jahren hier Ottmann und Bentley haben da den
Standardalgorithmus entwickelt, um mit einem sogenannten Besenansatz
hier von links nach rechts darüber zu laufen und immer zu gucken an
den interessanten Punkten.
Was passiert da gerade?
Das ist eine Reduktion des Suchraumes auf eine kleinere Dimension.
Von einem zweidimensionalen Problem reduziert man das auf ein Problem,
das man auf diesem Besen löst, den man sukzessive rüberschiebt.
Das werden Sie am Ende der Vorlesung auch noch erleben.
Also ein algorithmisch interessanter Ansatz.
Dann, was gibt es für typische Probleme in algorithmischer Geometrie?
Zum Beispiel könnte es sein, dass Sie meinetwegen ein Gebäude
überwachen wollen.
Es gibt Galerien, die haben manchmal etwas komische Formen und jetzt
könnte es sein, dass Sie die so angeordnet haben.
Es gibt solche Museen oder Ähnliches, die seltsame Geometrien haben.
Überlegen Sie sich, Sie wollen das gerne überwachen.
Das ist da eine typische Aufgabe.
Wie kann ich eine solche Struktur überwachen, sodass ich jeden Punkt
des Inneren tatsächlich sehen kann?
Also wenn ich hier eine Kamera hinstelle, was kann ich denn alles
sehen?
Da kann ich den Bereich nicht sehen.
Dann muss ich da vielleicht auch noch eine Kamera haben.
Ich könnte sie aber auch hier platzieren.
An dieser Stelle.
Und ich könnte dort eine Kamera haben.
Ich könnte vielleicht dort noch eine haben.
Also die Frage, an welchen Stellen muss ich Kameras platzieren, damit
ich einen Raum vollständig überwachen kann, ist eine interessante
Frage.
Typische Frage der algorithmischen Geometrie.
Es gibt ein dickes Buch über Galerie-Probleme.
Wo also solche Typen von Problemen behandelt werden.
Wir werden das Galerie-Problem nicht behandeln.
Ich werde Ihnen aber auf jeden Fall dieses Problem hier behandeln.
Nicht nachher, sondern am Ende der Vorlesung.
Das ist das letzte Kapitel.
Und ich werde Ihnen auch Dinge zeigen, wenn Sie also meinetwegen eine
Menge von Punkten haben.
Und Sie interessieren sich dafür, wo liegen eigentlich die Extreme?
Das ist etwas, was Sie in der Optimierung manchmal brauchen.
Dass Sie die konvexe Hülle einer Menge von Punkten brauchen.
Dafür zeige ich Ihnen eine ganze Reihe unterschiedlicher Algorithmen.
Also, vielfältige Probleme, die zu behandeln sind.
Vielfältige Operationen, die üblicherweise eingesetzt werden.
Und es ist die Frage, was für Operationen brauche ich eigentlich, um
solche geometrischen Probleme zu bearbeiten?
Brauche ich da Zirkel und Lineal?
Der Rechner hat leider kein Zirkel und Lineal zur Verfügung.
Das wäre schön, wenn er das hätte.
Dann wäre es ein Analogrechner.
Den haben wir aber nicht, sondern der ist digital.
Und dann müssen wir halt mit anderen Operationen arbeiten.
Wie macht man das eigentlich?
Das ist also dann die interessante Frage, wie man effizient
geometrische Operationen ausführen kann.
Okay.
Das ist also die typische Problemstellung.
Dann welche Anforderungen haben wir eigentlich, wenn wir davon reden,
dass wir möglichst kostengünstig, möglichst effizient die Ressourcen
nutzen wollen?
Das erste, was einem einfällt, ist geringer Zeitbedarf pro Aufgabe.
Das zählen verschiedene Dinge zu.
Eine Sache ist natürlich der Entwurfsaufwand.
Wenn Sie viele Probleme lösen müssen, wollen Sie wenig Zeit in den
Entwurf der Lösungen investieren, wollen das möglichst systematisch
machen.
Das andere ist, Sie wollen eine Aufgabe häufig ausführen.
Dann muss der Aufwand für die Ausführung der Aufgabe klein sein.
Also möglichst schnell eine Aufgabe lösen.
Also wenn Sie hier sich die Zeit angucken, Zeitachse und ein Problem,
das soll also die Zeitspanne für die Ausführung einer Aufgabe
möglichst kurz sein.
Es kann aber auch sein, dass Sie sagen, es kommt im Wesentlichen auf
den Durchsatz an.
Und der Durchsatz könnte ja auch darin bestehen, dass Sie viele
Aufgaben parallel ausführen können.
Und dann hätten Sie beim, wenn Sie den Durchsatz anschauen, wäre das
also die Anzahl der Aufgaben, die Sie pro Zeiteinheit ausführen
können.
Und die kann halt höher als 1 sein oder größer sein, wenn Sie
Pipelining -Verfahren zur Verfügung haben.
Also bei Hardware-basierten Algorithmen können Sie Pipelining machen
und dann haben Sie die Möglichkeit, etwas mit einem hohen Durchsatz zu
bearbeiten.
Sie kennen das alle aus der jeden Tag, wenn Sie Fernsehen,
hochauflösendes Fernsehen, arbeitet, im Pipelining-Verfahren, da
werden sehr viele Frames pro Sekunde bearbeitet mit einem hohen
Durchsatz in der Frequenz, mit der die Bilder dargestellt werden
müssen.
Aber die Bearbeitung der einzelnen Frames dauert natürlich eine
gewisse Zeit.
Und das wird genau auf diese Art und Weise gemacht.
Sie kennen das daraus, dass Sie manchmal, wenn Sie ein wirklich
hochauflösendes Fernsehbild haben, dass Sie etwas später das Tor
sehen, das in einem dummen Fernseher schon viel früher gezeigt wurde.
Weil halt erstmal noch die einzelnen Frames bearbeitet werden mussten.
Sie sehen nicht ein ruckelndes Bild, weil jeder Frame lange bearbeitet
wird, sondern Sie sehen mit einer hohen Frequenz die richtig
bearbeiteten Bilder.
Zum Beispiel auch in Übertragungen aus Sportstadien sehen Sie immer
schöne Werbung.
Das ist für jedes Land, für jeden Empfängerkreis entsprechend so
gemacht, dass Sie in jedem Land die richtige Werbung sehen.
Das ist nicht die Werbung, die im Stadion ist, sondern die wird
reingerechnet.
Und wird also erst bei der Präsentation dann tatsächlich erzeugt und
dann dargestellt.
Und auf die Art und Weise ist man in der Lage, eben sehr flexibel
Liveaufnahmen zu machen, auf denen nicht das drauf ist, was
tatsächlich live gesehen wurde, aber etwas, was für die Zielgruppe
sinnvoll ist.
Und das dauert eben ein bisschen, aber man macht das mit der
geeigneten Frequenz.
Und das geht nur so, weil man mit hohem Einsatz von Parallelrechnern
sehr stark Pipelining machen kann und einen hohen Durchsatz erzielt.
Also Anzahlaufgaben pro Zeiteinheit ganz wichtig bei
Signalverarbeitungsaufgaben.
Anderer Punkt ist wenig Speicherplatz.
Manchmal fragt man sich, wieso wenig Speicherplatz?
Speicherplatz ist so billig geworden.
Trotzdem wissen wir, dass je billiger der Speicherplatz wird, desto
größer werden die Anforderungen der Softwarepakete.
Die brauchen den Speicherplatz immer sofort und das ist schon gut,
wenn man das möglichst effizient machen kann.
Aber trotzdem, also Zeitbedarf ist normalerweise schon das Wichtigere
für uns.
Wenige Berechnungseinheiten ist durchaus auch wichtig, wobei man sich
darüber im Klaren sein muss, wenn wir Multicore und Minicore
-Architekturen haben mit wirklich zukünftig hunderten von Rechnern auf
einem Chip, dann haben wir ein Überangebot an Rechenkapazität und
können sehen, wie wir dieses Überangebot eigentlich bestmöglich
einsetzen können.
Dann ist die Anzahl der CPUs nicht mehr unbedingt ein begrenzender
Faktor.
Es kann aber sein, dass wir einen anderen begrenzenden Faktor haben,
nämlich wir wollen möglichst wenig Energie verbrauchen.
Und Energieverbrauch für Informationsverarbeitung ist durchaus
signifikant heutzutage.
Das ist also ein paar Prozent des Weltenergieverbrauchs mit steigender
Tendenz.
Wobei es interessant ist zu sehen, wie sich das tatsächlich
entwickelt.
Die einzelnen Rechner werden immer energieeffizienter, aber die Anzahl
der Rechner wird immer größer.
Deswegen ist der Gesamtenergieverbrauch für das Rechnen gar nicht so
stark verändert worden.
Aber wir haben eben so viele Anwendungen heutzutage, bei denen wir
Informationsverarbeitung brauchen, dass das schon ein signifikanter
Punkt ist.
Man muss aber auch schauen, ich habe ja einen Energieeinsatz für
Informationsverarbeitung.
Und wofür wird die Informationsverarbeitung genutzt?
Manchmal, hoffentlich häufig, wird sie dafür genutzt, um andere
Prozesse möglichst energieeffizient ausführen zu können.
Also zum Beispiel Energieverbrauch in einem Haus bestmöglich
einzustellen, macht man mit intelligentem Energiemanagement.
Informationsverarbeitung braucht Energie, aber sie sparen deutlich
mehr Energie ein, als sie einsetzen, um diese Einsparung zu erzielen.
Und insofern muss man genau gucken, wie bewerte ich den
Energieeinsatz, den ich dort habe.
Im Prinzip ist aber dieses Thema Energieeinsatz für
informationsverarbeitende Aufgaben ein Thema, das bisher nicht
wirklich im Vordergrund gestanden hat bei der Bewertung von
effizienten Algorithmen, oder von Algorithmen allgemein, sondern hat
man bisher überwiegend sich eigentlich auf Zeit und Platz beschränkt.
In letzter Zeit finden Sie auch öfter Ausführungen darüber, wie das
mit dem Energieeinsatz eigentlich aussieht.
Und das ist dann durchaus wichtig, wenn Sie ein großes Rechenzentrum
haben, wie kann ich dort eigentlich die Rechenlast modifizieren, so
dass der Energieverbrauch im Rechenzentrum angepasst wird, an das
aktuell verfügbare Angebot an Energie, zum Beispiel aus erneuerbaren
Quellen, wenn ich da irgendwelche Schwankungen habe, kann ich
entsprechend durch Steuerung meiner Berechnungen erreichen, dass ich
ähnliche Schwankungen im Verbrauch habe und darauf zumindest reagieren
kann.
Auch eine interessante Frage.
Wenige Nachrichten.
Was hat das mit Nachrichten zu tun?
Wenn Sie verteilte Berechnungen haben, müssen Sie Informationen, wenn
die gemeinsam eine Aufgabe bearbeiten wollen, dann müssen die
irgendwie Informationen austauschen können, entweder direkt durch
nächste Nachbarschaftsbeziehungen oder Sie haben irgendeine Menge von
Prozessoren, die nur irgendwie über ein Kommunikationsmedium verbunden
sind.
Dann ist die Zeit für die Ausführung der Berechnungen, wenn das eine
verteilte Berechnung ist, davon abhängig, wie schnell Sie die
Nachrichten austauschen können.
Und Sie wissen alle, wie lange es dauert, eine Nachricht zwischen zwei
Rechnern hin und her zu schicken, im Vergleich dazu, wie aufwendig es
ist, eine Rechenoperation im Rechner zu machen.
Die Nachricht hin und her zu schicken, die einfachste Nachricht wäre
ein Ping zwischen zwei Rechnern.
Kennen Sie alle, wenn Sie sowas mal austesten, ein Ping dauert immer
ein paar Millisekunden.
Also es ist auf jeden Fall ein Millisekundenbereich.
Sie können aber auf heutigen Rechnern mit mehreren Gigahertz
Bearbeitungsfrequenz oder Taktfrequenz, können Sie halt Millionen von
Operationen ausführen, während Sie ein Ping machen.
Und das heißt, man muss sehr genau überlegen, welche Aufgaben sind
eigentlich sinnvoll für verteilte Berechnungen und wo muss ich darauf
Wert legen, dass alles lokal gemacht wird, weil die Übertragungszeit
über die Kommunikationsmedien einfach zu lange dauert.
Insofern das ganze Thema Cloud Computing hat übrigens auch damit sehr
viel zu tun.
In bestimmten Anwendungen, wenn Sie Echtzeitanwendungen haben, macht
Cloud Computing wenig Sinn, weil bei Echtzeitanforderungen mit kurzen
oder mit sehr kleinen Grenzen für die erlaubte Zeit, da müssen Sie das
lokal machen.
Sie können nicht etwas erst mal übers Netz schicken.
Es gab mal irgendwo einen Vorschlag, man könnte ja ganz viele
Steuereinheiten aus den Autos im Prinzip vereinfachen, indem man die
wesentliche Funktionalität in die Cloud schiebt.
Also das Auto möchte ich nicht fahren, dass so etwas macht, aber da
werden einfach fundamentale Prinzipien einfach vernachlässigt.
Okay.
Insgesamt bestmögliche Nutzung der verfügbaren Ressourcen ist völlig
klar und natürlich zuverlässige Ausführung von Aufgaben.
Auch das ist wichtig, wenn Sie Störungen haben bei der Ausführung von
Aufgaben.
Komponenten fallen aus, insbesondere wenn Sie viele Komponenten
einsetzen und es fallen einige Komponenten aus.
Wie reagiert das Verfahren darauf?
Kann man damit umgehen?
Kommt trotzdem ein sinnvolles Ergebnis raus?
Also den Punkt werde ich hier nicht adressieren, obwohl er auch
wichtig ist, aber die anderen oben, die werden alle adressiert.
Dann kann ich analysieren, wie effizient ein Algorithmus ist und ich
kann das machen pro einzelner Aufgabe.
Also für sortieren, wie effizient kann ich sortieren meinetwegen, oder
wie effizient kann ich Matrizen multiplizieren, für die einzelne
Berechnung, für eine Gruppe von Berechnungen.
Ich habe viele Informationen zu machen.
Ich habe meinetwegen irgendwie gesagt, bei Matrix-Multiplikation muss
ich einzelne Operationen machen, wie Multiplikation von Zahlen.
Das können komplexe, ganze Zahlen, reelle Zahlen oder komplexe Zahlen
sein.
Wie hängt eigentlich die Ausführungszeit mit diesen einzelnen Zeiten
zusammen?
Gruppen von Berechnungen.
Ich mache viele Sortieraufgaben.
In der Signalverarbeitung muss ich häufig ganz viele Sortieraufgaben
lösen, wenn ich irgendwie Median- oder ich muss Median-Berechnungen
machen, um irgendwelche Ausreißer identifizieren zu können,
beziehungsweise um Informationen glätten zu können.
Da muss ich also sehen, wie kann ich eine Vielfalt von Berechnungen,
also so etwas, was ich hier angedeutet habe, wie ist der Gesamtaufwand
für die Ausführung einer Reihe von Berechnungen im Vergleich dazu der
Aufwand für eine Berechnung.
Pur genutzter Ressource.
Wie gut wird ein Rechner eigentlich ausgenutzt?
Oder ein Speicherplatz oder ähnliches.
Auch wichtige Analyse.
Brauche ich eigentlich die Ressourcen, die ich bereitgestellt habe?
Was passiert, wenn ich mich da einschränke, wenn ich all das
rausschmeiße, was nicht ständig genutzt wird?
Kann man sich vorstellen, dass da natürlich bei irgendwelchen
Spitzenlasten wieder Probleme auftauchen.
Das ist auch ein Punkt, den man sich angucken kann.
Dann wollen wir natürlich die Probleme durch Algorithmen lösen.
Jetzt geht es ein bisschen mehr in die Inhalte rein.
Sie kennen den Begriff aus den Einführungsvorlesungen über Informatik.
Intuitiver Algorithmusbegriff, ein endlich beschriebenes
deterministisches Verfahren mit Ein- und Ausgabe, das für alle
zulässigen Eingaben terminiert und dessen Operationen effektiv sind.
Da steht eigentlich alles drin.
Nicht ganz alles, aber es steht hier eben insbesondere drin, so die
wesentlichen Stichwörter.
Finitheit der Beschreibung, Effektivität der Operationen.
Das heißt, ich muss in endlicher Zeit den Algorithmus tatsächlich
lesen können.
Es müssen alle Operationen in endlicher Zeit ausgeführt werden können.
Es muss jede Operation oder jeder Algorithmus irgendwann enden.
es gibt natürlich auch, es gibt durchaus Algorithmen, bei denen ich
Wert drauf lege, dass sie nicht enden, dass sie dauernd weiterlaufen.
Mein Betriebssystem soll ständig laufen.
Es gibt durchaus Anwendungen, bei denen es wichtig ist, dass es etwas
dauerhaft tatsächlich laufen kann.
Aber das, was wir hier gerade eben alles angesprochen haben, da geht
es um Terminierung.
Dann Determiniertheit.
Da sehen Sie zwei Unterschiede.
Erstmal, hier steht Determiniertheit, da oben steht Deterministisch.
Deterministisch ist normalerweise so, dass jeder einzelne Schritt
genau vorgeschrieben ist.
Determiniert heißt nur, bei jeder Eingabe soll am Ende, wenn Sie eine
Eingabe mehrfach machen, soll immer die gleiche Ausgabe rauskommen.
Das ist etwas, was man standardmäßig so reinschreibt, aber es gibt
durchaus auch Anwendungen, bei denen es wichtig ist, dass man
randomisiert vorgehen kann.
Das heißt, dass Sie bei randomisierten Algorithmen, kann es passieren,
dass Sie nicht immer das gleiche Ergebnis kriegen.
Sie kennen viele Beispiele dafür.
Nehme ich an, Sie kennen vielleicht evolutionäre Algorithmen oder
überhaupt Metaheuristiken.
Ich mache mal hier einfach ein MH für Metaheuristiken, allgemeinerer
Begriff.
Die sind häufig randomisiert.
Optimierungsverfahren, bei denen Sie über einen randomisierten Prozess
Lösungen suchen in einem sehr großen Suchraum.
Und da bekommen Sie keineswegs bei jedem Lauf das gleiche Ergebnis,
sondern Sie wollen gerade bei unterschiedlichen Läufen auch
unterschiedliche Ergebnisse bekommen, weil Sie da nicht unbedingt das
Optimum finden, sondern Sie wollen möglichst gut da rankommen.
Und dafür wollen Sie den Lösungsraum möglichst breit untersuchen.
Und bei randomisierten Verfahren können Sie jedes Mal neue Lösungen
bekommen.
Und das ist auch gewünscht.
Also sofern, dieser klassische Begriff des Algorithmus ist ein
bisschen zu eingeschränkt gegenüber dem, was wir heutzutage machen.
Ein wichtiger Einsatz für randomisierte Algorithmen ist übrigens auch
der Einsatz für das Finden von großen
Primzahlen.
Das brauchen Sie, wenn Sie sicher kommunizieren wollen.
Dann brauchen Sie große Primzahlen, damit Sie in der Lage sind, ein
sicheres Paar von Schlüsseln zu erzeugen.
Insbesondere bei asymmetrischen Verfahren wie dem RSA-Verfahren oder
anderen in der Kryptographie.
Und da Sie, wenn es um Public Key Infrastrukturen geht, also
Infrastrukturen für öffentliche Schlüssel, da braucht man große
Primzahlen.
Und um festzustellen, ob eine große Zahl, also Zahlen mit mehreren
tausend Bits, ob die Primzahlen sind, kann man sehr effizient
randomisierte Testverfahren einsetzen.
Das war so der klassische erste Einsatz von randomisierten
Algorithmen, der sich sehr stark ausgebreitet hat.
Da könnte man auch eine ganze Vorlesung darüber halten und auch
mehrere über die Möglichkeiten, mit randomisierten Ansätzen Probleme
effizient zu lösen.
Das geht aber über die Vorlesung hier deutlich hinaus.
Wenn man es ein bisschen einfacher formuliert, ist ein Algorithmus
einfach nur die endliche Beschreibung der Ausführung einer endlichen
Folge von Befehlen auf einer abstrakten Maschine.
Das ist die Frage, was ist eine abstrakte Maschine?
Was ist ein Befehl?
Auch das muss man kennen.
Und wir müssen das ganz kurz uns angucken.
Das wird die nächste Vorlesungsstunde prägen, dass wir uns das genauer
angucken.
Und das, worauf ich hier Wert lege, ist anzugucken, die Einflüsse, die
Programmstrukturen haben auf die Algorithmen, beziehungsweise das, was
klassischerweise gemacht wird, ist Programmstrukturen anzuschauen,
Datenstrukturen, das ist so das übliche, Algorithmen und
Datenstrukturen.
Ich lege Wert darauf, auch die Rechnerstrukturen zu betrachten und
werde also, das ist im Wesentlichen unser Thema in dieser Vorlesung,
Programmstrukturen, Rechnerstrukturen, wie kann ich unterschiedliche
Rechner Infrastrukturen einsetzen für die Lösung von Problemen.
Die Datenstrukturen lasse ich ein bisschen raus, das ist Thema, also
klassisches Thema in so den üblichen Vorlesungen für effiziente
Algorithmen, auch sehr interessant, aber ich kann hier nicht alles
machen.
Gut, also, was für Strukturen haben wir?
Programmstruktur, Datenstruktur, Programmstrukturen sind eben je
nachdem, welche Arten von Sprachen sie haben, sehr unterschiedlich.
Sie können in algorithmischen Sprachen oder prozeduralen Sprachen
haben sie halt hier die Anweisungsfolgen, Verzweigung, Schleifen,
Prozedurfunktionsaufrufe und so weiter.
Dann haben sie in mehr objektorientierten Sprachen halt
Objektbeschreibungen, sie beschreiben Methoden, sie können bestimmte
Arten beschreiben, wie man mit Objekten umgeht, wie man mit Methoden
darauf zugreifen kann.
Das sind so die Möglichkeiten dort, also Programmstrukturen
aufzubauen, sie können Module erzeugen, können die miteinander
verbinden und ähnliches.
Bei Datenstrukturen gibt es viele verschiedene Strukturen, die man
dort klassischerweise einsetzt, Arrays, also Felder, Records, Listen,
Stacks, Queues, Bäume, also kennen sie alles, ein Heap kennen sie,
Heap ist ein spezieller Baum, bei dem sie noch eine Ordnungsstruktur
drauf haben, immer mit dem maximalen oder minimalen Element an der
Wurzel.
Das ist so klassisch, kennen sie aus der Anfängervorlesung.
Gridfile ist etwas, was man in der algorithmischen Geometrie einsetzt,
genauso ein Segmentbaum, auch in der algorithmischen Geometrie oder
für die algorithmische Geometrie entwickelt.
Skiptrees, spezielle Suchstrukturen, also es gibt eine Vielfalt von
Datenstrukturen, die bestimmte Aufgabenprofile dann besonders
unterstützen.
Ansonsten reden wir häufig von Interfaces oder Datenschnittstellen, um
für die Kommunikation zwischen unterschiedlichen Modulen festzulegen,
wie die Daten formuliert werden müssen, damit sie tatsächlich sinnvoll
Informationen austauschen können.
Das, worauf ich Wert lege, ist die Rechnerstruktur.
Befehlssatz, dazu gehört zunächst mal der Befehlssatz.
Also ein Intel-Rechner hat einen bestimmten Befehlssatz.
Andere Rechner haben andere Befehlssätze.
Es gibt unterschiedlichste Arten von Prozessoren, die unterschiedliche
Befehlssätze haben.
Hier der Befehlssatz prägt die Möglichkeiten, wie sie dort Algorithmen
formulieren können, wie sie ausgeführt werden.
Die Prozessorstruktur ist wichtig.
Wie viele Verarbeitungseinheiten habe ich?
Gibt es spezielle Gleitkomma-Operationen, spezielle Grafikprozessoren
und ähnliches?
Heutzutage können Sie viele Berechnungen beschleunigen, indem Sie die
GPUs, die Graphic Processing Units, sinnvoll einsetzen.
Das sind im Prinzip effiziente Parallelrechner mit einer bestimmten,
festgelegten Struktur.
Das spielt alles eine Rolle, die man ausnutzen muss bei der
bestmöglichen Nutzung der Ressourcen, die uns zur Verfügung stehen.
Verbindungsstrukturen, sagte ich schon, sind natürlich auch wichtig.
Man kann Rechner irgendwie linear anordnen oder man kann sie natürlich
auch irgendwie als Ring anordnen, man kann sie als Gitter anordnen,
das kennen Sie auch.
Oder können Sie sich vorstellen, wie sowas funktioniert, kann man noch
erweitern, kann alle Zeilen und Spalten jeweils, ups, auch die jeweils
durch sogenannte Wraparounds verbinden.
Dann haben Sie einen Torus und nicht nur Mesh Connected Array.
Sie können auch sagen, ich mache einen Hyperwürfel.
Was ist ein Hyperwürfel?
Ein beliebig dimensionaler Würfel.
Was ist ein eindimensionaler oder ein eindimensionaler Würfel?
Das ist ein nein, ein nulldimensionaler Würfel, das ist ein Punkt.
Wenn Sie einen eindimensionalen Würfel haben, dann haben Sie zwei
nulldimensionale Würfel, die Sie mit einer Linie verbinden, mit einer
Kante.
Wenn Sie einen zweidimensionalen Würfel haben, dann haben Sie im
Prinzip zwei eindimensionale Würfel und da werden korrespondierende
Punkte miteinander verbunden.
Das ist ein zweidimensionaler Würfel.
Was ist ein dreidimensionaler Würfel?
Sie brauchen zwei zweidimensionale Würfel und Sie müssen
korrespondierende Knoten miteinander verbinden.
Dann haben Sie einen dreidimensionalen Würfel.
Dann machen wir einen vierdimensionalen Würfel.
Wir brauchen zwei
zwei dreidimensionale Würfel und da waren die Punkte jeweils verbunden
und müssen korrespondierende Punkte miteinander verbinden.
So, und dann haben wir hier einen vierdimensionalen Würfel.
Jetzt können Sie das beliebig fortführen.
Sie haben also bei einem k-dimensionalen Würfel von jedem Punkt k
-Kanten, die rausgehen.
Wenn Sie also einen Hyperwürfel haben mit n Knoten, haben Sie einen
maximalen Weg zwischen zwei Punkten der Länge log n.
Das ist interessant.
Also ein k-dimensionaler Würfel hat zwei Hoch-K Elemente und insofern
ist das eine interessante Struktur, die sehr kurze Verbindungen hat
zwischen den einzelnen Punkten und eine sehr flexible Struktur.
Wichtige Verbindungsstruktur für Parallelrechner.
Das sind also Rechnerstrukturen, die man entsprechend bekommt, über
solche Verbindungsstrukturen.
Andere Verbindungsstrukturen, die übrigens auch wichtig sind, kurz
erwähnt vorher, steht hier jetzt gar nicht drin, eine
Verbindungsstruktur, die
das ist hier ein ach ja so das hier noch mal vier Punkte die muss ich
verbinden oder muss ich die Punkte hier noch mit den verbinden und die
mit den verbinden.
Dann habe ich ein kleines Butterfly-Netzwerk, Schmetterlingsnetzwerk.
Das ist die Struktur, hatte ich schon vorhin ganz kurz auf der ersten
Folie angedeutet, die man in der schnellen Folietransformation
verwendet.
Die hat eine nette Eigenschaft, wenn Sie das hier also beliebig größer
machen, mit diesem Prinzip, das ich gerade hier versucht habe
anzudeuten, dann können Sie von jedem Punkt auf der linken Seite zu
jedem Punkt auf der rechten Seite kommen, über einen Pfad in diesem
Netzwerk.
Und Sie können also eine beliebige Permutation durch diese Kanten
darstellen.
Das heißt, wenn Sie von irgendeiner Menge von Innenpunkten auf
irgendeinen anderen Punkt zugreifen wollen, können Sie das über ein
Schmetterlingsnetzwerk realisieren.
Das hat gewisse Schwachstellen, aber hat auch sehr viele Vorteile.
Ein sehr interessantes Netzwerk.
Noch interessanter wird es, wenn man die Verbindungsstrukturen hier
randomisiert, weil man dann noch ein bisschen bessere Eigenschaften
bekommt.
Da gehe ich aber später darauf ein.
Also Verbindungsstrukturen, auch ein interessantes Thema.
Und das ist ein Thema für parallele Rechner.
Hypercube habe ich Ihnen gerade vorgestellt.
Baumrechner ist klar.
Da haben Sie halt baumverbundene Rechner, die besonders gut geeignet
sind, um divide-and-conquer-Verfahren auszuführen.
Sie können gitterverbundene Rechner betrachten.
Torus habe ich hier oben angedeutet.
Das hier ist also ein Torus.
Sie können Mesh-of-Trees machen, war auf der Anfangsfolie drauf.
Multicore, Many-Core, da haben Sie im Prinzip beliebig viel, oder
nicht beliebig, aber sehr viele Rechner zur Verfügung auf einem Chip
und sollten diese einzelnen Rechnerkerne bestmöglich einsetzen.
Verbindungsstrukturen sind dort in der Regel einigermaßen flexibel,
auch virtuell dann zu realisieren.
Und Sie haben natürlich Rechnerstrukturen virtuell zur Verfügung über
die Rechnungen im Internet, irgendwo im Cloud, irgendwelche Anbieter
von Rechenressourcen.
Und wenn Sie damit umgehen wollen, effizient in Algorithmen, müssen
Sie wieder anders Ihre Algorithmen strukturieren, als wenn Sie das auf
einer PRAM machen oder auf einem Baumrechner oder was immer Sie hier
haben.
Und das zeigt, der Entwurf von Algorithmen ist nicht ganz so einfach,
wie wir das in der Anfängervorlesung zunächst mal Ihnen darstellen.
Man entwirft einfach ein schönes Verfahren, das man auf einem Rechner
ausführt.
Das ist der Algorithmus.
Also um ein Problem bestmöglich zu nutzen, müssen Sie immer sehen, auf
welche Infrastrukturen habe ich zur Verfügung, um diese Probleme
tatsächlich zu bearbeiten.
Und deswegen ist das ein sehr interessantes Thema, bei dem man sehr,
sehr viel sich anschauen kann.
Wir werden einen Ausschnitt davon bearbeiten.
Also, Entwurf und Analyse von Algorithmen, guckt sich verschiedene
Sachen an.
Der Entwurf, da gibt es alle möglichen Verfahren, die kennen Sie,
Divide and Conquer, Dynamic Programming, Branch and Bound Verfahren,
Branch and Cut könnte man noch erwähnen, Greedy Algorithmen, also
heuristische Verfahren, Scanline-Prinzip habe ich Ihnen kurz versucht
anzudeuten, das war dieses, um Schnittpunkte zwischen irgendwelchen
Linesegmenten zu finden.
MapReduce, ein Verfahren, das sehr populär ist oder gewesen ist, kann
man sagen, in letzter Zeit durch Google vor allen Dingen, sehr stark
propagiert worden.
MapReduce, da geht es darum, auf sehr großen Datenmengen oder auf sehr
großen Datenmengen Anfragen sinnvoll zu machen.
Typische Aufgabe, die man im Internet hat, wo man zunächst mal,
meinetwegen Sie wollen, aus einer großen Menge,
meinetwegen suchen Sie alle Studenten aus Karlsruhe, die an
irgendeiner Universität in Deutschland studieren.
Da brauchen Sie Informationen über alle Studenten, die an
irgendwelchen Universitäten studieren und dann bekommen Sie zunächst
mal von jeder Universität eine Liste von diesen Studierenden und dann
suchen Sie alle raus, die aus Karlsruhe kommen und wollen die noch
irgendwie nach Alter aufgelistet haben.
Das ist eine typische Aufgabe, wo Sie zunächst mal eine große
Datenmenge haben, dann extrahieren Sie daraus eine Reihe von
Teillösungen und Sie müssen anschließend noch wieder hier raus Dinge
zusammenfassen, um Ihre Lösung am Ende abliefern zu können.
Das ist dieses Map und Reduce, das sind wesentlich zwei Schritte.
Habe ich Ihnen jetzt sehr, sehr oberflächlich angedeutet, aber
wesentlich ist es also ein Map auf die relevanten Teildaten, die in
der Regel auf einzelnen Rechnern, einzelnen Rechnereinheiten abgelegt
werden und dann Reduce die richtigen Informationen tatsächlich
zusammenstellen, um das Ergebnis zu bekommen.
Das heißt, ich muss meine Aufgaben, die ich dann mit MapReduce
-Ansätzen bearbeite, in einer bestimmten Art und Weise strukturieren,
damit die wirklich dieses Prinzip bestmöglich unterstützen.
Das ist durchaus etwas, was nicht einfach ist, das sinnvoll zu machen.
Es gibt dafür einfache Oberflächen, die aber nicht immer bestmögliche
Resultate bringen.
Es gibt dafür auch spezielle Rechnerstrukturen oder Software
-Umgebungen, mit denen man das machen kann.
Hadoop ist ein solches Stichwort.
Das ist ein Software-Rahmenwerk, das auf Parallelrechnern gerade
solche MapReduce-Verfahren besonders unterstützt.
Ist aber in der aktuellen Literatur ist es so, dass man sagt,
MapReduce ist schon wieder nicht mehr aktuell, sondern man macht jetzt
noch wieder neue Verfahren, um auf sehr großen Datenmengen zu
arbeiten.
Aber Sie finden immer noch viele interessante Anwendungen von
MapReduce.
Das Nächste war hier, da bin ich noch nicht drauf eingegangen, die
Analyse von Algorithmen.
Hatte ich schon gesagt.
Die Zeit spielt eine Rolle, der Platz spielt eine Rolle, Anzahl
Prozessoren, die Fläche, was ist die Fläche eines Algorithmus?
Was kann die Fläche eines Algorithmus sein?
Also, stellen Sie sich vor, Sie haben einen Algorithmus, der ist
baumstrukturiert.
Ein Baum, das ist ja ganz einfach.
Ein Baum, das ist hier sowas, da habe ich hier so eine Struktur hier
ganz einfach angedeutet.
So, jetzt würde ich das auf dem Chip irgendwo platzieren.
Und ich möchte gerne, dass Sie jetzt sehen, dass es hier ganz schlecht
gezeichnet.
Ich möchte es auf dem Chip platzieren.
Auf dem Chip platzieren, so dass die Knoten alle am Rand liegen.
Dann will ich also die, also die Blätter alle am Rand, dann liegen die
hier also alle am Rand.
Ich mache hier mal ein paar hin.
Eins, zwei, drei, vier, fünf, sechs, sieben, acht.
So.
Und dann muss ich die hier irgendwie verbinden.
Und die muss ich auch irgendwie verbinden.
Die auch noch.
Und dann muss ich die natürlich auch verbinden.
Und dann muss ich die auch verbinden.
So.
Absquatsch.
Das war nix.
Das muss weg.
Die muss ich verbinden.
Und dann muss ich noch die beiden verbinden.
So, dann habe ich hier einen Baum gemalt.
Welche Fläche braucht denn so ein Baum?
Auf einem Chip, wenn ich das so anordnen will.
Naja, ich habe hier meinetwegen irgendwie N Knoten.
N Blätter.
Dann habe ich hier ist ein Baum.
Log N Schichten.
Also Fläche N, Log N.
Ich könnte es auch anders anordnen.
Ich könnte sagen, naja, ein Baum kann auch ich mal das mal ein
bisschen anders etwas kleiner auf.
Das hier ist auch ein Baum.
Da ist ein Knoten, da ist ein Knoten, da ist einer, da einer, da einer
und da einer.
Und ich kann noch so ein Haar dahinmalen und noch so ein Haar
dahinmalen und noch so ein Haar dahinmalen.
Und ich kann hier auch noch ein Haar reinmalen.
Und jedes Mal habe ich hier Verbindungsknoten drin.
Und meine Blätter sind natürlich nicht mehr am Rand angeordnet von
dieser Struktur, sondern sind in einem zweidimensionalen Feld
angeordnet.
Das ist eine sogenannte Haarbaum-Darstellung eines Baumes.
Und bei diesem Haarbaum-Layout sieht die Fläche ganz anders aus.
Wie viel Fläche brauche ich denn da?
Meine Blattknoten, die N-Blattknoten, sind gleichmäßig verteilt über
eine Fläche.
Das heißt, die Fläche ist linear, quadratisch angeordnet.
Ich habe also Wurzel N als Seitenlänge.
Die Fläche ist linear in der Anzahl der Blätter.
Und das, was wir hier vorher hatten, die ganze Fläche, diese Log-N
-Schichten, die haben wir hier integriert in den Platz, der sowieso da
ist.
Das heißt, hier hätten wir eine Fläche von O von N und hier oben
hatten wir eine Fläche von O von N Log-N.
Je nachdem, wie es sich darstellt, haben Sie völlig unterschiedliche
Flächenanforderungen.
Das heißt, auch wenn Sie sich vorstellen, Sie wollen von einer Reihe
von Prozessen aus mit anderen kommunizieren, dann müssen Sie irgendwie
jeden Knoten mit jedem anderen verbinden können.
Also im Prinzip brauchen Sie hier ein typisches, typische Struktur ist
so ein Crossbar, wo Sie irgendwelche Punkte miteinander verbinden
können, indem Sie Gitterpunkte schalten oder nicht schalten.
Die Fläche dafür, nur für die Leitungen, ist quadratisch in der Anzahl
der Punkte, die Sie verbinden wollen.
Das heißt, bei Fläche ist ganz wichtig, wie sieht eigentlich die
Kommunikationsstruktur aus und wie kann ich meine Struktur, die ich da
habe, bestmöglich anordnen.
In der Ebene, wenn ich eine zweidimensionale Struktur habe oder auch
in Dreidimension, wenn ich eine dreidimensionale Rechnerinfrastruktur
zur Verfügung habe.
Es gibt durchaus dreidimensionale Chip-Technologien, die allerdings
häufig nur eine begrenzte Anzahl von Schichten haben, aber es gibt in
etwas abstrakt oder etwas größerem Skalierung durchaus
dreidimensionale Anordnungen von Rechnern, wo das eine große Rolle
spielt.
Okay, das also zu den Dingen, das Ganze ist natürlich, das war die
Fläche, Volumen hatte ich schon gesagt, 3D, Kommunikationsbedarf hatte
ich auch darauf hingewiesen, Energie spielt mir mehr eine Rolle und
das Ganze ist abhängig von der Größe der Eingabe, in der Regel, und
wir gucken uns an das Verhalten im schlechtesten Fall und im Mittel.
Im schlechtesten Fall, dann weiß ich, was ich schlechtestmöglich an
Zeit investieren muss und im Mittel, das ist eben wichtig,
insbesondere, wenn ich eine große Anzahl von Berechnungen habe, was
ist der durchschnittliche Aufwand, den ich habe, dann weiß ich, was
ich insgesamt investieren muss.
Ist aber deutlich schwerer zu analysieren, weil ich dann wissen muss,
wie die einzelnen Eingaben oder die einzelnen Probleminstanzen
verteilt sind, ob das immer schwere Probleme sind oder eher leichte,
je nachdem verändert sich dann das mittlere Verhalten.
Also mittleres Verhalten geht nur in Bezug auf die Verteilung der
Berechnungsinstanzen.
Und wenn wir was fragen wollen über den Aufwand, dann müssen wir das
irgendwie formalisieren, jetzt kommen wir zu der Zeitkomplexität.
Also wie können wir das ein bisschen mehr formalisieren?
Wir haben ein Algorithmus mit einer bestimmten Eingabemenge, also
meinetwegen Sortierverfahren, Eingaben sind jeweils irgendwelche
Folgen, die sortiert werden sollen.
Und für jede Eingabe kriegen wir eine Größenangabe, also bei den
Sortierproblemen die Länge der Liste.
Und für jedes Problem sei also t a von x die Rechenzeit des
Algorithmus a bei Eingabe einer bestimmten zu sortierenden Liste zum
Beispiel.
Und dann ist die Zeitkomplexität im schlechtesten Fall gerade die
maximale Rechenzeit, die wir haben, für alle Eingaben einer bestimmten
Größe, also die Rechenzeit im schlechtesten Fall für Eingaben einer
Größe n ist dann entsprechend das Maximum über alle solche Eingaben.
Hier als Supremum angegeben muss ja nicht unbedingt eine endliche
Anzahl von möglichen Eingaben sein.
Das sind die typische Definitionen für Zeitkomplexität im
schlechtesten Fall.
Wenn wir eine Wahrscheinlichkeitsverteilung gegeben haben, dann muss
hier nicht das Supremum stehen, sondern dann steht hier halt einfach
der Erwartungswert über alle einzelnen Berechnungen für Eingaben der
Größe n.
Das ist die mittlere Zeitkomplexität.
Wir werden dazu auch ein paar Analysen machen von Algorithmen.
In der Regel schauen wir uns das allerdings an für nur im
schlechtesten Fall oder auch mal im besten Fall, der durchaus auch
manchmal interessant sein kann.
Für die anderen Komplexitätsmaße, Speicherplatz usw., können wir das
alles analog machen.
Dann haben Sie dort auch Komplexitätsmaße im schlechtesten Fall, im
mittel, im besten Fall usw.
Was ist das Ziel der Analyse?
Wir wollen etwas sagen über den Aufwand des Algorithmus, die Qualität
des Algorithmus.
Das kann ich nur machen, Qualitätsaussage, wenn ich irgendwas
vergleichen kann.
Das heißt, ich kann entweder zwei Algorithmen vergleichen und sagen,
der eine braucht mehr Zeit als der andere oder ich kann sagen, ich
habe eine Aussage darüber, wie viel Zeit ich mindestens brauche,
untere Schranke, für die Komplexität der Lösung des Problems, dann
weiß ich oder kann ich auch sagen, ein bestimmter Algorithmus ist
optimal.
Das ist natürlich toll, wenn ich sage, das geht nicht besser.
Also beim Sortieren wissen wir, untere Schranke ist nlogn und da
können wir auch genau nlogn im schlechtesten Fall erreichen.
Also können wir da optimale Algorithmen angeben, wobei es interessant
ist, für jede Problemgröße den wirklich optimalen Algorithmus zu
finden, der für eine bestimmte Problemgröße die minimale Anzahl von
Vergleichen braucht.
Interessantes Problem, das für jede Problemgröße anzugucken.
Die Verfahren sind ganz anders als die, die wir normalerweise als
optimale Verfahren für allgemeine Eingaben uns anschauen.
Es gibt andere Probleme, wie zum Beispiel Matrixmultiplikation, da
haben Sie eine triviale untere Schranke von n², wenn Sie n kreuz n
Matrixen betrachten.
Die bestmöglichen Verfahren, die wir kennen, die sind bei n hoch 2.35.
Das heißt, wir sind deutlich weg von der unteren Schranke.
Aber n hoch 2.35 ist signifikant besser als der klassische
Schulmethodenansatz, der n hoch 3 braucht.
Also da kann man durchaus Vergleich machen zwischen verschiedenen
Algorithmen.
Wir können aber, bis heute kennen wir keine Aussage über den optimalen
Algorithmus.
Da wissen wir nur, wir konnten es immer weiter runterdrücken.
Das werden Sie auch kennenlernen.
Sie werden nicht das Verfahren kennenlernen für n hoch 2.35, aber das
für n hoch 2.81, das ist der Strassenalgorithmus, ein klassischer
Algorithmus, der sehr viel Aufmerksamkeit bekommen hat, weil er den
klassischen Annahmen widerlegt hat, dass eigentlich sowas wie das
Gauss'sche Verfahren für die Lösung von Linienangleichungssystemen
optimal ist, was es eben nicht ist, wenn man effizient Matrizen
multiplizieren kann.
Vergleiche von Algorithmen.
Kurzes Beispiel.
Da muss man sich noch ein paar mehr Dinge anschauen.
Ich hatte ja gesagt, wir schauen uns an den Aufwand im schlechtesten
Fall für eine bestimmte Problemgröße.
Jetzt haben Sie in der Realität manchmal durchaus Einschränkungen für
die Problemgrößen, mit denen Sie es zu tun haben.
Also wenn Sie ein Verfahren haben, bei dem Sie sagen, die
Problemgrößen sind immer in einem bestimmten Spektrum, nur 127
Elemente in der zu sortierenden Liste, da können Sie Verfahren nehmen,
das dafür bestmöglich ist und das kann durchaus für andere Größen sehr
schlecht sein.
Hier ist ein typisches, so klassisches Beispiel für einen Vergleich
von vier Algorithmen, A1 bis A4, die sehr unterschiedliche Laufzeiten
haben.
Das erste Verfahren, angegeben hier in Millisekunden, brauche für
irgendein Problem 1000 n Millisekunden, also n die Problemgröße.
Das andere brauche 200 n log n, das nächste 10 n Quadrat und das
vierte 2 hoch n, exponentiell.
Würden Sie spontan sagen, natürlich nehme ich den linearen
Algorithmus.
Jetzt schauen Sie aber an, wie viel Rechenzeit Sie spendieren wollen,
um Probleme zu bearbeiten.
Jetzt sagen Sie, Sie haben eine Sekunde Rechenzeit zur Verfügung, wie
sieht die maximale Problemgröße aus, die Sie mit einer Sekunde
Rechenzeit bearbeiten können.
Sie stellen fest, das waren hier Millisekunden, diese Zeiteinheiten,
Sie haben hier verschiedene Konstanten davor, Sie stellen fest, dieses
Verfahren A1 kann nur Problemgröße 1 bearbeiten.
Das Verfahren A4 kann aber Problemgröße 9 bearbeiten, Verfahren A3
kann Problemgröße 10 bearbeiten, in einer Sekunde.
Gehen wir ein bisschen weiter, eine Minute, sieht das schon ganz
anders aus, aber auch hier ist es so, dass der lineare Algorithmus
Problemgröße 60 bearbeiten kann, A3 ist immer noch besser, kann bis zu
Problemgröße 77 gehen.
Das heißt, es macht durchaus Sinn, wenn Sie spezielle Problemgrößen
betrachten, sich genauer anzuschauen, wie sieht eigentlich die
konkrete Rechenzeit aus und nicht nur die asymptotische, bei der wir
häufig die Konstanten vergessen.
Die Konstanten spielen durchaus eine Rolle bei der Bewertung der
Effizienz von Verfahren und wenn Sie etwas für spezielle Anwendungen
machen, macht es Sinn, wirklich genauer reinzugucken.
Es ist völlig klar, dass dann bei großen Rechenzeiten natürlich das
lineare Verfahren das Bestmögliche ist und hier unten beim
Exponentiellen ist natürlich klar, da wächst die Problemgröße
natürlich nur sehr langsam, weil es einen exponentiellen Aufwand hat.
Optimal ist das exponentielle Verfahren trotzdem für sehr kleine
Problemgrößen.
Sobald Sie über 100 sind in der Problemgröße, ist das lineare
Verfahren das Beste und hier dieses mit NlogN ist nie optimal.
Das würden Sie also nie einsetzen.
Immer irgendeines der anderen.
Das also nur als kurzes Beispiel.
Jetzt könnte man sagen, das ist ja völlig fiktiv.
So etwas kommt doch gar nicht vor in der Praxis.
Und das ist durchaus nicht so fiktiv.
Also zunächst mal hier dieser Vergleich, das hatte ich gerade eben
schon angedeutet, für Problemgröße 10 sind also A4 und A3 etwa gleich
lang.
Für Problemgröße 25 ist der Algorithmus A4 also 5400 mal langsamer als
das Verfahren A3.
Das ist also klar.
Für großes N ist das Verhalten, oder das Verhalten für großes N ist
durchaus sehr wichtig.
Das Verhalten dieser Zwischenraum, der ist falsch.
Der kommt irgendwie durch die Darstellung von Formeln, die man in
Powerpoint setzt, auf der Folie manchmal zustande, dass dort irgendwie
Zwischenräume gesetzt werden, wo sie eigentlich gar nicht explizit
gewünscht waren.
Hier kommt jetzt ein Beispiel, bei dem man tatsächlich in der Praxis
so etwas sehen kann, wenn Sie ein Polynom auswerten wollen.
Ein typisches, einfaches Problem.
Wie macht man das eigentlich?
Was ist ein Polynom?
Summe i gleich 0 bis n a je x hoch i.
Also Sie haben ein a n x hoch n und so weiter bis a 0.
Und Sie müssen das jetzt irgendwie ausrechnen.
Wenn Sie das naiv machen, von links nach rechts, hier in dieser Art
und Weise, dass Sie ausrechnen, was passiert?
Sie rechnen hier a n mal x mal x mal x mal x bis Sie bis x hoch n
gekommen sind.
Dann rechnen Sie a n minus 1 mal x hoch n minus 1 und so weiter.
Und wenn Sie das dumm von links nach rechts machen, kommen Sie auf n
halbe mal n plus 1 Multiplikation und n Additionen.
Das sind hier die n Additionen da drin.
Aber Sie haben eben für jeden Term jeweils n, n minus 1, n minus 2 und
so weiter Multiplikationen, wenn Sie es dumm von links nach rechts
machen.
Wenn Sie es anders machen und das ein bisschen Gesetze der Arithmetik
hier verwenden, wissen Sie, Sie können das ja auch assoziativ hier
auseinander ziehen.
Dann rechnen Sie zunächst mal aus a n mal x plus a n minus 1.
Dann multiplizieren Sie mit x, dann addieren Sie a n minus 2,
multiplizieren mit x und so weiter.
Und was Sie hier brauchen, sind n Multiplikationen und n Additionen.
Einfach durch eine andere Darstellung dieses Polynoms.
Sie machen es hier nicht einfach dumm von links nach rechts, sondern
ein bisschen intelligenter.
Und machen das auf die Art und Weise, in dem Sie eben daraus eine
Klammerstruktur gemacht haben.
Und dazu müssen Sie aber wissen, dass man das machen darf in dieser
Art des Rechenraumes, wie wir den normalerweise kennen.
Und dann haben Sie n Multiplikationen und n Additionen.
Das ist tatsächlich optimal.
Kann man zeigen, man braucht genau n Multiplikationen und n
Additionen, wenn Sie ein beliebiges Polynom, dass Sie nichts anderes
wissen, als dass da irgendwelche Koeffizienten sind und der Grad n
ist, brauchen Sie genau n Multiplikationen und n Additionen.
Geht nicht besser.
Ein optimales Verfahren, bis auf die Konstant, also das geht wirklich
nicht besser.
Und das ist ein sehr einfaches Beispiel.
Wenn Sie es dumm machen, kommen Sie auf deutlich höhere Anzahl von
Operationen.
Asymptotischer Aufwand, hier natürlich sehr unterschiedlich, hatte ich
schon sehr deutlich gesagt.
Das obere Verfahren hätte quadratischen Aufwand, das untere linearen
Aufwand.
Und da muss man also genau aufpassen, was man tatsächlich macht.
Sie kennen das auch noch aus den Sortierverfahren, wo man eben auch
sehr unterschiedliche Aufwände hat.
Auch zum Teil bei Quicksort zum Beispiel, im schlechtesten Fall n², im
mittleren Fall n log n.
Und andere Verfahren, die im besten Fall linear sind beim Sortieren,
im schlechtesten Fall aber quadratisch.
Was nimmt man dann eigentlich?
Der Vergleich von Algorithmen ist nicht ganz so einfach.
Man muss genau wissen, was man eigentlich will.
Brauche ich ein Verfahren, das für beliebige Problemgrößen mir gute
Lösungen liefert?
Dann nehme ich vielleicht ein Verfahren, das asymptotisch am besten
ist, wie das lineare Verfahren unter der Annahme, die kleinen Probleme
tauchen nicht so oft auf.
Oder ich sage, ich habe meinetwegen für, wenn ich hier die
unterschiedlichen Problemgrößen mir anschaue, also hier die
Problemgröße n, dann habe ich vielleicht je nachdem, welche
Problemgröße ich habe, unterschiedliche, meinetwegen hier Algorithmen
a1, a2, a3, habe ich jeweils unterschiedliche Algorithmen, die ich
einsetze.
Das sind sogenannte Polyalgorithmen, wo sie je nachdem in welchem
Problemgrößenbereich sie sich befinden, verwenden sie andere
Algorithmen, die dann für den Bereich der Problemgrößen bestmöglich
sind.
Die guten Pakete, die sie, also wenn sie so meinetwegen ein MATLAB
oder so Standardfunktionen verwenden, die haben häufig solche
Polyalgorithmen implementiert.
Also die sind in der Regel schon recht gut gestaltet.
Jetzt rede ich ganze Zeit über das asymptotische Verhalten von
Problemen.
Sie kennen die Notation dazu im Prinzip, denke ich.
Ich muss nur ganz kurz das einmal als Grundlage wiederholen.
Wir haben die typische O-Notation.
O-Notation sagt also, das Verhalten von Funktionen für große Zahlen.
Das heißt, mit Groß-O von f, wenn f eine Funktion ist von N0 nach R+,
also in die positiven reellen Zahlen, dann ist dieses O von f eine
Menge von Funktionen, die nicht stärker wachsen als f, asymptotisch.
Also die asymptotisch maximal so stark wachsen wie f, bis auf eine
Konstante.
Bis auf einen konstanten Faktor.
Asymptotisch, nicht schneller wachsen als f, bis auf einen konstanten
Faktor, ist hier ausgedrückt.
G von N, die Funktion g hier, die hier drin ist, ist kleiner gleich
als c mal f von N.
c ist die Konstante.
Und das gilt für alle
Problemgrößen ab einer gewissen Grenze.
Wir hatten zum Beispiel, man kann da viele Beispiele vergeben, hängt
eben von der Konstante dann ab.
Also ist klar, dass jede lineare Funktion kleiner gleich irgendeiner
quadratischen Funktion ist.
Hängt aber von verschiedenen Dingen ab.
Es gibt hier viele Beispiele für und natürlich die Konstante muss
natürlich oder es gibt eben diese Konstante andersrum formuliert.
Das sind alle Funktionen, für die es eine Konstante gibt, sodass ab
einer gewissen Grenze diese Funktion g von N kleiner gleich c mal f
von N ist.
Also das kann durchaus sein, dass die Funktion hier zu Beginn
irgendwie größer wächst, aber irgendwann ist sie dann kleiner gleich
dieser anderen Funktion.
Der Anfangsteil kann durchaus sehr unterschiedlich aussehen, sehr
anders aussehen, aber irgendwann für großes N ist diese kleine
Gleichbeziehung da.
Jetzt kann man das Ganze auch ein bisschen drastischer ausdrücken.
Ich kann sagen, eine Funktion wächst mit klein o von f.
Das heißt, das ist eine Menge von Funktionen, die deutlich langsamer
wachsen als die Funktion f.
Und deutlich langsamer als die Funktion f heißt, wenn ich mir das
Verhalten für großes N anschaue von g und von f, dann ist der
Grenzwert dieser Verhältnisse gleich 0.
Das heißt, f wächst deutlich schneller als g. g zum Beispiel ist eine
lineare Funktion in klein o von N² zum Beispiel.
Das ist ein ganz einfaches Beispiel.
Das gleiche kann man betrachten für den umgekehrten Fall, dass man
sagt, ich gucke mir untere Schranken an, Funktionen, die mindestens so
stark wachsen wie die Funktion f, bis auf einen konstanten Faktor.
Das sind also dann Funktionen, bei denen es auch eine Konstante c
gibt, sodass ab einer bestimmten Stelle N0 für jeden größeren Wert
diese Funktion g von N mindestens so stark wächst wie c mal f von N.
Untere Schranke und das Ganze genauso wieder für die starke Aussage.
Alle Funktionen, die wesentlich stärker wachsen als die Funktion f,
das sind eben diejenigen, bei denen der Grenzwert hier auch wieder
gleich 0 ist, nur hier eben genau andersrum als bei dem klein o von f.
Das sind die asymptotischen Notationen, die man durchaus verwenden
muss, verwenden kann, in einer sinnvollen Art und Weise.
Man muss sich nur immer darüber im Klaren sein, was ich vorhin gerade
dargestellt habe.
Wenn ich an dem Verhalten für spezielle Problemgröße interessiert bin,
nutzen mir die asymptotischen Aussagen nichts.
Oder nur sehr wenig.
Da muss ich für den Vergleich von Algorithmen wirklich auch die
Konstanten mit berücksichtigen.
Und deswegen ist es wichtig, sich darüber auch immer im Klaren zu
sein.
Trotzdem ist es wichtig, zu wissen, wie man eben das asymptotische
Wachstum beschreibt, weil man häufig schon in der Lage sein möchte,
beliebig große Problemstellungen, Probleminstanzen tatsächlich auch zu
bearbeiten.
Dann als letztes noch das Theta von f.
Wenn ich sagen möchte, dass eine Funktion genauso stark wächst wie
eine Funktion g, also nicht mindestens so stark oder maximal so stark,
sondern genauso stark wächst, dann habe ich im Prinzip das Wachstum
der Funktion g eingeschränkt bis auf eine Konstante, also kleiner
gleich c mal f von n, größer gleich f von n durch c.
Das heißt, hier habe ich eine Konstante, die gerade ein Korridor
angibt für das Wachstum der Funktion g. Und damit habe ich also ein
gleichartiges Wachstum der Funktion, die hier drin sind.
Wenn Sie sich jetzt anschauen, die Schreibweise für asymptotische
Notationen, finden Sie oftmals etwas wie g gleich O von f, was
natürlich Quatsch ist, sondern g ist eine Funktion in der Menge der
Funktionen O von f.
Trotzdem wird es häufig so verwendet oder auch andersrum.
Groß O von f enthaltenen Groß O von g. Manchmal steht dann O von f
gleich O von g. Sie sehen das in diesem Beispiel.
Manchmal kann man durchaus schreiben, O von n ist gleich O von n².
Macht aber eigentlich von den Mengen her keinen Sinn, denn O von n²
ist ungleich O von n.
Die Menge sind nicht gleich, es ist aber O von n enthaltenen O von n².
Alle linear wachsenden Funktionen wachsen natürlich maximal oder auch
langsamer als quadratisch.
Also insofern ist das durchaus drin enthalten O von n in O von n²,
aber eben nicht O von n² in O von n enthalten.
Und da muss man aufpassen, wie man mit solchen laxen Schreibweisen
umgeht.
Besser ist es, man schreibt es wirklich in der richtigen Art und
Weise.
Dann haben wir noch eine andere Definition, die wir brauchen.
Das ist die Definition der Komplexität eines Problems.
Das kennen Sie auch aus den Grundvorlesungen.
Wenn ich ein Problem habe, meinetwegen das Sortierproblem, dann ist
eine untere Schranke dadurch gegeben, dass es eine Aussage ist darüber
für alle Algorithmen, die das Problem lösen.
Das heißt, für alle Algorithmen, die das Problem lösen, ist die Zeit
in Omega von f.
Das heißt, die Zeit wächst mindestens so stark wie diese Funktion f,
die die untere Schranke angibt.
Obere Schranke entsprechend wesentlich einfacher.
Da müssen Sie einen Algorithmus kennen, der das Problem löst.
Dann ist das eine obere Schranke für die Lösung des Problems.
Das kennen Sie alles.
Und natürlich muss ich aufpassen, dass das Ganze sich auf die gleiche
Rechnerstruktur bezieht.
Also was sind eigentlich die Befehle, die ich ausführe?
Habe ich da die gleiche Basis?
Ich brauche mindestens so und so viel Zeit.
Was zähle ich eigentlich als Zeiteinheit?
Da kommen wir später noch intensiver drauf zurück.
In der Regel ist es natürlich relativ schwierig, gute untere Schranken
zu bestimmen, weil Sie damit Aussagen über alle möglichen Algorithmen
machen müssen.
Und alle möglichen Algorithmen ist eine sehr große Menge.
Das heißt, da muss man genau aufpassen, wie man argumentiert, damit es
eine Aussage ist, die wirklich für alle möglichen Algorithmen gilt.
Wir werden aber einige untere Schranken kennenlernen.
Ohne Kenntnis unterer Schranken kann man natürlich nichts darüber
sagen, ob ein Algorithmus optimal ist.
Und das Ziel ist natürlich, zu sagen, hier, das ist der bestmögliche
Algorithmus.
Es gibt nur wenige Fälle, wo das wirklich tatsächlich so möglich ist,
das so zu sagen.
Ein Punkt, den wir noch ganz kurz ansprechen müssen in den letzten
Minuten dieser heutigen Vorlesungsstunde, die Zeit.
Wenn wir die messen wollen, wie machen wir das eigentlich?
Wie viel Zeit braucht ein Algorithmus?
Wir können das messen mit einer Stoppuhr, wie lange es braucht, vom
Starten bis zum Ende.
Wir können die Laufzeit des Algorithmus messen.
Wie misst man die Laufzeit?
Man guckt nach,
wie sieht eigentlich, wie war die Rechenzeit oder wie war die Zeit im
Rechner zu Beginn oder beim Starten des Programms?
Wie ist die Zeit im Rechner beim Ende?
Oder ich könnte auch einfach messen, wie viel CPU-Zeit hat eigentlich
mein Programm gebraucht.
Ich kann aber auch in ein Programm einfach Anweisungen reinschreiben,
die kurz die Zeit messen.
Ich kann die Zeit abrufen, als Integerwert und habe dann zwei Zahlen,
die ich vergleichen kann und weiß dann, wie viel Zeit ist verstrichen
von da nach da.
Wenn Sie das machen, solche Dinge einbauen, Sie wollen messen, wie
lange dauert eine Addition von zwei Zahlen, wenn hier zwischen nur
eine Addition steht, A plus B, da werden Sie nicht viel herausfinden
können.
Das müssen Sie, weil einfach die Zeit so klein ist, dass Sie das mit
der Auflösung und der Zeit, die Ihnen zurückgemeldet wird, gar nicht
messen können.
Da müssen Sie eine große Anzahl von Additionen ausführen, um
herauszufinden, wie lang hat dann eigentlich die einzelne Addition
gedauert.
Das ist also etwas, wo man aufpassen muss.
Allerdings, wenn Sie hier eine einfache Schleife bauen, ich möchte
jetzt, ich sagte gerade, man muss also viele Additionen ausführen.
Stellen Sie sich vor, Sie sagen, okay, ich will jetzt einfach die
Addition von zwei Zahlen ganz oft machen.
Ich baue da eine Schleife drum und führe die einfach tausendmal aus
und messe, wie lange das dauert.
Wenn Sie einen optimierenden Compiler haben, der wirft Ihnen dies A
plus B aus der Schleife raus, weil das immer die gleiche Operation ist
und macht das einmal vor der Schleife.
Und dann haben Sie die Zeit nicht mehr gemessen.
Also muss man aufpassen, wie man damit eigentlich umgeht, wie man Zeit
misst.
Man kann aber eben systematisch durchaus einfach Anweisungen über
Zeitmessungen in Programme einbauen und kriegt dann raus, wie lange
bestimmte Teile im Programm tatsächlich gedauert haben.
Die genaueste Messung, wie gesagt, ist, den Code einzuschließen durch
Zeitabfragen und dann diesen messenden Code sehr oft ausführen lassen.
Dann bekommt man etwas raus, wie die Zeit tatsächlich ist.
Das Interessante ist, wenn Sie ein Programm mehrfach ausführen, werden
Sie bei diesen Zeitmessungen unterschiedliche Werte bekommen.
Woran liegt das?
Liegt einfach daran, dass Sie ja nicht die Zeit bekommen, die dieses
Programm gebraucht hat, um ausgeführt zu werden, sondern Sie bekommen
die Zeit, die in der CPU vergangen ist oder im Rechner vergangen ist,
von diesem Zeitpunkt, wo die Anweisung ausgeführt wurde, bis zu dem
Zeitpunkt, wo die nächste Anweisung ausgeführt wurde, die nächste
Zeitmessung.
In der Zwischenzeit können aber viele andere Programme ausgeführt
worden sein, dadurch, dass dieses Programm unterbrochen wurde aufgrund
von höher priorisierten anderen Programmen.
Das heißt, die Last auf Ihrem Rechner ist durchaus wichtig, die
beeinflusst die Zeit, die Sie rausbekommen als Messung für die
Rechenzeit für ein bestimmtes Programm.
Deswegen ist es gar nicht so einfach, klare Aussagen zu bekommen über
die Rechenzeit, die ein gewisses Programm braucht.
Es gibt dafür gewisse Werkzeuge, Profiling-Optionen bei der
Programmausführung, kann man systematisch einsetzen.
Gehe ich nicht genauer darauf ein, wäre ein Thema, das man in den
Übungen auch nochmal ansprechen könnte, aber das mache ich in der
Vorlesung nicht explizit.
Ich wollte nur darauf hinweisen, dass es eine Rolle spielt.
Sie haben eine Frage?
Ja.
Auch das ist natürlich ein wichtiger Punkt.
Das ist klar, ein wichtiger Punkt bei der Gestaltung von Algorithmen,
wie kann ich die Anzahl der Festplattenzugriffe, also der Zugriffe auf
Hintergrundspeicher, wie kann ich die minimieren?
Und das ist auch ein wichtiger Punkt, natürlich, dass man wissen muss,
an welcher Stelle sitzt eigentlich das Programm, wo sitzen die Daten
im Speicher, habe ich einen schnellen oder langsamen Zugriff.
Danke für den Hinweis.
Das war im Wesentlichen das, was ich heute machen wollte.
Es ist auf jeden Fall so, wenn man misst, muss man Programmoptimierung
ausschalten.
Ich muss mir anschauen, Modelle meiner Berechnungssysteme und diese
Modelle von Berechnungssystemen sind das, was wir nächste Woche uns
genauer angucken werden.
Vielen Dank für die Aufmerksamkeit, das war's für heute.