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   
  • 3n-Sort   
  • s²-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   ©