Post on 05-Apr-2015
transcript
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