Algorithmen

Grundlagen

• Untere und obere Schranken   
• O-Notation   

Sortieren

• Insertionsort   
• Quicksort   
• Mergesort   
• Mergesort iterativ
• Natural Mergesort
• Heapsort   
• Shellsort   
• Untere Schranke
• Bucket Sort und Radix Sort
• Sortiernetze   
  • 0-1-Prinzip   
  • Bubblesort
  • Odd-even Trans­position Sort   
  • Odd-even Merge Sort   
  • Bitonic Sort   
• Sortieren auf Prozessor­feldern   
  • LS3 Sort   
  • 4-way Mergesort   
  • Rotatesort   
  • 3n-Sort   
  • s²-way Mergesort
  • Shearsort
  • 2D-Odd-Even Trans­positionSort

String Matching

• 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
• String-Matching-Automaten
• Längste gemeinsame Teilzeichenreihe

Codierung

• Huffman-Code
• CRC-Verfahren

Graphenalgorithmen

• Transitive Hülle: Floyd-Warshall-Algorithmus
• Breitensuche in einem Graphen
• Minimaler Spannbaum: Prim-Algorithmus
• Kürzeste Wege: Dijkstra-Algorithmus
• Zusammenhangs­komponenten
• Zweifacher Zusammenhang
• Maximaler Fluss in einem Fluss­netzwerk
• Spielbäume, Minimax-Algorithmus
• Problem des Handlungs­reisenden (Travelling Salesman Problem)

Geometrische Algorithmen

• Konvexe Hülle
  • Polygon
  • Definition der konvexen Hülle, untere Schranke
  • Graham-Scan-Algorithmus
  • Jarvis-March-Algorithmus
  • Quickhull-Algorithmus

Arithmetik

• Ripple-Carry-Addierer
• Carry-Lookahead-Addierer
• Carry-Save-Addierer
• Bitserieller Multi­plizierer (1)
• Bitserieller Multi­plizierer (2)   
• Karatsuba-Multi­plikation
• Modulare Multi­plikation
• Montgomery-Multi­plikation

Transformationen

• Polynom­multiplikation
• Schnelle Fourier-Trans­formation (FFT)
• Diskrete Kosinus-Trans­formation (DCT)

Zahlentheoretische Algorithmen

• Modulare Exponentiation
• Erweiterter euklidischer Algorithmus
• Miller-Rabin-Primzahltest
• Chinesischer-Restsatz-Algorithmus
• Inverses Element modulo Primzahl­potenz

NP-Vollständigkeit

• Ent­scheidungsprobleme, polynomielle Reduktion
• Mengen P und NP
• NP-vollständige Probleme
• Näherungsverfahren
  • Simulated Annealing
  • Selbst­organisierende Karte

Datenanalyse

• Neuronales Netz

Lineare Algebra

• Gram-Schmidt-Verfahren

Mathematische Grundlagen

• Menge
• Relation
• Abbildung
• Aussagen­logik
• Graph, Baum   
• Gruppe
• Ring, Körper
• Vektorraum
• Verband
• Matrix
• Polynom
• Norm
• Metrik
• Komplexe Zahlen
• Quaternionen
• Teilbarkeit, Kongruenz modulo n

 

[up]

 

---

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden