Schönen guten Tag.
Ich begrüße Sie zur Vorlesung effiziente Algorithmen.
Irgendwie ist es nicht so, wie ich das will.
Es sollte gar nicht animiert sein, ist es aber trotzdem.
Und ich begrüße Sie zur Vorlesung effizienter Algorithmen.
Tut mir leid, der Start war nicht so, wie das sein sollte.
Etwas verspätet, aber ich denke, wir kommen relativ schnell durch.
So, wie es angemessen ist, um Ihnen die Inhalte zu vermitteln, die ich
Ihnen gern vermitteln möchte.
Ich freue mich, dass wir gekommen sind zu dieser Vorlesung.
Wie gesagt, mein Name ist Hartmann Schmeck.
Viele von Ihnen kennen mich bereits aus anderen Vorlesungen.
Worum geht es ornatorisch?
Also hier ist nochmal mein Bild drauf, für die Leute, die die
Vorlesung nicht direkt im Hörsaal angucken, sondern die aufgezeichnete
Version.
Was sich gegenüber früheren Jahren hier geändert hat, ist diese
Angabe.
Raum OC 16, Allianzgebäude am Kronplatz, ist der Ort, an dem ich
inzwischen sitze, mit meiner ganzen Arbeitsgruppe und der von Herrn
Oberweis und Herrn Seese und Herrn Stucki, also diejenigen gegenüber.
Auf diesem Flur dürfte auch vielen von Ihnen schon bekannt sein, denke
ich, dass wir da umgezogen sind.
Es gibt zur Vorlesung natürlich einen Arbeitsbereich.
Sie kennen hoffentlich alle die Arbeitsbereiche, die wir inzwischen
am...
...heruntergeladen werden können, ist mir nicht klar.
Ich bin völlig unklar, warum das nicht ging.
Ich habe es gestern Abend eingebaut, den Link habe ich verwendet und
das war überhaupt kein Problem.
Und lassen Sie mich nur ganz kurz etwas sagen nochmal zum
Studierendenportal.
Wer von Ihnen war noch nie im Studierendenportal drin?
Waren alle schon mal drin?
Sehr gut, Sie kennen das alle, sehr schön.
Sie wissen, dass es diese schönen Dinge gibt, wie mein Semester mit
Vorlesungsfavoriten oder Stundenplan.
Haben Sie einen Stundenplan sich da eingerichtet?
Kennen Sie alles?
Sehr schön, das freut mich.
Und bei den Vorlesungsfavoriten habe ich natürlich hier den
Vorlesungsarbeitsbereich Effiziente Algorithmen.
Und da steht eben nochmal etwas hier zum Zeit- und Ort.
Sie sind alle hier, deswegen wissen Sie das.
Dann zur Aufzeichnung ist es ja so, dass wir...
...ich kann das auch hier dran kurz erläutern...
...die Vorlesung wird ja aufgezeichnet aus verschiedensten Gründen.
Ich finde es einfach sinnvoll, dass ich das, was ich hier erzähle,
auch verfügbar mache anschließend.
Und das heißt, es ist für Sie eine Möglichkeit, sich das anschließend
nochmal anzugucken, wenn Sie sich auf Prüfungen vorbereiten oder für
die Verarbeitung von Übungsaufgaben oder aus welchem Grund auch immer,
dass Sie sich nochmal die Vorlesung anschauen wollen oder anhören
wollen.
Es soll nicht dazu führen, dass Sie der Meinung sind, ich brauche
eigentlich kaum noch aufzupassen, ich kann es mir jederzeit wieder
anhören.
Das Ziel der Lehre ist, dass Sie etwas lernen.
Man lernt am besten etwas, wenn man aktiv mit dem Stoff umgeht.
Früher war das so, dass jeder Student einen ersten aktiven Umgang mit
dem Stoff hatte, dadurch, dass er alles, was in der Vorlesung
präsentiert wurde, normalerweise an der Tafel aufschreiben musste,
weil es halt ansonsten nichts dazu gab.
Das musste halt alles mitgeschrieben werden.
Das war die erste aktive Auseinandersetzung mit dem Stoff.
Dann haben wir Folien bereitgestellt und Sie sind in der Lage, sich
die Folien schon vorher anzugucken, sofern die vorher im Netz stehen,
was wir in der Regel auch machen werden.
Was vorher vielleicht noch nicht der Fall war, aber das wird in der
Regel so sein.
Dann braucht man die Folien nicht mehr, also die Texte, die auf Folien
stehen, nicht mehr aufzuschreiben, sondern es schreibt sich nur noch
irgendwelche Anmerkungen dazu.
Es ist schon ein Teil verloren von der aktiven Beschäftigung mit dem
Stoff.
Und jetzt kommt noch dazu die aufgezeichnete Vorlesung.
Das heißt, wir brauchen gar nicht mehr das, was ich sage,
aufzuschreiben, was nicht auf den Folien steht, sonst können Sie es
nochmal anhören.
Die Versuchung ist da, dass man sich nicht mehr wirklich selbst aktiv
damit beschäftigt.
Das wäre ein großer Fehler.
Deswegen haben wir ja die Übungen dazu und in den Übungen sollen Sie
sich aktiv mit dem Stoff beschäftigen.
Das ist auch ganz wichtig.
Wir beobachten in letzter Zeit leider so Dinge, nicht jetzt in Ihrem
Semester, sondern eigentlich eher in den Anfangssemestern, aber es
kann sich ja durchziehen auf spätere Semester.
Wir beobachten, dass in den Übungen Studierende kommen, nicht nur
Einzelne, sondern sehr viele, die sich mit dem Stoff überhaupt nicht
beschäftigt haben.
Die erwarten, dass der Stoff, der in der Vorlesung eigentlich
präsentiert wurde, nochmal in den Übungen präsentiert wird, bevor eine
Aufgabe bearbeitet werden kann.
Das kann irgendwie nicht sein, dass man erwartet, dass immer wieder
der gleiche Stoff präsentiert wird.
Also ich biete Ihnen all diesen Service, oder wir bieten Ihnen diesen
Service, dass wir Ihnen diese Möglichkeiten bieten, nochmal sich alles
anzuhören und anzuschauen, was in der Vorlesung gezeigt wurde.
Und das sollen Hilfsmittel sein, dass Sie daran unterstützt, den
Stoff, um den es hier geht, das Wissen zu erwerben, die Fertigkeiten
zu erwerben, die wir für sinnvoll halten.
Und das muss man Ihnen auch im Gesetz geben.
Ich habe nicht so richtig die Antwort darauf, wie man diesen Effekt
vermeiden kann, dass Studierende in Übungen kommen und sich nicht mit
dem Stoff beschäftigt haben und eigentlich nicht mehr aktiv damit
umgehen.
Das ist eine ganz schlechte Entwicklung.
Darf eigentlich nicht passieren.
Und wir suchen danach Möglichkeiten, das anders zu machen.
Ich möchte nicht auf all diesen Service jetzt verzichten und sagen,
ich schreibe wieder alles mal an die Tafel.
Das wäre nicht die richtige Reaktion, glaube ich.
Aber ich nehme da gerne auch von Ihrer Seite, von studentischer Seite,
Anregungen auf, wie Sie sagen würden, was wäre eigentlich eine
Möglichkeit, wie man das besser gestalten würde, effektiver gestalten
würde, in Bezug auf den Lerneffekt.
Das ist das Wesentliche.
Ich möchte Ihnen etwas vermitteln, darum geht es.
Und am Ende kommt auch irgendwo eine Note raus, vielleicht, oder
hoffentlich.
Hoffentlich auch eine sehr gute Note.
Aber das Wesentliche ist, dass Sie etwas lernen, was Sie später in
Ihrer beruflichen Tätigkeit gut einsetzen können.
Und wie wir das besser hinkriegen, das ist etwas, woran wir eigentlich
ständig arbeiten und auch insbesondere in einer Elite-Universität
arbeiten müssen.
Ich mache mir so den Eindruck, dass die ganze Gerede um die Elite
-Universität und Exzellenzinitiativen und Erfolge auf Kosten der Lehre
gehen.
Das ist überhaupt nicht intendiert und auch nicht das, was tatsächlich
passiert.
Aber wie wir dazu kommen, dass wir wirklich eine exzellente Lehre
haben, das ist gar nicht so einfach und das hängt nicht nur von uns
als Dozenten ab, das hängt auch davon ab, wie Sie als Studierende auf
das reagieren, was wir machen.
Also mir ist das wichtig, dass sich das gut entwickelt und dass wir
auch Erfolg haben in dem, was wir hier präsentieren.
Also, Vorlesungsaufzeichnung.
Wir bieten sie an.
Wir bieten sie natürlich auch für Leute an, die nicht in der Lage
sind, zur Vorlesung zu kommen.
Es gibt mal Personen, die sind vielleicht krank oder machen Praktikum,
wobei man Praktikum 1 nicht für in der Vorlesungszeit machen sollte
oder sind im Ausland, wollen trotzdem hier irgendwas hören oder haben
irgendeinen Grund, vielleicht alleinerziehende Mütter oder Väter.
Also irgendwelche Gründe, warum man hier nicht daran teilnehmen kann,
die können dann natürlich durch das Anschauen der aufgezeichneten
Vorlesung in Ort und Zeit, unabhängig von den Ort und Zeit der
Vorlesung, mit dem Stoff beschäftigen.
Das ist auch ein sinnvoller Effekt, den ich auch wichtig finde und
dafür biete ich das auch an.
Also insofern, auch wer nicht hier in der Vorlesung ist, ist trotzdem
ein willkommener Teilnehmer an dieser Vorlesung.
An den Übungen sollte man natürlich dann schon direkt teilnehmen.
Gut, und wenn man jetzt mit diesen Aufzeichnungen umgehen will, ist es
wichtig, dass man auch einen sinnvollen Player verwendet.
Was ist ein sinnvoller Player?
Es gibt ja so, für das Wiedergeben von Videoinformationen, gibt es den
Windows Media Player oder auch andere, Real Player oder ähnliches.
Die haben aber einen gravierenden Nachteil.
Wenn sie da durch den Inhalt durchscrollen, dann sehen sie nicht, wo
sie gerade sind.
Und dieses sichtbare Scrolling von dem Camtasia Player ist eigentlich
ganz wichtig.
Deswegen sollte man den verwenden.
Nehmen wir an, Sie haben alle, jetzt ganz kurz, von welchen
Studiengängen kommen Sie ein?
Alle?
Nicht?
Technische VWL und?
Informationswirtschaft.
Eine Informationswirtschaft.
Alle anderen haben sich jetzt gemeldet.
Gut, also die meisten haben sowieso dann in Grundlage der Informatik 2
schon die Aufzeichnungen kennengelernt und kennen das alles.
Und ich hätte das alles gar nicht erzählt.
Okay, machen wir also weiter.
Gehen wir zurück zu der Vorlesungspräsentation.
Also, wofür wir die haben, ist klar.
Hier oben habe ich noch draufstehen den Klausurtermin.
Das ist also an dem Montag, Dienstag oder Mittwoch nach, natürlich
nicht 2008, sondern 2009, nach Vorlesungsende.
Und an einem dieser Tage wird die Klausur sein, vermutlich eher am 28.
oder 29.
Dienstag oder Mittwoch und nicht am Montagnachmittag, aber das wird
sich rausstellen.
Hängt ja ein bisschen davon ab, wie viele sich eigentlich von Ihnen
dann anmelden zur Prüfung, weil ich eine Klausur nur machen werde,
wenn das also eine ausreichende Zahl von Personen ist.
Also wenn das unter 10 sind, würde ich Ihnen problemlos eine mögliche
Prüfung anbieten.
Diese Grenze ist aber nicht scharf.
Ich muss sehen, wie das dann konkret mit der Anmeldesituation
aussieht.
Natürlich auch mit Ihren Wünschen, wenn es also nicht zu viele sind
und alle, die sich für die Prüfung angemeldet haben, eine mögliche
Prüfung wollen, können wir das auch machen.
Ansonsten, wenn jemand eine schriftliche Prüfung haben möchte, dann
wird auch eine schriftliche Prüfung angeboten.
Gut.
Das kurz dazu.
Dann zu den Übungen.
Da ist also Herr Brotmann, der Übungsleiter, sitzt hier vorne in der
ersten Reihe und ist für die Koordination der Übungen zuständig.
Ein Tutor haben wir bisher noch nicht für diese Vorlesung.
Wenn es bei der Zahl von Teilnehmern bleibt, ist es glaube ich so auch
durchaus möglich, das so zu machen.
Die Übungen sind 14-tägig, Termine stehen schon auf der Webseite
drauf.
Braucht glaube ich auch so im Einzelnen nicht mehr darauf einzugehen.
Aber das Wesentliche ist natürlich inhaltlich, das ist ein Service, um
Ihnen Gelegenheit zu geben, sich aktiv für den Stoff der Vorlesung zu
beschäftigen.
Das ist der wesentliche Punkt, dass Sie einfach die Algorithmen, die
wir hier entwickeln, dass Sie mit denen einfach umgehen und ein Gefühl
dafür bekommen, wo eigentlich die wesentlichen Punkte sind.
Was man eigentlich verstehen muss, um so einen Algorithmus wirklich
sinnvoll einsetzen zu können.
Die Termine sind glaube ich soweit klar.
Erstes Übungsblatt steht hier am 1.5., das wäre ein Feiertag.
Das Übungsblatt wurde aber schon verteilt, ist also schon fertig.
Die erste Übung ist am 15.5., wo dann die abgegebenen Blätter
besprochen werden.
Also Abgabe ist der 12., genau in zwei Wochen, hier in der Vorlesung.
Und wir machen das so, dass wir einen Bonus vergeben.
Das heißt, die erfolgreiche Teilnahme an den Übungen ist ein
Bestandteil der Note, ein geringer Bestandteil.
Sie müssen in der Abschlussprüfung bestanden haben und mit dem Bonus
für erfolgreiche Verarbeitung bekommen Sie dann eine Notenstufe besser
als endgültige Note, als Sie nur aufgrund der Abschlussprüfung
bekommen hätten.
Rechnerübungen haben wir jetzt gar nicht vorher besprochen, ob wir sie
machen oder nicht, weil Sie praktische Übungen machen dürfen.
Also es ist durchaus sinnvoll, dass man eben auch wenn man sich mit
effizienten Algorithmen beschäftigt, auch mal direkt Algorithmen
implementiert und sieht, wie aufwendig ist es denn nun wirklich, für
bestimmte Problemgrößen ein Verfahren durchzuführen.
Und insofern gibt es also wieder mindestens eine Programmieraufgabe.
Und alles, was so an Informationen zur Vorlesung wichtig ist, sollten
Sie einfach auf den Webseiten im Studierendenportal anschauen.
Und Sie wissen, dass Sie auch dort einfach sich im Nachrichtendienst
abonnieren können.
Dass Sie sagen, Sie wollen einfach informiert werden, wenn dort sich
etwas ändert.
Das kann man ja einstellen auf den Webseiten in dem
Studierendenportal.
Zielgruppen ist klar, Wirtschaftsingenieure, Informationswirte,
Wirtschaftsmathematiker oder sonstige, die hier Interesse dran haben.
Die Art der Anrechnung oder Einordnung in irgendwelche Module, die
ändert sich natürlich zur Zeit.
Wir haben ja nicht mehr Diplomstudiengänge oder zum Teil haben wir sie
noch.
Ich nehme an, die Wirtschaftsingenieure kriegen hier noch Diplom.
Nicht mehr.
Bachelor.
Drittes Jahr Bachelor.
Viertes Jahr.
Viertes Semester.
Aha.
Okay, gut.
Klar, Sie haben drei Semester und dann geht es um das vierte Semester.
Ja, sehr gut.
Das heißt, Sie sind also gerade jetzt in dem fortgeschrittenen Teil
Ihres Bachelorstudiums.
Und da haben wir die effizienten Algorithmen im Informatikmodul.
Bei den Informationswirten ist es so, dass die Vorlesung in einem
Algorithmenmodul mit drin ist.
Da gab es so verschiedene Diskussionen.
Wenn es Schwierigkeiten geben sollte, für irgendjemanden die Vorlesung
sinnvoll einzurechnen, kann man das erklären.
Die technischen Volkswirte sind selbstverständlich auch herzlich
willkommen zu dieser Vorlesung.
Auch dort passt das in ein Modul rein zur Informatik.
Ich nehme an, dass Sie das da auch schon entdeckt haben.
Gut.
Also wenn es Probleme gibt, dann müssen Sie einfach melden.
Was sich im Augenblick etwas dynamisch verändert, ist die Zahl der
Leistungspunkte.
Wenn man sich das anguckt, die Leistungspunkte, da stand früher einmal
immer 4,5.
4,5 stand da mal, weil wir die Anzahl der Semesterwochenstunden mal 1
,5 gerechnet haben.
Dann stand dort irgendwann einmal 5, weil wir mit einer Einigung mit
einigen anderen Kollegen aus anderen Fakultäten gesagt haben, wir
rechnen die Vorlesungsstunden mal 2 und die Übungsstunden mal 1.
Dann kamen wir auf 5 Punkte.
Ein anderer Grund ist, dass ein Grund, der eigentlich unwürdig ist
eines Informatikers, das ist ein EDV-Argument, in den Einträgen im LSF
für Leistungspunkte gibt es nur ganze Zahlen.
Da können keine gebrochenen Zahlen eingetragen werden.
Deswegen ist 4,5 dort nicht eintragbar.
Das ist aber ein Argument, das eigentlich nicht zulässig ist.
Sowas kann man natürlich nicht verändern.
Ist aber im Augenblick so.
Und inzwischen gibt es wieder die starke Tendenz, daraus 4,5 Punkte zu
machen.
Also Sie werden irgendwie 5 oder 4,5 Punkte bekommen, je nachdem wie
das in dem aktuellen Modul vereinbart war.
Und das ist halt etwas, was wir im Augenblick immer angeben müssen.
Leistungspunkte sind das, pro Leistungspunkt rechnen wir etwa 30
Stunden Arbeit.
Und naja, ob 4,5 oder 5 ist dann relativ egal.
Allerdings soll sich das summieren insgesamt bei den
Wirtschaftsingenieuren auf 9 Punkte, meine ich.
Das heißt, 2 mal 4,5 sind genau 9 Punkte, 2 mal 5 wären 10, dann
hätten Sie einen Punkt zu viel gemacht.
Aber das ist jetzt Leistungspunkt-Arithmetik und lenkt uns ab von den
eigentlichen Inhalten.
Wenn Sie dazu Fragen haben, kommen Sie gerne zu mir, können wir
diskutieren und erklären.
Inhaltsübersicht ist so, dass wir uns mit einer Reihe von Problemen
beschäftigen, die man als Informatiker oder Wirtschaftsingenieur oder
technischer Volkswirt oder Informationswirt zu bearbeiten hat an
verschiedensten Stellen.
Also Matrizen zu modifizieren, Polynome auszuwerten und Ähnliches
taucht an vielen Stellen auf, deswegen ist das hier mit drin.
Genauso schnelle Projekttransformation, typisches Problem, technische
Anwendung.
Und dann gibt es eben so einige weitere typische Probleme, wie Sortier
- und Suchprobleme, Grafprobleme, geometrische Probleme, mit denen man
sich hier beschäftigen kann.
Und wenn wir das gemacht haben, in einigermaßen Ausführlichkeit oder
auch weniger Ausführlichkeit, sind die maximal 13 Termine sehr schnell
abgearbeitet.
Maximal 13 Termine inklusive heute, einschließlich Dienstag nach
Pfingsten.
Jetzt ist es so, dass ich in zwei Dienstagen nicht da bin.
Da wird entweder Herr Brothbaum mich vertreten oder wir verlegen den
Konflikt.
Literatur gibt es sehr, sehr, sehr, sehr viel.
Thema Algorithmen ist ein Kernthema für Informatik und deswegen gibt
es hier auch sehr, sehr viele Literatur.
Ich habe jetzt nicht die neuesten Bücher da nochmal wieder
reingenommen, aber die hier sind alle sehr würdig.
Also ich bin selber zum Teil stark beeinflusst durch eine Art der
Darstellung in einem Buch von Borodin und Monroe.
Ein sehr altes Buch, ist also 34 Jahre alt, Computation Complexity of
Algebraic and Numeric Problems.
Da werden zunächst die algebraischen Probleme halt behandelt, ich habe
das so übernommen.
Dann werden wir uns auch beschäftigen mit parallelen Algorithmen.
Also etwas, das komme ich gleich noch drauf, dass wir uns
verschiedenste Varianten von Algorithmen anschauen.
Und da gibt es ein schönes Buch von Celine Ackel.
Ansonsten gibt es sehr schöne Bücher von Sedgwick, eine ganze Reihe
von Büchern, Algorithmen in verschiedensten Sprachen, in C, in Java
und so weiter.
Die sind dort sehr anschaulich beschrieben, also nicht sehr formal.
Das ist ein gut lesbares Buch.
Das Buch von Knuth, The Art of Computer Programming, ist ein
Standardwerk über Algorithmen.
Und dann gibt es hier noch zwei Standardwerke, einmal von Ottmann
Wittmeier, Algorithmen und Datenstrukturen.
Und Cormen, Leisers & Rivest, Introduction to Algorithms.
Also jedes dieser beiden Bücher ist eine sehr umfangreiche Sammlung
von Algorithmen.
Wenn man also den Cormen, Leisers & Rivest durchgearbeitet hat, dann
weiß man wirklich sehr, sehr viel über Algorithmen.
Ein sehr, sehr tolles Buch.
Dann habe ich hier das Buch von Hans-Werner Lang noch drinstehen,
Algorithmen in Java.
Der hat sehr schöne Algorithmen, genau zu den Problemen, die wir hier
behandeln, in einer sehr schönen Art dargestellt.
Hat dazu auch ergänzende Webseiten und eine sehr anwendungsorientierte
Darstellung von Algorithmen.
Dieses Buch von Harel, Algorithmics, ist ein Buch, das man unheimlich
gut lesen kann.
Da sind so Algorithmen dargestellt, das wird ja auch Algorithmics.
Das heißt, da werden Ideen vermittelt.
Das ist etwas, was man einfach lesen kann.
Da geht es darum, was für Ideen man eigentlich so entwickelt, wenn man
Algorithmen schreibt oder sich mit dem ganzen Thema der effizienten
Nutzung von Rechnerstrukturen für schwierige Probleme beschäftigt.
Das ist einfach ein schön lesbares Buch, kann ich wirklich sehr
empfehlen.
Und dann gibt es halt noch einiges hier zu parallelen Algorithmen.
Es gibt auch ein Buch hier von Nathan, Introduction to Parallel
Algorithms and Architectures.
Sehr umfangreiches Buch, kann man mindestens eine lange Vorlesung
drüber halten.
Ich kann das also hier nur zum Teil ansprechen.
Dann finden Sie auch ein Buch von mir über Analyse von VLSI
-Algorithmen.
VLSI steht für Very Large Scale Integration, wie Sie wahrscheinlich
wissen.
Teile daraus kommen auch in meiner Vorlesung vor.
Also es geht um eine Vielfalt von Themen im Zusammenhang mit
Algorithmen.
Und am Ende hier das Buch von Ivar Zehntner, Entwurf systolischer
Systeme.
Das ist auch wieder ein sehr dickes Buch, sehr umfassend und gibt eine
sehr umfassende Darstellung mathematischer Ansätze, um Algorithmen zu
entwerfen.
Das heißt, Sie gehen von einer mathematischen Problembeschreibung aus
und leiten dann durch eigentlich mathematische Transformationen daraus
Algorithmen ab.
Können die also systematisch erzeugen.
Ich werde Ihnen das auch in einem Beispiel darstellen.
Dass man einfach sieht, man kann wirklich Algorithmen, verschiedenste
Varianten von Algorithmen, ingenieurmäßig systematisch entwerfen.
Man muss die entsprechenden Parameter spezifizieren und bekommt dann
die Algorithmen geliefert.
So, das war jetzt ein kurzer Einstieg.
Wenn Sie zu organisatorischen Dingen noch Fragen haben, verantworte
ich die gerne.
Ansonsten gehen wir dann gleich ins nächste Kapitel über.
Das war also das erste, das waren die einleitenden, oder die
organisatorischen Dinge.
Und dann kommen jetzt die Einführungen.
Erst
ein Kapitel weiter, Einführung in die Thematik.
Das ist nun mal kurz der Zitat aus dem Vorlesungskommentar.
Es geht halt um die systematischen Ansätze mit Analyse und die
effiziente Gestaltung von Algorithmen.
Und zwar mache ich das anhand von typischen Aufgaben, die man in der
Informationsverarbeitung hat.
Und ich gehe glaube ich am besten gleich auf die nächste Folge über,
weil ich dann hier etwas erzählen kann über diese Standardaufgaben der
Informationsverarbeitung.
Wir entwickeln Algorithmen nur, weil sie gebraucht werden.
Wir brauchen sie zum Beispiel, um irgendetwas zu simulieren.
Um etwas zu visualisieren, zu optimieren, zu steuern.
Also wir machen im Augenblick Projekte im Bereich des Energiesystems.
Da geht es zum Beispiel um interessante neue Anwendungen im
Energiehandel, im Energiemarkt.
Da werden neue Tarifmodelle entwickelt, da werden Laststeuerungen von
Geräten entwickelt.
Sowas muss man erstmal simulieren können.
Das Verhalten von Geräten am Energiemarkt simulieren können.
Oder sie wollen irgendein Fahrzeug entwickeln.
Sie wollen simulieren, wie das fahren kann, wie es aussieht und so
weiter.
Das heißt, wir brauchen Simulationen.
Wir wollen das Verhalten eines Objekts darstellen.
Wir wollen etwas visualisieren.
Es gibt hier das LESC am KIT, Life Cycle Engineering Center, wo es um
sogenanntes Virtual Engineering geht.
Da werfe ich irgendwelche technischen Objekte virtuell.
Dazu muss ich so etwas erstmal visualisieren können.
Optimierung ist ein wichtiger Punkt, der für Wirtschaftsingenieure
immer eine Rolle spielt.
Steuerung von Systemen ebenso.
Ich hatte angesprochen gerade eben, dass man im Energiebereich Dinge
steuern möchte.
In der ganzen Produktion, intelligente Produktion, muss man
Fertigungsstraßen steuern und ähnliches.
Dann gibt es die kommerziell betriebswirtschaftlichen Anwendungen.
Üblicherweise Datenverwaltung, Erhebung, Suche.
Statistiken müssen gemacht werden über das, was in einem Unternehmen
alles so abläuft.
Das Wissen muss extrahiert werden.
Auch hier muss ich visualisieren, was dort eigentlich passiert.
Gibt es so Sachen wie Data Warehouses und ähnliches.
Ich muss kommunizieren können.
Heutzutage ist ohne Kommunikation eigentlich gar nicht mehr sinnvolle
Informationsverarbeitung möglich.
Dazu muss ich wissen, was ist eigentlich die Schnittstelle für
Kommunikation.
Ein typisches Beispiel im Augenblick, wir reden gerade über Projekte
für Elektromobilität.
Da kommt also ein Elektrofahrzeug an, an eine Elektrozap-Säule, also
eine Elektro-Tankstelle.
Das ist zunächst mal nur eine Steckdose.
Aber da muss das Fahrzeug sich identifizieren gegenüber dem
Energieunternehmen.
Und ich muss wissen, was sind eigentlich die Informationen, die aus
dem Fahrzeug in das Energiesystem fließen müssen, die aus dem
Energiesystem in das Fahrzeug fließen müssen.
Was habe ich da eigentlich für Schnittstellen zu liefern.
Also Input-Output-Schnittstellen muss man definieren können.
Wir müssen grafische Datenverarbeitung sinnvoll machen können.
Sie kennen alle möglichen grafischen Anwendungen.
Ein typischer Bereich, wo man grafische Datenverarbeitung macht, ist
zum Beispiel bei Spielen.
Wenn Sie irgendwelche Spiele betrachten, da wird normalerweise sehr
viel grafisch dargestellt.
Sehr anspruchsvoll.
Einer der Haupttreiber für komplexe Anwendungen der
Informationsverarbeitung sind heutzutage Spiele.
Also Online-Spiele oder auch nicht Online-Spiele.
Sicherheitsmechanismen in der Kommunikation sind wichtig.
Was für Operationen treten dabei auf?
Wenn ich hier oben an diese technisch-wissenschaftlichen Berechnungen
denke, was brauche ich dort?
Also zum Beispiel habe ich meinetwegen irgendeine Tragfläche zu
entwerfen.
Eine Tragfläche hat irgendeine Oberfläche.
Und um darüber etwas aussagen zu können, um das modellieren zu können,
macht man in der Regel irgendwelche Anwendungen von Finiten-Element
-Methoden und beschreibt dann so etwas durch Triangulierung, hat hier
also ein Gitternetz drauf, und beschreibt also so eine Oberfläche
durch alle möglichen Dreiecksstrukturen zum Beispiel.
Macht dann Aussagen über das Verhalten dieser Oberfläche, indem man
sich das Verhalten an diesen einzelnen Punkten anschaut und dann das
Verhalten für die ganze Oberfläche hinbekommt.
Finiten-Element-Methoden, ein wichtiger Bereich, der in technisch
-wissenschaftlichen Berechnungen gebraucht wird.
Dann braucht man in ganz vielen Bereichen Multiplikation von Matrizen.
Das ist also eines der Standard-Benchmarks für die Leistungsfähigkeit
von Rechnerstrukturen.
Wie schnell kann ich dort Matrizen modifizieren?
Brauche ich eine lineare Transformation, wenn ich Gleichungssysteme
lösen will, typische Anwendungen oder typische Aufgaben in technisch
-wissenschaftlichen Berechnungen?
Deswegen muss ich wissen, wie kann ich eigentlich möglichst schnell
insbesondere große Matrizen modifizieren.
Oder ich möchte Funktionen approximieren, muss Integrale berechnen.
Auch da brauche ich geeignete Algorithmen für.
Oder eben Polynome auswerten.
Da kommen wir gleich noch drauf.
Wenn ich Funktionen approximiere, mache ich das normalerweise durch
irgendwelche Polynome.
Also so eine Kurve wäre durch den Polynomen zweiten Grades beschrieben
oder so etwas eben durch den Polynomen dritten Grades und so weiter.
Und wenn Sie halt irgendetwas haben wie so eine Funktion, wenn die
irgendeinen Kurvenverlauf beschreiben soll, wird die normalerweise
auch durch irgendeinen Polynomen dargestellt.
Und Sie müssen solche Polynome auswerten können, möglichst schnell
auswerten können, also die Werte berechnen können.
Dann müssen Sie hier in diesem Bereich der betriebswirtschaftlichen
Anwendungen natürlich auf die vielen Daten, die es dort gibt, schnell
zugreifen können.
Sie müssen lesen können, Sie müssen schreiben können, Sie müssen
verändern können.
Sie müssen Daten auffinden können, also suchen.
Häufig müssen Sie sortieren.
Das ist eine Standardaufgabe, die auf großen Datenmengen ausgeführt
wird.
Also nicht auf irgendwie ein paar hundert Daten, sondern das sind
Millionen von Daten, die in kurzer Zeit häufig sortiert werden müssen.
Insbesondere z.B.
im Bankbereich, da müssen irgendwelche Buchungen zugeordnet werden zu
einzelnen Konten, da werden die halt entsprechend sortiert und
ähnliches.
Also das sind wichtige Aufgaben, die müssen schnell erledigt werden
können.
Wegesuche in Graphen, wichtiges Thema, wenn Sie an Routingaufgaben
denken, Sie wollen navigieren in einem Graphen, dann müssen Sie ein
kürzes Gedicht finden können.
Also eine Variante der Wegesuche in Graphen.
Ich nehme an, dass Sie noch nicht, oder zum Teil haben Sie auch
Projekts -Research schon gehört.
Doch natürlich, Sie haben im zweiten und dritten Semester Projekts
-Research gehört.
Sie kennen also Anwendungen auf Graphen.
Das ist jedenfalls auch ein Bereich, in dem man sehr viel Aufwand oder
sehr viel Intelligenz reinsteckt, so etwas möglichst schnell zu
machen.
Sie müssen Graphen darstellen können.
Wir haben es häufig mit sehr stark vernetzten Systemen zu tun.
Wenn Sie zum Beispiel irgendwelche Websites darstellen wollen, sehen
wollen, wie sind eigentlich die einzelnen Komponenten miteinander
verbunden.
Dann müssen Sie das ja irgendwie vernünftig darstellen können.
Wo ordne ich jetzt welche Kanten an, wenn ich hier meinetwegen
irgendwelche Knoten habe in einem Graphen und ich möchte jetzt
Verbindungen darstellen zwischen diesen einzelnen Knoten.
Was ich hier gerade eben gemacht habe, das Überstreichen eines Knotens
ist nicht schön.
Das muss also eigentlich nur da rangehen.
Diese Kanten wären alle einfach darstellbar.
Aber jetzt gehe ich hier hin und jetzt gehe ich noch da hin und habe
vielleicht noch hier eine Kante und habe vielleicht noch da eine
Kante.
Sie sehen, das ist ja keine schöne Darstellung, wenn auf einmal eine
Linie über einen Knoten führt.
Wie man das hinbekommt, ist gar nicht so einfach.
Oder wenn Sie an Anwendungen wie Google Maps denken.
Da haben Sie Objekte auf eine Grafikstruktur.
Also wenn Sie da die Städte sich nehmen mit geometrischen
Randbedingungen.
Jetzt stellen Sie das in unterschiedlichen Auflösungen dar.
Und Sie haben Straßennamen, Sie haben Ortsnamen und ähnliches.
Das soll natürlich nicht Straßennamen über Straßennamen geschrieben
werden oder Ortsnamen über Ortsnamen.
Die müssen an der richtigen Stelle angeordnet werden.
Das sind interessante Fragestellungen, die alle algorithmisch sinnvoll
behandelt werden müssen.
Also, worum geht es?
Wir wollen die Aufgaben, die anstehen, mit möglichst effizienter
Ressourcensetzung machen.
Also möglichst wenig Kosten verursachen.
Ressourcen sind immer mit Kosten verbunden.
Eine Ressource ist die Zeit, ein sehr kostbares Gut.
Also möglichst schnell, pro Aufgabe.
Das ist häufig eine Anforderung.
Ich möchte eine Aufgabe sehr schnell erledigen.
Aber nicht immer so, dass es nur darum geht, eine Aufgabe sehr schnell
zu erledigen.
Also zwei Matrizen schnell zu modifizieren.
Es kann sein, dass ich einen hohen Durchsatz brauche.
Hoher Durchsatz.
Also das eine ist, ich habe hier eine Bearbeitung einer Aufgabe, die
dauert sehr lang.
Und eine andere, die geht sehr schnell.
Das hier ist der Zeitstrahl.
Wir nennen das jetzt die Dauer einer Berechnung.
Wenn ich hohen Durchsatz haben möchte, dann möchte ich möglichst viele
Berechnungen pro Zeiteinheit machen.
Vielleicht auch nebeneinander.
Das heißt, da kommt es darauf an, wie viele Aufgaben kann ich pro
Zeiteinheit erledigen.
Typische Anwendungen im Bereich der Signalübertragung.
Fernsehübertragung, Fernsehbildübertragung.
Sie müssen dafür sorgen, dass sie in dem Frame-Takt bleiben.
So und so viele Frames pro Sekunde müssen abgeliefert werden.
Und müssen weitergegeben werden.
So und so viele Punkte, so und so viele Pixel pro Sekunde müssen
bearbeitet werden, damit sie im Streaming-Modus Videos vernünftig
zeigen können.
Das kann durchaus etwas verzögert sein insgesamt.
Es ist nicht wichtig, dass Sie tatsächlich genau zur gleichen Zeit
etwas sehen.
Es darf durchaus eine Verschiebung geben.
Also Sie haben hier diese Verschiebung zwischen Anfang einer
Berechnung und Ende einer Berechnung.
Die kann durchaus lang sein.
Aber wenn Sie pro Takt etwas ganz schnell machen, also viele solche
Berechnungen pro Takt anstoßen können, bekommen Sie eben auch viele
Ergebnisse in einer hohen Frequenz geliefert.
Und das muss man unterstützen.
Deswegen sind eben Pipelining-Verfahren da wichtig.
Und das heißt, ich muss dann redundante Partnerstrukturen haben, die
parallel solche Berechnungen ausführen können.
Dann möchte ich manchmal wenig Speicherplatz haben.
Ich habe zwar immer mehr Speicherplatz, aber wir wissen, egal wie viel
Speicherplatz wir auf unseren Festplatten oder auf dem Hauptspeicher
haben, wir finden sofort irgendwelche Programme, die sofort wieder
auffressen.
Und wir haben eigentlich immer ein Problem, dass wir nicht genügend
Platz haben für die Speicherung von Daten.
Also das ist durchaus eine wichtige Aufgabe.
Wir gucken aber normalerweise eher hier auf diese Zeitaspekte.
Wenige Berechnungseinheiten hat wieder etwas mit Ressourcen zu tun.
Wobei die Bedeutung dieser Anforderung ein bisschen sich verändert.
Bisher war es immer so, dass man, wenn man Glück hatte, einen Rechner
für sich zur Verfügung hatte.
Wir sind jetzt in der Situation, wo ich nehme an, wenn Sie einen
Laptop haben, in der Regel mindestens zwei Cores drin sind.
Also Sie haben schon zwei Berechnungseinheiten, die gegeneinander
arbeiten können.
Vielleicht haben Sie sogar zwei Prozessoren mit jeweils zwei Cores
drin.
Und die meisten Rechner, die irgendwo im Hintergrund laufen, die haben
halt dann acht oder sechzehn Cores schon verfügbar.
Also Rechnerkerne.
Das heißt, wir haben eigentlich immer mehr Berechnungseinheiten zur
Verfügung.
Und in wenigen Jahren werden wir, wenn es um das Thema, das Stichwort
kommt später nochmal, Many-Core geht, da werden Sie so Größenordnung
100 bis 1000 Prozessoren auf Ihrem Rechner haben, für irgendwelche
Aufgaben eingesetzt werden können.
Das wird die Art, wie wir Informationsverarbeitung organisieren,
drastisch verändern.
Weil wir vermutlich in Zukunft mehr Prozessoren lokal zur Verfügung
haben, als wir eigentlich sinnvoll einsetzen.
Da diese Aussage noch etwas figurativ ist, muss man sehen, wie viele
Ideen wir dann haben, die sinnvoll einzusetzen.
Aber das verändert im Augenblick das, was wir entwickeln im Bereich
der Algorithmen, ziemlich drastisch.
Dann haben wir heutzutage sehr viel zu tun mit verteilten
Berechnungen.
Also wir können eigentlich heutzutage kaum noch Berechnungen sehen,
nur bezogen auf einen Rechner, der jetzt eine Folge von Operationen
ausführt, sondern wir haben in der Regel auch Kommunikation mit
anderen Einheiten da drin.
Wir haben viel Kommunikation im Internet und Ähnliches.
Aber auch ansonsten bekommen wir immer stärker eingebettete Systeme in
Objekten unserer täglichen Umgebung.
Und dann werden Nachrichten geschickt.
Und das Verschicken von Nachrichten ist teuer im Sinne der Zeit, die
man braucht.
Wenn Sie eine Nachricht verschicken, können Sie in der Regel mehrere
Millionen einzelne Berechnungsstätte machen.
Das heißt, da muss man sich genau überlegen, wann man Nachrichten
verschickt, wofür man sie verschickt, und wie wertvoll eigentlich das
Verschicken der Nachricht ist für den Fortgang der Berechnung.
Also wenige Nachrichten ist da ein wichtiger Aspekt, deswegen zählt da
manchmal nur die Nachrichten als Kosten.
Und dann ist ein weiterer Punkt, also hier unten steht es, die
weitgehende Nutzung der verfügbaren Ressourcen ist klar.
Zuverlässige Ausführung von Aufgaben.
Auch ganz wichtig.
Wenn Sie Homebanking machen oder Ähnliches, wollen Sie sicher sein,
dass eine Überweisung tatsächlich richtig ausgeführt wird.
Oder wenn Sie ein Raumschiff steuern, müssen Sie sicher sein, dass die
Steuerung zuverlässig funktioniert.
Oder wenn Sie ein Navigationsgerät haben, dann wollen Sie sich
verlassen können darauf, dass die Route, die Ihnen empfohlen wird,
tatsächlich eine kurze Route ist und nicht irgendein Umweg für Sie
bedeutet, der unnötig gewesen wäre.
Also die Zuverlässigkeit von Berechnungen ist auch ein wichtiges
Thema.
Hat also auch was mit Kosten zu tun, hat mit Anforderungen zu tun an
Algorithmen.
Insbesondere wenn Sie sehr viele Prozessoren haben auf Ihrem Rechner
und davon fällt einer aus, dann wollen Sie eigentlich, dass sich das
für die Qualität Ihrer Berechnung nicht auswirkt, sondern dass einfach
die Berechnung auf einem anderen Knoten nochmal ausgeführt wird, so
dass Sie Fehler maskieren können.
Auch das ist wichtig.
Das waren also eine Reihe von Anforderungen, die was mit Effizienz zu
tun hatten und diese Effizienzanalyse, die kann also einerseits pro
Aufgabe sein.
Ich möchte 100 Listen sortieren.
Ich schaue mir an, für jede einzelne Liste, wie lange hat das
gedauert.
Pro Aufgabe bezieht sich hier auf das Sortieren überhaupt.
Es kann aber auch sein, dass ich die einzelne Berechnung anschaue.
Es kann sein, dass ich eine Gruppe von Berechnungen anschaue, wie bei
dem Beispiel hier oben, wo ich eben diese ganze Gruppe von
Berechnungen betrachte.
Oder ich gucke mir einzelne Ressourcen an.
Wie gut kann ich diese einzelnen Ressourcen eigentlich einsetzen für
meine Aufgabe.
Ich rede die ganze Zeit von Algorithmen.
Sie wissen alle, was Algorithmen sind.
Das haben Sie im zweiten Semester spätestens gelernt.
Es gibt also den intuitiven Algorithmusbegriff von Anfang des vorigen
Jahrhunderts.
Ein endlich beschriebenes deterministisches Verfahren mit Ein- und
Ausgabe, das für alle zulässigen Eingaben terminiert und dessen
Operationen effektiv sind.
Begriffliche Beschreibung, die allgemein akzeptiert ist.
Allerdings sind diese Sachen, die hier stehen, nicht...
Das ist nochmal eine andere Formulierung.
Die wesentlichen Stichwörter sind also hier die Finitheit, die
Endlichkeit, die Effektivität der Operation, das heißt, ich kann sie
wirklich ausführen.
Da sind keine Operationen drin, bei denen ich nichts weiß über den
Ausgang.
Die Terminierung der Ausführung ist wichtig und die Determiniertheit,
das heißt, ich habe immer das gleiche Ergebnis am Ende.
Wenn ich mir angucke, mit welchen Algorithmen ich heute umgehe, dann
stelle ich schon mal fest, ich habe sehr viele randomisierte
Algorithmen.
Also randomisierte Algorithmen sind Algorithmen mit
Zufallsentscheidungen, nicht deterministisch.
Wenn ich einen randomisierten Algorithmus habe, kann es sein, dass ich
nichts genaues sagen kann oder nur Wahrscheinlichkeitsaussagen machen
kann über die Dauer einer Berechnung.
Es kann auch sein, dass ich nur unscharfe Aussagen machen kann über
das Ergebnis einer Berechnung.
Also das klassische Beispiel des Primzahltests, wo ich nur mit einer
gewissen Wahrscheinlichkeit sagen kann, ob das Ergebnis, das der
Algorithmus mir liefert, tatsächlich richtig ist.
Ob das wirklich eine Primzahl ist oder nicht.
Oder wenn Sie sich die Metaheuristik anschauen, genetische
Algorithmen, Ameisenalgorithmen, Simulated Kneeling oder ähnliches,
das sind randomisierte Algorithmen, die einen hohen Wert haben für den
Bereich Algorithmen, also den Bereich der Suche nach guten Lösungen
für schwierige Probleme.
Und sie haben keineswegs bei jedem Lauf das gleiche Ergebnis.
Sie wollen gerade unterschiedliche Ergebnisse haben.
Das heißt, da haben wir eine Klasse von Algorithmen, die nicht genau
dem entspricht, was hier steht.
Zwar einzeln effektive Operationen, aber die Ergebnisse können
durchaus unterschiedlich sein.
Also das ist so die klassische Definition, aber die Realität, die wir
haben bei Algorithmen, sieht heutzutage ein bisschen anders aus.
Genauso die Determiniertheit.
Also es gibt für Anwendungen... nein, Entschuldigung, Determinierung.
Ein einzelner Sortiervorgang soll selbstverständlich nach einer
gewissen Zeit enden.
Die Überwachung eines Rechners oder die Überwachung eines Geräts soll
aber nicht nach einer festen Zeit enden.
Sie soll immer weiterlaufen.
Ein Betriebssystem soll bitte nicht enden, das tut es manchmal.
Aber das wird nicht passieren.
Das wird eigentlich immer weiterlaufen.
Das heißt, wir haben auch wichtige Anwendungen, bei denen es wichtig
ist, dass eine Berechnung eigentlich kontinuierlich weiterläuft.
Also insofern, das ist die klassische Formulierung, was ist ein
Algorithmus.
Den hat man genommen, um zu sagen, wie kann ich eine Funktion
berechnen mit solchen algorithmischen Methoden.
Und wenn es darum geht, aus einer Eingabe eine Ausgabe zu erzeugen,
dann muss ich das in der Regel so machen, wie es hier steht.
Mit gewissen Variationen heutzutage in Richtung randomisierter
Algorithmen.
Aber im Bezug auf die Berechenbarkeit haben wir eben diese
begriffliche Festlegung gehabt.
Und wenn man das jetzt informatisch noch ein bisschen anders
formuliert, haben wir im Prinzip eine endliche Beschreibung der
Ausführung einer endlichen Folge von Befehlen auf einer abstrakten
Maschine.
Das passt sogar auch zu den randomisierten Algorithmen, weil es sein
kann, dass ich hier eine endliche Folge von Befehlen, bei denen ich
aber eben Zufallsentscheidungen drin habe.
Wir kennen diese Begriffsbildung alle aus den Anfangssemestern, aber
man muss sie doch ein bisschen von der höheren Barte angucken und
feststellen, naja, das ist für einen Teilbereich der Algorithmik und
der Berechenbarkeit sinnvoll.
Aber es gibt Bereiche, wo wir durchaus Variationen davon betrachten,
die sehr sinnvoll sind.
Dann ist noch ein Punkt, auf den ich großen Wert lege, dass wir bei
den Algorithmen natürlich einzelne Operationen haben.
Wir haben also einzelne Operationen, wir haben Konstrukte, mit denen
wir die Struktur von Algorithmen beschreiben, das ist die
Programmstruktur.
Also Sie haben zum Beispiel Y-Programme oder Sie können Schleifen
formulieren, Sie haben Abfragen und ähnliches, das ist die
Programmstruktur.
Dann haben wir alle möglichen Datenstrukturen, haben Sie alle
kennengelernt, Listen, Folden, Arrays, zweidimensionale Arrays oder
Bäume oder ähnliches.
Die bedingen einander sehr stark, die Qualität von Algorithmen hängt
sehr stark von der Qualität der Datenstrukturen oder von der
Adäquatheit der Datenstrukturen ab.
Aber was wir eben auch haben, sind die Rechnerstrukturen.
Und je nachdem, ob Sie einen Rechner haben oder mehrere oder sehr
viele Berechnungseinheiten, kann es sein, dass Sie Ihre Berechnungen
völlig unterschiedlich organisieren.
Und es liegt mir daran, bei dieser Vorlesung Ihnen dafür ein Gefühl zu
vermitteln, dass man Algorithmen in ihrer Gestaltung ganz stark darauf
ausrichtet, welche Programmstrukturen, Datenstrukturen,
Rechnerstrukturen die zu erfüllen haben.
Ein Algorithmus ist nicht etwas festes, für Sortieren können Sie
natürlich Quicksort verwenden, weil wenn Sie Quicksort sagen, beziehen
Sie sich auf einen Rechner, auf eine bestimmte Art des Algorithmus.
Und Sie können den vielleicht gar nicht so sinnvoll übertragen in
einen parallelen Algorithmus.
Das geht mit gewissen Variationen, aber ein Algorithmus wie zum
Beispiel Bubblesort, der Ihnen vielleicht noch geläufig ist als ein
Algorithmus, der in dieser Grenze zu bestimmten Teilverhalten hat, der
ist für die Implementierung in Hardware ideal geeignet.
Und ist dort einer der besten Algorithmen und einer anderen Art der
Beurteilung.
Das heißt, da muss man sehr genau aufpassen, worüber man eigentlich
redet.
Man hat hier eine Vielfalt von Variationsmöglichkeiten.
Und was dabei eine gute Variante ist und eine schlechte, das werden
wir uns genauer angucken.
Also Strukturen in Algorithmen sind hier alle möglichen Dinge wie...
Programmstrukturen kennen Sie alle, ich brauche nicht genau darauf
einzugehen jetzt.
Dann haben wir Datenstrukturen, hatte ich schon kurz erwähnt.
Arrays, Records, Listen, Stacks, Queues, Bäume, Heaps.
Dafür sollten Ihnen eigentlich alle schon etwas sagen, haben Sie in
Ihren ersten Vorlesungen alle kennengelernt.
Gridfile, Segmentbaum sagt Ihnen wahrscheinlich nichts.
Das sind Datenstrukturen, Baumstrukturen, die man im Bereich der
geometrischen Datenverarbeitung braucht.
Ein Skiptree ist eine spezielle Listenstruktur oder auch
Suchbaumstrukturen für anspruchsvolle Anwendungen.
Interfaces passen nicht so ganz rein zu den Datenstrukturen, aber
geben eigentlich an, wie die Übergaben zwischen Methoden, zwischen
Prozeduren, zwischen Funktionen oder zwischen Anwendungen gestaltet
sind.
Also welche Parameter muss ich alle angeben.
Insofern hat das schon etwas zu tun mit einer Struktur der
Informationen, die ich übergeben muss von einer Anwendung zu einer
anderen Anwendung.
Dann habe ich alle möglichen Rechnerstrukturen.
Rechnerstruktur wird definiert zunächst mal durch den Befehlssatz.
Welche Befehle habe ich eigentlich?
Also ich kann vielleicht irgendwie...
Also der Befehlssatz hängt natürlich auch zusammen mit dem Prozessor.
Also kann ich zum Beispiel addieren, subtrahieren, kann ich
normalerweise beides.
Multiplizieren, dividieren.
Auf irgendwelchen Objekten.
Das sind erstmal die arithmetischen Operationen.
Dann würde ich vielleicht auch logische Operationen ausführen können.
Oder auf ganzen Wörtern.
Auf irgendwelchen logischen Werten.
Also der Befehlssatz ist erstmal die Basis dafür, dass ich überhaupt
etwas programmieren kann.
Die Prozessorstruktur hängt stark damit zusammen, wie die Befehle
eigentlich interpretiert werden.
Und Verbindungsstrukturen sind natürlich auch ganz wichtig.
Also Verbindungsstrukturen zwischen Rechnern.
Habe ich hier Rechner, die so linear verbunden sind?
Oder sind die vielleicht irgendwie auch jitterverbunden?
Oder noch irgendwie anders?
Bei den Beispielen für Rechnerstrukturen habe ich jetzt gerade hier
ein paar Sachen nochmal aufgeführt.
Turing-Maschine ist allen bekannt vor diesen Grundlagen der Informatik
2.
Oder beim Informationswirt von Informatik 3.
Einfaches, sehr einfaches Modell.
Die Random Access Machine, bisschen passender, oder Registermaschine
auf deutsch.
Bisschen mehr angepasst an das, was wir tatsächlich machen in der
Informatik.
Die PRAM, also Random Access Machine, hat im Prinzip eben eine
Steuereinheit, eine Rechenausführung, also ein Control, ein Rechenwerk
und ein Speicher.
Das ist so die klassische Von-Neumann-Maschine, aber aus
algorithmischer Sicht dargestellt.
Jetzt kann ich davon natürlich viele haben.
Dann habe ich so eine Parallel Random Access Machine.
Mit vielen Speicherbereichen oder vielleicht auch einem gemeinsamen
Speicherbereich.
Also PRAM ist das klassische Modell für parallele Berechnungen.
Was kann ich machen, wenn ich beliebig viele Prozessoren zur Verfügung
habe?
Und die können jeweils beliebig zugreifen auf den Speicher.
Dann kann es sein, dass ich spezielle Verbindungsstrukturen habe.
Eine Hypercube.
Weiß jemand von Ihnen, was eine Hypercube ist?
Ein ganz einfaches.
Eine Hypercube der Dimension 0 ist ein einzelner Knoten.
Dimension 1 wäre zwei Hypercubes der Dimension 0 verbunden durch eine
Kante.
Hypercube der Dimension 2 wäre zwei Hypercubes der Dimension 1.
Die entsprechenden Knoten sind verbunden durch eine Kante.
Hypercube der Dimension 3 wären zwei Hypercubes der Dimension 2.
Und die entsprechenden Knoten jeweils durch eine Kante verbunden.
Hypercube der Dimension 4 wären zwei Hypercubes der Dimension 3.
Und da entsprechende Knoten miteinander verbunden.
Ich weise jetzt nicht alle Verbindungen auf, aber jedenfalls hätten
Sie hier alle möglichen Verbindungen zwischen den verschiedenen Knoten
der beiden Würfel.
Das heißt, Sie können beliebig dimensionale Hypercubes bauen und haben
dann entsprechend pro Knoten immer mehr Verbindungen zu Nachbarknoten.
Eine sehr interessante Struktur.
Also hier ein Durchmesser, das heißt maximale kürzeste Verbindung
zwischen zwei Knoten haben, die gerade logarithmisch in der Anzahl der
Knoten sind.
Ein sehr kleiner Durchmesser.
Hypercube.
Baumrechner ist klar, das wäre einfach nur so irgendein Baum, der
baumartig angeordnete Rechner.
Wobei Sie da sofort sehen, wenn Sie hier kommunizieren wollen zwischen
meinetwegen diesen Knoten hier und diesen Knoten, dann müssen Sie
immer hier ganz oben rumlaufen.
Das heißt, da ist ein Engpass in der Kommunikationsstruktur.
Hat trotzdem für bestimmte Dinge sinnvolle Anwendungen.
Ein gitterverbundenes Feld hatte ich vorhin mal kurz angedeutet, das
ist eben einfach so eine zweidimensionale Anordnung von Prozessoren.
Sehr naheliegend, die Prozessoren so in der Fläche anzuordnen.
Die Frage ist dann immer, was passiert eigentlich, wenn jetzt
irgendeiner von hier oben kommunizieren möchte mit einem Knoten, der
unten ist.
Was mache ich mit dem Rand?
Und da ist einfach die Idee, dass ich die Ränder miteinander verbinde.
Dann habe ich hier solche Verbindungen in der Richtung und in der
Richtung.
Und das ist dann ein Torus.
Im Prinzip ist das so, dass Sie, wenn Sie die Prozessoren
zweidimensional aufgemalt haben, einfach so ein Blatt Papier nehmen,
das so zusammenlegen, dann haben Sie Zylinder, dann können Sie das
nochmal wieder zusammenlegen, dann haben Sie einen Torus insgesamt.
Sogenannte Wraparound-Verbindungen, da ist die Nachbarschaft der
Prozessoren identisch, unabhängig von der Position im Torus, haben Sie
immer die gleichen Nachbarschaftsbedingungen.
Mesh of Trees, kommen wir später nochmal zu, das ist also ein Gitter
von Bäumen, eine besondere Art der Verbindungsstrukturen.
Also es gibt vielfältige Ideen, wie man parallele Rechner miteinander
verbindet.
Entsprechend können Sie sich vorstellen, wird man die auch alle etwas
unterschiedlich programmieren und Algorithmen anders strukturieren.
Und das ist so ein bisschen das Problem der Parallelverarbeitung
gewesen, dass es viele Ideen gab, wie man effiziente Parallelrechner
baut, und für jeden Parallelrechner brauchte man eine eigene Art der
Programmierung.
Und deswegen sind einige oder eine ganze Reihe von Firmen entstanden,
die Parallelrechner angeboten haben, aber es hat sich nicht wirklich
durchgesetzt, weil der Aufwand, irgendwelche Anwendungen darauf zu
bringen, irgendwann einfach zu groß war.
Man hat gesehen, dass die Einzelprozessoren in den 80er, 90er Jahren
so stark leistungsfähiger wurden, dass sich der Gewinn durch
Parallelverarbeitung gar nicht so bezahlt gemacht hat, außer im
wirklichen Hochleistungsrecht.
Jetzt sind wir in der Situation, wo wir die Leistungsfähigkeit der
einzelnen Prozessoren nicht mehr wirklich so erhöhen können.
Jetzt geht es nur noch in die Parallelität hinein.
Deswegen haben wir jetzt Multi-Core und Many-Core-Architekturen.
Die Taktfrequenz der einzelnen Prozessoren nimmt nicht mehr zu.
Die bleibt so in der Größenordnung 2-3 Gigahertz.
Oder vielleicht noch ein bisschen mehr, aber nicht wirklich wesentlich
mehr.
Aber die Anzahl der Prozessoren pro Quadratzentimeter, die wird
drastisch wachsen.
Dann haben Sie garantiert parallele Strukturen und es wird
wahrscheinlich so sein, dass man die Verbindungsstrukturen zwar in
einer gewissen Art physisch auf dem Chip drauf hat, aber sie
weitgehend virtualisieren wird, dass man unterschiedliche
Verbindungsstrukturen dort einsetzen kann, je nachdem, welche
Anwendung man hat.
Das ist ein unheimlich spannendes Gebiet, wo zur Zeit sehr, sehr viel
Forschung hineingeht.
Es ist so, dass das Vermitteln von Techniken, um parallele Anwendungen
zu entwickeln, das ist an vielen Unis eingeschlafen, weil es hieß,
naja, für die breite Masse ist Parallelverarbeitung nicht mehr so
aktuell.
Das hat sich jetzt wieder drastisch geändert und deswegen ist das, was
wir hier machen, eigentlich wirklich eine hochaktuelle Geschichte.
Hier steht nochmal das Stichwort Multicore oder auch Minicore.
Und eine Quelle für parallele oder verteilte Berechnung ist natürlich
das Grid.
Das,
was da eben auch steht, ist der Begriff Cloud.
Den Begriff Grid haben Sie vielleicht schon mal gehört.
Das ist so die Idee, dass man aus dem Power Grid, also dem
Energiesystem, Rechenleistung aus der Steckdose sich holt.
Sieht aber so aus, dass man dort im Wesentlichen große,
leistungsfähige Rechner zusammenschaltet und die dann verfügbar macht.
In Rechenzentren bei dem Thema Cloud geht es darum, Services zu
entwickeln, mit denen man die Bereitstellung virtueller
Rechenressourcen organisiert.
Berechnungscloud ist ein Thema, das seit etwa zwei Jahren aktuell ist
und zurzeit eine starke Dynamik gewinnt.
Hier bei uns im Rechenzentrum oder beim Steinbruch Center for
Computing haben wir ein internationales Testbett für Cloud Computing.
Das wird gerade aufgebaut und das ist eine sehr interessante
Geschichte der Virtualisierung von physischen Rechnerressourcen, die
Bereitstellung von Services, um solche virtuellen Ressourcen sinnvoll
zu nutzen.
Ein bisschen angestoßen wurde das durch Services von Amazon, die die
sogenannten Elastic Clouds anbieten.
Ein Elastic Cloud.
Hat jemand von Ihnen schon mal ein Elastic Cloud genutzt?
Können Sie jederzeit machen.
Es braucht nur zur Amazon zu gehen.
Sie können sich dort einen Rechner definieren, einen virtuellen
Rechner.
Irgendein Linux Operating System.
Es gibt verschiedene Varianten.
Sie können sich spezifizieren, was alles drauf sein soll.
Und dann können Sie den einsetzen.
Sie müssen pro Stunde Rechenzeit 10 Cent zahlen.
Man muss das bezahlen, aber das ist sehr preiswert.
Und Sie können eben je nach Bedarf dort Rechenleistung abrufen.
Und das ist ein wahnsinniger Vorteil, wenn Sie zum Beispiel ein
Unternehmen gründen wollen.
Sie wollen irgendwelche Dienste anbieten, für die Sie Rechenressourcen
brauchen.
Und Sie wissen noch gar nicht so richtig, wie groß wird eigentlich der
Bedarf sein.
Wie viel Rechenkapazität muss ich eigentlich vorhalten?
Als junger Unternehmer werden Sie kaum in der Lage sein, sich 100
Rechner hinzustellen.
Die müssen Sie erstmal installieren, die müssen Sie administrieren,
die müssen Sie betriebsfähig halten.
Das kostet sehr viel Energie, kostet Platz und Ähnliches.
Es kann sein, dass Sie einen Tag mal diese 100 Rechner brauchen, am
nächsten Tag brauchen Sie nur noch zwei und dann hätten Sie gerne 300
Rechner gehabt.
Mit einer Elastic Cloud ist das problemlos machbar.
Sie sagen einfach, heute brauche ich 1000 Rechner.
Und Sie haben die 1000 Rechner zur Verfügung, die führen Ihre
Berechnungen aus.
Das ist also ein interessantes Geschäftsmodell, Rechenressourcen
virtuell anzubieten.
War Ihnen das nicht bekannt, dass sowas existiert?
Hat jemand davon schon mal gehört gehabt, von diesen Clouds?
Sie haben davon gehört.
Die anderen noch nicht.
Wirtschaftsingenieure sollten das wissen.
Das sind ganz interessante Geschäftsideen, die man darauf aufbauen
kann, weil man eben dynamisch, on-demand Services anbieten kann, für
die man unterschiedlich die Rechenleistung braucht, ohne konkret
Investitionen in Hardware machen zu müssen.
Man zahlt nur dafür, was man tatsächlich nutzt.
Das ist ein Problem.
Es ist so, dass man natürlich...
Also es gibt schon gewisse Garantien, aber man weiß nicht, wo konkret
die Berechnungen ausgeführt werden.
Sie bieten also nicht nur Rechenkapazität an virtuell, sondern Sie
bieten auch Speicherkapazität an virtuell.
Sie können also auch Speicherplätze bieten, auch zum Spotpreis.
Sie wissen aber nicht, wo Ihre Daten sind.
Und das ist natürlich für die wirtschaftliche Anwendung sicher ein
Problem.
Wie kann ich gewährleisten, dass in einer virtualisierten
Rechnerinfrastruktur meine Daten auch mit dem entsprechenden
Vertraulichkeitsgrad gehandhabt werden, der erforderlich ist, damit
ich mein Geschäftsmodell tatsächlich sinnvoll ausführen kann.
Also das ist durchaus ein Problem.
Ich habe eine Frage.
Sie haben Copyright auf.
Sie haben also durchaus Copyright-Schutz für Algorithmen.
Das ist durchaus klar.
Richtig.
Ist so.
Das hängt zusammen mit Verlässlichkeit, mit Vertrauenswürdigkeit von
Diensten, die angeboten werden.
Und das ist ein Thema, das wir auch behandeln.
Wir versuchen seit zwei Jahren einen sogenannten EU4-Club einzurichten
für vertrauenswürdige, zertifizierbare Informatiksysteme.
Wo es genau um diese Problematik geht.
Wie kann ich einem Dienst, der mir angeboten wird, tatsächlich
vertrauen, dass er die Informationen so behandelt, wie ich das gerne
möchte.
Wie kann das gewährleistet werden?
Wichtige Thematik.
Aber das sind also interessante Fragestellungen in dem Zusammenhang.
Neben diesen algorithmischen Fragestellungen, wie kann man sinnvoll
solche dynamischen Rechnerstrukturen ausnutzen, sind das eine Reihe
von interessanten Fragestellungen, die man auch angucken muss, die
auch bearbeitet werden.
Aber die Zukunft für die Informationsverarbeitung liegt eindeutig in
diesen virtualisierten Welten.
Sie werden also im Wesentlichen Rechenleistung sich später abrufen.
Und vielleicht über ein kleines Gerät, das wie ein Rechner aussieht.
Oder einfach von der Handhabbarkeit ist so ein Notebook ganz
praktisch.
Aber ob die Rechenkapazität darin steckt oder ganz woanders ist, ist
völlig egal.
Es sollte egal sein.
Es sei denn, Sie haben ganz strikte Vertraulichkeitsanforderungen, wo
Sie sagen, dann mache ich das alles nur auf meinem Rechner.
Ich habe noch eine Frage.
Das ist überhaupt kein Problem.
Das ist kein großes Problem.
Die Bandbreiten werden ja immer größer und das ist nicht die große
Schwierigkeit.
Die Latenzzeiten können durchaus eine Rolle spielen.
Ich hatte vorhin gesagt, wenn Sie eine Nachricht verschicken wollen,
können Sie in der Zeit zur Vermittlung einer Nachricht, wenn Sie einen
Ping machen, zwischen zwei Rechnern, in der Zeit können Sie Millionen
von Berechnungen ausführen.
Millionen von Einzeloperationen.
Einfach weil Sie im Nanosekundenbereich Operationen ausführen, aber im
Minisekundenbereich halt Informationen austauschen zwischen Rechnern.
Das sind halt einfach zwei Größen, also 10 hoch 6 Unterschied in der
Größenordnung.
Und das ist halt einfach so.
Aber insofern muss man sich überlegen, für welche Anwendung setzt man
das sinnvoll ein.
Aber es gibt eine Vielfalt von Anwendungen, wo man das macht.
Führt uns aber auf ein völlig anderes Gebiet.
Ich wollte nur einfach darstellen, dass es hier unheimlich viele
Entwicklungen gibt, in denen man sich damit beschäftigt, wie kann ich
eigentlich die Ressourcen, die mir heutzutage zur Verfügung stehen,
sinnvoll einsetzen.
Dazu brauche ich geeignete Verfahren.
Da muss ich wissen, wie kann ich bei einem Verfahren eigentlich die
Kosten sinnvoll abschätzen.
Und damit beschäftigen wir uns bei effizienten Algorithmen.
Also, Entwurf und Analyse von Algorithmen.
Da haben Sie Entwurfsprinzipien kennengelernt.
Divide & Conquer, Dynamic Programming, Branch & Bout kennen Sie alle,
jetzt brauche ich nicht weiter darauf einzugehen.
3D-Algorithmen kennen Sie auch.
Scanline-Prinzip kennen Sie nicht.
Kennenlernen bei geometrischen Algorithmen.
Analyse der Algorithmen, da fragt man nach den Kosten eines
Algorithmus.
Also nach der Zeit, wobei wir uns normalerweise nur die Anzahl der
Programmschritte angucken.
Taktfrequenz oder Taktlänge.
Der Platz, Anzahl Speicherzellen ist klar.
Anzahl Prozessoren kann eine Rolle spielen.
Die Fläche ist durchaus wichtig.
Wieso ist die Fläche wichtig?
Also Sie haben meinetwegen hier eine Reihe von logischen Komponenten,
die wollen Sie einfach irgendwie miteinander verbinden.
Das ist ganz einfach zu machen.
Lineare Fläche, kurze Verbindungen.
Jetzt wollen Sie eine Verbindung machen, der soll mit dem noch
verbunden werden.
Der soll mit dem noch verbunden werden.
Der soll auch noch mit dem direkt da hinten verbunden werden.
Vielleicht soll der auch noch damit verbunden werden, der damit, der
damit.
Und Sie sehen, um das zu zeichnen, ohne dass sich alles überlagert,
brauche ich Platz.
Diesen Platz brauchen Sie auch, wenn Sie das auf Lithium darstellen
wollen.
Das heißt, wenn ich Kommunikation mache zwischen Strukturen, zwischen
irgendwelchen Bauteilen, brauche ich dafür Platz.
Leiterbahn, Platz.
Ich habe zwar eine Reihe von Schichten, die ich übereinander machen
kann, aber das ist begrenzt.
Und Sie brauchen einfach Platz, um bestimmte Dinge anordnen zu können.
Und deswegen muss man das genauer angucken.
Fläche ist teuer auf dem Lithiumchip.
Je mehr Fläche Sie brauchen, desto größer ist die Wahrscheinlichkeit,
dass Sie dort Verunreinigung haben.
Das heißt, hängt dann auch wieder mit der Zuverlässigkeit zusammen.
Das kann also bei Implementierung von Algorithmen direkt in Hardware
eine wichtige Rolle spielen.
Das Volumen kann eine Rolle spielen, wenn Sie 3D-Implementierung von
Algorithmen machen.
Wenn Sie dreidimensionale Schaltkreise haben.
Dreidimensionale Mikroelektronik hat man bisher praktisch nicht, aber
man ist immer noch daran, das irgendwann mal umzusetzen.
Kommunikationsbedarf hatte ich schon erwähnt.
Und das Ganze hängt natürlich ab von der Größe der Eingabe.
Es soll möglichst generisch sein, möglichst allgemein, damit ich auch
etwas allgemein aussagen kann und nicht mehr etwas sage für eine
spezielle Problemgröße.
Wobei ich bei, wenn ich also konkrete Anwendungen mache, da habe ich
vielleicht das Problem, dass ich eine effiziente Signalverarbeitung
machen muss auf Daten, die mit einer Bandbreite von 64 Bit pro Datum
ankommen.
Da muss ich auf diesen 64 Bit irgendeinen möglichst schnellen
Algorithmus machen, möglichst effizienten Filteralgorithmus oder
ähnliches.
Ich habe dann für eine konkrete Problemgröße auf einmal das beste
Verfahren zu suchen.
Und dann nützen mir diese ganzen asymptotischen Abschätzungen des
Laufzeitverhaltens von Algorithmen gar nicht mehr viel.
Da muss ich mir konkrete Problemgröße anschauen.
Also, Größe der Eingabe ist wichtig, Verhalten im schlechtesten Fall
und im Mittel spielt eine Rolle.
Manchmal spielt auch eine Rolle die attenuierte Komplexität.
Das heißt, ich habe 20 Berechnungen zu machen.
Wie ist der Aufwand für diese 20 Berechnungen?
Ich habe eine Menge von Aufgaben und der Gesamtaufwand dafür
interessiert mich, nicht der Aufwand für die einzelnen Berechnungen.
Das kann eine Rolle spielen.
Normalerweise schauen wir uns das Verhalten im schlechtesten Fall an.
Das brauche ich zum Beispiel, wenn ich Echtzeitanwendungen habe.
Sie bauen einen Algorithmus für ein Bremssystem, ein Fahrzeug.
Da müssen Sie in Echtzeit innerhalb eines gewissen Intervalls
garantiert das richtige Signal liefern.
Und da müssen Sie entsprechend wissen, wie ist das Verhalten im
schlechtesten Fall.
Verhalten im Mittel ist für andere Anwendungen, weil Sie also nicht
Echtzeit haben, durchaus sinnvoll.
Wissen Sie im Prinzip alles.
Jetzt kommen wir schon zur ersten, etwas formaleren Angabe.
Wenn wir also etwas über die Zeit sagen wollen, dann müssen wir etwas
sagen über einen Algorithmus mit irgendeiner Eingabemenge X.
Irgendwelche Eingaben, bei Matrizenmodifikationen sind das
irgendwelche Matrizen.
Und Sie haben irgendeine Größenfunktion.
Die Größenfunktion für Matrizen könnte sein die Anzahl der Elemente.
Dann wäre das für eine n-mal-n-Matrix n².
Sie können aber auch sagen, dass die Größe einfach nur n wäre bei
einer n-korts-n-Matrix.
Definitionssache.
Irgendeine Funktion, die nur etwas über die Größe sagt.
Und dann interessiert es Sie, wie die Rechenzeit bei Eingabe von X
ist.
Bei einer speziellen Eingabe.
Das wäre so die Rechenzeit eines Algorithmus A bei Eingabe eines
speziellen Matrizen oder beim Sortieren von irgendeiner sortierenden
Folge.
Jetzt wollen Sie aber nichts für einzelne Instanzen sagen, sondern Sie
wollen für bestimmte Problemgröße.
Sie haben jetzt folgende Länge 100.
Sie wollen wissen, wie lange dauert es maximal, wenn ich folgende
Länge 100 betrachte.
Deswegen haben wir dann eben die Rechenzeit im schlechtesten Fall oder
Zeitkomplexität von A im schlechtesten Fall als den maximalen Wert
über alle Eingaben einer gewissen Größe.
Und wenn Sie eine Wahrscheinlichkeitsverteilung gegeben haben, wenn
Sie wissen, wie die Eingaben verteilt sind, dann können Sie etwas
sagen über die mittlere Zeitkomplexität.
Zum Beispiel beim Sortieren wissen Sie, Quicksort ist gut im mittleren
Fall, aber nur wenn Sie eine Gleichverteilung annehmen.
Wenn Sie eine schlechte Verteilung haben, kann es sein, dass Sie damit
ganz schlecht landen.
Also Sie müssen etwas wissen über die Verteilung Ihrer Eingaben, dann
können Sie Aussagen machen über die mittlere Zeitkomplexität.
Und das Ziel ist natürlich, dass man etwas sagen kann über die
Qualität eines Algorithmus, wie gut ist der, im Vergleich mit anderen
Algorithmen zur Lösung des gleichen Problems.
Es ist klar, dass man das so macht.
In einigen Bereichen finden Sie manchmal Veröffentlichungen, dass
jemand für eine spezielle Problemstellung einen schönen Algorithmus
gemacht hat, der dort gut funktioniert hat, ohne einen Vergleich zu
liefern mit anderen Verfahren.
Dann sind aber diese Aussagen, hat gut funktioniert, völlig
irrelevant, weil Qualität immer etwas Relatives ist.
Das heißt, Sie müssen mit anderen Algorithmen vergleichen können zur
Lösung des gleichen Problems oder Sie haben untere Schranken zur
Verfügung und können sagen, ich brauche z.B.
für Sortieren mindestens so und so viele Operationen, das weiß ich,
geht nicht mit weniger und wenn ich daran direkt rankomme, dann habe
ich ein optimales Verfahren.
Dann weiß ich, das ist ein Algorithmus, der ist nicht nur recht gut,
der ist einfach optimal, denn es geht vom Zeitverhalten her nicht
besser.
Wir wissen, beim Sortieren können wir optimale Algorithmen angehen.
Sie kennen vielleicht diese Darstellung, wenn ich so Zeitvergleiche
mache.
Könnte in der Vorlesung Grundlage Informatik 1 gekommen sein oder auch
in sonstigen Informationswörtern schon mal.
Hier habe ich einfach mal diese typischen Abschätzungen oder Aussagen
über die Rechenzeiten zusammengestellt.
Stellen Sie sich vor, Sie haben vier verschiedene Algorithmen zur
Lösung des gleichen Problems.
Das sieht jetzt ein bisschen seltsam aus.
Wieso kann es sein, dass ich einen Algorithmus habe, der in
exponentieller Zeit läuft, für Eingaben der Länge n, 2 hoch n, und
einen anderen Algorithmus, der das in linearer Zeit macht.
Solche Beispiele gibt es.
Ein typisches Beispiel wäre die Berechnung von Fibonacci-Folgen.
Wenn Sie das nicht gut machen, haben Sie exponentielles Verhalten.
Wenn Sie es gut machen, haben Sie lineares oder sogar logarithmisches
Verhalten, wenn Sie es parallel machen.
Also das geht durchaus mit unterschiedlichem Zeitaufwand.
Das sind hier die Angaben allgemein für eine Problemgröße n,
meinetwegen in Millisekunden angegeben, Verhalten im schlechtesten
Fall.
Was uns normalerweise interessiert ist, was kann ich eigentlich
innerhalb einer gewissen Rechenzeit.
Ich habe ein Zeitbudget.
Jetzt möchte ich wissen, was ist eigentlich die maximale
Problemkomplexität, die ich in der Zeit bearbeiten kann.
Das heißt, ich gucke mir zum Beispiel an, was ist die maximale
Problemgröße, die ich in einer Sekunde bearbeiten kann, wenn ich diese
Algorithmen a1 bis a4 betrachte.
Wir stellen fest, der Algorithmus mit linearem Verhalten, 1000 mal n,
hat gerade Problemgröße 1, und der mit exponentiellen Verhalten hat
Problemgröße 9, und der mit 10n² hat Problemgröße 10.
Am besten in dem Fall.
Und es ist klar, wenn Sie an das andere Ende gehen hier, bei 10
Stunden Rechenzeit zur Verfügung, da haben Sie natürlich bei dem
linearen Algorithmus hier die größte Problemgröße und hier unten bei
dem exponentiellen die schlechteste Problemgröße.
Klar, Sie wissen, wie die Funktionen wachsen, aber es mag ja sein,
dass Sie nur ein spezielles Zeitbudget haben.
Und dann müssen Sie in diesem Zeitbudget den schnellsten Algorithmus
finden, zum Beispiel bei Echtzeitanforderungen.
Und da interessiert Sie nicht das asymptotische Verhalten, da
interessiert Sie ganz konkret das, was Sie in der Zeit machen können.
Und Sie sehen also, dass hier die Algorithmen jeweils optimal sind für
bestimmte Problemgrößen.
Also für einigermaßen große Probleme, n größer 101 oder größer gleich
101, haben Sie hier den linearen Algorithmus als besten.
Aber für sehr kleine Probleme ist der mit 2n besser, einfach deswegen,
weil der hier die kleinste Konstante hat.
Da muss man sich einfach nur bewusst sein, Aussagen über die Effizienz
oder die Eignung von Algorithmen für bestimmte Anwendungen sind nicht
nur über solche Wachstumsabschätzungen hier zu machen, sondern man
muss manchmal sehr konkret sich die einzelnen Ausdrücke angucken und
sehen, was da eigentlich passiert.
Hier ist nochmal so ein Beispiel von A4 und A3 angegeben.
Bei Größenordnung 10 sind A4 und A3 etwa gleich.
Bei Problemgröße 25 ist natürlich der exponentielle Algorithmus 5400
mal langsamer als der quadratische Algorithmus.
Das ist klar.
Und wenn man meint, das ist ja ein fiktives Beispiel, das kommt in der
Praxis nicht vor, schauen Sie sich an das typische Beispiel, Sie
wollen Polynomen auswerten.
Polynomen ist ja sowas, Summe a i x hoch i.
Und Sie machen das naiv, von links nach rechts.
Rechnen Sie a n mal x hoch n, das sind n Modifikationen.
Dann haben Sie hier a n-1 mal x hoch n-1, das sind n-1 Modifikationen.
Da haben Sie also die Summe von 1 bis n zu berechnen, um die Anzahl
der Modifikationen auszurechnen.
Kommen Sie auf n halbe mal n plus 1 Modifikationen und n Additionen
noch dazu.
Sehr viel, wenn Sie es von links nach rechts berechnen.
Wenn Sie das anders darstellen und das so von links nach rechts
berechnen, hier haben wir diese Klammerstruktur, dann geht es viel
einfacher.
Eine Modifikation, eine Addition, eine Modifikation, eine Addition
usw.
Sie haben n Modifikationen und n Additionen.
Eine andere Art, das zu berechnen.
Und Sie haben einmal einen quadratischen Algorithmus, einmal einen
linearen Algorithmus.
Also solche Dinge gibt es, Sie kennen es auch vom Sortieren, wo Sie
Unterschiede haben zwischen n² und n log n.
Also, wir reden häufig dann vom asymptotischen Aufwand.
Je nach Verfahren haben wir hier also in diesem Beispiel quadratisches
oder lineares Verhalten, O von n² oder O von n.
Arithmetische Operationen und jetzt habe ich gesagt asymptotisches
Verhalten.
Da muss ich nochmal kurz diese Begriffe darstellen.
Wie kennen die im Prinzip?
Ich wollte es nur noch einmal kurz wiederholen.
Also wir haben die Groß-O-Notation, irgendeine Funktion von n0 nach R.
Also irgendeine, im Prinzip eine beliebige PL-wertige Funktion.
Und wir sagen, die Klasse Groß-O von f enthält also alle Funktionen,
die nicht stärker wachsen, ab einer gewissen Größenordnung, also ab
einem gewissen n, als ein Standardmal dieser Funktion f.
Also alle Funktionen, die nach oben beschränkt sind durch c mal f von
n.
Ab einem gewissen n0.
Das ist unsere Abschätzung für eine obere Schranke.
Dadurch kann ich eine Aussage machen, wie stark also eine Funktion
wächst.
Das gleiche kann ich aber auch noch anders machen.
Es gibt auch ein kleines O von f.
Das kleine O von f sagt, dass f von n wesentlich stärker wächst als g
von n.
Also nicht nur so eine obere Schranke, die sich um eine Konstante
unterscheidet von dem f, sondern hier ist tatsächlich das f von n
wesentlich stärker als das g von n.
Das heißt, der Limus des Verhältnisses der beiden Werte ist eine
Nullfolge.
Das Ganze kann man auch andersrum sagen.
Da habe ich halt dann eine untere Schranke, Omega von f.
Da habe ich halt eine Funktion, also alle Funktionen, die mindestens
so stark wachsen wie das f.
Oder hier ist die Funktion bei dem kleinen Omega von f.
Da sind alle Funktionen drin, die deutlich schneller wachsen als
dieses f.
Also das sind untere Schranken.
Und dann gibt es noch die genauen Abschätzungen, gleiche
Größenordnung, Theta von f.
Das heißt, eine Funktion wird genau beschrieben durch diese Funktion f
im Lax-G.
Wir kennen diese üblichen Schreibweisen.
Eigentlich muss man sagen, g ist aus O von f.
Man schreibt häufig einfach Lax-G gleich O von f, wobei das natürlich
keine symmetrische Relation ist.
Also es ist das Groß-O von f enthalten in Groß-O von g. Aber natürlich
nicht...
oder es kann so sein.
Aber das heißt nicht, dass die beiden Funktionsklassen gleich sind.
Und mit konkreten Beispielen hinterlege ich...
Also es ist natürlich Groß-O von n² ungleich O von n.
Also gemeint ist eigentlich...
Also ich kann hinschreiben O von n gleich O von n².
Meine aber, das ist enthalten in O von n².
Die saubere Schreibweise ist diese hier mit dem Enthaltungszeichen.
Dann kann man eigentlich keinen Fehler machen.
Aber manchmal wird das so lax verwendet, muss man aufpassen, dass man
nicht da Dinge miteinander vertauscht.
Also diese Notation kennen Sie glaube ich alle aus Grundlagen der
Informatik 1.
Da sind solche Abschätzungen gemacht worden.
Vielleicht kennen Sie dort nur die Groß-O-Notation und nicht die
anderen.
Aber der Sinn ist einfach, dass man dadurch in der Lage ist, die
Größenordnung des Wachstums abzuschätzen.
Man muss dann nicht explizit sich die einzelnen Ausdrücke anschauen,
wie wir das hier auf der vorigen Folie hatten.
Hier, da haben wir solche Ausdrücke stehen.
Und da kann ich halt dafür sagen, dass Groß-O von n, Groß-O von n log
n oder n² oder 2 hoch n.
Das ist halt etwas einfacher, das so darzustellen.
Okay, das also zu diesem asymptotischen Wachstum von Funktionen.
Und damit ist eigentlich unsere Zeit für heute rum, das Viertel nach.
Wir kommen dann nächstes Mal noch kurz zum Abschluss dieses Kapitels,
wo wir dann etwas sagen zur Komplexität eines Problems oder einer
Funktion und noch ein bisschen mehr sagen.
Vielen Dank.