Refine
Year of publication
Document Type
- Diploma Thesis (46)
- Doctoral Thesis (38)
- Book (32)
- Bachelor Thesis (31)
- diplomthesis (26)
- Contribution to a Periodical (10)
- Article (9)
- Report (5)
- Working Paper (5)
- Part of a Book (4)
Language
- German (213) (remove)
Has Fulltext
- yes (213)
Is part of the Bibliography
- no (213)
Keywords
- Informatik (5)
- E-Learning (4)
- Computerlinguistik (3)
- Hochschule (3)
- Kollaboration <Informatik> (3)
- Lehre (3)
- Organic Computing (3)
- Präsenzlehre (3)
- Textanalyse ; Linguistische Datenverarbeitung; Computerlinguistik (3)
- Verteiltes System (3)
Institute
- Informatik (213) (remove)
Im Gegensatz zur Minimierung von DFAs ist die exakte Minimierung von NFAs oder regulären Ausdrücken nachweislich schwierig, im allgemeinen Fall PSpace-schwer. Wir zeigen, dass selbst schwache Approximationen zur Minimierung von NFAs und regulären Ausdrücken wahrscheinlich nicht effizient möglich sind. Falls als Eingabe ein NFA oder regulärer Ausdruck der Größe n gegeben ist, löst ein Approximationsalgorithmus für das Minimierungsproblem mit Approximationsfaktor o(n) bereits ein PSpace-vollständiges Problem. Wenn wir uns auf NFAs oder reguläre Ausdrücke über einem unären - also einelementigen - Alphabet beschränken, so ist das Problem der exakten Minimierung NP-vollständig. Wir weisen nach, dass effiziente Approximationen für das unäre Minimierungsproblem mit Approximationsfaktor n^(1-delta) für jedes delta>0 nicht möglich sind, sofern P != NP gilt. Liegt die Eingabe als DFA mit n Zuständen vor, kann sie exponentiell größer sein als ein äquivalenter NFA oder regulärer Ausdruck. Dennoch bleibt das Minimierungsproblem PSpace-schwer, wenn die Anzahl der Übergänge oder Zustände in einem äquivalenten NFA oder die Länge eines äquivalenten regulären Ausdrucks zu bestimmen ist. Wir zeigen, dass auch hierfür keine guten Approximationen zu erwarten sind. Unter der Annahme der Existenz von Pseudozufallsfunktionen, die wiederum auf der Annahme basiert, dass Faktorisierung schwierig ist, zeigen wir, dass kein effizienter Algorithmus einen Approximationsfaktor n/(poly(log n)) für die Zahl der Übergänge im NFA oder die Länge des regulären Ausdrucks garantieren kann. Für die Zahl der Zustände im NFA weisen wir nach, dass effiziente Approximationen mit Approximationsfaktor (n^(1/2))/(poly(log n)) ausgeschlossen sind. Wir betrachten dann Lernprobleme für reguläre Sprachen als Konzeptklasse. Mit den entwickelten Methoden, die auf der Annahme der Existenz von Pseudozufallsfunktionen beruhen, zeigen wir auch, dass es für das Problem des minimalen konsistenten DFAs keine effizienten Approximationen mit Approximationsfaktor n/(poly(log n)) gibt. Für den unären Fall hingegen weisen wir nach, dass es einen effizienten Algorithmus gibt, der einen minimalen konsistenten DFA konstruiert und erhalten somit auch einen effizienten PAC-Algorithmus für unäre reguläre Sprachen, die von DFAs mit n Zuständen akzeptiert werden. Für unäre Beispielmengen weisen wir außerdem nach, dass es keine effizienten Algorithmen gibt, die minimale konsistente NFAs konstruieren, falls NP-vollständige Probleme nicht in Zeit (n^(O(log n)) gelöst werden können. Andererseits geben wir einen effizienten Algorithmus an, der zu unären Beispielmengen einen konsistenten NFA mit höchstens O(opt^2) Zuständen konstruiert, wenn ein minimaler konsistenter NFA opt Zustände hat. Abschließend betrachten wir das Lernen von DFAs durch Äquivalenzfragen. Für den nicht-unären Fall ist bekannt, dass exponentiell viele Fragen für DFAs mit n Zuständen benötigt werden. Für unäre zyklische DFAs mit primer Zykluslänge und höchstens n Zuständen zeigen wir, dass Theta((n^2)/(ln n)) Äquivalenzfragen hinreichend und notwendig sind. Erlauben wir größere zyklische DFAs als Hypothesen, kommen wir mit weniger Fragen aus: Um zyklische DFAs mit höchstens n Zuständen durch Äquivalenzfragen mit zyklischen DFAs mit höchstens n^d Zuständen für d <= n als Hypothesen zu lernen, sind O((n^2)/d) Fragen hinreichend und Omega((n^2 ln d)/(d (ln n)^2)) Fragen nötig.
Wir haben Interaktion in der Kommunikationskomplexität untersucht und dabei die drei Modi probabilistische, (beschränkt) nichtdeterministische und quantenmechanische Kommunikation betrachtet. Bei allen drei Modi haben wir herausgefunden, dass Interaktion für Effzienz oft unerlässlich ist, im nichtdeterministischen Fall gibt es eine Abhängigkeit zwischen dem Einfluss der Interaktion und der erlaubten Anzahl der nichtdeterministischen Ratebits. Abgesehen von dem erreichten besseren Verständnis des Kommunikationsmodells haben wir verschiedene Anwendungen auf andere Berechnungsmodelle beschrieben, bei denen untere Schranken der Kommunikation zu unteren Schranken für andere Ressourcen in diesen Modellen geführt haben. Ein Beispiel eines kommunikations- und interaktionsbeschränkten Modells sind endliche Automaten, welche wir in allen drei Modi untersucht haben. Ein weiteres Beispiel sind Formeln, für die wir eine Verbindung zwischen Einweg Kommunikation und Formellänge herstellen konnten. Diese Verbindung führte zu unteren Schranken für probabilistische, nichtdeterministische und Quanten Formeln. Dabei sind die unteren Schranken für Quanten Formeln und probabilistische Formeln im wesentlichen gleich. Für monotone Schaltkreise haben wir gezeigt, wie nichtdeterministisches Raten die Tiefe drastisch reduzieren kann, und wie eine geringfügige Einschränkung der nichtdeterministischen Ratebits zu einer Tiefenhierarchie führt. Insgesamt lässt sich feststellen, dass die Schwäche interaktionsbeschränkter Kommunikation mathematisch nachvollziehbar ist. Außerdem scheint ein solches Verhalten in der Welt einfacher Berechnungsmodelle häufig aufzutreten. Oder anders gesagt, viele Berechnungsmodelle sind deshalb einfacher zu verstehen, weil sie durch interaktionsbeschränkte Kommunikation analysierbar sind.
Die letzten Jahrzehnte brachten einen enormen Zuwachs des Wissens und Verständnisses über die molekularen Prozesse des Lebens.Möglich wurde dieser Zuwachs durch die Entwicklung diverser Methoden, mit denen beispielsweise gezielt die Konzentration einzelner Stoffe gemessen werden kann oder gar alle anwesenden Metaboliten eines biologischen Systems erfasst werden können. Die großflächige Anwendung dieser Methoden führte zur Ansammlung vieler unterschiedlicher -om-Daten, wie zum Beispiel Metabolom-, Proteom- oder Transkriptoms-Datensätzen. Die Systembiologie greift auf solche Daten zurück, um mathematische Modelle biologischer Systeme zu erstellen, und ermöglicht so ein Studium biologischer Systeme auch außerhalb des Labors.
Für größere biologische Systeme stehen jedoch meistens nicht alle Informationen über Stoffkonzentrationen oder Reaktionsgeschwindigkeiten zur Verfügung, um eine quantitative Modellierung, also die Beschreibung von Änderungsraten kontinuierlicher Variablen, durchführen zu können. In einem solchen Fall wird auf Methoden der qualitativen Modellierung zurückgegriffen. Eine dieser Methoden sind die Petrinetze (PN), welche in den 1960er Jahren von Carl Adam Petri entwickelt wurden, um nebenläufige Prozesse im technischen Umfeld zu beschreiben. Seit Anfang der 1990er Jahre finden PN auch Anwendung in der Systembiologie, um zum Beispiel metabolische Systeme oder Signaltransduktionswege zu modellieren. Einer der Vorteile dieser Methode ist zudem, dass Modelle als qualitative Beschreibung des Systems begonnen werden können und im Laufe der Zeit um quantitative Beschreibungen ergänzt werden können.
Zur Modellierung und Analyse von PN existieren bereits viele Anwendungen. Da das Konzept der PN jedoch ursprünglich nicht für die Systembiologie entwickelt wurde und meist im technischen Bereich verwendet wird, existierten kaum Anwendungen, die für den Einsatz in der Systembiologie entwickelt wurden. Daher ist auch die Durchführung der für die Systembiologie entwickelten Analysemethoden für PN nicht mit diesen Anwendungen möglich. Die Motivation des ersten Teiles dieser Arbeit war daher, eine Anwendung zu schaffen, die speziell für die PN-Modellierung und Analyse in der Systembiologie gedacht ist, also in ihren Analysemethoden und ihrer Terminologie sich an den Bedürfnissen der Systembiologie orientiert. Zudem sollte die Anwendung den Anwender bei der Auswertung der Resultate der Analysemethoden visuell unterstützen, indem diese direkt visuell im Kontext des PN gesetzt werden. Da bei komplexeren PN die Resultate der Analysemethoden in ihrer Zahl drastisch anwachsen, wird eine solche Auswertung dieser notwendig. Aus dieser Motivation heraus entstand die Anwendung MonaLisa, dessen Implementierung und Funktionen im ersten Teil der vorliegenden Arbeit beschrieben werden. Neben den klassischen Analysemethoden für PN, wie den Transitions- und Platz-Invarianten, mit denen grundlegende funktionale Module innerhalb eines PN gefunden werden können, wurden weitere, meist durch die Systembiologie entwickelte, Analysemethoden implementiert. Dazu zählen zum Beispiel die Minimal Cut Sets, die Maximal Common Transitions Sets oder Knock-out-Analysen. Mit MonaLisa ist aber auch die Simulation des dynamischen Verhaltens des modellierten biologischen Systems möglich. Hierzu stehen sowohl deterministische als auch stochastische Verfahren, beispielsweise der Algorithmus von Gillespie zur Simulation chemischer Systeme, zur Verfügung. Für alle zur Verfügung gestellten Analysemethoden wird ebenfalls eine visuelle Repräsentation ihrer Resultate bereitgestellt. Im Falle der Invarianten werden deren Elemente beispielsweise in der Visualisierung des PN eingefärbt. Die Resultate der Simulationen oder der topologischen Analyse können durch verschiedene Graphen ausgewertet werden. Um eine Schnittstelle zu anderen Anwendungen zu schaffen, wurde für MonaLisa eine Unterstützung einiger gängiger Dateiformate der Systembiologie geschaffen, so z.B. für SBML und KGML.
Der zweite Teil der Arbeit beschäftigt sich mit der topologischen Analyse eines Datensatzes von 2641 Gesamtgenom Modellen aus der path2models-Datenbank. Diese Modelle wurden automatisiert aus dem vorhandenen Wissen der KEGG- und der MetaCyc-Datenbank erstellt. Die Analyse der topologischen Eigenschaften eines Graphen ermöglicht es, grundlegende Aussagen über die globalen Eigenschaften des modellierten Systems und dessen Entstehungsprozesses zu treffen. Daher ist eine solche Analyse oft der erste Schritt für das Verständnis eines komplexen biologischen Systems. Für die Analyse der Knotengrade aller Reaktionen und Metaboliten dieser Modelle wurden sie in einem ersten Schritt in PN transformiert. Die topologischen Eigenschaften von metabolischen Systemen werden in der Literatur schon sehr gut beschrieben, wobei die Untersuchungen meist auf einem Netzwerk der Metaboliten oder der Reaktionen basieren. Durch die Verwendung von PN wird es möglich, die topologischen Eigenschaften von Metaboliten und Reaktionen in einem gemeinsamen Netzwerk zu untersuchen. Die Motivation hinter diesen Untersuchungen war, zu überprüfen, ob die schon beschriebenen Eigenschaften auch für eine Darstellung als PN zutreffen und welche neuen Eigenschaften gefunden werden können. Untersucht wurden der Knotengrad und der Clusterkoeffizient der Modelle. Es wird gezeigt, dass einige wenige Metaboliten mit sehr hohem Knotengrad für eine ganze Reihe von Effekten verantwortlich sind, wie beispielsweise dass die Verteilung des Knotengrades und des Clusterkoeffizienten, im Bezug auf Metaboliten, skalenfrei sind und dass sie für die Vernetzung der Nachbarschaft von Reaktionen verantwortlich sind. Weiter wird gezeigt, dass die Größe eines Modelles Einfluss auf dessen topologische Eigenschaften hat. So steigt die Vernetzung der Nachbarschaft eines Metaboliten, je mehr Metaboliten in einem biologischen System vorhanden sind, gleiches gilt für den durchschnittlichen Knotengrad der Metaboliten.
Die Menge digital zur Verfügung stehender Dokumente wächst zunehmend. Umso wichtiger sind adäquate Methoden, um sehr große Dokumentkollektionen durch-suchen zu können. Im Gegensatz zur exakten Suche, bei der nach Dokumenten mit bekannten Dateinamen gesucht wird, werden Techniken des Information Retrieval (IR) dazu eingesetzt, relevante Ergebnisse zu einer Anfrage ausfindig zu machen. Seit einigen Jahren werden verstärkt Kollektionen mit strukturierten Dokumenten durch¬sucht, insbesondere seit Durchsetzung der eXtensible Markup Language (XML) als offizieller Standard des World Wide Web Consortiums (W3C). Mittlerweile gibt es eine Reihe von Forschungsansätzen, bei denen IR-Methoden auf XML-Dokumente angewendet werden. XML Information Retrieval (XML-IR) nutzt dabei die Struktur der Dokumente, um die Suche nach und in denselben effektiver zu machen, d.h. die Qualität von Suchergebnissen zu verbessern, beispielsweise durch Fokussierung auf besonders relevante Dokumentteile. Die bisherigen Lösungen beziehen sich jedoch alle auf zentralisierte Stand-Alone Suchmaschinen zu Forschungszwecken. Sehr große, über eine Vielzahl von Rechnern verteilte Datenkollektionen lassen sich damit nicht durchsuchen. Techniken für verteiltes XML-IR werden in der Praxis auch dort benötigt, wo das zu durchsuchende System aus einer Vielzahl lokaler, heterogener XML-Kollektionen besteht, deren Benutzer ihre Dokumente nicht auf einem zent¬ralen Server speichern wollen oder können; solche Benutzer schließen sich häufig in Form eines dezentralen Peer-to-Peer (P2P) Netzes zusammen. Dennoch gibt es derzeit weder für Systeme im Allgemeinen, noch für P2P-Systeme im Speziellen Suchmaschinen, mit denen nach relevanten Dokumenten gesucht werden kann. In der vorliegenden Dissertation wird daher am Beispiel von P2P-Netzen erstmalig untersucht, inwiefern XML-IR in verteilten Systemen überhaupt effektiv und effizient möglich ist. Dazu wird ein allgemeines Architekturmodell für die Entwick-lung von P2P-Suchmaschinen für XML-Retrieval entworfen, in dem Funktionalität aus den Bereichen XML-IR und P2P in abstrakten Schichten angeordnet ist. Das Modell wird als Grundlage für den Entwurf einer konkreten P2P-Suchmaschine für XML-IR verwendet. Es werden dazu verschiedene Techniken für verteiltes XML-IR entwickelt, um die einzelnen Phasen der Suche umzusetzen: Indizierung der Doku¬mente, Routing der Anfragen, Ranking geeigneter Dokumente und Retrieval von Ergebnissen. Insbesondere die Problematik von aus mehreren Suchbegriffen bestehenden Multitermanfragen sowie Verteilungsaspekte werden berücksichtigt. Neben der zu erzie-lenden Suchqualität steht vor allem der notwendige Kommunikations¬aufwand im Vordergrund. Die entwickelten Methoden werden in Form einer P2P-Suchmaschine für verteiltes XML-Retrieval implementiert, die aus fast 40.000 Zeilen Java-Code besteht. Diese Suchmaschine namens SPIRIX kann voll-funktionsfähig nach XML-Dokumenten in einem P2P-Netz suchen und deren Relevanz inhaltsbasiert bewerten. Für die Kommunikation zwischen Peers wird ein P2P-Protokoll namens SpirixDHT entworfen, das auf Basis von Chord arbeitet und speziell für den Einsatz von XML-IR angepasst wird. Für die Evaluierung der entworfenen Techniken wird zunächst die Suchqualität von SPIRIX nachgewiesen. Dies geschieht durch die Teilnahme an INEX, der internationalen Initiative für die Evaluierung von XML-Retrieval. Im Rahmen von INEX werden jedes Jahr XML-IR Lösungen weltweit miteinander verglichen. Für 2008 konnte mit SPIRIX eine Suchpräzision erreicht werden, die vergleichbar mit der Qualität der Top-10 XML-IR Lösungen ist. In weiteren Experimenten werden die entworfenen Methoden für verteiltes XML-Retrieval mit INEX-Werkzeugen evaluiert; dabei werden jeweils die erzielte Such-qualität und der notwendige Aufwand gegenübergestellt. Die gewonnenen Er¬kenn-tnisse werden auf den Routingprozess angewendet; hier ist speziell die Frage-stellung interessant, wie XML-Struktur zur Performanzverbesserung in Bezug auf die Effizienz eines verteilten Systems genutzt werden kann. Die Evaluierung der konzi¬pier¬ten Routingtechniken zeigt eine signifikante Reduzierung der Anzahl versendeter Nachrichten, ihrer Größe und somit der Netzlast, wobei gleichzeitig eine Steigerung der Suchqualität erreicht wird. Im Rahmen der Dissertation wird somit der Nachweis erbracht, dass verteiltes XML-IR sowohl effektiv als auch effizient möglich ist. Zugleich wird gezeigt, wie die Ver¬wendung von XML-IR Techniken beim Routing der Anfragen dazu beitragen kann, den notwendige Suchaufwand – insbesondere den für die Kommunikation zwischen Peers – so weit zu reduzieren, dass das System auch zu einer großen Anzahl von teil¬nehmenden Peers skaliert und trotzdem eine hohe Suchqualität aufrecht erhalten werden kann.
Wiki-Systeme im eLearning
(2006)
Wiki-Systeme lassen sich in den verschiedensten Anwendungsgebieten auf angenehme Weise, aufgrund ihrer Open-Source Lizenz, durch die Anreicherung entsprechender Zusatzmodule anpassen. An dieser Stelle muss jedoch bedacht werden, dass durch die Integration vermehrter Funktionen, das charakteristische Merkmal der Wiki-Systeme 'Einfachheit' an Präsenz verlieren kann. Dieses, für Wikis typische Charakteristikum ist eine nicht zu unterschätzende Stärke, da sowohl die Expansion der Enzyklopädie Wikipedia, als auch die zunehmende Anzahl bestehender Wikis im Internet geradezu Beweis dafür sind, dass keine anderen Anwendungen in diesem Verhältnis existiert haben. Würde somit das Wiki, aufgrund der Anpassung an ein vorliegendes Konzept an Einfachheit verlieren, so müssten die Beweggründe des Wiki-Einsatzes noch mal überdacht werden. Ebenso könnte in den Bereichen, in denen die Stärken von Wikis unbrauchbar sind, ein anderes System womöglich bessere Ergebnisse liefern als ein Wiki. Aus diesen Gründen sollte vor einem Wiki-Einsatz überprüft werden, ob die vorhandenen Merkmale und Funktionen eines Wikis mit den eigenen Anforderungen übereinstimmen. Die im Rahmen dieser Arbeit durchgeführte Befragung hat gezeigt, das Wikis größtenteils als Präsentationsmedium, zur gemeinsamen Texterstellung und als Informationsplattform genutzt werden. Es ist deutlich geworden, dass die Integration von Wikis im Lehrbereich geeignete Anwendung findet. Auffallend war, dass zwar bei (fast) allen Befragten Schwierigkeiten aufgetreten sind und sogar erhoffte Erwartungen teilweise nicht erfüllt wurden, dennoch war der größte Teil der Befragten mit dem Wiki-Einsatz zufrieden und bewertete diesen als positiv. Die Art der aufgetretenen Schwierigkeiten und Schwachstellen zeigt, dass den Lehrenden gewisse Anleitungen und Richtlinien für einen erfolgreichen Wiki-Einsatz fehlten. Denn Informationen zum didaktischen Rahmen - in denen Wikis eingesetzt werden können - und wie Wikis eingesetzt werden sollen, waren nicht vorhanden. Somit sollen die - in dieser Arbeit - erarbeiteten Empfehlungen und Kriterien, Lehrende zu einem optimierten Wiki-Einsatz in Lehrveranstaltungen verhelfen. Außerdem sind in dieser Arbeit Vorgaben enthalten, wie Wiki-Einsätze von Lehrenden gestaltet werden können, so dass die häufig auftretenden Probleme vermieden werden können. Die erarbeiteten Empfehlungen und Kriterien sind gleichermaßen aus den positiven, wie auch aus den negativen Erfahrungen der Befragten entstanden. Insbesondere sollen die Empfehlungen und Kriterien, die von den Befragten permanent beklagten auftretenden Schwierigkeiten und Probleme verhindern. Eine Garantie jedoch, dass die Einhaltung dieser Empfehlungen und Kriterien zu einem erfolgreichen Wiki-Einsatz führen und ob keine relevanten Kriterien unbeachtet gelassen sind, kann an dieser Stelle nicht gegeben werden. Ob sich nun die Probleme, die sich mit Wiki-Einsätzen wiederholt ergeben haben, durch die Befolgung dieser Kriterien und Empfehlungen vermeiden lassen, könnte im Rahmen einer nachfolgenden Diplomarbeit untersucht werden, in der Wiki- Einsätze, begleitet werden. Weiterhin sollte im Rahmen einer weiteren Arbeit die Situation der Lernenden und die Auswirkung auf das Lernverhalten in Verbindung mit Wiki-Systemen evaluiert werden, so dass einige Thesen dieser Arbeit belegt oder gar widerlegt werden können.
In der Realität setzen sich Farben aus einzelnen Wellen zusammen, welche in Kombination mit zugehörigen Wellenlängen und Intensitäten bei Menschen den Sinneseindruck einer Farbe hervorrufen. Die Computergraphik definert Farben mit dem RGB-Modell, in dem durch 3 Grundfarben (Rot, Grün, Blau) der darstellbare Farbbereich festgelegt wird. Ein Spektrum (genauer Spectral Power Distribution, SPD) ermöglicht eine variablere, physikalisch exaktere Darstellung von Farbe, kann aber nicht einfach mit dem RGB-Modell verwendet werden. Das von der Commission Internationale de l'Eclairage definierte XYZ-Farbmodell erlaubt es mit Wellenlängen zu rechnen, und bildet die Grundlage der Beleuchtungsrechnung mit Spektren.
Farben mittels Spektren zu ermitteln ist die Paradedisziplin von Raytracern, da der Berechnungsaufwand für Echtzeitanwendungen meist zu groß ist. Die neueste Graphikkarten-Generation kann große Datenmengen effizient parallel verarbeiten, und es wurden entsprechende Ansätze gesucht, wellenlängenbasiert zu rechnen. Das hier vorgestellte System erlaubt auf Grundlage von physikalischen Formeln einzelne Intensitäten zu beeinflusen, welche in Kombination mit den Tristimulus-Werten des Menschen in dem XYZ-Farbmodell abgebildet werden können. Diese XYZ-Koordinaten können anschließend in das RGBModell transformiert werden.
Im Gegensatz zu bestehenden Systemen wird direkt mit Spektren gearbeitet und diese nicht von einer RGB-Farbe abgeleitet, so dass für bestimmte Effekte eine höhere Genauigkeit entsteht. Durch die Verwendung einer SPD ist es möglich, Interferenzeffekte an dünnen Schichten und CDs in einem Polygon-Renderer zu visualisieren. In dieser Arbeit wird eine Berechnung von mehrlagigen dünnen Schichten mit komplexen Brechungsindizes präsentiert und ein LOD-System vorgestellt, welches es ermöglicht den Berechnungsaufwand frei zu skalieren.