Spelling suggestions: "subject:"found"" "subject:"sound""
111 |
Efficient Evaluation of Set ExpressionsMirzazadeh, Mehdi January 2014 (has links)
In this thesis, we study the problem of evaluating set expressions over sorted sets in the comparison model. The problem arises in the context of evaluating search queries in text database systems; most text search engines maintain an inverted list, which consists of a set of documents that contain each possible word. Thus, answering a query is reduced to computing the union, the intersection, or a more complex set expression over sets of documents containing the words in the query.
At the first step, for a given expression on a number of sets and the sizes of the sets, we investigate the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We prove lower bounds and provide algorithms with the matching running time up to a constant factor. We then refine the problem further and design an algorithm that computes such expressions according to the degree by which the input sets are interleaved rather than only considering sets sizes. %We prove the running time of our algorithm is asymptotically optimal. We prove the optimality of our algorithm by way of presenting a matching lower bound sensitive to the interleaving measure.
The algorithms we present are different in the set of set operators they allow in input expressions. We provide algorithms that are worst-case optimal for inputs with union, intersection, and symmetric difference operators. One of the algorithms we provide also supports minus and complement operators and is conjectured to be optimal when an input is allowed to contain these operators as well. We also provide a worst-case optimal algorithm for the form of problem where the input may contain "threshold'" operators, which generalize union and intersection operators: for a number t, a t-threshold operator selects elements that appear in at least in t of the operand sets. Finally, the adaptive algorithm we provide supports union and intersection operators.
|
112 |
A mixed integer approach for the transient case of gas network optimizationMoritz, Susanne. Unknown Date (has links)
Techn. University, Diss., 2006--Darmstadt.
|
113 |
The application of the inclusion-exclusion principle in learning monotone boolean functionsGaffney, Christopher T., January 2008 (has links)
Thesis (M.S.)--University of Nevada, Reno, 2008. / "May, 2008." Includes bibliographical references (leaves 63-64). Online version available on the World Wide Web.
|
114 |
Two Fermion bound state equation using light front Tamm-Dancoff field theory in 3+1 dimensions.Wort, Philip M. (Philip Michael), Carleton University. Dissertation. Physics. January 1992 (has links)
Thesis (Ph. D.)--Carleton University, 1992. / Also available in electronic format on the Internet.
|
115 |
Static dynamic : an urban outward bound centre for youth. An explanatory document submitted in partial fulfilment of the requirements for the degree of Master of Architecture (Professional), Unitec New Zealand /Yap, Alby. Unknown Date (has links)
Thesis (M.Arch)--Unitec New Zealand, 2009. / Statement of responsibility from cover. Landscape format. Includes bibliographical references (leaves 86-87).
|
116 |
A study of the effectiveness of incorporating expressive arts group therapy into TRiO: Upward Bound services /Wright, Sarah J., January 2009 (has links)
Thesis (M.S.)--Missouri State University, 2009. / "May 2009." Includes bibliographical references (leaves 57-62). Also available online.
|
117 |
Modellierung und Optimierung von Hub-and-Spoke-Netzen mit beschränkter SortierkapazitätBlunck, Steffen. January 2005 (has links) (PDF)
Universiẗat, Diss., 2005--Karlsruhe.
|
118 |
Attitude and Learning at Upward Bound in the Field of StatisticsZukowski, Adam January 2008 (has links) (PDF)
No description available.
|
119 |
Analysis of Perceptron-Based Active LearningDasgupta, Sanjoy, Kalai, Adam Tauman, Monteleoni, Claire 17 November 2005 (has links)
We start by showing that in an active learning setting, the Perceptron algorithm needs $\Omega(\frac{1}{\epsilon^2})$ labels to learn linear separators within generalization error $\epsilon$. We then present a simple selective sampling algorithm for this problem, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error $\epsilon$ after asking for just $\tilde{O}(d \log \frac{1}{\epsilon})$ labels. This exponential improvement over the usual sample complexity of supervised learning has previously been demonstrated only for the computationally more complex query-by-committee algorithm.
|
120 |
Evaluación Técnica de Códigos Computacionales para la Optimización de la Operación de Corto Plazo en el SINGRomero Hernández, Cristian Leonardo January 2008 (has links)
El objetivo general del presente trabajo de título es realizar, mediante la aplicación de criterios
técnicos de ingeniería, una evaluación técnica del desempeño de los algoritmos de Relajación
Lagrangeana (RL) y Branch and Bound (B&B) en la búsqueda de soluciones para el problema de
optimización de corto plazo en el sistema eléctrico interconectado del norte grande (SING).
En la primera parte de la memoria se muestra el planteamiento general del problema de optimización
de la operación de corto plazo, el cual corresponde a un problema de optimización entero-mixto y un
conjunto de restricciones lineales mediante las cuales se establecen las características técnicas del
sistema. Por otra parte, la función objetivo de dicho problema de optimización corresponde a la
minimización de los costos asociados a la operación de las unidades en el horizonte de tiempo
evaluado.
Posteriormente, se muestra una revisión del estado del arte presentando algunas de las principales
técnicas utilizadas para resolver este tipo de problema: Lista de Prioridad, Programación Dinámica,
Unit Decommitment, RL, Método de Benders, B&B y Algoritmos Genéticos.
Para realizar la evaluación sobre los algoritmos de RL y B&B, se realizan programas en Matlab de
dichos métodos con el objeto de realizar pruebas que permitan efectuar un análisis comparativo de los
rendimientos de ambos algoritmos.
Se aplican dichos programas para resolver problemas de predespacho en un modelo reducido del
SING. De esta forma se puede observar el rendimiento de cada algoritmo respecto de su capacidad de
obtener soluciones factibles, calidad de las soluciones, uso de heurística para generar soluciones y
tiempos de ejecución requeridos. Adicionalmente, se puede estudiar la flexibilidad de ambos
algoritmos para considerar restricciones de mayor complejidad y sus limitaciones para resolver
predespacho en sistemas de dimensiones reales.
Se concluye que el algoritmo que presenta un rendimiento que permite resolver de manera más
eficiente el problema de predespacho en el SING corresponde al algoritmo RL, lo anterior debido
principalmente a los tiempos de ejecución requeridos para su aplicación en sistemas de dimensiones
reales y a que las soluciones generadas presentan una precisión del orden del 99% respecto a las
soluciones generadas por el otro algoritmo. Adicionalmente, se puede acotar que las actuales políticas
de operación aplicadas en el SING no representan una gran complejidad de programación y por lo
tanto, la heurística requerida no presenta una complejidad adicional.
|
Page generated in 0.0511 seconds