Darbo tikslas – sukurti bendrą prieigos tinklo modeliavimo metodiką bei jos programinę realizaciją, atitinkančią šiuos reikalavimus: • n užduotų prieigos tinklo parametrų reikšmių optimalus nustatymas pagal m užduotų prieigos tinklo kokybės apribojimų, kai n ≥ 1, o m ≥ 0; • optimalus stočių koordinačių nustatymas mobiliojo telefono ryšio tinklui; • optimalus stočių koordinačių nustatymas laidinio telefono ryšio tinklui; Darbo pradžioje apžvelgiamos telekomunikacijų sektoriaus užduotys, kurios gali būti sprendžiamos kombinatorinio optimizavimo metodais. Taipogi pristatomi ir suklasifikuojami galimi šių užduočių sprendimo metodai. Tiriamojoje darbo dalyje pristatomas daugiaparametrinis prieigos tinklo optimizavimo algoritmas integruotas su stočių išdėstymo algoritmais. Stočių išdėstymui pateikiami du meta-euristiniai algoritmai: • Skruzdžių kolonijos algoritmas, papildytas lokalios paieškos procedūra; • Genetinis algoritmas, papildytas lokalios paieškos procedūra. Minėtų algoritmų realizacijos skirstomos pagal šias prieigos tinklo ryšio topologijas: • Mobiliojo telefono ryšio tinklui; • Fiksuoto telefono ryšio tinklui. Esminiai darbe pasiekti rezultatai: • Sukurta universali metodika, leidžianti kurti realius prieigos tinklo modelius; • Sukurta šios metodikos programinė realizacija. Darbe nagrinėjamų uždavinių ir algoritmų pagrindu buvo paskelbti ir pristatyti šie straipsniai: • „Prieigos tinklo parametrų optimalaus... [toliau žr. visą tekstą] / The objective of this work is creation of telecommunication network approach algorithm and its realization. The created algorithm must fulfill following requirements: • optimal values evaluation of n given network approach parameters with m given network approach quality constrains, where n ≥ 1, o m ≥ 0; • optimal solution for transmitters placement problem in mobile phone network; • optimal solution for transmitters placement problem in fixed phone network; In the beginning of this paper we present a set of telecommunication segment problems which can be solved using combinatorial optimization methods. Also we present a set of combinatorial optimization methods which can be used for solving these problems. Finally we present a graphical classification of analyzed problems and connect it with algorithms which are capable for solving it. In the research part of this paper we present a multi parametric network approach optimization algorithm united with algorithms for placing transmitters. Next we present two Meta heuristics based optimization algorithms: • Ant Colony Optimization algorithm with local search procedure; • Genetic algorithm with local search procedure. The realization of these two algorithms depends on the topology of the network approach being analyzed. In this paper we analyze two most common types of network approaches: • Mobile phone network approach; • Fixed phone network approach. The two main achievements of... [to full text]

This thesis explores the structure of games, including both the internal structure of various games and also the structure of classes of games as partially ordered sets. Internal structure is explored through consideration of juxtapositions of game positions and how the underlying games interact. We look at ordinal sums and introduce side-sums as a means of understanding this interaction, giving a full solution to a Toppling Dominoes variant through its application. Loopy games in which only one player is allowed a pass move, referred to as Oslo games, are introduced and their game structure explored. The poset of Oslo games is shown to form a distributive lattice. The Oslo forms of Wythoff’s game, Grundy’s game and octal .007 are introduced and full solutions given. Finally, the poset of option-closed games is given up to day 3 and all are shown to form a planar lattice. The option-closed game of Cricket Pitch is also fully analyzed.

Cette recherche porte sur la lexicologie, la lexicographie et l’enseignement/apprentissage du lexique. Elle s’inscrit dans le cadre du projet Modélisation ontologique des savoirs lexicographiques en vue de leur application en linguistique appliquée, surnommé Lexitation, qui est, à notre connaissance, la première tentative d’extraction des savoirs lexicographiques — i.e. connaissances déclaratives et procédurales utilisées par des lexicographes — utilisant une méthode expérimentale. Le projet repose sur le constat que les savoirs lexicographiques ont un rôle crucial à jouer en lexicologie, mais aussi en enseignement/apprentissage du lexique. Dans ce mémoire, nous décrirons les méthodes et les résultats de nos premières expérimentations, effectuées à l’aide du Think Aloud Protocol (Ericsson et Simon, 1993). Nous expliquerons l’organisation générale des expérimentations et comment les savoirs lexicographiques extraits sont modélisés pour former une ontologie. Finalement, nous discuterons des applications possibles de nos travaux en enseignement du lexique, plus particulièrement pour la formation des maîtres. / This research is about lexicology, lexicography and vocabulary teaching/learning. It is part of a project called Ontologization of lexicographic abilites for use in the fields of applied linguistics, nicknamed Lexitation, which is, to our knowledge, the first attempt at extracting lexicographic abilities using experimental techniques. The project relies on the assumption that lexicographic abilities play a role in teaching and acquisition of lexical knowledge, and not only in lexicography per se. We will describe the methods and results of our initial set of experiments, that are based on the use of so-called Think Aloud Protocol (Ericsson et Simon, 1993). We will explain how experiments have been set up and how we are currently proceeding with the extraction and modeling of various types of knowledge and strategies used by lexicographers while performing lexicographic tasks. Finally, we will present possible applications of our work in the field of language teaching, more specifically, teachers’ training.

Cette étude porte sur les différentes formalisations du sens linguistique dans le cadre de la théorie Sens-Texte (TST) ; elle s’intéresse notamment à la représentation sémantique, la représentation la plus importante dans la modélisation du sens d’énoncés et d’unités lexicales de la langue. Cette étude a trois objectifs : premièrement, décrire trois formalisations de la représentation sémantique existant dans la TST – les réseaux sémantiques, les définitions lexicographiques et les définitions de la BDéf (des définitions très formalisées) ; deuxièmement, identifier les disparités et les décalages entre les formalisations choisies ; troisièmement, proposer des modifications aux formalisations existantes pour réduire au maximum ces disparités. / This study explores the different formalisations of linguistic meaning as encountered in the Meaning-Text Theory (MST) framework. Its main interest is semantic representation, which is the most important representation in the modeling of the meaning of utterances and lexical units. This study has three objectives: first, describing three existing formalisations of semantic representation in the MST – semantic networks, lexicographical definitions, and BDéf definitions (definitions that are extremely formalized); second, identifying the discrepancies between these formalisations; finally, proposing modifications to these formalisations in order to reduce the disparities as much as possible.

Chronic Myelogenous Leukemia (CML) is a blood cancer that arises when hematopoietic cells acquire an abnormal protein known as BCR-ABL. Current therapies for CML include drugs that inhibit BCR-ABL. However, these drugs only suppress the disease and do not cure it. One reason is that BCR-ABL drugs fail to kill the primitive population of CML cells, referred to as leukemia stem cells (LSCs), which are responsible for initiating and propagating CML. Since LSCs are not killed, the cancer is not cured and many affected patients eventually relapse. Recent studies suggest that LSCs are protected from current therapies by the bone marrow micro-environment where they reside. There, cytokine signaling molecules are present, which mediate processes that protect LSCs from BCR-ABL drugs. The stem cell factor (SCF) is one of these signaling molecules. It activates the receptor c-Kit located on the surface of LSCs, and this activation in turn allows proliferating LSCs to resist BCR-ABL drugs, even without prior exposure to these drugs, i.e., innate resistance is observed. In this thesis, the mechanism of this innate resistance is investigated, so that a suitable treatment strategy can be developed. To this end, a co-agent approach based on synthetic antibodies (sABs) is proposed to inhibit the receptor c-Kit, with the goal of disrupting its activation by the ligand SCF. This disruption should in turn block the SCF-mediated innate resistance, thus potentially restoring BCR-ABL drug apoptotic activity. The method for this disruption involves targeting the c-Kit structural susceptibility. Specifically, the sABs are designed via antibody phage display technology to target the D1–D2–D3 domains representing the SCF binding sites, hence preventing downstream pathway activation. The hypothesis is that, by blocking the SCF-mediated innate resistance, a suitable combination of such an sAB co-agent and a BCR-ABL drug should be conducive to suppressing LSCs, thereby providing a potential means to improve CML treatment. In addition, to assess the performance of the proposed treatment strategy, a set of in vitro tests is conducted, focusing on performance behaviors such as cell binding, cell death, and the progenitor inhibition. The experimental results support the hypothesis that the proposed combinatorial strategy is indeed a promising approach to mitigate the innate resistance, thus restoring BCR-ABL drug apoptotic activity.

The advent of new technology enhance the speed and reduce the cost for sequencing biological data. Making biological sense of this genomic data is a big challenge to the algorithm design as well as the high performance computing society. There are many problems in Bioinformatics, such as how new functional genes arise, why genes are organized into chromosomes, how species are connected through the evolutionary tree of life, or why arrangements are subject to change. Phylogenetic analyses have become essential to research on the evolutionary tree of life. It can help us to track the history of species and the relationship between different genes or genomes through millions of years. One of the fundamentals for phylogenetic construction is the computation of distances between genomes. Since there are much more complicated combinatoric patterns in rearrangement events, the distance computation is still a hot topic as much belongs to mathematics as to biology. For the distance computation with input of two genomes containing unequal gene contents (with insertions/deletions and duplications) the problem is especially hard. In this thesis, we will discuss about our contributions to the distance estimation for unequal gene order data. The problem of finding the median of three genomes is the key process in building the most parsimonious phylogenetic trees from genome rearrangement data. For genomes with unequal contents, to the best of our knowledge, there is no algorithm that can help to find the median. In this thesis, we make our contributions to the median computation in two aspects. 1) Algorithm engineering aspect, we harness the power of streaming graph analytics methods to implement an exact DCJ median algorithm which run as fast as the heuristic algorithm and can help construct a better phylogenetic tree. 2) Algorithmic aspect, we theoretically formulate the problem of finding median with input of genomes having unequal gene content, which leads to the design and implementation of an efficient Lin-Kernighan heuristic based median algorithm. Inferring phylogenies (evolutionary history) of a set of given species is the ultimate goal when the distance and median model are chosen. For more than a decade, biologists and computer scientists have studied how to infer phylogenies by the measurement of genome rearrangement events using gene order data. While evolution is not an inherently parsimonious process, maximum parsimony (MP) phylogenetic analysis has been supported by widely applied to the phylogeny inference to study the evolutionary patterns of genome rearrangements. There are generally two problems with the MP phylogenetic arose by genome rearrangement: One is, given a set of modern genomes, how to compute the topologies of the according phylogenetic tree; Another is, given the topology of a model tree, how to infer the gene orders of the ancestor species. To assemble a MP phylogenetic tree constructor, there are multiple NP hard problems involved, unfortunately, they organized as one problem on top of other problems. Which means, to solve a NP hard problem, we need to solve multiple NP hard sub-problems. For phylogenetic tree construction with the input of unequal content genomes, there are three layers of NP hard problems. In this thesis, we will mainly discuss about our contributions to the design and implementation of the software package DCJUC (Phylogeny Inference using DCJ model to cope with Unequal Content Genomes), that can help to achieve both of these two goals. Aside from the biological problems, another issue we need to concern is about the use of the power of parallel computing to assist accelerating algorithms to handle huge data sets, such as the high resolution gene order data. For one thing, all of the method to tackle with phylogenetic problems are based on branch and bound algorithms, which are quite irregular and unfriendly to parallel computing. To parallelize these algorithms, we need to properly enhance the efficiency for localized memory access and load balance methods to make sure that each thread can put their potentials into full play. For the other, there is a revolution taking place in computing with the availability of commodity graphical processors such as Nvidia GPU and with many-core CPUs such as Cray-XMT, or Intel Xeon Phi Coprocessor with 60 cores. These architectures provide a new way for us to achieve high performance at much lower cost. However, code running on these machines are not so easily programmed, and scientific computing is hard to tune well on them. We try to explore the potentials of these architectures to help us accelerate branch and bound based phylogenetic algorithms.

Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

M.Sc. University of KwaZulu-Natal, Durban 2013.

The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers. / Graduate / 0984 / 0405 / bbird@uvic.ca