Mathematik
Refine
Year of publication
Document Type
- diplomthesis (33)
- Doctoral Thesis (30)
- Article (28)
- Book (22)
- Conference Proceeding (9)
- Contribution to a Periodical (8)
- Bachelor Thesis (7)
- Diploma Thesis (7)
- Master's Thesis (6)
- Report (6)
- Review (2)
- Course Material (1)
- Other (1)
Language
- German (160) (remove)
Has Fulltext
- yes (160)
Is part of the Bibliography
- no (160)
Keywords
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Stochastik (4)
- Finanzmathematik (3)
- Mathematik (3)
- Statistik (3)
- Arithmetische Gruppe (2)
- Biographie (2)
- Frankfurt <Main> / Universität (2)
- Martingal (2)
Institute
- Mathematik (160)
- Präsidium (22)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Informatik (5)
- Physik (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Gitter sind diskrete additive Untergruppen des Rn. Praktische Bedeutung erlangte die Gittertheorie durch effziente Algorithmen zur Gitterbasenreduktion, mit deren Hilfe Optimierungsprobleme gelöst werden können. Der erste dieser Algorithmen wurde von Lenstra, Lenstra und Lovasz entwickelt. Schnorr und Euchner entwickelten effizientere Algorithmen. Sie untersuchten die Güte der Reduktion anhand von Rucksack-Problemen. Bei einem Rucksack-Problem der Dimension n müssen aus einer gegebenen Menge von n Gewichten diejenigen bestimmt werden, die zusammen einen gegeben Rucksack genau ausfüllen. Die Algorithmen von Schnorr und Euchner lösen fast alle Rucksack-Probleme der Dimensionen 42 bis 66. Meine neuen verbesserten Algorithmen lösen einen noch größeren Anteil der Rucksack-Probleme in kürzerer Rechenzeit. Gleichzeitig sind sie in Dimensionen 103 bis 151. Coster, Joux, LaMacchia. Odlyzko, Schnorr und Stern geben eine untere Schranke für die Größe der Gewichte von Rucksack-Problemen an, die fast immer gelöst werden können. Die Gewichte werden zufällig aus einem Intervall natüurlicher Zahlen gewählt. Dieses Ergebnis erweitere ich auf k-fache Rucksack-Probleme. Weiterhin kann für für die Wahl jedes Gewichtes eine beliebige Menge ganzer Zahlen festgelegt werden. Ebenso sind Mengen mit nur einem Element zulässig.
Der im Jahr 2004 am IWR Heidelberg entwickelte Neuronen Rekonstruktions-Algorithmus NeuRA extrahiert die Oberflächenmorphologie oder ein Merkmalskelett von Neuronenzellen, die mittels konfokaler oder Zwei-Photon-Mikroskopie als Bildstapel aufgenommen wurden. Hierbei wird zunächst das Signal-zu-Rausch-Verhältnis der Rohdaten durch Anwendung des speziell entwickelten trägheitsbasierten anisotropen Diffusionsfilters verbessert, dann das Bild nach der statistischen Methode von Otsu segmentiert und anschließend das Oberflächengitter der Neuronenzellen durch den Regularisierten Marching-Tetrahedra-Algorithmus rekonstruiert oder das Merkmalskelett mit einer speziellen Thinning-Methode extrahiert. In einschlägigen Vorarbeiten wurde mit Hilfe solcher Rekonstruktionen von Neuronenzellkernen gezeigt, dass diese, entgegen der vorher üblichen Meinung, nicht notwendigerweise rund sind, sondern Einstülpungen, sogenannte Invaginationen, aufweisen können. Der Einfluss der Invaginationen auf die Ausbreitung von Calciumionen innerhalb solcher Zellkerne konnte durch entsprechende numerische Simulationen systematisch untersucht werden.
Um diese Rekonstruktionsmethode auf hochaufgelöste Mikroskopaufnahmen anwenden zu können, wurden im Rahmen der vorliegenden Arbeit, die in NeuRA verwendeten Verfahren auf Basis von Nvidia CUDA auf moderner Grafikhardware parallelisiert und unter dem Namen NeuRA2 optimiert und neu implementiert. Erzielte Beschleunigungen von bis zu einem Faktor 100, bei Verwendung einer Hochleistungsgrafikkarte, zeigen, dass sich die moderne Grafikarchitektur besonders für die Parallelisierung von Bildverarbeitungsoperatoren eignet. Insbesondere das Herzstück des Rekonstruktions-Algorithmus - der sehr rechenintensive trägheitsbasierte anisotrope Diffusionsfilter - wurde durch eine clusterbasierte Implementierung, welche die parallele Verwendung beliebig vieler Grafikkarten ermöglicht, immens beschleunigt.
Darüber hinaus wurde in dieser Arbeit das Konzept von NeuRA verallgemeinert, um nicht nur Neuronenzellen aus konfokalen oder Zwei-Photon-Bildstapeln rekonstruieren zu können, sondern vielmehr die Oberflächenmorphologie oder Merkmalskelette von allgemeinen Objekten aus beliebigen Bildstapeln zu extrahieren. Dabei wird das ursprüngliche Konzept von Rauschreduktion, Bildsegmentierung und Rekonstruktion beibehalten. Für die einzelnen Schritte stehen aber nun eine Vielfalt von Bildverarbeitungs- und Rekonstruktionsmethoden zur Verfügung, die abhängig von der Beschaffenheit der Daten und den Anforderungen an die Rekonstruktion, ausgewählt werden können. Die meisten dieser Verfahren wurden ebenfalls auf Basis moderner Grafikhardware parallelisiert.
Die weiterentwickelten Rekonstruktionsverfahren wurden in mehreren Anwendungen eingesetzt: Einerseits wurden Oberflächen- und Volumengitter aus konfokalen Bildstapeln und Computertomographie-Aufnahmen generiert, die für verschiedene numerische Simulationen eingesetzt wurden oder eingesetzt werden sollen. Des Weiteren wurden über zwanzig antike Keramikgefäße und Fragmente anderer antiker Keramiken rekonstruiert. Hierbei wurde jeweils die Rohdichte und bei den komplett erhaltenen Gefäßen das Füllvolumen berechnet. Es konnte gezeigt werden, dass dieses Verfahren exakter ist als die in der Archäologie üblichen Methoden zur Volumenbestimmung von Gefäßen. Außerdem zeigt sich eine Abhängigkeit der Rohdichte der rekonstruierten Objekte vom jeweils verwendeten Keramiktyp. Eine Analyse, wie genau die Krümmung von Objekten durch die Approximation von Dreiecksgittern dargestellt werden kann, wurde ebenfalls durchgeführt.
Zusätzlich wurde ein Verfahren zur Rekonstruktion der Merkmalskelette lebender Neuronenzellen oder Teilen von Neuronenzellen entwickelt. Bei den damit rekonstruierten Daten wurden einzelne dendritische Dornfortsätze, auch Spines genannt, hochaufgelöst mikroskopiert. Auf Basis dieser Rekonstruktionen kann die Länge von Dendriten oder einzelner Spines, der Winkel zwischen Dendritenverzweigungen, sowie das Volumen einzelner Spines automatisch berechnet werden. Mit Hilfe dieser Daten kann der Einfluss pharmakologischer Präparate und mechanischer Eingriffe in das Nervensystem von lebenden Versuchstieren systematisch untersucht werden.
Eine Adaption der beschriebenen Rekonstruktionsverfahren ist aufgrund deren einfacher Erweiterbarkeit und flexibler Verwendbarkeit für zukünftige Anwendungen leicht möglich.
Gitter sind diskrete, additive Untergruppen des IRm, ein linear unabhängiges Erzeugendensystem eines Gitters heißt Gitterbasis. Die Anzahl der Basisvektoren eines Gitters ist eindeutig bestimmt und heißt Rang des Gitters. Zu jedem Gitter vom Rang n gibt es mehrere Gitterbasen, die man alle erhält, indem man eine Basismatrix B = [b1, · · · , bn] von rechts mit allen Matrizen aus der Gruppe GLn(ZZ) multipliziert. Eine wichtige Fragestellung der Gittertheorie ist es, zu einem gegebenen Gitter einen kürzesten, vom Nullvektor verschiedenen Gittervektor zu finden. Dieses Problem heißt das kürzeste Gittervektorproblem . Ein dazu verwandtes Problem ist das "nächste Gittervektorproblem", das zu einem beliebigen Vektor x aus IRm einen Gittervektor sucht, dessen Abstand zu x minimal ist. Aus dem "kürzesten Gittervektorproblem" entwickelte sich die Gitterbasenreduktion, deren Ziel es ist, eine gegebene Gitterbasis in eine Gitterbasis zu transformieren, deren Vektoren bzgl. der Euklidischen Norm kurz und möglichst orthogonal zueinander sind. Wichtig für die Güte einer Reduktion ist der Begriff der sukzessiven Minima ¸1(L), · · · , ¸n(L) eines Gitters L. Dabei ist ¸i(L) die kleinste reelle Zahl r > 0, für die es i linear unabhängige Vektoren cj 2 L gibt mit kcjk · r für j = 1, · · · , i. Man versucht, für ein Gitter L eine Gitterbasis b1, · · · , bn zu finden, bei der die Größe kbik / ¸i(L) für i = 1, · · · , n möglichst klein ist. Für Gitter vom Rang 2 liefert das Gauß'sche Reduktionsverfahren eine Gitterbasis mit kbik = ¸i(L) für i = 1, 2. Eine Verallgemeinerung der Gauß-Reduktion auf Gitter mit beliebigem Rang ist die im Jahre 1982 von Lenstra, Lenstra, Lovasz vorgeschlagene L3-Reduktion einer Gitterbasis, deren Laufzeit polynomiell in der Bitlänge der Eingabe ist. L3-reduzierte Gitterbasen approximieren die sukzessiven Minima bis auf einen (im Rang des Gitters) exponentiellen Faktor. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil (Kapitel 1-6) wird ein neues Reduktionskonzept von M. Seysen aus der Arbeit "A Measure for the Non-Orthogonality of a Lattice Basis" behandelt und im zweiten Teil (Kapitel 7) ein aktuelles Ergebnis von M. Ajtai über die Faktorisierung ganzer Zahlen aus "The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions"[2]. Seysen führte in [13] zu einer gegebenen Gitterbasis b1, · · · , bn die Größe ¾(A) ein, die nur von den Einträgen der zugehörigen Gram-Matrix A = [b1, · · · , bn]T · [b1, · · · , bn] und der Inversen A 1 abhängt. Sie hat die Eigenschaft, daß für jede Gitterbasis b1, · · · , bn mit Gram-Matrix A gilt, daß ¾(A) ¸ 1, wobei die Gleichheit genau dann gilt, wenn b1, · · · , bn orthogonal ist. Aus dieser Defintion ergibt sich folgender Reduktionsbegriff: Eine Gitterbasis b1, · · · , bn mit Gram-Matrix A heißt genau dann ¿ -reduziert, wenn ¾(A) minimal für alle Basen des Gitters ist. Der wesentliche Unterschied der ¿-Reduktion zur L3-Reduktion ist, daß die Größe ¾(A) unabhängig von der Reihenfolge der Basisvektoren ist, so daß eine ¿ -reduzierte Gitterbasis bei beliebiger Permutation der Basisvektoren ¿ -reduziert bleibt. Die ¿-Reduktion reduziert also im Gegensatz zur L3-Reduktion die Basisvektoren gleichmäßig. Seysen zeigte, daß man zu jedem Gitter vom Rang n eine Gitterbasis mit Gram-Matrix A findet, so daß ¾(A) durch eO((ln n)2) beschränkt ist. Daraus läßt sich ableiten, daß ¿ -reduzierte Gitterbasen eines Gitters vom Rang n die sukzessiven Minima bis auf den Faktor eO((ln n)2) approximieren. Da es sich bei der ¿-Reduktion um einen sehr starken Reduktionsbegriff handelt, für den es schwer ist, einen effizienten Algorithmus zu finden, definiert man folgenden schwächeren Reduktionsbegriff: b1, · · · , bn heißt genau dann ¿2-reduziert, wenn keine Basistransformation der Form bj := bj +k · bi mit 1 · i 6= j · n und k 2 ZZ die Gr¨oße ¾(A) erniedrigt. Für n = 2 entspricht die ¿-Reduktion sowohl der ¿2- Reduktion als auch der Gauß-Reduktion. Für die ¿2-Reduktion findet man einen effizienten Algorithmus. Wendet man diesen Algorithmus auf Rucksackprobleme an, so ergibt sich, daß durch einen Algorithmus, bestehend aus ¿2-Reduktion und anschließender L3-Reduktion, bei großer Dichte und bei kleiner Dimension wesentlich mehr Rucksackprobleme gelöst werden als durch den L3-Algorithmus. Die Faktorisierung großer ganzer Zahlen ist ein fundamentales Problem mit großer kryptographischer Bedeutung. Schnorr stellte in [11] erstmals einen Zusammenhang zwischen Gitterbasenreduktion und Faktorisierung her, indem er das Faktorisieren ganzer Zahlen auf das "nächste Gittervektorproblem in der Eins-Norm" zurückführte. Adleman führte in [1] das Faktorisieren ganzer Zahlen sogar auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" zurück, allerdings unter zahlentheoretischen Annahmen. In [2] stellte Ajtai ein neues Ergebnis vor, in dem er das Faktorisieren ganzer Zahlen auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" ohne zusätzliche Annahmen zurückführte.
Wir verallgemeinern die Reduktionstheorie von Gitterbasen für beliebige Normen. Dabei zeigen wir neue Eigenschaften reduzierter Basen für die verallgemeinerten Reduktionsbegriffe. Wir verallgemeinern den Gauß-Algorithmus zur Reduktion zweidimensionaler Gitterbasen für alle Normen und erhalten eine universelle scharfe obere Schranke für die Zahl seiner Iterationen. Wir entwickeln für spezielle lp-Normen eine Variante des Gauß-Algorithmus mit niedriger Bit-Komplexität. Hierzu wird Schönhages schneller Reduktionsalgorithmus für quadratische Formen auf die Reduktion von Gitterbasen im klassischen zentrierten Fall übertragen.
Große Stammbäume
(2003)
Sei T ein kritischer oder subkritischer Galton-Watson Stammbaum (GW-Baum) mit einer Kinderzahlverteilung endlicher oder unendlicher Varianz. Wir sind an der Struktur von T , bedingt darauf, dass T "groß" ist, interessiert. Der klassische sowie naheliegende Zugang ist, T auf eine große Gesamtgröße oder eine große Höhe zu bedingen. In dieser Arbeit werden drei, zum GW-Baum eng verwandte Typen von zufälligen Stammbäumen vorgestellt, deren Analyse aufschlussreiche Einsichten über große GW-Stammbäume liefert. Zur Untersuchung dieser auf große Gesamtgröße bedingten Stammbäume schlagen wir eine Familie von zufälligen, größenverzerrten Bäumen vor, deren auf Größe bedingte Verteilung mit der des, auf gegebener Größe bedingten, Baumes T übereinstimmt. Diese zufälligen Stammbäume besitzen eine einfache probabilistische Struktur, wenn man sie entlang der Ahnenlinien von rein zufällig gezogenen Knoten zerlegt. Die Verwandschaftsstruktur des von den gezogenen Knoten und der Wurzel aufgespannten Teilbaumes hängt im wesentlichen von dem asymptotischen Verhalten der Kinderzahlverteilung ab. Während bei endlicher Varianz diese Teilbäume asymptotisch binär sind, können bei unendlicher Varianz im Limes auch andere Formen auftreten. Wir zeigen, dass diese Teilbäume GW-Bäume bedingt auf ihre Gesamtblätterzahl sind. Mit Hilfe der Zerlegung entlang der Ahnenlinien erhalten wir zudem einen Grenzwertsatz für die reskalierte Gesamtgröße des Baumes mit einer Gamma-Verteilung als Limes. Die Analyse großer Bäume führen wir unter dem Aspekt des Größenverzerrens fort, indem wir eine weitere Familie zufälliger Bäume vorschlagen. Diese erhalten wir durch Größenverzerrung in der n-ten Generationsgröße. Wir werden sehen, dass der dadurch gewonnene zufällige Stammbaum eine ähnliche probabilistische Struktur wie der in der Gesamtgröße größenverzerrte Baum besitzt. Hier beweisen wir mit einfachen Überlegungen Aussagen über die Generation des jüngsten gemeinsamen Vorfahren (MRCA) von uniform aus Generation n gezogenen Knoten, sowie die Struktur des von diesen Knoten aufgespannten Skeletts. Schließlich betrachten wir die in [15] vorgestellte probabilistische Zerlegung des auf Mindesthöhe n bedingten GW-Baumes. Damit werden wir klassische Sätze über die Höhe des MRCA und die Grenzverteilung der reskalierten n-ten Generationsgröße für den Fall einer Kinderzahlverteilung mit unendlicher Varianz auf alternativem und anschaulichem Weg beweisen. Zudem erhalten wir eine Grenzverteilung für die Anzahl der Kinder des MRCA.
Der Zufall – ein Helfer und kein Störenfried : warum die Wissenschaft stochastische Modelle braucht
(2008)
Der Zufall hat in den Wissenschaften weithin einen zweifelhaften Ruf. Für die Philosophie hat Hegel festgestellt: »Die philosophische Betrachtung hat keine andere Absicht, als das Zufällige zu entfernen« (Die Vernunft in der Geschichte, 1822) – und ähnlich denkt man auch in anderen Wissenschaften. Die Auseinandersetzungen der Physik mit dem Zufall sind verschlungen und bis heute von Kontroversen begleitet. Was die Biologie betrifft, so herrscht noch einiger Argwohn gegenüber den modernen Evolutionstheorien, die sich entscheidend auf den Zufall stützen. Und dass derartige Theorien unvereinbar sind mit der Vorstellung von einer göttlichen Schöpfung der Welt, gilt unter manchen ihrer Gegner wie Befürworter als ausgemacht.