登入
選單
返回
Google圖書搜尋
Generalized Kraft's Inequality and Discrete K-Modal Search
Anmol Mathur
University of Illinois at Urbana-Champaign. Department of Computer Science
Edward 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