Spelling suggestions: "subject:"noncompletion"" "subject:"oncompletion""
131 |
Towards a Bezout-type Theory of Affine VarietiesMondal, Pinaki 21 April 2010 (has links)
We study projective completions of affine algebraic varieties (defined over an algebraically closed field K) which are given by filtrations, or equivalently, integer valued `degree like functions' on their rings of regular functions. For a polynomial map P := (P_1, ..., P_n): X -> K^n of affine varieties with generically finite fibers, we prove that there are completions of the source such that the intersection of completions of the hypersurfaces {P_j = a_j} for generic (a_1, ..., a_n) in K^n coincides with the respective fiber (in short, the completions `do not add points at infinity' for P). Moreover, we show that there are `finite type' completions with the latter property, i.e. determined by the maximum of a finite number of `semidegrees', by which we mean degree like functions that send products into sums. We characterize the latter type completions as the ones for which ideal I of the `hypersurface at infinity' is radical. Moreover, we establish a one-to-one correspondence between the collection of minimal associated primes of I and the unique minimal collection of semidegrees needed to define the corresponding degree like function. We also prove an `affine Bezout type' theorem for polynomial maps P with finite fibers that admit semidegrees corresponding to completions that do not add points at infinity for P. For a wide class of semidegrees of a `constructive nature' our Bezout-type bound is explicit and sharp.
|
132 |
Solution Approaches For Flexible Job Shop Scheduling ProblemsBalci, Serife Aytug 01 February 2013 (has links) (PDF)
discrete parts manufacturing industries. We are motivated by the production
environment of Roketsan Missiles Industries Incorporation, operating at Turkish
defense industry. Our objective is to minimize the total weighted completion
times of the jobs in the system.
We formulate the problem as a mixed integer linear program and find that our
model could find optimal solutions only to small sized problem instances. For
medium and large sized problem instances, we develop heuristic algorithms with
high quality approximate solutions in reasonable solution time.
Our proposed heuristic algorithm has hierarchical approach and benefits from
optimization models and priority rules. We improve the heuristic method via
best move with non-blocking strategy and design several experiments to test the
performances. Our computational results have revealed that proposed heuristic
algorithm can find high quality solutions to large sized instances very quickly.
|
133 |
Towards a Bezout-type Theory of Affine VarietiesMondal, Pinaki 21 April 2010 (has links)
We study projective completions of affine algebraic varieties (defined over an algebraically closed field K) which are given by filtrations, or equivalently, integer valued `degree like functions' on their rings of regular functions. For a polynomial map P := (P_1, ..., P_n): X -> K^n of affine varieties with generically finite fibers, we prove that there are completions of the source such that the intersection of completions of the hypersurfaces {P_j = a_j} for generic (a_1, ..., a_n) in K^n coincides with the respective fiber (in short, the completions `do not add points at infinity' for P). Moreover, we show that there are `finite type' completions with the latter property, i.e. determined by the maximum of a finite number of `semidegrees', by which we mean degree like functions that send products into sums. We characterize the latter type completions as the ones for which ideal I of the `hypersurface at infinity' is radical. Moreover, we establish a one-to-one correspondence between the collection of minimal associated primes of I and the unique minimal collection of semidegrees needed to define the corresponding degree like function. We also prove an `affine Bezout type' theorem for polynomial maps P with finite fibers that admit semidegrees corresponding to completions that do not add points at infinity for P. For a wide class of semidegrees of a `constructive nature' our Bezout-type bound is explicit and sharp.
|
134 |
Verification of Pipelined CiphersLam, Chiu Hong January 2009 (has links)
The purpose of this thesis is to explore the formal verification technique of completion functions and equivalence checking by verifying two pipelined cryptographic circuits, KASUMI and WG ciphers. Most of current methods of communications either involve a personal computer or a mobile phone. To ensure that the information is exchanged in a secure manner, encryption circuits are used to transform the information into an unintelligible form. To be highly secure, this type of circuits is generally designed such that it is hard to analyze. Due to this fact, it becomes hard to locate a design error in the verification of cryptographic circuits. Therefore, cryptographic circuits pose significant challenges in the area of formal verification. Formal verification use mathematics to formulate correctness criteria of designs, to develop mathematical models of designs, and to verify designs against their correctness criteria.
The results of this work can extend the existing collection of verification methods as well as benefiting the area of cryptography. In this thesis, we implemented the KASUMI cipher in VHDL, and we applied the optimization technique of pipelining to create three additional implementations of KASUMI. We verified the three pipelined implementations of KASUMI with completion functions and equivalence checking. During the verification of KASUMI, we developed a methodology to handle the completion functions efficiently based on VHDL generic parameters. We implemented the WG cipher in VHDL, and we applied the optimization techniques of pipelining and hardware re-use to create an optimized implementation of WG. We verified the optimized implementation of WG with completion functions and equivalence checking. During the verification of WG, we developed the methodology of ``skipping" that can decrease the number of verification obligations required to verify the correctness of a circuit. During the verification of WG, we developed a way of applying the completion functions approach such that it can deal with a circuit that has been optimized with hardware re-use.
|
135 |
Verification of Pipelined CiphersLam, Chiu Hong January 2009 (has links)
The purpose of this thesis is to explore the formal verification technique of completion functions and equivalence checking by verifying two pipelined cryptographic circuits, KASUMI and WG ciphers. Most of current methods of communications either involve a personal computer or a mobile phone. To ensure that the information is exchanged in a secure manner, encryption circuits are used to transform the information into an unintelligible form. To be highly secure, this type of circuits is generally designed such that it is hard to analyze. Due to this fact, it becomes hard to locate a design error in the verification of cryptographic circuits. Therefore, cryptographic circuits pose significant challenges in the area of formal verification. Formal verification use mathematics to formulate correctness criteria of designs, to develop mathematical models of designs, and to verify designs against their correctness criteria.
The results of this work can extend the existing collection of verification methods as well as benefiting the area of cryptography. In this thesis, we implemented the KASUMI cipher in VHDL, and we applied the optimization technique of pipelining to create three additional implementations of KASUMI. We verified the three pipelined implementations of KASUMI with completion functions and equivalence checking. During the verification of KASUMI, we developed a methodology to handle the completion functions efficiently based on VHDL generic parameters. We implemented the WG cipher in VHDL, and we applied the optimization techniques of pipelining and hardware re-use to create an optimized implementation of WG. We verified the optimized implementation of WG with completion functions and equivalence checking. During the verification of WG, we developed the methodology of ``skipping" that can decrease the number of verification obligations required to verify the correctness of a circuit. During the verification of WG, we developed a way of applying the completion functions approach such that it can deal with a circuit that has been optimized with hardware re-use.
|
136 |
Cohomology Jumping Loci and the Relative Malcev CompletionNarkawicz, Anthony Joseph 12 December 2007 (has links)
Two standard invariants used to study the fundamental group of the complement X of a hyperplane arrangement are the Malcev completion of its fundamental group G and the cohomology groups of X with coefficients in rank one local systems. In this thesis, we develop a tool that unifies these two approaches. This tool is the Malcev completion S_p of G relative to a homomorphism p from G into (C^*)^N. The relative completion S_p is a prosolvable group that generalizes the classical Malcev completion; when p is the trivial representation, S_p is the Malcev completion of G. The group S_p is tightly controlled by the cohomology groups H^1(X,L_{p^k}) with coefficients in the irreducible local systems L_{p^k} associated to the representation p.The pronilpotent Lie algebra u_p of the prounipotent radical U_p of S_p has been described by Hain. If p is the trivial representation, then u_p is the holonomy Lie algebra, which is well-known to be quadratically presented. In contrast, we show that when X is the complement of the braid arrangement in complex two-space, there are infinitely many representations p from G into (C^*)^2 for which u_p is not quadratically presented.We show that if Y is a subtorus of the character torus T containing the trivial character, then S_p is combinatorially determined for general p in Y. We do not know whether S_p is always combinatorially determined. If S_p is combinatorially determined for all characters p of G, then the characteristic varieties of the arrangement X are combinatorially determined.When Y is an irreducible subvariety of T^N, we examine the behavior of S_p as p varies in Y. We define an affine group scheme S_Y over Y such that if Y = {p}, then S_Y is the relative Malcev completion S_p. For each p in Y, there is a canonical homomorphism of affine group schemes from S_p into the affine group scheme which is the restriction of S_Y to p. This is often an isomorphism. For example, if there exists p in Y whose image is Zariski dense in G_m^N, then this homomorphism is an isomorphism for general p in Y. / Dissertation
|
137 |
Non-parametric Bayesian Learning with Incomplete DataWang, Chunping January 2010 (has links)
<p>In most machine learning approaches, it is usually assumed that data are complete. When data are partially missing due to various reasons, for example, the failure of a subset of sensors, image corruption or inadequate medical measurements, many learning methods designed for complete data cannot be directly applied. In this dissertation we treat two kinds of problems with incomplete data using non-parametric Bayesian approaches: classification with incomplete features and analysis of low-rank matrices with missing entries.</p><p>Incomplete data in classification problems are handled by assuming input features to be generated from a mixture-of-experts model, with each individual expert (classifier) defined by a local Gaussian in feature space. With a linear classifier associated with each Gaussian component, nonlinear classification boundaries are achievable without the introduction of kernels. Within the proposed model, the number of components is theoretically ``infinite'' as defined by a Dirichlet process construction, with the actual number of mixture components (experts) needed inferred based upon the data under test. With a higher-level DP we further extend the classifier for analysis of multiple related tasks (multi-task learning), where model components may be shared across tasks. Available data could be augmented by this way of information transfer even when tasks are only similar in some local regions of feature space, which is particularly critical for cases with scarce incomplete training samples from each task. The proposed algorithms are implemented using efficient variational Bayesian inference and robust performance is demonstrated on synthetic data, benchmark data sets, and real data with natural missing values.</p><p>Another scenario of interest is to complete a data matrix with entries missing. The recovery of missing matrix entries is not possible without additional assumptions on the matrix under test, and here we employ the common assumption that the matrix is low-rank. Unlike methods with a preset fixed rank, we propose a non-parametric Bayesian alternative based on the singular value decomposition (SVD), where missing entries are handled naturally, and the number of underlying factors is imposed to be small and inferred in the light of observed entries. Although we assume missing at random, the proposed model is generalized to incorporate auxiliary information including missingness features. We also make a first attempt in the matrix-completion community to acquire new entries actively. By introducing a probit link function, we are able to handle counting matrices with the decomposed low-rank matrices latent. The basic model and its extensions are validated on</p><p>synthetic data, a movie-rating benchmark and a new data set presented for the first time.</p> / Dissertation
|
138 |
Human resource development of Hispanic students in a large Hispanic-majority community college in south Texas: student entry characteristics as predictors of successful course completion and retention in face-to-face and distance educationCole, Brenda S. 02 June 2009 (has links)
Hispanic student success within community colleges is critical to our future
national economy and as such, was pertinent to this Human Resource Development
(HRD) research. In this ex-post-facto study, the researcher examined the student entry
characteristics of 2,523 Hispanic entering freshmen enrolled anytime between Fall 2000
and Fall 2005 who attempted History, English Composition, or College Algebra for the
first time in either face-to-face or distance education courses at South Texas College.
The following student entry characteristics of the Hispanic students in the study
population were examined for their impact on successful course completion and
retention: age, country of elementary education, custody of minors, disabilities, English
as a second language, gender, high school diploma type, high school GPA, hours of
employment, income level indicators, intent to continue employment, intent to transfer,
intended length of enrollment, marital status, number of credit hours, parents’ education, participation in workforce programs in high school, reason for attending,
recent migrant work, resident status, and veteran status.
The resulting profile of Hispanic distance education student characteristics was
found to be similar to common characteristics noted in the literature for other distance
education non-Hispanic populations. Furthermore, the researcher identified significant
student entry characteristics for predicting the risk of failing to successfully complete
courses or to re-enroll. Finally, the researcher provided suggestions for further research
regarding Hispanic student performance and success in higher education as a
responsibility of the work of Hispanic human resource development within community
colleges. This study provides empirical findings related to the student entry
characteristics construct found in current theoretical models of retention in commuter
institutions of higher education. The researcher recommends expanding this research to
other elements of theoretical models of student departure such as the external
environment and the internal campus environment. Doing this will support the further
refinement and development of the theory and confirm its applicability to local
institutional populations.
|
139 |
Approximation and Optimal Algorithms for Scheduling Jobs subject to Release DatesYu, Su-Jane 30 July 2003 (has links)
In this dissertation, we study the single machine scheduling problem with an objective of minimizing the total completion time subject to release dates. The problem, denoted 1|rj £UCj ,was known to be strongly NP-hard and both theoretically and practically important. The focus of the research in this dissertation is to develop the efficient algorithms for solving the 1|rj|£UCj problem.
This thesis contains two parts.
In the first part, the theme concerns the approximation approach. We derive a necessary and sufficient condition for local optimality, which can be implemented as a priority rule and be used to construct three heuristic algorithms with running times of O(n log n). By ¡¨local optimality¡¨, we mean the optimality of all candidates whenever a job is selected in a schedule, without considering the other jobs preceding or following. This is the most broadly considered concepts of locally optimal rule. We also identify a dominant subset which is strictly contained in each of all known dominant subsets, where a dominant subset is a set of solutions containing all optimal schedules.
In the second part, we develop our optimality algorithms for the 1|rj |£UCj problem. First, we present a lemma for estimating the sum of delay times of the rest jobs, if the starting time is delayed a period of time in a schedule. Then, using the lemma, partially, we proceed to develop a new partition property and three dominance theorems, that will be used and have improved the branch-and-bound algorithms for our optimization approach. By exploiting the insights gained from our heuristics as a branching scheme and by exploiting our heuristics as an upper bounding procedure, we propose three branch-and-bound algorithms. Our algorithms can optimally solve the problem up to 120 jobs, which is known to be the best till now.
|
140 |
AN ADVISORY SYSTEM FOR THE DEVELOPMENT OF UNCONVENTIONAL GAS RESERVOIRSWei, Yunan 16 January 2010 (has links)
With the rapidly increasing demand for energy and the increasing prices for oil
and gas, the role of unconventional gas reservoirs (UGRs) as energy sources is becoming
more important throughout the world. Because of high risks and uncertainties associated
with UGRs, their profitable development requires experts to be involved in the most
critical development stages, such as drilling, completion, stimulation, and production.
However, many companies operating UGRs lack this expertise. The advisory system we
developed will help them make efficient decisions by providing insight from analogous
basins that can be applied to the wells drilled in target basins.
In North America, UGRs have been in development for more than 50 years. The
petroleum literature has thousands of papers describing best practices in management of
these resources. If we can define the characteristics of the target basin anywhere in the
world and find an analogous basin in North America, we should be able to study the best
practices in the analogous basin or formation and provide the best practices to the
operators.
In this research, we have built an advisory system that we call the
Unconventional Gas Reservoir (UGR) Advisor. UGR Advisor incorporates three major
modules: BASIN, PRISE and Drilling & Completion (D&C) Advisor. BASIN is used to identify the reference basin and formations in North America that are the best analogs to
the target basin or formation. With these data, PRISE is used to estimate the technically
recoverable gas volume in the target basin. Finally, by analogy with data from the
reference formation, we use D&C Advisor to find the best practice for drilling and
producing the target reservoir.
To create this module, we reviewed the literature and interviewed experts to
gather the information required to determine best completion and stimulation practices
as a function of reservoir properties. We used these best practices to build decision trees
that allow the user to take an elementary data set and end up with a decision that honors
the best practices. From the decision trees, we developed simple computer algorithms
that streamline the process.
|
Page generated in 0.0785 seconds