Algorithmen
Inhalt
Grundlagen
Asymptotische Komplexität, O-Notation
Untere und obere Schranken
Sortieren
Insertionsort
Quicksort
Mergesort
Mergesort iterativ
Natural Mergesort
Heapsort
Shellsort
Untere Schranke
Bucket Sort und Radix Sort
Sortiernetze
0-1-Prinzip
Bubblesort
Odd-even Transposition Sort
Odd-even Merge Sort
Bitonic Sort
Sortieren auf Prozessorfeldern
LS3 Sort
4-way Mergesort
Rotatesort
3
n
-Sort
s
2
-way Mergesort
Shearsort
2D-Odd-Even TranspositionSort
Textsuche
Problem
Naiver Algorithmus
Nicht ganz so naiver Algorithmus
Knuth-Morris-Pratt-Algorithmus
Boyer-Moore-Algorithmus
Horspool-Algorithmus
Sunday-Algorithmus
Skip-Search-Algorithmus
Karp-Rabin-Algorithmus
Shift-And-Algorithmus
Codierung
Huffman-Code
CRC
-Verfahren
Hamming-Code
Graphenalgorithmen
Transitive Hülle: Floyd-Warshall-Algorithmus
Minimaler Spannbaum: Prim-Algorithmus
Kürzeste Wege: Dijkstra-Algorithmus
Zusammenhangskomponenten
Zweifacher Zusammenhang
Spielbäume, Minimax-Algorithmus
Geometrische Algorithmen
Konvexe Hülle
Polygon
Definition der konvexen Hülle, untere Schranke
Graham-Scan-Algorithmus
Quickhull-Algorithmus
Arithmetik
Ripple-Carry-Addierer
Carry-Lookahead-Addierer
Carry-Save-Addierer
Bitserieller Multiplizierer (1)
Bitserieller Multiplizierer (2)
Modulare Multiplikation
Transformationen
Transformation
Polynommultiplikation
Schnelle Fourier-Transformation (
FFT
)
Diskrete Kosinus-Transformation (
DCT
)
Kryptografie
Modulare Exponentiation
Erweiterter euklidischer Algorithmus
Miller-Rabin-Primzahltest
RSA
-Verfahren
Faktorisierung: Quadratisches Sieb
NP-Vollständigkeit
Entscheidungsprobleme, polynomielle Reduktion
Mengen
P
und
NP
NP
-vollständige Probleme
Travelling Salesman Problem
Simulated Annealing
Selbstorganisierende Karte
Mathematische Grundlagen
Menge, Relation, Abbildung
Graph, Baum
Wort, Sprache, Grammatik
Gruppe
,
Ring, Körper
,
Vektorraum
Teilbarkeit, Kongruenz modulo
n
Weiter mit
[Theoretische Informatik]
oder
H.W. Lang FH Flensburg
lang@fh-flensburg.de
Impressum
©