Next:
Literatur
Algorithmen
Vorlesung im WS 2013/2014
Oliver Vornberger
Institut für Informatik
Fachbereich Mathematik/Informatik
Universität Osnabrück
Skript als PDF-Version
Literatur
Danksagung
Einführung
Informatik
Algorithmus, Programm, Prozess
Beispiele:
Anweisungen, Ablaufprotokoll
Elementare Anweisungen
Strukturierte Anweisungen
Beispiel für einen Algorithmus in umgangssprachlicher Form
Ablaufprotokoll (
trace
)
Java
Sprachmerkmale
Variablen
Kontrollstrukturen
Einfache Datentypen
Ganze Zahlen (
byte
,
short
,
int
,
long
)
Codierung
Operatoren
Konstantenbezeichner
Gleitkommazahlen (
float, double
)
Operatoren
Konstantenbezeichner
Boolean (
boolean
)
Codierung
Operatoren
Charakter (
char
)
Codierung
Operatoren
Typumwandlung
Konstanten
Felder
Feld von Ziffern
Feld von Daten
Feld von Zeichen
Feld von Wahrheitswerten
Feld von Indizes
Feld von Zuständen
Lineare und binäre Suche
Analyse der Laufzeit der linearen Suche
Analyse der Laufzeit der binären Suche
Klassenmethoden
Methodenaufrufe
Parameterübergabe an Arrays
Sichtbarkeit
Fehlerbehandlung
Rekursion
Fakultät, Potenzieren, Fibonacci, GGT
Türme von Hanoi
Komplexität, Verifikation, Terminierung
O-Notation
Analyse von
for
-Schleifen
Analyse von
while
-Schleifen
Analyse eines rekursiven Programms
Korrektheit und Terminierung
Halteproblem
Sortieren
SelectionSort
Bubblesort
MergeSort
QuickSort
Bestimmung des Medians
HeapSort
Zusammenfassung von Laufzeit und Platzbedarf
Untere Schranke für Sortieren durch Vergleichen
BucketSort
Objektorientierte Programmierung
Sichtbarkeit von Datenfeldern
Erste Beispiele
Binden
Referenzen
Wrapperklassen
Abstrakte Datentypen
Liste
Keller
Schlange
Baum
Suchbaum
AVL-Baum
Hashing
Offenes Hashing
Geschlossenes Hashing
Java Collection Framework
Collection
Map
Graphen
Implementation von Graphen
Graphalgorithmen für Adjazenzmatrizen
Implementation für gerichtete Graphen durch Adjazenzlisten
Traversieren von Graphen
Topologisches Sortieren
Kürzeste Wege
Hamiltonkreis
Maximaler Fluss
Implementation für ungerichtete Graphen durch Adjazenzlisten
Minimaler Spannbaum
Matching
Chinese Postman
Next:
Literatur
