返回Google圖書搜尋

Generalized Kraft's Inequality and Discrete K-Modal Search

Anmol MathurUniversity of Illinois at Urbana-Champaign. Department of Computer ScienceEdward M. Reingold

出版	Department of Computer Science, University of Illinois at Urbana-Champaign, 1993
URL	http://books.google.com.hk/books?id=8EWwm7Y1uaUC&hl=&source=gbs_api

註釋Abstract: "A function f:R [approaches] R is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for k = 3, and near-optimal algorithms when k [> or =] 5 and odd. A novel generalization of Kraft's inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeroes of a k-modal function