Global ETD Search

151	Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion Grußien, Berit 10 November 2017 (has links) Diese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind. Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert. / This theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs. deskriptive Komplexität modulare Zerlegung Polynomialzeit Fixpunktlogik Permutationsgraphen chordale Komparabilitätsgraphen Kanonisierung logarithmischer Platz Intervallgraphen chordale klauenfreie Graphen descriptive complexity modular decomposition polynomial time fixed-point logic permutation graphs chordal comparability graphs canonization logarithmic space interval graphs chordal claw-free graphs 004 Informatik ST 134 ddc:004
152	Wiederholungen in Texten / segmentieren und klassifizieren mit vollständigen Substringfrequenzen Golcher, Felix 16 December 2013 (has links) Diese Arbeit untersucht vollständige Zeichenkettenfrequenzverteilungen natürlichsprachiger Texte auf ihren linguistischen und anwendungsbezogenen Gehalt. Im ersten Teil wird auf dieser Datengrundlage ein unüberwachtes Lernverfahren entwickelt, das Texte in Morpheme zerlegt. Die Zerlegung geht von der Satzebene aus und verwendet jegliche vorhandene Kontextinformation. Es ergibt sich ein sprachunabhängiger Algorithmus, der die gefundenen Morpheme teilweise zu Baumstrukturen zusammenordnet. Die Evaluation der Ergebnisse mit Hilfe statistischer Modelle ermöglicht die Identifizierung auch kleiner Performanzunterschiede. Diese sind einer linguistischen Interpretation zugänglich. Der zweite Teil der Arbeit besteht aus stilometrischen Untersuchungen anhand eines Textähnlichkeitsmaßes, das ebenfalls auf vollständigen Zeichenkettenfrequenzen beruht. Das Textähnlichkeitsmaß wird in verschiedenen Varianten definiert und anhand vielfältiger stilometrischer Fragestellungen und auf Grundlage unterschiedlicher Korpora ausgewertet. Dabei ist ein wiederholter Vergleich mit der Performanz bisheriger Forschungsansäzte möglich. Die Performanz moderner Maschinenlernverfahren kann mit dem hier vorgestellten konzeptuell einfacheren Verfahren reproduziert werden. Während die Segmentierung in Morpheme ein lokaler Vorgang ist, besteht Stilometrie im globalen Vergleich von Texten. Daher bietet die Untersuchung dieser zwei unverbunden scheinenden Fragestellungen sich gegenseitig ergänzende Perspektiven auf die untersuchten Häufigkeitsdaten. Darüber hinaus zeigt die Diskussion der rezipierten Literatur zu beiden Themen ihre Verbindungen durch verwandte Konzepte und Denkansätze auf. Aus der Gesamtheit der empirischen Untersuchungen zu beiden Fragestellungen kann abgeleitet werden, dass den längeren und damit selteneren Zeichenketten wesentlich mehr Informationsgehalt innewohnt, als in der bisherigen Forschung gemeinhin angenommen wird. / This thesis investigates the linguistic and application specific content of complete character substring frequency distributions of natural language texts. The first part develops on this basis an unsupervised learning algorithm for segmenting text into morphemes. The segmentation starts from the sentence level and uses all available context information. The result is a language independent algorithm which arranges the found morphemes partly into tree like structures. The evaluation of the output using advanced statistical modelling allows for identifying even very small performance differences. These are accessible to linguistic interpretation. The second part of the thesis consists of stylometric investigations by means of a text similarity measure also rooted in complete substring frequency statistics. The similarity measure is defined in different variants and evaluated for various stylometric tasks and on the basis of diverse corpora. In most of the case studies the presented method can be compared with publicly available performance figures of previous research. The high performance of modern machine learning methods is reproduced by the considerably simpler algorithm developed in this thesis. While the segmentation into morphemes is a local process, stylometry consists in the global comparison of texts. For this reason investigating of these two seemingly unconnected problems offers complementary perspectives on the explored frequency data. The discussion of the recieved litarature concerning both subjects additionally shows their connectedness by related concepts and approaches. It can be deduced from the totality of the empirical studies on text segmentation and stylometry conducted in this thesis that the long and rare character sequences contain considerably more information then assumed in previous research. Stilometrie Morphologische Induktion lineare gemischte Modelle generalisierte lineare gemischte Modelle logarithmische Transformation Stylometry Morphological Induction linear mixed models generalized linear mixed models logarithmic transformation 430 Deutsch und verwandte Sprachen ES 965 ddc:430
153	Grundlagen der Elasto-Plastizität in Creo Simulate - Theorie und Anwendung / Basics of Elasto-Plasticity in Creo Simulate - Theory and Application Jakel, Roland 10 May 2012 (has links) (PDF) Der Vortrag beschreibt die Grundlagen der Elasto-Plastizität sowie die softwaretechnische Anwendung mit dem FEM-Programm Creo Simulate bzw. Pro/MECHANICA von PTC. Der erste Teil des Vortrages beschreibt die Charakteristika plastischen Verhaltens, unterschiedliche plastische Materialgesetze, Fließkriterien bei mehrachsiger Beanspruchung und unterschiedliche Verfestigungsmodelle. Im zweiten Vortragsteil werden Möglichkeiten und Grenzen der Berechnung elasto-plastischer Probleme mit der Software dargestellt sowie Anwendungstipps gegeben. Im dritten Vortragsteil schließlich werden verschiedene Beispiele vorgestellt, davon besonders ausführlich das Verhalten einer einachsigen elasto-plastischen Zugprobe vor und nach dem Eintreten der Einschnürdehnung. / This presentation describes the basics of elasto-plasticity and its application with the finite element software Creo Simulate (formerly Pro/MECHANICA) from PTC. The first part describes the characteristics of plastic behavior, different plastic material laws, yield criteria for multiaxial stress states and different hardening models. In the second part, the opportunities and limitations of analyzing elasto-plastic problems with the FEM-code are described and user information is provided. The last part finally presents different examples. Deeply treated is the behavior of a uniaxial tensile test specimen before and after elongation with necking appears. Elasto-Plastizität Creo Simulate Mechanica FEM Plastitzität kleiner Dehnungen Plastitzität großer Dehnungen technische Spannung wahre Spannung technische Dehnung logarithmische Dehnung kinematische und isotrope Verfestigung plastische Materialgesetze sprödes und duktiles Verhalten Mehrachsigkeit Lastschritte Entlasten Elasto-plasticity Creo Simulate Mechanica FEM small strain plasticity finite strain plasticity engineering stress true stress engineering strain logarithmic strain yield criteria kinematic and isotropic hardening elasto-plastic material laws brittle and ductile behavior multi-axial plasticity characteristic measures for plasticity load steps unloading meshing uniaxial tensile test with necking ddc:629 Fließbedingung Plastizität Dehnung Mehrachsigkeit Vernetzung
154	Modèles attractifs en astrophysique et biologie : points critiques et comportement en temps grand des solutions / Attractive models in Astrophysics and Biology : Critical Points and Large Time Asymtotics Campos Serrano, Juan 14 December 2012 (has links) Dans cette thèse, nous étudions l'ensemble des solutions d'équations aux dérivées partielles résultant de modèles d'astrophysique et de biologie. Nous répondons aux questions de l'existence, mais aussi nous essayons de décrire le comportement de certaines familles de solutions lorsque les paramètres varient. Tout d'abord, nous étudions deux problèmes issus de l'astrophysique, pour lesquels nous montrons l'existence d'ensembles particuliers de solutions dépendant d'un paramètre à l'aide de la méthode de réduction de Lyapunov-Schmidt. Ensuite un argument de perturbation et le théorème du Point xe de Banach réduisent le problème original à un problème de dimension finie, et qui peut être résolu, habituellement, par des techniques variationnelles. Le reste de la thèse est consacré à l'étude du modèle Keller-Segel, qui décrit le mouvement d'amibes unicellulaires. Dans sa version plus simple, le modèle de Keller-Segel est un système parabolique-elliptique qui partage avec certains modèles gravitationnels la propriété que l'interaction est calculée au moyen d'une équation de Poisson / Newton attractive. Une différence majeure réside dans le fait que le modèle est défini dans un espace bidimensionnel, qui est expérimentalement consistant, tandis que les modèles de gravitationnels sont ordinairement posés en trois dimensions. Pour ce problème, les questions de l'existence sont bien connues, mais le comportement des solutions au cours de l'évolution dans le temps est encore un domaine actif de recherche. Ici nous étendre les propriétés déjà connues dans des régimes particuliers à un intervalle plus large du paramètre de masse, et nous donnons une estimation précise de la vitesse de convergence de la solution vers un profil donné quand le temps tend vers l'infini. Ce résultat est obtenu à l'aide de divers outils tels que des techniques de symétrisation et des inégalités fonctionnelles optimales. Les derniers chapitres traitent de résultats numériques et de calculs formels liés au modèle Keller-Segel / In this thesis we study the set of solutions of partial differential equations arising from models in astrophysics and biology. We answer the questions of existence but also we try to describe the behavior of some families of solutions when parameters vary. First we study two problems concerned with astrophysics, where we show the existence of particular sets of solutions depending on a parameter using the Lyapunov-Schmidt reduction method. Afterwards a perturbation argument and Banach's Fixed Point Theorem reduce the original problem to a finite-dimensional one, which can be solved, usually, by variational techniques. The rest of the thesis is de-voted to the study of the Keller-Segel model, which describes the motion of unicellular amoebae. In its simpler version, the Keller-Segel model is a parabolic-elliptic system which shares with some gravitational models the property that interaction is computed through an attractive Poisson / Newton equation. A major difference is the fact that it is set in a two-dimensional setting, which experimentally makes sense, while gravitational models are ordinarily three-dimensional. For this problem the existence issues are well known, but the behaviour of the solutions during the time evolution is still an active area of research. Here we extend properties already known in particular regimes to a broader range of the mass parameter, and we give a precise estimate of the convergence rate of the solution to a known profile as time goes to infinity. This result is achieved using various tools such as symmetrization techniques and optimal functional inequalities. The last chapters deal with numerical results and formal computations related to the Keller-Segel model Tour de bulles Réduction de Lyapunov-Schmidt Exposant critique Modèle de Keller-Segel Chemotactisme Asymptotiques en temps grand Masse critique Solutions auto-similaires Entropie relative Énergie libre Fonctionnelle de Lyapunov Trou spectral Équilibre relatif Équation de Vlasov-Poisson Problème à N-corps Développement asymptotique Bubble-tower solutions Lyapunov-Schmidt reduction Critical exponent Keller-Segel model Chemotaxis Large time asymptotics Subcritical mass Self-similar solutions Relative entropy Free energy Lyapunov functional Spectral gap Relative equilibrium Vlasov-Poisson equation N-Body Problem Continous stellar dynamics Matched asymptotics expansion 515
155	Grundlagen der Elasto-Plastizität in Creo Simulate - Theorie und Anwendung / Basics of Elasto-Plasticity in Creo Simulate - Theory and Application Jakel, Roland 10 May 2012 (has links) Der Vortrag beschreibt die Grundlagen der Elasto-Plastizität sowie die softwaretechnische Anwendung mit dem FEM-Programm Creo Simulate bzw. Pro/MECHANICA von PTC. Der erste Teil des Vortrages beschreibt die Charakteristika plastischen Verhaltens, unterschiedliche plastische Materialgesetze, Fließkriterien bei mehrachsiger Beanspruchung und unterschiedliche Verfestigungsmodelle. Im zweiten Vortragsteil werden Möglichkeiten und Grenzen der Berechnung elasto-plastischer Probleme mit der Software dargestellt sowie Anwendungstipps gegeben. Im dritten Vortragsteil schließlich werden verschiedene Beispiele vorgestellt, davon besonders ausführlich das Verhalten einer einachsigen elasto-plastischen Zugprobe vor und nach dem Eintreten der Einschnürdehnung. / This presentation describes the basics of elasto-plasticity and its application with the finite element software Creo Simulate (formerly Pro/MECHANICA) from PTC. The first part describes the characteristics of plastic behavior, different plastic material laws, yield criteria for multiaxial stress states and different hardening models. In the second part, the opportunities and limitations of analyzing elasto-plastic problems with the FEM-code are described and user information is provided. The last part finally presents different examples. Deeply treated is the behavior of a uniaxial tensile test specimen before and after elongation with necking appears. info:eu-repo/classification/ddc/629 ddc:629
156	Minimization of Noise and Vibration Related to Driveline Imbalance using Robust Design Processes Al-Shubailat, Omar 17 August 2013 (has links) Variation in vehicle noise, vibration and harshness (NVH) response can be caused by variability in design (e.g. tolerance), material, manufacturing, or other sources of variation. Such variation in the vehicle response causes a higher percentage of produced vehicles to have higher levels (out of specifications) of NVH leading to higher number of warranty claims and loss of customer satisfaction, which are proven costly. Measures must be taken to ensure less warranty claims and higher levels of customer satisfactions. As a result, original equipment manufacturers (OEMs) have implemented design for variation in the design process to secure an acceptable (or within specification) response. The focus here will be on aspects of design variations that should be considered in the design process of drivelines. Variations due to imbalance in rotating components can be unavoidable or costly to control. Some of the major components in the vehicle that are known to have imbalance and traditionally cause NVH issues and concerns include the crankshaft, the drivetrain components (transmission, driveline, half shafts, etc.), and wheels. The purpose is to assess NVH as a result of driveline imbalance variations and develop a tool to help design a more robust system to such variations. program. Java quality engineering quality capability studies manufacturing processes manufacturing engineer design engineer sales profit customer concern warranty objectionable Eigen functions vectors Eigen Eigen values identity Euler differential equations differential transfer case shaft driveline static imbalance dynamic imbalance passenger customer driver inboard ear driver outboard ear steering wheel seat track variation Gamma distribution normal distribution standard deviation average variance mean phasor victor scalar linear system LTI linear time invariant transfer function output input microphone accelerometers tachometer channels order frequency frequency domain time domain convolution Transformation Fourier Transformer Fourier imaginary and real logarithmic decibel sensitivity curves run down run up two wheel drive Four Wheel Drive Nissan Truck OEM Original Equipment Manufacturers Data Acquisitions Channels Simulation Six Sigma variability Design Robust sensitivity Vibration Imbalance Noise Harshness NVH Driveline

Page generated in 0.0585 seconds