中科院陈玉福计算机算法设计与分析期末简答题答案
历年试题简答题答案,很有用的考试资料,开卷必备二者的区别就在于,确定性的每·步只有种选择,而非有多种选择,由些可见,非的计算能力比确定性强得多。时间复杂性即从开妈直至进入停机状态所运行的步数,同理空间复杂度归并排序算法和快速排序算法各自强调了那个方面?各自提高效率的策略是什么?归并由分解与合并两部分组成。提高的话一个是当元素比较少时,可以直接进行排序,比如插入排序。这比分解合并要快得多。二是尽量采用链表结构,因链表结构的移动要快于数组决排也是利用分治法排序。主要过程为划分。些改进的方法在确定第小元素时,就是将个元素分为一段这种方法复杂性可达到()二.(分)试用算法求解下面无向赋权图的最小生成树,指出最小生成树及该树中各边被选中的先后次序;写出算法的基本步骤。iTCHY181513,(81347166120解:根据算法,从开始,选择和加入集合找出集合中顶点相邻的最小权值点加入集合依次为基本步骤:从第一个结点开始,加入集合每次选择中顶点与外的顶点权值最小的顶点,加入集合直到集合包含所有顶点分)用—分枝限界算法求解背包问题:,物品重量和价值分别是画出由算法生成的状态空间树,并标明各节点的优先级的值;给出各节点被选作当前扩展节点的先后次序;给出最优解。解具体步骤就不写了四.(分)已知一组数满足,且被搜索的对象的概率分布是a=0.1.a1=0.01,a2=0.02,a3=0.04,a4=0.03,c=0.2h=015.b2=005b=075b=025b3=0075其中表示被搜索对象在区间内的概率,表示被搜索对象为的概率,使用动态规划算法求该搜索门的最优二叉搜索树。解:各了树的根:最优二叉树结构是根是的左孩子是的左孩子是的右孩子是的左孩子是的左孩子是的右孩子是的右孩子是的右孩子是的左孩子是的右孩子五.分假定已知“无向图的回路”问题是问题,证明“旅行商判定问题乜是问题。解:首先,旅行商问题是的,因为对其解的任一猜想,要检验它是否是最优的,需要同所有其它的环游戏比较,这样的环游会有指数个,因而不可能在多项式吋间内完成考虑图的哈密顿回路问题,已知无向图构造其对应的旅行商问题为()属于边,,否则显然,这一变换可以在多项式时间内完成,而且,有哈回路的充分必要条件是上述构建的旅行商问题有解,且解对应的路长度为,因为,若中不含哈回路,则路长至少为因为已知哈回路问题是问题,并且上述变换为多项式变换,所以旅行商问题也为问题
- 2020-12-11下载
- 积分:1
FAM和SSCA算法的matlab源程序-detection and identification of signal
FAM和SSCA算法的matlab源程序-detection and identification of signalFAM和SSCA算法的matlab源程序-detection and identification of signalDISCLAIMER NOTICEMTHIS DOCUMENT IS BESTQUALITY AVAILABLE. THECOPY FURNISHED TO DTICCONTAINED A SIGNIFICANTNUMBER OF PAGES WHICH DONOT REPRODUCE LEGIBLY.ilApproved for public release; distribution is unlimitedDETECTION AND IDENTIFICATION OF CYCLOSTATIONARY SIGNALSEvandro luiz da costaLieutenant Commander, brazilian NavyB.S., Instituto Militar de Engenharia, 1980Submitted in partial fulfillmentof the requirements for the degree ofMASTER OF SCIENCE IN ELECTRICAL ENGINEERINGANDMASTER OF SCIENCE IN ENGINEERING ACOUSTICSfrom theNAVAL POSTGRADUATE SCHOOLMarch 1996Author.Evandrodk da costaapproved byRQ求Ralph Hippenstiel, Thesis Co-AdvisorRoberto Cristi, Thesis Ca-AdvisoiHerschel. Loomis, Jr, hairmanDepartment of Electrical and Computer EngineeringArthony A. Atchley / ChairmanEngineering Acoustics Academic CommitteeABSTRACTPropeller noise can be modeled as an amplitude modulated(AM) signalCyclic Spectral Analysis has been used successfully to detect the presence ofanalog and digitally modulated signals in communication systems. It can also identithe type of modulation. Programs for Signal Processing based on compiledlanguages such as FORTRAN or C are not user friendly, and MATLAB basedprograms have become the de facto language and tools for signal processingengineers worldwideThis thesis describes the implementation in mAtlab of two fast methods ofcomputing the Spectral Correlation Density(SCD)Function estimate, the FFTAccumulation Method (FAM)and the Strip Spectral Correlation Algorithm( SSCA),toperform Cyclic Analysis. Both methods are based on the Fast Fourier transformFFT)algorithm. The results are presented and areas of possible enhancement forpropeller noise detection and identification are discussedTABLE OF CONTENTSINTRODUCTIONA MOTIVATION,P,中“····*s···:···:B BACKGROUNDC THESIS GOALSIL NOISE IN THE OCEAN··+A TYPES OF UNDERWATER NOISE25561. Ambient Noise番申2. Self noise3. Radiated noise8B RADIATED NOISE FROM SHIPS, SUBMARINES AND TORPEDOES.......8C PROPELLER NOISE10lI CYCLOSTATIONARY PROCESSING15A CYCLOSTATIONARIT15B THE CYCLIC AUTOCORRELATION FUNCTION (ACF)17C THE SPECTRAL CORRELATION DENSITY FUNCTION (SCD)18N. ESTIMATION OF THE SPECTRAL CORRELATION DENSITY FUNCTION23A FFT ACCUMULATION METHOD(FAM)25B STRIP SPECTRAL CORRELATION ALGORITHM(SSCA■D28V. EXPERIMENTAL RESULTSA. ANALOG-MODULATED SIGNALS311. Amplitude Modulated(AM)Signal===2-312. Pulse-Amplitude Modulated(PAM) Signal58B DIGITAL-MODULATED SIGNALS1. Amplitude Shift Keying(ASK) Signal中中非昏号即即号自唱即自曲音非带卡.最662. Binary-Phase Shift Keying(BPSK) Signal6了VI CONCLUSIONS81A SUMMARY81B SUGGESTIONS82APPENDIX A-CALCULATION OF THE SCD FUNCTION OF AN AMPLITUDE-MODULATED SIGNAL83APPENDIX B-FUNCTION AUTOFAM95APPENDIX C-FUNCTION AUTOSSCA99APPENDIXD-FUNCTION CROSSFAM103APPENDIX E-FUNCTION CROSSSSCA109APPENDIX F-PLOTTING ROUTINES113LIST OF REFERENCES115INITIAL DISTRIBUTION LIST看音117INTRODUCTIONA. MOTIVATIONPropeller related acoustic signatures typically exhibit modulationcharacteristics. These modulation characteristics originate from the cavitationprocess that takes place in the water due to the cyclic movement of the propellerThe cavitation process is basically the collapse of air and vapor bubblesdue to variations in the static pressure. These variations in static pressure are aconsequence of the passage of the propeller blades through the water. Thismovement, cyclic in nature, causes amplitude modulation in the static pressureand as a consequence an amplitude-modulated(AM) signal can be detected in areceiverCyclostationary processing techniques have been used to detect andlentify analog and digital communication signals very successfully. Thesetechniques have the advantage of using a more realistic model for the signalthan the stationary model used in most of the more conventional signalprocessing techniquesB BACKGROUNDThe basic elements of cyclic spectral analysis are the time-variant cyclicperiodogram and the time-variant cyclic correlogram. These two functions form aFourier transform pair. This fact is known as the cyclic Wiener relation or thecyclic Wiener-Khinchin relation [Ref. 1: p. 49.1
- 2020-12-05下载
- 积分:1