【最新】一章绪论Preface

Inaugural DissertationzurErlangung der Doktorw¨u rdeder Naturwissenschaftlich-Mathematischen Gesamtfakult¨a tderRuprecht-Karls-Universit¨a tHeidelbergvorgelegt vonDiplom-Mathematiker Bernd Borchertaus L¨u nne im Emsland1994F¨u r meine ElternPredicate Classes,Promise Classes,and theAcceptance Power of Regular Languages Gutachter:Prof.Dr.Klaus Ambos-Spies,Universit¨a t Heidelberg Prof.Dr.Klaus W.Wagner,Universit¨a t W¨u rzburg Tag der m¨u ndlichen Pr¨u fung:20.Dezember1994PrefaceTheoretical Computer Science This Ph.D.thesis was written in the time from January 1991until July 1994and is submitted to the Department of Mathematics of the University of Heidelberg.It contributes some results to Structural Complexity Theory which is a subfield of Theoretical Computer Science.First of all I have to thank my advisor Prof.Klaus Ambos-Spies for his con-tinuing guidance and support.He also gave several crucial hints for the results of this thesis.Also I have to thank Prof.Juris Hartmanis and his former students Richard Chang,Suresh Chari,Desh Ranjan,and Pankaj Rohatgi.The initial results leading to this thesis were observed while I was visiting Cornell University in spring 1992.This is the right place to express gratitude to Prof.Steven Homer and Prof.Ak-ihiro Kanamori from Boston University who six years ago led me to the interest-ing field of Structural Complexity Theory.Also I would like to thank Prof.Klaus Weihrauch,University of Hagen,for supervising my first diploma thesis,and Prof.Wolfgang Sch¨o nfeld,IBM Heidelberg,for his guidance while I was working in his group.For helpful discussions I would like to thank Andreas Eisenbl¨a tter,Ulrich Her-trampf,Birgit Jenner,Klaus-J¨o rn Lange,Pierre McKenzie,Wolfgang Merkle,An-dre Nies,Thomas Schwentick,Nikolai Vereshchagin,and Heribert Vollmer.I am grateful to Prof.Klaus W.Wagner,University of W¨u rzburg,who agreed to referee this thesis.The results of Part I of the thesis were presented at the 9th Annual IEEE Con-ference of Structure in Complexity Theory 1994,see [Bo94b],a journal version will be submitted.The results of Part II were presented at the 11th Annual Sym-posium of Theoretical Aspects of Computer Science (STACS)1994,see [Bo94a],a journal version will appear in .Heidelberg,July 1994iiiContents1Introduction11.1Outline of Part I11.2Ouline of Part II21.3Related Work2I Predicate Classes and Promise Classes52Preliminaries52.1Order-Theoretic Notions52.2Recursively Presentable Classes62.3Polynomial Time Many-One Reducibility72.4Polynomial Time Many-One Degrees72.5Principal Ideals82.6Ideals112.7Computation Trees153Predicate Classes173.1The Definition of Predicate Classes173.2The Characterization of Predicate Classes194Promise Classes224.1The Definition of Promise Classes224.2The Characterization of the Promise Classes244.3Consequences of the Characterization of the Promise Classes295Analogous Results for Other Nondeterministic Computation Models305.1Balanced Polynomial Time Turing Machines305.2Polynomial Time Bit-Reducibility315.3Polynomial Time Nondeterministic Transducers335.4Polynomial Time Function Classes345.5Relativized Predicate Classes35iiiII On the Acceptance Power of Regular Languages396Predicate Classes Accepted by Regular Languages396.1Predicate Classes Accepted by Languages396.2The Definition of Regular Languages406.3Predicate Classes Accepted by Regular Languages417A Lemma about Regular Languages437.1o-h-Reducibility437.2Generalized Definite Languages467.3The Main Lemma468A Result for Classes Accepted by Regular Languages488.1The Main Result488.2A Non-Density Result on the Assumption that PH does not Collapse508.3A Non-Density Result for the Relativized Case518.4An Analogous Result for the Log-Space Case53 References55 Subject Index63 Symbol Index64 Index of Classes65iv1Introduction1.1Outline of Part Ipolynomial time many-one reducibility polynomial time nondeterministic computation regular language accepted predicate classes principal ideal promise function Part I of this thesis observes a close connection between two basic concepts of Structural Complexity Theory,both introduced by Karp in [Ka72]:1.The concept of which since its defi-nition was studied intensively,see for example [La75,AS85a].2.The concept of ,in the slightly more general sence as it is used to define not only the class NP (like in the original paper)but also classes like P,PP,UP,BPP,and RP.Part II of this thesis relates the concepts of Part I to the notion of a .More detailed outlines of the two parts and references to related work are given below.Several complexity classes –like NP,P,and PP –are defined (say )by a predicate on computation trees produced by polynomial time nondeterministic Turing machine computations.Such classes will be called .For example NP is accepted by the predicate on computation trees which is 1if and only if the tree contains a leaf with label 1.As another example,P is accepted by the predicate on computation trees which is 1if and only if the tree contains an odd number of leaves with label 1.Call a class a if with re-spect to polynomial time many-one reducibility it has a complete set and is closed downward.It is well known that the example classes NP,P,and PP are principal ideals.This observation can be generalized:The set of predicate classes is equal to the set of principal ideals.After the preliminary definitions and observations in Chapter 2this theorem will be shown in Chapter 3.In Chapter 4complexity classes like UP,BPP,and RP will be considered.These classes have in common that their original definition can be seen the fol-lowing way:there is a 01-valued function –called –on1.2Ouline of Part II1.3Related Workpromise classes accepted ideal yield computation trees where it is presumed (=’promised’)for each machine accept-ing a language in the class that for each input the promise function is not for the corresponding computation tree.Such classes will be called .For example UP is defined (say )by the promise function on computation trees which has the value 0if the tree does not contain a leaf with label 1,which has the value 1if the tree contains exactly one leaf with label 1,and which has the value if the tree contains more than one leaf with label 1.Call a class an if with respect to polynomial time many-one reducibility it is closed downward and closed under join.It is easy to see that the example classes UP,BPP,and RP are countable ideals.Like before,this observation can be generalized:The set of promise classes is equal to the set of countable ideals.The two characterizations of predicate classes and promise classes described above –and their corresponding versions for the recursive case –are the two main results of Part I of this thesis.In Chapter 5analogous results for some other models of nondeterministic computation will be shown.In Part II predicates with a low complexity will be considered:the predicates which are determined by a regular language for the the yields of computation trees (the is the left-to-right concatenation of the leaf labels).For example,NP is accepted by the predicate determined by the regular language which consists of the words containing at least one letter 1.The main result of Part II will be that if the class determined by a (nontrivial)regular language is not equal to P then the class contains at least one of the classes NP,co-NP and MOD P for prime.This will be interpreted as a non-density result in two ways:(1)on the as-sumption that the Polynomial Time Hierarchy does not collapse,and (2)for the relativized case.Additionally,the analog of the main result for the log-space case is shown.Similar work like in Part I was done in Bovet,Crescenzi,and Silvestri in [BCS91,BCS92],by Vereshchagin in [Ve93],by Hertrampf,Lautemann,Schwentick,Voll-locally definable acceptance types mod-classes finite acceptance types mer,and Wagner in [HL*93],and by Jenner,McKenzie,and Th´e rien in [JMT94].Like in Part I of this thesis also in these papers the definability of complexity classes with the help of nondeterministic computation models is investigated.The classes determined by regular languages,see Part II,were first considered by Hertrampf,Lautemann,Schwentick,Vollmer,and Wagner in [HL*93].These classes are a special case (namely the associative case)of the classes determined by defined by Hertrampf in [Her92a,Her94b].On the other hand the and the classes determined by ,considered systematicly in [Her90,Bei91,BG92]and [GW87,Her94a],re-spectively,are classes which are by definition determined by regular languages.Part I2Preliminaries2.1Order-Theoretic NotionsPredicate Classes and Promise Classesrecursively presentable classes polynomial time many-one reducibility degrees,principal ideals ideals computation trees binary relation reflexive transitive symmetric antisymmetric preorder partial order equivalence relation isomorphic -complete -minimum -maximum -supremum -infimum supremum First some standard order-theoretic notions will be defined in Section 2.1.The well-known concept of will be defined in Section2.2.Then the and its notions of and are presented in the Sections 2.3–2.6.Section 2.7introduces .The following order-theoretic notions are standard,see for example [Gr78].A on a set is a subset of .Only the infix notation will be used,i.e.stands for ().A binary relation is if for all ,it is if from and it follows ,it is if from it follows ,and it is if from and it follows =.A is a reflexive and transitive binary relation on a nonempty set.A is a preorder which is antisymmetric,and an is a preorder which is symmetric.A binary relation on a set and a binary relation on a set are called if there exists an isomorphism,i.e.a bijective mapping from to such that ()().Let be a preorder on a set .An element is called for a subset if and holds for all .A ()is an elementsuch that ()for all .For two elements a ()of and is an element such that and (and )and if also for another element it holds that and (and )then ().If it is clear from the context that one is dealing with a preorder ,a –supremum will just be called ,this will be done the same way for other order-theoretic notions.ΣΣ()()2.2Recursively Presentable ClassesPredicate Classes and Promise Classesupper semi-lattice lattice distributive -chain -antichain -atom atomic dense language words class recursively presentable recursive language 6Part I Let be a partial order on a set .Note that for a partial order the supremum (infimum)of two elements,if it exists,is unique.The partial order is called an if the supremum exists for every pair of elements,it is called a if both supremum and infimum exist for every pair of elements.A binary relation on a set is called an (upper semi-)sublattice of an (upper semi-)lattice on a set if is a subset of ,is the restriction of to ,and is closed under -suprema (and -infima).Note that an (upper semi-)sublattice is an (upper semi-)lattice.An (upper semi-)lattice is called if for all elements the following holds:if ,where is the supremum of and ,then there are elements such that ,,and is the supremum of and .Let be a partial order on a set .Two elements are called -comparable if or .A subset is called a if any two elements of are comparable,is called an if any two elements are incomparable.If the minimum exists then an element =is called anif no element =exists such that .The partial order is called if for every element =there is an atom such that .A partial order is called if for any two comparable but different elements there is an element properly between them,formally:for all for which but notthere is a such that and but neither nor .A partial order which contains an atom is obviously not dense because there is no element properly between the minimum and the atom.In this thesis a will always be a set of words over the alphabet =01,for basic definitions like the one of see for example [HU79].A is a set of languages.Let be the (+1)st word of in the length-lexicographic order,see for example [AS89].For a language and an I N define to be the languagewhere is a usual bijective polynomial time computable pairingfunction,see for example [BDG88].Call,like in [BDG88,AS89],a complexityclass if =I N for some recursive ,forthe notion of a see for example [HU79].ΣΣΣΣΣPreliminaries 2.3Polynomial Time Many-One Reducibility2.4Polynomial Time Many-One Degreesjoin polynomial time many-one equivalent polynomial time many-one degree of a language trivial recursive 7Let FP denote the class of functions which can be computed by a Tur-ing machine running in deterministic polynomial time,see for example [HU79,BDG88]for a more detailed definition.Let denote the polynomial time many-one reducibility among languages,i.e.if there exists a function FP such that ()for all words .The original definition of this reducibility is from Karp in [Ka72].It is easy to see that the binary relation is a preorder on the set of all languages.Define the of two languagesto be the language 01.The join is a -supremum of and :and for all languages :.The following enumeration of FP will be useful.Let in some straightforward way the deterministic Turing machines which compute functions be encoded by words.Define for every the function FP to be the function computed by the following polynomial time deterministic Turing machine:on input the machine simulates the computation of the deterministic Turing machine encoded by and cancels the simulation –with output –if the simulated machine has not terminated after +steps.It is easy to see that FP =I N and that the function which maps to ()is recursive.For the notions of this section see for example [La75,AS85a].Two languagesare called ,in short ,ifand .Note that is an equivalence relation on the set of all languages.Let the ,in short deg (),be the set of languages polynomial time many-one equivalent to ,and let denote the partial order on the -degrees defined bydeg ()deg ():Note that this definition does not depend on the choice of and .The degree deg ()is the unique -supremum of deg ()and deg ().This shows that is an upper semi-lattice on the set of all polyno-mial time many-one degrees.The two degrees and are called the degrees.Call a degree deg ()if and therefore all languages in deg ()are recursive.ΣΣΣΣ2.5Principal IdealsPredicate Classes and Promise ClassesTheorem 2.1(Ladner 1975,Ambos-Spies 1985a)The following partial orders are distributive upper semi-lattices,the one in (b)is an upper semi-sublattice of the one in (a).(a)The partial order on the set of all nontrivial polynomial time many-one degrees.(b)The partial order on the set of the nontrivial recursive polynomial time many-one degrees.This upper semi-lattice is additionally dense.principal-ideal principal ideal lower cone of downward closure of principal ideal trivial8Part I Many results are known for the partial order .In this thesis only the following basic results about density and distributivity due to Ladner in [La75]and Ambos-Spies in [AS85a],respectively,will be considered.Call a set of languages a ,or simply ,if there exists a language such that =():=.There areseveral other names for the class (),sometimes it is called or .For the choice of the name see the next section.Note that the language is -complete for ().The following classes are examples of principal ideals.The class NP should be mentioned first as an example of a principal plete languages for NP,like the problem SAT,were –for polynomial time Turing reducibility –first presented by Cook in [Co71],their -completeness was shown in [Ka72,Le73].For a list of -complete prob-lems for NP see [GJ79].The fact that for example SAT is not only -complete for NP but also every language -reducible to SAT is in NP is easy to see.The two principal ideals=(),=()will be called principal ideals.The class P is a principal ideal ()where is any language in P.P contains the two trivial principal ideals and is contained in every nontrivial principal ideal,see Figure 1.=2ΣΣΠ∆Preliminaries 9PFigure 1:The two trivial principal ideals and PNot only P and NP but also all other classes and of the Polyno-mial Time Hierarchy are principal ideals,the existence of -complete lan-guages was shown in [St77,Wr77].Let be any language.Then the class P consisting of all languages com-putable in polynomial time with oracle (see for example [Co71,BDG88]and also Section 5.5)is a principal (many-one)ideal according to the results in [AS86a],see also Corollary 5.8.As a special case,the classes of the Polynomial Time Hierarchy are principal ideals.The classes NP(n)and co-NP(n)of the Boolean Hierarchy are principal ide-als,the existence of -complete languages was shown in [CG*88].Counting classes like PP,C P,MOD P,P =MOD P,US =1–NP are principal ideals,for the original definitions see [Gi77,Wa86b,BG92,PZ83,BGu82,GW87].The exponential time classes EXPTIME =DTIME(2poly )and NEXPTIME =NTIME(2poly )are principal ideals.More generally,the classes -EXPTIME=DTIME(2...2poly )and -NEXPTIME =NTIME(2...2poly ),where inboth cases the exponentiation tower has height ,can easily be shown to be principal ideals for every 1.For the exact definitions see for example [Jo90].()()()Predicate Classes and Promise Classes Proposition 2.1Proof.Corollary 2.1Proposition 2.2Proof.For all languages it holds:()()For all languages it holds:()()Let be a language.()is recursively presentable is recursiveis recursive.10Part I There is a strong connection between the inclusion order on the principal ideals and the partial order on the polynomial time many-one degrees.deg ()deg ()Note that the second equivalence holds by the definition of.In order to see the first equivalence assume that ()().Because()it holds by the assumption that (),this shows .If on the other side then for each it holds by the transitivity of that ,this shows ()()In other words,the inclusion order on the principal ideals is isomorphic to the -order on the polynomial time many-one degrees.It is clear by the proof that this isomorphism between the partial order on the degrees and the inclusion order on the principal ideals exists not only for but for every preorder.The following corollary follows immediately from Proposition 2.1.=deg ()=deg ()By the following proposition the property of being recursively presentable is determined for a principal ideal by any -complete language.deg ()Note that the second equivalence was already mentioned in the definition of the recursiveness of a -degree.In order to see the first equivalence assume that ()=I N forsome recursive language .Then =for some I N.But if is recursivethen also =is.For the other direction let a recursive language be given.Define the language :=(),the functions were defined in Section 2.3.It is easy to see that is recursive and that ()==I N :()2.6IdealsPreliminariesCorollary 2.2Proposition 2.3Proof.The following partial orders are distributive upper semi-lattices.The one in (b)is an upper semi-sublattice of the one in (a).(a)The inclusion order on the set of all nontrivial principal ideals.(b)The inclusion order on the set of all nontrivial recursively presentable principal ideals.This upper semi-lattice is additionally dense.-ideal ideal ideal (a)The principal ideals are exactly the ideals which have a-complete language.(b)The recursively presentable principal ideals are exactly the ideals which have a recursive -complete language.11:()=I N .This finishes the proof of the fact that the class ()is recursively presentable if and only if is recursive.By Propositions 2.1and 2.2the results for the polynomial time many-one de-grees stated in Theorem 2.1can be transfered to the principal ideals immediately.A ,or simply ,is a nonempty set of languages such that if lan-guages and are in then each language with is also in .In other words,an ideal is a nonempty set of languages which is closed under join und closed downward.The name follows the notation in Lattice Theory,see for example Gr¨a tzer [Gr78].The following proposition shows the relation between between ideals and prin-cipal ideals.(a)Let a principal ideal()be given.is -complete for ()because is in ()and by definition all languages in ()are -reducible to .It remains to show that ()is an ideal.Let ()and.Then by the supremum property of the join.By the transitivity of it follows that ().Therefore,()is an ideal.For the other direction let an ideal have a -complete language .It will be shown that =().It holds ()because every language in is -reducible to .And it holds ()because and I is closed downward.ΣΣΠΣI N I N 1trivial ideals Predicate Classes and Promise Classes12Part I Part (b)follows from part (a)and Proposition 2.2.The two trivial principal ideals and will be also be called .Like in the case of principal ideals it is easy to see that the ideal P contains the two trivial ideals and every nontrivial ideal contains P.Some examples of classes are given which are ideals but which are not princi-pal ideals or not known to be principal ideals.Classes like UP (defined in [Va76]),BPP,RP (both defined in [Gi77]),FewP (defined as FNP in [Al86]),and AM (defined in [Ba85]),are easily shown to be (recursively presentable)ideals.These classes are not known to be principal ideals,see [Si82,Kow84,AS86b,HH88,Hem88,AS89].In Proposition 2.5it will be shown that pairwise intersections of nontrivial (recursively presentable)ideals are nontrivial (recursively presentable)ide-als,like (for1)or ZPP =RP co-RP.Generally,it is not known if such an intersection is a principal ideal.For a discussion of this question for the class NP co-NP see [Si82,Kow84,HI85,Hem88,AS89].(Effective)infinite unions of increasing sequences of (recursively presentable)ideals,like the class of languages of the Polynomial Time Hierarchy PH=and the class of languages of the Boolean Hierarchy BH=NP(n),are (recursively presentable)ideals which are in general not known to be principal ideals.For the original definitions of PH and BH see [St77,Wr77,CG*88].Let the class ELEMENT ARY be the union -EXPTIME,for the defini-tion of the classes -EXPTIME for 1see the examples of principal ide-als in Section 2.5.The class ELEMENTARY is a (recursively presentable)ideal which is provably not a principal ideal because by the Time Hierarchy Theorem of [HS65]it can be shown for each 1that -EXPTIME is a proper subset of (+1)-EXPTIME.The class of all recursive languages is a countable ideal but neither a prin-cipal ideal nor a recursively presentable ideal.The class P/poly defined by Karp and Lipton in [KL80,KL82]can easily be shown to be an ideal.It is not countable,but for example P/poly NP is a countable ideal.PreliminariesProposition 2.4Proof.Proposition 2.5(a)Every recursively presentable ideal is a countable ideal.(b)Every principal ideal is a countable ideal.(c)There is a recursively presentable ideal which is not a principal ideal.(d)There is a principal ideal which is not recursively presentable.(e)There is an ideal which is not countable.The following partial orders are distributive lattices,the one in (b)is a sublattice of the one in (a),and the one in (c)is a sublattice of the ones in (a)and (b).(a)The inclusion order on the set of all nontrivial ideals.(b)The inclusion order on the set of all nontrivial countable ideals.(c)The inclusion order on the set of all nontrivial recursively presentable ideals.In (a),(b)and (c)the infimum of two nontrivial ideals and is given by their intersection,and the supremum is given by the smallest ideal containing both and .13The class of all languages is an ideal but not countable.The following classes are not ideals.The class E =DTIME(2lin )is recursively presentable,has a -complete language,and is closed under join but is not an ideal because it is not closed downward.A polynomial time many-one degree is an ideal if and only if it is one of the two trivial degrees because otherwise it is not closed downward.For two -incomparable recursive languages the class ()()is recursively presentable and closed downward but is not an ideal because it is not closed under join.The relation of the different types of ideals introduced so far is described by the following Proposition 2.4,see also Figure 2.(a)Every recursively presentable class is by definition countable.(b)A principal ideal ()is by Proposition 2.3an ideal,and it is countable because there are at most countably many -reductions.A witness for (c)is the class ELEMENTARY,see the examples above,and a witness for (d)is according to Propositions 2.2and 2.3any class ()for a non-recursive .A witness for (e)is the class P/poly,see the examples above.()()Proof.Predicate Classes and Promise Classes14Part I recursively presentable principal idealsrecursively presentable ideals principal idealscountable idealsidealsFigure 2:Types of Ideals(a)Let two nontrivial ideals and be given.It will be shown thatis a nontrivial ideal.Therefore,is the infimum of and .Because both and contain the class P also the class contains P and is not empty.Letfor two languages ,then both and containand .Therefore,they contain also by their property of being an ideal.This shows that is a nontrivial ideal.The supremum of and is the class =:.It is easy to see that this class is an ideal,that it contains both and ,and that it is contained in every ideal containing both and .For the distributivity let be as above and let be contained in .Now it is shown that the supremum of =and =equals .and and therefore also their supremum are contained in .For the other direction it obviously suffices to show that for every language in the principal ideal ()is the supremum of two principal ideals in and ,respectively.By definition of there exist sets such that ,in other words ()is contained in the supremum of ()and ().By the distributivity of the principal ideals there are languages ()()such that ()is the supremum of ()and ().(b)By the property of a sublattice to be a lattice it suffices to observe that for two given countable nontrivial ideals and the classes and from (a)are countable.The distributivity follows like in (a).(c)It suffices like in (b)to show that for two recursively presentable ideals=I N and =I N (for recursive languages and )Preliminaries ()()()()()()()()()2.7Computation TreesTheorem 2.2(Ambos-Spies 1986)Theorem 2.3(Shinoda &Slaman 1990)Proposition 2.6exact pair theorems For a recursively presentable ideal thereexist two recursive languages and such that ()().For a countable ideal there exist two languages and such that ()().(a)The nontrivial countable ideals are exactly the pairwise in-tersections of the nontrivial principal ideals.(b)The nontrivial recursively pre-sentable ideals are exactly the pairwise intersections of the nontrivial recursively presentable principal ideals.15the classes and from (a)are also recursively presentable.Define tobe the recursive language and for all with itholds that .It will be shown that this constructionguarantees that =I N .The inclusion from left to right is obvious.For the other direction consider a fixed :if is infinite,then it is also an (infinite)language of both and ,and if is finite then it is in P and thereforein .This shows =I N .To represent the class define tobe the language (),where was definedin Section 2.3.It is easy to check that is recursive,and by construction it holdsthat =I N .The distributivity follows like in (a).The following two results –called –of Ambos-Spies in[AS86b]and Shinoda and Slaman in [ShS90]relate the notions of ideals and prin-cipal ideals more closely.The latter was shown to hold for the polynomial time Turing reducibility but the proof is also valid for the many-one case.==For the nontrivial ideals the two Theorems 2.2and 2.3can by Proposition 2.5be expressed the following way.Consider nondeterministic Turing machines as presented for example in [BDG88].In this thesis it is additionally assumed for a Turing machine that for a state and a tupel of symbols read by the heads at most two transitions are specified by the transition function,and also it is assumed that the transition function is given as a linear list.This way it is guaranteed that if nondeterminism appears during a。

序言Preface:项目管理项目管理 (xii)概论:MICROSOFT PROJECT for Windows (xiii)如何使用这本手册 (xv)单元学习模块 (xvi)格式惯例 (xvi)文件扩展名 (xvi)解压缩练习文件 (xvi)复制练习文件 (xvi)开始 (xvii)学前测验 (xix)单元 1: 计划基础单元预览:计划基础.................................................... M1 - 3 单元目标............................................................. M1 - 5 练习 A:移动于计划中.................................................. M1 - 6 练习 B:探索菜单 .....................................................M1 - 12 练习 C:移动于试图中................................................. M1 - 16 练习 D:使用模板..................................................... M1 - 22 练习 E:设置标准日历................................................. M1 - 28 练习 F:改变缺省设置................................................. M1 - 32 练习 G:使用帮助......................................................M1 - 36 单元复习 ............................................................M1 - 43 学习向导 ............................................................M1 - 44单元 2: 管理任务单元预览:管理任务.................................................... M2 - 3 单元目标............................................................. M2 - 5 练习 A:输入任务...................................................... M2 - 6 练习 B:编辑任务 .....................................................M2 - 10 练习 C:组织任务..................................................... M2 - 14 练习 D:列出任务提纲................................................. M2 - 18 单元复习 ............................................................M2 - 22 学习向导 ............................................................M2 - 23单元 3: 时间管理单元预览:时间管理....................................................M3 - 3 单元目标.............................................................M3 - 5 练习 A:设置计划开始日期.............................................. M3 - 6 练习 B:设置期限..................................................... M3 - 10 练习 C:联接任务..................................................... M3 - 14v练习 D:创建相互关系................................................. M3 - 18 练习 E:使用落后时间................................................. M3 - 22 练习 F:设置约束 .....................................................M3 - 26 单元复习............................................................ M3 - 30 学习向导 ............................................................M3 - 31单元 4: 资源管理单元预览:资源管理....................................................M4 - 3 单元目标.............................................................M4 - 5 练习 A:创建资源库.................................................... M4 - 6 练习 B:创建资源日历 .................................................M4 - 10 练习 C:分配资源 .....................................................M4 - 14 练习 D:校准资源..................................................... M4 - 18 练习 E:分配工作优先权............................................... M4 - 22 单元复习 ............................................................M4 - 26 学习向导 ............................................................M4 - 27单元 5: 多个计划单元预览:多个计划....................................................M5 - 3 单元目标.............................................................M5 - 5 练习 A:分配口令...................................................... M5 - 6 练习 B:保存工作区 ...................................................M5 - 12 练习 C:共享资源 .....................................................M5 - 16 练习 D:资源排序..................................................... M5 - 20 练习 E:创建子计划 ...................................................M5 - 24 练习 F:纠正计划联接................................................. M5 - 30 单元复习............................................................ M5 - 33 学习向导 ............................................................M5 - 34单元 6: 追踪和报告单元预览:追踪进程.................................................... M6 - 3 单元目标............................................................. M6 - 5 练习 A:保存基线......................................................M6 - 6 练习 B:输入实际的数据............................................... M6 - 10 练习 C:输入实际成本................................................. M6 - 16 练习 D:确定费用..................................................... M6 - 20 练习 E:回顾获得的值数据............................................. M6 - 24 练习 F:创建报告 .....................................................M6 - 30 练习 G:打印报告 .....................................................M6 - 36 练习 H:使用组功能 ...................................................M6 - 42 单元复习 ............................................................M6 - 46 学习向导 ............................................................M6 - 47vi序言插图单元 7: 自定义计划单元预览:自定义计划.................................................. M7 - 3 单元目标............................................................. M7 - 5 练习 A:改变计划选项..................................................M7 - 6 练习 B:自定义甘特表................................................. M7 - 12 练习 C:自定义甘特图................................................. M7 - 18 练习 D:创建自定义菜单 ...............................................M7 - 24 练习 E:创建自定义工具栏............................................. M7 - 30 练习 F:创建自定义表格............................................... M7 - 34 练习 G:使用组织者 ...................................................M7 - 40 单元复习............................................................ M7 - 44 学习向导 ............................................................M7 - 45模块 8: 图形单元预览:图形.........................................................M8 - 3 单元目标............................................................. M8 - 5 练习 A:使用绘图工具栏................................................ M8 - 6 练习 B:创建图表 .....................................................M8 - 12 练习 C:编辑图表..................................................... M8 - 16 练习 D:锚定图表..................................................... M8 - 20 单元复习............................................................ M8 - 23 学习向导 ............................................................M8 - 24评估学后测验.............................................................. T - 1 投资收益...............................................................T - 3附录附录 A:快速参考向导....................................................A - 3 附录 B:词汇表..........................................................A - 5 附录 C:窗口元素.......................................................A - 11 附录 D:工具栏.........................................................A - 13 附录 E:菜单...........................................................A - 19 附录 F:使用鼠标.......................................................A - 21 附录 G:键盘...........................................................A - 23vii- 学员笔记 - viii序言插图插图单元 1单元预览图 1.1 MICROSOFT PROJECT环境.............................M1 - 3练习 A:图 1.2开始MICROSOFT PROJECT............................................... M1 - 6 图 1.3 缩放计划窗格...................................... M1 - 7图 1.4 使用视图栏........................................ M1 - 8图 1.5 甘特表和甘特图....................................M1 - 9 练习 B:图 1.6菜单-选项快捷键..................................................M1 - 12 图 1.7 MICROSOFT PROJECT菜单栏..........................M1 - 12图 1.8 选定一个菜单条目的结果........................... M1 - 13图 1.9 用键盘移动于菜单之间............................. M1 - 14 练习 C:图 1.10更多视图对话框................................................. M1 - 16 图 1.11 移动于视图间..................................... M1 - 17图 1.12 资源表........................................... M1 - 18图 1.13 追踪表、甘特图、任务表........................... M1 - 19 练习 D:图 1.14选择模板................................................. M1 - 22 图 1.15 模板转换为文件................................... M1 - 23图 1.16 计划模板文件.....................................M1 - 24图 1.17 模板另存为新名................................... M1 - 25 练习 E:图 1.18 改变工作时间对话框............................................... M1 - 28 图 1.19 新的计划文件..................................... M1 - 29图 1.20 改变工作时间..................................... M1 - 30 练习 F:图 1.21改变缺省设定................................................. M1 - 33 图 1.22 新的开始和结束时间............................... M1 - 34 练习 G:图 1.23办公室助手................................................. M1 - 36 图 1.24 在对话框里访问帮助................................M1 - 37图 1.25 查看帮助主题.....................................M1 - 38图 1.26 显示一步一步指令.................................M1 - 39图 1.27 查找主题......................................... M1 - 40图 1.28 注解对话框.......................................M1 - 41 单元 2单元预览图 2.1 给任务著做提纲.................................... M2 - 3 练习 A:图 2.2 第一个任务.................................................. M2 - 6 图 2.3 任务输入计划文件...................................M2 - 7图 2.4 给任务插入行......................................M2 - 8图 2.5 使用GOTO对话框.................................... M2 - 9 练习 B:图 2.6编辑任务条目................................................. M2 - 10 图 2.7 在甘特表里编辑任务名............................ M2 - 11图 2.8 给任务添加备注................................... M2 - 12 练习 C:图 2.9移动任务..................................................M2 - 14 图 2.10 任务粘贴到新的位置............................... M2 - 15 练习 D:图 2.11通过提纲创建的任务总结............................................ M2 - 19 图 2.12 缩进子任务....................................... M2 - 20ix单元 3单元预览图 3.1 定义约束.......................................... M3 - 3 练习 A:图 3.2 新的开始日期..................................................M3 - 6 图 3.3 计划设置为在新的日期开始.......................... M3 - 7图 3.4 任务要尽快开始.....................................M3 - 8 练习 B:图 3.5为单个任务定义期限..................................................M3 - 10 图 3.6 为任务期限设置....................................M3 - 11图 3.7 给多个任务指定期限................................M3 - 12 练习 C:图 3.8增加时间尺度................................................. M3 - 14 图 3.9 联接任务.........................................M3 - 15图 3.10 结束-开始联接.................................... M3 - 16 练习 D:图 3.11 创建结束-开始关系.............................................M3 - 18 图 3.12 定义任务关系.....................................M3 - 19图 3.13 开始-开始关系.................................... M3 - 20 练习 E:图 3.14使用落后时间..................................................M3 - 22 图 3.15 使用流逝时间作为落后时间.........................M3 - 23 练习 F:图 3.16挑选约束类型................................................. M3 - 26 图 3.17 给任务定义约束....................................M3 - 27图 3.18 挑选约束日期......................................M3 - 28 单元 4单元预览图 4.1 资源表............................................ M3 - 3 练习 A:图 4.2 资源名...................................................M3 - 6 图 4.3 资源库............................................ M3 - 7图 4.4 定义资源单位的最大值...............................M3 - 8 练习 B:图 4.5定义资源的工作时间................................................. M3 - 10 图 4.6 为非工作时间安排时间表........................... M3 - 11 练习 C:图 4.7 原先的开始日期..................................................M3 - 14 图 4.8 把多个资源单位应用到一个任务..................... M3 - 15图 4.9 任务期限是被资源驱动的........................... M3 - 16图 4.10 把资源指定给多个任务.............................M3 - 17 练习 D:图 4.11过度分配的资源................................................. M3 - 18 图 4.12 任务在校准后重新排定时间表........................M3 - 19图 4.13 校准过度分配的资源...............................M3 - 20 练习 E:图 4.14取消校准................................................. M3 - 22 图 4.15 根据优先权重新排定任务时间表......................M3 - 23图 4.16 把优先权指定给多个任务...........................M3 - 24 单元 5单元预览图 5.1 共享资源..........................................M5 - 3 练习 A:图 5.2 分配口令.......................................... M5 - 6 图 5.3 删除修订口令......................................M5 - 7图 5.4 确认口令..........................................M5 - 8图 5.5 删除保护口令......................................M5 - 9图 5.6 增加保留口令.....................................M5 - 10图 5.7 文件将只读打开................................... M5 - 11 x序言插图练习 B:图 5.8保存工作区................................................. M5 - 12 图 5.9 打开工作区文件................................... M5 - 13 练习 C:图 5.10访问共用资源选项 ..................................................M5 - 16 图 5.11 查看资源链接.....................................M5 - 17图 5.12 共用资源对话框...................................M5 - 18 练习 D:图 5.13更新这资源库................................................. M5 - 20 图 5.14 资源在两个计划文件里排序......................... M5 - 21图 5.15 排序资源.........................................M5 - 22图 5.16 启用资源重编码................................... M5 - 23 练习 E:图 5.17调整列宽................................................. M5 - 24 图 5.18 更新期限..........................................M5 - 25图 5.19 插入子计划....................................... M5 - 26图 5.20 任务期限在子计划更新............................. M5 - 27 练习 F:图 5.21正确的计划链接..................................................M5 - 31 图 5.22 定义链接的任务关系...............................M5 - 32 单元 6单元预览图 6.1 计划报告..........................................M6 - 3 练习 A:图 6.2保存基线...................................................M6 - 6 图 6.3 追踪基线与实际的数据..............................M6 - 7 练习 B:图 6.4 追踪工具栏................................................. M6 - 10 图 6.5 进程线应用到甘特图............................... M6 - 11图 6.6 追踪进程......................................... M6 - 12图 6.7 实际的完成日期...................................M6 - 13图 6.8 更新计划.........................................M6 - 14 练习 C:图 6.9更新实际成本..................................................M6 - 17 图 6.10 更新实际的工作................................... M6 - 18 练习 D:图 6.11查看各资源的费用 ..................................................M6 - 20 图 6.12 查看费用统计..................................... M6 - 21图 6.13 使用资源图表追踪费用..............................M6 - 22 练习 E:图 6.14访问赚得值表................................................. M6 - 24 图 6.15 把赚得值数据用EXCEL制图.......................... M6 - 25图 6.16 定义使用细节..................................... M6 - 26图 6.17 费用细节.........................................M6 - 27图 6.18 挑选制图的域.....................................M6 - 28 练习 F:图 6.19 报告对话框..................................................M6 - 30 图 6.20 自定义报告......................................M6 - 31图 6.21 计划总结报告....................................M6 - 32图 6.22 命名自定义报告...................................M6 - 33图 6.23 为报告选择细节....................................M6 - 34图 6.24 格式化报告正文...................................M6 - 35 练习 G:图 6.25挑选横向..................................................M6 - 36 图 6.26 打印报告.........................................M6 - 37图 6.27 规定新的报告标题................................. M6 - 38图 6.28 自定义页脚....................................... M6 - 39xi练习 H:图 6.29要求有关一个特定的任务的信息...................................... M6 - 42 图 6.30 使用 TeamStatus功能.............................. M6 - 43图 6.31 使用TeamAssign功能............................... M6 - 44 单元 7单元预览图 7.1 自定义工具栏......................................M7 - 3 练习 A:图 7.2恢复期限增量.................................................. M7 - 7 图 7.3 手动地调整实际成本.................................M7 - 8图 7.4 在新的一天开始一个星期............................ M7 - 9图 7.5 改变期限的显示...................................M7 - 10 练习 B:图 7.6改变列标题.................................................M 7 - 12 图 7.7 把自定义表格应用到视图........................... M7 - 13图 7.8 创建一个新的域列................................. M7 - 14图 7.9 定义自定义字段................................... M7 - 15图 7.10 自定义表将出现在视图菜单.........................M7 - 16 练习 C:图 7.11把颜色应用到关键任务 ..............................................M7 - 18 图 7.12 把新的一般格式应用到栏........................... M7 - 19图 7.13 定义一个个别的栏的格式............................M7 - 20图 7.14 应用一般的改变................................... M7 - 21 练习 D:图 7.15创建自定义菜单..................................................M7 - 24 图 7.16 使用自定义菜单...................................M7 - 25图 7.17 设置菜单.........................................M7 - 26图 7.18 设置自定义条目................................... M7 - 27 练习 E:图 7.19命名自定义工具栏 ..................................................M7 - 30 图 7.20 自定义菜单放置在新工具栏......................... M7 - 31图 7.21 把按钮定位在工具栏............................... M7 - 32 练习 F:图 7.22自定义表单对话框 ..................................................M7 - 34 图 7.23 自定义表单...................................... M7 - 35图 7.24 定义自定义表单对话框.............................M7 - 36图 7.25 选定对象.........................................M7 - 37图 7.26 缩放表单......................................... M7 - 38 练习 G:图 7.27访问自定义表单视图.................................................M7 - 40 图 7.28 从共用模板删除自定义元素..........................M7 - 41图 7.29 自定义元素复制到计划文件.........................M7 - 42 模块 8单元预览图 8.1 创建嵌入图表...................................... M8 - 3 练习 A:图 8.2绘图工具栏.................................................. M8 - 6 图 8.3 格式化的文本框对象................................ M8 - 7图 8.4 在甘特图上绘制箭头对象.............................M8 - 8图 8.5 定义新对象的属性.................................. M8 - 9 练习 B:图 8.6图表对象被插入甘特图............................................... M8 - 13 图 8.7 插入对象对话框...................................M8 - 14图 8.8 信息粘贴入数据表................................. M8 - 15 练习 C:图 8.9 三维视图对话框..................................................M8 - 16 图 8.10 更新的图表对象................................... M8 - 17xii序言插图图 8.11 给图表添加标题................................... M8 - 18图 8.12 格式化图例文字...................................M8 - 19 练习 D:图 8.13给任务附加对象................................................. M8 - 20 图 8.14 把图表对象锚定到任务............................. M8 - 21图 8.15 为对象规定新的尺寸............................... M8 - 22xiii序言xv练习文件HOUSE2.MPP HOUSE3.MPP HOUSE4.MPP HOUSE5.MPP HOUSE5A.MPPHOUSE6.MPP HOUSE7.MPP HOUSE7A.MPP HOUSE8.MPP HOUSE8A.MPP支持文件GLOBAL.MPT增补应用程序MICROSOFT EXCEL 5.0 或更高版本MICROSOFT GRAPH 97— 学员笔记 —xvi初级Microsoft Projectfor Windows序言计划管理Microsoft Project 提供了复杂工具，可供规划时间安排表和管理计划。