Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Gut, wir hatten uns ja gestern angefangen so mit Grafen zu beschäftigen und die

grundlegenden Begriffe dafür kennenzulernen. Erstmal überhaupt, was ist ein Graf, was ist

eine Kante, Knoten, was ist ein Weg in einem Grafen, was ist ein vollständiger Graf, was ist ein Schnitt

in einem Graf und all diese grundlegenden Konzepte, mit denen werden wir auch ein Großteil der

Vorlesungen auch arbeiten. Und heute wollen wir uns einen zweiten wesentlichen Aspekt, zumindest die

Grundbegriffe uns nochmal, darauf einigen, ist das eines Algorithmus, weil wir ja sozusagen der Fokus

ist für kombinatorische oder ganzteilige Optimierungsprobleme gute oder schnelle

Algorithmen kennenzulernen, die eben deutlich effizienter sind als das, was man klassisch

unter Enumeration versteht und einfach mal alle ausrechnen und ausprobiert. Und deswegen, das sind

so die zwei grundlegenden Begriffe. Es ist vielleicht auch ein Stück weit ein bisschen

ein anderer Zugang als man kennt aus den Vorlesungen, die man bislang hat, aus der

Analysis unter linearen Algebra, man häufig, sagen wir mal, dort erst mal Existenzaussagen hat, also auch

ein Großteil der Mathematik kümmert sich um Existenzaussagen, gibt es überhaupt eine Lösung

und nicht immer, wie kriege ich die tatsächlich. Ja, auch wenn sie mal so ein bisschen durch ihre

Skripte gucken, die sie bislang kennen, welche dieser Beweise sind konstruktiv und welche sind

es nicht, also zum Beispiel durch Annahme von einer Gegenannahme und dann sozusagen das zum

Widerspruch führen, das ist grundsätzlich erst mal kein konstruktiver Ansatz. Einige dieser

Beweise, die sie kennengelernt haben, sind konstruktiv, zum Beispiel Generierung einer Basis

in der linearen Algebra, das ist durchaus ein konstruktives Argument, dahinter aber bei anderen

ist es nicht so. Also was wir auf jeden Fall brauchen ist das Element der Konstruktion, weil

wir wollen ja nachher Lösungen tatsächlich generieren und das zweite, was wir eben anschauen

wollen, ist, uns reicht nicht an sich die Konstruktion selbst, sondern wie kriegen wir die möglichst

schnell und dazu schauen wir uns an, was sind denn die wesentlichen Schritte, die ich brauche,

dort hinzukommen und eine Schwierigkeit, die wir eben sehen werden, ist, die Schritte, die dazu

hinführen, müssen wir sehr feinskala runterbrechen auf kleine Einheiten, sprich, am Schluss werden

wir nur so etwas erlauben wie Addition und Vergleich und das ist das, was den Kern eines

Algorithmus eigentlich ausmacht, nämlich eine schrittweise Anleitung zum System, zu einer

Lösung von einem Problem, an dem ich ganz unten eigentlich nur Addition und Vergleich

erlaube. Es klingt jetzt sehr eingeschränkt, aber wir werden sehen, dass genau diese zwei

Elemente eigentlich reichen und im Wesentlichen alle Arten von Berechnungen dann auch tatsächlich

durchzuführen. Also das steht ein bisschen heute auf dem Programm und je nachdem, wie

weit wir dann kommen, schauen wir uns vielleicht auch schon mal die ersten Algorithmen an,

wo wir dann genau diese Prinzipien dann auch gleich schon mal üben können. Aber bevor

wir da einsteigen, gibt es zu gestern noch Nachfragen zur Definition, Grafen, Begrifflichkeiten,

die wir gestern uns da angeschaut haben. Gut, wenn das nicht der Fall ist, dann schauen wir

uns das eben an, was ist überhaupt in unserem Sinne ein Algorithmus, das ist das Kapitel

4.2, Algorithmen. Ich habe das im Skript als Exkursion betrachtet, aber nachdem sich doch

einige noch gar nicht sich da gedanklich auseinandergesetzt haben, würde ich sagen, lass mal Exkursion

weg und nimm es als durchaus Bestandteil mit auf. Ein Algorithmus, jetzt müssen wir uns

erstmal überlegen, bevor wir zum Algorithmus kommen, ich habe das ja schon immer so intuitiv

verwendet, dass ein Algorithmus eine Anleitung zum Lösen von einem Problem ist, jetzt müssen

wir uns natürlich erstmal überlegen, welche Art von Probleme können wir denn überhaupt

algorithmisch angehen oder mathematisch algorithmisch angehen. Wir können ja nicht jedes Problem

in dieser Welt sozusagen mathematisch formulieren und auch algorithmisch angehen, was weiß

ich, Beziehungsprobleme oder sonst was, wenn wir hier nicht behandeln können, da fehlt

uns sozusagen vielleicht der mathematische Zugang und vielleicht ist es auch gut so, dass

es da keinen mathematischen Zugang gibt. Also müssen wir uns erstmal darauf einigen, welche

Art von Probleme wir uns überhaupt anschauen und wir wollen uns formal auf solche Probleme

beschränken, die eine Fragestellung beinhalten mit offenen Parametern und einer Spezifikation