| Prof. Dr. Hans Jürgen Ohlbach |
|
Lehr- und Forschungseinheit für
Programmier- und Modellierungssprachen
Institut für Informatik der Ludwig-Maximilians-Universität München |
| Last Modified: |
Diese Website enthält Miniskripten zu Themen der Informatik. Die Miniskripte sind in erster Linie für Studierende gedacht, die Informatik als Nebenfach haben. Sie eigenen sich aber auch als Einführungsliteratur für Hauptfachstudierende der Informatik. Jeder andere, der sich über einzelne Themen der Informatik informieren möchte, mag die Miniskripte gerne auch studieren.
Der Aufbau der Miniskripte richtet sich nach folgenden Prinzipien:
Es gibt wenig Literaturhinweise in den Miniskripten. Die Originalliteratur ist selten didaktisch aufbereitet. Dafür gibt es umfangreiche Lehrbücher und andere Literatur, die auch permanent erweitert wird. Es ist heutzutage sehr einfach, die passende Literatur zu finden.
Die Miniskripte entstanden im Projekt ZITAN des Digitalen Campus Bayern. Sie werden permanent erweitert und ergänzt. Es ist auch geplant, sie mit weiterem Lehrmaterial, insbesondere Übungsmaterial und Tutorial-Videos anzureichern.
Kommentare und Verbesserungsvorschläge bitte an o h l b a c h (AT) ifi * lmu * de schicken.
| Mathematisch/Logische Schreibweisen | Miniskript: Mathematisch/Logische Schreibweisen |
| Funktionen und Relationen | Miniskript: Funktionen und Relationen |
| Boolesche Algebra | Miniskript: Boolesche Algebra |
| Mengen | Miniskript: Mengen |
| Formale Sprachen | Miniskript: Formale Sprachen |
| Typ 3 Sprachen | Miniskript: Typ 3 Sprachen, Miniskript: Reguläre Ausdrücke |
| Typ 2 Sprachen | Miniskript: Typ 2 Sprachen, Miniskript: Kellerautomaten, Miniskript: Bottom-Up Parsing, Miniskript: ANTLR |
| Turingmaschinen | Miniskript: Turingmaschinen |
| Typ 0,1 Sprachen | Miniskript: Typ 0 und Typ 1 Sprachen |
| Berechenbarkeit | Miniskript: Berechenbarkeitstheorie |
| NP-Probleme | Miniskript: NP-Probleme |
| Digitale Arithmetik | Miniskript: Digitale Zahldarstellung und Arithmetik |
| Zeichenkodierung | Miniskript: Zeichenkodierungw |
| Komplexe Strukturen | Miniskript: Komplexe Strukturen, JSON, XML |
| Datenübertragung | Miniskript: Datenübertragung |
| Speichertechniken | Miniskript: Speichertechniken |
| Schaltnetze | Miniskript: Schaltnetze |
| Prozessorarchitektur | Miniskript: Prozessorarchitektur |
| Maschinensprache | Miniskript: Maschinensprache |
| Betriebssysteme | Miniskript: Betriebssysteme |
| Prozesse | Miniskript: Prozesse |
| Prozesserzeugung | Miniskript: Prozesserzeugung, Linker, Lader, Bibliotheken |
| Threads | Miniskript: Threads |
| Virtualisierung | Miniskript: Virtualisierung in Betriebssystemen |
| Filesysteme | Miniskript: Filesysteme |
| Programmierung | Miniskript: Programmierung allgemein |
| Primitive Datentypen | Miniskript: Primitive Datentypen |
| Listen | Miniskript: Listen |
| Arrays, Stacks und Strings | Miniskript: Arrays, Stacks und Strings, Binäre Suche in Arrays |
| Graphen | Miniskript: Graphen |
| O-Notation | Miniskript: O-Notation |
| Iteration, Rekursion | Miniskript: Iteration, Rekursion und Master Theorem |
| Hashing | Miniskript: Hashing |
| Gewichtete Graphen | Miniskript: Gewichtete Graphen |
| Sortieren | Miniskript: Sortieren |
| Union-Find | Miniskript: Union-Find |
| Bäume | Miniskript: Bäume allgemein |
| Baumsuche | Miniskript: Baumsuche (Breitensuche, Tiefensuche, Iterative Deepening) |
| Heaps | Miniskript: Heaps |
| AVL-Bäume | Miniskript: AVL-Bäume (binäre Suchbäume) |
| B-Baeume | Miniskript: B-Bäume (Suchbäume) |
| R-Bäume | Miniskript: R-Bäume (für multidimensionale Daten) |
Auch wenn in den Miniskripten weitgehend auf Formalismen verzichtet wird, sind einige mathematische Grundlagen, die über die Schulmathematik hinausgehen, notwendig und nützlich. Es werden jedoch selten formale Beweise geführt. Wer sich jedoch tiefer in Beweistechniken, insbesondere der Informatik, einarbeiten möchte, sei z.B. auf das Buch Design Patterns für mathematische Beweise hingewiesen.
Viele Texte der Mathematik und der Informatik benutzen die Sprache der Prädikatenlogik, um logische und mathematische Zusammenhänge auszudrücken. Diese Sprache sollte man zumindest lesen können. Die Komponenten der Sprache sind Junktoren wie nicht, und, oder,, Quantoren wie für alle und es existiert, sowie Variablen-, Funktions- und Prädikatensymbole. Daraus lassen sich Terme und Formeln bilden. In diesem Miniskript werden die verschiedenen Schreibweisen dieser Logik, sowie die rein logischen Rechenregeln dafür eingeführt. Die Semantik, d.h. die Bedeutung der Terme und Formeln, wird nur informell angedeutet. Sie entspricht jedoch weitgehend der Intuition. Einen präzisen mathematischen Begriff der Semantik wird erst dann benötigt, wenn man Aussagen über die Logik selbst beweisen will, z.B. die Korrektheit der Rechenregeln beweisen will. Das ist im Miniskript nicht vorgesehen.
Miniskript: Mathematisch/Logische Schreibweisen
Funktionen bilden Objekte auf Objekte ab, und Relationen beschreiben Beziehungen zwischen Objekten, die wahr oder falsch sein können. Funktionen und Relationen sind jedoch nicht nur von theoretischem Interesse, sondern sie werden ganz konkret in Programmen implementiert.
Im Miniskript werden zunächst Funktionen mit ihren Eigenschaften thematisiert: totale und partielle Funktionen, Argument- und Werttypen, und davon unabhängig Definitions- und Wertebereich, Kommutativität, Assoziativität, Distributivität, Injektivität, Surjektivität, Bijektivität, Isomorphismen. Funktionen kann man aus anderen Funktionen komponieren. Für Informatiker besonders interessant ist auch das Kapitel über die Berechenbarkeit von Funktionen.
Die Kapitel über Relationen behandeln, die Schreibweisen von Relationen, die Konstruktion von Relationen als Komposition, Inversen, Komplementen von anderen Relationen. Die Transformation von n-stelligen Relation in zweistellige Relationen wird angesprochen. Eigenschaften von zweistelligen Relation, wie Reflexivität, Symmetrie und Transitivität sollte man kennen. Äquivalenzrelationen sind ebenfalls ein wichtiges Konzept. Ein eigenes Kapitel ist den Ordnungsrelationen gewidmet, die insbesondere für Sortieralgorithmen gebraucht werden. Schließlich wird auch auf die verschiedenen Möglichkeiten der Visualisierung von Funktionen und Relationen eingegangen. Ein kurzes Kapitel am Ende erwähnt mögliche Datenstrukturen, mit denen man zweistellige Relationen speichern kann.
Miniskript: Funktionen und Relationen
Digitale Rechner arbeiten mit Bits, also 0 und 1. Die Theorie der Funktionen mit 0 und 1 ist die Boolesche Algebra. In dem Miniskript wird diese Theorie eingeführt, zunächst die Booleschen Funktionen, die Booleschen Terme, und dann die Rechenregeln und Algorithmen zur Herstellung von Normalformen für Boolesche Terme. Wichtig sind auch Verfahren, um Boolesche Terme zu vereinfachen.
Manche Boolesche Terme sind in sich widersprüchlich, z.B. ist p und nicht p widersprüchlich, egal ob p = 1 oder p = 0 gilt. Das Problem, einen beliebigen Booleschen Term auf Widerprüchlichkeit zu testen ist das SAT-Problem, für das es bisher keine effizienten Algorithmen gibt. Dieses Problem wird ebenfalls vorgestellt.
Weiterhin wird ein Verfahren vorgestellt, um Boolesche Funktionen aus Wertetabellen zu erzeugen. Dieses Verfahren wird zur Entwicklung von digitalen Schaltkreisen eingesetzt.
Ein weiteres Kapitel führt die Boolesche Mengenalgebra ein. Dabei sind die Werte nicht mehr 0 und 1, sondern Mengen. Ganz zum Schluss wird die Beziehung zur Aussagenlogik hergestellt.
Miniskript: Boolesche Algebra
In diesem Miniskript geht es nicht um die naive Mengenlehre, sondern um Eigenschaften von Mengen, die nicht explizit, sondern implizit über abstrakte Definition oder charakteristische Funktionen gegeben sind. Die angesprochenen Eigenschaften sind:
Miniskript: Mengen
Die Theoretische Informatik untersucht Probleme der Informatik auf abstrakte Weise. Sie bildet das Gerüst, innerhalb dessen konkrete Programme konkrete Probleme lösen können.
Formale Sprachen sind, i.A. unendliche, Mengen, deren Elemente durch einen Spezifikationsmechanismus definiert sind. Insbesondere gehören Programmiersprachen dazu. Jedes syntaktisch korrekte Programm einer bestimmten Programmiersprache ist ein Element der Menge dieser Programme. Damit ein Computer solche Programme analysieren kann, Syntaxfehler finden kann, und das Programm in lauffähigen Maschinencode übersetzen kann, muss die Programmiersprache formal definiert sein.
In diesem Miniskript wird ein Grammatikformalismus eingeführt, mit dem man u.A. auch Programmiersprachen definieren kann. Die Sprachen werden dabei in 4 verschiedene Typen eingeteilt, die die sog. Chomsky-Hierarchie bilden. Das Wortproblem wird eingeführt. Das ist das Problem, zu entscheiden, ob eine Zeichenkette ein Wort der Sprache ist, oder nicht. Jeder Compiler, der Programmcode analysiert muss dieses Problem lösen. Der technische Ausdruck dafür ist Parsing. Schließlich werden noch Syntaxbäume erläutert.
Miniskript: Formale Sprachen
Der speziellste Typ der Chomsky-Hierarchie sind die Typ 3 oder reguläre Sprachen. Sie werden durch spezielle Grammatiken definiert. Das Wortproblem kann durch sog. endliche Automaten gelöst werden. Es werden nichtdeterministische und deterministische endliche Automaten eingeführt, und gezeigt, wie man die nichtdeterministischen Automaten deterministisch machen kann.
Ein wichtiges Hilfsmittel zur Untersuchung von Sprachen ist das sog. Pumping Lemma für Typ 3-Sprachen. Damit kann man zeigen, dass eine Sprache nicht vom Typ 3 ist.
Miniskript: Typ 3-Sprachen
Ein weiterer Spezifikationsmechanismus für Typ 3-Sprachen sind die regulären Ausdrücke. Diese werden in einem weiteren Miniskript eingeführt. Dort wird auch gezeigt, wie man einen regulären Ausdruck in einen Automaten übersetzt. Reguläre Ausdrücke sind Bestandteil vieler Programmiersprachen. Als Beispiel werden die regulären Ausdrücke in Java vorgestellt.
Des weiteren werden sog. Abschlusseigenschaften diskutiert. Hier geht es darum, was entsteht, wenn man mehrere Typ 3-Sprachen auf verschiedene Weise miteinander kombiniert.
Miniskript: Reguläre Ausdrücke
Typ 2-Sprachen, oder auch kontextfreie Sprachen, sind der zweitspeziellste Typ in der Chomsky-Hierarchie. Die meisten Programmiersprachen sind als Typ 2-Sprachen, mit einigen Erweiterungen definiert.
Im ersten Miniskript werden die Typ 2-Grammatiken definiert, die sog. Chomsky-Normalform dieser Grammatiken, und das Typ 2-Pumping Lemma eingeführt. Damit kann man beweisen, dass eine Sprache nicht vom Typ 2 ist.
Miniskript: Typ 2-Sprachen
Im nächsten Miniskript werden Kellerautomaten eingeführt. Das sind endliche Automaten mit einem zusätzlichen Speicher, dem Keller oder Stack. Mithilfe von Kellerautomaten kann man Zeichenketten als Typ 2-Sprachen parsen.
Miniskript: Kellerautomaten
Im nächsten Miniskript wird Bottom-Up Parsing eingeführt. Im Gegensatz zu Parsen mit Kellerautomaten, bei dem man von der Startvariablen einer Grammatik ausgeht, geht Bottom-Up Parsing von der Wortebene aus, und baut rückwärts einen Syntaxbaum auf. Der typische Algorithmus dazu ist der CYK-Algorithmus.
Miniskript: Bottom-Up Parsing
Ein konkreter Parsergenerator, der eine Grammatik in einen Parser transformiert ist der in Java geschriebene ANTLR Parsergenerator.
Miniskript: Der ANTLR-Parser
Turingmaschinen sind eine bis auf das absolute Minimum vereinfachte Rechnerarchitektur. Ihre Einfachheit erlaubt, mathematische Beweise darüber zu führen. Die Church-Turing-These besagt, dass jede berechenbare Funktion auf einer Turingmaschine implementiert werden kann.
In diesem Miniskript wird zunächst die Einband-Turingmaschine eingeführt, dann die Mehrband-Turingmaschine als Modell für Parallelrechner, schließlich die universelle Turingmaschine, die jede andere Turingmaschine simulieren kann.
Miniskript: Turingmaschinen
In dem Miniskript werden die Typ 1- und Typ 0-Sprachen eingeführt, und gezeigt, wie man mit Turingmaschinen das Wortproblem lösen kann.
Miniskript: Typ 0 und Typ 1 Sprachen
Eines der faszinierendsten Problem, die die theoretische Informatik beschäftigt, ist das Problem: was kann man überhaupt berechnen, und was ist jenseits davon? Dazu muss man konkrete Berechnungsverfahren definieren, und untersuchen, was man damit berechnen kann. Leider gab es in den letzten Jahrzehnten kaum Fortschritt auf diesem Gebiet. Der Stand der Dinge ist immer noch, dass die Turingmaschine das allgemeinste Berechnungsmodell ist. Für eine Vielzahl alternativer Modell konnte man zeigen, dass die auch nicht mehr berechnen können als Turingmaschinen.
In diesem Miniskript werden verschiedene Berechnungsmodelle eingeführt, auch schwächere als Turingmaschinen, u.A. Loop-Berechenbarkeit. Eine Funktion, die nicht Loop-berechenbar ist, aber Turing-berechenbar ist die Ackermann-Funktion. Sie wächst ungeheuer schnell zu astronomischen Werten.
Ein weiteres Thema in diesem Miniskript ist die Unentscheidbarkeit des Halteproblems: Man kann kein Programm schreiben, welches andere Programme auf Endlosschleifen testet, und immer nach endlicher Zeit die korrekte Lösung findet. Der Beweis dazu ist ein Beispiel für einen Unmöglichkeitsbeweis mittels Diagonalisierungstechnik.
Miniskript: Berechenbarkeitstheorie
Berechenbare Probleme werden u.a. nach der Zeit eingeteilt, die benötigt wird, um das Problem, in Abhängigkeit von der Größe der Eingabe, zu lösen. In diesem Miniskript wird nach einem kurzen Exkurs in die Komplexitätstheorie die Klasse der NP-vollständigen Probleme behandelt. NP-vollständig bedeutet, dass zunächst das Problem in NP ist, d.h. mit einer nichtdeterministischen Turingmaschinen in polynomieller Zeit gelöst werden kann, und dann auch noch jedes andere Problem in dieser Klasse auf das Problem transformiert werden kann, so dass die transformierte Lösung zurück transformiert werden kann und das ursprüngliche Problem löst. D.h. das Problem ist NP-hart.
Das prototypische Problem in dieser Klasse ist das SAT-Problem, d.h. der Test auf aussagenlogische Erfüllbarkeit. Indem man zeigt, wie man eine nichtdeterministische Turingmaschine für ein NP-Problem in ein SAT-Problem umbaut, so dass dessen Lösung die Auflösung des Nichtdeterminismus ermöglicht, kann man beweisen, dass SAT NP-hart ist.
In dem Miniskript werden auch weitere NP-Probleme vorgestellt: 3SAT, Graph-Coloring, Rucksackproblem, Partitionsproblem, Bin Packing. Als Algorithmen werden vollständige und Random-Walk Ansätze zur Lösung dieser Probleme eingeführt.
Miniskript: NP-Probleme
Neben den rein logischen Operationen wie nicht und, oder, exklusiv oder auf Bitebene sind die Operationen mit Zahlen die wichtigsten Basisoperationen eines Computers. In diesem Miniskript wird die Zahldarstellung mit 32 und 64 Bits eingeführt, Integerzahlen und Gleitkommazahlen. Negative ganze Zahlen werden als Zweierkomplement dargestellt. Als Operationen werden die arithmetischen Operationen, die logischen Operationen auf Wortebene, und die Shift-Operationen eingeführt. Ein oft sehr nützliches Hilfsmittel ist die Maskierungstechnik, mit der einzelne Bits innerhalb von Bitsequenzen bearbeitet werden können.
Miniskript: Digitale Zahldarstellung und Arithmetik
In diesem Miniskript geht es um die Kodierung und Darstellung von Buchstaben. Es wird die ASCII-Kodierung, die ISO-8859-Kodierung, Unicode, UTF-8 und UTF-16 eingeführt. Dies sind die internen Kodierungen von Buchstaben. Für die Darstellung auf dem Bildschirm oder Drucker braucht man aus Glyphen aufgebaute Fonts, entweder in Bitmap- oder Vektordarstellung.
Miniskript: Zeichenkodierung
Zur Darstellung komplexer Strukturen, wie z.B. einer ganzen Website, wurden Standards entwickelt wie JSON oder XML. In diesem Miniskript wird neben JSON auch XML mit vielen seiner Varianten und Erweiterungen vorgestellt: DTD, XML-Schema, RELAX-NG, XLink, Xpath, XPointer, XSLT, XQuery.
Miniskript: Komplexe Strukturen, JSON, XML
Hier geht es um analoge und digitale Datenübertragung, Multiplexing, Signal und Rauschen.
Miniskript: Datenübertragung
Für die externe Speicherung von Daten wurden ganz unterschiedliche Techniken entwickelt, die in diesem Miniskript vorgestellt werden: Magnetspeicher, Bänder und Platten, Flash-Speicher, optische Speicher, CDs, DVDs, Blue Rays. Als Speichertechnik für interne Speicher dienen Flipflops (RAMs), die hier ebenfalls eingeführt werden.
Miniskript: Speichertechniken
Viele Komponenten eines Computers sind aus sog. Gattern aufgebaut. In diesem Miniskript werden die verschiedenen Gattertypen eingeführt. Dann wird erklärt, wie man mit Hilfe Boolescher Algebra die Gatter zu Schaltnetzen zusammenschalten kann. Als Beispiel für den Schaltungsentwurf werden Halbaddierer, Volladdierer und daraus ganze Addierwerke vorgestellt.
Miniskript: Schaltnetze
Die interne Architektur von Computern geht noch auf John von Neumann zurück, und wird daher als von Neumann Architektur bezeichnet. Hier wird der Aufbau einer CPU nach John von Neumann, sowie moderne Erweiterungen behandelt: Caches, Pipelining, Superskalarität, Hyperthreading, Multicore Architektur und Parallelrechner.
Miniskript: Prozessorarchitektur
Thema dieses Miniskripts ist die Struktur von Maschinensprachen. Sie wird an einem einfachen Prozessormodell eingeführt. Weitere Themen sind die verschiedene Adressierungsmethoden, RISC vs. CISC, und Assemblerprogrammierung.
Miniskript: Maschinensprache
Dieses Miniskript gibt einen ersten groben Überblick über Kernkomponenten eines Betriebssystems: Gerätetreiber, Prozesse und Threads, Filesysteme, Virtualisierung.
Miniskript: Betriebssysteme
Jedes Programm, welches gestartet wird, erzeugt einen Prozess. Diese Prozesse müssen vom Betriebssystem verwaltet werden. Dazu gehört auch eine Speicherverwaltung, Prozesskommunikation über Pipes und Sockets. Parallel arbeitende Prozesse können auch Problem erzeugen, wie Race Conditions und Deadlocks, die nicht allein vom Betriebssystem gelöst werden können. Da muss der Programmierer Vorsorge treffen, dass das nicht passiert.
Miniskript: Prozesse
Threads sind parallele Durchläufe durch dasselbe Programm. Sie sind das Mittel der Wahl wenn man parallele Prozessoren nutzen will, oder Serverprogramme schreiben will, die Clients parallel bedienen. In diesem Miniskript werden Threads eingeführt und an Java Beispielen illustriert. Weitere Themen sind User- und Kernel-Level Threads, Serverprogrammierung, Race Conditions in Java, Synchronize, Monitore, volatile.
Miniskript: Threads
In diesem Miniskript geht es um Virtualisierung von Betriebssystemen oder Teilen des Betriebssystems. Es werden verschiedene Methoden dazu beschrieben: Paravirtualisierung, Emulation, Partitionierung, API-Emulatoren, Dynamisches Recompilieren
Miniskript: Virtualisierung in Betriebssystemen
Eine ganz wichtige Komponente von Betriebssystemen ist das Filesystem. In dem Miniskript kann natürlich nicht ein konkretes Filesystem mit all seinen Eigenschaften beschrieben werden. Es werden aber die grundlegenden Techniken vorgestellt: Partitionen auf der Festplatte, Cluster, FAT, iNodes, Dateinamen, Directories, Hard- und Softlinks, Attribute, Journaling und schließlich Network-Filesystem (NFS).
Miniskript: Filesysteme
Diese (noch zu erweiternde) Folge von Miniskripten gibt eine Einführung in die Welt der Programmierung.
In diesem Miniskript werden die wichtigsten Konzepte und Begriffe aus der Welt der Programmiemrung eingeführt: Programmierparadigmen: imperativ, funktional, objektorientiert, aspektorientiert, neben\-läufig; Constraint Handling, Compiler und Interpreter, Virtuelle Maschinen, Typsysteme, Ausnahmebehandlung, Design Patterns, Testen, Debuggen, Profilen, Disassemblieren, Verifizieren, Kommentieren, Programmiersprachen.
Miniskript: Programmierung
Die Kernaufgabe eines Rechners ist natürlich, zu rechnen, d.h. Algorithmen ablaufen zu lassen. Die Algorithmen brauchen aber Objekte, mit denen sie arbeiten können, das sind die Datenstrukturen. Grundlegende Datenstrukturen, wie Integer und Gleitkommazahlen, sind schon in die Hardware der Rechner integriert. Komplexere Datenstrukturen, jedoch, müssen programmiert werden. Viele davon sind schon in Bibliotheken verfügbar, andere muss der Programmierer selbst programmieren.
In den folgenden Miniskripten werden zunächst häufig verwendete Datenstrukturen vorgestellt, und dann vielfach verwendbare Algorithmen dafür eingeführt.
Hier geht es um primitive Datentypen, wie Integer, Gleitkommazahlen, Boolesche Werte, Buchstaben, und den Umgang mit einzelnen Bits. Es wird die Sichtweise der Programmiersprache C, die sehr hardwarenahe ist, vorgestellt, und dann die Sichtweise vom Java, die von der Hardware abstrahiert.
Miniskript: Primitive Datentypen
Listen sind eine extrem häufig gebrauchte Datenstruktur. Sie gibt es als einfach verkettete Liste, bei der man nur vorwärts durchlaufen kann, und doppelt verkettete Liste, wo man in beide Richtungen laufen kann. Es wird sowohl eine abstrakte Sichtweise auf Listen, als auch die konkrete Realisierung im Hauptspeicher vorgestellt. Die Operationen auf Listen werden mit Java Programmen illustriert.
Miniskript: Listen
Arrays sind im Speicher unmittelbar hintereinander liegende Folgen von Objekten. Die mathematische Entsprechung wären Vektoren, und, im mehrdimensionalen Fall, Matrizen und Tensoren. Im Miniskript werden zunächst statische eindimensionale Arrays und dann mehrdimensionale Arrays eingeführt. Spezielle Arrays sind Stacks (Kellerspeicher) und Strings. Neben den statischen Arrays, bei denen die Größe bei ihrer Erzeugung festgelegt werden muss, gibt es auch dynamische Arrays, die ihre Größe automatisch anpassen.
Miniskript: Arrays, Stacks und Strings
In vielen Anwendungen gibt es Strukturen, die sich als Graphen mit Knoten und Kanten modellieren lassen. Ein Beispiel ist das Straßennetz. Im Miniskript werden die verschiedenen Varianten von Graphen eingeführt: ungerichtete und gerichtete Graphen, orientierte Graphen, Multigraphen, gelabelte Graphen, gewichtete Graphen, planare Graphen, bipartite Graphen. Häufig gebraucht Begriffe sind u.a. Pfade in Graphen, Hamiltonkreis, Zusammenhangskomponenten Es wird auch auf die Speicherung von Graphen mit Adjazenzlisten, Adjazenzmatrizen und Inzidenzmatrizen eingegangen.
Miniskript: Graphen
Eine extrem wichtige Eigenschaft von Algorithmen ist die Zeitkomplexität in Abhängigkeit von der Größe der Eingabe. Hierbei ist nicht die absolute Zeit relevant, sondern das Wachstumsverhalten, wenn man die Eingabe vergrößert. Das Wachstumsverhalten wird mit sog. Landau-Symbolen beschrieben, wovon die sog. O-Notation ein wichtiger Teil ist. Dies wird im Miniskript thematisiert.
Miniskript: O-Notation
Algorithmen können auf verschiedene Weisen strukturiert werden. Die häufigsten Vorgehensweisen werden im Miniskript beschrieben: Iteration, Divide and Conquer und Rekursion. Eine optimierte Rekursionsvariante ist die Endrekursion. Um die Komplexität eines Divide and Conquer-Algorithmus abzuschätzen, hilft das Master- Theorem.
Miniskript: Iteration, Rekursion und Master Theorem
Hashing bedeutet die Abbildung von Objekten auf Zahlen, mittels sog. Hashfunktionen. Diese Zahlen kann man z.B. in Hashtabellen verwenden, um die Objekte in Arrays abzuspeichern. Eine andere Anwendung von Hashing ist die Bildung von Prüfsummen, mit denen man bis zu einem hohen Grad sicher stellen kann, dass Objekte, insbesondere Texte, nicht manipuliert wurden.
Miniskript: Hashing
Es gibt eine ganze Reihe von Standardprobleme, die sich als Suche in gewichteten Graphen modellieren lassen. Im Miniskript werden folgende Probleme mit entsprechenden Algorithmen dazu vorgestellt:
Miniskript: GewichteteGraphen
Das Sortieren von Mengen von Objekten nach einem vorgegebenen Sortierkriterium ist eines der Standardprobleme in vielen Anwendungen und auch intern in vielen Algorithmen. Im Miniskript werden folgende vergleichsbasierte und nicht-vergleichsbasierte Sortieralgorithmen vorgestellt:
Mit speziellen Techniken können disjunkte Mengen verwaltet werden, so dass die Operationen darauf extrem schnell sind.
Miniskript: Union-Find
Eine spezielle Art von Graphen sind Bäume. Im Miniskript werden Gerichtete und ungerichtete Bäume vorgestellt, zusammen mit wichtigen Konzepten wie Tiefe eines Knotens, Tiefe des Baums, Grad eines Knotens, Binärbäume. Bäume mit festem Grad können in Arrays gespeichert werden, was einen extrem schnellen Zugriff auf die einzelnen Teile eines Baums ermöglicht.
Miniskript: Bäume
Eine ziemlich häufige algorithmische Aufgabe ist die Suche nach einem bestimmten Knoten in einem Baum oder einem Directed Acyclic Graphs (DAGs). Dafür werden die verschiedenen Möglichkeiten vorgestellt: Tiefensuche, Breitensuche und Iterative Tiefensuche.
Miniskript: Baumsuche
Heaps sind zunächst binäre Bäume, deren Knotenlabel aus einer Totalordnung kommen. Die einzige Bedingung ist, dass der Label eins Knotens größer ist, als die Labels der Kindknoten. Heaps kann man effizient in Arrays speichern, und dort immer das größte Element am Anfang des Arrays halten. Heaps sind wichtig für die Implementierung von Prioritätsschlangen und Heapsort.
Miniskript: Heaps
Miniskript: AVL-Bäume
Miniskript: B-Bäume
R-Bäume sind Suchbäume für mehrdimensionale Regionen und werden daher insbesondere als Indexstrukturen in Geodatenbanken eingesetzt.
Miniskript: R-Bäume