發(fā)布時間：2018-04-27 18:35

  本文選題：信息與算法的復(fù)雜性 + 多變量問題的易處理性��； 參考：《安徽大學(xué)》2017年碩士論文

【摘要】：在許多學(xué)科中,例如物理學(xué)、化學(xué)、計算機(jī)科學(xué)、量子力學(xué)、金融學(xué)、經(jīng)濟(jì)學(xué)等,我們經(jīng)常會遇到定義在d維多變量函數(shù)空間的數(shù)值逼近問題,其中d可能很大,成百上千,甚至更大,當(dāng)d很大的時候,通常我們在指定的誤差ε下,用函數(shù)的泛函(線性信息)或函數(shù)值(標(biāo)準(zhǔn)信息)作為信息構(gòu)造算法來逼近該問題.逼近該多變量數(shù)值問題算法的復(fù)雜性,記為C(n,ε,d),一直是近年來計算數(shù)學(xué)的主要研究方向之一.逼近該多變量問題算法所需的最少信息個數(shù)稱為信息的復(fù)雜性,記為n(ε,d).顯然信息的復(fù)雜性是算法復(fù)雜性的一個下界,尤其對于許多線性問題,信息的復(fù)雜性與算法的復(fù)雜性是成一定的比例,所以算法復(fù)雜性的研究重點集中于信息的復(fù)雜性研究上.多變量問題的易處理性主要研究n(ε,d)如何依賴于ε和d,傳統(tǒng)的多變量問題研究時,對于任給的d是固定的,那么就容易忽略了維數(shù)d的影響,而n(ε,d)有可能依賴于d的指數(shù)形式增長,所以對于多變量問題的復(fù)雜性還需要新的大量的研究.1994年,波蘭數(shù)學(xué)家Wozniakowski教授提出了多變量問題易處理性的許多新慨念與理論,例如,多變量問題的不易處理性(intractability)、強(qiáng)易處理性(strong tractabili-ty)、弱易處理性(weak tractability)、多項式易處理性(polynomial tractability)、弱擬多項式易處理性(weak and quasi-polynomial tractability)、對數(shù)多項式易處理(polylog tractability),許多學(xué)者研究并得出大量成果.本文主要在平均框架下對多變量問題的對數(shù)多項式易處理性與弱易處理性做進(jìn)一步研究.本文的工作主要包括以下幾章:第一章,首先簡要介紹信息與算法的復(fù)雜性與易處理性相關(guān)研究背景和發(fā)展歷史,給出本文需要的復(fù)雜性的一些基本概念和符號以及結(jié)果.第二章,我們主要在平均框架下討論多變量問題的易處理性,并給出了多變量問題是對數(shù)多項式易處理及(s,lnk)弱易處理的充要條件,隨后對于特殊的加權(quán)逼近問題,我們證明了加權(quán)逼近問題S是lnk弱易處理性,并且在線性信息與標(biāo)準(zhǔn)信息下是等價的.第三章,我們還是在平均框架下,針對張量積問題進(jìn)行討論,首先我們介紹了基本知識,并給出了張量積問題是(s,t)弱易處理的充要條件,然后證明了線性張量積問題既不是(1,ln1)弱易處理也不是對數(shù)多項式易處理的.第四章,對前面幾章進(jìn)行總結(jié),提出自己今后關(guān)于進(jìn)一步研究的工作,并給出了幾個自己暫時未解決的問題.
[Abstract]:In many disciplines, such as physics, chemistry, computer science, quantum mechanics, finance, economics and so on, we often encounter numerical approximation problems defined in d dimensional multivariable function space, where d can be very large, hundreds of thousands, Even larger, when d is very large, we usually use the functional of function (linear information) or the value of function (standard information) as the information construction algorithm to approach the problem under the specified error 蔚. Approximating the complexity of the multivariable numerical algorithm, denoted as Cnn, 蔚 DX, has been one of the main research directions of computational mathematics in recent years. The minimum number of information needed to approximate the multivariable problem algorithm is called the complexity of the information, which is denoted as n (蔚 / d). It is obvious that the complexity of information is a lower bound of algorithm complexity, especially for many linear problems, the complexity of information is proportional to the complexity of algorithm, so the research of complexity of algorithm focuses on the research of complexity of information. The easiness of multivariable problem is mainly studied how n (蔚 d) depends on 蔚 and d. When traditional multivariable problem is studied, it is easy to ignore the influence of dimension d when the given d is fixed. While n (蔚) may depend on the exponential growth of d, the complexity of multivariate problems needs a lot of new research. In 1994, Professor Wozniakowski, a Polish mathematician, put forward many new ideas and theories on the easiness of multivariable problems, such as, The intractability, strong tractable, weak tractability, polynomial tractability, weak and quasi-polynomial tractability, weak and quasi-polynomial tractability and logarithmic polynomials of multivariable problems are easy to deal with. Many scholars have studied and obtained a great deal of results. In this paper, the logarithmic polynomial easiness and weakly easiness of multivariable problems are studied in the average frame. The main work of this paper includes the following chapters: the first chapter briefly introduces the research background and development history of complexity and processability of information and algorithm, and gives some basic concepts, symbols and results of complexity needed in this paper. In the second chapter, we mainly discuss the controllability of multivariable problem under the average frame, and give the necessary and sufficient condition that the multivariable problem is logarithmic polynomial easy and weak easy to deal with, and then for the special weighted approximation problem, We prove that the weighted approximation problem S is lnk weakly easy to deal with and is equivalent to the standard information under linear information. In the third chapter, we discuss the tensor product problem under the average frame. Firstly, we introduce the basic knowledge and give the necessary and sufficient conditions for the tensor product problem to be weakly easy to deal with. Then it is proved that the linear tensor product problem is neither weakly easy to deal with nor logarithmic polynomial to deal with. In the fourth chapter, the author summarizes the previous chapters, puts forward his future work on further research, and gives some unsolved problems for the time being.
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O241.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前1條

1 羅競維;鐘文祥;;某城鎮(zhèn)污水處理廠進(jìn)水水質(zhì)特征分析和處理性評價[J];科技風(fēng);2014年04期

相關(guān)碩士學(xué)位論文 前2條

1 黃亞飛;多變量問題的對數(shù)多項式與弱易處理性研究[D];安徽大學(xué);2017年

2 張順;一些多變量函數(shù)空間的積分與逼近的易處理性[D];安徽大學(xué);2007年

，

本文編號：1811840