Software Engineering Body of Knowledge (v3) (2014) (811503), страница 74
Текст из файла (страница 74)
The basis step is complete.Inductive Step: The induction hypothesis (IH)is that the proposition is true for n = k, k being anarbitrary positive integer k.∴ 1 + 3 + 5+ … + (2k − 1) = k2Now, it’s to be shown that P(k) → P(k + 1).P(k + 1) = 1 + 3 + 5+ … +(2k − 1) + (2k + 1) = P(k) + (2k + 1) = k2 + (2k + 1) [using IH] = k2 + 2k + 1 = (k + 1)2Thus, it is shown that if the proposition is truefor n = k, then it is also true for n = k + 1.The basis step together with the inductive step ofthe proof show that P(1) is true and the conditionalstatement P(k) → P(k + 1) is true for all positiveintegers k. Hence, the proposition is proved.4. Basics of Counting[1*c6]The sum rule states that if a task t1 can be donein n1 ways and a second task t2 can be done inn2 ways, and if these tasks cannot be done at thesame time, then there are n1+ n2 ways to do eithertask.• If A and B are disjoint sets, then |A ∪ B|=|A|+ |B|.• In general if A1, A2, ….
, An are disjointsets, then |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2|+ … + |An|.For example, if there are 200 athletes doingsprint events and 30 athletes who participate inthe long jump event, then how many ways arethere to pick one athlete who is either a sprinteror a long jumper?Using the sum rule, the answer would be 200+ 30 = 230.The product rule states that if a task t1 can bedone in n1 ways and a second task t2 can be donein n2 ways after the first task has been done, thenthere are n1 * n2 ways to do the procedure.• If A and B are disjoint sets, then |A × B| =|A| * |B|.• In general if A1, A2, …, An are disjoint sets,then |A1 × A2 × … × An| = |A1| * |A2| * ….* |An|.For example, if there are 200 athletes doingsprint events and 30 athletes who participate inthe long jump event, then how many ways arethere to pick two athletes so that one is a sprinterand the other is a long jumper?Using the product rule, the answer would be200 * 30 = 6000.The principle of inclusion-exclusion states thatif a task t1 can be done in n1 ways and a secondtask t2 can be done in n2 ways at the same timewith t1, then to find the total number of ways thetwo tasks can be done, subtract the number ofways to do both tasks from n1 + n2.• If A and B are not disjoint, |A ∪ B| = |A| +|B| − |A ∩ B|.In other words, the principle of inclusionexclusion aims to ensure that the objects in theintersection of two sets are not counted more thanonce.14-8 SWEBOK® Guide V3.0Recursion is the general term for the practiceof defining an object in terms of itself.
There arerecursive algorithms, recursively defined functions, relations, sets, etc.A recursive function is a function that callsitself. For example, we define f(n) = 3 * f(n − 1)for all n ∈ N and n ≠ 0 and f(0) = 5.An algorithm is recursive if it solves a problemby reducing it to an instance of the same problemwith a smaller input.A phenomenon is said to be random if individual outcomes are uncertain but the long-term pattern of many individual outcomes is predictable.The probability of any outcome for a random phenomenon is the proportion of times theoutcome would occur in a very long series ofrepetitions.The probability P(A) of any event A satisfies 0≤ P(A) ≤ 1.
Any probability is a number between0 and 1. If S is the sample space in a probability model, the P(S) = 1. All possible outcomestogether must have probability of 1.Two events A and B are disjoint if they haveno outcomes in common and so can never occurtogether. If A and B are two disjoint events, P(Aor B) = P(A) + P(B). This is known as the addition rule for disjoint events.If two events have no outcomes in common,the probability that one or the other occurs is thesum of their individual probabilities.Permutation is an arrangement of objects inwhich the order matters without repetition.
Onecan choose r objects in a particular order from atotal of n objects by using nPr ways, where, npr =n! / (n − r)!. Various notations like nPr and P(n, r)are used to represent the number of permutationsof a set of n objects taken r at a time.Combination is a selection of objects in whichthe order does not matter without repetition. Thisis different from a permutation because the orderdoes not matter. If the order is only changed (andnot the members) then no new combination isformed. One can choose r objects in any orderfrom a total of n objects by using nCr ways, where,nCr = n! / [r! * (n − r)!].5. Graphs and Trees[1*, c10, c11]5.1. GraphsA graph G = (V, E) where V is the set of vertices(nodes) and E is the set of edges.
Edges are alsoreferred to as arcs or links.Figure 14.8. Example of a GraphF is a function that maps the set of edges E toa set of ordered or unordered pairs of elements V.For example, in Figure 14.8, G = (V, E) where V= {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (C, B)), (e3, (B, A))}.The graph in Figure 14.8 is a simple graph thatconsists of a set of vertices or nodes and a set ofedges connecting unordered pairs.The edges in simple graphs are undirected.Such graphs are also referred to as undirectedgraphs.For example, in Figure 14.8, (e1, (A, C)) maybe replaced by (e1, (C, A)) as the pair betweenvertices A and C is unordered.
This holds goodfor the other two edges too.In a multigraph, more than one edge may connect the same two vertices. Two or more connecting edges between the same pair of vertices mayreflect multiple associations between the sametwo vertices. Such edges are called parallel ormultiple edges.For example, in Figure 14.9, the edges e3 ande4 are both between A and B. Figure 14.9 is amultigraph where edges e3 and e4 are multipleedges.Mathematical Foundations 14-9A directed graph G = (V, E) consists of a set ofvertices V and a set of edges E that are orderedpairs of elements of V. A directed graph may contain loops.For example, in Figure 14.11, G = (V, E) whereV = {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (B, C)), (e3, (B, A))}.Figure 14.9. Example of a MultigraphIn a pseudograph, edges connecting a node toitself are allowed.
Such edges are called loops.Figure 14.12. Example of a Weighted GraphFigure 14.10. Example of a PseudographFor example, in Figure 14.10, the edge e4 bothstarts and ends at B. Figure 14.10 is a pseudograph in which e4 is a loop.In a weighted graph G = (V, E), each edge has aweight associated with it. The weight of an edgetypically represents the numeric value associatedwith the relationship between the correspondingtwo vertices.For example, in Figure 14.12, the weights forthe edges e1, e2, and e3 are taken to be 76, 93,and 15 respectively. If the vertices A, B, and Crepresent three cities in a state, the weights, forexample, could be the distances in miles betweenthese cities.Let G = (V, E) be an undirected graph withedge set E.
Then, for an edge e ∈ E where e = {u,v}, the following terminologies are often used:• u, v are said to be adjacent or neighbors orconnected.• edge e is incident with vertices u and v.• edge e connects u and v.• vertices u and v are endpoints for edge e.If vertex v ∈ V, the set of vertices in the undirected graph G(V, E), then:Figure 14.11.
Example of a Directed Graph• the degree of v, deg(v), is its number of incident edges, except that any self-loops arecounted twice.14-10 SWEBOK® Guide V3.0• a vertex with degree 0 is called an isolatedvertex.• a vertex of degree 1 is called a pendantvertex.Let G(V, E) be a directed graph. If e(u, v) is anedge of G, then the following terminologies areoften used:• u is adjacent to v, and v is adjacent from u.• e comes from u and goes to v.• e connects u to v, or e goes from u to v.• the initial vertex of e is u.• the terminal vertex of e is v.If vertex v is in the set of vertices for thedirected graph G(V, E), then• in-degree of v, deg−(v), is the number ofedges going to v, i.e., for which v is the terminal vertex.• out-degree of v, deg+(v), is the number ofedges coming from v, i.e., for which v is theinitial vertex.• degree of v, deg(v) = deg−(v) + deg+(v), is thesum of vs in-degree and out-degree.• a loop at a vertex contributes 1 to both indegree and out-degree of this vertex.It may be noted that, following the definitionsabove, the degree of a node is unchanged whetherwe consider its edges to be directed or undirected.In an undirected graph, a path of length n fromu to v is a sequence of n adjacent edges from vertex u to vertex v.• A path is a circuit if u=v.• A path traverses the vertices along it.• A path is simple if it contains no edge morethan once.A cycle on n vertices Cn for any n ≥ 3 is a simple graph where V = {v1, v2, …, vn} and E = {{v1,v2}, {v2, v3}, … , {vn−1, vn}, {vn, v1}}.For example, Figure 14.13 illustrates twocycles of length 3 and 4.Figure 14.13.
Example of Cycles C3 and C4An adjacency list is a table with one row pervertex, listing its adjacent vertices. The adjacencylisting for a directed graph maintains a listing ofthe terminal nodes for each of the vertex in thegraph.VertexAdjacencyListAB, CBA, B, CCA, BFigure 14.14. Adjacency Lists for Graphs in Figures 14.10and 14.11For example, Figure 14.14 illustrates the adjacency lists for the pseudograph in Figure 14.10and the directed graph in Figure 14.11. As theout-degree of vertex C in Figure 14.11 is zero,there is no entry against C in the adjacency list.Different representations for a graph—likeadjacency matrix, incidence matrix, and adjacency lists—need to be studied.5.2. TreesA tree T(N, E) is a hierarchical data structure of n= |N| nodes with a specially designated root nodeR while the remaining n − 1 nodes form subtreesunder the root node R.
The number of edges |E| ina tree would always be equal to |N| − 1.The subtree at node X is the subgraph of thetree consisting of node X and its descendants andall edges incident to those descendants. As analternate to this recursive definition, a tree maybe defined as a connected undirected graph withno simple circuits.Mathematical Foundations 14-11Figure 14.15. Example of a TreeHowever, one should remember that a tree isstrictly hierarchical in nature as compared to agraph, which is flat. In case of a tree, an orderedpair is built between two nodes as parent andchild.
Each child node in a tree is associatedwith only one parent node, whereas this restriction becomes meaningless for a graph where noparent-child association exists.An undirected graph is a tree if and only ifthere is a unique simple path between any two ofits vertices.Figure 14.15 presents a tree T(N, E) where theset of nodes N = {A, B, C, D, E, F, G, H, I, J, K}.The edge set E is {(A, B), (A, C), (A, D), (B, E),(B, F), (B, G), (C, H), (C, I), (D, J), (D, K)}.The parent of a nonroot node v is the uniquenode u with a directed edge from u to v. Eachnode in the tree has a unique parent node exceptthe root of the tree.For example, in Figure 14.15, root node A isthe parent node for nodes B, C, and D.
Similarly,B is the parent of E, F, G, and so on. The rootnode A does not have any parent.A node that has children is called an internalnode.For example, in Figure 14.15, node A or node Bare examples of internal nodes.The degree of a node in a tree is the same as itsnumber of children.For example, in Figure 14.15, root node A andits child B are both of degree 3. Nodes C and Dhave degree 2.The distance of a node from the root node interms of number of hops is called its level. Nodesin a tree are at different levels.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
