No description available.

A good strategy to test a software component involves the generation of the whole set of cases that participate in its operation. While testing only individual values may not be enough, exhaustive testing of all possible combinations is not always feasible. An alternative technique to accomplish this goal is called combinato- rial testing. Combinatorial testing is a method that can reduce cost and increase the effectiveness of software testing for many applications. It is based on con- structing functional test-suites of economical size, which provide coverage of the most prevalent configurations. Covering arrays are combinatorial objects, that have been applied to do functional tests of software components. The use of cov- ering arrays allows to test all the interactions, of a given size, among the input parameters using the minimum number of test cases. For software testing, the fundamental problem is finding a covering array with the minimum possible number of rows, thus reducing the number of tests, the cost, and the time expended on the software testing process. Because of the importance of the construction of (near) optimal covering arrays, much research has been carried out in developing effective methods for constructing them. There are several reported methods for constructing these combinatorial models, among them are: (1) algebraic methods, recursive methods, (3) greedy methods, and (4) metaheuristics methods. Metaheuristic methods, particularly through the application of simulated anneal- ing has provided the most accurate results in several instances to date. Simulated annealing algorithm is a general-purpose stochastic optimization method that has proved to be an effective tool for approximating globally optimal solutions to many optimization problems. However, one of the major drawbacks of the simulated an- nealing is the time it requires to obtain good solutions. In this thesis, we propose the development of an improved simulated annealing algorithm / Avila George, H. (2012). Constructing Covering Arrays using Parallel Computing and Grid Computing [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17027

The problem of historical explanation consists in how historical facts are put together. No mere collection of facts constitutes an explanation: there must be some underlying explanation for why those facts occurred in the way they did. Many competing theories of historical explanation have thus been offered, from the highly technical D-N or covering law model, to narrative-based explanations. This paper exposes the flaws in the covering law model proposed by Carl Hempel, and offers a justification for narrative-based explanations by appealing to the notion of language games as used by Ludwig Wittgenstein, as well as the narrative and paradigm models of Arthur Danto and Thomas Kuhn for explaining historical events. / Master of Arts / The problem of historical explanation consists in how historical facts are put together. No mere collection of facts constitutes an explanation: there must be some underlying explanation for why those facts occurred in the way they did. Many competing theories of historical explanation have thus been offered, from the highly technical D-N or covering law model, which imitates the methods of explanation in “hard” scientific inquiry through a careful description of initial conditions and relevant laws and formulas, to narrative-based explanations, or explanations that use a story with a beginning, a middle, and an end. This paper exposes the flaws in the covering law model proposed by Carl Hempel, and offers a justification for narrative-based explanations by appealing to the notion of language games as used by Ludwig Wittgenstein, as well as the narrative and paradigm models of Arthur Danto and Thomas Kuhn for explaining historical events. The aim of this project is to prevent scientific analysis being incorrectly applied to non-scientific entities, such as persons (e.g. Napoleon Bonaparte) and places (e.g. Russia) which are referenced in ordinary language, and which are in principle irreducible to the primary entities of the so-called “hard” sciences, such as subatomic particles and fundamental forces.

The property B(P,∝)-refinability is studied and is used to obtain new covering characterizations of paracompactness, collectionwise normality, subparacompactness, d-paracompactness, a-normality, mesocompactness, and related concepts. These new characterizations both generalize and unify many well-known results. The property B(P,∝)-refinability is strictly weaker than the property Θ-refinability. A B(P,∝)-refinement is a generalization of a σ-locally finite-closed refinement. Here ∝ is a fixed ordinal which dictates the number of "levels" in a given refinement, and P represents a property such as discreteness or local finiteness which each "level" must satisfy relative to a certain subspace. / Ph. D. / incomplete_metadata

In dieser Arbeit untersuchen wir Algorithmen für Scheduling-Probleme. Wir betrachten semi-online Makespan-Scheduling und generalisiertes Bin Covering. Im online Makespan- Scheduling-Problem sind m Maschinen und n Jobs gegeben, wobei letztere jeweils eine individuelle Bearbeitungszeit haben. Es wird zu jedem Zeitpunkt ein Job offengelegt und muss sofort und unwiderruflich einer Maschine zugewiesen werden, ohne Wissen über zukünftige Jobs. Die Last einer Maschine wird als die Summe der Bearbeitungszeiten der ihr zugewiesenen Jobs definiert. Das Ziel ist es, eine Zuweisung von Jobs zu Maschinen zu finden, sodass die höchste Last einer Maschine minimiert wird. Im semi-online Scheduling-Modell wird dieses strikte Szenario relaxiert. Wir untersuchen drei verschied- ene Modelle. Im ersten ist uns die kumulierte Bearbeitungszeit der Jobs vor Ankunft der einzelnen Jobs bekannt. Im zweiten Modell dürfen wir bis zu einem gewissen Grade bereits zugewiesene Jobs anderen Maschinen neu zuordnen.Im dritten semi-online Scheduling-Modell darf ein Algorithmus mehrere Lösungen parallel konstruieren, von denen die beste ausgegeben wird. Beim generalisierten Bin Covering sind uns m Bintypen und n Objekte gegeben. Ein Bintyp Mj hat einen Bedarf dj und einen Profit rj. Jedes Objekt Jt hat eine Größe pt. Ein Bin vom Typ Mj heißt abgedeckt, wenn die Summe der Größen der ihm zugewiesenen Objekte mindestens dj ist. Wenn ein Bin vom Typ Mj abgedeckt ist, erzielen wir einen Profit von rj. Ziel ist es, die Objekte Bins zuzuweisen, sodass der erzielte Gesamtprofit maximiert wird. Wir untersuchen zwei Modelle, die sich in der Verfügbarkeit von Bintypen unterscheiden. Im Unit-Supply-Modell steht uns von jedem Bintyp genau ein Bin zur Verfügung. Im Gegensatz dazu stehen uns im Infinite-Supply-Modell von jedem Bintyp beliebig viele Bins zur Verfügung. Das Unit-Supply-Modell ist daher eine Verallgemeinerung des Infinite-Supply-Modells. Für alle Modelle zeigen wir beinahe scharfe obere und untere Schranken. / In this thesis we study algorithms for scheduling problems. We investigate semi-online minimum makespan scheduling and generalized bin covering. In online minimum makespan scheduling we are given a set of m machines and n jobs, where each job Jt is specified by a processing time. The jobs arrive one by one and we have to assign them to the machines without any knowledge about future incoming jobs. The load of a machine is defined to be total processing time of the assigned jobs. The goal is to place the jobs on the machines such that the maximum load of a machine is minimized. In semi-online minimum makespan scheduling this strict setting is softened. We investigate three different models. In the first setting an algorithm is given an advice on the total processing time of the jobs. In the second setting we may reassign jobs upto a limited amount. The third semi-online setting we study is minimum makespan scheduling with parallel schedules. In this problem an algorithm may maintain several schedules, the best of which is output after the arrival of the entire job sequence. In generalized bin covering we are given m bin types and n items. Each bin type Mj is specified by a demand dj and a revenue rj. Each item Jt has a size pj. A bin of type Mj is said to be covered if the total size of the assigned items is at least the demand dj. Then the revenue rj is earned. The goal is to find an assignment of items to bins maximizing the total obtained revenue. We study two models of bin supply. In the unit supply model there is only one bin of each type available. By contrast in the infinite supply model each bin type is available arbitrarily often, and hence the former is a generalization of the latter. We provide nearly tight upper and lower bounds for all models.

Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans plusieurs espaces métriques spécifiques, et, en particulier, ceux générés par certains de ces outils, comme Vivaldi et Sequoia. / During this Ph.D we introduced Bin Covering under Distance Constraint (BCCD in French) and Bin Packing under Distance Constraint (BPCD in French). Those two problems find their applications in the context of large scale networks, like Internet. We studied those problems in general metric spaces, and proved that using resource augmentation is mandatory. Resource augmentation allows to build algorithms working on solutions with less constraints than the optimal solution to which it is compared to. We found interesting approximations algorithms using this relaxation, and proved the necessity of this resource augmentation. However many tools are used to embed large networks we are interested in in specific metric spaces. Thus we studied those problems in different specific metric spaces, in particular those generated by the use of Vivaldi and Sequoia, two of those tools.

In dieser Dissertation untersuchen wir das Verhalten von Schrödinger-Operatoren unter Riemannschen Überlagerungen. Wir betrachten folgende Situation: Sei eine Riemannsche Überlagerung und ein Schrödinger-Operator S mit glattem, von unten beschränktem Potential auf der Basismannigfaltigkeit gegeben. Sei S‘ der Lift von S auf die Überlagerungsmannigfaltigkeit. Man sieht leicht, dass das Minimum des Spektrums von S nicht größer als das Minimum des Spektrums von S‘ ist. R. Brooks hat als erster untersucht, wann die Gleichheit gilt. Er bewies insbesondere, dass eine normale Riemannsche Überlagerung einer geschlossenen Mannigfaltigkeit genau dann amenabel ist, wenn sie das Minimum des Spektrums des Laplace-Operators unverändert lässt. Zusammen mit W. Ballmann und H. Matthiesen bewiesen wir, dass amenable Riemannsche Überlagerungen immer das Minimum des Spektrums von Schrödinger-Operatoren erhalten; dies verallgemeinert Resultate von R. Brooks sowie von P. Bérard und Ph. Castillon. In dieser Dissertation beweisen wir, dass im Fall vollständiger Mannigfaltigkeiten das Spektrum von S im Spektrum von S‘ enthalten ist. Tatsächlich beweisen wir diese Beziehung sogar für eine deutlich größere Klasse von Differentialoperatoren. Obwohl Amenabilität eine natürliche Bedingung für die Gleichheit der Minima der Spektren ist, ist es unklar, inwieweit diese Bedingung optimal ist. In dieser Dissertation beweisen wir: Wenn eine Riemannsche Überlagerung das Minimum des Spektrums eines Schrödinger-Operators erhält, und wenn dieses zum diskreten Spektrum des Operators auf der Basismannigfaltigkeit gehört, dann ist die Überlagerung amenabel. Man beachte, dass wir keinerlei geometrische oder topologische Bedingungen an die Mannigfaltigkeiten stellen. Dies verallgemeinert sowohl frühere Resultate von R. Brooks, T. Roblin und S. Tapie als auch ein kürzliches Resultat aus einer gemeinsamen Arbeit mit W. Ballmann und H. Matthiesen. / In this thesis, we investigate the behavior of the spectrum of Schrödinger operators under Riemannian coverings. To set the stage, consider a Riemannian covering and a Schrödinger operator S on the base manifold, with smooth potential bounded from below potential. Let S’ be the lift of S on the covering space. It is easy to see that the bottom (that is, the minimum) of the spectrum of S is no greater than the bottom of the spectrum of S’. R. Brooks was the first one to examine when the equality holds. In particular, he proved that a normal Riemannian covering of a closed manifold is amenable if and only if it preserves the bottom of the spectrum of the Laplacian. Generalizing former results of R. Brooks, and P. Berard and Ph. Castillon, in a joint work with W. Ballmann and H. Matthiesen, we proved that amenable Riemannian coverings preserve the bottom of the spectrum of Schrödinger operators. In this thesis, we prove that if, in addition, the manifolds are complete, then the spectrum of S is contained in the spectrum of S’. As a matter of fact, we establish this result for a quite wide class of differential operators. Although amenability is a natural assumption for the preservation of the bottom of the spectrum, it is not clear to what extent it is optimal. In this thesis, we prove that if a Riemannian covering preserves the bottom of the spectrum of a Schrödinger operator, which belongs to the discrete spectrum of the operator on the base manifold, then the covering is amenable. It is worth to point out that we do not impose any geometric or topological assumptions on the manifolds. This generalizes former results by R. Brooks, T. Roblin and S. Tapie, and a recent result of a joint work with W. Ballmann and H. Matthiesen.

Det har blivit mer och mer vanligt med ny, datoriserad teknik i hemmen. Fler människor har ett allt stressigare liv och inte längre samma tid att ta hand om det egna hemmet. Behovet av en hjälpande hand med hushållsarbete har blivit allt större. Tänk själv att komma hem från jobbet eller skolan och så har golvet blivit skinande rent utan att Ni knappt har behövt göra någonting! Det finns idag flera olika robotar på marknaden för detta ändamål. En av dessa är den autonoma dammsugaren, som är det vi inriktat vår uppsats på. I huvudsak är uppsatsen inriktad på mjukvaran, som kan användas i en autonom dammsugare. Vi har valt att titta närmare på två stycken sökalgoritmer, som kan användas av autonoma mobila robotar, exempelvis en autonom dammsugare, som har i uppdrag att täcka en hel obekant yta. Dessa algoritmer är Spanning Tree Covering (STC) och ”A Topological Coverage Algorithm”, också kallad ”Landmark-based World Model” (fritt översatt till Topologisk Täckande Algoritm, TTA). Vi har också undersökt hur ett av Sveriges största märken på marknaden för autonoma dammsugare, nämligen Electrolux Trilobite ZA1, klarar sig i test. Vi har även analyserat testet med Trilobiten och jämfört detta med antaget beteende hos Trilobiten ifall den hade varit implementerad med sökalgoritmerna STC eller TTA. Hur fungerar sökalgoritmerna? Hur kan en autonom dammsugare hitta på en hel obekant yta? Hur beter sig Electrolux Trilobite ZA1? Täcker de alla en obekant yta? Är de effektiva?

No description available.

On the category of representations of a given quiver we define a tensor product point-wise and arrow-wise. The corresponding Clebsch-Gordan problem of how the tensor product of indecomposable representations decomposes into a direct sum of indecomposable representations is the topic of this thesis. The choice of tensor product is motivated by an investigation of possible ways to modify the classical tensor product from group representation theory to the case of quiver representations. It turns out that all of them yield tensor products which essentially are the same as the point-wise tensor product. We solve the Clebsch-Gordan problem for all Dynkin quivers of type A, D and E6, and provide explicit descriptions of their respective representation rings. Furthermore, we investigate how the tensor product interacts with Galois coverings. The results obtained are used to solve the Clebsch-Gordan problem for all extended Dynkin quivers of type Ãn and the double loop quiver with relations βα=αβ=αn=βn=0.