Ein Algorithmus ist eine eindeutige Handlungsvorschrift, um eine Aufgabe zu lösen und kann als Computer-Programm implementiert werden. Damit sind Algorithmen ein zentrales Thema der Informatik. Egal, ob wir eine Suchmaschine im Internet nutzen, eine Mail verschicken, eine Liste von Kundendaten sortieren, einen Routenplaner verwenden, oder ein Schaltungslayout optimieren, in allen Fällen kommen leistungsfähige Algorithmen zum Einsatz.
Die Verwendung effizienter Algorithmen ist eine notwendige Voraussetzung für schnelle und effiziente Computersysteme. Die Wahl eines ”schlechten“ Algorithmus kann selbst durch eine hundertfache Erhöhung der Rechenleistung eines Computers nicht kompensiert werden.
Durch den Einsatz von geeigneten Algorithmen können also erhebliche Kosten eingespart werden.
In der Vorlesung werden viele Algorithmen für praktisch relevante Aufgabenstellungen vorgestellt. Die Algorithmen werden aber nicht nur aufgelistet, sondern es wird auch betrachtet, wie Algorithmen analysiert und bewertet werden können. Zudem werden Methoden vorgestellt, mit denen effiziente Algorithmen entworfen werden können.
1 | Einleitung |
2 | Analyse von Algorithmen |
2.1 | Maschinenmodell |
2.2 | Analyse von Insertion Sort |
2.3 | Größenordnung der Laufzeit |
2.4 | Best-case, Average-case, Worst-case |
2.5 | Sequentielle und binäre Suche |
3 | Elementare Datenstrukturen |
3.1 | Standard-Datenstrukturen |
3.2 | Listen |
3.3 | Bäume |
3.4 | Graphen |
4 | Mengen |
4.1 | Dictionaries |
4.2 | Hashing |
4.3 | Priority Queues |
5 | Algorithmen und Bäume |
5.1 | Lineare Ordnung auf binären Bäumen |
5.2 | Binäre Suchbäume |
5.3 | Balancierte Bäume |
5.4 | Traversieren von Graphen |
5.5 | Bestimmung kürzester Wege in einem Graphen |
5.6 | Minimaler Spannbaum |
6 | Textsuche |
6.1 | Naiver Algorithmus |
6.2 | Rabin-Karp Algorithmus |
6.3 | Endliche Automaten |
6.4 | Knuth-Morris-Pratt Algorithmus |
7 | Sortieren |
7.1 | Bubble Sort |
7.2 | Quicksort |
7.3 | Heapsort |
7.4 | Mergesort |
8 | Komprimieren |
8.1 | Lauflängen-Codierung |
8.2 | Huffman-Codierung |
9 | Verschlüsseln |
9.1 | Grundlagen |
9.2 | Einfache Verfahren |
9.3 | Blockverschlüsselung |
9.4 | Public-Key-Verfahren |
9.5 | Hybride Kryptosysteme |
9.6 | Angriff auf den öffentlichen Schlüssel |
9.7 | Digitale Signatur |
9.8 | Public-Key-Infrastruktur |
9.9 | RSA-Algorithmus |
10 | Geometrische Algorithmen |
10.1 | Grundlagen |
10.2 | Segmentschnitt |
10.3 | Konvexe Hülle |
11 | Komplexität von Problemen |
11.1 | Maschinenmodelle |
10.2 | Entscheidungsprobleme |
10.3 | P und NP |
10.4 | NP-Vollständigkeit |