Spelling suggestions: "subject:"eomputer algorithms"" "subject:"aomputer algorithms""
31 
Combinatorial property of prefixfree trees with some regular constraints /Yeung, Siu Yin. January 2004 (has links)
Thesis (M. Phil.)Hong Kong University of Science and Technology, 2004. / Includes bibliographical references (leaves 6768). Also available in electronic version. Access restricted to campus users.

32 
Boolean matching and levelbased technology mapping /Ciric, Jovanka. January 2001 (has links)
Thesis (Ph. D.)University of Washington, 2001. / Vita. Includes bibliographical references (leaves 9197).

33 
Improved results on models of greedy and primaldual algorithms /Kwon, Hyukjoon. January 2008 (has links)
Thesis (M.Sc.)York University, 2008. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 4951). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.882004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR45954

34 
Cache miss analysis of WalshHadamard Transform algorithms /Furis, Mihai Alexandru. Johnson, Jeremy. January 2003 (has links)
Thesis (M.S.)Drexel University, 2003. / Includes abstract. Includes bibliographical references (leaves 6465).

35 
Knowledge frontier discovery a thesis presented to the faculty of the Graduate School, Tennessee Technological University /Honeycutt, Matthew Burton, January 2009 (has links)
Thesis (M.S.)Tennessee Technological University, 2009. / Title from title page screen (viewed on Feb. 24, 2010). Bibliography: leaves 7883.

36 
Sequence mining algorithmsZhang, Minghua, 張明華 January 2004 (has links)
published_or_final_version / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

37 
Crossdomain subspace learningSi, Si, 斯思 January 2010 (has links)
published_or_final_version / Computer Science / Master / Master of Philosophy

38 
Medial axis simplification based on global geodesic slope and accumulated hyperbolic distanceWang, Rui, 王睿 January 2012 (has links)
The medial axis is an important shape representation and the computation of the medial axis is a fundamental research problem in computer graphics. Practically, the medial axis is widely used in various aspects of computer graphics, such as shape analysis, image segmentation, skeleton extraction and mesh generation and so forth. However, the applications of the medial axis have been limited by its sensitivity to boundary perturbations. This characteristic may lead to a number of noise branches and increase the complexity of the medial axis. To solve the sensitivity problem, it is critical to simplify the medial axis.
This thesis first investigates the algorithms for computing medial axes of different input shapes. Several algorithms for the filtration of medial axes are then reviewed, such as the local importance measurement algorithms, boundary smoothness algorithms, and the global algorithms. Two novel algorithms for the simplification of the medial axis are proposed to generate a stable and simplified medial axis as well as its reconstructed boundary.
The developed Global Geodesic Slope(GGS) algorithm for the medial axis simplification is based on the global geodesic slope defined in this thesis, which combines the advantages of the global and the local algorithms. The GGS algorithm prunes the medial axis according to local features as well as the relative size of the shape. It is less sensitive to boundary noises than the local algorithms, and can maintain the features of the shape in highly concave regions while the global algorithms may not.
The other simplification algorithm we propose is the Accumulated Hyperbolic Distance(AHD) algorithm. It directly uses the evaluation criterion of the error, accumulated hyperbolic distance defined in this thesis, as the pruning measurement in the filtration process. It guarantees the upper bound of the error between the reconstructed shape and the original one within the defined threshold. The AHD algorithm avoids sudden changes of the reconstructed shape as the defined threshold changes. / published_or_final_version / Computer Science / Master / Master of Philosophy

39 
New results on online job schedulingZhu, Jianqiao., 朱剑桥. January 2013 (has links)
This thesis presents several new results on online job scheduling. Job scheduling is a basic requirement of many practical computer systems, and the scheduling behavior directly affects a system’s performance. In theoretical aspect, scheduling scenarios are abstracted into scheduling models, which are studied mathematically. In this thesis, we look into a variety of scheduling models which are under active research. We incorporate these models and organize them into generalized pictures.
We first study nonclairvoyant scheduling to minimize weighted flow time on two different multiprocessor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the nonclairvoyant model, the online scheduler has no information about the actual job size and degree of speedup due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)competitive algorithms for this problem under the unitweight multiprocessor setting [13, 14] as well as the weighted singleprocessor setting [5]. This thesis shows the first O(1)competitive algorithm for weighted flow time in the multiprocessor setting.
In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of nonclairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multiprocessor model. In this thesis we take a first step to study nonclairvoyant scheduling on this multiprocessor model. Motivated by the literature on 2machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a nonclairvoyant algorithm that is O(1)competitive for weighted flow time.
This thesis also initiates the study of online scheduling with rejection penalty in the nonclairvoyant setting. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant singleprocessor setting [3, 10] and has produced O(1)competitive online algorithm for jobs with arbitrary weights and penalties. This thesis gives the first nonclairvoyant algorithms that are O(1)competitive for minimizing the total user cost on a single processor and multiprocessors, when using slightly faster (i.e., (1 + ∈)speed for any ∈> 0) processors. Note that if no extra speed is allowed, no online algorithm can be O(1)competitive even for minimizing (unweighted) flow time alone.
The above results assume a processor running at a fixed speed. This thesis shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the abovementioned user cost and energy. This thesis gives two O(1)competitive nonclairvoyant algorithms for minimizing the user cost plus energy on a single processor and multiprocessors, respectively. / published_or_final_version / Computer Science / Master / Master of Philosophy

40 
New competitive algorithms for online job schedulingLi, Rongbin, 李榕滨 January 2014 (has links)
Job scheduling, which greatly impacts on the system performance, is a fundamental problem in computer science. In this thesis, we study three kinds of scheduling problems, that is, deadline scheduling, due date scheduling, and flow time scheduling. Traditionally, the major concern for scheduling problems is the system performance, i.e. the “Quality of Service" (QoS). Different scheduling problems use different QoS measurements. For deadline scheduling, the most common QoS to optimize is the throughput; for due date scheduling, it is the total quoted lead time; and for flow time scheduling, it is the total (weighted) flow time.
Recently, energy efficiency is becoming more and more important. Many modern processors adopt technologies like dynamic speed scaling and sleep management to reduce energy usage. Much work is done on energy efficient scheduling. In this thesis, we study this topic for all three kinds of scheduling mentioned above.
Meanwhile, we also revisit the traditional flow time scheduling problem to optimize the QoS. However, we consider the problem in a more realistic model that makes the problem much more challenging.
Below is the summary of the problems studied in the thesis. First, we consider the tradeoff between energy and throughput for deadline scheduling. Specifically, each job is associated with a value (or importance) and a deadline. A scheduling algorithm is allowed to discard some of the jobs, and the objective is to minimize total energy usage plus total value of discarded jobs. When processor's maximum speed is unbounded, we propose an O(1)competitive algorithm. When processor's maximum speed is bounded, we show a strong lower bound and give an algorithm with a competitive ratio close to that lower bound.
Second, we study energy efficient due date scheduling. Jobs arrive online with different sizes and weights. An algorithm needs to assign a due date to each job once it arrives, and complete the job by the due date. The quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We propose a competitive algorithm for minimizing the sum of the total quoted lead time and energy usage.
Next, we consider flow time scheduling with power management on multiple machines. Jobs with arbitrary sizes and weights arrive online. Each machine consumes different amount of energy when processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage and, meanwhile, guarantee high QoS. Our result is an O(1)competitive algorithm to minimize total weighted flow time plus energy usage.
Finally, we consider the traditional preemptive scheduling to minimize total flow time. Previous theoretical results often assume preemption is free, which is not true for most systems. We investigate the complexity of the problem when a processor has to perform a certain amount of overhead before it resumes the execution of a job preempted before. We first show an Ω(n^(1/4)) lower bound, and then, propose a (1+ε)speed (1+ 1/ε )competitive algorithm in resource augmentation model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Page generated in 0.0804 seconds