Software Engineering Body of Knowledge (v3) (2014) (811503), страница 65
Текст из файла (страница 65)
Often, a data structure can determine whether a program runs in afew seconds or in a few hours or even a few days.From the perspective of physical and logical ordering, a data structure is either linear ornonlinear. Other perspectives give rise to different classifications that include homogeneousvs. heterogeneous, static vs. dynamic, persistentvs. transient, external vs. internal, primitive vs.aggregate, recursive vs. nonrecursive; passive vs.active; and stateful vs.
stateless structures.6.2. Types of Data StructureAs mentioned above, different perspectives canbe used to classify data structures. However, thepredominant perspective used in classificationcenters on physical and logical ordering betweendata items. This classification divides data structures into linear and nonlinear structures. Linearstructures organize data items in a single dimension in which each data entry has one (physicalor logical) predecessor and one successor withthe exception of the first and last entry. The firstentry has no predecessor and the last entry hasno successor.
Nonlinear structures organize dataitems in two or more dimensions, in which caseone entry can have multiple predecessors andsuccessors. Examples of linear structures includelists, stacks, and queues. Examples of nonlinearstructures include heaps, hash tables, and trees(such as binary trees, balance trees, B-trees, andso forth).Another type of data structure that is oftenencountered in programming is the compoundstructure. A compound data structure builds ontop of other (more primitive) data structures and,in some way, can be viewed as the same structureas the underlying structure. Examples of compound structures include sets, graphs, and partitions. For example, a partition can be viewed asa set of sets.6.3. Operations on Data StructuresAll data structures support some operations thatproduce a specific structure and ordering, orretrieve relevant data from the structure, store datainto the structure, or delete data from the structure.Basic operations supported by all data structuresinclude create, read, update, and delete (CRUD).• Create: Insert a new data entry into thestructure.• Read: Retrieve a data entry from the structure.• Update: Modify an existing data entry.• Delete: Remove a data entry from thestructure.Some data structures also support additionaloperations:13-10 SWEBOK® Guide V3.0• Find a particular element in the structure.• Sort all elements according to some ordering.• Traverse all elements in some specific order.• Reorganize or rebalance the structure.Different structures support different operations with different efficiencies.
The differencebetween operation efficiency can be significant.For example, it is easy to retrieve the last iteminserted into a stack, but finding a particular element within a stack is rather slow and tedious.7. Algorithms and Complexity[5*, s1.1–1.3, s3.3–3.6, s4.1–4.8, s5.1–5.7,s6.1–6.3, s7.1–7.6, s11.1, s12.1]Programs are not random pieces of code: they aremeticulously written to perform user-expectedactions. The guide one uses to compose programsare algorithms, which organize various functionsinto a series of steps and take into considerationthe application domain, the solution strategy, andthe data structures being used. An algorithm canbe very simple or very complex.7.1. Overview of AlgorithmsAbstractly speaking, algorithms guide the operations of computers and consist of a sequence ofactions composed to solve a problem.
Alternativedefinitions include but are not limited to:• An algorithm is any well-defined computational procedure that takes some value or setof values as input and produces some valueor set of values as output.• An algorithm is a sequence of computationalsteps that transform the input into the output.• An algorithm is a tool for solving a wellspecified computation problem.Of course, different definitions are favoredby different people. Though there is no universally accepted definition, some agreement existsthat an algorithm needs to be correct, finite (inother words, terminate eventually or one must beable to write it in a finite number of steps), andunambiguous.7.2. Attributes of AlgorithmsThe attributes of algorithms are many and ofteninclude modularity, correctness, maintainability, functionality, robustness, user-friendliness(i.e.
easy to be understood by people), programmer time, simplicity, and extensibility. A commonly emphasized attribute is “performance”or “efficiency” by which we mean both timeand resource-usage efficiency while generallyemphasizing the time axis. To some degree, efficiency determines if an algorithm is feasible orimpractical. For example, an algorithm that takesone hundred years to terminate is virtually useless and is even considered incorrect.7.3. Algorithmic AnalysisAnalysis of algorithms is the theoretical studyof computer-program performance and resourceusage; to some extent it determines the goodnessof an algorithm. Such analysis usually abstractsaway the particular details of a specific computerand focuses on the asymptotic, machine-independent analysis.There are three basic types of analysis.
Inworst-case analysis, one determines the maximum time or resources required by the algorithmon any input of size n. In average-case analysis,one determines the expected time or resourcesrequired by the algorithm over all inputs of sizen; in performing average-case analysis, one oftenneeds to make assumptions on the statistical distribution of inputs. The third type of analysis isthe best-case analysis, in which one determinesthe minimum time or resources required by thealgorithm on any input of size n.
Among thethree types of analysis, average-case analysis isthe most relevant but also the most difficult toperform.Besides the basic analysis methods, there arealso the amortized analysis, in which one determines the maximum time required by an algorithm over a sequence of operations; and thecompetitive analysis, in which one determinesthe relative performance merit of an algorithmagainst the optimal algorithm (which may notbe known) in the same category (for the sameoperations).Computing Foundations 13-117.4. Algorithmic Design StrategiesThe design of algorithms generally follows oneof the following strategies: brute force, divideand conquer, dynamic programming, and greedyselection.
The brute force strategy is actually ano-strategy. It exhaustively tries every possibleway to tackle a problem. If a problem has a solution, this strategy is guaranteed to find it; however,the time expense may be too high. The divide andconquer strategy improves on the brute forcestrategy by dividing a big problem into smaller,homogeneous problems. It solves the big problem by recursively solving the smaller problemsand combing the solutions to the smaller problems to form the solution to the big problem.
Theunderlying assumption for divide and conquer isthat smaller problems are easier to solve.The dynamic programming strategy improveson the divide and conquer strategy by recognizing that some of the sub-problems produced bydivision may be the same and thus avoids solvingthe same problems again and again. This elimination of redundant subproblems can dramaticallyimprove efficiency.The greedy selection strategy further improveson dynamic programming by recognizing thatnot all of the sub-problems contribute to the solution of the big problem.
By eliminating all butone sub-problem, the greedy selection strategyachieves the highest efficiency among all algorithm design strategies. Sometimes the use ofrandomization can improve on the greedy selection strategy by eliminating the complexity indetermining the greedy choice through coin flipping or randomization.7.5. Algorithmic Analysis StrategiesThe analysis strategies of algorithms includebasic counting analysis, in which one actuallycounts the number of steps an algorithm takes tocomplete its task; asymptotic analysis, in whichone only considers the order of magnitude ofthe number of steps an algorithm takes to complete its task; probabilistic analysis, in whichone makes use of probabilities in analyzing theaverage performance of an algorithm; amortized analysis, in which one uses the methods ofaggregation, potential, and accounting to analyze the worst performance of an algorithm on asequence of operations; and competitive analysis,in which one uses methods such as potential andaccounting to analyze the relative performance ofan algorithm to the optimal algorithm.For complex problems and algorithms, onemay need to use a combination of the aforementioned analysis strategies.8. Basic Concept of a System[6*, c10]Ian Sommerville writes, “a system is a purposefulcollection of interrelated components that worktogether to achieve some objective” [6*].
A system can be very simple and include only a fewcomponents, like an ink pen, or rather complex,like an aircraft. Depending on whether humansare part of the system, systems can be dividedinto technical computer-based systems and sociotechnical systems. A technical computer-basedsystem functions without human involvement,such as televisions, mobile phones, thermostat,and some software; a sociotechnical systemwill not function without human involvement.Examples of such system include manned spacevehicles, chips embedded inside a human, and soforth.8.1. Emergent System PropertiesA system is more than simply the sum of its parts.Thus, the properties of a system are not simply thesum of the properties of its components.
Instead,a system often exhibits properties that are properties of the system as a whole. These properties arecalled emergent properties because they developonly after the integration of constituent parts inthe system. Emergent system properties can beeither functional or nonfunctional. Functionalproperties describe the things that a system does.For example, an aircraft’s functional propertiesinclude flotation on air, carrying people or cargo,and use as a weapon of mass destruction. Nonfunctional properties describe how the systembehaves in its operational environment. Thesecan include such qualities as consistency, capacity, weight, security, etc.13-12 SWEBOK® Guide V3.0Figure 13.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
