Difference between revisions of "Chapter 13: Computing Foundations"
(→Analyze the Problem) |
(→Analyze the Problem) |
||
Line 194: | Line 194: | ||
any reoccurrences of the problem or the development | any reoccurrences of the problem or the development | ||
of new problems must be determined. | of new problems must be determined. | ||
+ | |||
+ | ===Design a Solution Search Strategy=== | ||
+ | Once the problem analysis is complete, we can | ||
+ | focus on structuring a search strategy to find the | ||
+ | solution. In order to find the “best” solution (here, | ||
+ | “best” could mean different things to different | ||
+ | people, such as faster, cheaper, more usable, different | ||
+ | capabilities, etc.), we need to eliminate | ||
+ | paths that do not lead to viable solutions, design | ||
+ | tasks in a way that provides the most guidance in | ||
+ | searching for a solution, and use various attributes | ||
+ | of the final solution state to guide our choices in | ||
+ | the problem solving process. | ||
+ | |||
+ | ===Problem Solving Using Programs=== | ||
+ | The uniqueness of computer software gives problem | ||
+ | solving a flavor that is distinct from general | ||
+ | engineering problem solving. To solve a problem | ||
+ | using computers, we must answer the following | ||
+ | questions. | ||
+ | |||
+ | * How do we figure out what to tell the computer to do? | ||
+ | * How do we convert the problem statement into an algorithm? | ||
+ | * How do we convert the algorithm into machine instructions? | ||
+ | |||
+ | The first task in solving a problem using a computer | ||
+ | is to determine what to tell the computer to | ||
+ | do. There may be many ways to tell the story, but | ||
+ | all should take the perspective of a computer such that the computer can eventually solve the problem. | ||
+ | In general, a problem should be expressed | ||
+ | in such a way as to facilitate the development of | ||
+ | algorithms and data structures for solving it. | ||
+ | |||
+ | The result of the first task is a problem statement. | ||
+ | The next step is to convert the problem statement | ||
+ | into algorithms that solve the problem. Once | ||
+ | an algorithm is found, the final step converts the | ||
+ | algorithm into machine instructions that form the | ||
+ | final solution: software that solves the problem. | ||
+ | |||
+ | Abstractly speaking, problem solving using a | ||
+ | computer can be considered as a process of problem | ||
+ | transformation—in other words, the step-bystep | ||
+ | transformation of a problem statement into | ||
+ | a problem solution. To the discipline of software | ||
+ | engineering, the ultimate objective of problem | ||
+ | solving is to transform a problem expressed in | ||
+ | natural language into electrons running around | ||
+ | a circuit. In general, this transformation can be | ||
+ | broken into three phases: | ||
+ | |||
+ | * a) Development of algorithms from the problem statement. | ||
+ | * b) Application of algorithms to the problem. | ||
+ | * c) Transformation of algorithms to program code. | ||
+ | |||
+ | The conversion of a problem statement into | ||
+ | algorithms and algorithms into program codes | ||
+ | usually follows a “stepwise refinement” (a.k.a. | ||
+ | systematic decomposition) in which we start | ||
+ | with a problem statement, rewrite it as a task, | ||
+ | and recursively decompose the task into a few | ||
+ | simpler subtasks until the task is so simple that | ||
+ | solutions to it are straightforward. There are three | ||
+ | basic ways of decomposing: sequential, conditional, | ||
+ | and iterative. | ||
+ | |||
+ | ==Abstraction== | ||
+ | {{RightSection|{{referenceLink|number=3|parts=s5.2–5.4}}}} | ||
+ | |||
+ | Abstraction is an indispensible technique associated | ||
+ | with problem solving. It refers to both the | ||
+ | process and result of generalization by reducing | ||
+ | the information of a concept, a problem, or an | ||
+ | observable phenomenon so that one can focus | ||
+ | on the “big picture.” One of the most important | ||
+ | skills in any engineering undertaking is framing | ||
+ | the levels of abstraction appropriately. | ||
+ | |||
+ | “Through abstraction,” according to Voland, | ||
+ | “we view the problem and its possible solution | ||
+ | paths from a higher level of conceptual understanding. | ||
+ | As a result, we may become better prepared | ||
+ | to recognize possible relationships between | ||
+ | different aspects of the problem and thereby generate | ||
+ | more creative design solutions” [2*]. This | ||
+ | is particularly true in computer science in general | ||
+ | (such as hardware vs. software) and in software | ||
+ | engineering in particular (data structure vs. data | ||
+ | flow, and so forth). | ||
+ | |||
+ | ===Levels of Abstraction=== | ||
+ | When abstracting, we concentrate on one “level” | ||
+ | of the big picture at a time with confidence that | ||
+ | we can then connect effectively with levels above | ||
+ | and below. Although we focus on one level, | ||
+ | abstraction does not mean knowing nothing about | ||
+ | the neighboring levels. Abstraction levels do not | ||
+ | necessarily correspond to discrete components | ||
+ | in reality or in the problem domain, but to welldefined | ||
+ | standard interfaces such as programming | ||
+ | APIs. The advantages that standard interfaces | ||
+ | provide include portability, easier software/hardware | ||
+ | integration and wider usage. | ||
+ | |||
+ | ===Encapsulation=== | ||
+ | Encapsulation is a mechanism used to implement | ||
+ | abstraction. When we are dealing with one | ||
+ | level of abstraction, the information concerning | ||
+ | the levels below and above that level is encapsulated. | ||
+ | This information can be the concept, problem, | ||
+ | or observable phenomenon; or it may be the | ||
+ | permissible operations on these relevant entities. | ||
+ | Encapsulation usually comes with some degree | ||
+ | of information hiding in which some or all of | ||
+ | the underlying details are hidden from the level | ||
+ | above the interface provided by the abstraction. | ||
+ | To an object, information hiding means we don’t | ||
+ | need to know the details of how the object is represented | ||
+ | or how the operations on those objects | ||
+ | are implemented. | ||
+ | |||
+ | ===Hierarchy=== | ||
+ | When we use abstraction in our problem formulation | ||
+ | and solution, we may use different abstractions at different times—in other words, we work on different | ||
+ | levels of abstraction as the situation calls. | ||
+ | Most of the time, these different levels of abstraction | ||
+ | are organized in a hierarchy. There are many | ||
+ | ways to structure a particular hierarchy and the | ||
+ | criteria used in determining the specific content of | ||
+ | each layer in the hierarchy varies depending on the | ||
+ | individuals performing the work. | ||
+ | |||
+ | Sometimes, a hierarchy of abstraction is sequential, | ||
+ | which means that each layer has one and only | ||
+ | one predecessor (lower) layer and one and only | ||
+ | one successor (upper) layer—except the upmost | ||
+ | layer (which has no successor) and the bottommost | ||
+ | layer (which has no predecessor). Sometimes, | ||
+ | however, the hierarchy is organized in a tree-like | ||
+ | structure, which means each layer can have more | ||
+ | than one predecessor layer but only one successor | ||
+ | layer. Occasionally, a hierarchy can have a manyto- | ||
+ | many structure, in which each layer can have | ||
+ | multiple predecessors and successors. At no time, | ||
+ | shall there be any loop in a hierarchy. | ||
+ | |||
+ | A hierarchy often forms naturally in task decomposition. | ||
+ | Often, a task analysis can be decomposed | ||
+ | in a hierarchical fashion, starting with the larger | ||
+ | tasks and goals of the organization and breaking | ||
+ | each of them down into smaller subtasks that can | ||
+ | again be further subdivided This continuous division | ||
+ | of tasks into smaller ones would produce a | ||
+ | hierarchical structure of tasks-subtasks. | ||
+ | |||
+ | ===Alternate Abstractions=== | ||
+ | Sometimes it is useful to have multiple alternate | ||
+ | abstractions for the same problem so that one can | ||
+ | keep different perspectives in mind. For example, | ||
+ | we can have a class diagram, a state chart, | ||
+ | and a sequence diagram for the same software | ||
+ | at the same level of abstraction. These alternate | ||
+ | abstractions do not form a hierarchy but rather | ||
+ | complement each other in helping understanding | ||
+ | the problem and its solution. Though beneficial, it | ||
+ | is as times difficult to keep alternate abstractions | ||
+ | in sync. | ||
+ | |||
+ | ==Programming Fundamentals== |
Revision as of 18:07, 27 August 2015
- AOP
- Aspect-Oriented Programming
- ALU
- Arithmetic and Logic Unit
- API
- Application Programming Interface
- ATM
- Asynchronous Transfer Mode
- B/S
- Browser-Server
- CERT
- Computer Emergency Response Team
- COTS
- Commercial Off-The-Shelf
- CRUD
- Create, Read, Update, Delete
- C/S
- Client-Server
- CS
- Computer Science
- DBMS
- Database Management System
- FPU
- Float Point Unit
- I/O
- Input and Output
- ISA
- Instruction Set Architecture
- ISO
- International Organization for Standardization
- ISP
- Internet Service Provider
- LAN
- Local Area Network
- MUX
- Multiplexer
- NIC
- Network Interface Card
- OOP
- Object-Oriented Programming
- OS
- Operating System
- OSI
- Open Systems Interconnection
- PC
- Personal Computer
- PDA
- Personal Digital Assistant
- PPP
- Point-to-Point Protocol
- RFID
- Radio Frequency Identification
- RAM
- Random Access Memory
- ROM
- Read Only Memory
- SCSI
- Small Computer System Interface
- SQL
- Structured Query Language
- TCP
- Transport Control Protocol
- UDP
- User Datagram Protocol
- VPN
- Virtual Private Network
- WAN
- Wide Area Network
The scope of the Computing Foundations knowledge area (KA) encompasses the development and operational environment in which software evolves and executes. Because no software can exist in a vacuum or run without a computer, the core of such an environment is the computer and its various components. Knowledge about the computer and its underlying principles of hardware and software serves as a framework on which software engineering is anchored. Thus, all software engineers must have good understanding of the Computing Foundations KA.
It is generally accepted that software engineering builds on top of computer science. For example, “Software Engineering 2004: Curriculum Guidelines for Undergraduate Degree Programs in Software Engineering” [1] clearly states, “One particularly important aspect is that software engineering builds on computer science and mathematics” (italics added).
Steve Tockey wrote in his book Return on Software:
Both computer science and software engineering deal with computers, computing, and software. The science of computing, as a body of knowledge, is at the core of both. … Software engineering is concerned with the application of computers, computing, and software to practical purposes, specifically the design, construction, and operation of efficient and economical software systems. Thus, at the core of software engineering is an understanding of computer science.
While few people will deny the role computer science plays in the development of software engineering both as a discipline and as a body of knowledge, the importance of computer science to software engineering cannot be overemphasized; thus, this Computing Foundations KA is being written.
The majority of topics discussed in the Computing Foundations KA are also topics of discussion in basic courses given in computer science undergraduate and graduate programs. Such courses include programming, data structure, algorithms, computer organization, operating systems, compilers, databases, networking, distributed systems, and so forth. Thus, when breaking down topics, it can be tempting to decompose the Computing Foundations KA according to these often-found divisions in relevant courses.
However, a purely course-based division of topics suffers serious drawbacks. For one, not all courses in computer science are related or equally important to software engineering. Thus, some topics that would otherwise be covered in a computer science course are not covered in this KA. For example, computer graphics—while an important course in a computer science degree program—is not included in this KA.
Second, some topics discussed in this guideline do not exist as standalone courses in undergraduate or graduate computer science programs. Consequently, such topics may not be adequately covered in a purely course-based breakdown. For example, abstraction is a topic incorporated into several different computer science courses; it is unclear which course abstraction should belong to in a course-based breakdown of topics.
The Computing Foundations KA is divided into seventeen different topics. A topic’s direct usefulness to software engineers is the criterion used for selecting topics for inclusion in this KA (see Figure 13.1). The advantage of this topic-based breakdown is its foundation on the belief that Computing Foundations— if it is to be grasped firmly—must be considered as a collection of logically connected topics undergirding software engineering in general and software construction in particular.
The Computing Foundations KA is related closely to the Software Design, Software Construction, Software Testing, Software Maintenance, Software Quality, and Mathematical Foundations KAs.
The breakdown of topics for the Computing Foundations KA is shown in Figure 13.1.
1 Problem Solving Techniques
The concepts, notions, and terminology introduced here form an underlying basis for understanding the role and scope of problem solving techniques.
1.1 Definition of Problem Solving
Problem solving refers to the thinking and activities conducted to answer or derive a solution to a problem. There are many ways to approach a problem, and each way employs different tools and uses different processes. These different ways of approaching problems gradually expand and define themselves and finally give rise to different disciplines. For example, software engineering focuses on solving problems using computers and software.
While different problems warrant different solutions and may require different tools and processes, the methodology and techniques used in solving problems do follow some guidelines and can often be generalized as problem solving techniques. For example, a general guideline for solving a generic engineering problem is to use the three-step process given below [2*].
- Formulate the real problem.
- Analyze the problem.
- Design a solution search strategy.
1.2 Formulating the Real Problem
Gerard Voland writes, “It is important to recognize that a specific problem should be formulated if one is to develop a specific solution” [2*]. This formulation is called the problem statement, which explicitly specifies what both the problem and the desired outcome are.
Although there is no universal way of stating a problem, in general a problem should be expressed in such a way as to facilitate the development of solutions. Some general techniques to help one formulate the real problem include statement-restatement, determining the source and the cause, revising the statement, analyzing present and desired state, and using the fresh eye approach.
1.3 Analyze the Problem
Once the problem statement is available, the next step is to analyze the problem statement or situation to help structure our search for a solution. Four types of analysis include situation analysis, in which the most urgent or critical aspects of a situation are identified first; problem analysis, in which the cause of the problem must be determined; decision analysis, in which the action(s) needed to correct the problem or eliminate its cause must be determined; and potential problem analysis, in which the action(s) needed to prevent any reoccurrences of the problem or the development of new problems must be determined.
1.4 Design a Solution Search Strategy
Once the problem analysis is complete, we can focus on structuring a search strategy to find the solution. In order to find the “best” solution (here, “best” could mean different things to different people, such as faster, cheaper, more usable, different capabilities, etc.), we need to eliminate paths that do not lead to viable solutions, design tasks in a way that provides the most guidance in searching for a solution, and use various attributes of the final solution state to guide our choices in the problem solving process.
1.5 Problem Solving Using Programs
The uniqueness of computer software gives problem solving a flavor that is distinct from general engineering problem solving. To solve a problem using computers, we must answer the following questions.
- How do we figure out what to tell the computer to do?
- How do we convert the problem statement into an algorithm?
- How do we convert the algorithm into machine instructions?
The first task in solving a problem using a computer is to determine what to tell the computer to do. There may be many ways to tell the story, but all should take the perspective of a computer such that the computer can eventually solve the problem. In general, a problem should be expressed in such a way as to facilitate the development of algorithms and data structures for solving it.
The result of the first task is a problem statement. The next step is to convert the problem statement into algorithms that solve the problem. Once an algorithm is found, the final step converts the algorithm into machine instructions that form the final solution: software that solves the problem.
Abstractly speaking, problem solving using a computer can be considered as a process of problem transformation—in other words, the step-bystep transformation of a problem statement into a problem solution. To the discipline of software engineering, the ultimate objective of problem solving is to transform a problem expressed in natural language into electrons running around a circuit. In general, this transformation can be broken into three phases:
- a) Development of algorithms from the problem statement.
- b) Application of algorithms to the problem.
- c) Transformation of algorithms to program code.
The conversion of a problem statement into algorithms and algorithms into program codes usually follows a “stepwise refinement” (a.k.a. systematic decomposition) in which we start with a problem statement, rewrite it as a task, and recursively decompose the task into a few simpler subtasks until the task is so simple that solutions to it are straightforward. There are three basic ways of decomposing: sequential, conditional, and iterative.
2 Abstraction
Abstraction is an indispensible technique associated with problem solving. It refers to both the process and result of generalization by reducing the information of a concept, a problem, or an observable phenomenon so that one can focus on the “big picture.” One of the most important skills in any engineering undertaking is framing the levels of abstraction appropriately.
“Through abstraction,” according to Voland, “we view the problem and its possible solution paths from a higher level of conceptual understanding. As a result, we may become better prepared to recognize possible relationships between different aspects of the problem and thereby generate more creative design solutions” [2*]. This is particularly true in computer science in general (such as hardware vs. software) and in software engineering in particular (data structure vs. data flow, and so forth).
2.1 Levels of Abstraction
When abstracting, we concentrate on one “level” of the big picture at a time with confidence that we can then connect effectively with levels above and below. Although we focus on one level, abstraction does not mean knowing nothing about the neighboring levels. Abstraction levels do not necessarily correspond to discrete components in reality or in the problem domain, but to welldefined standard interfaces such as programming APIs. The advantages that standard interfaces provide include portability, easier software/hardware integration and wider usage.
2.2 Encapsulation
Encapsulation is a mechanism used to implement abstraction. When we are dealing with one level of abstraction, the information concerning the levels below and above that level is encapsulated. This information can be the concept, problem, or observable phenomenon; or it may be the permissible operations on these relevant entities. Encapsulation usually comes with some degree of information hiding in which some or all of the underlying details are hidden from the level above the interface provided by the abstraction. To an object, information hiding means we don’t need to know the details of how the object is represented or how the operations on those objects are implemented.
2.3 Hierarchy
When we use abstraction in our problem formulation and solution, we may use different abstractions at different times—in other words, we work on different levels of abstraction as the situation calls. Most of the time, these different levels of abstraction are organized in a hierarchy. There are many ways to structure a particular hierarchy and the criteria used in determining the specific content of each layer in the hierarchy varies depending on the individuals performing the work.
Sometimes, a hierarchy of abstraction is sequential, which means that each layer has one and only one predecessor (lower) layer and one and only one successor (upper) layer—except the upmost layer (which has no successor) and the bottommost layer (which has no predecessor). Sometimes, however, the hierarchy is organized in a tree-like structure, which means each layer can have more than one predecessor layer but only one successor layer. Occasionally, a hierarchy can have a manyto- many structure, in which each layer can have multiple predecessors and successors. At no time, shall there be any loop in a hierarchy.
A hierarchy often forms naturally in task decomposition. Often, a task analysis can be decomposed in a hierarchical fashion, starting with the larger tasks and goals of the organization and breaking each of them down into smaller subtasks that can again be further subdivided This continuous division of tasks into smaller ones would produce a hierarchical structure of tasks-subtasks.
2.4 Alternate Abstractions
Sometimes it is useful to have multiple alternate abstractions for the same problem so that one can keep different perspectives in mind. For example, we can have a class diagram, a state chart, and a sequence diagram for the same software at the same level of abstraction. These alternate abstractions do not form a hierarchy but rather complement each other in helping understanding the problem and its solution. Though beneficial, it is as times difficult to keep alternate abstractions in sync.