國立清華大學

資訊工程學系

Department Of Computer Science

National Tsing Hua University

專題演講

SEMINAR

 主 講 人: Professor Ker-I Ko

SPEAKER Department of Computer Science, Stony Brook University, New York, and

          Department of Computer Science, National Chiao-Tung University, Hsinchu.

題  目：Computational Complexity in Analysis

TOPIC

時  間：101年5月17日(四) PM 3:30-4:30

DATE

地    點：綜二館753室

PLACE                                                                    

             連絡人：韓永楷教授

敬請踴躍參加

Abstract:

  =========

The classical theory of computation does not deal adequately with computations that operate on real-valued data. Most computational problems in physical sciences and engineering are of this type, such as the complexity of network flow problems and of dynamical and hybrid systems.  In this talk, we introduce a theory of computational complexity over continuous data, which is based on the Turing machine model and is consistent with the discrete NP-completeness theory. We will present the general model of this theory and give a hierarchical classfication of numerical operations based on discrete complexity theory.  We will also extend this theory to the study of continuous computational geometry. The complexity analysis of problems like convex hull and shortest path in the continuous setting will be presented.