Algorithmen

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.

Themen

1Einleitung
2Analyse von Algorithmen
2.1Maschinenmodell
2.2Analyse von Insertion Sort
2.3Größenordnung der Laufzeit
2.4Best-case, Average-case, Worst-case
2.5Sequentielle und binäre Suche
3Elementare Datenstrukturen
3.1Standard-Datenstrukturen
3.2Listen
3.3Bäume
3.4Graphen
4Mengen
4.1Dictionaries
4.2Hashing
4.3Priority Queues
5Algorithmen und Bäume
5.1Lineare Ordnung auf binären Bäumen
5.2Binäre Suchbäume
5.3Balancierte Bäume
5.4Traversieren von Graphen
5.5Bestimmung kürzester Wege in einem Graphen
5.6Minimaler Spannbaum
6Textsuche
6.1Naiver Algorithmus
6.2Rabin-Karp Algorithmus
6.3Endliche Automaten
6.4Knuth-Morris-Pratt Algorithmus
7Sortieren
7.1Bubble Sort
7.2Quicksort
7.3Heapsort
7.4Mergesort
8Komprimieren
8.1Lauflängen-Codierung
8.2Huffman-Codierung
9Verschlüsseln
9.1Grundlagen
9.2Einfache Verfahren
9.3Blockverschlüsselung
9.4Public-Key-Verfahren
9.5Hybride Kryptosysteme
9.6Angriff auf den öffentlichen Schlüssel
9.7Digitale Signatur
9.8Public-Key-Infrastruktur
9.9RSA-Algorithmus
10Geometrische Algorithmen
10.1Grundlagen
10.2Segmentschnitt
10.3Konvexe Hülle
11Komplexität von Problemen
11.1Maschinenmodelle
10.2Entscheidungsprobleme
10.3P und NP
10.4NP-Vollständigkeit