Refine
Document Type
- Doctoral Thesis (2) (remove)
Language
- German (2) (remove)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Heuristik (2) (remove)
Institute
- Informatik (1)
- Medizin (1)
Analyse von Heuristiken
(2006)
Heuristiken treten insbesondere im Zusammenhang mit Optimierungsproblemen in Erscheinung, bei solchen Problemen also, bei denen nicht nur eine Lösung zu finden ist, sondern unter mehreren möglichen Lösungen eine in einem objektiven Sinne beste Lösung ausfindig gemacht werden soll. Beim Problem kürzester Superstrings werden Heuristiken herangezogen, da mit exakten Algorithmen in Anbetracht der APX-Vollständigkeit des Problems nicht zu rechnen ist. Gegeben ist eine Menge S von Strings. Gesucht ist ein String s, so dass jeder String aus S Teilstring von s ist. Die Länge von s ist dabei zu minimieren. Die prominenteste Heuristik für das Problem kürzester Superstrings ist die Greedy-Heuristik, deren Approximationsfaktor derzeit jedoch nur unzureichend beschränkt werden kann. Es wird vermutet (die sogenannte Greedy-Conjecture), dass der Approximationsfaktor genau 2 beträgt, bewiesen werden kann aber nur, dass er nicht unter 2 und nicht über 3,5 liegt. Die Greedy-Conjecture ist das zentrale Thema des zweiten Kapitels. Die erzielten Ergebnisse sind im Wesentlichen: * Durch die Betrachtung von Greedyordnungen können bedingte lineare Ungleichungen nutzbar gemacht werden. Dieser Ansatz ermöglicht den Einsatz linearer Programmierung zum Auffinden interessanter Instanzen und eine Vertiefung des Verständnisses solcher schwerer Instanzen. Dieser Ansatz wird eingeführt und eine Interpretation des dualen Problems wird dargestellt. * Für die nichttriviale, große Teilklasse der bilinearen Greedyordnungen wird gezeigt, dass die Länge des von der Greedy-Heuristik gefundenen Superstrings und die des optimalen Superstrings sich höchstens um die Größe einer optimalen Kreisüberdeckung der Strings unterscheiden. Da eine optimale Kreisüberdeckung einer Menge von Strings stets höchstens so groß ist wie ein optimaler Superstring (man schließe einen Superstring zu einem einzelnen Kreis), ist das erzielte Ergebnis für die betrachtete Teilklasse der Greedyordnungen stärker als die klassische Greedy-Conjecture. * Es wird eine neue bedingte lineare Ungleichung auf Strings -- die Tripelungleichung -- gezeigt, die für das eben genannte Hauptergebnis wesentlich ist. * Schließlich wird gezeigt, dass die zum Nachweis der oberen Schranke von 3,5 für den Approximationsfaktor herangezogenen bedingten Ungleichungen (etwa die Monge-Ungleichung) inhärent zu schwach sind, um die Greedy-Conjecture selbst für lineare Greedyordnungen zu beweisen. Also ist die neue Tripelungleichung auch notwendig. Zuletzt wird gezeigt, dass das um die Tripelungleichung erweiterte System bedingter linearer Ungleichungen inhärent zu schwach ist, um die klassische Greedy-Conjecture für beliebige Greedyordnungen zu beweisen. Mit der Analyse von Queueing Strategien im Adversarial Queueing Modell wird auch ein Fall betrachtet, in dem Heuristiken auf Grund von anwendungsspezifischen Forderungen wie Online-Setup und Lokalität eingesetzt werden. Pakete sollen in einem Netzwerk verschickt werden, wobei jeder Rechner nur begrenzte Information über den Zustand des Netzwerks hat. Es werden Klassen von Queueing Strategien untersucht und insbesondere untersucht, wovon Queueing Strategien ihre lokalen Entscheidungen abhängig machen sollten, um ein gewisses Qualitätsmerkmal zu erreichen. Die hier erzielten Ergebnisse sind: * Jede Queueing Strategie, die ohne Zeitstempel arbeitet, kann zu einer exponentiell großen Queue und damit zu exponentiell großer Verzögerung (im Durchmesser und der Knotenzahl des Netzwerks) gezwungen werden. Dies war bisher nur für konkrete prominente Strategien bekannt. * Es wird eine neue Technik zur Feststellung der Stabilität von Queueing Strategien ohne Zeitnahme vorgestellt, die Aufschichtungskreise. Mit ihrer Hilfe können bekannte Stabilitätsbeweise prominenter Strategien vereinheitlicht werden und weitere Stabilitätsergebnisse erzielt werden. * Für die große Teilklasse distanzbasierter Queueing Strategien gelingt eine vollständige Klassifizierung aller 1-stabilen und universell stabilen Strategien.
In der medizinischen Praxis in Deutschland ist Klassifikation als essentieller Bestandteil der Dokumentation in vielen Bereichen durch gesetzliche Regelungen vorgeschrieben. Über diesen gesetzlich determinierten Rahmen hinaus können durch Klassifikation vergleichbar gemachte Informationen als Basis neuer wissenschaftlicher Erkenntnisse herangezogen werden und weiterhin helfen, bestehende Lehrmeinungen zu evaluieren. Ein Blick auf die im medizinischen Umfeld vorhandene organisatorische Realisierung der Klassifikation zeigt, daß diese in der Regel von medizinisch qualifiziertem Fachpersonal neben der eigentlichen Tätigkeit durchgeführt wird. Eine Klassifikation vorhandener Dokumentationen im Sinne einer Erschließung zusätzlicher wertvoller Informationsquellen über den gesetzlichen Mindestumfang hinaus scheitert somit häufig an der organisatorisch bedingten Überlastung der eingesetzten Mitarbeiter. Eine Unterstützung medizinischer Klassifikation in der Praxis durch den geeigneten Einsatz von Informationstechnologie (IT) erscheint somit sinnvoll und wünschenswert. Im Rahmen der vorliegenden Arbeit wird ein entsprechender Ansatz in Form eines entwickelten Prototypen (XDIAG) vorgestellt und evaluiert. Der entwickelte Prototyp realisiert ein IT-gestütztes leitbegrifforientiertes Verfahren zur automatischen Kodierung von Diagnosen auf Basis vorliegender medizinischer Freitexte. Die hierbei realisierten Ansätze und Verfahren folgen den Vorschlägen von Herrn D. Schalck und sind somit das Resultat langjähriger intensiver und praxisnaher Beschäftigung mit Fragen medizinischer Freitextverarbeitung und Klassifikation. Die besondere Vorgehensweise verleiht dem vorgestellten Prototypen den Charakter einer Heuristik. In Abgrenzung zu zahlreichen bestehenden Verfahren erfolgt eine konsequente Reduktion der Komplexität der eingesetzten Algorithmen und Stammdaten durch einen Verzicht auf eine tiefgreifende linguistische Analyse der zur Kodierung vorgelegten Texte. Durch diesen Verzicht kann auf die Verwendung einer Grammatik und somit auf die Verwendung komplexer Stammdaten verzichtet werden. Als Stammdatenbasis werden vielmehr Datenbestände verwendet, die entweder besonders leicht zu pflegen sind oder aber ohnehin permanent im Rahmen von Langzeitprojekten gepflegt werden. An dieser Stelle spielt insbesondere der ICD10-Diagnosen-Thesaurus mit seiner umfassenden und besonders praxisorientierten Begriffsmenge eine wichtige Rolle. In Erweiterung bestehender Verfahren bietet der vorgestellte Prototyp darüber hinaus die Möglichkeit, mehrere medizinische Diagnosen im Rahmen eines Satzes zu kodieren. Weiterhin können dem Benutzer interaktiv qualifizierte Fehlerhinweise mit dem Ziel einer verbesserten Kodierung bereitgestellt werden. Als Ergebnis der Evaluation des realisierten Prototypen läßt sich festhalten, daß die hierbei eingesetzten Verfahren helfen können, eine synergistische Brücke zwischen praktischer Medizin, medizinischer Verwaltung und medizinischer Forschung zu schlagen, wenn sie an der richtigen Stelle und mit der richtigen Motivation eingesetzt werden.