Thesis (Ph. D.)--Carleton University, 2003. / Includes bibliographical references (p. 226-237). Also available in electronic format on the Internet.

Thesis (Ph. D.)--UCLA, 2008. / Vita. Includes bibliographical references (leaves 473-520).

Thesis (M.S.)--University of North Carolina at Wilmington, 2004. / Includes bibliographical references (leaf : 32).

Thesis (Ph. D.)--University of Florida, 2004. / Title from title page of source document. Document formatted into pages; contains 130 pages. Includes vita. Includes bibliographical references.

Thesis (Ph. D. in Mathematics)--Vanderbilt University, Dec. 2004. / Title from title screen. Includes bibliographical references.

Thesis (M.Sc.)--Acadia University, 2006. / Includes bibliographical references (leaves 142-143). Also available on the Internet via the World Wide Web.

Thesis (M.C.S.)--Carleton University, 1993. / Also available in electronic format on the Internet.

Thesis (Ph.D.)--York University, 2005. Graduate Programme in Philosophy. / Typescript. Includes bibliographical references (leaves 227-240). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://wwwlib.umi.com/cr/yorku/fullcit?pNR11615

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.

When designing real-time systems, we want to prove that they will satisfy given timing constraints at run time. The main objective of real-time scheduling theory is to analyze properties of mathematical models that capture the temporal behaviors of such systems. These models typically consist of a collection of computational tasks, each of which generates an infinite sequence of task activations. In this thesis we study different classes of models and their corresponding analysis problems. First, we consider models of mixed-criticality systems. The timing constraints of these systems state that all tasks must meet their deadlines for the run-time scenarios fulfilling certain assumptions, for example on execution times. For the other scenarios, only the most important tasks must meet their deadlines. We study both tasks with sporadic activation patterns and tasks with complicated activation patterns described by arbitrary directed graphs. We present sufficient schedulability tests, i.e., methods used to prove that a given collection of tasks will meet their timing constraints under a particular scheduling algorithm. Second, we consider models where tasks can lock mutually exclusive resources and have activation patterns described by directed cycle graphs. We present an optimal scheduling algorithm and an exact schedulability test. Third, we address a pair of longstanding open problems in real-time scheduling theory. These concern the computational complexity of deciding whether a collection of sporadic tasks are schedulable on a uniprocessor. We show that this decision problem is strongly coNP-complete in the general case. In the case where the asymptotic resource utilization of the tasks is bounded by a constant smaller than 1, we show that it is weakly coNP-complete.