The NP-completeness column an ongoing guide

The NP-Completeness Column:An Ongoing Guide

D AVID S.J OHNSON

Bell Laboratories,Murray Hill,New Jersey07974

This is the fourth edition of a quarterly column the purpose of which is to provide con-

tinuing coverage of new developments in the theory of NP-completeness.The presenta-

tion is modeled on that used by by M.R.Garey and myself in our book‘‘Computers and

Intractability:A Guide to the Theory of NP-Completeness,’’W.H.Freeman&Co.,San

Francisco,1979(hereinafter referred to as‘‘[G&J]’’;previous columns will be referred to

by their dates).A background equivalent to that provided by[G&J]is assumed,and,

when appropriate,cross-references will be given to that book and the list of problems

(NP-complete and harder)presented there.Readers who have results they would like

mentioned(NP-hardness,PSPACE-hardness,polynomial-time-solvability,etc.),or open

problems they would like publicized,should send them to David S.Johnson,Room2C-

355,Bell Laboratories,Murray Hill,NJ07974,including details,or at least sketches,of

any new proofs(full papers are preferred).In the case of unpublished results,please state

explicitly that you would like the results to be mentioned in the https://www.wendangku.net/doc/0b5398930.html,ments

and corrections are also welcome.For more details on the nature of the column and the

form of desired submissions,see the December1981issue of this Journal.

1.I NTRODUCTION

According to the prospectus presented in this column’s first[Dec.1981]edi-tion,one of its functions is to provide‘‘occasional reports on new theoretical de-velopments concerning NP-completeness and related issues.’’This month seems like an appropriate time to initiate this feature,as exciting developments have occurred recently in two separate areas.I shall devote the first half of the column to covering them.

The column is organized as follows.Section2discusses an extension of the work on relativized complexity covered in Chapter7of[G&J],which suggests a new approach to proving P≠NP(but doesn’t,according to the latest word,sug-gest it very loudly).Section3surveys some surprising new approximation algo-

rithms for the‘‘bin packing’’problem(a problem discussed in detail in Chapter 6of[G&J])and uses these results to motivate this column’s‘‘open problem of the month.’’We return to our list-making in Section4,which surveys new re-sults related to problems of permutations and orderings.Section5concludes with some brief‘‘updates.’’

The promised discussion of routing problems will have to wait one more is-sue,by which time I hope to be able to capture the pictorial nature of these prob-lems by using Chris Van Wyk’s IDEAL program for typesetting figures[41].

2.P≠NP(ALMOST ALWAYS)

In Chapter7of[G&J]the concept of a Turing machine(TM)with an‘‘ora-cle’’is discussed.An oracle for a language A is a‘‘black box’’that,given a string x as input,will tell in one step whether or not x∈A.If we augment ordi-nary TM’s with oracles for language A,we can ask all the standard questions of complexity theory,but now they are‘‘relativized to A’’and the answers may well depend on A.In particular,in[6]it was shown that there are languages B and C such that P B=NP B and P C≠NP C.Since all of the known techniques for distinguishing classes of languages yield the same results whether the TM’s have oracles or not,this was taken as evidence that the standard techniques would be of little help in resolving the P versus NP question.

However,in a recent paper[7],Bennett and Gill suggest that there might be hope after all.They show that languages like language B above are exceedingly rare,in a rigorous,measure-theoretic sense.Note that there is a one-to-one cor-respondence between infinite sets of strings in{0,1}*and points in the unit in-terval[0,1):Lexicographically order the strings in{0,1}*as x1,x2,...,and let each p∈[0,1)correspond to the set that contains all x i such that the i+1st bit in the binary representation of p is1.Thus we can ask what is the measure of the set of languages A for which P A=NP A,or equivalently,given a‘‘random’’ora-cle A,what is the probability that P A=NP A?Bennett and Gill prove that this probability is0,in other words,P A≠NP A,almost always.

Bennett and Gill then argue that this result provides strong evidence that P≠NP,since‘‘random oracles by their very structurelessness appear more benign and less likely to distort the relations among complexity classes than(ones)de-signed expressly to help or frustrate some class of computations.’’In particular, they propose the following random oracle hypothesis:

Let S A be an acceptably relativized statement(a rather complicated defini-

tion of‘‘acceptably relativized’’is used,one that is designed to avoid certain

obvious pitfalls while still allowing all of our standard conjectures to be consid-

ered).Then the unrelativized statement S is true if and only if the relativized

statement S A is‘‘almost always’’true.

Given the results in[7],this hypothesis would imply not only P≠NP,but also

that LOGSPACE≠P,that NP≠co-NP≠PSPACE≠EXPTIME,and that P is identical to the random polynomial time class R of[1]and a number of its vari-ants.

Thus we have a new way to resolve P versus NP and our other open problems concerning complexity classes:prove the random oracle hypothesis.Initially, this seemed promising,as it opened up the P versus NP question to attack by a whole new range of techniques.Unfortunately,it now appears that proving the hypothesis may well be significantly more difficult than proving P≠NP:the random oracle hypothesis,at least as formalized by Bennett and Gill,is false. Kurtz[25]has provided two counterexamples,one of which we shall describe briefly.Let P3SAT be the set of languages that can be recognized in polynomial time with the aid of an oracle for3SAT.It is easy to see that NP?P3SAT.How-ever,if we relativize this statement to a random oracle A(the second class thus has two oracles),it becomes false with probability1,even though it qualifies as ‘‘acceptably relativized.’’Although there is some hope(not shared by Kurtz) that the hypothesis may yet be resurrected by an appropriate redefinition of‘‘ac-ceptable relativization,’’none has yet been proposed.For now,at least,it ap-pears that‘‘almost always’’is not nearly often enough.

3.B IN P ACKING AND THE E LLIPSOID A LGORITHM

Recall that in the bin packing problem we are given a set U={u1,u2,...,u n}of items,each with a rational size s(u i)∈[0,1],and are asked to partition U into dis-joint sets U1,U2,...,U k,called bins,such that the sum of the item sizes in each U i is no more than1,and such that k is as small as possible.This problem is,of course,NP-hard(transformation from3-PARTITION),and so efforts have con-centrated on‘‘approximation’’algorithms.Such an algorithm A,given an in-stance I,constructs a packing(partition)with a number A(I)of bins close to,but not necessarily equal to,the optimum number OPT(I).

Since in most applications of interest the number of bins is large,the criterion for comparison between algorithms has been,from the first,the asymptotic worst case ratio R A∞,defined as follows.

for some N,A(I)/OPT(I)≤r for all

R A∞=inf r≥1:

instances I satisfying OPT(I)≥N

A brief summary of the highlights of the past decade of bin packing goes as fol-lows.A first,easy,observation was that the straightforward,linear time algo-rithm NEXT FIT(NF)satisfied R NF∞=2[21].Garey,Graham,and Ullman[13] showed that the slightly more sophisticated O(n log n)time FIRST FIT(FF)algo-rithm yielded R FF∞=1.7,and proved that the next step in sophistication,FIRST FIT DECREASING,obeyed R FFD∞≤1.25.Johnson(yours truly)then observed

that FFD was also O(n log n)and spent100pages of his thesis[20](see also[22]) proving the exact result R FFD∞=11/9=1.222...Progress then stalled from1973 until1978,when A.Yao finally succeeded in breaking the11/9barrier,devising an O(n10log n)algorithm A with R A∞≤(11/9)?(1/10,000,000)[44].Thus inspired, other bin packers returned to the fray,with Friesen and Langston[11]develop-ing an O(n log n)hybrid algorithm having R A∞≤6/5=1.20and Garey and Johnson [14]devising an O(n log n)modified FFD having R A∞=71/60=1.18333...

This process of incremental improvement in R A∞has now come to a surpris-ingly abrupt conclusion.Two researchers,Lueker and Fernandez de la Vega, have independently discovered that for everyεthere is a linear time algorithm A[ε]with R A[ε]∞≤1+ε.Algorithms with this sort of behavior had long been known for problems such as the knapsack problem,where performance is mea-sured by absolute(rather than asymptotic)worst case ratios,with the term ap-proximation scheme being used to describe the overall collection of algorithms {A[ε]:ε>0}.Lueker and Fernandez de la Vega discovered that,counter to ex-pectations,techniques from the knapsack approximation scheme could be adapt-ed to bin packing,so long as one was prepared to solve a very large,but(for eachε)fixed-size,linear program.The details of this‘‘asymptotic approxima-tion scheme’’are discussed in a joint paper[10].

A few of these details may limit the applicability of the algorithms:the pre-cise performance guarantee provided is

A[ε](I)≤(1+ε).OPT(I)+(1/ε)2,

and the running time,although linear in n,is exponential in(1/ε)2.Forε=1/10, the additive constant in the guarantee would be about100bins,and the algo-rithm would take on the order of1020steps.One can,by a standard trick,move the1020term out of the running time and into the additive constant,but that would not be much of an improvement.

What one would really like is an asymptotic approximation scheme that si-multaneously provides a guarantee of the form(1+ε).OPT(I)+p1(1/ε)and a running time of p2(n,1/ε),where p1and p2are both polynomials.One’s first thought is to try to speed up the algorithms of Lueker and Fernandez de la Vega by using the now-famous‘‘ellipsoid algorithm’’for linear programming.There is a bottleneck,however.The linear program Pεthat has to be solved in the al-gorithm A[ε]has a number of variables that is exponential in1/ε.Even the el-lipsoid algorithm will have trouble with that.Karp and Karmarkar[23],how-ever,do https://www.wendangku.net/doc/0b5398930.html,ing an imposing arsenal of techniques from mathematical pro-gramming and complexity theory,they have very recently succeeded in con-structing the desired‘‘fully polynomial’’asymptotic approximation scheme. Their first step is to note that the dual of Pεhas only a polynomial number of variables(although an exponential number of constraints).They therefore can make use of the fact that,in the ellipsoid algorithm,one doesn’t need to know

all the constraints,but only to be able to find a violated constraint when there is one[17].

This approach is applicable here because,using an old idea due to Gilmore and Gomory[15],a violated constraint can be generated by solving a knapsack problem.The knapsack problem is,of course,NP-complete.However,it can be solved approximately using the above-mentioned knapsack approximation scheme,which turns out to be good enough if one only wants an approximate solution to the dual.An approximate solution to the dual is good enough,if one only wants a lower bound on the optimal solution of Pε.This is good enough, because with it we can obtain,in polynomial time,an approximate lower bound on OPT(I).This lower-bounding procedure can then be used as a subroutine in an iterative process for building up a near-optimal packing,much as one can use a procedure for computing the exact value of OPT(I)as a subroutine in building up an optimal packing.

There are,of course,many more details than this brief summary can convey, and the algorithm is quite a tour-de-force.However,although these approxima-tion scheme results are generating much excitement among the packers of theo-retical bins,one should stress that,as of yet,none of the schemes has much pre-tension toward practicality.Nevertheless,as long as we are following the path of better and better guarantees for less and less practical algorithms,there is one more step to be taken.So far we have found that,for everyε>0,there is a polynomial time algorithm with R A∞≤1+ε.What aboutε=0,i.e.,is there a polynomial time algorithm A with R A∞=1?

The answer is yes.Indeed,such algorithms are easily derived from either of the above schemes,merely by making an appropriate choice ofεas a function of the instance at hand(actually,as a function ofΣi=1n s(u i),a sum that is al-ways within a factor of2of OPT(I)).The difference between the two schemes shows up in the additive terms of the guarantees provided.These unfortunately are no longer constants,although they do remain o(OPT(I)).For Lueker and Fer-nandez de la Vega we have

OPT(I)loglog[OPT(I)]

A(I)≤OPT(I)+O

log[OPT(I)]

whereas for Karp and Karmarkar we have

A(I)≤OPT(I)+O(OPT(I)1?δ)

for someδ>0.With both algorithms there is a trade-off between running time and the asymptotic growth rate of the additive term,but no way of balancing the two to yield an algorithm that would be useful for instances of less than astro-nomical size.A much more attractive additive term would be something like log[OPT(I)],or better yet,a constant,independent of OPT(I).However,Karp and

Karmarkar seem to have pushed the state of the art about as far as it will go. Thus here is perhaps where one should begin to investigate the possibility of ‘‘impossibility’’results,e.g.,the possibility of proving that unless P=NP no polynomial time approximation algorithm A can guarantee that A(I)?OPT(I)is less than some given bound.

To date there has been little success in this direction.Still open is the weakest possible such result,which can hence serve as our‘‘open problem of the month.’’Prove or disprove:Assuming that P≠NP,there can be no polynomial time approximation algorithm A that guarantees A(I)≤OPT(I)+1.

4.P ROBLEMS OF O RDERINGS AND P ERMUTATIONS

The most famous problems involving permutations are probably the TRAV-ELING SALESMAN problem[ND22]and its special case,the HAMILTO-NIAN CIRCUIT problem[GT37].A number of new developments concerning the latter problem have come to my attention since I discussed it in the[Mar. 1982]column(where it revealed its multifaceted nature by masquerading as an embedding problem).

Akiyama,Nishizeki,and Saito[4]have continued the process of finding ever-more restricted classes of graphs for which HAMILTONIAN CIRCUIT is NP-complete,showing that NP-completeness continues to hold both for2-connected cubic bipartite planar graphs and for3-connected cubic bipartite(not necessarily planar)graphs.Wigderson[43]has shown that NP-completeness also holds for maximal planar graphs,a result that implies NP-completeness for the following interesting variant:‘‘Given a planar graph G,can we add new edges(but not new vertices)so as to render the resulting graph Hamiltonian, while still keeping the graph planar?’’There is a more positive development for the directed HAMILTONIAN CIRCUIT problem:Ramanath[38]has shown that this problem(as well as the directed HAMILTONIAN PATH problem)can be solved in polynomial time when restricted to‘‘reducible flowgraphs’’(as de-fined,for instance,in[2],pp.938-941).

There have also been a number of interesting developments related to opti-mization version of TRAVELING SALESMAN,which we shall refer to as the ‘‘TSP’’in what follows.Consider the version of the TSP in which the cities correspond to points in the plane.In applying the standard approximation algo-rithms(see[G&J],Chapter6),one can obtain tours in which the path intersects itself,and hence can clearly be shortened by an appropriate interchange.Van Leeuwen and Schoone have recently shown that all such crossings can be re-moved in polynomial time[40],a result that is not entirely obvious since remov-ing one crossing may create new ones.A second way of improving the tours found by the heuristics is by optimizing the choice of‘‘shortcuts’’taken when an Euler tour is reduced to a Hamiltonian one.Here we are not so fortunate. Papadimitriou and Vazirani[33]have shown that,even for the Euler tours gen-

erated by Christofides’algorithm,this optimization problem is NP-hard.

On a more theoretical plane,Papadimitriou[32]has shown that the problem ‘‘Given an instance of the TSP,does it have more than one optimal solution?’’is complete for the class P3SAT mentioned in Section2(i.e.,the class?2p in the polynomial hierarchy).A future column will report on work of Papadimitriou and Yannakakis[34]extending earlier results on the complexity of the‘‘TSP polytope.’’

Another famous problem that can be viewed as a permutation problem is GRAPH ISOMORPHISM:is there a permutation of the vertices of G that makes it identical to H?This problem remains open,but some interesting variants have been shown to be NP-complete.

[1]GRAPH ISOMORPHISM WITH RESTRICTIONS

INSTANCE:Two graphs G=(V,E)and H=(U,F),and a set R?V×U. QUESTION:Is there an isomorphism f of G to H that,when viewed as a set of ordered pairs,contains no pair from R?

Reference.Lubiw[29].Transformation from3SAT.

Comment.Remains NP-complete when H=G(AUTOMORPHISM WITH RESTRICTIONS).In the latter case,remains NP-complete even if R= {(v,v):v∈V}(FIXED-POINT-FREE AUTOMORPHISM),and this problem re-mains NP-complete even if we ask for an order2fixed-point-free automor-phism.Note,however,that the order2fixed-point-free automorphism problem is solvable in polynomial time for groups.AUTOMORPHISM WITH RE-STRICTIONS remains NP-complete so long as|R|≥εn1/k for fixedεand k. However,if|R|=1,this problem becomes Turing-equivalent to the still open GRAPH ISOMORPHISM problem.It is not known whether the ordinary GRAPH AUTOMORPHISM problem(|R|=0)is as hard as GRAPH ISOMOR-PHISM,although the problem of counting automorphisms is equivalent to that of counting isomorphisms(and both are equivalent to GRAPH ISOMORPHISM itself)[30].

[2]PARTITIONED GRAPH ISOMORPHISM

INSTANCE:Two graphs G=(V,E)and H=(U,F),and a positive integer K. QUESTION:Are there partitions E=E1∪...∪E K and F=F1∪...∪F K of E and F into disjoint(and possibly empty)sets such that G i=(V,E i)is isomorphic to H i=(U,F i),1≤i≤K?

Reference. F.Yao[45].Transformation from EXACT COVER BY3-SETS

(X3C).

Comment.Remains NP-complete for K=2;equivalent to GRAPH ISOMOR-PHISM for K=1.The variant in which we are just given G,and are asked whether there is a partition E=E1∪E2such that the two graphs G1=(V,E1)and

G2=(V,E2)are isomorphic,is NP-complete even for trees[16],although for trees it can be solved in polynomial time if E1and E2are required to be con-nected[18].

To conclude our discussion of vertex permutation problems,let us consider two related problems that were mentioned in the[Mar.1982]column:BAND-WIDTH[GT40]and MINIMUM CUT LINEAR ARRANGEMENT[GT44]. New special-case algorithms have been found for both of these problems.Ass-man,Peck,Syslo,and Zak[5]have shown that BANDWIDTH can be solved in time O(n log n)for‘‘caterpillars with hairs of length1and2.’’Chung,Makedon, Sudborough,and Turner[8]have shown that MINIMUM CUT LINEAR AR-RANGEMENT can be solved in time O(n(log n)d?1)for trees with maximum ver-tex degree d.This yields polynomial time algorithms for any fixed value of d,in contrast to the case for BANDWIDTH,which is known to be NP-complete even for trees of maximum degree3[12].Some new complexity results for variants on BANDWIDTH are collected together in the following entry.

[3]CYCLIC BANDWIDTH

INSTANCE:Graph G=(V,E),positive integer K≤|V|.

QUESTION:Is there a cyclic ordering of V with bandwidth K or less,i.e.,is there a one-to-one function f:V→{1,2,...,|V|}such that,for all{u,v}∈E,either |f(u)?f(v)|≤K or(|V|?|f(u)?f(v)|)≤K?

Reference.Leung,Vornberger,and Witthoff[27].Transformation from3-PARTITION.

Comment.Unlike ordinary BANDWIDTH,which can be solved in polyno-mial time for any fixed K[39],this problem remains NP-complete for K=2(it is trivial for K=1).It can,however,be solved in polynomial time for any fixed K if G is required to be connected.The‘‘separation’’variant,in which both dis-tances above must exceed K,is NP-complete for K=1and connected G,as is the corresponding variant of ordinary BANDWIDTH.For DIRECTED BAND-WIDTH[GT41],the‘‘separation’’variant is NP-complete for arbitrary K,but solvable for in-forests or out-forests,for interval orders,and for K=1[27].

We turn now to a problem involving the ordering of edges,rather than ver-tices.

[4]SEARCH NUMBER

INSTANCE:Graph G=(V,E),positive integer K≤|V|.

QUESTION:Does G have a search number of K or less,i.e.,can K searchers ‘‘clear’’the graph according to the following rules:

(a)A move consists of placing a searcher on a vertex,removing a searcher from

a vertex,or moving a searcher along an edge.A vertex is guarded if it con-

tains a searcher.

(b)An edge is clear if it has been‘‘cleared’’and there is no unguarded path

from it to an unclear edge.Initially,all edges are unclear.

(c)If{u,v}is an edge and u is guarded,then{u,v}can be cleared by placing a

second searcher at u and then moving it along the edge to v.If{u,v}is the only unclear edge with u as endpoint,the second searcher is not needed and we may clear the edge by moving the u’s guard from u to v along it. Reference.Megiddo,Hakimi,Garey,Johnson,Papadimitriou[31].Trans-formation from MINIMUM CUT INTO EQUAL-SIZED SUBSETS(see com-ments to[ND17]).

Comment.This problem was first studied by Parsons[35,36].The fact that the problem is really about edge permutations(and hence is in NP),is due to a recent result of LaPaugh[26],who shows that if the search number of G is K, then G can be cleared by K searchers in such a way that no edge is ever‘‘re-contaminated.’’In other words,no guard is ever removed from a vertex if its absence will open up an unguarded path from an uncleared edge to a cleared one.Thus any search strategy determines,and is determined by,a permutation of the edges,and the existence of the desired strategy can be verified in nonde-terministic polynomial time by guessing this permutation.The problem can be solved in deterministic polynomial time if K≤3or if G is a tree[31].There is an interesting connection between SEARCH NUMBER and MINIMUM CUT LINEAR ARRANGEMENT:for any graph G the search number is no greater than cutwidth(where‘‘cutwidth’’is the quantity minimized in MINIMUM CUT LINEAR ARRANGEMENT).The quantities are in fact equal for trees of maxi-mum degree3[8],although not in general.

Our final three problems concern the generation of permutations.

[5]MINIMUM LENGTH GENERATOR SEQUENCE

INSTANCE:A set{g i:1≤i≤k}of generators of a permutation group G,a tar-get permutation P∈G,and a positive integer K.

QUESTION:Is there a sequence g i1,g i2,...,g i j,j≤K,such that P=g i1g i2...g i j?

Reference.Even and Goldreich[9].Transformation from X3C. Comment.Also NP-hard is the problem,given a set of generators and an in-teger K,of determining whether all permutations in G can be generated by gen-

erator sequences of length K or less.

[6]SHUFFLED STRING

INSTANCE:Finite alphabetΣ,strings w and w1,w2,...,w n inΣ*. QUESTION:Is the string w in the shuffle of w1,w2,...,w n,i.e.,is it of the form w1[1]w2[1]...w n[1]w1[2]w2[2]...w n[2]...w1[k]w2[k]...w n[k],where w i[1]w i[2]...w i[k] is a partition of w i into a sequence of(possibly empty)substrings,1≤i≤n? Reference.Warmuth and Haussler[42].Transformation from3-PARTITION.

Comment.Remains NP-complete even if|Σ|=2.If|Σ|=3,remains NP-complete even if w1=w2=...=w n,in which case we are asking whether w is in the iterated shuffle of w1.If we extend the definition of iterated shuffle to languages in the standard way,there exist fixed context free languages L such that membership in the iterated shuffle of L is NP-complete.For any fixed regu-lar language L,however,the problem is solvable in polynomial time.Reference [42]also contains a number of other results along this line,asking when NP-complete languages can be generated by combining the shuffle and iterated shuffle operators with the standard ones for generating languages,i.e.,∪,.,*, etc.For more on theoretical aspects of the shuffle,see[19].

[7]DEFECTIVE SORTING NETWORK

INSTANCE:Sequence x1,x2,...,x n of input variables and a program P consisting of a sequence of statements of the form‘‘if x i≥x j,then interchange their val-ues,’’where ix k+1? Reference.Rabin[37].Transformation from3-DIMENSIONAL MATCH-ING.

Comment.Can be solved in polynomial time if all statements are of the form ‘‘if x i≥x i+1,then interchange their values,’’i.e.,if all comparators link adjacent lines in the network(see[24],Exercise5.3.4-36c).Sorting networks are in

vogue again,what with the recent claim by Ajtai,Komlo′s,and Szemere′di[3]of a network with O(n log n)comparators and O(log n)delay time,both bounds offer-ing an improvement by a factor of log n over bounds that had stood for some18 years.

5.U PDATES

Since this column is in danger of overflowing its page allotment,I will limit myself to some minor items that can be disposed of quickly.In the last column [Jun.1982],the‘‘to appear’’citation on reference[31]should be moved to ref-erence[32],and the first occurrence of the word‘‘NP-complete’’in the com-ments to Problem13should be replaced by‘‘NP-hard.’’Also,the claim that 11-colorability of Steiner triple systems is NP-complete turns out to have been based on a misreading of that column’s reference[11].The appropriate conclu-sion is that14-colorability is NP-complete.Our final comment concerns the source problem in many of the transformations reported in the last two columns. The proof of the NP-completeness of PLANAR3-SAT has at last made its for-mal appearance[28],after four years as an‘‘unpublished manuscript.’’

R EFERENCES

1.L.A DLEMAN AND K.M ANDERS,Reducibility,randomness,and intractability,in‘‘Proceedings

9th Ann.ACM Symp.on Theory of Computing,’’pp.151-153,Association for Computing Ma-chinery,New York,1977.

2. A.V.A HO AND J.D.U LLMAN,‘‘The Theory of Parsing,Translation,and Compiling,Vol.II:

Compiling,’’Prentice-Hall,Englewood Cliffs,N.J.,1972.

3.M.A JTAI,J.K OMLO′S,AND E.S ZEMERE′DI,in preparation,(1982).

4.T.A KIYAMA,T.N ISHIZEKI,AND N.S AITO,NP-completeness of the Hamiltonian cycle problem

for bipartite graphs,Journal of Information Processing3(1980),73-76.

5.S.F.A SSMAN,G.W.P ECK,M.M.S YSLO,AND J.Z AK,The bandwidth of caterpillars with hairs

of length1and2,SIAM J.Algebraic and Discrete Methods2(1981),387-393.

6.T.B AKER,J.G ILL,AND R.S OLOVAY,Relativizations of the P=?NP question,SIAM https://www.wendangku.net/doc/0b5398930.html,-

put.4(1975),431-442.

7. C.H.B ENNETT AND J.G ILL,Relative to a random oracle A,P A≠NP A≠co?NP A with proba-

bility1,SIAM https://www.wendangku.net/doc/0b5398930.html,put.10(1981),96-113.

8.M-J.C HUNG,F M AKEDON,I.H.S UDBOROUGH,AND J.T URNER,Polynomial algorithms for the

min cut problem on degree restricted trees,manuscript(1982).

9.S.E VEN AND O.G OLDREICH,The minimum-length generator sequence problem is NP-hard,J.

Algorithms2(1981),311-313.

10.W.F ERNANDEZ DE LA V EGA AND G.S.L UEKER,Bin packing can be solved within1+εin linear

time,Combinatorica1(1981),349-355.

11. D.K.F RIESEN AND M.A.L ANGSTON,Analysis of a compound bin packing algorithm,

manuscript(1981).

12.M.R.G AREY,R.L.G RAHAM,D.S.J OHNSON,AND D.E.K NUTH,Complexity results for band-

width minimization,SIAM J.Appl.Math.34(1978),835-859.

13.M.R.G AREY,R.L.G RAHAM,AND J.D.U LLMAN,Worst-case analysis of memory allocation al-

gorithms,in‘‘Proceedings4th Ann.ACM Symp.on Theory of Computing,’’pp.143-150,As-sociation for Computing Machinery,New York,1972.

14.M.R.G AREY AND D.S.J OHNSON,A71/60algorithm for one-dimensional bin packing,

manuscript(1980).

15.P.C.G ILMORE AND R.E.G OMORY,A linear programming approach to the cutting-stock prob-

lem,Operations Res.9(1961),849-859.

16.R.L.G RAHAM AND R.W.R OBINSON,private communication(1982).

17.M.G RO..TSCHEL,L.L OVA′SZ,AND A.S CHRIJVER,The ellipsoid method and its consequences in

combinatorial optimization,Combinatorica1(1981),169-198.

18. F.H ARARY AND R.W.R OBINSON,Isomorphic factorizations VIII:Bisectable trees,manuscript

(1981).

19.M.J ANTZEN,‘‘Eigenschaften von Petrinetzsprachen,’’Report No.IFI-HH-B-64,Fachbereich In-

formatik,Universit a..t Hamburg,Hamburg,1979.

20. D.S.J OHNSON,‘‘Near-optimal bin packing algorithms,’’Report No.MAC TR-109,Project

MAC,Massachusetts Institute of Technology,Cambridge,Mass.,1973.

21. D.S.J OHNSON,Fast algorithms for bin packing,https://www.wendangku.net/doc/0b5398930.html,put.System Sci.8(1974),272-314.

22. D.S.J OHNSON,A.D EMERS,J.D.U LLMAN,M.R.G AREY,AND R.L.G RAHAM,Worst-case per-

formance bounds for simple one-dimensional packing algorithms,SIAM https://www.wendangku.net/doc/0b5398930.html,put.3(1974), 299-325.

23.R.M.K ARP AND N.K ARMARKAR,An efficient approximation scheme for the one-dimensional

bin packing problem,in‘‘Proceedings23rd Ann.Symp.on Foundations of Computer Science,’’IEEE Computer Society,Long Beach,Calif.,1982(to appear).

24. D.E.K NUTH,‘‘The Art of Computer Programming,Vol.3:Sorting and Searching,’’Addison-

Wesley Publishing Company,Inc.,Reading,Mass.,1973.

25.S.L.K URTZ,On the random oracle hypothesis,in‘‘Proceedings14th Ann.ACM Symp.on The-

ory of Computing,’’pp.224-233,Association for Computing Machinery,New York,1982.

26. A.S.L A P AUGH,Recontamination does not help,manuscript(1982).

27.J.Y-T.L EUNG,O.V ORNBERGER,AND J.D.W ITTHOFF,On some variants of the bandwidth mini-

mization problem,manuscript(1982).

28. D.L ICHTENSTEIN,Planar formulae and their uses,SIAM https://www.wendangku.net/doc/0b5398930.html,put.11(1982),329-343.

29. A.L UBIW,Some NP-complete problems similar to graph isomorphism,SIAM https://www.wendangku.net/doc/0b5398930.html,put.10

(1981),11-21.

30.R.M ATHON,A note on the graph isomorphism counting problem,Inform.Process.Lett.8

(1979),131-132.

31.N.M EGIDDO,S.L.H AKIMI,M.R.G AREY,D.S.J OHNSON,AND C.H.P APADIMITRIOU,The com-

plexity of searching a graph(preliminary version),in‘‘Proceedings22nd Ann.Symp.on Foun-dations of Computer Science,’’pp.376-385,IEEE Computer Society,Los Angeles,1981. 32. C.H.P APADIMITRIOU,On the complexity of unique solutions,in‘‘Proceedings23rd Ann.Symp.

on Foundations of Computer Science,’’IEEE Computer Society,Long Beach,Calif.,1982(to appear).

33. C.H.P APADIMITRIOU AND U.V.V AZIRANI,On two geometric problems related to the travelling

salesman problem,manuscript(1981).

34. C.H.P APADIMITRIOU AND M.Y ANNAKAKIS,The complexity of facets(and some facets of com-

plexity),in‘‘Proceedings14th Ann.ACM Symp.on Theory of Computing,’’pp.255-260,As-sociation for Computing Machinery,New York,1982.

35.T.D.P ARSONS,Pursuit-evasion in a graph,in‘‘Theory and Application of Graphs,’’(Y.Alavi

and D.R.Lick,eds.)pp.426-441,Springer-Verlag,Berlin,1976.

36.T.D.P ARSONS,The search number of a connected graph,in‘‘Proceedings9th Southeastern

Conference on Combinatorics,Graph Theory,and Computing,’’pp.549-554,Utilitas Mathe-matica Publishing,Winnipeg,Ont.,1978.

37.M.O.R ABIN,private communication(1981).

38.M.V.S.R AMANATH,The Hamiltonian path and cycle problems are P-time solvable for re-

ducible flow graphs,manuscript(1982).

39.J.B.S AXE,Dynamic-programming algorithms for recognizing small-bandwidth graphs in poly-

nomial time,SIAM J.Algebraic and Discrete Methods1(1980),363-369.

40.J.VAN L EEUWEN AND A.A.S CHOONE,‘‘Untangling a traveling salesman tour in the plane,’’Re-

port No.RUU-CS-80-11,Department of Computer Science,University of Utrecht,the Nether-lands,1980.

41. C.J.VAN W YCK,A graphics typesetting language,SIGPLAN Notices16(1981),99-107.

42.M.K.W ARMUTH AND D.H AUSSLER,‘‘On the complexity of iterated shuffle,’’Report No.CU-

CS-201-81,Department of Computer Science,University of Colorado,Boulder,Colo.,1981. 43. A.W IGDERSON,‘‘The complexity of the Hamiltonian circuit problem for maximal planar

graphs,’’Report No.298,Electrical Engineering and Computer Science Department,Princeton University,Princeton,N.J.,1982.

44. A.C.Y AO,New algorithms for bin packing,https://www.wendangku.net/doc/0b5398930.html,put.Mach.27(1980),207-227.

45. F.F.Y AO,Graph2-isomorphism is NP-complete,Inform.Process.Lett.9(1979),68-72.

a,an和the用法区别

a，an和the用法区别 a，an和the 用法你们都了解了吗?今天给大家带来a，an 和the 用法，希望能够给帮助到大家，下面就和大家分享，来欣赏一下吧。 英语无捷径|| a，an和the 用法区别，记住就不要再犯错了! 1. 不定冠词 a 还是an 判断用a还是用an的依据是其后的单词的发音，而不是字母!以元音音素开头的单词前用an来修饰，以辅音音素开头的单词前用a来修饰。 常用的搭配规律： 1) 多数以元音字母(a、e、i、o、u)开头的单词，首音节都是发元音：I atean an apple yesterday. It’s sweet.我昨天吃了一个很甜的苹果。An American usually speaks English.美国人通常讲英语。Driving carefully helps avoid an accident.谨慎驾驶有助于避免事故。Learn how to survive anearthquake.学习如何在地震中生存。He went to aninterview yesterday.他昨天去面试了。She is cutting anonion.她在切洋葱。

2) 元音字母U开头的单词，首音节可能发元音或者辅音[ju:] 【j】a university [junivsiti] studenta unique [junik] styleA university is where you do your degree.大学是你获得学位的地方。Have you ever seena UFO/an unidentified flying object?你见过不明飞行物吗? 3) 记住三个h开头却不发音的名词：hour，honst，honourHalf an hour has passed.半小时过去了。Its an honour to be invited to your dinner.很荣幸被邀请参加你的晚宴。 4)European 欧洲人，欧洲的，元音字母e不发音，首音节是[ju:]He is a European, and he has lived in Hangzhou for 10 years. 他是欧洲人，在杭州住了10年。 5)如果名词前有形容词做定语修饰，则我们看形容词是辅音还是元音开头。There stands an oak tree in front of the house.房子前面有一棵橡树。An important lessonIve learned from it is never to give up.我从中学到的重要一课是永不放弃。He drives an old car.他开一辆旧车。In those years he was just an unknown pianist.在时的他只是一个默默无闻的钢琴家。An honest man never lies.诚实的人从不说谎。 2. 定冠词the 定冠词the : 表示特指某事物或人

介词from的语法特点与用法习惯

介词?f rom的语法特点与用法习惯 1.不要根据汉语意思在及物动词后误加介词?from。如： 他上个星期离开中国去日本了。 误：?H e left from China for Japan last week. 正：?H e left Chine for Japan last week. 另外，也不要根据汉语意思错用介词?from。如： 太阳从东方升起，从西方落下。 误：?T he sun rises from the east and sets from the west. 正：?T he sun rises in the east and sets in the west. 2.f rom虽然本身是介词，但它有时也可接介词短语作宾语。如： Choose a book from among these. 从这些书中选一本吧。 A man stepped out from behind the wall. 一个人从墙后走出来。 比较： I took it from the bed. 我从床那儿（或床上）拿的。 I took it from under the bed. 我从床下拿的。 注意，下面一句用了?from where（引导非限制性定语从句），而未用?f rom which，其中的where=i n the tree，即?from where=f rom in the tree。如： He hid himself in a tree, from where he could see the enemy in the distance. 他躲在一棵树上，从那儿他可以看到远处的敌人。 3.有时其后可接?w hen, where引导的宾语从句，此时可视为其前省略了?t he time, the place。如： He didn’t speak to me from when we moved in. 从我们迁入之时起，他没和我说过话。

Seated的用法小结

Seated的用法小结 seated是一个比较特别的过去分词，说它特殊一是因为它的词性尚有不确定性——它有时是过去分词，有时又具有形容词的性质，像是一个形容词；二是因为这样一个很少引人注意的过去分词，在近几年的高考英语考题中经常“露脸”，一下子变成了一个热点词汇。下面我们先来看几道高考题： 1. Please remain __________ until the plane has come to a complete stop. (山东卷) A. to seat B. to be seated C. seating D. seated 2. Please remain __________; the winner of the prize will be announced soon. (辽宁卷) A. seating B. seated C. to seat D. to be seated 3. Can those _________ at the back of the classroom hear me? (福建卷) A. seat B. sit C. seated D. sat 对于seated的用法，首先要从动词seat说起。 同学们可能只知道seat的名词用法，即只知道它表示“座位”。 其实，seat还可用作动词，且是一个典型的及物动词，其意为“给某人座位”“让人坐”或“能容纳……”句式：sb be seated 或seat sb / oneself 。 如： Seat the boy next to his brother. 让那个孩子坐在他哥哥旁边。 We can seat 300 in the auditorium. 我们这个礼堂可容纳300人。

aanthe的用法区别修订版

a a n t h e的用法区别 集团标准化小组：[VVOPPT-JOPP28-JPPTL98-LOPPNN]

三人行教育a,a n,t h e的用法区别（一）a, an的用法 1.a：用于辅音音素（不是辅音字母）开头的词前，表示单数的数量“一”。 a book a desk 2.an：用于元音音素（不是元音字母）开头的词前，表示单数的数量“一”。 an apple a big apple an old man 3.元音字母：以元音字母Aa, Ee, Ii, Oo开头的单词基本都是以元音音素开头 Uu较特殊 4.辅音字母：26个字母中，除了5个元音字母，其他是辅音字母 5.特殊情况：an umbrella（u发元音） a useful english book （u发辅音） an hour（h是辅音字母，但它不发音） 练习一：用a, an, the填空 1._____book 2._____apple 3._____orange 4._____uncle 5._____eraser 6._____ math book 7._____new book 8._____old book 9._____teacher 10.______English 11.____ hour 12._____good teacher 13.____idea 14.____good idea 15.____island 16.____ astronaut （二）the的用法 1.一般用于特指：The girl is my sister. 那个女孩是我的妹妹。

2.第二次出现：There is a book on the desk. The book is mine. 书桌上有一本书，那本书是我的。 3.世界上独一无二：the moon月亮 the earth地球the Great Wall长城the sun太阳 4.固定的词组：on the desk在书桌上 5.形容词最高级前：Jenny is the oldest girl in the class. 在 班里珍妮是年纪最大的女孩。 练习二：选择 ( )1.That’s _____ island. I like to go there. A.a B.an C.the ( )2.I have ___ new book. Jenny has ___ old book. A.a/ an B.an/ a C.an/ an ( )3.This is ___ orange. That’s ____big orange. A.a/ an B.an/ a C.an/ an ( )4.Yesterday I studied English for ____ hour. A.an B.the C.a ( )5.This is a bag. ____ bag is Tom’s. A.A B.An C.The ( )6.___ man is Lisa’s father. A.A B.The C.An ( )7.____ Great Wall is in China. A.A B.The C.An ( )8.My English book is in ___ desk. A.the B.an C./ ( )9.She has ___ idea. It’s a good idea. A.a B.an C.the 练习三：a, an, the填空

aan和the的用法

a a n和t h e的用法球类运动前面不用冠词 在操场上是固定搭配ontheplayground （一）不定冠词：a∕an的用法： ⑴表示一个 例：Shehasacleverson.她有个聪明的儿子。 ⑵表示每个 例：wehave3Englishclassesaweek.我们每周上3次英语课。 ⑶表示某个 例：Thebookis∕waswrittenbyastudent.这本书是一个学生写的。 ⑷表示某类之一 例：Iamateacher,heisadoctor.我是一名老师，他是一名医生。 ⑸第一次提到的人或物用不定冠词表示，再次提到时用定冠词。 例：Ihaveabike,thebikeisgreen.我有一辆自行车，这辆自行车是绿色的。 ⑹用于可数名词单数形式前，表示类别。 例：Ateachermustlovehisstudent.老师应该爱学生。 ⑺用于表示价格，速度，比率，时间等意义的名词前 例：3timesaday.一天三次 10yuanameter.10元一米

⑻用于抽象名词前，表示一种… 例：anewculture一种新文化 ⑼用于句型：“a∕an+Mr.∕Mrs.∕Miss.+姓氏”中 例：aMr.Wang一位姓王的先生（不认识） Mr.Wang王先生（认识） ⑽用于某些短语中 例：alotof许多，大量 haveagoodtime玩的开心，过的愉快 （二）定冠词the的用法： ⑴表示特定的人或事物 例：Thebookonthedeskismine.桌子上的书是我的。 ⑵表示听话人，说话人彼此都很熟悉的人或事物 例：WhereisTom汤姆在哪儿？ Heisintheroom.他在屋里。 ⑶第一次提到的人或物用不定冠词表示，再次提到时用定冠词。 例：Ihaveabike,thebikeisgreen.我有一辆自行车，这辆自行车是绿色的。 ⑷表示世界上独一无二的东西（专有名词除外） 例：Thesun太阳

动名词的语法特征及用法

动名词的语法特征及用法 动名词由动词加－ing词尾构成，既有名词的特征，又有动词的特征。了解动名词的语法特征可帮助学习者深入理解动名词的意义，从而正确使用动名词。 一、动名词的名词特征 动名词的名词特征表现在它可在句子中当名词来用，作主语、宾语、表语、定语。例如： Beating a child will do more harm than good．打孩子弊大于利。（作主语） Do you mind answering my question？你不介意回答我的问题吧？（作宾语） To keep money that you have found is stealing．把拾到的钱留起来是偷盗行为。（作表语） No one is allowed to speak aloud in the reading room．阅览室里不许大声说话。（作定语） 在动名词担任这些句子成分时，学习者需注意的是： 1、有些动词后只能用动名词作宾语，构成固定搭配，需特别记忆。常见的这类动词有：admit（承认），advise（建议），allow（允许）， appreciate（感激），avoid（避免），can't help（禁不住），consider（考虑），deny（否认），dislike（不喜欢），enjoy（喜欢），escape（逃脱），excuse（原谅），feel like（想要），finish（结束），give up（放弃），imagine（想象），involve（包含），keep（保持），mind（介意），miss（错过），permit（允许），practise（练习），quit（停止），recollect （记得），recommend（推荐），suggest（建议），stop（停止），resent（对……感到愤恨、怨恨），risk（冒……危险），cannot stand（受不了）等。例如： We do not permit smoking in the office．我们不允许在办公室吸烟。 In fighting the fire，he risked being burnt to death．在救火中，他冒着被烧死的危险。 She denied having stolen anything．她否认偷过任何东西。 I suggest doing it in a different way．我建议换一个方法做这件事。 2、动名词常用于一些固定句型中，常见的有：It is no use ／no good．．．；It is a waste oftime．．．；It is fun ／nice ／good．．．；There isno．．．（不可以／不可能……）等。例如： It is no use asking him．He doesn't know any more than you do． 问他也没用，他并不比你知道得更多。 It's no fun being lost in rain．在雨中迷路可不是好玩的。 It's a waste of time your reasoning with him．你和他讲道理是在浪费时间。

EXCEL的函数大全(完整版)

实用EXCE的函数 1.ADDRESS 用途：以文字形式返回对工作簿中某一单元格的引用。 语法：ADDRESS(row_num，column_num，abs_num，a1，sheet_text) 参数：Row_num是单元格引用中使用的行号;Column_num是单元格引用中使用的列 标;Abs_num指明返回的引用类型(1或省略为绝对引用，2绝对行号、相对列标，3相对行号、绝对列标，4是相对引用);A1是一个逻辑值，它用来指明是以A1或R1C1返回引用样式。如果A1为TRUE或省略，函数ADDRESS返回A1样式的引用;如果A1为FALSE，函数ADDRESS 返回R1C1样式的引用。Sheet_text为一文本，指明作为外部引用的工作表的名称，如果省略sheet_text，则不使用任何工作表的名称。 实例：公式“=ADDRESS(1，4，4，1)”返回D1。 2.AREAS 用途：返回引用中包含的区域个数。 语法：AREAS(reference)。 参数：Reference是对某一单元格或单元格区域的引用，也可以引用多个区域。 注意:如果需要将几个引用指定为一个参数，则必须用括号括起来，以免Excel将逗号作为参数间的分隔符。 实例：公式“=AREAS(a2:b4)”返回1，=AREAS((A1:A3，A4:A6，B4:B7，A16:A18))返回4。 3.CHOOSE 用途：可以根据给定的索引值，从多达29个待选参数中选出相应的值或操作。 语法：CHOOSE(index_num，value1，value2，...)。 参数：Index_num是用来指明待选参数序号的值，它必须是1到29之间的数字、或者是包含数字1到29的公式或单元格引用;value1，value2，...为1到29个数值参数，可以是数字、单元格，已定义的名称、公式、函数或文本。 实例：公式“=CHOOSE(2，"电脑"，"爱好者")返回“爱好者”。公式“=SUM(A1:CHOOSE(3，A10，A20，A30))”与公式“=SUM(A1:A30)”等价(因为CHOOSE(3，A10，A20，A30)返回A30)。 4.COLUMN

冠词a,an,the的用法

想说“这个/那个”的时候用the, 想说“（任意）一个”的时候用a。 专指： 专有名词KFC专指肯德基 地名国家名什么的独一无二的事物 类指:凡是同一类：都是苹果有大有小，the big one ，the small one 泛指：很不具体的，无特别指定对象，是和“特指”相对的；例如a girl就是一女孩，普通吧。此时也可是泛指一类人。a beautiful girl is like a evil. 特指：有特别指定对象，和“泛指”相对。the girl可能是上文提到过或者对话人都心知肚明的女孩，是有一个具体对象的. 冠词是用在名词前面，帮助说明名词所指的人或事物，是泛指还是特指的词。冠词是一种虚词。冠词分不定冠词（The Indefinite Article）和定冠词（The Definite Article）a, an是不定冠词，the 是定冠词。 an, a是不定冠词，仅用在单数可数名词前面，表示“一”的意义，但不强调数目观念。a用在以辅音（指辅音音素）开头的词前，an用在以元音（指元素音素）开头的词前 不定冠词的用法： 1. 表示人或事物的某一类 A steel worker makes steel. A plane is a machine that can fly. 2. 表示某一类人或事物中的任何一个。 This is an apple. His father is a teacher. 3. 泛指某人或某物，但不具体说明何人何物。 A comrade is waiting for you downstairs. I met an old man on my way to school. 4. 表示“一个”的意思

试题专题练习不定冠词(含解析)

不定冠词 1、（2016?天津）Tianjin is beautiful city in north of China．（）A．a；a B．a；the C．the；不填D．不填；the 【考点】不定冠词（a，an）；定冠词（the）． 【分析】天津是中国北方的一个美丽的城市． 【解答】答案：B 不定冠词a，an 表示泛指；定冠词the 表示特指或者再次提到；根据Tianjin is beautiful city，可知是首次提到，且为泛指一个美丽的城市． beautiful 第一个音/b/是辅音，应该用a；根据in north of China．在中国的北部，是特指，应该加定冠词the，故选：B． 2、（2016?河北）I have _______ pet cat．It is so cute．（） A．a B．an C．the D．不填 【考点】不定冠词（a，an）． 【分析】我有一只宠物猫．它很可爱． 【解答】答案：A a，an 表示泛指；the 表示特指或者再次提到；零冠词用于一些特殊的结构中．根据It is so cute．它很可爱．推测可知上文是应该是：我有一只宠物猫．是泛指．an用于第一个音节是元音的音素前，a用于第一个音节是辅音的音素前；pet 第一个音节/p/是辅音，应该用a，故选：A 3、（2016?重庆）Ciqikou is______famous place in Chongqing．（） A．a B．an C．the D．/ 【考点】不定冠词（a，an）． 【分析】磁器口是重庆的一个著名的地方． 【解答】答案：A．根据句意，这里表示一个有名的地方，要用不定冠词a/an，表示数量"一"，元音音素前用an，辅音音素前用a，famous/?fe?m?s/中字母f发/f/，辅音音素，即a famous place一个有名的地方．定冠词the，表示特指，故选：A． 4、（2016?济宁）_____ apple a day keeps the doctor away．（） A．A B．An C．The D．/ 【考点】不定冠词（a，an）． 【分析】一日一苹果，医生远离我． 【解答】答案为B．不定冠词（a，an）表示泛指，定冠词（the）表示特指．不定冠词a、an是"一个"的意思．a与an 的区别是a用于辅音音素前，an则用于元音音素前．句子中apple是泛指苹果，而apple的音标为['?p（?）l]，apple是以元音音素开头，故答案为B．5、（2016?重庆）Mary wants to be ________ good doctor when she grows up．（）A．a B．an C．the D．/ 【考点】不定冠词（a，an）． 【分析】当玛丽长大之后，她想成为一名好医生． 【解答】答案为A．不定冠词（a，an）表示泛指，定冠词（the）表示特指．句子的good doctor （好医生）是属于泛指任何一位好医生，故要用不定冠词．不定冠词a、an是"一个"的意思．a 与an 的区别是a用于辅音音素前，an则用于元音音素前．good的音标为[g?d]，good以辅音音素开头，故要用a，故答案为A 6、（2016?青岛）David is ______ eight-year-old boy with short black hair．（）A．/ B．a C．an D．the 【考点】不定冠词（a，an）． 【分析】David是一个黑色短发的八岁男孩．

Excel常用函数功能列表

Excel常用函数功能、用法及实例剖析 我们在使用Excel制作表格整理数据的时候，常常要用到它的函数功能来自动统计处理表格中的数据。本专题 整理了Excel中使用频率最高的函数的功能、使用方法，以及这些函数在实际应用中的实例剖析，并配有详细的介 绍和图示，同时提供.xls文件供大家下载参考。 Excel常用函数实例剖析 实例功能原文件下载 .xls文件下载 ·奖金计算表只要将员工的出勤情况记录在表中，该员工的奖金将自动 计算出来，兼有考勤和计算奖金两种功能。自动统计表做 好以后还可以保存成模板，以便以后使用。 ·制作万年历这个万年历可以显示当月的月历，还可以随意查阅任何日 .xls文件下载 期所属的月历，非常方便。如果你愿意，还可以让它在特 殊的日子里显示不同的提醒文字。 .xls文件下载 ·自动评分计算表参加比赛的选手为20人，评委9人，去掉1个最高分和 1个最低分后，求出平均分，然后根据平均分的高低排定 选手的名次。 .xls文件下载 ·自动统计学生成绩自动统计最高分、最低分、总分、平均分、名次等数据信 息，还可以根据自定条件以不同的颜色显示分数。自动统 计表做好以后还可以保存成模板，以便以后使用。 ·各分数段学生数统计统计各学科相应分数段或各等级的学生人数。.xls文件下载 .xls文件下载 ·自动生成员工简历表自动提取“员工基本情况登记表”中的信息，生成并打印员 工简历表。 >>> 更多内容<<< ⊙Excel常用函数功能及用法介绍 .xls 文件下载 函数名功能用途示例 ABS求出参数的绝对值。数据计算 条件判断 AND“与”运算，返回逻辑值，仅当有参数的结果均为逻辑“真（TRUE）” 时返回逻辑“真（TRUE）”，反之返回逻辑“假（FALSE）”。

aan和the用法精讲和练习

a, an, the的用法 冠词是虚词，本身不能单独使用，也没有词义，它用在名词的前面，帮助指明名词的含义。英语中的冠词有三种，一种是定冠词（the Definite Article），另一种是不定冠词（the Indefinite Article），还有一种是零冠词（Zero Article）。 an, a是不定冠词，仅用在单数可数名词前面，表示“一”的意义，但不强调数目观念。a用在以辅音（指辅音音素）开头的词前， an用在以元音（指元素音素）开头的词前。the是定冠词，修饰特指名词翻译成“这个”。如果泛指某物,用a,/an,具体指某物的话，用the. 注意：（1）当我们使用an时，条件有三：①这个名词的读音必须是以元音音素开头--即它的音标的第一个音素是元音，而不是说它是以元音字母开头。②它必须是个可数名词。③它还必须是个单数名词。我们常常见到这类用法： a university 一所大学 an hour 一个小时 an orange 一只桔子 an engineer 一位工程师 an ordinary man一个普通人 an honest person一位诚实的人

a boy, a city, a girl, a useful animal , an old man, an honest boy, a bad apple, a tall elephant, a university(虽然u 是元音字母，但不读元音), an hour 一个小时 (虽然h 不是元音，但单词读音是元音开头) 不定冠词有a和an两种：a用于辅音音素开头的词前，an用于元音音素开头的词前。例如： a boy, a city, a girl, a useful animal , an old man, an honest boy, a bad apple, a tall elephant, a university(虽然u 是元音字母， 但不读元音), an hour 一个小时 (虽然h 不是元音，但单词读音是元音开头) 1．指某类人或事物中的任何一个。 An elephant is bigger than a horse. A car runs faster than a bike. （2）指人或事物,用来表示“—”的意思，但不强调数的观念，只说明名词为不特定者。指人或事物即不具体说明是何人何物。。例如： There are seven days in a week. We have three meals a day. A teacher is looking for you. We work five days a week.

法语语法-名词的特点和用法

{1} 1. 名词（le nom, le substantif）的特点 名词是实体词，用以表达人、物或某种概念，如：le chauffeur（司机），le camion（卡车），la beauté（美丽）等。 法语的名词各有性别，有的属阳性，如：le soleil（太阳），le courage（勇敢），有的属阴性，如：la lune（月亮），la vie（生活）。名词还有单数和复数，形式不同，如：un ami（一个朋友），des amis（几个朋友）。 法语名词前面一般要加限定词（le déterminant），限定词可以是数词、主有形容词，批示 形容词或冠词。除数词外，均应和被限定性名词、数一致，如：la révolution（革命），un empire （一个帝国），cermarins（这些水手），mon frère（我的兄弟）。https://www.wendangku.net/doc/0b5398930.html, 大部分名词具有多义性，在文中的意义要根据上下文才能确定，如： C’est une pluie torrentielle.（这是一场倾盆大雨。） Lorsque rentre la petite fille, c’est sur elle une pluie de baisers.（当小姑娘回家时，大家都拥上去亲吻她）。 第一例, pluie是本义，第二例, pluie是上引申意义。 2. 普通名词和专有名词（le nom commun et le nom propre） 普通名词表示人、物或概念的总类，如：un officier（军官），un pays（国家），une montagne （山），la vaillance（勇敢、正直）。 专有名词指特指的人、物或概念，如：la France（法国）。 专有名词也有单、复数；阴阳性。如：un Chinois（一个中国男人），une Chinoise（一个中国女人），des Chinois（一些中国人）。 3. 普通名词和专有名词的相互转化（le passage d’une catégorie àl’autre） 普通名词可转化为专有名词，如：报刊名：l’Aube（黎明报），l’Humanité（人道报），l’Observateur（观察家报）等报刊名称是专有名词，但它们是从普通名词l’aube（黎明），I’humanité（人道），l’Observateur（观察家）借用来的。 专有名词也可以转化为普通名词，意义有所延伸，其中许多还保持第一个字母大写的形式，如商品名：le champagne（香槟酒），une Renault（雷诺车），le Bourgogne（布尔戈涅洒）。以上三例分别来自专有名词la Champagne（香槟省），Renault（雷诺，姓），la Bourgogne（布尔戈涅地区）。 4. 具体名词和抽象名词（les noms concrèts et les noms abstraits）

关于英语元音和辅音 (aan用法)区别

元音字母有：a，e，i，0，u 我的问题是当这些元音出现在单词的那个位置?才能在这个单词的前面用定冠词an 首先要记住：在名词前加an的，是指其后的单词是以发音的元音音素(即：元音音标)开始的，不是通常所说的上面几个元音字母，因为它们有时的读音不是元音音素。 正常加an的情况：an egg, an apple, an interesting book, an orange, an ugly woman，an 后面单词的读音都是元音音素。 特殊情况：an hour, an honesty boy，因为an后面的单词中的h没有发音，实际上还是读“o”的音，所以用an。 再如：a university student ，a used book之所以用a, 是因为这里u的读音不读元音音素，而是读辅音[j] 。又如：We were a unit on the question.在这个问题上，我们的意见是一致的。 掌握用an还是用a，其实很简单：如上所述，关键的是要知道紧跟在所要 选择的不定冠词(an/a)后的单词的第一个音节的读音：如果它的读音是元音 音素，就用an，否则，用a。一般情况下，五个元音字母开头的词读元音 音素，如：apple, egg, orange, umbrella, idea，它们前面就用an。 但也有以元音字母开始的单词不读元音音素的情况，经常是u，如：university, unit 或名词前有以u开始的形容词修饰时，用a。a united front 统一战线。 有时虽然是以辅音字母开始，但这个辅音字母不发音，而它的读音却是元 音音素开始，这时，也应该用an，如：hour, honest man, 前面用an，因 为这时的h没有发音，而是读o的音。 如果后面是辅音字母开始的单词，那就用a，这点并不难。如：a bed. a cup等。 一句话：用an还是用a，看紧跟其后的发音是元音音素，就用an，否则， 统统用a。

SQL教程(函数编)

SQL 教程（函数篇）
课程表
SQL 基础
? ? ? ? ? ? ? ? ? ? ?
SQL 首页 SQL 简介 SQL 语法 SQL select SQL distinct SQL where SQL AND & OR SQL Order By SQL insert SQL update SQL delete SQL 高级
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
SQL Top SQL Like SQL 通配符 SQL In SQL Between SQL Aliases SQL Join SQL Inner Join SQL Left Join SQL Right Join SQL Full Join SQL Union SQL Select Into SQL Create DB SQL Create Table SQL Constraints SQL Not Null SQL Unique SQL Primary Key SQL Foreign Key SQL Check SQL Default SQL Create Index SQL Drop

? ? ? ? ? ? ? ?
SQL Alter SQL Increment SQL View SQL Date SQL Nulls SQL isnull() SQL 数据类型 SQL 服务器 SQL 函数
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
SQL functions SQL avg() SQL count() SQL first() SQL last() SQL max() SQL min() SQL sum() SQL Group By SQL Having SQL ucase() SQL lcase() SQL mid() SQL len() SQL round() SQL now() SQL format()
SQL 总结
? ?
SQL 快速索引 SQL 总结 实例/测验 实例 测验
?
SQL 测验 建站手册
? ? ? ? ? ? ?
网站构建 万维网联盟 (W3C) 浏览器信息 网站品质 语义网 职业规划 网站主机

小学语法归纳a, an, the的用法

a, an, the的用法 （一）a, an的用法 1.a：用于辅音音素（不是辅音字母）开头的词前，表示单数的数量：“一”。但小学阶段学生一般理解为：单词开头第一个不是元音用a a book 一本书 a desk一张书桌 2.an：用于元音音素（不是元音字母）开头的词前，表示单词的数量“一”。但小学阶段学生一般理解为：单词第一个字母是元音字母用an an apple 一个苹果 a big apple一个大苹果an old man一位老人 3.元音字母：Aa, Ee, Ii, Oo, Uu 4.特殊情况：an hour（h是辅音字母，但它不发音） 5.辅音字母：26个字母中，除了5个元音字母，其他是辅音字母 练习一：用a, an, the填空 1._____book 2._____apple 3._____orange 4._____uncle 5._____eraser 6._____math book 7._____new book 8._____old book 9._____teacher 10.______English 11.____ hour 12._____good teacher 13.____idea 14.____good idea 15.____island 16.____ astronaut （二）the的用法 1.一般用于特指：The girl is my sister. 那个女孩是我的妹妹。 2.第二次出现：There is a book on the desk. The book is mine. 书桌上有一本书，那本书是我的。 3.世界上独一无二：the moon月亮the earth地球the Great Wall长城the sun太阳 4.固定的词组：on the desk在书桌上 5.形容词最高级前：Jenny is the oldest girl in the class. 在班里珍妮是年纪最大的女孩。 练习二：选择 ( )1.That’s _____ island. I like to go there. A.a B.an C.the ( )2.I have ___ new book. Jenny has ___ old book. A.a/ an B.an/ a C.an/ an ( )3.This is ___ orange. That’s ____big orange. A.a/ an B.an/ a C.an/ an ( )4.Yesterday I studied English for ____ hour. A.an B.the C.a ( )5.This is a bag. ____ bag is Tom’s. A.A B.An C.The ( )6.___ man is Lisa’s father. A.A B.The C.An ( )7.____ Great Wall is in China. A.A B.The C.An ( )8.My English book is in ___ desk. A.the B.an C./ ( )9.She has ___ idea. It’s a good idea. A.a B.an C.the 练习三：a, an, the填空 1.Tom wants to be _____ scientist(科学家).He wants to go to ___ moon. 2.Jenny has ______ uncle and _____ cousin. 3.I have _____ eraser. _____ eraser is in my bag. 4._____ boy is Tom’s brother. 5.The bird was here ______ hour ago. 6.There is _____ English book on the desk. ______ English book is Tom’s. 7.I have _____ book. It is _____ English book. And it has _____ goos story. _____ book is in my bag. 8.There is _____ cat under the tree. _____ cat is playing.

常见系动词的分类及使用特点

常见系动词的分类及使用特点 系动词词义不完整，在句中不能单独使用（除省略句外），后面必须接有表语，系动词和表语一起构成合成谓语。常见的系动词大致可分为三类。 第一类：表示特征或状态的，有 be, look, feel, seem, appear, smell, taste, sound, turn out（结果是、证明是）等。 You'll be all right soon. You don't look very well. I feel rather cold. He seems to be ill. It appears that he is unhappy. The roses smell sweet. The mixture tasted horrible. How sweet the music sounds! The day turned out (to be）a fine one. 第二类：表示从一种状态到另一种状态的变化，有 become, get, grow, turn, fall, go, come, run 等。 He became a world-famous scientist. It is getting warmer and warmer. It grew dark. The food has turned bad. Yesterday he suddenly fell ill. Mary's face went red. His dream has come true. The boy's blood ran cold. 第三类：表示保持状态的，有keep, remain, continue 等。 Keep quiet, children! The weather continued fine for a long time. It remains to be proved. 系动词后的表语可以是名词、代词、数词、形容词、分词、动名词、不定式、副词、介词短语、词组、从句，系动词 be 可用于上述所有情况。如： The people are the real heroes. (名词) That's something we have always to keep in mind. (代词) She is often the first to come here. (数词) She is pretty and wise. (形容词). The news was surprising. (分词) His job is teaching English. (动名词) The only method is to give the child more help. (不定式） I must be off now. (副词) The bridge is under construction. (介词短语) That would be a great weight off my mind. (词组) This is why he was late. (从句) 系动词的使用特点： 1、所有的系动词都可接形容词作表语，此处略举数例。

a an the的用法

有点多请细心看啊不定冠词有"a和an"两种形式."a"用在以辅音开头的词前,"an"用在以元音开头的词前.判断一个词是以元音开头还是以辅音开头,是根据读音而不是根据字母.一般情况下,开头字母是 a、e、f、h、j、l、m、n、o、r、s、x前用不定冠词an. 1. 用于可数名词的单数形式前,表示"一" There is a tiger in the zoo. 动物园里有一只老虎. 2. 表示一类人和东西 A tiger can be dangerous. 老虎可能有危害性. 3. 表示"某一个"的意思 A gentleman wants to see you. 有一位先生要见你. 4. 表示"同一"的意思 They are nearly of an age. 他们几乎同岁. The two shirts are much of a size. 这两件衬衫大小差不多. 5. 表示"每一"的意思 We go swimming four times a week. 我们每周去游泳四次. 6. 用在作表语的单数可数名词前,表示身份、职业 My mother is a teacher. 我妈妈是教师. 7. 第一次提到的人或事物,但不特别指明是哪一个 Long long ago there was an old king who had a very beautiful daughter. 很久很久以前,有一个年老的国王,他有一个非常美丽的女儿. 8. 在英国英语中,以"h"开头的多音节词,如第一个音节不重读,其前亦可用"an" There is a hotel near here. 这附近有一家旅馆. 9. 在such a,quite a句式中 He is quite a good actor. 他是一个相当好的演员. Don't be in such a hurry. 不要如此匆忙. 10. 在感叹句what...的句式中 What a pretty girl she is! 她是一个多么漂亮的女孩呀! 用在某些表示数量的词组中： a lot of 许多 a couple of 一对 a great many 很多 a dozen 一打（但也可以用one dozen） a great deal of 大量[编辑本段] 定冠词的用法 1. 用以特指某（些）人或某（些）事物 This is the house where Luxun once lived. 这是鲁迅曾经住过的房子. 2. 用于指谈话双方都明确所指的人或事物 Open the door, please.