下载文档原格式
Reprinted with corrections from The Bell System Technical Journal,V ol.27,pp.379–423,623–656,July,October,1948.A Mathematical Theory of CommunicationBy C.E.SHANNONI NTRODUCTIONHE recent development of various methods of modulation such as PCM and PPM which exchangebandwidth for signal-to-noise ratio has intensified the interest in a general theory of communication.A basis for such a theory is contained in the important papers of Nyquist1and Hartley2on this subject.In the present paper we will extend the theory to include a number of new factors,in particular the effect of noise in the channel,and the savings possible due to the statistical structure of the original message and due to the nature of thefinal destination of the information.The fundamental problem of communication is that of reproducing at one point either exactly or ap-proximately a message selected at another point.Frequently the messages have meaning;that is they refer to or are correlated according to some system with certain physical or conceptual entities.These semantic aspects of communication are irrelevant to the engineering problem.The significant aspect is that the actual message is one selected from a set of possible messages.The system must be designed to operate for each possible selection,not just the one which will actually be chosen since this is unknown at the time of design.If the number of messages in the set isfinite then this number or any monotonic function of this number can be regarded as a measure of the information produced when one message is chosen from the set,all choices being equally likely.As was pointed out by Hartley the most natural choice is the logarithmic function.Although this definition must be generalized considerably when we consider the influence of the statistics of the message and when we have a continuous range of messages,we will in all cases use an essentially logarithmic measure.The logarithmic measure is more convenient for various reasons:1.It is practically more useful.Parameters of engineering importance such as time,bandwidth,numberof relays,etc.,tend to vary linearly with the logarithm of the number of possibilities.For example,adding one relay to a group doubles the number of possible states of the relays.It adds1to the base2logarithm of this number.Doubling the time roughly squares the number of possible messages,ordoubles the logarithm,etc.2.It is nearer to our intuitive feeling as to the proper measure.This is closely related to(1)since we in-tuitively measures entities by linear comparison with common standards.One feels,for example,thattwo punched cards should have twice the capacity of one for information storage,and two identicalchannels twice the capacity of one for transmitting information.3.It is mathematically more suitable.Many of the limiting operations are simple in terms of the loga-rithm but would require clumsy restatement in terms of the number of possibilities.The choice of a logarithmic base corresponds to the choice of a unit for measuring information.If the base2is used the resulting units may be called binary digits,or more briefly bits,a word suggested by J.W.Tukey.A device with two stable positions,such as a relay or aflip-flop circuit,can store one bit of information.N such devices can store N bits,since the total number of possible states is2N and log22N N.If the base10is used the units may be called decimal digits.Sincelog2M log10M log102332log10M1Nyquist,H.,“Certain Factors Affecting Telegraph Speed,”Bell System Technical Journal,April1924,p.324;“Certain Topics in Telegraph Transmission Theory,”A.I.E.E.Trans.,v.47,April1928,p.617.2Hartley,R.V.L.,“Transmission of Information,”Bell System Technical Journal,July1928,p.535.INFORMATIONSOURCE TRANSMITTER RECEIVER DESTINATIONNOISESOURCEFig.1—Schematic diagram of a general communication system.a decimal digit is about31physical counterparts.We may roughly classify communication systems into three main categories:discrete, continuous and mixed.By a discrete system we will mean one in which both the message and the signal are a sequence of discrete symbols.A typical case is telegraphy where the message is a sequence of lettersand the signal a sequence of dots,dashes and spaces.A continuous system is one in which the message and signal are both treated as continuous functions,e.g.,radio or television.A mixed system is one in which both discrete and continuous variables appear,e.g.,PCM transmission of speech.Wefirst consider the discrete case.This case has applications not only in communication theory,but also in the theory of computing machines,the design of telephone exchanges and otherfields.In additionthe discrete case forms a foundation for the continuous and mixed cases which will be treated in the second half of the paper.PART I:DISCRETE NOISELESS SYSTEMS1.T HE D ISCRETE N OISELESS C HANNELTeletype and telegraphy are two simple examples of a discrete channel for transmitting information.Gen-erally,a discrete channel will mean a system whereby a sequence of choices from afinite set of elementarysymbols S1S n can be transmitted from one point to another.Each of the symbols S i is assumed to have a certain duration in time t i seconds(not necessarily the same for different S i,for example the dots anddashes in telegraphy).It is not required that all possible sequences of the S i be capable of transmission on the system;certain sequences only may be allowed.These will be possible signals for the channel.Thus in telegraphy suppose the symbols are:(1)A dot,consisting of line closure for a unit of time and then line open for a unit of time;(2)A dash,consisting of three time units of closure and one unit open;(3)A letter space consisting of,say,three units of line open;(4)A word space of six units of line open.We might place the restriction on allowable sequences that no spaces follow each other(for if two letter spaces are adjacent, it is identical with a word space).The question we now consider is how one can measure the capacity of such a channel to transmit information.In the teletype case where all symbols are of the same duration,and any sequence of the32symbols is allowed the answer is easy.Each symbol representsfive bits of information.If the system transmits n symbols per second it is natural to say that the channel has a capacity of5n bits per second.This does not mean that the teletype channel will always be transmitting information at this rate—this is the maximum possible rate and whether or not the actual rate reaches this maximum depends on the source of information which feeds the channel,as will appear later.In the more general case with different lengths of symbols and constraints on the allowed sequences,we make the following definition:Definition:The capacity C of a discrete channel is given bylog N TC LimT∞and thereforeC log X0In case there are restrictions on allowed sequences we may still often obtain a difference equation of this type andfind C from the characteristic equation.In the telegraphy case mentioned aboveN t N t2N t4N t5N t7N t8N t10as we see by counting sequences of symbols according to the last or next to the last symbol occurring. Hence C is log0where0is the positive root of12457810.Solving this wefind C0539.A very general type of restriction which may be placed on allowed sequences is the following:We imagine a number of possible states a1a2a m.For each state only certain symbols from the set S1S n can be transmitted(different subsets for the different states).When one of these has been transmitted the state changes to a new state depending both on the old state and the particular symbol transmitted.The telegraph case is a simple example of this.There are two states depending on whether or not a space was the last symbol transmitted.If so,then only a dot or a dash can be sent next and the state always changes. If not,any symbol can be transmitted and the state changes if a space is sent,otherwise it remains the same. The conditions can be indicated in a linear graph as shown in Fig.2.The junction points correspond totheFig.2—Graphical representation of the constraints on telegraph symbols.states and the lines indicate the symbols possible in a state and the resulting state.In Appendix1it is shown that if the conditions on allowed sequences can be described in this form C will exist and can be calculated in accordance with the following result:Theorem1:Let b s i j be the duration of the s th symbol which is allowable in state i and leads to state j. Then the channel capacity C is equal to log W where W is the largest real root of the determinant equation:∑s W bsi j i j0where i j1if i j and is zero otherwise.For example,in the telegraph case(Fig.2)the determinant is:1W2W4W3W6W2W410On expansion this leads to the equation given above for this case.2.T HE D ISCRETE S OURCE OF I NFORMATIONWe have seen that under very general conditions the logarithm of the number of possible signals in a discrete channel increases linearly with time.The capacity to transmit information can be specified by giving this rate of increase,the number of bits per second required to specify the particular signal used.We now consider the information source.How is an information source to be described mathematically, and how much information in bits per second is produced in a given source?The main point at issue is the effect of statistical knowledge about the source in reducing the required capacity of the channel,by the useof proper encoding of the information.In telegraphy,for example,the messages to be transmitted consist of sequences of letters.These sequences,however,are not completely random.In general,they form sentences and have the statistical structure of,say,English.The letter E occurs more frequently than Q,the sequence TH more frequently than XP,etc.The existence of this structure allows one to make a saving in time(or channel capacity)by properly encoding the message sequences into signal sequences.This is already done to a limited extent in telegraphy by using the shortest channel symbol,a dot,for the most common English letter E;while the infrequent letters,Q,X,Z are represented by longer sequences of dots and dashes.This idea is carried still further in certain commercial codes where common words and phrases are represented by four-orfive-letter code groups with a considerable saving in average time.The standardized greeting and anniversary telegrams now in use extend this to the point of encoding a sentence or two into a relatively short sequence of numbers.We can think of a discrete source as generating the message,symbol by symbol.It will choose succes-sive symbols according to certain probabilities depending,in general,on preceding choices as well as the particular symbols in question.A physical system,or a mathematical model of a system which produces such a sequence of symbols governed by a set of probabilities,is known as a stochastic process.3We may consider a discrete source,therefore,to be represented by a stochastic process.Conversely,any stochastic process which produces a discrete sequence of symbols chosen from afinite set may be considered a discrete source.This will include such cases as:1.Natural written languages such as English,German,Chinese.2.Continuous information sources that have been rendered discrete by some quantizing process.Forexample,the quantized speech from a PCM transmitter,or a quantized television signal.3.Mathematical cases where we merely define abstractly a stochastic process which generates a se-quence of symbols.The following are examples of this last type of source.(A)Suppose we havefive letters A,B,C,D,E which are chosen each with probability.2,successivechoices being independent.This would lead to a sequence of which the following is a typicalexample.B DC B C E C C C AD C B D D A AE C E E AA B B D A E E C A C E E B A E E C B C E A D.This was constructed with the use of a table of random numbers.4(B)Using the samefive letters let the probabilities be.4,.1,.2,.2,.1,respectively,with successivechoices independent.A typical message from this source is then:A A A C D CB DC E A AD A D A CE D AE A D C A B E D A D D C E C A A A A A D.(C)A more complicated structure is obtained if successive symbols are not chosen independentlybut their probabilities depend on preceding letters.In the simplest case of this type a choicedepends only on the preceding letter and not on ones before that.The statistical structure canthen be described by a set of transition probabilities p i j,the probability that letter i is followedby letter j.The indices i and j range over all the possible symbols.A second equivalent way ofspecifying the structure is to give the“digram”probabilities p i j,i.e.,the relative frequency ofthe digram i j.The letter frequencies p i,(the probability of letter i),the transition probabilities 3See,for example,S.Chandrasekhar,“Stochastic Problems in Physics and Astronomy,”Reviews of Modern Physics,v.15,No.1, January1943,p.1.4Kendall and Smith,Tables of Random Sampling Numbers,Cambridge,1939.p i j and the digram probabilities p i j are related by the following formulas:p i ∑j p i j∑j p j i ∑j p j p j ip i j p i p i j∑j p ij ∑i p i ∑i jp i j 1As a specific example suppose there are three letters A,B,C with the probability tables:p i j A B C 045i B 21151p i jA1518270C 274135A typical message from this source is the following:A B B A B A B A B A B A B A B B B A B B B B B A B A B A B A B A B B B A C A C A BB A B B B B A B B A B AC B B B A B A.The next increase in complexity would involve trigram frequencies but no more.The choice ofa letter would depend on the preceding two letters but not on the message before that point.A set of trigram frequencies p i j k or equivalently a set of transition probabilities p i j k would be required.Continuing in this way one obtains successively more complicated stochastic pro-cesses.In the general n -gram case a set of n -gram probabilities p i 1i 2i n or of transition probabilities p i 1i 2i n 1i n is required to specify the statistical structure.(D)Stochastic processes can also be defined which produce a text consisting of a sequence of“words.”Suppose there are five letters A,B,C,D,E and 16“words”in the language with associated probabilities:.10A.16BEBE .11CABED .04DEB .04ADEB.04BED .05CEED .15DEED .05ADEE.02BEED .08DAB .01EAB .01BADD .05CA .04DAD .05EESuppose successive “words”are chosen independently and are separated by a space.A typical message might be:DAB EE A BEBE DEED DEB ADEE ADEE EE DEB BEBE BEBE BEBE ADEE BED DEED DEED CEED ADEE A DEED DEED BEBE CABED BEBE BED DAB DEED ADEB.If all the words are of finite length this process is equivalent to one of the preceding type,but the description may be simpler in terms of the word structure and probabilities.We may also generalize here and introduce transition probabilities between words,etc.These artificial languages are useful in constructing simple problems and examples to illustrate vari-ous possibilities.We can also approximate to a natural language by means of a series of simple artificial languages.The zero-order approximation is obtained by choosing all letters with the same probability and independently.The first-order approximation is obtained by choosing successive letters independently but each letter having the same probability that it has in the natural language.5Thus,in the first-order ap-proximation to English,E is chosen with probability .12(its frequency in normal English)and W with probability .02,but there is no influence between adjacent letters and no tendency to form the preferred5Letter,digram and trigram frequencies are given in Secret and Urgent by Fletcher Pratt,Blue Ribbon Books,1939.Word frequen-cies are tabulated in Relative Frequency of English Speech Sounds,G.Dewey,Harvard University Press,1923.digrams such as TH,ED,etc.In the second-order approximation,digram structure is introduced.After aletter is chosen,the next one is chosen in accordance with the frequencies with which the various lettersfollow thefirst one.This requires a table of digram frequencies p i j.In the third-order approximation, trigram structure is introduced.Each letter is chosen with probabilities which depend on the preceding twoletters.3.T HE S ERIES OF A PPROXIMATIONS TO E NGLISHTo give a visual idea of how this series of processes approaches a language,typical sequences in the approx-imations to English have been constructed and are given below.In all cases we have assumed a27-symbol “alphabet,”the26letters and a space.1.Zero-order approximation(symbols independent and equiprobable).XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIBZL-HJQD.2.First-order approximation(symbols independent but with frequencies of English text).OCRO HLI RGWR NMIELWIS EU LL NBNESEBY A TH EEI ALHENHTTPA OOBTTV ANAH BRL.3.Second-order approximation(digram structure as in English).ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVE TU-COOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.4.Third-order approximation(trigram structure as in English).IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONS-TURES OF THE REPTAGIN IS REGOACTIONA OF CRE.5.First-order word approximation.Rather than continue with tetragram,,n-gram structure it is easierand better to jump at this point to word units.Here words are chosen independently but with their appropriate frequencies.REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NAT-URAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHESTHE LINE MESSAGE HAD BE THESE.6.Second-order word approximation.The word transition probabilities are correct but no further struc-ture is included.THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHAR-ACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THATTHE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.The resemblance to ordinary English text increases quite noticeably at each of the above steps.Note that these samples have reasonably good structure out to about twice the range that is taken into account in their construction.Thus in(3)the statistical process insures reasonable text for two-letter sequences,but four-letter sequences from the sample can usually befitted into good sentences.In(6)sequences of four or more words can easily be placed in sentences without unusual or strained constructions.The particular sequence of ten words“attack on an English writer that the character of this”is not at all unreasonable.It appears then that a sufficiently complex stochastic process will give a satisfactory representation of a discrete source.Thefirst two samples were constructed by the use of a book of random numbers in conjunction with(for example2)a table of letter frequencies.This method might have been continued for(3),(4)and(5), since digram,trigram and word frequency tables are available,but a simpler equivalent method was used.To construct(3)for example,one opens a book at random and selects a letter at random on the page.This letter is recorded.The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded.Turning to another page this second letter is searched for and the succeeding letter recorded,etc.A similar process was used for(4),(5)and(6).It would be interesting if further approximations could be constructed,but the labor involved becomes enormous at the next stage.4.G RAPHICAL R EPRESENTATION OF A M ARKOFF P ROCESSStochastic processes of the type described above are known mathematically as discrete Markoff processes and have been extensively studied in the literature.6The general case can be described as follows:There exist afinite number of possible“states”of a system;S1S2S n.In addition there is a set of transition probabilities;p i j the probability that if the system is in state S i it will next go to state S j.To make thisMarkoff process into an information source we need only assume that a letter is produced for each transition from one state to another.The states will correspond to the“residue of influence”from preceding letters.The situation can be represented graphically as shown in Figs.3,4and5.The“states”are thejunctionFig.3—A graph corresponding to the source in example B.points in the graph and the probabilities and letters produced for a transition are given beside the correspond-ing line.Figure3is for the example B in Section2,while Fig.4corresponds to the example C.In Fig.3Fig.4—A graph corresponding to the source in example C.there is only one state since successive letters are independent.In Fig.4there are as many states as letters. If a trigram example were constructed there would be at most n2states corresponding to the possible pairs of letters preceding the one being chosen.Figure5is a graph for the case of word structure in example D. Here S corresponds to the“space”symbol.5.E RGODIC AND M IXED S OURCESAs we have indicated above a discrete source for our purposes can be considered to be represented by a Markoff process.Among the possible discrete Markoff processes there is a group with special properties of significance in communication theory.This special class consists of the“ergodic”processes and we shall call the corresponding sources ergodic sources.Although a rigorous definition of an ergodic process is somewhat involved,the general idea is simple.In an ergodic process every sequence produced by the process 6For a detailed treatment see M.Fr´e chet,M´e thode des fonctions arbitraires.Th´e orie des´e v´e nements en chaˆıne dans le cas d’un nombrefini d’´e tats possibles.Paris,Gauthier-Villars,1938.is the same in statistical properties.Thus the letter frequencies,digram frequencies,etc.,obtained from particular sequences,will,as the lengths of the sequences increase,approach definite limits independent of the particular sequence.Actually this is not true of every sequence but the set for which it is false has probability zero.Roughly the ergodic property means statistical homogeneity.All the examples of artificial languages given above are ergodic.This property is related to the structure of the corresponding graph.If the graph has the following two properties7the corresponding process will be ergodic:1.The graph does not consist of two isolated parts A and B such that it is impossible to go from junctionpoints in part A to junction points in part B along lines of the graph in the direction of arrows and also impossible to go from junctions in part B to junctions in part A.2.A closed series of lines in the graph with all arrows on the lines pointing in the same orientation willbe called a“circuit.”The“length”of a circuit is the number of lines in it.Thus in Fig.5series BEBES is a circuit of length5.The second property required is that the greatest common divisor of the lengths of all circuits in the graph beone.If thefirst condition is satisfied but the second one violated by having the greatest common divisor equal to d1,the sequences have a certain type of periodic structure.The various sequences fall into d different classes which are statistically the same apart from a shift of the origin(i.e.,which letter in the sequence is called letter1).By a shift of from0up to d1any sequence can be made statistically equivalent to any other.A simple example with d2is the following:There are three possible letters a b c.Letter a isfollowed with either b or c with probabilities13respectively.Either b or c is always followed by lettera.Thus a typical sequence isa b a c a c a c a b a c a b a b a c a cThis type of situation is not of much importance for our work.If thefirst condition is violated the graph may be separated into a set of subgraphs each of which satisfies thefirst condition.We will assume that the second condition is also satisfied for each subgraph.We have in this case what may be called a“mixed”source made up of a number of pure components.The components correspond to the various subgraphs.If L1,L2,L3are the component sources we may writeL p1L1p2L2p3L37These are restatements in terms of the graph of conditions given in Fr´e chet.where p i is the probability of the component source L i.Physically the situation represented is this:There are several different sources L1,L2,L3which are each of homogeneous statistical structure(i.e.,they are ergodic).We do not know a priori which is to be used,but once the sequence starts in a given pure component L i,it continues indefinitely according to the statistical structure of that component.As an example one may take two of the processes defined above and assume p12and p28.A sequence from the mixed sourceL2L18L2would be obtained by choosingfirst L1or L2with probabilities.2and.8and after this choice generating a sequence from whichever was chosen.Except when the contrary is stated we shall assume a source to be ergodic.This assumption enables one to identify averages along a sequence with averages over the ensemble of possible sequences(the probability of a discrepancy being zero).For example the relative frequency of the letter A in a particular infinite sequence will be,with probability one,equal to its relative frequency in the ensemble of sequences.If P i is the probability of state i and p i j the transition probability to state j,then for the process to be stationary it is clear that the P i must satisfy equilibrium conditions:P j∑iP i p i jIn the ergodic case it can be shown that with any starting conditions the probabilities P j N of being in state j after N symbols,approach the equilibrium values as N∞.6.C HOICE,U NCERTAINTY AND E NTROPYWe have represented a discrete information source as a Markoff process.Can we define a quantity which will measure,in some sense,how much information is“produced”by such a process,or better,at what rate information is produced?Suppose we have a set of possible events whose probabilities of occurrence are p1p2p n.These probabilities are known but that is all we know concerning which event will occur.Can wefind a measure of how much“choice”is involved in the selection of the event or of how uncertain we are of the outcome?If there is such a measure,say H p1p2p n,it is reasonable to require of it the following properties:1.H should be continuous in the p i.2.If all the p i are equal,p i12,p216.On the right wefirst choose between two possibilities each withprobability13,1216H121312is because this second choice only occurs half the time.In Appendix2,the following result is established:Theorem2:The only H satisfying the three above assumptions is of the form:H Kn∑i1p i log p iwhere K is a positive constant.This theorem,and the assumptions required for its proof,are in no way necessary for the present theory.It is given chiefly to lend a certain plausibility to some of our later definitions.The real justification of these definitions,however,will reside in their implications.Quantities of the form H∑p i log p i(the constant K merely amounts to a choice of a unit of measure) play a central role in information theory as measures of information,choice and uncertainty.The form of H will be recognized as that of entropy as defined in certain formulations of statistical mechanics8where p i isthe probability of a system being in cell i of its phase space.H is then,for example,the H in Boltzmann’s famous H theorem.We shall call H∑p i log p i the entropy of the set of probabilities p1p n.If x is a chance variable we will write H x for its entropy;thus x is not an argument of a function but a label for anumber,to differentiate it from H y say,the entropy of the chance variable y.The entropy in the case of two possibilities with probabilities p and q1p,namelyH p log p q log qis plotted in Fig.7as a function of p.HBITSpFig.7—Entropy in the case of two possibilities with probabilities p and1p.The quantity H has a number of interesting properties which further substantiate it as a reasonable measure of choice or information.1.H0if and only if all the p i but one are zero,this one having the value unity.Thus only when weare certain of the outcome does H vanish.Otherwise H is positive.2.For a given n,H is a maximum and equal to log n when all the p i are equal(i.e.,1。
CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson 方法是用矩阵( D - θI)- 1( A - θI) 产生子空间，这里D 是A 的对角元所组成的对角矩阵。
θ是由Rayleigh-Ritz 过程所得到的A的近似特征值。
什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi 的迭代形式来求解。
这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。
如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。
记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。
定义1：对于n 阶方阵A 而言，如果存在一个排列阵P 使得P'AP 为一个分块上三角阵，我们就称矩阵A 是可约的；否则称矩阵A 是不可约的。
定义2：对于n 阶方阵A=(aij) 而言，如果指标集{1，2，...，n} 能够被划分成两个不相交的非空指标集J 和K，使得对任意的j∈J 和任意的k∈K 都有ajk=0, 则称矩阵 A 是可约的；否则称矩阵A 是不可约的。
1000 A+B Problem 送分题1001 Exponentiation 高精度1003 Hangover 送分题1004 Financial Management 送分题1005 I Think I Need a Houseboat 几何1006 Biorhythms 送分题1007 DNA Sorting 送分题1008 Maya Calendar 日期处理1010 STAMPS 搜索＋DP1011 Sticks 搜索1012 Joseph 模拟/数学方法1014 Dividing 数论/DP?/组合数学->母函数?1015 Jury Compromise DP1016 Numbers That Count 送分题1017 Packets 贪心1018 Communication System 贪心1019 Number Sequence 送分题1020 Anniversary Cake 搜索1023 The Fun Number System 数论1025 Department 模拟1026 Cipher 组合数学1027 The Same Game 模拟1028 Web Navigation 送分题1031 Fence 计算几何1034 The dog task 计算几何1037 A decorative fence DP/组合数学1039 Pipe 几何1042 Gone Fishing 贪心/DP1045 Bode Plot 送分题(用物理知识)1046 Color Me Less 送分题1047 Round and Round We Go 高精度1048 Follow My Logic 模拟1049 Microprocessor Simulation 模拟1050 To the Max DP1053 Set Me 送分题1054 The Troublesome Frog 搜索1060 Modular multiplication of polynomials 高精度1061 青蛙的约会数论1062 昂贵的聘礼DP1064 Cable master DP/二分查找1065 Wooden Sticks DP1067 取石子游戏博弈论1068 Parencodings 送分题1069 The Bermuda Triangle 搜索1070 Deformed Wheel 几何1071 Illusive Chase 送分题1072 Puzzle Out 搜索1073 The Willy Memorial Program 模拟1074 Parallel Expectations DP1075 University Entrance Examination 模拟1080 Human Gene Functions DP->LCS变形1082 Calendar Game 博弈论1084 Square Destroyer 搜索？1085 Triangle War 博弈论1086 Unscrambling Images 模拟?1087 A Plug for UNIX 图论->最大流1088 滑雪DFS/DP1090 Chain ->格雷码和二进制码的转换1091 跳蚤数论1092 Farmland 几何1093 Formatting Text DP1094 Sorting It All Out 图论->拓扑排序1095 Trees Made to Order 组合数学1096 Space Station Shielding 送分题1097 Roads Scholar 图论1098 Robots 模拟1099 Square Ice 送分题1100 Dreisam Equations 搜索1101 The Game 搜索->BFS1102 LC-Display 送分题1103 Maze 模拟1104 Robbery 递推1106 Transmitters 几何1107 W's Cipher 送分题1110 Double Vision 搜索1111 Image Perimeters 搜索1112 Team Them Up! DP1113 Wall 计算几何->convex hull1119 Start Up the Startup 送分题1120 A New Growth Industry 模拟1122 FDNY to the Rescue! 图论->Dijkstra 1125 Stockbroker Grapevine 图论->Dijkstra 1128 Frame Stacking 搜索1129 Channel Allocation 搜索（图的最大独立集）1131 Octal Fractions 高精度1135 Domino Effect 图论->Dijkstra1137 The New Villa 搜索->BFS1141 Brackets Sequence DP1142 Smith Numbers 搜索1143 Number Game 博弈论1147 Binary codes 构造1148 Utopia Divided 构造1149 PIGS 图论->网络流1151 Atlantis 计算几何->同等安置矩形的并的面积->离散化1152 An Easy Problem! 数论1157 LITTLE SHOP OF FLOWERS DP1158 TRAFFIC LIGHTS 图论->Dijkstra变形1159 Palindrome DP->LCS1160 Post Office DP1161 Walls 图论1162 Building with Blocks 搜索1163 The Triangle DP1170 Shopping Offers DP1177 Picture 计算几何->同等安置矩形的并的周长->线段树1179 Polygon DP1180 Batch Scheduling DP1182 食物链数据结构->并查集1183 反正切函数的应用搜索1184 聪明的打字员搜索1185 炮兵阵地DP->数据压缩1187 陨石的秘密DP（BalkanOI99 Par的拓展）1189 钉子和小球递推?1190 生日蛋糕搜索/DP1191 棋盘分割DP1192 最优连通子集图论->无负权回路的有向图的最长路->BellmanFord 1193 内存分配模拟1194 HIDDEN CODES 搜索+DP1197 Depot 数据结构->Young T ableau1201 Intervals 贪心/图论->最长路->差分约束系统1202 Family 高精度1209 Calendar 日期处理1217 FOUR QUARTERS 递推1218 THE DRUNK JAILER 送分题1233 Street Crossing 搜索->BFS1245 Programmer, Rank Thyself 送分题1247 Magnificent Meatballs 送分题1248 Safecracker 搜索1250 T anning Salon 送分题1251 Jungle Roads 图论->最小生成树1271 Nice Milk 计算几何1273 Drainage Ditches 图论->最大流1274 The Perfect Stall 图论->二分图的最大匹配1275 Cashier Employment 图论->差分约束系统->无负权回路的有向图的最长路->Bellman-Ford1280 Game 递推1281 MANAGER 模拟1286 Necklace of Beads 组合数学->Polya定理1288 Sly Number 数论->解模线性方程组1293 Duty Free Shop DP1298 The Hardest Problem Ever 送分题1316 Self Numbers 递推同Humble Number一样1322 Chocolate 递推/组合数学1323 Game Prediction 贪心1324 Holedox Moving BFS+压缩储存1325 Machine Schedule 图论->二分图的最大匹配1326 Mileage Bank 送分题1327 Moving Object Recognition 模拟?1328 Radar Installation 贪心（差分约束系统的特例）1338 Ugly Numbers 递推(有O(n)算法)1364 King 图论->无负权回路的有向图的最长路->BellmanFord1370 Gossiping (数论->模线性方程有无解的判断)+(图论->DFS)2184 Cow Exhibition DP2190 ISBN 送分题2191 Mersenne Composite Numbers 数论2192 Zipper DP->LCS变形2193 Lenny's Lucky Lotto Lists DP2194 Stacking Cylinders 几何2195 Going Home 图论->二分图的最大权匹配2196 Specialized Four-Digit Numbers 送分题2197 Jill's Tour Paths 图论->2199 Rate of Return 高精度2200 A Card Trick 模拟2210 Metric Time 日期处理2239 Selecting Courses 图论->二分图的最大匹配2243 Knight Moves 搜索->BFS2247 Humble Numbers 递推(最优O(n)算法)2253 Frogger 图论->Dijkstra变形(和1295是一样的)2254 Globetrotter 几何2261 France '98 递推2275 Flipping Pancake 构造2284 That Nice Euler Circuit 计算几何2289 Jamie's Contact Groups 图论->网络流?2291 Rotten Ropes 送分题2292 Optimal Keypad DP2299 Ultra-QuickSort 排序->归并排序2304 Combination Lock 送分题2309 BST 送分题2311 Cutting Game 博弈论2312 Battle City 搜索->BFS2314 POJ language 模拟2315 Football Game 几何2346 Lucky tickets 组合数学2351 Time Zones 时间处理2379 ACM Rank T able 模拟+排序2381 Random Gap 数论2385 Apple Catching DP(像NOI98“免费馅饼”)2388 Who's in the Middle 送分题(排序)2390 Bank Interest 送分题2395 Out of Hay 图论->Dijkstra变形2400 Supervisor, Supervisee 图论->二分图的最大权匹配?2403 Hay Points 送分题2409 Let it Bead 组合数学->Polya定理2416 Return of the Jedi 图论->2417 Discrete Logging 数论2418 Hardwood Species 二分查找2419 Forests 枚举2421 Constructing Roads 图论->最小生成树2423 The Parallel Challenge Ballgame 几何2424 Flo's Restaurant 数据结构->堆2425 A Chess Game 博弈论2426 Remainder BFS2430 Lazy Cows DP->数据压缩1375 Intervals 几何1379 Run Away 计算几何->1380 Equipment Box 几何1383 Labyrinth 图论->树的最长路1394 Railroad 图论->Dijkstra1395 Cog-Wheels 数学->解正系数的线性方程组1408 Fishnet 几何1411 Calling Extraterrestrial Intelligence Again 送分题1430 Binary Stirling Numbers 日期处理1431 Calendar of Maya 模拟1432 Decoding Morse Sequences DP1434 Fill the Cisterns! 计算几何->离散化/1445 Random number 数据结构->碓1447 Ambiguous Dates 日期处理1450 Gridland 图论(本来TSP问题是NP难的，但这个图比较特殊，由现成的构造方法)1458 Common Subsequence DP->LCS1459 Power Network 图论->最大流1462 Random Walk 模拟+解线性方程组1463 Strategic game 贪心1466 Girls and Boys 图论->n/a1469 COURSES 贪心1475 Pushing Boxes DP1476 Always On the Run 搜索->BFS1480 Optimal Programs 搜索->BFS1481 The Die Is Cast 送分题1482 It's not a Bug, It's a Feature! 搜索->BFS1483 Going in Circles on Alpha Centauri 模拟1484 Blowing Fuses 送分题1485 Fast Food DP(似乎就是ioi2000的postoffice)1486 Sorting Slides 图论->拓扑排序1505 Copying Books DP+二分查找1510 Hares and Foxes 数论1512 Keeps Going and Going and ... 模拟1513 Scheduling Lectures DP1514 Metal Cutting 几何1515 Street Directions 图论->把一个无向连通图改造成为有向强连通图1517 u Calculate e 送分题1518 Problem Bee 几何1519 Digital Roots 送分题(位数可能很大)1520 Scramble Sort 排序1547 Clay Bully 送分题1555 Polynomial Showdown 送分题(非常阴险)1563 The Snail 送分题1601 Pizza Anyone? 搜索1604 Just the Facts 送分题1605 Horse Shoe Scoring 几何1606 Jugs 数论/搜索1631 Bridging signals DP+二分查找1632 Vase collection 图论->最大完全图1633 Gladiators DP1634 Who's the boss? 排序1635 Subway tree systems 图论->不同表示法的二叉树判同1637 Sightseeing tour 图论->欧拉回路1638 A number game 博弈论1639 Picnic Planning 图论->1641 Rational Approximation 数论1646 Double Trouble 高精度1654 Area 几何1657 Distance on Chessboard 送分题1658 Eva's Problem 送分题1660 Princess FroG 构造1661 Help Jimmy DP1663 Number Steps 送分题1664 放苹果组合数学->递推1677 Girls' Day 送分题1688 Dolphin Pool 计算几何1690 (Your)((Term)((Project))) 送分题1691 Painting A Board 搜索/DP1692 Crossed Matchings DP1693 Counting Rectangles 几何1694 An Old Stone Game 博弈论?1695 Magazine Delivery 图论->1712 Flying Stars DP1713 Divide et unita 搜索1714 The Cave 搜索/DP1717 Dominoes DP1718 River Crossing DP1719 Shooting Contest 贪心1729 Jack and Jill 图论->1730 Perfect Pth Powers 数论1732 Phone numbers DP1734 Sightseeing trip 图论->Euler回路1738 An old Stone Game 博弈论?1741 Tree 博弈论?1745 Divisibility DP1751 Highways 图论->1752 Advertisement 贪心/图论->差分约束系统1753 Flip Game 搜索->BFS1755 Triathlon 计算几何?1770 Special Experiment 树形DP1771 Elevator Stopping Plan DP1772 New Go Game 构造?1773 Outernet 模拟1774 Fold Paper Strips 几何1775 Sum of Factorials 送分题1776 T ask Sequences DP1777 Vivian's Problem 数论1870 Bee Breeding 送分题1871 Bullet Hole 几何1872 A Dicey Problem BFS1873 The Fortified Forest 几何+回溯1874 Trade on Verweggistan DP1875 Robot 几何1876 The Letter Carrier's Rounds 模拟1877 Flooded! 数据结构->堆1879 Tempus et mobilius Time and motion 模拟+组合数学->Polya定理1882 Stamps 搜索+DP1883 Theseus and the Minotaur 模拟1887 Testing the CATCHER DP1889 Package Pricing DP1893 Monitoring Wheelchair Patients 模拟+几何1915 Knight Moves 搜索->BFS1916 Rat Attack 数据结构->?1936 All in All DP?1946 Cow Cycling DP1947 Rebuilding Roads 二分1985 Cow Marathon 图论->有向无环图的最长路1995 Raising Modulo Numbers 数论->大数的幂求余2049 Finding Nemo 图论->最短路2050 Searching the Web 模拟(需要高效实现)2051 Argus 送分题(最好用堆，不用也可以过)2054 Color a Tree 贪心2061 Pseudo-random Numbers 数论2080 Calendar 日期处理2082 Terrible Sets 分治/2083 Fractal 递归2084 Game of Connections 递推(不必高精度)2105 IP Address 送分题2115 C Looooops 数论->解模线性方程2136 Vertical Histogram 送分题2165 Gunman 计算几何2179 Inlay Cutters 枚举2181 Jumping Cows 递推2182 Lost Cows ->线段树/＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝1370 Gossiping (数论->模线性方程有无解的判断)+(图论->DFS)1090 Chain ->格雷码和二进制码的转换2182 Lost Cows ->线段树/2426 Remainder BFS1872 A Dicey Problem BFS1324 Holedox Moving BFS+压缩储存1088 滑雪DFS/DP1015 Jury Compromise DP1050 To the Max DP1062 昂贵的聘礼DP1065 Wooden Sticks DP1074 Parallel Expectations DP1093 Formatting Text DP1112 Team Them Up! DP1141 Brackets Sequence DP1157 LITTLE SHOP OF FLOWERS DP1160 Post Office DP1163 The Triangle DP1170 Shopping Offers DP1179 Polygon DP1180 Batch Scheduling DP1191 棋盘分割DP1293 Duty Free Shop DP2184 Cow Exhibition DP2193 Lenny's Lucky Lotto Lists DP2292 Optimal Keypad DP1432 Decoding Morse Sequences DP1475 Pushing Boxes DP1513 Scheduling Lectures DP1633 Gladiators DP1661 Help Jimmy DP1692 Crossed Matchings DP1712 Flying Stars DP1717 Dominoes DP1718 River Crossing DP1732 Phone numbers DP1745 Divisibility DP1771 Elevator Stopping Plan DP1776 T ask Sequences DP1874 Trade on Verweggistan DP1887 Testing the CATCHER DP1889 Package Pricing DP1946 Cow Cycling DP1187 陨石的秘密DP（BalkanOI99 Par的拓展）1485 Fast Food DP(似乎就是ioi2000的postoffice) 2385 Apple Catching DP(像NOI98“免费馅饼”) 1064 Cable master DP/二分查找1037 A decorative fence DP/组合数学1936 All in All DP?1505 Copying Books DP+二分查找1631 Bridging signals DP+二分查找1159 Palindrome DP->LCS1458 Common Subsequence DP->LCS1080 Human Gene Functions DP->LCS变形2192 Zipper DP->LCS变形1185 炮兵阵地DP->数据压缩2430 Lazy Cows DP->数据压缩1067 取石子游戏博弈论1082 Calendar Game 博弈论1085 Triangle War 博弈论1143 Number Game 博弈论2311 Cutting Game 博弈论2425 A Chess Game 博弈论1638 A number game 博弈论1694 An Old Stone Game 博弈论?1738 An old Stone Game 博弈论?1741 Tree 博弈论?2083 Fractal 递归1104 Robbery 递推1217 FOUR QUARTERS 递推1280 Game 递推2261 France '98 递推2181 Jumping Cows 递推1316 Self Numbers 递推同Humble Number一样2084 Game of Connections 递推(不必高精度) 1338 Ugly Numbers 递推(有O(n)算法)2247 Humble Numbers 递推(最优O(n)算法)1322 Chocolate 递推/组合数学1189 钉子和小球递推?1947 Rebuilding Roads 二分2418 Hardwood Species 二分查找2082 Terrible Sets 分治/1001 Exponentiation 高精度1047 Round and Round We Go 高精度1060 Modular multiplication of polynomials 高精度1131 Octal Fractions 高精度1202 Family 高精度2199 Rate of Return 高精度1646 Double Trouble 高精度1147 Binary codes 构造1148 Utopia Divided 构造2275 Flipping Pancake 构造1660 Princess FroG 构造1772 New Go Game 构造?1005 I Think I Need a Houseboat 几何1039 Pipe 几何1070 Deformed Wheel 几何1092 Farmland 几何1106 Transmitters 几何2194 Stacking Cylinders 几何2254 Globetrotter 几何2315 Football Game 几何2423 The Parallel Challenge Ballgame 几何1375 Intervals 几何1380 Equipment Box 几何1408 Fishnet 几何1514 Metal Cutting 几何1518 Problem Bee 几何1605 Horse Shoe Scoring 几何1654 Area 几何1693 Counting Rectangles 几何1774 Fold Paper Strips 几何1871 Bullet Hole 几何1875 Robot 几何1873 The Fortified Forest 几何+回溯1031 Fence 计算几何1034 The dog task 计算几何1271 Nice Milk 计算几何2284 That Nice Euler Circuit 计算几何1688 Dolphin Pool 计算几何2165 Gunman 计算几何1755 Triathlon 计算几何?1379 Run Away 计算几何->1113 Wall 计算几何->convex hull1434 Fill the Cisterns! 计算几何->离散化/1151 Atlantis 计算几何->同等安置矩形的并的面积->离散化1177 Picture 计算几何->同等安置矩形的并的周长->线段树2419 Forests 枚举2179 Inlay Cutters 枚举1025 Department 模拟1027 The Same Game 模拟1048 Follow My Logic 模拟1049 Microprocessor Simulation 模拟1073 The Willy Memorial Program 模拟1075 University Entrance Examination 模拟1098 Robots 模拟1103 Maze 模拟1120 A New Growth Industry 模拟1193 内存分配模拟1281 MANAGER 模拟2200 A Card Trick 模拟2314 POJ language 模拟1431 Calendar of Maya 模拟1483 Going in Circles on Alpha Centauri 模拟1512 Keeps Going and Going and ... 模拟1773 Outernet 模拟1876 The Letter Carrier's Rounds 模拟1883 Theseus and the Minotaur 模拟2050 Searching the Web 模拟(需要高效实现)1012 Joseph 模拟/数学方法1086 Unscrambling Images 模拟?1327 Moving Object Recognition 模拟?1893 Monitoring Wheelchair Patients 模拟+几何1462 Random Walk 模拟+解线性方程组2379 ACM Rank T able 模拟+排序1879 Tempus et mobilius Time and motion 模拟+组合数学->Polya定理1520 Scramble Sort 排序1634 Who's the boss? 排序2299 Ultra-QuickSort 排序->归并排序1008 Maya Calendar 日期处理1209 Calendar 日期处理2210 Metric Time 日期处理1430 Binary Stirling Numbers 日期处理1447 Ambiguous Dates 日期处理2080 Calendar 日期处理2351 Time Zones 时间处理1770 Special Experiment 树形DP1916 Rat Attack 数据结构->?1197 Depot 数据结构->Young T ableau1182 食物链数据结构->并查集2424 Flo's Restaurant 数据结构->堆1877 Flooded! 数据结构->堆1445 Random number 数据结构->碓1023 The Fun Number System 数论1061 青蛙的约会数论1091 跳蚤数论1152 An Easy Problem! 数论2191 Mersenne Composite Numbers 数论2381 Random Gap 数论2417 Discrete Logging 数论1510 Hares and Foxes 数论1641 Rational Approximation 数论1730 Perfect Pth Powers 数论1777 Vivian's Problem 数论2061 Pseudo-random Numbers 数论1014 Dividing 数论/DP?/组合数学->母函数?1606 Jugs 数论/搜索1995 Raising Modulo Numbers 数论->大数的幂求余2115 C Looooops 数论->解模线性方程1288 Sly Number 数论->解模线性方程组1395 Cog-Wheels 数学->解正系数的线性方程组1000 A+B Problem 送分题1003 Hangover 送分题1004 Financial Management 送分题1006 Biorhythms 送分题1007 DNA Sorting 送分题1016 Numbers That Count 送分题1019 Number Sequence 送分题1028 Web Navigation 送分题1046 Color Me Less 送分题1053 Set Me 送分题1068 Parencodings 送分题1071 Illusive Chase 送分题1096 Space Station Shielding 送分题1099 Square Ice 送分题1102 LC-Display 送分题1107 W's Cipher 送分题1119 Start Up the Startup 送分题1218 THE DRUNK JAILER 送分题1245 Programmer, Rank Thyself 送分题1247 Magnificent Meatballs 送分题1250 T anning Salon 送分题1298 The Hardest Problem Ever 送分题1326 Mileage Bank 送分题2190 ISBN 送分题2196 Specialized Four-Digit Numbers 送分题2291 Rotten Ropes 送分题2304 Combination Lock 送分题2309 BST 送分题2390 Bank Interest 送分题2403 Hay Points 送分题1411 Calling Extraterrestrial Intelligence Again 送分题1481 The Die Is Cast 送分题1484 Blowing Fuses 送分题1517 u Calculate e 送分题1547 Clay Bully 送分题1563 The Snail 送分题1604 Just the Facts 送分题1657 Distance on Chessboard 送分题1658 Eva's Problem 送分题1663 Number Steps 送分题1677 Girls' Day 送分题1690 (Your)((Term)((Project))) 送分题1775 Sum of Factorials 送分题1870 Bee Breeding 送分题2105 IP Address 送分题2136 Vertical Histogram 送分题1555 Polynomial Showdown 送分题(非常阴险) 2388 Who's in the Middle 送分题(排序)1519 Digital Roots 送分题(位数可能很大)1045 Bode Plot 送分题(用物理知识)2051 Argus 送分题(最好用堆，不用也可以过) 1011 Sticks 搜索1020 Anniversary Cake 搜索1054 The Troublesome Frog 搜索1069 The Bermuda Triangle 搜索1072 Puzzle Out 搜索1100 Dreisam Equations 搜索1110 Double Vision 搜索1111 Image Perimeters 搜索1128 Frame Stacking 搜索1142 Smith Numbers 搜索1162 Building with Blocks 搜索1183 反正切函数的应用搜索1184 聪明的打字员搜索1248 Safecracker 搜索1601 Pizza Anyone? 搜索1713 Divide et unita 搜索1129 Channel Allocation 搜索（图的最大独立集）1190 生日蛋糕搜索/DP1691 Painting A Board 搜索/DP1714 The Cave 搜索/DP1084 Square Destroyer 搜索？1010 STAMPS 搜索＋DP1194 HIDDEN CODES 搜索+DP1882 Stamps 搜索+DP1101 The Game 搜索->BFS1137 The New Villa 搜索->BFS1233 Street Crossing 搜索->BFS2243 Knight Moves 搜索->BFS2312 Battle City 搜索->BFS1476 Always On the Run 搜索->BFS1480 Optimal Programs 搜索->BFS1482 It's not a Bug, It's a Feature! 搜索->BFS 1753 Flip Game 搜索->BFS1915 Knight Moves 搜索->BFS1017 Packets 贪心1018 Communication System 贪心1323 Game Prediction 贪心1463 Strategic game 贪心1469 COURSES 贪心1719 Shooting Contest 贪心2054 Color a Tree 贪心1328 Radar Installation 贪心（差分约束系统的特例）1042 Gone Fishing 贪心/DP1752 Advertisement 贪心/图论->差分约束系统1201 Intervals 贪心/图论->最长路->差分约束系统1097 Roads Scholar 图论1161 Walls 图论1450 Gridland 图论(本来TSP问题是NP难的，但这个图比较特殊，由现成的构造方法)2197 Jill's Tour Paths 图论->2416 Return of the Jedi 图论->1639 Picnic Planning 图论->1695 Magazine Delivery 图论->1729 Jack and Jill 图论->1751 Highways 图论->1122 FDNY to the Rescue! 图论->Dijkstra1125 Stockbroker Grapevine 图论->Dijkstra1135 Domino Effect 图论->Dijkstra1394 Railroad 图论->Dijkstra1158 TRAFFIC LIGHTS 图论->Dijkstra变形2395 Out of Hay 图论->Dijkstra变形2253 Frogger 图论->Dijkstra变形(和1295是一样的)1734 Sightseeing trip 图论->Euler回路1466 Girls and Boys 图论->n/a1515 Street Directions 图论->把一个无向连通图改造成为有向强连通图1635 Subway tree systems 图论->不同表示法的二叉树判同1275 Cashier Employment 图论->差分约束系统->无负权回路的有向图的最长路->Bellman-Ford1274 The Perfect Stall 图论->二分图的最大匹配1325 Machine Schedule 图论->二分图的最大匹配2239 Selecting Courses 图论->二分图的最大匹配2195 Going Home 图论->二分图的最大权匹配2400 Supervisor, Supervisee 图论->二分图的最大权匹配?1637 Sightseeing tour 图论->欧拉回路1383 Labyrinth 图论->树的最长路1094 Sorting It All Out 图论->拓扑排序1486 Sorting Slides 图论->拓扑排序1149 PIGS 图论->网络流2289 Jamie's Contact Groups 图论->网络流?1192 最优连通子集图论->无负权回路的有向图的最长路->BellmanFord 1364 King 图论->无负权回路的有向图的最长路->BellmanFord1985 Cow Marathon 图论->有向无环图的最长路1087 A Plug for UNIX 图论->最大流1273 Drainage Ditches 图论->最大流1459 Power Network 图论->最大流1632 Vase collection 图论->最大完全图2049 Finding Nemo 图论->最短路1251 Jungle Roads 图论->最小生成树2421 Constructing Roads 图论->最小生成树1026 Cipher 组合数学1095 Trees Made to Order 组合数学2346 Lucky tickets 组合数学1286 Necklace of Beads 组合数学->Polya定理2409 Let it Bead 组合数学->Polya定理1664 放苹果组合数学->递推。
《人工智能》课程习题第一章绪论1-1. 什么是人工智能？试从学科和能力两方面加以说明。
1-2. 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？1-3. 为什么能够用机器（计算机）模仿人的智能？1-4. 现在人工智能有哪些学派？它们的认知观是什么？1-5. 你认为应从哪些层次对认知行为进行研究？1-6. 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？第二章知识表示方法2-1状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么？它们有何本质上的联系及异同点?2-2设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。
该船的负载能力为两人。
在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。
他们怎样才能用这条船安全地把所有人都渡过河去?再定义描述过河方案的谓词：L-R(x, x1, y, y1,S)：x1个修道士和y1个野人渡船从河的左岸到河的右岸条件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)动作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’)R-L (x, x1, y, y1,S)：x2个修道士和y2个野人渡船从河的左岸到河的右岸条件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S)动作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)(2) 过河方案Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)L-R(3, 1, 3, 1,S0) L-R(3, 0, 3, 2,S0)Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’)R-L (2, 1, 2, 0,S1) R-L (3,0, 1, 1,S1’)Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2)L-R(3, 0, 2, 2,S2)Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3)R-L (3, 0, 0, 1,S3)Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4)L-R(3, 2, 1, 0,S4)Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5)R-L (1, 1, 1, 1,S5)Safety(L,2,2,S6)∧Safety(R,1,1,S6)∧Boat(L,S6)L-R(2, 2, 2, 0,S6)Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7)R-L (0, 0, 2, 1,S7)Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8)L-R(0, 0, 3, 2,S8)Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9)R-L (0, 1, 1, 0,S9)Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10)2-3利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。
第7章 图论图论是建立和处理离散型数学模型的重要数学工具，它已发展成具有广泛应用的一个数学分支。
图论的发展已有200多年的历史，它最早起源于一些数学游戏的难题研究。
1736年瑞士数学家欧拉（L.Eluer ）发表了关于解决哥尼斯堡七桥问题的一篇文章，标志着图论的正式诞生。
从19世纪中叶到20世纪中叶，图论问题大量出现，如汉密尔顿图问题、四色猜想等。
这些问题的出现进一步促进了图论的发展。
1847年，克希霍夫（Kirchhoff ）用图论分析电网络，这是图论最早应用于工程科学的一个例子。
随着计算机科学的迅猛发展，在现实生活中的许多问题，如交通网络问题，运输的优化问题，社会学中某类关系的研究，都可以用图论进行研究和处理。
图论在计算机领域中，诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有重大贡献。
本章主要介绍图论的基本概念、基本性质和一些典型应用。
7.1 图的基本概念7.1.1 图的基本概念1.图的定义图在现实生活中随处可见，如交通运输图、旅游图、流程图等。
此处我们只考虑由点和线所组成的图。
这种图能够描述现实世界的很多事情。
例如，用点表示球队，两队之间的连线代表二者之间进行比赛，这样，各支球队的比赛情况就可以用一个图清楚地表示出来。
到底什么是图呢？可用一句话概括：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。
因为上述描述太过于抽象，难于理解，因此下面给出图作为代数结构的一个定义。
定义7.1.1 一个图（Graph ）是一个三元组〈)(G V ，)(G E ，G ϕ〉，其中)(G V 是一个非空的节点集合，)(G E 是有限的边集合，G ϕ是从边集合E 到点集合V 中的有序偶或无序偶的映射。
例7.1.1 图G =〈)(G V ，)(G E ，G ϕ〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，),()(1b a e G =ϕ，),()(2c a e G =ϕ，),()(3d b e G =ϕ，),()(4c b e G =ϕ，),()(5c d e G =ϕ，),()(6d a e G =ϕ。
学科代码学科名称A数理科学B化学科学C生命科学D地球科学E工程与材料科学F信息科学G管理科学A01数学A0101基础数学A010101数论A01010101解析数论A01010102代数数论A01010103丢番图分析A01010104超越数论A01010105模型式与模函数论A01010106数论的应用A010102代数学A01010201群论A01010202群表示论A01010203李群A01010204李代数A01010205代数群A01010206典型群A01010207同调代数A01010208代数K理论A01010209Kac-Moody代数A01010210环论A01010211代数(可除代数)A01010212体A01010213编码理论与方法A01010214序结构研究A010103几何学A01010301整体微分几何A01010302代数几何A01010303流形上的分析A01010304黎曼流形与洛仑兹流形A01010305齐性空间与对称空间A01010306调和映照及其在理论物理中的应用A01010307子流形理论A01010308杨--米尔斯场与纤维丛理论A01010309辛流形A010104拓扑学A01010401微分拓扑A01010402代数拓扑A01010403低维流形A01010404同伦论A01010405奇点与突变理论A01010406点集拓扑A010105函数论A01010501多复变函数论A01010502复流形A01010503复动力系统A01010504单复变函数论A01010505Rn中的调和分析的实方法A01010506非紧半单李群的调和分析A01010507函数逼近论A010106泛函分析A01010601非线性泛函分析A01010602算子理论A01010603算子代数A01010604泛函方程A01010605空间理论A01010606广义函数A010107常微分方程A01010701泛函微分方程A01010702特征与谱理论及其反问题A01010703定性理论A01010704稳定性理论、分支理论A01010705混沌理论A01010706奇摄动理论A01010707复域中的微分方程A01010708动力系统A010108偏微分方程A01010801连续介质物理与力学、及反应扩散等应用领域中A01010802几何与数学物理中的偏微分方程A01010803微局部分析与一般偏微分算子理论A01010804非线性椭圆（和抛物）方程研究中的新方法和新A01010805混合型及其它带奇性的方程A01010806非线性波、非线性发展方程和无穷维动力系统A010109数学物理A01010901规范场论A01010902引力场论的经典理论与量子理论A01010903孤立子理论A01010904统计力学A01010905连续介质力学等方面的数学问题A010110概率论A01011001马氏过程A01011002随机过程A01011003随机分析A01011004随机场A01011005鞅论A01011006极限理论A01011007概率论在调和分析、几何及微分方程等方面的应A01011008在物理、生物、化学管理中的概率论问题A01011009平稳过程A010111数理逻辑与数学基础A01011101递归论A01011102模型论A01011103证明论A01011104公理集合证A01011105数理逻辑在人工智能及计算机科学中的应用A0102应用数学A010201数理统计A01020101抽样调查与抽样方法A01020102试验设计A01020103时间序列分析及其算法研究A01020104多元分析及其算法研究A01020105数据分析及其图形处理A01020106非参数统计方法A01020107应用统计中的基础性工作A01020108统计线性模型A01020109参数估计方法A01020110随机过程的统计理论及方法A01020111蒙特卡洛方法 (统计模拟方法) A010202运筹学A01020201线性与非线性规划A01020202整数规划A01020203动态规划A01020204组合最优化A01020205随机服务系统A01020206对策论A01020207不动点算法A01020208随机最优化A01020209多目标规划A01020210不可微最优化A01020211可靠性理论A010203控制论A01020301有限维非线性系统A01020302分布参数系统的控制理论A01020303随机系统的控制理论A01020304最优控制理论与算法A01020305参数辨识与适应控制A01020306线性系统理论的代数与几何方法A01020307控制的计算方法A01020308微分对策理论A01020309稳健控制A010204若干交叉学科A01020401信息论及应用A01020402经济数学A01020403生物数学A01020404不确定性的数学理论A01020405分形论及应用A010205计算机的数学基础A01020501可解性与可计算性A01020502机器证明A01020503计算复杂性A01020504VLSI的数学基础A01020505计算机网络与并行计算A010206组合数学A01020601组合计数A01020602组合设计A01020603图论A01020604线性计算几何A01020605组合概率方法A0103计算数学与科学工程计算A010301偏微分方程数值计算A01030101初边值问题数值解法及应用A01030102非线性微分方程及其数值解法A01030103边值问题数值解法及其应用A01030104有限元、边界元数值方法A01030105变分不等式的数值方法A01030106辛几何差分方法A01030107数理方程反问题的数值解法A010302常微分方程数值解法及其应用A01030201二点边值问题A01030202STIFF 问题研究A01030203奇异性问题A01030204代数微分方程A010303数值代数A01030301大型稀疏矩阵求解A01030302代数特征值问题及其反问题A01030303非线性代数方程A01030304一般线性代数方程组求解A01030305快速算法A010304函数逼近A01030401多元样条A01030402多元逼近A01030403曲面拟合A01030404有理逼近A01030405散乱数据插值A010305计算几何A01030501曲面造型A01030502曲面光滑拼接A01030503曲面设计A01030504体素拼接A01030505几何问题的计算机实现A010306新型算法A01030601并行算法A01030602多重网格技术A01030603自适应方法A01030604区间分析法及其应用A02力学A0201一般力学A020101分析力学A020102动力系统的分岔、混沌A020103运动稳定性与控制A020104非线性振动与控制A020105多体动力学A020106转子动力学A020107弹道力学和飞行力学A020108理性力学A020109力学中的反问题A020110力学发展史学A0202固体力学A020201弹性力学与塑性力学A020202疲劳与断裂力学A020203损伤、破坏机理和微结构演化A020204本构关系A020205复合材料力学A020206新型材料的力学问题A020207极端条件下的材料和结构A020208微机电系统中的固体力学问题A020209岩体力学和土力学A020210冲击动力学A020211结构力学A020212结构振动与噪声A020213结构优化和可靠性分析A020214制造工艺力学A020215实验固体力学A020216计算固体力学A020217流固耦合作用A0203流体力学A020301流动的稳定性A020302湍流A020303水动力学A020304空气动力学A020305分层流A020306非平衡流A020307渗流A020308多相流A020309非牛顿流A020310内流A020311化工流体力学A020312工业空气动力学A020313微重力流体力学A020314微机电系统中的流体力学问题A020315流动噪声与控制A020316稀薄气体力学A020317实验流体力学A020318计算流体力学A0204交叉与边缘领域的力学A020401物理力学A020402爆炸力学A020403环境流体力学A020404生物力学A020405电磁流体力学和等离子体动力学A03天文学A0301宇宙学A0302星系和类星体A0303恒星物理与星际物质A0304太阳和太阳系A0305射电天文A0306空间天文A0307理论天体物理A0308天体测量和天文地球动力学A0309天体力学和人造卫星动力学A0310时间、频率A0311天文仪器A0312天文学史A0313其它A04物理学(Ⅰ)A0401凝聚态物性Ｉ：结构、力学和热学性质A040101液体和固体结构；晶体、非晶、准晶的物质结构A040102凝聚态物质的力学和声学性质A040103晶格动力学和晶体统计学A040104状态方程、相平衡和相变A040105凝聚态物质的热学性质A040106凝聚态物质的输运性质A040107量子流体和固体;液态氦和固态氦A040108表面和界面;薄膜和晶须；人工微结构（结构和 A0402凝聚态物性Ⅱ：电子结构、电学、磁学和光学性A040201电子态A040202凝聚态物质中的电子输运A040203表面.界面.薄膜和低维系统的电子结构及电学性A040204超导电性A040205磁学性质A040206凝聚态物质的磁共振和弛豫;穆斯堡尔效应A040207介电性质A040208光学性质、凝聚态物质的波谱学、物质与粒子的A040209液体和固体的电子发射和离子发射;碰撞现象A040210与凝聚态物理有关的交叉学科A0403原子和分子物理A040301原子和分子理论A040302原子光谱及原子与光子相互作用A040303分子光谱及分子与光子相互作用A040304原子和分子碰撞过程及相互作用A040305研究原子和分子性质的实验设备和技术A040306特殊原子和分子的研究A040307与原子、分子有关的其它物理问题和交叉学科A0404光学A040401光在均匀介质中的传播A040402光在非均匀介质中的传播A040403像的形成和分析A040404全息照相A040405量子光学A040406微波激射A040407激光发射过程A040408激光系统和激光与物质相互作用A040409非线性光学A040410光学材料中物理问题及固体发光A040411光源和光学标准A040412光学透镜和反射镜系统A040413光学器件的原理A040414与光学有关的其它物理问题和交叉学科A0405声学A040501普通线性声学A040502非线性声学和强声学A040503航空声学和大气声学A040504水声A040505超声、量子声学和声的物理效应A040506次声A040507噪声、噪声效应及其控制A040508建筑声学A040509声的信号处理A040510声全息照相A040511语言声学A040512乐声A040513声的测量及专用仪器A040514声的转换原理A040515与声学有关的其它物理问题和交叉学科A05物理学(Ⅱ)A0501基础物理学A050101物理教育学及物理学史A050102物理学中的数学问题A050103经典物理学和量子理论A050104相对论与引力A050105热力学与统计物理学 (含混沌)A050106测量科学、一般实验技术和测试系统A0502粒子物理学和场论A050201粒子基本特性及粒子物理一般问题A050202场论中的基本问题和新方法A050203对称性及对称破缺A050204量子色动力学、强相互作用和强子物理A050205电－弱相互作用及其唯象学A050206非标准模型及其唯象学A050207新粒子A050208粒子的延展体理论A050209宇宙射线和超高能现象A050210粒子物理与宇宙学A0503核物理A050301原子核特性A050302原子核结构模型的理论研究A050303原子核统计理论研究A050304原子核高激发态、高自旋态和超形变A050305带奇异数系统、奇异核和超核A050306核内非核子自由度A050307核力与少体系统A050308强子、轻子与核相互作用A050309核物质理论及核多体方法A050310核衰变、核裂变、核聚变A050311低能核反应与散射A050312重离子核物理A050313中高能核物理A050314核天体物理A050315核数据分析和计算机模拟A0504核技术及其应用A050401离子束与物质相作用和辐照损伤A050402核分析技术 ( RBS、PIXE、NRA )A050403穆斯堡尔谱学及其应用A050404正电子湮灭技术及其应用A050405中子衍射及其应用A050406扰动角关联及其应用A050407核磁共振及其应用A050408中子活化和同位素示踪技术A050409离子束材料改性A050410核技术在地学中的应用A050411核技术在医学中的应用A050412核技术在农业中的应用A050413核技术在工业中的应用A050414核科学和其它学科的交叉A0505粒子物理与核物理实验设备A050501加速器原理和关键技术A050502离子源和电子枪A050503预加速装置和加速器部件A050504束流输运和性能测量A050505真空和超高真空技术A050506反应堆A050507辐射探测方法A050508探测技术和谱仪A050509辐射剂量及其防护A050510核电子学A0506等离子体物理A050601等离子体中的基本过程与特性A050602等离子体的加热、约束和辐射A050603等离子体动力学与电磁流体力学A050604等离子体中的混沌、孤立波、湍流等非线性现象A050605等离子体的模拟、数值方法和软件A050607等离子体诊断技术A050608等离子体与固体相互作用A050609激光束、粒子束、微波与等离子体A050610低气压低温等离子体的应用A050611热平衡低温等离子体的应用A050612非中性等离子体A050613强耦合等离子体A050614空间等离子体B01无机化学B0101无机合成和制备化学B010101合成技术B010102合成化学B010103特殊聚集态制备B0102丰产元素化学B010201稀土化学B010202钨化学B010203钼化学B010204锡化学B010205锑化学B010206钛化学B010207钒化学B010208稀有碱金属化学B010209稀散元素化学B0103配位化学B010301固体配位化学B010302溶液配位化学B010303金属有机化学B010304原子簇化学B010305功能配合物化学B0104生物无机化学B010401金属酶化学及其化学模拟B010402金属蛋白化学及其化学模拟B010403生物体内微量元素的状态及功能、受体底物相互B010404金属离子与生物膜的作用及其机理B010405金属离子与核酸化学B0105固体无机化学B010501缺陷化学B010502固体反应B010503固体表面化学B010504无机固体材料化学B0106分离化学B010601萃取化学B010602无机色层B010603无机膜分离B0107物理无机化学B010701无机化合物结构与性质B010702理论无机化学B010703无机反应机制及反应动力学B010704熔盐化学及相平衡B0108同位素化学B010801同位素分离B010802同位素分析B010803同位素应用B0109放射化学B010901核燃料化学B010902超铀元素化学B010903裂片元素化学B010904放射性核素及其标记化合物的制备和应用B010905放射分析化学B010906放射性废物处理和综合利用B0110核化学B011001低能核化学B011002高能核化学B011003裂变化学B011004重离子核化学B011005核天体化学B02有机化学B0201有机合成B020101有机合成反应B020102新化合物和复杂化合物的设计与合成B020103高选择性有机合成试剂B020104不对称合成B0202金属有机及元素有机化学B020201有机磷化学B020202有机硅化学B020203有机硼化学B020204有机氟化学B020205金属有机化合物的合成及其应用B0203天然有机化学B020301甾体及萜类化学B020302糖类黄酮类化学B020303中草药有效成份B020304具有重要应用价值的天然产物的研究B0204物理有机化学B020401活泼中间体化学B020402化学动态学B020403有机光化学B020404立体化学B020405有机分子结构与活性关系B020406具有光、电、磁特性的化合物研究B020407计算有机化学B0205药物化学B020501新药物分子设计和合成B020502药物构效关系B0206生物有机化学B020601多肽化学B020602核酸化学B020603仿生及模拟酶B020604天然酶的化学修饰及应用B020605生物合成及生物转化B0207有机分析B020701新化合物和复杂化合物的结构研究B020702有机分析、分离新方法新技术研究B020703有机化合物结构波谱学B0208应用有机化学B020801除草剂B020802植物生长促进剂B020803害虫引诱剂、昆虫信息素B020804高效、低毒、低抗性农药B020805食品化学B020806香料化学B020807染料化学B03物理化学B0301结构化学B030101体相静态结构B030102表面结构B030103溶液结构B030104动态结构B030105谱学B030106结构化学方法和理论B0302量子化学B030201基础量子化学B030202应用量子化学B0303催化B030301多相催化B030302均相催化B030303人工酶催化B030304光催化B0304化学动力学B030401宏观反应动力学B030402分子动态学B030403反应途径和过渡态B030404快速反应动力学B030405结晶过程动力学B0305胶体与界面化学B030501表面活性剂B030502分散体系B030503流变性能B030504界面吸附现象B030505超细粉和颗粒B0306电化学B030601电极过程及其动力学B030602腐蚀电化学B030603熔盐电化学B030604光电化学B030605半导体电化学B030606生物电化学B030607表面电化学B030608电化学技术B030609电催化B0307光化学B030701激光闪光光解B030702激发态化学B030703电子转移光化学、光敏化B030704光合作用B030705大气光化学B0308热化学B030801热力学参数B030802相平衡B030803电解质溶液化学B030804非电解质溶液化学B030805生物热化学B030806量热学B0309高能化学B030901辐射化学B030902等离子体化学B030903激光化学B0310计算化学B031001化学信息的运筹B031002计算模拟B031003计算控制B031004计算方法的最优化B04高分子科学B0401高分子合成B040101催化剂、聚合反应及聚合方法B040102高分子设计和合成B040103新单体及单体的新合成方法B040104聚合反应动力学B040105高分子光化学、辐射化学、等离子体化学B040106微生物参与的聚合反应、酶催化聚合反应B0402高分子反应B040201高分子老化、降解、交联B040202高分子接枝、嵌段改性B040203高分子功能化改性B040204粒子注入、辐射、激光等方法对高分子的改性B0403功能高分子B040301吸附、分离、离子交换、螯合功能的高分子B040302用于有机合成、医疗、分析等领域的高分子试剂B040303医用高分子、高分子药物B040304液晶态高分子B040305有机固体电子材料、磁性高分子B040306储能、换能、敏感材料及高分子催化剂B040307高分子功能膜B040308微电子材料、分子组装材料及器件B0404天然高分子B0405高分子物理及高分子物理化学B040501高分子溶液性质和溶液热力学B040502高分子链结构B040503高分子流变学B040504高聚物聚集态结构B040505高分子结构与性能关系B040506高聚物测试及表征方法B040507高分子材料的传质理论、强度理论、破坏机理B040508高分子多相体系B0406高分子理论化学B040601高分子聚合、交联、聚集态统计理论B040602数学、计算机方法在高分子凝聚态、分子动态学B0407聚合物工程及材料B040701聚合工程反应动力学及聚合反应控制B040702聚合物成型理论及成型方法B040703塑料、纤维、橡胶及成型研究B040704涂料、粘合剂及高分子肋剂B040705可生物降解薄膜B040706高分子润滑材料B040707其它领域中应用的高分子材料B040708高分子资源的再生和综合利用B05分析化学B0501色谱分析B050101气相色谱B050102液相色谱B050103薄层色谱B050104离子色谱B050105超临界液体色谱B050106毛细管电泳B0502电化学分析B050201伏安法B050202极谱法B050203化学修饰电极B050204库伦分析B050205光谱电化学分析B050206电化学传感器B0503光谱分析B050301原子发射光谱（包括ICP）B050302原子吸收光谱B050303原子荧光光谱B050304X射线荧光光谱B050305分子发射光谱（包括荧光光谱、磷光光谱和化学B050306紫外和可见光谱B050307光声光谱B050308红外光谱B050309拉曼光谱B0504波谱分析B050401顺磁B050402核磁B0505质谱分析B050501有机质谱B050502无机质谱B0506化学分析B050601萃取剂、显色剂、特殊功能试剂B050602色谱柱固定相、分离膜B0507热分析B0508放射分析B050801活化分析B050802质子荧光B0509生化分析及生物传感B0510联用技术B0511采样、分离和富集方法B0512化学计量学B051201分析方法与计算机技术B051202分析讯号与数据解析B0513表面、微区、形态分析B051301表面分析B051302微区分析B051303形态分析B06化学工程及工业化学B0601化工热力学和基础数据B060101状态方程与溶液理论B060102相平衡B060103热化学B060104化学平衡B060105热力学理论模型和分子系统的计算机模拟B060106热力学数据和数据库B0602传递过程B060201化工流体力学和传递性质B060202传热过程及设备B060203传质过程B060204流变学B060205颗粒学及浆料化学B0603分离过程及设备B060301蒸馏B060302蒸发与结晶B060303干燥B060304吸收B060305萃取B060306吸附与离子交换B060307机械分离过程B060308膜分离B060309其他分离技术B0604化学反应工程B060401化学(催化)反应动力学B060402反应器原理及传递特性B060403反应器的模型化和优化B060404流态化技术和多相流反应工程B060405固定床反应工程B060406聚合反应工程B060407电化学反应工程B060408生化反应工程B060409催化剂工程B0605化工系统工程B060501化学过程的控制与模拟B060502化工系统的优化B060503化工过程动态学B0606无机化工B060601常规无机化工B060602工业电化学(电解、电镀、化学腐蚀与防腐)B060603精细无机(无机颜料、吸附剂及表面活性剂等) B060604核化工与放射化工B0607有机化工B060701工业有机化工B060702精细有机化工（染料、涂料、感光剂、粘合剂与B0608生物化工与食品化工B060801生化反应动力学及反应器B060802发酵物的提取和纯化B060803生化过程的化工模拟及人工器官B060804酶化工B060805天然产物和农副产品的化学改性及深度加工B060806生物医药工程B0609能源化工B060901煤化工B060902石油化工B060903燃料电池B060904其它能源化工B0610化工冶金B061001矿产资源的利用研究B061002化学选矿与浸出B061003湿法冶金物理化学B061004等离子体冶金B061005化学涂层B0611环境化工B061101环境治理中的物理化学原理B061102三废治理技术中的化工基础B061103环境友好的化工过程B061104可持续发展环境化工的新概念B07环境化学B0701环境分析化学B070101环境中微量生命元素及其化合物的分离、分析技B070102环境中微量有机污染物的分离、分析技术B0702环境污染化学B070201大气污染化学B070202水污染化学B070203土壤污染化学B070204固体废弃物及放射性核素污染化学B0703污染控制化学B070301化学控制、防治新工艺、新技术及其基础性研究B070302无害化工艺(原料、能源和资源的综合利用)B0704污染生态化学B0705理论环境化学B0706全球性环境化学问题C01基础生物学C0101微生物学C010101微生物分类学C01010101细菌分类C01010102放线菌分类C01010103真菌分类C010102微生物生理及生物化学C010103微生物遗传育种C010104微生物方法学C010105微生物资源与生态C010106应用微生物学基础C01010601工业微生物C01010602农业、土壤微生物C010107病毒学C01010701动物病毒C01010702植物病毒C01010703微生物病毒C010108医学与兽医微生物学C01010801病毒C01010802立克次氏体(含衣原体)C01010803病原细菌(含支原体与螺旋体)C01010804病原真菌C0102植物学C010201植物结构学C01020101植物形态解剖学C01020102植物形态发生C01020103植物胚胎学C010202植物系统学与分类学C01020201植物系统发育与演化C01020202种子植物分类C01020203孢子植物分类C01020204植物区系与地理学C010203植物生理学C01020301光合作用及固氮C01020302呼吸作用、采后生理及次生物质代谢C01020303矿质营养及有机物质运输C01020304水分生理及抗性生理C01020305植物激素、生长发育及生殖生理C010204植物资源学C01020401植物资源评价C01020402植物引种驯化C01020403植物种质保存C01020404资源植物化学C0103动物学C010301动物形态学C010302动物胚胎学C010303动物分类学C010304动物生理学C010305动物行为学C010306动物进化和动物遗传学C010307动物地理学C010309保护生物学C010310实验动物学C0104生物化学和分子生物学C010401生物分子的结构与功能、合成机理及调节过程C01040101蛋白质与肽C01040102核酸C01040103酶C01040104多糖及糖复合物C01040105激素C01040106天然产物化学C010402生物膜的结构与功能C010403无机生物化学C0105生物物理学与生物医学工程学C010501理论生物物理C01050101量子生物学C01050102生物信息论和生物控制论C01050103生物功能的计算机模拟、生物数学C01050104生命现象的生物物理理论阐述C010502环境生物物理C01050201电离辐射生物物理C01050202光生物物理C01050203电磁辐射生物物理C01050204声生物物理C01050205其它环境因素对生物的作用C01050206自由基生物学C010503生物组织的物理特性C01050301生物光学C01050302生物电磁学C01050303生物声学C01050304生物力学和生物流变学C01050305生物组织的其它物理特性C010504分子生物物理C01050401生物分子结构的运动性C01050402生物分子的相互作用C01050403生物分子中的能量传递与电子传递C010505膜与细胞生物物理C010506感官与神经生物物理C010507生物物理技术C010508生物物理学研究中的新概念和新方法C010509人工器官C010510生物医学信号处理C010511生物医学测量技术C010512生物系统的建模与应用C010513生物医学超声C010514生物医学传感技术C010515生物材料C010516生物医学图象C010517其它生物医学工程学研究C0106神经生物学C010601分子神经生物学C010602细胞神经生物学C010603系统神经生物学C010604高级神经生物学C010605比较神经生物学C010606发育神经生物学C010607感觉系统神经生物学C0107生理学C010701循环生理学C010702血液生理学C010703呼吸生理学C010704消化生理学C010705泌尿生理学C010706内分泌生理学C010707特殊环境生理学C010708生殖生理学C010709年龄生理学C0108心理学C010801心理学的基本过程研究C010802认知心理学C010803生物心理学C010804医学心理学(含精神卫生学)C010805工程心理学C010806发展与教育心理学C010807运动心理学C0109细胞生物学及发育生物学C010901细胞结构与功能C010902细胞增长、分裂与分化C010903模型动植物及实验体系的建立C010904细胞工程(生物技术和细胞培养) C010905细胞代谢C010907细胞信息C010908胚的成因、形态及其形成C010909细胞间的作用、演变和再生C0110遗传学C011001植物遗传学C011002动物遗传学C011003微生物遗传学C011004人类遗传学C011005医学遗传学及遗传病C011006细胞遗传学C011007分子遗传学C011008基因工程C0111生态学C011101生态学一般理论和方法C011102个体生态学及生理生态学C011103种群生态学C011104群落与系统生态学C011105行为生态学与进化生态学C011106景观生态学与地理生态学C011107毒理生态学C011108保育生态学及恢复生态学C011109生态管理学与农业生态学C011110其它生态学及环境问题C02农业科学C0201农业基础科学C020101农业数学C020102农业物理学C020103农业气象学C020104农业化学C020105肥料学C020106农业系统管理工程C0202农学C020201作物栽培学C020202作物营养学C020203作物生理学C020204作物品种资源学C020205作物遗传育种学C02020501稻类遗传育种学C02020502麦类遗传育种学C02020503其它禾谷类作物遗传育种学C02020504油料作物遗传育种学C02020505薯类作物遗传育种学C02020506棉麻作物遗传育种学C02020507饲料作物遗传育种学C02020508糖料作物遗传育种学C02020509热带、亚热带作物遗传育种学C02020510其它经济作物遗传育种学C02020511作物遗传育种新方法C02020512作物种子学C020206植物保护学C02020601病虫测报学C02020602作物真菌病害C02020603作物细菌病害C02020604作物病毒病害C02020605作物其它病害C02020606作物虫害C02020607杂草、鼠害防治C02020608化学保护(抗药性)C02020609作物病虫害检疫学C020207植病生防C020208害虫生防C020209抗病、抗虫作物选育C020210园艺学C02021001蔬菜学C02021002瓜果学C02021003果树学C02021004食用真菌学C02021005果蔬保鲜加工中的生物学问题C02021006观赏园艺学C0203畜牧、兽医学C020301普通畜牧学C02030101畜牧学基础理论C02030102草原学C02030103遗传育种学C02030104繁殖学C02030105畜禽组织与解剖学C02030106畜禽行为学C020302畜禽营养学C020303饲料资源学C020304畜禽生理学C020305畜禽环境工程学C020306兽医学C02030601兽医学基础理论C02030602中兽医学C02030603兽医临床医学基础C02030604兽医传染病学C02030605兽医寄生虫病学C02030606畜禽病理学C02030607诊断学基础C02030608兽医药理学C020307野生经济饲养动物学C0204蚕桑、养蜂学C020401养蚕学C020402养蜂学C0205水产学C020501水产基础科学C020502水产资源学C020503水产保护学C020504水产养殖学C020505水生经济生物遗传育种学C020506水产生物学C020507水生经济动物营养学C020508水产品加工与保鲜基础理论C0206林学C020601森林基础科学C02060101森林数学C02060102木材物理学C02060103森林化学C02060104森林气象学C02060105树木生理学C02060106森林土壤学C020602森林培育学C02060201造林学C02060202种苗学C02060203森林经理学C020603森林保护学C02060301森林病理学C02060302森林昆虫学C02060303森林防火学C02060304防护林学C020604林木遗传育种学C02060401林木遗传学C02060402林木育种学C020605经济林学C020606复合农林业C020607园林学C020608森林资源学C020609荒漠化及其防治C03医学与药学C0301预防医学与卫生学C030101环境卫生学(含环境医学和卫生工程学) C03010101环境卫生监测与卫生工程学C03010102环境流行病学C03010103环境毒理学C030102劳动卫生学与职业病学C030103营养与食品卫生学C03010301营养学C03010302食品卫生学C030104儿童与少年卫生学C030105毒理学C03010501分子、遗传毒理学。
学校代码：10004 密级：公开北京交通大学硕士学位论文沿圆曲线的Radon变换的数值解The Numerical Solution of the Radon TransformAlong the Circular Curve作者姓名：汪琳学号：17121553导师姓名：渠刚荣职称：教授学位类别：理学学位级别：硕士学科专业：计算数学研究方向：图像重建北京交通大学2020年6月致谢本篇论文是在导师渠刚荣教授的悉心指导下完成的，从论文选题，文章结构到中期修改，程序实现等过程中，渠老师都给与了我详细认真的指导和帮助。
学习生活中，渠老师严谨治学的工作态度，一丝不苟的科研精神，以及对待生活乐观的心态，都让我受益匪浅，记忆深刻。
在交大学习的这三年时间里，跟渠老师学到的不仅有专业的知识，还有很多为人的道理，渠老师对于我而言，不仅是专业上的导师，也是一个可以谈论人生的长辈。
由衷感谢渠老师这三年来对我专业上细心的指导，生活上无微不至的关心。
在此，向渠老师的辛勤培育及谆谆教诲表示诚挚的谢意和崇高的敬意。
论文成稿于新冠肺炎疫情期间，感谢强大的祖国和最美的医护逆行者，感谢你们的勇敢无畏，因为有你们，我们才有如今安全的港湾。
感谢北京交通大学给我提供广阔的学习平台及资源，感谢理学院的老师们在专业课程上的指导，感谢学院领导对我生活上的关心，我为自己是理学院的一员而感到自豪。
感谢同门的师兄师姐师弟师妹们，每次讨论班上和大家讨论遇到的问题，总是能茅塞顿开，从而有信心继续钻研。
从刚入师门，到现在即将离开，正是你们的帮助和支持，我才能克服遇到的困难，解决学习上的疑惑，明确自己的目标，衷心感谢大家三年的帮助与陪伴。
还有，要感谢一直支持我的家人和朋友。
感谢我的父母，正是有你们的辛劳付出我才可以毫无后顾之忧的安心学习。
感谢我的朋友们，在我遇到困难时，是你们的陪伴与鼓励支持我一直向前，你们永远都是我坚强的后盾。
最后，感谢各位专家能在百忙之中抽时间审阅我的论文，我将诚恳的接受您的宝贵意见，期待您的批评指正。
