Prof. Dr. Heiner Klocke, Algorithmische Anwendungen im WS 2005/06

Themen der Praktikumsprojekte, Liste vom 03.11.2005

Recherchieren Sie bitte auch in der ACM Digital Library: http://portal.acm.org/portal.cfm

Falls Sie dort etwas finden, sagen Sie mir Bescheid. Ich schicke Ihnen den Artikel dann per E-Mail.

Thema	Team
String-Searching, KMP-Algorithmus, Boyer-Moore-Algorithmus Literatur: BOYER R.S., MOORE J.S., 1977, A fast string searching algorithm. Communications of the ACM. 20:762-772. HUME A. and SUNDAY D.M. , 1991. Fast string searching. Software - Practice & Experience 21(11):1221-1248.	A_lila
Lineare Programmierung, Simplex-Algorithmus Literatur: George Dantzig. 1947 Ellipsoidverfahren von L.G. Khachiyan in O(n^6), interior-point-Methode von Karmarkar in O(n^3.5) L.G. Khachiyan, "A polynomial algorithm in linear programming", Doklady Akademiia Nauk SSR 244 (1979), 1093-1096 http://citeseer.ist.psu.edu/173633.html N. Karmarkar. A new Polynomial-Time Algorithm for Linear-Programming.	A_blau
The shifting algorithm technique fort he partitioning of trees. Alternativ: Alpha-Beta Suche zur optimalen Zugermittlung bei Spielen	A_rot
Space Optimizations for Total Ranking. Ähnlichkeitssuche, invertierte Indizes. Heuristische Suchstrategien	A_gelb
Data Compression with the Burrows-Wheeler Transform. Kompression von Testdateien.	A_grün
Symmetrische Verschlüsselung mit dem Blowfish-Algorithmus von Bruce Schneier (1994). Lit.: · http://www.schneier.com/ · B. Schneier, "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)," Fast Software Encryption, Cambridge Security Workshop Proceedings (December 1993), Springer-Verlag, 1994, pp. 191-204. · B. Schneier, "The Blowfish Encryption Algorithm," Dr. Dobb's Journal, v. 19, n. 4, April 1994, pp. 38-40.	C_rot
Backtracking-Algorithmen, NP-vollständige Algorithmen · 8-Damen-Problem · 4-Farben-Problem · Labyrinth-Problem	C_blau
Algorithmen zur Berechnung konvexer Hüllen von Punkten im 2-dim. Raum Graham Scan Algorithmus, O(n log n). Lit.: Ronald Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set, Info.Proc. Letters, 1 (1972), 132-133. · Gift wrapping Algorithmus, O(nk) [n = Anzahl der Punkte, k = Anzahl der Punkte auf der konvexen Hülle]	C_lila
DES, symmetrischer Verschlüsselungs-Algorithmus	C_grün
Advanced Encryption Standard (AES). Symmetrisches Kryptosystem. Der Rijndael-Algorithmus. Lit.: Joan Daemen, Vincent Rijmen: The Design of Rijndael. The Wide Trail Strategy. ISBN 3540425802	C_gelb
Genetische Algorithmen. Lit.: Goldberg, Holland	B_rot
Bayes-Filter zur Text-Klassifizierung, Anwendung: SPAM-Bekämpfung	B_grün
Fourier-Transformation und Fast-Fourier-Transformation. Anwendung: Bildanalyse	B_blau
Beste-Wege-Suche. Algorithmen: Floyd, Dijkstra mit Fibonacci-Heaps, Parallelisierung durch Relaxed Heaps, negative Kantengewichte zugelassen.	B_lila
Biologische Algorithmen zur redundanten Wegesuche. Unscharfe Suche. Wie organisieren Ameisen ihre Informationsübermittlung?	B_gelb
Hough-Transformation. Image Processing. Auffinden von Kanten und Formen in Bildern. Lit.: P. V. C. Hough, “Methods and means for recognition complex pattern,” U. S. Patent 3,069,654 (1962).	E_rot
Quine McCluskey-Verfahren zur Minimierung von logischen Schaltungen. Karnaugh-Veitch-Verfahren Quine McCluskey-Verfahren zur Minimierung von logischen Schaltungen.	E_grün
Finanz-Mathematische Verfahren. Kapitalwert-Algorithmen. Net Present Value.	E_blau
Heuristische Algorithmen. A*-Algorithmus.	E_gelb
Multigrid-Algorithmen zur Simulation	E_pink
MD5-Codierung für Integritätsprüfungen. Stempel in JPG-Bildern-	F_gelb
Lempel-Ziv-Algorithmus. Kompression.	D_rot
Schwachstellen der MD5-Verschlüsselung, Beispiele, Anwendungen. Absprache mit Gruppe F_gelb	D_gruen
ShellSort	D_blau
Erweiterungen und Verbesserungen des Boyer-Moore-String-Searching-Algorithmus. Literatur Richard S. Bird. Polymorphic String Searching.	D_gelb
Plane-Sweep-Technik	D_lila
Pixelorientierte Verfahren zur Segmentierung von digitalen Bildern. Schwellwertverfahren. Lit.: N. Otsu. A threshold selection method from grey level histograms. IEEE Trans Systems Man and Cybernetics, Vol 9, 1979	F_rot
Numerische Algorithmen für das exakte Berechen von Wurzeln.	F_gruen
Transportproblem	F_blau
Asymmetrische Verschlüsselung mit dem RSA-Algorithmus. Mathematische Grundlagen. Implementation in Java. Lit. R. L. Rivest , A. Shamir , L. Adleman.  A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.  Volume 21,  Issue 2  (February 1978) Pages: 120 – 126, ISSN:0001-0782	F_pink
Sequence Alignment. Wiki: „Ein Alignment (englisch: Abgleich, Anordnung, Ausrichtung) dient dem Vergleich mehrerer Strings (technischer Begriff für Zeichenfolge, Sequenz) und wird besonders häufig in der Bioinformatik verwendet, um die funktionelle oder evolutionäre Verwandtschaft (Homologie) von DNA- oder Proteinsequenzen zu untersuchen. Sequenzalignment ist ein Teil des Pattern Matching.“ Algorithmen: Needleman-Wunsch Algorithmus Smith-Waterman-Algorithmus Linearspace-Algorithmus (Hirschberg-Algorithmus) Heuristische Algorithmen	F_lila

Recherchieren Sie bitte auch in der ACM Digital Library: http://portal.acm.org/portal.cfm

Falls Sie dort etwas finden, sagen Sie mir Bescheid. Ich schicke Ihnen den Artikel dann per E-Mail.