西安電子科技大學(xué)-算法導(dǎo)論-Let1-introduction

DesignandAnalysisofAlgorithms

Introduction(Ch1)SoftwareSchoolZhangLiyong1Contactus張立勇zhangliyong@

88204613鄧凡dfmyfavorites@126.com

137599955942TopicsBasicConceptsAsymptoticAnalysis3FactorsofProgrammingProgrammingLanguages？C程序設(shè)計(jì)語言BASICPASCALC#IDE?4Whatismoreimportant?SoftwareArchitecture5SoftwareArchitectureSoftwareArchitectureStyleC2Style6SoftwareArchitectureSoftwareArchitectureStylePipe-FilterStyleFiltersPipes#include<iostream>usingnamespacestd;

intmain(){

int

a,b;

while(cin>>a>>b)

cout<<a+b<<endl;}intwhile()>><<+;{}mainabcin

cout

endl……Function(main)Declaration;whilestructure(condition)expression*.o*.exe7SoftwareArchitectureSoftwareArchitectureStyleRepositoriesStyle8SoftwareArchitectureOtherstyles：eventbased，orimplicitinvocationprocesscontrolinterpreterlayeredsystemsdistributedprocessesmainprogram/subroutineorganizationsstatetransitionsystemsotherdssa9SoftwareArchitectureSoftwareArchitecture——J2EEJ2SEJ2SEJ2SEJMSJNDIRMI/IIOPJDBCJavaMailJAFApplicationClientContainerJMSJNDIRMI/IIOPJDBCJTAJCAWebContainerEJBContainerDatabaseEIS(CICS)EIS(SAP)AppletContainerJ2SEAppletApplicationClientServletJSPEnterpriseBeanHTTPSSLHTTPSSLRMI/IIOPClientTierMiddleTierEISTierJavaMailJAFJMSJNDIRMI/IIOPJDBCJTAJCA10SoftwareArchitectureSoftwareArchitecture——J2EE11SoftwareArchitectureSoftwareArchitecture——CORBACORBAFacilitiesDomainInterfaceObjectRequestBrokerApplicationInterfaceCORBAServices12SoftwareArchitectureSoftwareArchitecture——.NET13SoftwareArchitectureSoftwareArchitecture——WebServiceUDDIRegistryServiceProviderServiceBrokerServiceRequesterFind/UDDI/WSDLBind/InvokePublish/UDDI/WSDLWebServiceClientApplicationSOAP14Whatismoreimportant?SystemServices?HowcanweassembleasoftwaresystemmorethantodeveloponeCORBAFacilitiesDomainInterfaceObjectRequestBrokerApplicationInterfaceCORBAServices15SystemServicesTransactionFinishallornone16SystemServicesSecurityWhoru?Whatdouwant?17UsingComponents18What’smoreafterframework?DSandAlgorithm19Algorithms

Algorithm.()--Awell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.--Broadly:astep-stepprocedureforsolvingaproblemoraccomplishingsomeendespeciallybyacomputer.--issues:correctness,efficiency(amountofworkdoneandspaceused),storage(simplicity,clarity),optimality.etc.InputAlgorithmOutputAlgorithm?=Program20WhatkindofproblemsHumanGenomeProject100,000genes，sequencesofthe3billionchemicalbasepairsInternetFindinggoodroutesonwhichthedatawilltravelSearchengineElectroniccommercePublic-keycryptographyanddigitalsignaturesManufacturingAllocatescarceresourcesinthemostbeneficialway21AconcreteproblemProblem:youaregivennintegers(theremaybenegativeonesbutnotall)a1,a2,…,an,determineiandjwhichmaximizethesumfromaitoaj.Case:6integers:(-2，11，-4，13，-5，-2)Ans:i=2,j=4,maxsumis20.22ImportanceofalgorithmsProblem:sorting10,000,000integersCase1:ComputerAexecutesonebillioninstructionspersecond(1GHz),analgorithmtakingtimeroughlyequalto2n2tosortnintegers.Case2:ComputerBexecutesonehundredmillioninstructionspersecond(100MHz),analgorithmtakingtimeroughlyequalto50nlgntosortnintegers.Case1:Case2:23Importanceofalgorithms24AbouttheCourseDesignandAnalysisHowcanIproposeanalgorithmforaspecificproblem?Isthealgorithmgoodenough?DesignAnalysisD&CGreedyDP…MSQS…ASPHuffman…ALSMCM……HSBasicsCases25結(jié)束

2009年8月18日26AnalysisofalgorithmsThetheoreticalstudyofcomputer-programperformanceandresourceusage.what’smoreimportantthanperformance?--modularity--user-friendliness--correctness--programmertime--maintainability--simplicity--functionality--extensibility--robustness--reliability27Whystudyalgorithmandperformance?Algorithmshelpustounderstandscalability.Performanceoftendrawsthelinebetweenwhatisfeasibleandwhatisimpossible.Algorithmicmathematicsprovidesalanguagefortalkingaboutprogrambehavior.Thelessonsofprogramperformancegeneralizetoothercomputingresource.Speedisfun.28TheproblemofsortingInput:sequence<a1,a2,…,an>ofnnaturalnumbers

Output:permutation<a’1,a’2,…,a’n>suchthata’1≤a’2≤…≤a’nExample--Input:<5,2,4,6,1,3>--Output:<1,2,3,4,5,6>29InsertionSort1nijsortedkey30InsertionSort654321469758初始654321469758j=2654321469785j=3654321469875j=4654321469875j=5654321498765j=6-∞-∞-∞-∞-∞-∞31RunningtimeTherunningtimedependsontheinput:analreadysortedsequenceiseasiertosort.Parameterizetherunningtimebythesizeoftheinput,sinceshortsequencesareeasiertosortthanlongones.Generally,weseekupperboundsontherunningtime,becauseeverybodylikesaguarantee.32Kindsofanalysis

Worst-case:(usually)--T(n)=maximumtimeofalgorithmonanyinputofsizen.

Average-case:(sometimes)

--T(n)=expectedtimeofalgorithmoverallinputsofsizen.--Needassumptionofstatisticsdistributionofinputs.Best-case:(bogus)--Cheatwithaslowalgorithmthatworksfastonsomeinput.33Machine-independenttimeWhatisinsertionsort’sworst-casetime?--Itdependsonthespeedofourcomputer:>>relativespeed(onthesamemachine)>>absolutespeed(ondifferentmachine)

BIGIDEA:--Ignoremachine-dependentconstants.--LookatgrowthofT(n)asn∞“AsymptoticAnalysis”34Θ--notation

Math:Θ(g(n))={f(n):Thereexistpositiveconstantsc1,c2,andn0>0suchthat0≤c1g(n)≤f(n)≤c2g(n)