Jedes Programm verwendet Datenstrukturen und Algorithmen um seine Aufgabe zu erfüllen

Diese müssen offenbar zunächst sorgfältig dem speziellen Problem entsprechend ausgewählt werden

Hat man sich für solche D‘s und A‘s entschieden, müssen diese noch sorgfältig implementiert werden

Algorithmen, Java(Javac)…

Nach welchen Kriterien wählt man

Datenstrukturen und Algorithmen für ein

spezielles Problem?

Korrektheit (klar…) Laufzeit Speicherverbrauch

Für kleine Problemgrössen spielt die Laufzeit meist keine Rolle. Uns interessiert statt dessen die Laufzeit für grosse Probleminstanzen!

Daher analysieren wir häufig das Laufzeitverhalten nur für genügend grosse Eingaben (Grenzwertprozess!)

Dies motiviert die folgenden Wachstumsklassen:

o(f(n)): alle Funktionen die „langsamer wachsen“ als f O(f(n)): alle Funktionen die „nicht schneller wachsen“

als f (f(n)): alle Funktionen die „so schnell wachsen“ wie f (f(n)): alle Funktionen die „nicht langsamer

wachsen“ als f (f(n)): alle Funktionen die „schneller wachsen“ als f

Asymptotische Notation – Das Wachstum von Funktionen

}:{ 0 RNfF

Definition [1]: Für gF ist

)}()(::0|{)( 00 ncgnfnnNncFfgO

Sei die Menge aller Funktionen von N nach R0+.

)}()()(::0,|{)( 210021 ngcnfngcnnNnccFfg

)}()(::0|{)( 00 ncgnfnnNncFfg

)}()(::0|{)( 00 ncgnfnnNncFfgo

)}()(::0|{)( 00 ncgnfnnNncFfg

Häufig lassen sich die folgenden Sätze einfacher anwenden

als die Definitionen:

Bei iterativen Algorithmen ist es oft leicht, einfach die Anweisungen zu zählen

Die Analyse rekursiver Algorithmen führt hingegen meist auf eine sog. Rekurrenzgleichung

Dies ist eine Rekurrenzgleichung, denn T hängt vom Wert von T für

kleinere Eingaben ab!

Wie löst man Rekurrenzgleichungen?

Wir haben zwei Verfahren dafür kennengelernt:

• Substitutionsmethode

• Mastertheorem

Wir landen also bei den folgenden drei Fällen (a¸1, b>1, f(n)¸0):

(1) Ist

)()()(log

ab

nOnf für ein > 0, so gilt: )(log)( abnnT

(2) Ist

)()()(log ab

nnf dann ist: )log()( )(log nnnT ab

))(()( nfnT

(3) Ist

)()()(log

ab

nnf für ein > 0, und ist a f(n/b) ≤ c f(n) für eine Konstante c < 1 und genügend großes n, so gilt:

)()/()( nfbnaTnT

Erste Lücke

Zweite Lücke

Unbounded arrays (vector in C++) Listen (einfach verkettet, doppelt verkettet, zyklisch,

…) (Such-)Bäume und Wälder (binär, Rot-Schwarz,

AVL, …) Heaps (Binär, d-när, Binomial, Fibonacci) Graphen (gerichtet, ungerichtet)

Einfügen geht bei Heaps effizient (O(log(n)) Effizient Löschen können wir aber nur das

maximale Element (max-Heap) bzw. das minimale Element (min-Heap)

Auch die Suche ist nicht wirklich schnell

Wofür braucht man dann denn überhaupt Heaps?

• Heaps können gut sortieren (Heapsort)

• Heaps ergeben gute Priority Queues („intelligente ToDo-Liste“

mit den Operationen insert, maximum, extract_max)

Vielleicht die wichtigste und allgemeinste Datenstruktur der Informatik

Graphen verbinden Knoten über Kanten miteinander

Knoten und Kanten können jeweils Informationen tragen (z.B. Stadtnamen und Entfernungen)

Hamburg

Berlin

Dresden

Nürnberg

MünchenStuttgart

Saarbrücken

KölnFrankfurt

Mannheim

300 km

200 km

200 km

200 km

150 km

250 km

50 km

100 km

450 km400 km

300 km

200 km

200 km

BREITENSUCHE: TIEFENSUCHE:

ausgehend von einem Knoten v, durchsuche die von ihm erreichbaren Knoten in der Reihenfolge Ihrer Distanz von v

Steige immer so tief wie möglich in den Baum hinab, d.h. folge immer den Kanten des letzten „neu entdeckten“ Knoten.

v

u

x

w

y z

v

u w

v

x y z

u w

x y z

Beispiele für wichtige Graphalgorithmen:

Bestimmen der starken Zusammenhangskomponenten (basiert auf DFS)

Topologisches Sortieren (geht auch mittels DFS) Bestimmung des Minimum Spanning Tree; dies ist ein

Baum, der alle Knoten eines Graphen verbindet, und für den die Summe der Kantengewichte (geklaut aus dem Originalgraphen) minimal ist

Wichtiges Beispiel für einen Greedy-Algorithmus! (läuft immer in Richtung des aktuellen lokalen Optimums)

Bestimmen von kürzesten Pfaden, d.h. Pfaden mit minimalen Kantengewichten (SSSP, SDSP usw.)

It’s the current “hot” language It’s almost entirely object-oriented It has a vast library of predefined objects

and operations It’s more platform independent

this makes it great for Web programming It’s more secure It isn’t C++

Objektorientier Methodenbindung Javac(Compiler) Byte-Codes werden von der Java Virtual

Machine ausgeführt werden Applets Anwendung ist ein herkömmliches

Programm HTML zum Aufruf von Applets JDK(Entwicklungswerkzeuge)

Die. Class-Dateien vom Compiler erzeugten EXE-Dateien.

so kombiniert Java Compiler und Interpretation

Dieser Ansatz bietet Plattform-Unabhängigkeit und mehr Sicherheit

Javascript ist eine Erweiterung von HTML

Ein Folge von Befehlen Computer befolgt diese Befehle In eine Sprache, die den PC versteht

( Binär)

public class HelloWorld { public static void main(String[] args) {

System.out.println("Hello World!");

} }

int, double, boolean, char, byte, short, long, float

In C ist fast alles in Funktionen

In Java ist fast alles in Klassen

Es darf nur eine öffentliche Klasse geben (public class)

Der Dateiname muss der gleiche wie der Name des öffentlich-Klasse sein, aber mit einem. Java-Erweiterung

Kann nicht für sich allein ausgeführt Werden von HTML-Doc eingebettet Im Browser ausgewertet und

angezeigt(Lebensraum) Wird mit <applet> Tag aufgerufen. Hat keine main() Methode Hat fünf

Methode(int(),Start(),Paint(),stop(),Destroy())

Javascript HTML CSS PHP