Mein Name ist Peter Sanders, ich werde die Vorlesungen halten und dort
stehen Timo Bingmann und Christian Schulz.
Genau, kann ich euch jetzt lasern?
Die machen die Übungen.
Es geht um Algorithmen und was das ist, wissen Sie wahrscheinlich
schon aus dem ersten Semester und ich werde gleich auch nochmal ein
bisschen was dazu sagen.
Gut, dann fangen wir mal langsam an, erstmal mit organisatorischen
Sachen.
Die Vorlesungen sind montags und mittwochs, immer hier im Audimax.
Wenn ich hier in die Runde gucke, bin ich darum sehr froh.
Ich glaube, vor so vielen Leuten habe ich noch nie vorgetragen, für
mich also auch was Besonderes hier.
Wir werden also montags im Allgemeinen Vorlesungen machen und
mittwochs 14.45 Uhr nur eine Dreiviertelstunde Vorlesung und dann eine
Dreiviertelstunde Übung.
Das hat sich aus meiner Sicht sehr bewährt, weil dann hat man nicht
immer so diese 90 Minuten Frontalgeschichten und man hat auch
vielleicht mehr Motivation, in die Übung zu gehen.
Bei der Saalübung wird es so sein, dass wir da verschiedene Inhalte
haben.
Das Wichtigste ist sicherlich Vertiefung des Stoffs aus der Vorlesung
mittels Durchgehen von Beispielen, Rechnen von Übungsaufgaben, aber
auch ein bisschen Blick über den Tellerrand, wo dann mal Anwendungen
erklärt werden oder der Stand der Technik ein bisschen beleuchtet
wird.
Wir sind da aber auch sehr flexibel, wir sind da ein bisschen auf ihr
Feedback angewiesen, können wir die Gewichte dann entsprechend
anpassen, was wir verstärkt machen, gerade in den Übungen.
Wir werden gelegentlich, ich bin zum Beispiel einmal verreist und es
gibt ein paar Feiertage und so, das ein bisschen anpassen, wann was
passiert.
Die erste Anpassung ist jetzt gleich zu Beginn, für die Übungen haben
wir eigentlich noch nicht genug Material, deshalb werde ich Mittwoch
komplett Vorlesungen machen.
Und dann ist die erste Übung erst am Mittwoch in der nächsten Woche.
Zu den Tutorien werden sicherlich die beiden gleich noch was sagen, da
muss ich jetzt über das Web und Skype wahrscheinlich nichts
Detaillierteres sagen.
Übungsblätter sagt ihr wahrscheinlich auch noch.
Sprechstunden habe ich jetzt für mich 13.45 bis 14.45 Uhr am Dienstag,
Timo und Christian haben auch Sprechstunden, ich weiß nicht, ob ihr
die noch individuell bekannt gebt.
Wenn bei mir die Tür offen ist, können sie auch jederzeit kommen, sie
können auch klopfen, aber dann habe ich meistens einen guten Grund,
wenn es zu ist oder ich bin sowieso nicht da.
Oder sie können halt auch einen Termin vereinbaren.
Es wird am 3.6., das ist ziemlich genau in der Mitte des Semesters,
eine Mitsemesterklausur geben.
Die hat jetzt keinen großen Status, die wird...
Oh, da gibt es eine kleine Inkonsistenz, wir haben gesagt zwei
Übungsblätter, hier steht 10% der Übungspunkte, passen wir noch an.
Dazu muss ich sagen, es gibt Übungsblätter, die werden auch
korrigiert, sie kriegen auch Punkte dafür und daraus ergeben sich
Bonuspunkte für die Klausur.
Also es ist nicht sehr hochgehängt, was sie da kriegen, aber diese
Mitsemesterklausur ist mir trotzdem sehr wichtig, weil das für sie
eine Möglichkeit ist, zu sehen, wo sie stehen.
Wenn sie bei dieser Klausur sehr wenig Punkte kriegen und am Ende
bestehen wollen, wissen sie, sie müssen sich stärker reinhängen, sie
müssen vor allem natürlich auch das, was sie am Anfang versäumt haben,
nacharbeiten.
Und wenn sie halt gut dastehen, ist es vielleicht erst recht eine
Ermunterung.
Das Wichtigste ist die Abschlussklausur, am 30.
Juli ist, denke ich, ein ganz angenehmer Termin, das Einzige ist, dass
da eine andere Klausur ist, die vielleicht für einige ein bisschen
ungünstig ist, irgendwie einen Tag vorher oder nachher, aber wir haben
da leider sehr wenig Kontrolle, für so eine Riesenveranstaltung gibt
es halt eine zentrale Planung der Hörsäle.
Trotzdem, wenn es mit diesem Klausurtermin irgendwie Riesenprobleme
gibt, weil da irgendwas übersehen worden ist, sollten Sie uns
möglichst bald darauf hinweisen.
Genau, wenn Sie dann nicht mitschreiben oder nicht bestehen, gibt es
halt in den Semesterferien nach dem Wintersemester 2013-2014 den
zweiten Termin für die Klausur.
So, jetzt etwas näher zum Inhaltlichen.
Materialien sind vor allem diese Folien, die auch schon im Web stehen
sollten.
Es gibt Übungsblätter, es gibt ein Diskussionsforum, ich denke, da
sagt Ihr auch noch mehr zu, den Link findet man auf der Homepage.
Eine gewisse Besonderheit dieses Kurses ist, dass ich auch selber ein
Buch geschrieben habe, das sehr nah an dem Kurs dran ist.
Das heißt, das habe ich geschrieben, bevor ich überhaupt angefangen
habe, Algorithmen 1 zu schreiben, trotzdem ist es nicht ganz zufällig,
dass dieses Buch, etwa zwei Drittel bis vier Fünftel von dem Buch ist
der Inhalt dieser Vorlesung.
Das heißt, Sie haben da Materialien, die eigentlich sehr gut passen.
Das Ganze ist auf Englisch geschrieben, allerdings gibt es eine
deutsche Übersetzung, die zwar noch nicht erschienen ist, aber wir
haben Ihnen die vorläufige Version auf die Webseite gestellt, Passwort
geschützt, aber Ihr gebt da gleich noch das Passwort an.
Und wir finden etwa ein- bis zweimal pro Jahr Schwarzkopien von dem
Buch im Internet ohnehin und das wird dann irgendwie an den Verlag
gemeldet und trotzdem möchte ich Sie bitten, das dann nicht irgendwie
gleich überall hochzuladen, weil wir dann Ärger mit dem Verlag
kriegen.
Also das sind so die Hauptmaterialien, wenn Sie ein bisschen was noch
Motivierenderes brauchen, ich hoffe, dass das auch so schon
motivierend ist, dieses Buch, gibt es so, um so einen Einstieg zu
kriegen in Algorithmen und warum das eigentlich ganz einfach ist und
warum das eigentlich ganz nah an unseren alltäglichen Erfahrungen auch
ist, dieses Taschenbuch der Algorithmen im Springer-Verlag, das ist
eigentlich eher so an, ich sag mal, Abiturienten oder sowas gerichtet,
die noch keinerlei Vorkenntnisse in der Informatik haben, aber
vielleicht trotzdem etwas, um da mal reinzuschauen.
So, dann gibt es noch weitere Bücher, die durchaus empfehlenswert
sind.
Weltweit das meistverkaufte Buch ist von Cormen, Leifersen, Reivist
und Stein.
Das ist so ein Trümmer von 1000 Seiten.
Das Witzige ist, da steht ungefähr genauso viel drin wie in unserem
300 -Seiten-Buch.
Also es gibt ein paar Zusatzkapitel, aber das ist sehr, sehr viel
ausführlicher geschrieben.
Das ist ein bisschen Geschmackssache, wenn Sie selbst Studium machen
wollen, sich das alles selber anlesen oder so, dann könnte es sein,
dass das Ding hier besser funktioniert.
Andererseits, wenn Sie eine Mathematikausbildung hier in Karlsruhe
genießen, sollte der relativ kompakte Stil unseres Buches für Sie
nicht so ein Problem sein.
Müssen Sie einfach ausprobieren, sich mal in die Bibliothek setzen, da
mal reingucken.
Dann gibt es noch ein anderes deutschsprachiges Buch von Ottmann und
Wittmeier.
Ganz witzig ist, dass die beiden auch in Karlsruhe mal waren, das habe
ich allerdings vor allem vorher angegeben, als es noch keine
deutschsprachigen Alternativen gab, und wer es noch kürzer gefasst
gerne hätte, der kann da dieses Algorithmen kurzgefasst von Uwe
Schöning sich besorgen.
Allerdings da fehlt es dann halt an vielen Details, die wir ja auch in
der Vorlesung machen, aber um so einen Einstieg zu kriegen und um das
Wichtigste zu lernen, ist das sicherlich auch ein sehr gutes Buch.
So, das wäre das Organisatorische von meiner Seite.
Gibt es jetzt direkt noch Fragen an mich, die nichts mit den Übungen
zu tun haben?
Es ist bei der Menge von Leuten sogar schon schwierig zu sehen, ob da
überhaupt ein Arm ist, aber ich möchte Sie bitten, sich trotzdem zu
überwinden, auch mal Fragen zu stellen.
Es wäre halt sehr schade, wenn wir hier nur reinen Frontalunterricht
machen, ja?
Ich würde fragen, ob es die erste Folie gibt?
Erste Folie noch mal zeigen, die da, genau.
Wenn Sie auf meine Homepage gehen, finden Sie das auch unter Studium
und Lehre, ist da die erste Zeile.
Die Ilias-Frage, könnt ihr die beantworten?
Ob die Folien ins Ilias kommen?
Ach so, die sind genau da.
Also worum genau geht es dabei, was findet man im Ilias?
Ich sehe jetzt nicht so ganz den Grund, warum wir das über eine dritte
Seite hosten, sondern Sie finden das auf unserer Homepage und da
können wir Ihnen vor jeder Vorlesung immer die aktuelle Version
hochladen.
Was allerdings passiert ist, dass die Artist das jetzt aufzeichnet und
Sie auch einen Soundtrack und Beamer-Bilder und sowas runterladen
können, aber das ist wieder was anderes.
Ich glaube, es gibt fünf oder sechs solche Plattformen am KIT, deshalb
bin ich da auch manchmal nicht völlig informiert.
Aber wenn es einen guten Grund gibt, das auch noch woanders
hochzuladen, können wir das gerne machen.
Ich habe jetzt nur noch nicht verstanden, wozu Ilias für uns besonders
wichtig ist.
Aber können Sie mir vielleicht nochmal per E-Mail erklären oder
nachher.
Weitere Fragen?
Okay, dann übergebe ich das Mikrofon jetzt an den Christian Schulz.
Also mein Name ist Christian Schulz.
Wir haben jetzt nochmal fünf Minuten organisatorische Sachen zur
Übung.
Hier ist der Workflow, wie das funktioniert bei uns mit den
Übungsblättern und den Abgaben.
Also es ist in der Regel so, dass mittwochs nach der Übung das
Übungsblatt rauskommt.
Dann gibt es neun Tage Zeit, bis man das Übungsblatt abgeben muss.
Und ein bis zwei Wochen später gibt es das dann korrigiert im Tutorium
zurück.
Das erste Blatt ist jetzt eine Ausnahme, das gibt es schon auf der
Webseite.
Hat das schon jemand gemacht?
Okay, hat noch keiner gemacht.
Ist jetzt auch nicht verwerflich oder so.
Genau.
Dann ist das so, dass die Übungsblätter dürfen zu zweit abgegeben
werden.
Das heißt, wenn ihr die Übungsblätter zu zweit abgeben wollt, dann
müsst ihr eine Gruppe bilden von Paaren.
Und die bleibt auch für das Semester bestehen.
Also ihr könnt dann nicht zwischendurch die Paare wechseln, wo ihr die
Übungsblätter abgeben wollt.
Genau, die Partner müssen im gleichen Tutorium sein.
Das ist ganz wichtig, da solltet ihr dann auch beim Webinscribe darauf
achten, dass ihr dort Gruppen bildet und dann auch im gleichen
Tutorium seid.
Das geht nicht über die Tutoriumsgänze hinweg.
Die Übungsblätter sollten ziemlich gut beschriftet werden, also ihr
müsst ganz groß und sichtbar eure Tutoriumsnummer draufschreiben, weil
wir sonst beim Sortieren eurer Übungsblätter in der
Tutorenbesprechung, also wir kriegen die halt einfach nicht sortiert
dann.
Wir brauchen dann hier Name, Matrikelnummer, Nummer des Übungsplatzes,
Name des Tutors und hier ganz, ganz wichtig, Nummer des Tutoriums.
Genau, hier ist der Workflow, wie man Bonuspunkte für die Klausur
bekommt.
Also ihr habt ja gerade schon mitbekommen, dass es in der Vorlesung
jetzt keinen Übungsschein gibt.
Also keine Prüfungsleistung an sich.
Was man aber kriegen kann, ist Bonuspunkte für die Klausur.
Das funktioniert folgendermaßen.
Also zum einen gibt es die Punkte für die Übungsblätter pro Blatt.
Jede Woche gibt es ein Übungsblatt und dann gibt es jeweils Punkte
dafür.
Dann kann man in den Tutorien Aufgaben vorrechnen.
Dafür gibt es maximal sechs Übungspunkte.
Man kann genau einmal vorrechnen, um Übungspunkte zu erhalten.
Und es gibt diese Mitsemesterklausur, die im Juni stattfindet und da
gibt es ungefähr Punkte für circa zwei Übungsblätter.
Diese drei Komponenten hier, das sind erstmal 100 Prozent der
Übungspunkte.
Und der Bonus, den man nachher durch die Klausur kriegt, das sind
echte Punkte, die man auf die Punkte addiert in der Klausur.
Die werden dann linear verteilt in Abhängigkeit davon, wie viel
Prozent man hat.
Das sehen wir auf der nächsten Folie gleich nochmal genauer.
Also maximal gibt es da vier Punkte.
Und dann haben wir noch eine Programmieraufgabe.
Das machen wir als Wettbewerb.
Da findet ein Wettbewerb statt, da kann man eine Tafel Schokolade
gewinnen, nichts für die Klausur.
Und wir haben Zusatzaufgaben, die sind ziemlich knackig.
Das ist in der Regel so, dass das einer von 400 löst, beziehungsweise
vielleicht zwei von 700 jetzt.
Aber die geben zusätzliche Übungspunkte, also man kann dann vielleicht
110 Prozent oder 105 Prozent haben oder sowas.
Wenn man 20 Prozent der Übungspunkte hat, von diesen 100 Prozent,
kriegt man einen Bonuspunkt für die Klausur.
Bei 40 sind es dann zwei, bei 60 drei, bei 80 vier.
Also wir denken, dass das relativ fair ist.
Man kann mit relativ wenig Aufwand wenigstens einen Bonuspunkt für die
Klausur kriegen.
Und ich denke, dass das auch die meisten von Ihnen machen werden.
...
Ja,
das ist richtig.
Dann haben wir ein Diskussionsforum, das kennen Sie wahrscheinlich,
dieses Ilias, da klickt man sich einfach durch, Fakultät für
Informatik, Sommersemester 2013 und dann Algorithmen 1 und dann könnt
ihr euch dort anmelden, Fragen stellen und dann ist das so, dass zum
einen wir Übungsleiter die Fragen beantworten und die Tutoren werden
da wahrscheinlich auch Fragen beantworten.
Lösungen posten ist allerdings verboten, also das sollte man dann
nicht unbedingt machen.
Genau, dann gibt es Tutorien, die Einteilung läuft wie immer, das
kennt ihr wahrscheinlich alle übers Webinscribe.
Genau, Abgabe zu zweit sollte man dort schon Gruppen bilden, das habe
ich eben schon gesagt.
Und die Tutorien finden das erste Mal nächste Woche statt.
Hier ist das Passwort und der Username für das Buch, das müsstet ihr
mitschreiben, weil später ist das nicht auf den Folien.
Okay, ich denke, das hat jeder.
Das war es im Wesentlichen von dem Organisatorischen, von meiner
Seite.
Persönlich würde ich euch noch ans Herz legen, die Übungsblätter
wirklich zu machen.
Das ist etwas, was sehr, sehr wichtig ist, weil anders kriegt man
keine Übung.
Ich glaube, unsere Klausur wird ziemlich voll mit Aufgaben und wenn
man da nicht richtig schnell nachher ist, dann sieht man da alt aus,
glaube ich.
Ich denke, man hat auf jeden Fall was.
Als ich an eurer Stelle war, vor neun Jahren, war ich immer alle
Übungsblätter gemacht.
Ich denke, es lohnt sich.
Ich kenne ein paar Leute, die haben das damals nicht gemacht.
Die sind auch gut, keine Frage, aber man hat was davon.
Wir geben uns da sehr viel Mühe, die Aufgaben zu machen und ich denke,
dass ihr hoffentlich auch was davon habt, wenn ihr die Übungsblätter
macht.
Also das war es von meiner Seite.
Vielen Dank, Christian.
Gibt es noch weitere organisatorische Fragen, bevor die beiden
verschwinden?
Ja.
Mitsemesterklausur ist am 3.
oder am 5.
Juni.
Scheinbar gab es da irgendwie eine Inkonsistenz.
Das ist die Pfingstwoche, das heißt... nee, ist nicht die.
Der richtige Zeitpunkt ist der dritte, sechste.
Und wer hat das falsch?
Ihr oder ich?
Okay, dritter, sechster ist die Mitsemesterklausur.
Weitere Fragen?
Die Frage ist, wie viele Punkte gibt es in der Hauptklausur?
Unter 100.000.
Also 60 Punkte gibt es in der Hauptklausur.
Also vier davon ist schon eine ganze Menge.
Das ist sowas wie eine Notenstufe, je nachdem, wo dann die
Durchfallgrenze liegt.
Dazu auch noch eine Bemerkung.
Irgendwas ist hier mit der Rückkopplung.
So viel ich weiß, ist es aus rechtlichen Gründen nicht möglich, diese
Bonuspunkte zum Bestehen zu verwenden.
Das heißt, es wird irgendeine Punktegrenze gehen, ab der Sie bestanden
haben.
Und wenn Sie die nur mithilfe der Bonuspunkte überschreiten, sind Sie
trotzdem durchgefallen.
Aber das ist jetzt so eine technische Sache.
Weitere Fragen?
Die Frage ist, ab wann man sich für die Tutorien eintragen kann?
Vermutlich ab Mittwoch.
Achso, das hat gerade jemand zu machen.
Ab morgen 18 Uhr?
Weitere Fragen?
Eine Frage war noch, Sie dürfen die Übungsblätter auch alleine
abgeben?
Das ist sicherlich weiterhin möglich.
Weitere Fragen?
Kann man die Folien auch online stellen?
Die Folien sind schon online, oder?
Die Folien von den Übungen kommen erst am Wochenende, hast Du gesagt?
Aber in der Regel ist alles online, das kann sich mal um eine Woche
verzögern, dass die aktuellste Version da ist, aber wenn das so ist,
machen Sie uns darauf aufmerksam, wir laden das so schnell wie möglich
hoch.
Ne, wenn die Übungsblätter in der Übung...
Und in der Übung am ehesten, wenn es irgendwie Probleme gab oder
sowas, wenn kaum jemand was rausgefunden hat oder so, dann redet Ihr
nochmal darüber.
Ist das korrekt so?
Weitere Fragen, da hinten?
Die Mitsemesterklausur kann man nicht nachschreiben, das tut uns leid.
Genau, das wird eine ganz witzige Veranstaltung, die machen wir hier
mit allen Teilnehmern.
Sitzen Sie so eng aufeinander, Sie kriegen dann jeder eine mehr oder
weniger individualisierte Klausur, sodass wenn Sie von den Nachbarn
abschreiben, Sie auch genauso gut die Antwort würfeln können.
Also das werden so Multiple-Choice-Aufgaben sein.
Weitere Fragen?
Okay, dann bedanke ich mich bei Christian und Timo.
Okay, äh, Algorithmen.
Ja, also manchmal rede ich mit Journalisten oder Freunden von meinen
Eltern oder sowas, und dann hat man so den Eindruck, dass die
überhaupt keine Ahnung haben.
Hat das was mit Logarithmen zu tun, kommt dann die Frage, oder kann
man das essen?
Also was ist das überhaupt für ein Wort?
Ich weiß nicht, inwieweit das in Grundbegriffe schon gemacht wurde.
Wer weiß das schon so richtig, wo das herkommt?
Traut sich zumindest nicht jeder, also mache ich es nochmal kurz.
Also es ist auch ganz interessant, weil das ziemlich kompliziert ist.
Also es gibt so einen Herrn, nachdem das eigentlich benannt ist, der
hieß sowas wie Al-Khawarizmi, und das ist eigentlich ein Usbeke
gewesen, oder kam jedenfalls aus der damals persischen Provinz
Khorasan, heute ist das halt in Usbekistan, lebte so 87 bis 840, aber
eben nicht in Usbekistan, sondern in Bagdad.
Das war damals kulturell so ein bisschen der Nabel der Welt.
Elite-Universität oder so hätte man vor zwei Jahren noch darauf
hingewiesen, heute verschwergen wir sowas ja lieber.
Und der hat ein Buch geschrieben über Rechnen.
Also so wie bei uns der Adam Riese, wie multipliziere ich zwei Zahlen
und so, und das sind halt Rechenverfahren.
Und damit wurde dann sein Name auch synonym benutzt mit dem Begriff
Rechenverfahren selber.
Im Europa hat man natürlich gedacht, das wäre ein Araber, war er gar
nicht, aber egal, konnte aber Arabisch auch nicht sprechen und hat es
dann so umgedreht, diesen Namen, dass das klingt wie ein griechisches
Wort, Algorithmus.
Und so ist dann dieses Wort entstanden, also es geht über Usbekisch,
Arabisch, Griechisch, hin zum, ja damals hat man ja Lateinisch
geschrieben oder so, also ziemlich viel stille Post dabei, ist also
einfach ein Wort.
Viel wichtiger ist natürlich, was ist ein Algorithmus, wo kommt das
Wort her, das ist aber ganz einfach, das ist eine Handlungsvorschrift
und das einzige, was man vielleicht vergessen könnte, ist, dass es
eine genau definierte Handlungsvorschrift sein soll und eben eine
Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten
Art von Problemen in endlich vielen Schritten.
Das ist das, was in Wikipedia steht und was ich auch finde, mehr muss
man dazu gar nicht sagen.
Aber was einem dabei schon klar sein sollte, aus meiner Sicht
zumindest, ist, wenn man jetzt Informatiker ist oder sich sonst wie
mit Computern beschäftigt, sollte es klar sein, dass das eine
Kerndisziplin ist.
Weil wenn Sie die ganzen Benutzeroberflächen-Gadgets von den Rechnern,
die wir benutzen, abziehen, dann bleibt innen drin ein Motor von
Rechneranwendungen und das ist, zumindest wenn das was nicht Triviales
ist, immer ein Algorithmus oder eben viele Algorithmen, die irgendwie
zusammenwirken.
Und deshalb sollte man als Informatiker eine gute Vorstellung davon
haben, was Algorithmik ist oder was Algorithmen sind.
Und wie man sie versteht, wie man sie erfindet und so weiter und das
ist Gegenstand dieser Vorlesung.
An dieser Stelle vielleicht auch noch eine Bemerkung, die ich nur in
dieser Vorlesung halten kann, oder das befürchte ich zumindest, die
Erfahrung in den letzten Jahren war, dass die
Informationswissenschaftler unter uns nicht der Meinung sind, dass
Algorithmen wichtig für sie sind.
Sie haben das zwar in Ihren Lichtveranstaltungsdings drin, schreiben
auch die Klausur mit mehr oder auch weniger viel Erfolg, aber wenn ich
dann die Vorlesungsevaluation am Ende sehe, dann habe ich da vier
Evaluationsbögen von Informationswirten, also so drei Prozent der
Informationswirte sind dann noch in der Vorlesung, während es bei den
Informatikern etwa 50 Prozent oder mehr sind.
Und da habe ich mich dann gefragt, woran liegt das?
Ich habe mich auch intensiv mit der Fachschaft unterhalten.
So eine richtige Antwort haben wir da nicht gefunden, weil ich hoffe,
klarzumachen, wir werden auch noch mehr Beispiele bringen, dass das
auch für Informationswirte sehr wichtig ist.
Natürlich kann es sein, dass Sie als Informationswirt am Ende einen
Beruf haben, wo Sie nicht selber programmieren und erst recht nicht
selber Algorithmen bauen müssen.
Wenn aber Ihre Konkurrenz plötzlich ein Produkt anbietet, das
tausendmal besser ist als Ihres und Sie gar nicht verstehen, was da
abgeht, weil der Kern von diesem Produkt nämlich ein Algorithmus ist,
an den Sie nie gedacht haben und wo Sie auch nie jemanden angeheuert
haben als großer Chef oder so, der vielleicht für Sie sowas baut, dann
sind Sie ganz schnell weg vom Fenster.
Also auch als großer Chef und Manager muss ich wissen, was ein
Algorithmus ist.
Gerade in so einer schnelllebigen und konkurrenzreichen Industrie wie
der Informationswirtschaft.
Und Algorithmen sind nämlich auch der Motor der meisten nicht
-trivialen Web-Anwendungen.
Das fängt schon an bei der Suche, zum Beispiel jetzt Google, also die
leben wovon?
Erstens Index-Datenstrukturen, die so schnell sind, dass man gewaltige
Datenmengen auf Knopfdruck untersuchen kann.
Zweitens Ranking-Algorithmen, die dafür sorgen, dass aus 500 Millionen
Treffern für Ihre Suche die zehn wichtigsten auf einer Seite
dargestellt werden.
Drittens Algorithmen zur Platzierung und Versteigerung von Werbung,
die Ihnen auch noch viele Milliarden Dollar pro Jahr einbringen.
Wenn Sie das nicht verstehen, wie das funktioniert, können Sie es
gleich lassen.
Deshalb hoffe ich, in dieser Vorlesung die Informationswirte diesmal
irgendwie bei der Stange halten zu können.
Und wenn irgendwie nicht klar ist, wozu was wichtig ist, bitte sofort
fragen.
Das gilt natürlich auch für alle anderen.
Also, was ist Algorithmik?
Man kann sich vielleicht die Informatik auch nochmal ganz grob als so
ein Schema vorstellen.
Worum geht es denn?
Es geht um effiziente und korrekte Software und Hardware.
Und was ist theoretische Informatik?
Na ja, ganz einfach, das sind die Grundlagen von effizienter und
korrekter Software und Hardware.
Und Algorithmik sind die Grundlagen effizienter Software und Hardware,
wohlgemerkt auch Hardware, ja.
Wir werden als allererstes über Multiplikationsalgorithmen reden, die
sind heute in der Regel in Hardware implementiert.
Und jetzt kann man hier vielleicht noch ein bisschen genauer schauen,
Algorithmen können auch was sehr Praktisches sein, sodass ich das
durchaus als Teil der praktischen Informatik teilweise auch sehe, dann
interessieren wir uns natürlich auch für Korrektheit, aber es ist halt
eher so, dass die Domäne von Logik, formale Systeme und sowas, wo es
halt auch eigene Veranstaltungen noch für gibt.
Dann gibt es hier so Bereiche der Theorie, die so weit weg von der
Praxis sind, dass ich sie halt gar nicht als Grundlagen davon sehen
würde und da, wo es dann bei den Algorithmen Richtung
Komplexitätstheorie geht, würde ich das auch zu diesen sehr
theoretischen Grundlagen zählen.
Aber was für uns jetzt wichtig ist, ist eigentlich dieser Bereich
hier, wir lernen hier in dieser Vorlesung zwar die Grundlagen, aber
diejenigen Teile davon, die wirklich in ganz vielen Anwendungen auch
benötigt werden.
Gut, und dann gibt es immer dieses Wortpaar Algorithmen und
Datenstrukturen.
In einigen Hochschulen gibt es dann auch separate Vorlesungen dafür.
Für mich ist das nicht so sinnvoll, also eine Datenstruktur ist ja was
sehr Statisches.
Und wenn Sie mit der was machen wollen, brauchen Sie immer einen
Algorithmus, der dann Operationen darauf durchführt.
Deshalb geht es eigentlich um Algorithmen und dann gibt es eben
Algorithmen, die ohne sehr komplexe Datenstrukturen arbeiten und
solche, bei denen Datenstrukturen wichtig sind.
Okay, also nochmal erklären, was sind denn Datenstrukturen überhaupt?
Das ist halt auch fast selbstverständlich, aber für mich ist natürlich
vieles hier selbstverständlich.
Wenn es da irgendwelche Fragen gibt, immer sofort nachfragen.
Also ein Algorithmus bearbeitet Daten, offensichtlich.
Wenn diese Daten nicht völlig platt im Speicher liegen, sondern
irgendwie eine Struktur haben, ich habe hier mal so ein Bild
gezeichnet, so einen Baum, wo also Objekte im Speicher liegen, die
über Zeiger miteinander verkettet sind, auf eine recht komplexe Art
und Weise, die es mir ermöglicht, bestimmte Operationen darauf sehr
effizient durchzuführen, dann nennt man das eine Struktur dieser
Daten.
Also immer wenn Daten in irgendeiner Form eine interessante Struktur
haben, dann kann man das eine Datenstruktur nennen.
Und wenn man so will, ist alles eine Datenstruktur, weil die Daten
liegen in einem linear adressierten Speicher, aha, das ist ein Array
und das ist eine Datenstruktur.
Und wenn Sie jetzt durch die Daten nur linear durchgehen und einmal
verarbeiten, dann wird man hier nicht von Datenstrukturen reden, aber
wenn Sie komplexe Sachen darauf machen, dann kann selbst ein Array
eine spannende Datenstruktur sein.
Wir werden das auch im zweiten Kapitel tatsächlich ein spannendes
Beispiel dafür sehen.
So, und diese Datenstrukturen und dazugehörige Algorithmen sind
tatsächlich wichtige Grundwerkzeuge der Informatik und insbesondere
natürlich der Algorithmik und das ist deshalb auch ein Namensgeber für
dieses Buch.
Im Englischen The Basic Toolbox und im Deutschen haben wir das jetzt
als Grundwerkzeuge übersetzt.
So, was sind denn diese Grundwerkzeuge?
Wie schon gesagt, immer wieder benötigte Datenstrukturen und
Algorithmen, aber darüber hinaus auch allgemeine Entwurfstechniken für
Algorithmen, die es Ihnen also ermöglichen, selber neue Algorithmen zu
entwerfen, und Analysetechniken, also wenn der Algorithmus schon da
ist, wie können Sie überhaupt verstehen, was der tut, wann der
effizient ist und so weiter.
Erlauben Ihnen also Leistungsgarantien oder einen objektiven Vergleich
von Algorithmen.
Und wichtig für die Vorlesung und auch für den Informatiker allgemein
sind alle vier Dinge und da muss man eben aufpassen, auf den ersten
Blick, ich habe immer wieder Leute getroffen, die gesagt haben, ihr
Buch oder ihre Vorlesung, das ist doch einfach eine Liste von
irgendwelchen Kochbuchrezepten, wie mache ich dies, wie mache ich das?
Aber das stimmt eben nicht.
Natürlich machen wir ein algorithmisches Problem nach dem anderen,
aber eben als Beispiele, um diese Sachen zu lernen.
Und ich werde auch immer wieder darauf hinweisen, aber man muss es
halt selber auch im Kopf behalten.
Nicht, wie hat er das jetzt gemacht, sondern was ist die Grundidee
dahinter, wie kann ich das in anderen Fällen anwenden.
Und auch da gilt, wenn ich da schuldig werde, zu sehr auf ein
spezifisches Problem einzugehen, ohne das Allgemeine zu beleuchten,
machen Sie mich darauf aufmerksam.
So, genau, diese Sachen braucht jeder Informatiker und deshalb ist es
halt auch eine Pflichtvorlesung.
Übrigens in den meisten Universitäten in Deutschland werden Sie das so
ähnlich finden.
So, konkrete Inhaltsübersicht.
Wir machen so Arithmetik-Geschichten als Beispiel, was ist das
überhaupt, nicht triviale Algorithmik, weil Sie das eigentlich im
zweiten Schuljahr schon gelernt haben.
Wie multipliziere ich zwei Zahlen und selbst das ist nicht so
offensichtlich, wie Sie es sich vielleicht vorstellen.
Dann so ein Werkzeugkasten für den Werkzeugkasten, Okalküle und so ein
Zeug.
Wie schreibe ich Pseudocode hin?
Das sind so zwei Einführungskapitel und dann geht es erst richtig los.
Erstmal mit Arrays und verketteten Listen und abstrakteren
Datenstrukturen, die darauf aufbauen.
Braucht man ständig.
Dann sozusagen eine erste nicht-triviale Datenstruktur, Hashtabellen,
wo Sie lernen werden, dass Chaos auch ein Ordnungsprinzip ist, was ich
meinem zweieinhalbjährigen noch nicht erklären kann, aber als
Fünfjähriger wird es da heftige Debatten geben, wo er mir dann
erklärt, Chaos ist doch gut und ich will nicht aufräumen und ich muss
ihm dann ein Recht geben und erst im nächsten Kapitel lernt man dann,
dass auch Ordnung was bringen kann.
Da lernen wir also, wie man Dinge sortiert und das ist vielleicht so
das kanonischste algorithmische Problem, dass die Informatik sich
angeschaut hat, was wirklich viele, viele Anwendungen hat, wie bringe
ich etwas in eine vorgegebene Reihenfolge.
Da kann man schon sehr viel dran sehen und darauf aufbauen werden noch
weiter fortgeschrittene Datenstrukturen eingeführt, die im Prinzip so
eine Verallgemeinerung der Sachen sind, die wir hier im vierten und
fünften Kapitel haben.
Also Caching sagt mir, wie lege ich etwas so ab, dass ich es
wiederfinde.
Mir wird eine Antwort darauf gegeben, die noch zusätzliche Operationen
erlaubt, aber sehr statisch ist.
Ich muss alle Daten am Anfang schon haben und dann mit den
Prioritätslisten und sortierten Listen wird das Ganze dynamisch.
Sie können dann die Menge der Objekte, die Sie verwalten, auch noch
ändern.
Und mit der sortierten Liste haben Sie dann eine sehr mächtige
Datenstruktur, mit der Sie fast alles machen können.
Also wenn man den Algorithmiker fragt, du musst auf die Insel gehen
und darfst nur eine Datenstruktur mitnehmen, und dann musst du
irgendwie eine große Anwendung implementieren, darfst aber nur eine
Datenstruktur verwenden für alles, dann wird der sagen, ja, dann nehme
ich die sortierte Liste mit.
Die ist nicht immer das schnellste, aber immer ganz nah dran und Sie
können ganz viele Sachen damit machen.
Kapitel drei bis sieben bilden damit sozusagen den Datenstrukturteil
dieser Vorlesung.
Sortieren können Sie als eine Vorverarbeitung für eine Datenstruktur
sehen.
Und es ist immer so, Sie haben einfache Objekte, die Sie irgendwie
organisieren, die aber keine weitergehende Struktur haben.
Und dann gibt es einen Block von vier Vorlesungen, wo wir uns eine
komplexere Objekte angucken, die Relationen zueinander haben, das sind
Graphen.
Das könnten in Anwendungen zum Beispiel Straßennetzwerke sein oder
Kommunikationsnetzwerke, aber auch viel abstraktere Dinge, die in der
Informatik immer wieder auftreten.
Und da lernen wir dann erstmal, wie man solche Graphen repräsentiert,
wie man wichtige Grundoperationen darauf durchführt und dann zwei
konkrete algorithmische Probleme, kürzeste Wege finden und minimale
Spannbäume finden.
Und dann gibt es ein letztes Kapitel, Optimierungsverfahren, wo man
dann insbesondere noch mal weitere Entwurfsmethoden kennenlernt, das
aber ein bisschen abstrakter ist als diese Sachen hier, wo man also
dann eine riesige Klasse von Problemen, die immer wieder in der
Informatik auftreten, kennenlernt und eben so Muster für Entwicklung
von Lösungen dafür.
Also ein klassisches Optimierungsproblem wäre zum Beispiel das
Handlungsreisendenproblem.
Da soll jemand eine gegebene Anzahl von Städten besuchen und möchte
eben möglichst wenig fahren dafür.
Da muss er die in der richtigen Reihenfolge besuchen und das ist ein
schwieriges Optimierungsproblem.
Wie gehe ich an sowas ran?
So,
gibt es noch Fragen zum Inhalt der Vorlesung, Algorithmik insgesamt?
Wenn es da irgendwelche Wünsche gibt, was Sie zum Beispiel noch
abgedeckt haben wollen oder sowas, können Sie das auch noch mal per E
-Mail oder so mir mitteilen.
Irgendwelche Fragen dazu?
Dann fangen wir jetzt mit dem Amüs Göhl an, dem Appetitmacher
sozusagen, Langzahlmultiplikation.
Das lernen Sie spannenderweise schon in der zweiten Schulklasse, wobei
das gar nicht so simpel ist.
Da investiert die Schule wirklich sehr viel Zeit darin, Ihnen
schriftliches Rechnen beizubringen.
Und heutzutage kann man sich fragen, brauche ich das noch?
Jeder hat einen Taschenrechner.
Möchte ich mich jetzt nicht so äußern?
Müsste man mal mit einem Pädagogen reden, aber schaden kann es
sicherlich nicht.
Und wenn irgendwie ein elektromagnetischer Puls sämtliche Rechner
zerstören würde, würden wir ganz schön alt aussehen.
Wenn wir noch nicht mal addieren könnten oder so.
Aber hier in der Informatikvorlesung muss ich natürlich schon ein
bisschen verallgemeinern.
Sie lernen im zweiten Schuljahr Arithmetik zur Basis 10, weil wir das
Dezimalsystem am Anfang lernen.
Als Informatiker wissen Sie vielleicht, dass das gar nicht das
einfachste denkbare System ist.
Die Basis 2 ist viel einfacher, allerdings wenn Sie sowas jetzt in
Software tatsächlich implementieren wollen, zum Beispiel eine
Arithmetik, die über die Wortlänge des Rechners hinausgeht, dann
wollen Sie vielleicht auch eine Basis haben, die eine andere
Zweierpotenz ist.
Zum Beispiel Basis 2 hoch 32 oder 2 hoch 64 oder sowas.
Deshalb mache ich das jetzt mal allgemein.
Eine Zahl schreiben wir als Ziffernfolge, höchstwertiger Ziffer
zuerst, ist halt so üblich.
Das ist übrigens auch was, was Sie, glaube ich, aus dem Arabischen
haben.
Die schreiben nämlich von rechts nach links.
Hätten wir das als Lateiner vielleicht andersrum machen sollen.
Das ist manchmal konsistenter mit der Art und Weise, wie wir an Text
und so rangehen.
Aber das ist nun mal so.
Aber da müssen Sie manchmal aufpassen, weil normalerweise schreibe ich
Rays oder Tuple, nummeriere ich andersrum.
Die fangen links an bei 1 oder 0 und gehen dann größer.
Aber bei Zahlen machen wir das halt so rum.
Und die Ziffern haben Werte zwischen 0 und Basis minus 1.
Genauso die Dezimalzahl besteht nicht aus den Ziffern 0 bis 10,
sondern aus den Ziffern 0 bis 9.
Und im einfachsten Fall ist B gleich 2, dann haben Sie die Ziffern 0
und 1.
Und wir werden die Algorithmen jetzt analysieren, nicht in irgendeinem
konkreten Maschinenmodell, sondern wir zählen die Anzahl
arithmetischer Operationen, die durchgeführt werden.
Das ist eine Abstraktion, die uns vieles vereinfacht.
Wir müssen dann nicht genau wissen, wie lange dauert was in dieser
Maschine.
Und wir haben auch nur zwei Operationen, das eine ist eine Addition,
allerdings eine sogenannte Volladdition, da addieren Sie nicht zwei
Ziffern, sondern drei.
Und heraus kommt auch nicht eine Ziffer, sondern zwei.
Weil wenn Sie 9 plus 9 rechnen, kommt da 18 raus, das können Sie nicht
als eine Ziffer schreiben.
Sondern es kommt eine Überlaufziffer heraus, das ist hier dieses C
-Strich.
Und andererseits ist klar, Sie müssen diese Überläufe auch irgendwie
weiterverarbeiten, deshalb gibt es auch drei Eingaben bei uns.
Das ist dieser Carry hier.
Und dann gibt es eine Ziffernmultiplikation, da werden also zwei
Ziffern multipliziert und raus kommt dann eine Zahl zwischen 0 und b-1
zum Quadrat.
Und dafür brauchen Sie dann auch zwei Ziffern, um das zu schreiben,
deshalb schreiben wir das hier als so ein Tupel auch.
Also diese Tupel sind immer so höherwertiger Teil, niedrigwertiger
Teil.
Gibt es dazu Fragen zu den Grundoperationen?
Okay.
So, Addition ist wirklich sehr simpel.
Das machen wir so, wie wir es in der Schule lernen, wir schreiben die
Zahlen untereinander, addieren die stellenweise, kriegen aber jeweils
einen Überlauf mit raus.
Also die unterste Stelle, da habe ich noch keinen Überlauf, da addiere
ich nur die beiden Zahlen und kriege die unterste Stelle meiner Summe
heraus und das hat nichts zu tun mit dem, was weiter links steht.
Hier könnte allerdings ein Überlauf entstanden sein und dann bei der
Ziffer mit der Wertigkeit 1 muss ich nicht nur die beiden Ziffern aus
a und b addieren, sondern auch den Überlauf, den ich vorher bekommen
habe.
Also so können Sie das jetzt lesen, jeder dieser Rechtecke hier ist
eigentlich so eine Volladdition mit zwei Eingaben von oben, nämlich
eine von a und eine von b, jeweils aus der darüber stehenden Stelle
und eine Eingabe von rechts, das ist der Überlauf aus der vorherigen
Operation.
Und die Ergebnisse müssen Sie dann nur so aufsammeln und das war es
schon.
Das können Sie jetzt auch als Pseudocode hinschreiben, hier sehen Sie
schon so ein bisschen meinen Pseudocode-Stil, der vielleicht noch ein
bisschen gewöhnungsbedürftig ist, deshalb mache ich am Anfang ganz
langsam und hoffe aber auch erklären zu können, warum ich das so mache
und nicht anders.
Das ist so ein Syntax, so ein bisschen wie Pascal oder Modular, weil
ich das typografisch viel schöner finde als C oder C++ und weil das
halt auch eine klare Abgrenzung gibt von echtem Sourcecode.
Wir arbeiten hier viel higher level, insbesondere haben wir neben
diesen Programmiersprachenspekten auch beliebige mathematische Formeln
als Teil des Codes und es sollte dann jeweils klar sein, was das
bedeutet.
Hier deklarieren wir eine Variable c vom Typ Ziffer und initialisieren
die auf 0.
Das ist dieses Carry-Bit, dieses Überlaufs-Bit oder Überlaufswert.
Dann iterieren wir von 0 bis n-1 und berechnen jetzt die i-te Stelle
des Ergebnisses als die Summe aus den i-ten Stellen der Eingaben und
dem Carry-Bit.
Oder dem Character-Carry-Ziffer.
Und dann gibt es eine n-te Stelle der Ausgabe, das ist dann der letzte
Überlaufswert.
Ich denke, das sollte relativ klar sein.
Wir können jetzt folgendem Satz n Ziffern zahlen, kann man mit n
solchen Volladditionen addieren.
Das klingt jetzt so, als wäre das die letztgültige Antwort, besser
geht es sicherlich nicht.
Aber hier sehen wir schon eine interessante algorithmische Challenge.
Wenn wir jetzt wirklich Zahlen mit vielen Milliarden Ziffern hätten
und wir wollen schnell Langzahl-Arithmetik machen, wäre das ein
Problem.
Weil da brauchen wir eigentlich parallele Algorithmen.
Wie addiere ich parallel?
Und es ist tatsächlich so, dass Sie das sogar in der Hardware dann
unten ja haben, dieses Problem.
Wenn es so wäre, dass die Addierer in Mikroprozessoren so addieren
würden, dann könnten Sie sich die Taktfrequenzen, die heutige
Maschinen haben, abschminken.
Da würden Sie bit-seriell addieren, das würde dann etwa 64 Mal so
lange dauern, wie es bei heutigen Rechnern dauert.
Das wäre schon eine ziemliche Einschränkung und da gibt es dann
ziemlich komplexe Schaltkreise im Prinzip zur Vorhersage von diesen
Überlaufwerten.
Weil Sie können diese komponentenweisen Additionen beliebig parallel
machen, aber Sie wollen die Überlaufwerte, die dann hier ganz
mittendrin entstehen, vorhersagen können aus den Eingaben.
Das geht, aber mit einem erheblichen schaltungstechnischen Aufwand.
So einen Addierer können Sie ja mit einer konstanten Anzahl Gatter
machen.
Wäre ein richtiger Volladdierer, da brauchen Sie glaub ich nLogN
-Gatter oder quadratische Fläche, das werden wir nicht in dieser
Vorlesung machen, aber ich will nur mal darauf hinweisen, selbst die
allereinfachsten Sachen, die man sich vorstellen kann, wenn Sie die zu
Ende denken für wirkliche Big-Data-Anwendungen oder so, oder massiven
Parallelismus, höchste Geschwindigkeit etc.
etc., Echtzeit, werden die plötzlich zu algorithmischen
Herausforderungen.
Und auch die Grenzen zwischen Software und Hardware verschwimmen dann
schnell.
Gut, addieren können wir jetzt zumindest in dem einfachen
Sequentiellen.
Gut, dazu noch mal ein bisschen Exkurs zum Pseudocode, ich hab da
schon ein bisschen was zu gesagt.
Ein anderer Grund, warum ich nicht diese C-artigen Syntaxe verwende
ist, es geht hier ja um Menschenlesbarkeit, nicht um
Maschinenlesbarkeit.
Allgemein sind Programmiersprachen ja nicht nur dafür da, dass der
Programmierer das lesen kann, sondern auch, dass der Compiler das
Ganze leicht parsen kann.
Spannenderweise ist das dann auch so, dass diese Syntaxgeschichten
haben sich dann schon in den 60er, 70er Jahren sehr stark verfestigt.
Und die Fähigkeiten, die heutige Rechner haben, werden da gar nicht
berücksichtigt.
Ob das so optimal ist, kann man sich dann auch mal fragen.
Jedenfalls haben wir uns entschlossen, für die Darstellung von
Pseudocoden ein bisschen reichere Typografie zu verwenden.
Und dafür andere Dinge, die eigentlich redundant sind, wie Klammern,
um irgendwelche Blöcke zum Material zu beschreiben, dass wir die auch
weglassen können und durch Einrückungen oder sowas darstellen.
Ja.
Ganz wichtig eben auch, wir benutzen mathematische Notationen, so
Mengennotationen, die halt viel mächtiger sind als
Programmiersprachen, um komplexe Sachverhalte auch mal auf einer Folie
darstellen zu können.
Ja, Zuweisung ist bei uns dieses Doppelpunkt gleich.
Kommentare sind wie in C, weil das ja eigentlich sehr übersichtlich
ist, genauer gesagt wie in C++ und C hat das dann irgendwann
übernommen als eine Option, glaube ich.
Ausdrücke können halt die volle Leistung der mathematischen
Notationen, also hier die Menge aller I größer gleich 2 mit der
Eigenschaft, es gibt keine A und B größer gleich 2, sodass I gleich A
mal B.
Was bedeutet das in Worten, kann mir das jemand sagen?
Die Menge der Primzahlen, genau.
Sowas in C hinzuschreiben würde halt irgendwie etwas länger dauern.
Deklarationen sind halt Variable, Doppelpunkttyp und dann gibt es
dazwischen noch eine mögliche Initialisierung, das ist halt Pascal
-Syntax.
Wir benutzen tuple in Zuweisungen, das können einige
Programmiersprachen auch, aber ich glaube nicht die gängigen, oder
kann Java das inzwischen?
Ich glaube auch nicht.
Schleifen, Vorschleifen, also irgendwas mit Index, While-Schleifen,
Tour solange eine Bedingung gilt, Tour, Repeat-Schleifen, das ist das
Do -While in C und Verwandtensprachen.
Und vieles, vieles mehr, im Buch steht das in Abschnitt 2, 3, ich
werde das hier nicht im Detail irgendwie unter einem Block vorführen,
sondern immer, wenn neuer Pseudocode kommt und ich irgendeine Notation
verwende, die wir noch nicht hatten, werde ich das kurz erklären.
Und wenn ich vergesse das zu erklären, bitte ich Sie sofort, Hand
hoch, Zwischenfrage, was bedeutet denn das?
Also wir haben so eine ganz rudimentäre Objektorientierung da drin,
Datentypen, Speicherverwaltung und so weiter und so fort, das muss man
alles noch erklären, aber da Sie sowieso schon programmieren können,
hoffe ich, dass das relativ einfach ist.
So, zurück zu unserem Beispiel, also addieren können wir jetzt, wir
wollen jetzt multiplizieren.
Und dafür machen wir erstmal was anderes Einfaches, wir multiplizieren
so eine Langzahl mit einer einzelnen Ziffer.
Das ist eigentlich auch ganz einfach.
Hier haben wir tatsächlich eine ziemlich einfache Art Parallelismus
erstmal drin, also wir multiplizieren einfach diese Ziffer B mit jeder
Ziffer von der Langzahl.
Unabhängig voneinander und das gibt dann n Paare von Ziffern, jeweils
höherwertig, lowerwertig, niedrigerwertig.
Da schreibe ich hier blau die niedrigerwertigen Teile der Ergebnisse
hin und hier rot die höherwertigen.
Und jetzt werden die einfach addiert und die Tatsache, dass das hier
die höherwertigen sind, der trage ich einfach dadurch Rechnung, dass
ich den um eine Stelle nach links schiebe.
Und das ist eigentlich schon alles, was ich tun muss.
Also ich addiere diese beiden Zahlen, dann kriege ich hier an der 0.
Stelle die Spezialität, dass ich da gar nichts tun muss, weil hier
eine 0 steht, am Endeffekt.
Und ab da ist das wie die normale Addition.
Jetzt habe ich das auch mal als Pseudocode hingeschrieben.
Das ist jetzt vielleicht auch ganz witzig, also das, was ich jetzt
erzählt habe, ist nicht ganz genau das, was hier in dem Pseudocode
steht.
Wenn Sie das 1 zu 1 umsetzen, hätten Sie so eine Schleife, die erstmal
alle diese Teilmultiplikationen berechnet.
Und dann hat man hier ein Eingabe-Array, ein Ausgabe-Array und noch so
zwei temporäre Arrays, alle der Größe n.
Und das könnte ein Platzproblem sein oder auch Cashfalls und sowas
erzeugen.
Deshalb würde man das in einem effizienten, sequentiellen Programm ein
bisschen anders machen.
Nämlich man hat nur das Eingabe-Array A und das Ergebnis-Array Result.
Hier haben wir jetzt zusätzlichen Pseudocode.
Was bedeutet das?
Also A ist eine Variable vom Typ Array.
Und ein Array ist ein etwas komplexerer Typ.
Einerseits müssen Sie da wissen, welche Komponenten sind da erlaubt.
Ich gebe explizit an, welche das sind, 0 bis n-1, also gebe ich die
Größe in diesem Fall auch schon vor.
Und die Elemente, die ich in dem Array speichere, haben selber wieder
einen Typ und das schreibe ich als Array of.
Und wir werden so ähnliche Sachen haben, das ist jetzt auch wieder
Higher -Level, das ist normale Sprache, so eine Art Generizität ist
dieses of.
Wir werden dann auch List of haben oder Set of, um solche generischen
Typen in einer übersichtlichen Art und Weise darzustellen.
Also wir haben ein Eingabe-Array, wir haben ein Ergebnis-Array, das
hat eine Ziffer mehr, weil wenn ich eine endstellige Zifferzahl mit
einer Ziffer multipliziere, kann im Allgemeinen was endlos
Einstelliges rauskommen.
So, und ansonsten habe ich nur skalare Variable, die einzelne Ziffern
speichern.
Und jetzt habe ich das so implementiert, dass dann trotzdem die
gleichen Berechnungen durchgeführt werden und was man hier beobachtet
ist, man geht halt wieder von rechts nach links durch und speichert in
diesen zusätzlichen Variablen eben nur das, was man später nochmal
braucht.
Und was wir hier sehen ist, wenn wir hier durchgehen, brauchen wir
eigentlich die bereits berücksichtigten Werte hier nicht mehr.
Man braucht nur noch die Überläufe, die es gegeben hat und man hat die
Endergebnisse abgespeichert und ansonsten braucht man immer nur
konstant viele Bits aus diesen Teilen.
Also das ist die Idee.
Und jetzt, wie mache ich das konkret?
Wie gesagt, ich habe das Ergebnis-Array, ich brauche eine temporäre
Variable c für diesen Überlauf, also einfach eine Ziffer, Überlauf
-Ziffer und ich habe Variablen h und l, die sozusagen high und low
Teil einer Multiplikation wiedergeben und das h habe ich allerdings in
zwei Formen.
Das h-Strich ist sozusagen der ältere high-Wert und das h ist der
neuere.
Wir werden noch sehen, wozu man das braucht.
Am Anfang mache ich sozusagen die erste Ziffern-Multiplikation, die
ich überhaupt brauche, da wird also die 0.
Ziffer mit b multipliziert und das Ergebnis ist in low-high
gespeichert, aber eben in diesem h-Strich.
Und ich weiß außerdem schon, dass das Ergebnis an der Stelle 0 ist,
wenn wir n-1 weitere Ziffern anschauen, niedrigwertige Ziffer zuerst,
jetzt wird einfach erstmal diese Multiplikation gemacht, also die i
-Ziffer wird mit der Ziffer b multipliziert, speichere das Ergebnis in
high -low und jetzt sehe ich auch, wieso ich das h-Strich brauche.
Das h-Strich brauche ich jetzt für die nächste Addition.
Das Ergebnis an der Stelle i ist jetzt einfach die Summe von h-Strich
und L.
Also das L ist halt... Moment... Also ich bin jetzt irgendwo hier in
diesem Array an der i-Stelle.
Und hier, was ich brauche, ist der niedrigwertigere Teil dieses Bits,
dann der höherwertige Teil aus der letzten Iteration, das ist gerade
das h-Strich, und den Überlauf vom letzten Mal.
Und deshalb hier Überlauf vom letzten Mal, höherwertiger Teil vom
letzten Mal und der niedrigere Teil von diesem Mal.
Und erst wenn ich das tatsächlich gemacht habe, kann ich das h-Strich
wegwerfen und dann durch dieses h auch ersetzen.
Also ich brauche immer zwei von diesen h-Werten und deshalb brauche
ich auch zwei Variablen dafür, h und h-Strich.
Der Rest ist eigentlich trivial, denke ich.
Ganz am Ende muss ich die höchstwertige Ziffer des Ergebnisses noch
berechnen aus der Summe von dem Überlauf und dem h-Strich.
So und jetzt könnte man fragen, aha, eigentlich ist das ja jetzt auch
wieder, ich muss ja irgendwelche Volladditionen machen und wenn das
hier beliebige Ziffern sind, zum Beispiel beides b-1, dann könnte hier
ein Überlauf passieren und dann hätte ich irgendein Teilergebnis, das
nicht berücksichtigt wurde.
Kann mir jemand sagen, warum das nicht auftreten kann?
Warum kann hier kein Überlauf stattfinden?
Sie haben gesagt, h-Strich ist höchstens die größte Ziffer?
Höchstens die zweitgrößte.
Also Sie argumentieren schon in die richtige Richtung, allerdings das
Problem ist, der Überlauf kann durchaus im Allgemeinen größer sein als
1, weil eine Volladdition hat ja als Ergebnis, als Eingabe drei
Ziffern.
Wenn Sie jetzt zum Beispiel im Dezimalsystem sind, dann könnten Sie
haben, 3 mal 9 ist 27, dann wäre der Überlauf ja 2.
Der Kollege bringt da gerade schon einen detaillierten Beweis, dem ich
nicht 100% folgen kann, aber das kann trotzdem richtig sein.
Also ich hätte jetzt argumentiert vom Endergebnis her, wir wissen ja,
was kommt denn hierbei raus?
Die größte Zahl, die hier entstehen kann, ist, wenn das alles b-1 sind
und das b hier auch und dann kann ich mal ausrechnen, wie groß ist die
Zahl und die hat höchstens n Stellen.
So würde ich argumentieren.
Aber wahrscheinlich kann man Ihre detailliertere Argumentation auch
irgendwie durchführen.
Aber das Wichtige ist hier, dass man so ein bisschen einen Blick dafür
kriegt, was kann eigentlich einem Algorithmus alles schief gehen?
Und was muss ich an zusätzlichen Dingen beweisen, damit ich sicher
bin, dass mein Algorithmus auch korrekt ist.
Also nur weil ich gesagt habe, dass wir Algorithmiker uns nicht so
sehr für die Korrektheit, sondern eher für die Effizienz
interessieren, heißt nicht, dass wir nicht als allererste
Voraussetzung immer haben, das Ganze muss natürlich korrekt sein.
Und wir werden auf irgendeinem Niveau auch immer wieder beweisen, dass
unsere Algorithmen korrekt sind.
Das wird auch eine große Rolle in der Vorlesung spielen.
Aber wir werden da nicht so viel Energie drauf verwenden, wie das
vielleicht Leute machen, die dann formale Beweise für komplette
Softwareprodukte bauen wollen.
Ja, genau, also wo wir uns dann noch mehr drum kümmern, sind so Sachen
wie Analyse.
Wie gesagt, hier geht es ja um die Anzahl Operationen.
Wir haben hier eine Multiplikation, hier n-1 mal eine Multiplikation
sind insgesamt n Multiplikationen.
Wir haben hier jeweils eine Volladdition und dann hier nochmal eine,
das sind also auch n.
Also wir haben n Multiplikationen und n Additionen.
Nicht so schwierig.
So, der spannende Teil fängt jetzt natürlich erst an, wie
multipliziere ich?
Und das ist vielleicht auch noch langweilig, insofern, als Sie es halt
wie gesagt in der zweiten Schulklasse schon gelernt haben, aber wann
haben Sie das das letzte Mal gemacht?
Wer hat mehr als drei Jahre lang keine schriftliche Multiplikation
mehr gemacht?
Die meisten, ne?
Also ich habe es zufällig letztens mal gemacht, einfach um das mal zu
machen, aber wahrscheinlich hat es auch mehrere drei Jahresintervalle
gegeben, wo ich es nicht gemacht habe in meinem Leben.
Also wie geht das?
Wenn ich diese Multiplikation mit einer Ziffer kann, ist das
eigentlich tatsächlich ein trivialer Algorithmus.
Eigentlich ist das eine ziffernweise Multiplikation.
Wir haben also unser Endergebnis P für Produkt, wir fangen wieder mit
der niedrigstwertigen Ziffer an, multiplizieren die mit der
niedrigstwertigen Ziffer von B, also wir wollen A und B
multiplizieren, multiplizieren die niedrigstwertige Ziffer mit A,
kriegen ein Ergebnis, dann nehmen wir die zweitniedrigstwertige,
multiplizieren das mit A.
So, und wie wird das jetzt zum Gesamtergebnis zusammengebracht?
Naja, wir schieben das hier um B nach links und addieren das zum
Ergebnis, das wir vorher hatten.
Und so geht das weiter.
In der I-Iteration multiplizieren wir, in der J-Iteration
multiplizieren wir A mit der J-Ziffer von B und schieben das Ganze um
J -Stellen nach links.
Ich habe das hier mathematisch durch eine Multiplikation mit B hoch J
dargestellt, aber das sollten Sie jetzt nicht so lesen, oh, jetzt muss
er noch einen Potenzierungsalgorithmus angeben und hier komplizierte
Sachen machen, sondern eine Multiplikation mit B hoch J ist halt
einfach ein Verschieben.
Und da wir nur die arithmetischen Operationen zählen, ist das
sozusagen umsonst, weil das kann man ja durch Umkopieren im Speicher
erreichen.
Frage dazu?
Die Frage war, ob man das Schema auch nutzen kann, um eine Zahl zu
faktorisieren.
Ich glaube eher nicht, weil faktorisieren irgendwie ein schwierigeres
Problem ist.
Jetzt kommt die Gegenfrage, die Frage ist, was ist faktorisieren?
Der Kollege meinte, wenn einer der Faktoren bekannt ist, dann kann man
vielleicht tatsächlich so ein ähnliches Schema nehmen und das ist eben
tatsächlich schriftliche Division.
Die sieht ja gar nicht so viel anders aus.
Also insofern kann man das umkehren, aber nicht zum Faktorisieren,
sondern zum Dividieren.
Okay.
Vielen Dank.
Wie gesagt, das kennen wir und das ist halt mit unserer jetzt neu
erworbenen Pseudocode-Kompetenz auch sehr kompakt hinschreibbar, das
sind im Endeffekt nur drei Zeilen Code.
Und ist ziemlich genau das, was man bei der Schulmultiplikation macht.
Es gibt einen winzigen Unterschied, also wenn man wirklich schriftlich
multipliziert, ist das ja so, dass man hier einfach die Zahl jeweils
drunter schreibt und dann hier eben so spaltenweise addiert.
Aber das macht jetzt keinen so riesigen Unterschied, während wir hier
zeilenweise addiert haben.
Aber die Anzahl der Operationen bleibt im Endeffekt die gleiche.
Okay, jetzt können wir das als Beispiel nehmen, wie analysieren wir
als Algorithmiker so einen Algorithmus?
Naja, wichtig ist, in der j-Iteration haben wir es mit Zahlen zu tun,
die n plus j Ziffern haben.
Wir haben hier eine Addition von zwei Zahlen, die zwar n plus j
Ziffern haben, aber, gucken wir uns das mal an, also wir sind zum
Beispiel in dieser Zeile hier, dann haben wir ein Teilergebnis, das
ist so groß, das fängt hier an, geht bis ganz rechts, aber wir fangen
irgendwo mittendrin an zu addieren.
Und was hier steht, interessiert uns gar nicht, das bleibt einfach
stehen.
Deshalb genügt uns, also wir sind jetzt ziemlich geizig, wir zählen
wirklich jede Operation, also genügt uns tatsächlich eine Addition von
Zahlen mit n plus 1 Ziffern, um unser Ergebnis auf den neuesten Stand
zu bringen.
Und dann gibt es hier diese Multiplikation, das braucht eben n
Additionen und Multiplikationen, also das ist diese Multiplikation mit
einer Ziffer.
Und dann gibt es dieses Verschieben, das ist umsonst, weil keine
arithmetischen Operationen durchgeführt werden, sondern irgendwie so
Speicherzugriffsoperationen, die wir hier gar nicht zählen.
Wenn man das zusammenrechnet, haben wir n Quadratmultiplikationen und
n Quadrat plus...
wie komme ich da drauf?
Genau, also diese n Quadratmultiplikationen, die stecken eigentlich
hier drin, das sind ja...
Genau, wir haben n Iterationen von dieser Schleife und hier jeweils so
eine Ziffernmultiplikation der Länge n, die braucht n Multiplikationen
und n Additionen, macht insgesamt n Quadratmultiplikationen und
Additionen für diese Zeile hier.
Und dann haben wir noch diese Additionen, das sind n minus 1 mal n
plus Additionen, weil ich habe ja n plus 1 Additionen pro
Schleifendurchlauf, aber ich muss nicht in jedem Schleifendurchlauf
tatsächlich addieren, weil am Anfang ist das p gleich 0, im ersten
Schleifendurchlauf ist das umsonst.
Also eine sehr geizige Interpretation zeigt uns, dass wir drei n
Quadrat minus 1 Ziffernoperationen haben und das ist wirklich dann
ganz genau.
Fragen dazu?
Also nach dem Stil funktionieren Analysen, wir werden nur bei
komplexeren Algorithmen manchmal nicht ganz so genau hinschauen und
dann konstante Faktoren oder sowas unter den Tisch falten lassen.
Aber ansonsten funktioniert so Algorithmenanalyse und das ist jetzt
unser erstes Beispiel und ich denke, das haben Sie nicht in der
zweiten Schulklasse gelernt.
Also insofern haben Sie da auch schon ein bisschen was, wo Sie ein
bisschen aufpassen müssen.
Wie gesagt, wollen wir später nicht ganz so genau sein und ein
mathematisches Hilfsmittel dafür ist das O-Kalkül und das kennen Sie,
glaube ich, auch schon aus dem ersten Semester.
Wer kennt das noch nicht?
Darf ich kurz fragen, wieso Sie es nicht kennen?
Kommen Sie irgendwo von anderen?
Vielleicht haben Sie nicht aufgepasst, gut.
Trotzdem finde ich das mutig, wenn jemand sich meldet, weil manchmal
stelle ich da auch Fragen, wo ich mich vertue und dann geht keiner
Hand hoch und am Ende merken wir in der Übung, dass es keiner kann.
Und dann nützt das niemandem.
Worst case ist, wir merken es in der Klausur.
Oder wir merken es dann bei der Klausurkorrektur, Sie merken es bei
der Klausur.
Das wäre nicht so schön.
Gut.
Nochmal formal, wir werden dazu auch ein paar Übungen noch machen.
Formal ist O von F von N, eine Menge von Funktionen.
Nämlich die Menge aller der Funktionen, der Eigenschaft, dass es eine
Konstante größer 0 gibt, sodass für hinreichend große N, nämlich alle,
die größer sind als ein entsprechendes N0, gilt G von N kleiner gleich
C mal F von N.
Aber wie gesagt, das kennen Sie hoffentlich.
Für mich ist jetzt wichtig, warum brauchen wir das in der Algorithmik.
Und der Trick ist eigentlich der folgende, wir wollen konstante
Faktoren und das Anfangsstück so einer Funktion unter den Tisch fallen
lassen.
Und das ist wichtig, weil meistens wollen wir bestimmte
Schlüsseloperationen zählen, wie hier die Arithmetik-Operationen und
alles andere unter den Tisch fallen lassen.
Zum Beispiel Speicherzugriffsoperationen oder Kontrollschluss.
Und wenn wir die Auswahl der gezählten Operationen richtig machen,
also da nicht irgendwie einen inneren Loop vergessen oder so, dann ist
das auch gerechtfertigt, aber wir können halt die konstanten Faktoren
der Ausführungszeit nicht genau bestimmen.
Wir zählen halt nur einen Teil dessen, was passiert.
Wenn wir aber das O-Kalkül verwenden, lassen wir das ja ohnehin unter
den Tisch fallen.
Das passt gut zusammen.
Wir wollen mit diesen Ergebnissen weiterrechnen und dafür müssen wir
die irgendwie vereinfachen.
Das geht gut mit dem O-Kalkül.
Und wir wollen auch die Interpretation am Ende vereinfachen.
Zum Beispiel, wir sagen jetzt im Wesentlichen, naja, die
Schulmultiplikation braucht O von n² arithmetische Operationen und O
von n² Zeit.
Und wenn wir dann einen anderen Algorithmus kennenlernen und der
braucht auch O von n², dann können wir sagen, naja, die sind
vielleicht ähnlich gut.
Wenn wir aber einen finden, bei dem da nicht n² steht, sondern n hoch
1,6 oder sowas, dann wissen wir, dass der asymptotisch für große
Eingaben irgendwann besser ist.
Und genau sowas möchte ich Ihnen nämlich vorführen.
Wahrscheinlich nicht mehr heute, aber am Mittwoch dann.
Frage?
Ja, da kam der Einwand.
Wir werfen Informationen weg.
Manchmal werfen wir auch zu viele Informationen weg.
Es gibt tatsächlich Algorithmen, da steht dann O von n hoch 1,6, aber
der Kollege sagte, was ist, wenn der konstante Faktor 10 hoch 100 ist?
Naja, dann war das wahrscheinlich ein Fehler, dann haben wir zu viel
weggeworfen.
Oder ein Theoretiker würde sagen, ist mir doch egal, Hauptsache das
ist asymptotisch besser.
Das kommt also sehr auf Ihren Standpunkt an.
Aber natürlich, wenn wir Sachen vereinfachen, dann können wir sie auch
übervereinfachen.
Wir sollten das immer im Hinterkopf behalten.
Insofern eine gute Bemerkung.
So, ich gehe jetzt anhand der Abschnittnummerierung im Buch, aber ganz
klavisch halte ich mich halt dann doch nicht dran.
Dieses Thema Ergebnisüberprüfung machen wir erst später ein Beispiel.
Tatsächlich lernen wir, glaube ich, auch in der Schule so Dinge wie,
wie mache ich so Prüfsummen, um herauszufinden, ob mein Endergebnis
korrekt ist.
Quersummen, Bildung und sowas kennen Sie vielleicht.
Aber das machen wir hier erstmal nicht.
So, jetzt zeige ich Ihnen mal einen, zumindest oberflächlich, komplett
anderen Algorithmus für Multiplikation.
Der zeigt, dass das halt nicht so vorgegeben ist.
Wir müssen nicht so rechnen wie vor 1200 Jahren.
Dann können vielleicht auch typische andere Design-Entwurfsmuster für
Algorithmen anwenden.
Und wir werden dann später sehen, dass eine kleine Variante davon
tatsächlich zu einem besseren Algorithmus führt.
Während es schwierig wäre, die Schulmultiplikation effizienter zu
machen.
Okay, also hier ist jetzt ein rekursiver Algorithmus zur
Multiplikation.
Und wir nehmen jetzt mal der Einfachheit halber an, dass wir 2k
Ziffern haben.
2k gleich n und n ist eine Zweierpotenz.
Dann geht das alles besser auf, das lässt sich immer irgendwie
verallgemeinern für andere Ziffernzahlen, aber na gut.
Ja, rekursiver Algorithmus braucht immer einen Basisfall.
Wenn wir einfach 2 Ziffern multiplizieren wollen, also n gleich 1,
dann ist das eine arithmetische Operation und wir machen das einfach.
So, sonst schreibe ich meine Zahl als...
Und jetzt haben wir zum ersten Mal das Problem, dass wir in diesem
Hörsaal keine Tafel haben.
Würde ich gerne da irgendwie an die Tafel malen.
Es gibt ja auch prima Software, mit der man in den Folien drin
rummalen kann, aber leider nur unter Windows.
Und leider so, dass man alles, was man da reinmalt, dann von Hand
wieder weglöschen muss.
Und da arbeiten wir noch dran.
Da gibt es dann Softwareprobleme jenseits der Algorithmik, mit denen
wir uns da noch beschäftigen müssen.
Genau, ist da jemand hier im Raum, der sich mit solchen Sachen zum
Beispiel auskennt?
Wir haben daran gedacht, uns modern, wie wir sein wollen, so ein
Notepad oder sowas zu holen.
Das könnte ich halt wirklich problemlos mit rumschleppen.
Das sollte allerdings in der Lage sein, diesen Beamer anzusteuern.
Sollte in der Lage sein, PDFs darzustellen, und zwar auch im
Vollbildmodus.
Es sollte einen Stift haben, mit dem man da drauf rummalen kann.
Und der sollte auch Funktionalität haben, die man brauchen kann.
Genau, das Ding da kennen wir, haben wir auch, ja.
Dankeschön.
Also was es gibt, sind vollwertige Notebooks, aber das läuft nur unter
Windows, oder?
Zumindest die Stiftsoftware, bei uns zumindest.
Ah ja, also wenn Sie mir da mal Pointer schicken könnten, weil genau
so ein Gerät haben wir eigentlich.
Das könnten wir dann tatsächlich auch verwenden.
Ja,
aber lassen Sie mich die letzten fünf Minuten noch erklären, wie
dieser Algorithmus funktioniert.
Das geht vielleicht hier auch noch ohne große Bildermalerei.
Eigentlich sieht man das hier auch an dem Bild schon, das ich gemalt
habe.
Also das A ist im Prinzip dieses Ding, und das teilen Sie in zwei
Hälften.
Das B ist dieses Ding, das teilen Sie in zwei Hälften.
Also einen höherwertigen Teil, einen niederwertigen Teil, mit jeweils
N halben Stellen.
Oder K Stellen in dem Fall.
Ja, wenn ich noch um zwei Minuten Ruhe bitten kann, und die schlauen
softwaretechnischen Hinweise bitte per E-Mail an mich und nicht per
Sprache an den Nebensitzen, dann können wir das auch zu Ende führen.
Gut, Basisfall ist klar, ansonsten teile ich die Dinger auf.
Das ist jetzt auch eine rein konzeptuelle Sache, kostet keine
Operationen.
Und wir multiplizieren die höherwertigen Teile, die niederwertigen
Teile.
Es ist klar, die höherwertigen Teile muss man um zwei K Stellen nach
links verschieben im Ergebnis.
Die niederwertigen Teile werden gar nicht verschoben.
Und dann gibt es noch so ein Kreuzding, also man muss den
niederwertigen Teil vom einen mit dem höherwertigen Teil vom anderen
multiplizieren.
Und umgekehrt, das Ganze wird addiert und um K Stellen verschoben.
Und dann werden diese drei Komponenten einfach zusammen addiert.
Man kann sich überlegen, dass das, was man da berechnet...
Wir hatten eben für die Schulmultiplikation dieses Rechteck hier.
Und im Endeffekt haben wir dieses Rechteck jetzt in vier Rechtecke
aufgeteilt, die genauso aussehen.
Also wir machen ungefähr die gleichen arithmetischen Operationen, aber
in einer anderen Reihenfolge.
Nebenbei gemerkt, in einer Reihenfolge, die für einen parallelen
Algorithmus supergut geeignet sind.
Also das lässt sich richtig gut parallelisieren.
Und kriegen dann wieder das gleiche Endergebnis wie vorher.
Das kann man auch analysieren, wir haben hier den Basisfall mit einer
Operation.
Dann wird es ein bisschen spannender.
Wir können jetzt nicht einfach sagen, so viele Schleifendurchläufe,
die multiplizieren wir mit der Anzahl Operationen darin.
Sondern wir kriegen jetzt eine Rekurrenzrelation.
Ein Aufruf für Genauigkeit n macht vier Aufrufe für Genauigkeit n
halbe.
Plus zusätzliche Operationen hier in den Additionen, die hier
stattfinden.
Man kann sich dann relativ leicht überlegen, dass wir dann so eine
Rekurrenz kriegen, wie T von n, also Anzahl arithmetischer Operationen
für Multiplikationen von zwei n Ziffern zahlen, ist kleiner gleich 4
mal T n halbe plus 6n.
Und man kann dann mögliche Übungen sich noch überlegen, ob man das auf
4n irgendwie drücken kann oder sowas.
Indem man genauer hinguckt, wo welche Additionen nötig sind.
Wie analysiere ich das?
Eine Möglichkeit ist Blackbox.
Wer kennt dieses Master-Theorem schon?
Das haben Sie ja so offenbar in den Grundbegriffen auch schon gemacht.
Hier eine schöne Anwendung dafür.
Wenn wir so eine Rekurrenz haben, können wir einfach nachgucken.
T von n ist Theta n hoch log zur Basis 2 von 4.
Und oh Wunder, das ist genau das gleiche wie beim Schulalgorithmus.
Wir haben andere im quadratischen Algorithmus gefunden.
Big Deal, können Sie sagen, was habe ich jetzt davon?
Vor allem, wenn ich hier die konstanten Faktoren nachverfolge, komme
ich irgendwie statt 3n² auf 7n².
Das könnte sein, dass das eine Ungenauigkeit in der Analyse ist, das
weiß ich nicht so genau.
Aber es könnte auch sein, dass ich tatsächlich ein bisschen mehr
Arbeit leiste.
Beim nächsten Mal werden wir dann sehen, naja, wir haben daraus schon
einiges gelernt.
Und wir können auf der Basis einen noch schnelleren Algorithmus bauen,
der tatsächlich sowas erreicht.
Und ich werde Ihnen erklären, wie das geht.
Vielen Dank.