Hide Notes 

Slide 1: Part 14 Software tools and programming languages The purpose of this part is to provide a forum for software scientists to present and discuss recent researches and developments in the programming languages and software. The scope of the part is not restricted, it covers ongoing research in different countries related to software technology with emphasize in programming languages and software tools e.g.: algorithms and data structures, programming languages and paradigms, software engineering, information systems, logic and declarative programming, parallel and distributed computing, embedded computing, etc. The papers include the impact of quality factors on the success of software development, language structure decompositions, embedded applications for driverless metro train, a post-mortem JavaSpaces debugger, stochastic numerical simulations using C#, visualization and analyses of multi-dimensional data sets using OLAP, design of a computer-based triangle chess machine, a taxonomy model for analyzing project-based learning using analytical hierarchy process , a framework of mixed model of a neural network and boolean logic for financial crisis prediction, chinese document clustering using self-organizing map-based on botanical document warehouse, linear discriminant analysis in Ottoman alphabet character recognition, user requirements engineering and management in software development and tools for active filter synthesis.
Slide 2: Chapter 1 Impact of quality factors on the success of software development M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi 1 1 2 Department of Computer Engineering & IT, Islamic Azad University Fars Sciences and Research Branch, Fars, IRAN 2 Department of Computer Engineering, Amir Kabir University Tehran, IRAN Abstract. During the design of a system, software engineering is faced with many choices. Most of these choices involve the identification of a solution for a problem from a given set of alternatives. The alternative solutions generally only differ with respect to quality attributes. Quality factors have very strong impact on the success of software development methodologies, therefore the alterative should be selected which satisfies the quality requirements best. This paper was undertaken to gathering popular methodologies such as SSADM (Structured System Analysis and Design) and ObjectOriented towards the impact of quality factors on methodology choice. In this paper, an empirical comparison was made between two mentioned methodologies used with a software project. The mentioned methodologies for project domain were compared using some quality factors such as maintainability, flexibility, reliability and usability. The obtained results indicated that investigation of quality factors such as maintainability, flexibility, reliability in Object-Oriented methodology was achieved in less time than SSADM, whereas on usability parameter users were clearly more satisfied with their experience with the SSADM.
Slide 3: Impact of quality factors on the success of software development Keywords. SSADM Methodology, Object-Oriented Methodology, Maintainability, Reliability, Flexibility, Usability. 147 1.1 Introduction Engineering approach for constructing systems needs methodology and suitable tools to produce software. There is no general software development methodology powerful enough to handle all the variations of today systems [11]. Methodology could be revised, improved and extended [6]. The main objective of this paper is to compare and evaluate two evaluation methodologies such as SSADM and Object-Oriented based on quality factors to discover the similarities and differences. Currently, the most widely used methodology for constructing software system is SSADM. This methodology was introduced by Yourdon and Constantine [10], and has since been developed and modified by a number of authors [9, 13, 5, 4, 11]. SSADM methodology focuses on the flow of data through the software processes (functions) which each function is a basic design component. Today, most information systems are built using Object-Oriented methodology [1, 7]. This methodology allows programmer to build software from software parts called objects. An object contains both the data and functions that operate upon the data. An object can only be accessed via the functions it makes publicly available, so that the details of its implementation are hidden from other objects. By the adoption of Object-Oriented methodology, higher productivity, lower maintenance cost and better quality can be achieved. Measurement is fundamental to any engineering discipline, and software engineering is, or should be, no exception. Software metrics deals with the measurement of the software product and process by which it is developed. The metrics are used to estimate/predict product costs and schedules and to measure productivity and product quality. So software metrics tell us something about the quality of software. In this paper, we discuss some quality metrics (Reliability, Maintainability, Usability and Flexibility) as quality parameters. Next section briefly reviews some Distinguishing Characteristics of Object-Oriented methodology like encapsulation, inheritance and abstraction. Section three describes some quality factors that are used for evaluating the mentioned systems. Section four presents an Illustrative Case Study Problem. Section five shows the results of comparing SSADM and Object-
Slide 4: 148 M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi Oriented used in an exciting software project and discusses the obtained results. 1.2 The distinguishing characteristics The Object-Oriented methodology includes a set of mechanisms such as inheritance, encapsulation, and abstraction. Each of these characteristics is discussed briefly in the sections that fallow: 1.2.1Abstraction Abstraction is the best hope for dramatically the difficulty and cost of software development [7]. At a low level of abstraction, a more procedural orientation is taken. Finally, at the lowest level of abstraction, the solution is stated in a manner that can be directly implemented. 1.2.2Encapsulation Encapsulation means that all of this information is packaged under one name and can be reused as one specification or program component. For Object- Oriented systems, encapsulation is encompasses the responsibilities of a class, including its attributes, and operation, and the states of the class as defined by specific attributes values [5]. 1.2.3Inheritance Inheritance is a mechanism that enables the responsibilities of one object to be propagated to other objects. Inheritance occurs throughout all level of a class hierarchy. Because Inheritance is a pivotal characteristic in many Object Oriented systems, many Object Oriented metrics focus on it [5]. 1.3 Software quality factors Software quality is a complex mix of factors that will vary across different applications and the customers who request them [5]. Software quality can be modeled in different ways and quality as a metric depends on software
Slide 5: Impact of quality factors on the success of software development 149 we are measuring [2]. In this paper, we concentrate on some operational quality factors which are discussed briefly in the sections that fallow: 1.3.1Flexibility Flexibility is an effort required to modify an operational program. In this paper, flexibility of two implemented systems was investigated with creating a new requirement. 1.3.2Maintainability Maintainability is the ease with which a program can be corrected if an error is encountered, adapted if its environment changes, or enhanced if the customer desires a change in requirement. In this paper, maintainability of two implemented systems was investigated with creating code modification 1.3.3Reliability Reliability metric as a quality factor attempts to measure and predict the probability of failures during a particular time interval, or the mean time to failure (MTTF). In this paper, reliability of two implemented systems was investigated with creating faulty inputs. 1.3.4Usability On early models of quality, McCall's and Boehms quality models [14], usability doesn't play big part. But for end-users usability is perhaps the most important quality metric [2, 8]. For a large number of products, it is believed that usability becomes the final arbiter of quality. Usability metric as a quality factor attempts to measure the effort required to learn, operate, prepare input, and interrupt output of program. In this paper, Usability of two implemented systems was investigated with training users (staffs). 1.4 An illustrative case study problem As a case study, In order to compare Structured System Analysis and Design Methodology (SSADM) and Object-Oriented methodologies, we
Slide 6: 150 M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi decided to examine software system produced by each of the methodologies for a single problem domain. For the problem domain, we take a project of Tehran exchange software system and investigate one part of it. The systems’ overall purpose was the” management of monitoring factories and share investigation”. First, the requirements analysis and system design was conducted using SSADM methodology with DFD diagrams by Easy Case software. Second, to complete the modeling, we performed a simulated Object-Oriented requirements and system design with UML diagrams by Rational Rose software. At last, we implemented the system with Delphi programming language, employing SQL Server database management system. There is a fundamental difference between data flow and object models. In data flow model, we concentrate on organizing system knowledge around a hierarchy of functions, with data organization playing a secondary role. In an object model, the primary organizing concept is that of an object and its embodied data (attributes) and functions (services). Because of this basic difference, it is natural to ask which the superior methodology for system modeling is. In this paper, we are attempting the resolution of this question based on some quality factors such as flexibility, reliability, maintainability and usability. 1.5 Comparing the two methodologies 1.5.1Preliminary results This section presents quality factors (Reliability, Maintainability, Flexibility and Usability) in terms of the time needed to perform the task. In this section, we first review the results of comparing SSADM and Object-Oriented based on these factors and then discuss about the obtained results. 1.5.1.1 Reliability results In this paper, Reliability of two implemented systems was investigated with creating faulty inputs. Table 1.1 shows the number of failures detected during a particular time interval in two methodologies. Table 1.1. Measurement of Reliability in terms of Time (Minutes) SSADM Methodology Object-Oriented Methodology
Slide 7: Impact of quality factors on the success of software development 0.10 0.15 0.23 0.27 0.10 0.15 0.17 0.18 151 Fig. 1.1. Comparing Reliability of two Methodologies 1.5.1.2 Maintainability results In this paper, Maintainability of two implemented systems was investigated with creating code modification. Table 1.2 shows the time it takes to correct a change in two methodologies. Table 1.2. Measurement of Maintainability in terms of Time (Minutes) SSADM Methodology 37 45 40 85 Object-Oriented Methodology 20 30 40 60 Fig. 1.2. Comparing Maintainability of two Methodologies
Slide 8: 152 M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi 1.5.1.3 Flexibility results In this paper, flexibility of two implemented systems was investigated with creating a new requirement. Table 1.3 shows the time it takes this change in the analysis, design and coding. Table 1.3. Measurement of Flexibility in terms of Time SSADM Methodology 60 m 95 m 105 m 185 m Object-Oriented Methodology 40 m 55 m 70 m 85 m Fig. 1.3. Comparing Flexibility of two Methodologies 1.5.1.4 Usability results In this paper, Usability of two implemented systems was investigated with training users (staffs). Learnability measured in time needed for learning perform tasks or required training. Thirty-two staffs participated in this study. There were 13 female and 19 male participants ranging in age from 22 to 38. Of the 32 participants, 19 learned SSADM in less time, 9 learned Object–Oriented in less time and 4 learned approximately in equal time.
Slide 9: Impact of quality factors on the success of software development 153 Fig. 1.4. Comparing Usability of two Methodologies Table 1.4. Measurement of Training in terms of Time Number of staffs 19 (59%) 9 (28.12%) 4 (12.50%) Methodology SSADM Object-Oriented SSADM and Object-Oriented 1.5.2Discussions This section discusses the results that obtained in the previous section. 1.5.2.1 Differences in reliability Results showed that the probability of failures during a particular time interval Object-Oriented methodology is fewer than SSADM. The obtained results of this research reveled that Object-Oriented is a suitable methodology based on reliability metric (Figure 1.1). Theses results are because of some reasons as follow: • Objects are reusable. Once they are designed, tested and built, objects can be reused in multiple systems and application. Therefore using reusable components can increase reliability. • Coupling is already proven to be useful criteria for reliability. Interfaces among encapsulated objects are simplified. An object that sends a message need not be concerned with the details of internal data structures. Hence, interfaces is simplified and the system coupling tends to be reduced so reliability increased.
Slide 10: 154 M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi • Encapsulation is the concept that objects should hide their internal contents from other system component and prevents the unauthorized access of an object’s data. 1.5.2.2 Differences in maintainability The obtained results of this research reveled that Object-Oriented is a suitable methodology based on maintainability metric (Figure 1.2). These results are because of some reasons as follow: • Object-Oriented methodology consists of independent modules, so independent modules are easer to maintain and test because secondary effects caused by design or code modification are limited and error propagation is reduced. • Encapsulation can cause the internal implementation details of data and procedures are hidden from the outside world (information hiding). This reduces the propagation of side effects when changing occurs. • In Object-Oriented methodology, localization is based on objects, and the relationship between operations (functions) and classes is not necessarily one to one. So each object can be changed at any time without affecting the other objects. • Objects are extensible. They can be changed easily without adversely impacting any previous application that used them. 1.5.2.3 Differences in flexibility The obtained Results showed that Object-Oriented methodology handle creating a new requirement much faster than SSADM (Figure 1.3). These results are because of some reasons as follow: • Reused of a subroutine or function decrease the need to create new code to perform the same task therefore reuse increases flexibility of software. • In Object-Oriented methodology, better understanding established by the association of data with operations. By maintaining this tight association, maintainability of the software is facilated by localizing the impact of change to specific parts of the system. • Objects are extensible. They can be expanded easily without adversely impacting any previous applications that used them. 1.5.2.4 Differences in usability The obtained Results showed that time needed for learning perform tasks or required training in SSADM is much faster than Object-Oriented. The
Slide 11: Impact of quality factors on the success of software development 155 obtained results of this research reveled that SSADM is a suitable methodology based on Usability metric (Figure 1.4). These results are because of SSADM does not require very special skills and can easily be taught to the staff. Nowadays common modeling and diagramming tools are used, commercial case tools are also offered in order to be able to set up SSADM easily [3]. 1.6 Conclusions Selecting a suitable methodology for development of a system is difficult. However, some measurements are needed for software engineers in order to choose the suitable methodology. In this paper, we have defined some quality factors such as reliability, maintainability, flexibility and Usability that are practical and easily computable. We introduced two types of methodologies like SSADM and Object-Oriented. In this paper, we compared two mentioned methodologies based on quality factors to choose the suitable one. The obtained results of this research revealed that Object-Oriented is a suitable methodology based on Reliability, Flexibility and Maintainability, whereas SSADM is an appropriate methodology based on usability factor. Refrences 1. Cox B (1987) Object Oriented Programming: An evolutionary approach. Addision-Welsey 2. Fenton N, Lawrence S (1997) Software metrics – A rigorous et practical approach. PWS Publishing Company, Revised Printing, pp 337-361 3. ISO (1995) Information Technology- Software lifecycle processes. International Organization for Standardization, ISO/IEC 4. ITS (2003) An introduction to Structured System Analysis and Design Method (SSADM). The Government of Hong Kong Special Adminstrative Resion 5. Jackson M (1983) System development. Prentice-Hall, Englewood Cliffs 6. Jones M (1980) The practical guide to structured systems design. Yourdon Press, New York 7. Korpua, A (2006) Measuring usability. Thesis 8. Meyer B (2003) The power of abstraction, reuse and simplicity: an object-oriented library for event-driven design. Springer-Verlag 9. Nichols D, Twidale B (2002) Usability and open Source Software 10. Pressman R (2002) Adaptable Process Model 11. Rambaugh J, Blaha M, Premerlani W, Eddy F, Lorensen W Object Oriented modeling and design. Prentice Hall
Slide 12: 156 M. Sepehri, A. Abdollahzadeh, M. Sepehri, M. Goodarzi 12. Sargent R, Behling P (2002) Back to systems delivery basics with five methodology imperatives. 13. Vazquez F (1994) Selecting a software development process. ACM 14. Yourdon E, Constantine L (1975) Structured design. Yourdon Press, New York
Slide 13: Chapter 2 Sisal 3.2 language structure decomposition V.N. Kasyanov, A.P. Stasenko A.P. Ershov Institute of Informatics Systems / Novosibirsk State University, Novosibirsk, 630090, RUSSIA Abstract. The functional programming system SFP system being under development at the Institute of Informatics Systems in Novosibirsk is aimed at supporting development of parallel computing applications that still offer high performance and portability. The paper describes equivalent transformations of the Sisal 3.2 programming language (based on Sisal 90) structures. These transformations are to decompose the complex language structures into more simple ones that can be directly expressed by the internal representation IR1, which is based on the intermediate form language IF1. Currently some description of similar transformations can be found in few works about Sisal 90 in the form of examples. These transformations are performed by the front-end compiler from Sisal 3.2 into IR1 and help to better understand its translation strategy. The paper also briefly describes IR1 languages. Keywords. Compiler, Functional programming, Optimization, Parallel programming, Equivalent transformations 2.1 Introduction Using traditional methods, it is very difficult to develop high quality, portable software for parallel computers. In particular, parallel software cannot
Slide 14: 158 V.N. Kasyanov, A.P. Stasenko be developed on low cost, sequential computers and then moved to high performance parallel computers without extensive rewriting and debugging. Functional programming [1] is a programming paradigm, which is entirely different from the conventional model: a functional program can be recursively defined as a composition of functions where each function can itself be another composition of functions or a primitive operator (such as arithmetic operators, etc.). The programmer need not be concerned with explicit specification of parallel processes since independent functions are activated by the predecessor functions and the data dependencies of the program. This also means that control can be distributed. Further, no central memory system is inherent to the model since data is not “written” in by any instruction but is “passed from” one function to the next. Functional language Sisal (Steams and Iterations in a Single Assignment Language) is considered as an alternative to Fortran language for supercomputers [2]. Compared with imperative languages (like Fortran), functional languages, such as Sisal, simplifies programmer's work. He has only to specify a result of calculations and it is a compiler that is responsible for mapping an algorithm to certain calculator architecture (including instructions scheduling, data transfer, execution synchronization, memory management and etc.) In contrast with other functional languages, Sisal supports data types and operators typical for scientific calculations. At present, there are implementations of the Sisal 1.2 language for many supercomputers, e.g., SGI, Sequent, Encore Multimax, Cray X-MP, Cray 2, etc (see [3]). The Sisal 90 language definition [4] increases the language's utility for scientific programming. It includes language level support for complex values, array and vector operations, higher order functions, rectangular arrays, and an explicit interface to other languages like Fortran and C. The Sisal 3.2 language that has been designed as the input language of the SFP system being under development at the Institute of Informatics Systems in Novosibirsk [6] is an extension of the Sisal 3.1 [5] which is based on the Sisal 90. Sisal 3.1 simplifies, improves, extends and more exactly specifies Sisal 90. Sisal 3.2 also incorporates ideas of enhanced module support, annotated and preprocessing of Sisal 3.0 [7]. Other extensions of Sisal 3.2 are function overloading and user-defined types, which allow user-defined operations. The SFP system is aimed at supporting development of parallel computing applications that still offer high performance and portability. It works on a personal computer under Microsoft Windows 2000/XP and provides means to write and debug Sisal-programs regardless target architectures as well as to translate the Sisal-programs into optimized imperative programs, appropriate to the target execution platforms.
Slide 15: Sisal 3.2 language structure decomposition 159 The SFP system uses intermediate language R1 [8], which is based on the intermediate form language IF1 [9]. IR1 is a language of hierarchical graphs [10] made up simple and compound computation nodes, edges and ports. Nodes correspond to computations. Simple nodes are vertices of underlying graph and denote operations such as add or divide. Compound nodes are fragments (or subgraphs) of underlying graph and represent compound constructions such as structured expressions and loops. Ports are vertices of underlying graph that are used for input values and results of compound nodes. Edges show the transmission of data between simple nodes and ports; types are associated with the data transmitted on edges. In the paper equivalent transformations of the Sisal 3.2 programming language structures are described. These transformations aim to decompose the complex language structures into more simple ones that can be directly expressed by the internal representation IR1. Currently some description of similar transformations can be found in few works about Sisal 90 in the form of examples. These transformations are performed by our front-end compiler and help to better understand its translation strategy. The paper also briefly describes IR1 language. The rest of the paper is structured as follows. Sections 2.2 and 2.3 briefly describe the most important Select and Forall compound nodes of the intermediate language IR1 that represent the most Sisal 3.2 language syntax constructions. Sections 2.4 – 2.12 present transformations of complex Sisal 3.2 language structures into more simple ones that can be directly represented by IR1. 2.2 The compound node Select The compound node Select has arbitrary number of input ports and nonzero number of output ports. Let N ≥ 3 be the number of its graphs. The input ports of all graphs are the same as the input ports of the containing compound node and directly receive values from them. All graphs except the first one have the same output ports as the output ports of the containing compound node. One of these N–1 graphs is chosen to supply values of its output ports to the output ports of the containing compound node. The choice is based on the first graph, which has different semantics compared to its prototype from IF1. The first graph has N–2 Boolean output ports (edges that end in these ports have Boolean type), which are sequentially checked until the true value is found on the output port number M. In that case, graph number M+1 is chosen. If no true value is found, then the last graph is chosen. In the case of the erroneous Boolean value,
Slide 16: 160 V.N. Kasyanov, A.P. Stasenko the error values are placed on the output ports of the containing compound node. It is clear that the Select compound node can directly represent the if expression of Sisal 3.2. If the else branch is omitted, then the last graph is generated to return error values of the corresponding types. 2.3 The compound node Forall The compound node Forall uses the following groups of ports and has four graphs described in Table 2.1. Each port group consists of the same ports for each separate compound node Forall. • The group C – the constants, imported to the compound node ports. • The group R – the result values, exported from the compound node ports. • The group L – the dependent loop values. • The group L2 – the local loop values. • The group OL – the old dependent loop values. • The group D – the loop range generator values. Table 2.1. Port groups of the compound node Forall and its graphs Graph Number 1 2 3 4 Graph Name Forall Initialization Range generator Loop body Return statement Input port groups C C C OL, D, C OL, L, L2, D. C Output port groups R L D L, L2 R At the beginning, the output ports of the initialization graph are computed and their values are used as the values of the port group OL on the first iteration (if any) of the loop body graph. The loop body graph computes its output ports, for each instance of the port group D, generated by the range generator graph. The return statement graph is computed after each loop iteration and after the last iteration, its output port values are used as the values of the compound node. Before the next iteration, the values from the port group L are copied to the ports of the group OL. The return statement graph contains the reduction nodes that can only (and only they can) supply values to the output ports of this graph. These reduction nodes directly correspond to one-dimensional reductions of Sisal 3.2 and have an additional memory associated with them between loop iterations.
Slide 17: Sisal 3.2 language structure decomposition 161 The range generator graph also has the unique Scatter nodes that can only (and only they can) supply values to the output ports of this graph. The Scatter node has one input and two output ports. The input port has a type of the array or stream of the type T. The first output port has the type T and the second output port has the integer type. The Scatter node sequentially emits a new array or stream element with its index for every loop iteration. If there are several Scatter nodes, then they emit new values simultaneously until at least one of them can do it, while the others that cannot, return the error values. The compound node Forall can represent any one-dimensional for expression, which is controlled with a range. 2.4 Decomposition of the case expression The conditional expression case is naturally decomposed into the conditional expression if with additional elseif branches. Since the if expression with arbitrary number of elseif branches can be already explicitly expressed by the IF1 language, its further simplification is not performed by the Sisal 3.2 front-end compiler and is not shown in this paper. Every selection list of the case expression is transformed into one if or elseif condition using logical disjunction and conjunction operations over the comparison operation results: equality (=), “less than or equal to” (≤) and “greater than or equal to” ( ≥ ). For expressions “ case tag'' and “case type”, the infix operation tag (tag function of Sisal 90) and the expression “type[…]” are used, respectively. 2.5 Decomposition of the multidimensional loops Let us consider the following n-ary m-dimensional loop, where each reduction corresponds to one loop dimension (for the simplicity of further notation): for D1 cross D2 repeat B returns RN1 of RV1; …; RNn of RVn end for The name D1 denotes the loop range generator part without the operator cross and multidimensional indices of the at construction, the name D2 denotes the remaining part of the range generator, the name RNi (i ∈1,…, n)
Slide 18: 162 V.N. Kasyanov, A.P. Stasenko denotes the reduction name with possible initial values and the name RVi denotes reduction loop values. In that notation m-dimensional loop expression can be decomposed into the following two loop expressions of dimensions 1 and m–1: for D1 repeat x1 ,..., xn := for D2 repeat B returns RN1’ of RV1; …; RNn’ of RVn end for returns RN1” of RV1; …; RNn” of RVn end for The name xi here and any other name with overline without a special note later denote any unique name. The names RN’i and RN”i depend on the name RNi as shown in Table 2.2. Table 2.2. Decomposition rules for multi-dimensional reductions, that show how to determine the names RN'i and RN''i, which are used in this section before, from the name RNi Value of the RNi.name RN'i Equals to value, product, least, greatest, caten- RNi ate, ''catenate(…)'' or user-defined reduction. Equals to ''array[k](i1,…, ik)'', where k>1 - part ''[k]'' is optional and equals to ''[m]'' by array[k-1](i2, …, ik) default; k=1 - last indices of the part ''(i1,…, ik)'' are option- array[1](i2, …, ik) al like this whole part and equal to 1 if omitted. Equals to ''stream[k]'' where part ''[k]'' is op- k>1 stream [k-1] tional and equals to ''[m]'' by default. k=1 stream [1] RN''i value array(i1) catenate(i1) stream catenate If the range generator contains multidimensional indices “n in S at j1, …” before the operator cross, then the multidimensional loop can be represented in the following way: for D3 n in S at j1, D4 repeat B returns RN1 of RV1; …; RNn of RVn end for The name D3 denotes the range generator part without the operator cross and multidimensional indices of the construction at, the name S denotes the array or stream source of multidimensional indices, the name D4 denotes the remaining part of the range generator. In that notation m-dimensional loop expression can also be decomposed into the following two loop
Slide 19: Sisal 3.2 language structure decomposition 163 expressions of dimensions 1 and m-1 (where the names RN'i and RN''i depend on the name RNi as shown in Table 2.2): for D3 n in S at j1,repeat x1 ,..., xn := for n in n1 at D4 repeat B returns RN1’ of RV1; …; RNn’ of RVn end for returns RN1” of x1 ; …; RNn” of xn end for 2.6 Decomposition of the array element selection Let us represent the element selection expression from the array A as “A [selection construction]”. If a selection construction does not have the cross (or comma) operator, then it can be represented as “D1 dot D2 dot … dot Dm”, where m ≥ 1 and all expressions D1, D2, …, Dm are ranges (as required by the operator dot semantics). If m = 1 and the part D1 is a singlet, then the array element selection operation can be represented directly in the IR1 and does not require further decomposition, otherwise the array element selection operation can be decomposed into the following one-dimensional loop: for x1 in D1 dot x2 in D2 dot … xm in Dm A1 := A [x1, x2 , …, xm] returns array of A1 end for The name xi (here and later) denotes any unique name, if the part Di does not have the form “name N in Di”, and denotes the name N otherwise. If the selection construction contains the operator cross (or comma), then it can be represented as “S1, S2, …, Sm cross C1” or “D1 dot D2 dot … dot Dm cross C2”, where S1, S2, …, Sm denote singlets and the names C1 and C2 denote the remaining parts of the selection construction and additionally the part C1 does not begin with a singlet. The array element selection operation beginning with a singlet can be decomposed into the following let expression (further decompositions need to be applied recursively): let A1 := A [S1, S2, …, Sm] in A1 [ C1] end let
Slide 20: 164 V.N. Kasyanov, A.P. Stasenko The array element selection operation beginning with a range can be decomposed into the following one-dimensional loop (further decompositions need to be applied recursively): for x1 in D1 dot x2 in D2 dot … xm in Dm repeat A1 := A [x1, x2 , …, xm] returns array of A1 [C2] end for The presented decomposition of the array element selection operation also explains the additional restriction, which is missed in Sisal 90 user manual, for the selection construction triplets with omitted parts: they must be placed as the first operand of the selection construction or just after the cross operator. In the range D1 the first and second omitted triplet parts are explicitly represented via “liml(A)” and “limh(A)”, correspondingly. In the ranges D2, …., Dm the triplet parts cannot be omitted because there is no corresponding univocal array dimension available whose lower and upper bounds can be taken. In summary, any array element selection operation was decomposed into the array element selection with simple indices. 2.7 Array element replacement with a singlet list selection construction This section continues to use the notation of selection construction introduced before. The array element replacement expression in a general form looks like “A[selection construction:= replacement construction]”. As it shown further, any array element replacement expression can be decomposed into the array one-element replacement with simple index. If the selection construction is a singlet list S1, S2, …, Sn, then the replacement construction is allowed to be the expression E1, …, Et and the array element replacement operation is elementary represented as a composition of the following one-element replacement operations: A[S1, S2,…, Sn := E1][S1, S2,…, (Sn)+1:= E2] … [S1, S2,…, (Sn)+(t-1):= Et]
Slide 21: Sisal 3.2 language structure decomposition 165 2.8 Array element replacement with a scalar replacement construction Let us consider the case then the selection construction is not a singlet list and the replacement construction is an expression of type of the n-th dimension of the array A, where n is the number of the selection construction ranges and singlets. In this case, the array element replacement operation can be decomposed into nested one-dimensional loops, obtained after the recursive application of the decompositions given below. If the selection construction does not have the cross (or comma) operator, the array element replacement operation can be decomposed into the following one-dimensional loop: for x1 in D1 dot x2 in D2 dot … xm in Dm A:= old A [x1, x2 , …, xm := replacement construction] returns value of A end for The array element replacement operation beginning with a singlet can be decomposed into the following let expression (further decompositions need to be applied recursively): let A1 := A [S1, S2, …, Sm] in A1 [C1 := replacement construction] end let The array element replacement operation beginning with a range can be decomposed into the following one-dimensional loop (further decompositions need to be applied recursively): let A1 := A in for x1 in D1 dot x2 in D2 dot … xm in Dm A2 := old A1 [x1, x2 , …, xm ] A3 := A2 [ C2 := replacement construction ] A1 := old A1 [x1, x2 , …, xm := A3 ] returns value of A1 end for end let
Slide 22: 166 V.N. Kasyanov, A.P. Stasenko 2.9 Array element replacement with array replacement construction Let us consider the case then the selection construction is not a singlet list and the replacement construction is an expression of type of a k-dimensional array of elements that have the type of the n-th dimension of the array A. In the considered case, k should be a sum of ranges in the selection construction minus the number of its dot operators. In this case, the array element replacement operation can be also decomposed into nested one-dimensional loops, obtained after the recursive application of decompositions given below. If the selection construction does not have the cross (or comma) operator, the array element replacement operation can be decomposed into the following one-dimensional loop: let i := 1 in for x1 in D1 dot x2 in D2 dot … xm in Dm A := old A [ x1, x2 , …, xm := (replacement construction)[ i ] ]; := old i + 1 i returns value of A end for end let The array element replacement operation beginning with a singlet can be decomposed into the following let expression (further decompositions need to be applied recursively): let A1 := A[S1, S2, …, Sm ] in A1 [C1 := replacement construction] end let The array element replacement operation beginning with a range can be decomposed into the following one-dimensional loop (further decompositions need to be applied recursively): let A1 := A; i := 1 in for x1 in D1 dot x2 in D2 dot … xm in Dm A2 := old A1 [x1, x2 , …, xm ]
Slide 23: Sisal 3.2 language structure decomposition 167 A3 := A2 [C2 := (replacement construction)][ i ]]; A1 := old A1 [x1, x2 , …, xm := A3 ] i := old i + 1 returns value of A1 end for end let 2.10 Decomposition of the where expression The Sisal 3.2 where expression is decomposed into nested one-dimensional loops in the following way, where A, n, R and I are some values for A1 in A returns array of for A2 in A1 returns array of … for I in An−1 returns array of expression R end for … end for end for 2.11 Decomposition of the vector operations All vector operations are decomposed into one-dimensional loops. An operation on multidimensional vectors is decomposed into a vector operation on vectors of lower dimensions. Prefix and postfix operations on arrays op(A) decompose into: for i in A returns array (liml(A)) of op( i ) end for Prefix and postfix operations on streams op(S) decompose into: for i in S returns stream of op( i ) end for An infix operation op on two arrays A1 and A2 decomposes into:
Slide 24: 168 V.N. Kasyanov, A.P. Stasenko for i1 in A1 dot i 2 in A2 returns array of i1 op i 2 end for An infix operation op on array A and stream S decomposes into: for i a in A dot i s in S returns stream of i a op i s end for An infix operation op on array A and scalar value V decomposes into: for i in A returns array (liml(A)) of i op V end for An infix operation op on stream S and scalar value V decomposes into: for i in S returns stream of i op V end for 2.12 Conclusion In the paper the intermediate language IR1 of the functional programming system SFP for supporting supercomputing has been briefly presented. During translation from Sisal 3.2 to the internal representation IR1 some complex Sisal 3.2 language structures need to be reduced to more unified objects of the IR1-language. These transformations have been shown in the terms of Sisal 3.2 by the decomposition of complex language structures into more simple ones that can be directly represented by IR1. The transformations are performed by the front-end compiler and help to better understand its translation strategy. They can be used also as a basis for formal description of semantics of the Sisal 3.2 language. For a general-purpose machine (without any special hardware support for the operations considered in this paper), the described transformations do not introduce unnecessary inefficiency and open additional optimization opportunities. Acknowledgments. The authors are thankful to all colleagues taking part in the SFP project. The work was partially supported by the Russian Foundation for Basic Research under grant N 07-07-12050.
Slide 25: Sisal 3.2 language structure decomposition 169 References 1. Backus J (1978) Can programming be liberated from the von Neumann style? Commun ACM 21:613–641 2. Cann D (1992) Retire Fortran? A debate rekindled. Commun ACM 35:81–89 3. Gaudiot J–L, DeBoni T, Feo J, Bohm W, Najjar W, Miller P (2001) The Sisal project: real world functional programming. Lecture Notes in Computer Science 1808:45–72 4. Feo J, et al (1995) SISAL 90. In: Proc. High Performance Functional Computing, Denver, pp 35–47 5. Stasenko AP, Sinyakov AI (2006) Basic means of the Sisa 3.1 language (in Russian). Preprint N 132, A.P. Ershov Institute of Informatics Systems, Novosibirsk 6. Kasyanov VN, Stasenko AP, Gluhankov MP, Dortman PA, Pyjov KA, Sinyakov AI (2006) SFP – An interactive visual environment for supporting of functional programming and supercomputing. WSEAS Transactions on Computers 5:2063–2070 7. Kasyanov VN, Biryukova YuV, Evstigneev VA (2001) A functional language SISAL 3.0 (in Russian). In: Supercomputing support and Internet-oriented technologies, Novosibirsk, pp 54–67 8. Stasenko AP (2004) Internal representation of functional programming system SISAL 3.0 (in Russian). Preprint N 110, A.P. Ershov Institute of Informatics Systems, Novosibirsk 9. Skedzielewski SK, Glauert J (1985) IF1 – An intermediate form for applicative languages, version 1.0. Tech. Rep. M-170, Lawrence Livermore National Laboratory, Livermore, CA 10. Kasyanov VN, Lisitsyn IA (2000) Hierarchical graph models and visual processing. In: Proc. of Intern. Conf. on Software: Theory and Practice, 16th IFIP World Computer Congress, PHEI, Beijing, pp 179–182
Slide 26: Chapter 3 An embedded application for driverless metro train 1 Vivek Kumar Sehgal, Nitin 1 2 2 Member IEEE and ACM, Department of ECE, Member IEEE and ACM, Department of CSE and IT, Jaypee University of Information Technology, Waknaghat, Solan–173215, Himachal Pradesh, INDIA {vivekseh,delnitin}@gmail.com Abstract. We developed an embedded platform with 8-bit microcontroller 89C51 to implement driverless Metro Train. This sort of work is first time reported in India. Keywords. Embedded 8-bit processor, Stepper motor, Liquid Crystal Display, Assembly Language, UMPS 3.1 Introduction Automated Software Controlled Train Simulation (ASCTS) is an example for implementation of a general-purpose rail vehicle application. The trains are equipped with a Central Processing Unit. A human administrator, if required can also access the controls. The train is programmed for a specific path. Each station is well defined i.e. stoppage timing of the train and distance between stations is predefined. ASCTS is built over the Atmel processor 8051, an 8-bit microcontroller with 4KB of on chip ROM, 128 Bytes of RAM, 2 timers and 32 I/0 pins. The motion of the train is con-
Slide 27: An embedded application for driverless metro train 171 trolled by a Stepper Motor and for display of messages intelligent Liquid Crystal Display is used. Since we use software control, the benefit is that the hardware can be standardized i.e. hardware for a new model becomes a question of selecting units from a library of existing units [1].The design is under research and we propose to add more features to it also. The simulator would have more of user-defined variables. Reports would be generated for multiple trains on a single track [2]. This sort of real time implementation would pave a way to the success of country by reducing time complexity as well as increasing reliability. The rest of the paper is organized as follows: Section 3.2 describes the working of designed application and hardware used in it with schematic diagram. Section 3.3 describes the hardware implementation for this embedded application. Section 3.4 describes the assembly language code and software for implementation and Section 3.5 describes Challenges followed by conclusion and future scope.
Slide 28: 172 Vivek Kumar Sehgal, Nitin Fig. 3.1. Flow diagram of embedded application 3.2 Experimental Set Up of train control system The train system is functioned as according to the flow diagram shown in Figure 3.1 and the embedded platform for this automated application is designed as according to the circuit shown in Figure 3.2. Here we are taking examples of two stations, Shimla (2800m from sea level) and Kalka, two hill stations in Himachal Pradesh in India. Initially the train starts at a station “Shimla”, then blows a buzzer and starts moving for a predefined time of 6 s to next station “Kalka”. Here the train stops for a predefined interval of 3 s and if emergency brakes are applied then it stays at the station till the brakes are released. Again, it starts moving to the last programmed sta-
Slide 29: An embedded application for driverless metro train 173 tion “New Delhi”, halts for a predefined 3 s and now starts the upward journey or the round trip. An LED displays the direction of the movement. The cycle repeats until the train is stopped finally. Everything is depicted in the flow chart. Fig. 3.2. Schematic diagram for embedded hardware 3.2.1Hardware The ASCTS hardware consists of 1. Atmel’s AT89C51 2. 2X16 Liquid Crystal Display 3. ULN2003 4. A step down transformer: 220:9 for power supply 5. A Buzzer
Slide 30: 174 Vivek Kumar Sehgal, Nitin 3.3 Hardware implementation We implemented the solution in the form of hardware as depicted in the circuit diagram. In the circuit, the LCD display is connected with the P1 of the MC. Control lines are connected with port 3 of the microcontroller. 10K variable resistor controls the contrast of the LCD. A unipolar Stepper motor is used for running of the train. This motor has 5 wires, which are named as A1, B1, A2, B2 and COM. Common line is given at +5V. The other lines can be connected with port 2 of the microcontroller. The ULN 2003 chip derives the stepper motor. This Chip includes Darlington pairs, so that motor can get enough current for its running. This chip requires pull-ups at inputs. Push button is placed at pin no. 12, whose default state is logic 1 & when switch is pressed then logic 0 is applied on the pin. This logic 0 causes 8051 Embedded Processor to be interrupted. 3.3.1The Resulting Hardware Here Figure 3.3 shows the embedded circuitry for Metro Train after implementing our design on the board, and Figure 3.4 shows the side view of running model results i.e. the desired hardware model Fig. 3.3. Embedded circuitry for Metro Train Fig. 3.4. Side view of running model 3.4 Simulations The system programming is done using assembly language. The program handles things as: 1. Displaying interactive messages on the LCD. 2. Giving the right amount of rotations to the stepper motor at regular intervals. 3. Stopping the train for the required time interval.
Slide 31: An embedded application for driverless metro train 175 4. Stopping the train as soon as the passenger activates the emergency braking system. 5. Controlling the forward as well as the backward motion of the train. 6. Calling the subroutines as is required. 3.4.1Assembly code (written on UMPS Version 2.1) The coding of the metro train prototype is given in the assembly language. The program main routines are the routines for running of stepper motor in forward direction as well as in reverse direction. The routines for this purpose are stepperf and stepperb. The code also explains the various subroutines in detail that are called for correct display of interactive messages on the LCD as well as controlling the overall movement of the train on the desired path. data equ p1 busy equ p1.7 rs equ p3.5 rw equ p3.4 en equ p3.3 bzr equ p0.2 ledf equ p0.0 ledb equ p0.1 org 400h ajmp main org 0003h test: mov c,p3.2 jnc halt setb bzr reti halt: clr bzr ;till zero blow on the bzr ajmp test main: mov ie,#00h setb ea setb ex0 here: mov p2,#00h acall ini mov dptr,#show0 acall command mov dptr,#show4 acall read setb bzr acall delay10 acall stepperb mov a,#01h acall command mov dptr,#show1 acall read mov a,#0c0h acall command mov dptr,#show4 acall read clr ledf ;p1.0 acall delay mov a,#01h acall command; Now make memory clear cursor home mov dptr,#show1 acall read setb.ex0 ##### mov a,#0c0h acall command mov dptr, #show3 acall read acall.delay;;Stopage1 time 3 sec Shimla loopa1: acall delay clr bzr acall delay mov a,#01h acall command mov dptr,#show2 acall read mov a,#0c0h acall command mov dptr,#show4 push 01h push p0 push p1 mov r0,#0eh loopr: mov a,#0ffh loopb: mov b,#0ffh loopa: djnz b,loopa djnz 0e0h,loopb djnz r0,loopr pop p1 pop p0 acall read setb bzr acall delay10 acall stepperf mov a,#01h acall command mov dptr,#show1 acall read mov a,#0c0h acall command mov dptr,#show4 acall read acall delay ;Stopage2 time 3 sec Kalka acall delay clr bzr acall delay mov a,#01h acall command mov dptr,#show2 acall read mov a,#0c0h acall command mov dptr,#show5 acall read setb bzr acall delay10 Routine to read data from prog mem read: nex: clr a movc a,@a+dptr cjne a,#'0',aga sjmp down aga: acall display sjmp nex down: ret stepper routine stepperf: acall stepperf mov a,#01h acall command mov dptr,#show1 acall read mov a,#0c0h acall command mov dptr,#show5 acall read acall delay ;Stopage3 time 3 sec New Delhi acall delay clr bzr acall delay setb ledf ; p1.0;off led at p1.0 for forward journey clr ledb ; p1.1 ; 0n Led for back ward journey mov a,#01h acall command mov dptr,#show2 ;display ne Kalka acall read mov a,#0c0h mov a,#0eh acall command mov a,#06h acall command mov a,#01h acall command mov a,#80h acall command ret command: acall ready mov data, a clr rs
Slide 32: 176 Vivek Kumar Sehgal, Nitin pop 01h pop 00h pop acc ret ;Delay stepper delays: push acc push 00h push 01h push p0 push p1 mov a,#0ffh**** loopa1: mov b,#0fh loopb1: djnz b,loopb1 djnz 0e0h,loopa1 pop p1 pop p0 pop 01h pop 00h pop acc ret delay10: mov tmod,#01h mov tcon,#00h mov tl0,#0f0h mov th0,#0f8h setb tr0 no: jnb tf0,no clr tr0 clr tf0 ret push acc push p1 mov a,#88h mov r1,#04h loop1: mov r0,#0e0h loop: mov p2,a acall delays rr a djnz r0,loop djnz r1,loop1 pop p1 pop acc ret stepperb: push acc push p1 mov a,#88h mov r1,#04h loop12: mov r0,#0e0h loop0: mov p2,a acall delays ;LCD strobe subroutines ini: mov a,#38h acall command mov a,#38h acall command mov a,#38h acall command mov a,#38h acall command clr rw setb en clr en ret display: acall ready mov data,a setb rs clr rw setb en clr en ret ready: clr en mov data,#0ffh clr rs setb rw wait: clr en setb en jb busy,wait clr en ret end acall read acall delay ;Stopage2 time 3 sec Kalka acall delay clr bzr acall delay mov a,#01h acall command movdptr,#show2 ;display ne Shimla acall read mov a,#0c0h acall command mov dptr,#show3 acall read setb bzr acall delay10 acall stepperb mov a,#01h acall command mov dptr,#show1 acall read mov a,#0c0h acall command mov dptr,#show3 acall read setb ledb ;p1.1 ljmp here ;routine for stepper motor ;Delay Routine delay: push acc push 00h 3.5 Challenges The domain of railways represents a huge variety of possibilities for applications of software. The realm of automatic control interacts strongly with many facets of statistics gathering, planning, train scheduling, resource allocation etc [3]. The field of computing science provides design tools, techniques, principles and methods that allow classical automatic control engineering designs to link up to more modern operations analysis, graph theoretic and combinatorial resource optimization [4]. 3.6 Conclusion and future scope of this model We developed an embedded platform with 8-bit microcontroller 89C51 to implement driverless metro train. This sort of work is first of its kind in India. This sort of system could make the railways network more efficient and reliable.
Slide 33: An embedded application for driverless metro train 177 Optimum throughput can be achieved through the mapping of tracks. Another feature of the system could be implementation of vital remote controls on software. We need to define safe failures also in the control system. A safe failure occurs when the failure of a component in a processing system is detected and the effect of the failure emerges as a safeside operation [4]. In the railway application, the safe-side failures are defined for the outputs of the controller. Failures in wayside control functions can be safely handled by shutting down the microprocessor-based controller. In addition, Adhoc methodologies to safety-critical design can be implemented in these systems to ensure safety and fault-tolerant operation. Acknowledgement. This model got the Third Prize at The Annual Techfest – TROIKA 2007, Sponsored by IEEE and IEE Student Chapters of Delhi College of Engineering at DCE, New Delhi in INDIA. References 1. Astrom P (1992) Control electronics on rail vehicles. In: Proceedings of the ASME/IEEE Spring Joint Railroad Conference, pp 107-116 2. Gordon SP, Leherer DG (1998) Coordinated train control and energy management control strategies. In: Proceedings of the 1998 ASME/IEEE Joint Railroad Conference, Philadelphia, PA, USA, pp 165-176 3. Raymond Abrial Jean (2000) Formal software techniques in Railway Systems. In: Proc. 9th IFAC Symposium on Control in Transportation Systems, Braunschweig, Germany, pp 1-12 4. Hachiga A (1993) The concepts and technologies of dependable and real time computer systems for Shinkansen train control. Dependable computing and fault tolerant systems, Springer Verlag, Berlin, pp 225-252 5. Mazidi MA, Mazidi JG (2006) 8051 microcontroller and embedded system. Prentice Hall
Slide 34: Chapter 4 A post-mortem JavaSpaces debugger Jason Howarth, Edward Stow School of Computing and Mathematics, Charles Sturt University, Boorooma St. Wagga Wagga, NSW Australia 2678 Abstract. We describe a post-mortem debugger called JavaSpaces Debugger (JSD) that is able to detect a class of properties that occur in a distributed JavaSpaces program. To detect a property using JSD, the user specifies a global predicate to be evaluated. This global predicate is divided into a series of local predicates that are evaluated by each system node. During execution, an event message is sent to the debugger whenever one of these local predicates is true. The debugger arranges event messages according to logical time, and reports whether the global predicate occurred. JSD can detect both weak and strong unstable predicates, using integer, boolean, or bytecode expressions. Keywords. JavaSpaces, Jini, distributed debugging, strong unstable predicates, weak unstable predicates, vector clock, Java Virtual Machine, Java Virtual Machine Debugging Interface 4.1 Introduction Distributed computing systems are characterised by the absence of a global time base, unpredictable message delays, and the dispersion of program state amongst nodes [10]. This makes it difficult to capture and analyse the state of such systems.
Slide 35: A post-mortem JavaSpaces debugger 179 We describe JSD (JavaSpaces Debugger), a debugger able to overcome some of these limitations. JSD is used to detect a class of properties that occur in a distributed JavaSpaces program. To detect a property using JSD, the user first specifies a global predicate to be evaluated. This global predicate is divided into a series of local predicates that are evaluated by each system node. During execution, an event message is sent to a global checker process whenever one of the local predicates is true. The checker process arranges these messages according to logical time, and reports whether the global predicate occurred. JSD is used to detect global predicates classified as unstable. An unstable predicate is one that may alternate between true and false during execution. Unstable predicates may be either weak or strong [5, 6]. A strong unstable predicate, where true, defines a property that certainly occurred in an observed run of the monitored program. A weak unstable predicate, where true, specifies a property that may have occurred, but which cannot be proven. JSD can detect both strong and weak unstable predicates. 4.2 Background The following sections contain a brief background on the technologies and algorithms used in our debugger. 4.2.1JavaSpaces JavaSpaces is based on the shared-memory model of distributed computing [1]. Instead of cooperating directly, processes exchange Java objects through a network storage area, called a JavaSpace. This makes JavaSpaces different to the message-exchanging framework common to many distributed systems. JavaSpaces has been used for cluster computing [2], software agent systems [11] and distributed programming generally [3]. The main operations performed on a JavaSpace are write, read, take, and notify. The write method deposits an object in the JavaSpace. To read an entry, it is necessary to supply a template object to match against. If a match is found, a copy of the matched object is returned from the JavaSpace. The take method acts the same as read, except the entry is deleted from the JavaSpace. The notify method allows a process to register interest in future entries that appear.
Slide 36: 180 Jason Howarth, Edward Stow Although the JavaSpaces API (Application Programmer’s Interface) is minimal, complex distributed algorithms can be constructed via the flow of objects in and out of JavaSpaces [4]. 4.2.2Jini JavaSpaces rests upon the Jini foundation, a technology used to create networked communities of software and hardware services. JavaSpaces is provided as a standard Jini service. Like all Jini services, JavaSpaces is used through its service proxy, which is stored at a Jini Lookup Service. The Lookup Service is a registry of all currently active services available within a Jini community. To retrieve a service proxy, the lookup repository is searched for services matching certain criteria. For example, to retrieve the JavaSpaces proxy, a client might search the Lookup Service for a proxy with a name attribute of ‘JavaSpaces’. Once the client has the proxy, it can make local method calls on this object to access the backend service. JavaSpaces plays an important role in the overall Jini architecture by providing a network storage facility. This allows Jini clients to store objects centrally, as well as allowing clients to communicate via the flow of objects in and out of the JavaSpace. 4.2.3Weak Unstable Predicates We turn to an approach for detecting weak unstable predicates. Such predicates may be either conjunctive or disjunctive. A conjunctive predicate is of the form s(i) ^ s(j) ^ s(k), where s(i) represents the local state of process i, s(j) the local state of process j, etc. This paper will focus only on conjunctive predicates. Disjunctive predicates are trivial to detect since only local state must be monitored [5]. The algorithm [5] relies on each process checking its local portion of the predicate. For example, if the predicate is x=1 ^ y=2 for two variables x and y held at processes P1 and P2 respectively, then process P1 monitors x, and process P2 monitors y. When a local predicate becomes true, the current vector clock timestamp is sent by the local process to a global checker process. Once computation has ended, the checker process evaluates the global predicate to see whether both local predicates could have occurred concurrently. The weak conjunctive predicate a ^ b is true if a and b occur concurrently in the program trace [5]. The implementation of this algorithm requires a special type of vector clock, called an lcmvector (last causal message vector) [5]. An lcmvector
Slide 37: A post-mortem JavaSpaces debugger 181 consists of a vector of n integers, one for each process. Each process is responsible for maintaining its own vector. For a system with three processes, the lcmvector stored at process Pi takes the form [Ci, Cj, Ck], where Ci is the clock that measures progress at Pi, and Cj and Ck are set to values advised by processes Pj and Pk, respectively. The operations permitted on an lcmvector are initialisation <init>, increment <incr>, and synchronization <synch>. Initially, the values in each vector are set to 0. The <init> operation occurs at process startup, where each process Pi sets its clock value to i = 1. Whenever a message is sent, the <incr> operation is performed. For a process Pi, this involves incrementing its clock by one (Ci = Ci + 1). When a message is received, the synchronize operation is invoked. This means that the receiving process performs the componentwise maximum operation, using as input its own clock and the clock of the process sending the message. To implement the algorithm, lcmvectors are passed between processes when a message is sent. Operations on lcmvectors are depicted as occurring between states. Process events have the clock value that appears before the event. Hence in Figure 4.1, events a and b both have the vector time stamp {1, 0}. Fig. 4.1. Events measured using lcmvectors Vector clocks are compared using a type of vector clock algebra, based on the happened before [8] relation ( ⇒ ). Vector clocks are considered concurrent ( ⇔ ) if the happened before relation cannot be established. Consider two clocks V1 and V2. Based on the values contained in these clocks, the following holds true: V1 ⇒ V2 if V1 != V2 and if each value in V1 is less than or equal to each value in V2 V2 ⇒ V1 if V1 != V2 and if each value in V1 is greater than or equal to each value in V2 V1 ⇔ V2 if neither V1 ⇒ V2 nor V2 ⇒ V1
Slide 38: 182 Jason Howarth, Edward Stow Applying these rules to the example in Figure 4.1, we can assert that e ⇒ c, and that c ⇔ f. We turn to the checker process to see how the global predicate is evaluated. The checker process enqueues clock values received as <debug> messages (Figure 4.2) whenever a portion of the global predicate is detected locally. For example, if the global predicate is x = 4 ^ y = 3, process P1 sends a message to checker process C whenever its portion of the predicate is true (see Figure 4.2); process P2 does likewise. The messages sent to the checker process C contain the timestamps associated with detection of the local predicate. The checker process uses the vector clock comparison rules to decide if the predicate is true. In the case of a weak unstable predicate, the predicate i ^ j is true if i ⇔ j [5]. Fig. 4.2. Time-stamped debug messages sent to the checker process 4.2.4Strong unstable predicates Strong conjunctive predicates are of the form s(i) ^ s(j) ^ s(k), where s(i) represents the local state of process i, s(j) the local state of process j, and so on. In detecting such predicates, we rely on the notion of intervals [6]. An interval is a pair of vector clocks that delineate a period during which the predicate was true. In the following discussion, clock_lo refers to the start, and clock_hi to the end of an interval. Consider two processes with a boolean variable ready_to_commit. Assume it must be determined if there is a point when these processes on Hosts A and B are simultaneously ready to commit. To achieve this, it must be determined if the intervals where the predicate is detected on each host overlap.
Slide 39: A post-mortem JavaSpaces debugger 183 For example, assume host A is ready to commit during the interval {2, 1} to {4, 2}, and host B during the interval {0, 1} to {2, 2}. If these intervals overlap, then there must have been a time when the global predicate (i.e., when both hosts were simultaneously ready to commit) is also true. To determine overlap, the rules for comparing vector clocks are applied to see if host A.clock_lo ⇒ host B.clock_hi AND host B.clock_lo ⇒ host. clock_hi. If so, these intervals have overlapped in (logical) time and the global predicate must have occurred [6]. In the example above, since {2, 1} ⇒ {2, 2} and {0, 1} ⇒ {4, 2}, these intervals overlap, and it is certain that the global predicate was true at some point in the computation. 4.3 JSD architecture A feature of JSD is the level of indirection added to the JavaSpaces architecture to capture debugging information. A typical JavaSpaces client interacts with the JavaSpace using the JavaSpaces proxy. In JSD, the debugged host is modified to load a different proxy, called the debugging proxy. The debugging proxy does not communicate directly with the JavaSpace; instead, it routes messages through another proxy-like object, JSDebugSpace. JSDebugSpace is a custom-written Jini service used to filter messages intended for the real JavaSpace. Information is captured about these messages before they are passed to the JavaSpace for normal processing. Similarly, when a message is returned from the JavaSpace, it returns through JSDebugSpace before it is handed back to the debugged application. By this means, debugging control is interposed between the debugged program and the JavaSpace. Both JSDebugSpace and the debugging proxy on each host maintain a lcmvector clock to order system events. These clocks are exchanged between the proxy and JSDebugSpace whenever a JavaSpaces call is made. By this means, clocks in the debugged system are kept current through the increment and synchronization methods described earlier. To monitor the local predicate, the debugging proxy loads a DLL (dynamic link library) on the host being debugged. This DLL uses the JVMDI (Java Virtual Machine Debugger Interface) [7]. The DLL is passed details of the predicate to watch. Based on the contents of this predicate, it then registers for watchpoint events with the local JVM. When such an event occurs, the JVM notifies the DLL, which in turn notifies a checker process with the lcmvector reading at the local host. These readings are put in a queue maintained by the checker process. The contents of this queue are
Slide 40: 184 Jason Howarth, Edward Stow later used to reconstruct the event sequence that occurred during monitoring. Once the debugged program ends, the truth of the global predicate first entered by the user can be determined. 4.3.1Predicate detection language We have designed a simple language called JPL (JavaSpaces Predicate Language) to submit predicates to our debugger. JPL is used to express a predicate containing either integer or boolean values. A bytecode index can also be specified. An integer or boolean predicate takes the form hostname: class name: variable operator result [^]. The ^ symbol is the conjunctive operator, used to chain local predicates into a single global predicate. To give an example, the following predicate seeks to determine if variables x and y, at different hosts in the system, are ever equal to 10 at the same point in the computation: Host A: Adder: x = 10 ^ Host B: Subtractor: y = 10. The local predicates in this example are Host A: Adder: x = 10 and Host B: Subtractor: y = 10. The variables x and y are declared in classes Adder and Subtractor, respectively. JPL also allows predicates that contain more complex expressions. All of the basic mathematical operators are supported. In addition, a boolean predicate can use greater-than or less-than logic, such as Adder: i > 5 ^ Subtractor: j < 3. The other type of predicate is the bytecode predicate, which has the structure hostname: break: class name: method name: bytecode index [^]. An example is Host A: break: Adder: increment: 44 ^ Host B: break: Subtractor: decrement: 23. This is asking: when class Adder hits bytecode index 44 in the increment method, is it true that class Subtractor hits bytecode index 23 simultaneously in the decrement method? We believe bytecode predicates offer an advantage over integer and boolean predicates because a variable need not exist in the application being debugged to perform predicate evaluation. 4.4 JSD example The example we describe is based on a simple chat program that consists of a Listener and two Talkers. To send a message to the Listener, a Talker must first hold an exclusive token T. This token is exchanged between each Talker via a JavaSpace. The Listener is notified through the JavaSpaces notify method whenever a message is written to space. Our concern
Slide 41: A post-mortem JavaSpaces debugger 185 here is with the token, which should not simultaneously be held by more than one Talker. The predicate for this is as follows: Host A: Talker: hasToken = true ^ Host B: Talker: hasToken = true. If this predicate is true, there is a problem with our algorithm because there is a chance that both hosts can talk at once. The setup is as follows. Hosts Sun and Moon each run a Talker process (Figure 4.3). In this test, Sun.Talker was started first, followed by Moon.Talker. We assume that the token has already been written to the JavaSpace, and contains the name of the host who has first possession. This host takes the token, sends a message to the Listener (not shown), then releases the token again, addressed to the next recipient who performs the same set of actions. SUN (1) take MOON (3) take JavaSpace (2) write Token T (4) write Fig. 4.3. Hosts Sun and Moon take and write the token After running the test, the following values appear in the local predicates screen of JSD: Sun Talker:hasToken = true {2,0,1} Moon Talker:hasToken = true {2,2,3} This shows that each local predicate was true when the lcmvector readings were {2, 0, 1} and {2, 2, 3}, respectively. The three readings in each lcmvector indicate that three clocks were used in this debugging session, one for each host and one for the JavaSpace. We are now in a position to determine whether the weak predicate was true during this run of the program. To do this, we must determine if it were possible for readings {2, 0, 1} and {2, 2, 3} to have occurred concurrently. When we compare these clocks, we find that {2, 0, 1} ⇒ { 2, 2, 3}, which means that the weak conjunctive predicate is false, at least under the scenario where host Sun is started first. In this example, the source code on both hosts contains the boolean variable hasToken = true for use in detecting the predicate. If this variable did not exist the predicate could not be assessed. Unfortunately, many distrib-
Slide 42: 186 Jason Howarth, Edward Stow uted debuggers [3, 9] assume such a variable. JSD overcomes this limitation by allowing the user to specify a bytecode index instead of a variable when constructing the predicate. We next apply a strong conjunctive predicate to the same scenario - this time to see if it was definitely the case that, at some point in the computation, Sun had the token and Moon did not. The predicate to express this is Sun: Talker: hasToken = true ^ Moon: Talker: hasToken = false. Only one round of token passing is used, and Moon is started before Sun. Once the test is run, JSD reports the following intervals: Sun Talker: hasToken = true [{2,1,1} {3,1,2}] Moon Talker:hasToken = false [{0,1,0} {2,2,3}] JSD reports that the strong conjunctive predicate is true because intervals {[2, 1, 1] [3, 1, 2,]} and {[0, 1, 0] [2, 2, 3]} overlap. In general, however, due to the loosely-coupled nature of JavaSpaces, a strong conjunctive predicate will never be true unless the processes named in the predicate are both active in the same JavaSpace at the same (physical) time. A time overlap only occurs when both processes are engaged in a common task – that is, when both simultaneously interact with the JavaSpace. This makes strong conjunctive predicates much less useful than weak conjunctive predicates in a JavaSpaces environment. 4.5 Conclusion We have described JSD, a debugger able to detect both weak and strong unstable predicates in a JavaSpaces program, using the algorithms of [5, 6]. MaX [9], a distributed debugger framework for a Java/CORBA environment, also uses these algorithms. There are several important differences between MaX and our debugger, including the ability of JSD to detect bytecode predicates. Our design also offers fewer overheads than MaX because only one process per machine is needed to run both the original program and the predicate detection algorithms. Hence, our debugger is in process, whereas MaX is out-of-process. The JavaSpaces debugger described in [3] is used to capture message activity between the proxy and the JavaSpace. We believe our approach is superior because, in addition to capturing message activity, JSD can arrange these messages into a global sequence, as well as detect strong and weak conjunctive predicates.
Slide 43: A post-mortem JavaSpaces debugger 187 Many enhancements could be made to JSD. Debugging data could be saved in XML format to compare debugging sessions. This would offer a more complete picture than is currently provided. Any predicate judged against this additional data would have more validity than one judged against a single program run. The architecture might also be adapted to an RMI or CORBA environment so that debugging on each host is directed by stub objects, rather than by a Jini proxy. Acknowledgement. The authors gratefully acknowledge the valuable comments provided on an early draft of this paper by Dr. Barney Dalgarno of Charles Sturt University, Wagga Wagga. References 1. Attiya H (1998) Distributed computing theory. In: Zomaya A (ed) Parallel and distributed computing handbook. McGraw-Hill, New York 2. Batheja J, Parashar M (2001) Adaptive cluster computing using JavaSpaces. Research Report, Dept. of Electrical and Computer Engineering, Rutgers University, New Jersey 3. Bishop P, Warren N (2003) Javaspaces in practice. Addison-Wesley, London 4. Freeman E, Hupfer S, Arnold K (1999) JavaSpaces: Principles, patterns and practice. Addison-Wesley, Reading, Massachusetts 5. Garg V, Waldecker B (1994) Detection of weak unstable predicates in distributed programs. IEEE Transactions on Parallel and Distributed Systems 5(3):299-307 6. Garg V, Waldecker B (1996) Detection of strong unstable predicates in distributed programs. IEEE Transactions on Parallel and Distributed Systems 7(12):1323-1333 7. Java Platform Debugger Architecture, Sun Microsystems Inc (2002) last viewed May 10, 2007 <http://java.sun.com/j2se/1.4.2/docs/guide/jpda/> 8. Lamport L (1978) Time, clocks and the ordering of events in a distributed system. Communications of the ACM 21(7):558-65 9. Otta M (2001) A distributed debugger framework applicable in a Java/CORBA environment. European Research Seminar on Advances in Distributed Systems, last viewed May 1, 2007 <http://www.cs.unibo.it/ersads/program.html> 10. Stoller S (1997) Detecting global predicates in distributed systems with clocks. In: Proceedings of the 11th International Workshop on Distributed Algorithms (WDAG97), Springer-Verlag, London, pp 185-199 11. Wang A (2002) Using JavaSpaces to implement a mobile multi-agent system. Research Report, Norwegian University of Science and Technology, Trondheim
Slide 44: Chapter 5 Stochastic numerical simulations using C# Edita Kolářová, Csaba Török 1 1 2 Brno University of Technology, Technická 8, 616 00 Brno, Czech Republic 2 Technical University Košice, Letná 9, 042 00 Košice, Slovakia Abstract. This paper considers numerical solutions of stochastic differential equations. The stochastic Euler scheme and the stochastic Milstein scheme are examined. We present two different approaches to implementation of these schemes in the MS .NET Framework. The first one is based on matrices and the second one on delegates. The schemes and the codes are illustrated with an example. Keywords. Stochastic differential equation, Euler scheme, Milstein scheme, C# 5.1 Introduction The effects of intrinsic noise within physical phenomena are ignored when using deterministic differential equations for their modelling. Stochastic differential equations (SDEs) include a random term which describes the randomness of the system as well. A general scalar SDE has the form dX t = F (t , X t ) dt + G (t , X t ) dWt ,
Slide 45: Stochastic numerical simulations using C# 189 where F : 0, T × R → R is the drift coefficient and G : 0, T × R → R is the diffusion coefficient. Wt is the so called Wiener process (see [2]), a stochastic process representing the noise. We can represent the SDE in the integral form X t = X 0 + ∫ F ( s, X s ) ds + ∫ G ( s, X s ) dWs , t0 t0 t t where the first integral is an ordinary Riemann integral. Since the sample paths of a Wiener process do not have bounded variation on any time interval, the second integral cannot be a Riemann-Stieljtes integral. K. Itô proposed a way to overcome this difficulty with the definition of a new type of integral, a stochastic integral which is now called the Itô integral (see [2]). Later R. L. Stratonovich proposed another kind of stochastic integral, called the Stratonovich integral. 5.2 Numerical solutions of SDEs There are two main approaches to numerical solutions. The first one is based on numerical methods for ordinary differential equations (see [5]). The second one uses more information about the Wiener process (see [1]). We give here the formulae for the simplest examples of these two approaches, the Euler and the Milstein methods. A general N-dimensional Itô SDE with an M-dimensional Wiener pro1 M cess Wt = (Wt ,…,Wt ) can be written componentwise as dX ti = F i (t , Xt ) dt + ∑ G i , j (t , Xt ) dWt j , j =1 M i = 1,…, N , where Xt = ( X t1 ,…, X tN ). Let the stochastic process Xt , t0 ≤ t ≤ T be the solution of the multidimensional SDE on t0 ≤ t ≤ T with the initial value Xt0 = X 0 . Let us consider an equidistant discretisation of the time interval tn = t0 + nh, where h = n 0 = tn +1 − tn and the corresponding discretisation of Wiener processes T −t ∆Wnj = Wtnj+1 − Wtnj = ∫ tn+1 tn dWs j , j = 1,…, M . To be able to apply any stochastic numerical scheme, first we have to generate the random incre-
Slide 46: 190 Edita Kolářová, Csaba Török ments of the Wiener processes as independent Gauss random variables j j2 with E[∆Wn ] = 0 and E[(∆Wn ) ] = h. The Euler scheme for the i-th component of the multidimensional SDE has the form i i X n +1 = X n + F i (tn , X n )h + ∑ G i , j (tn , X n )∆Wnj . j =1 M The Milstein scheme for the i-th component of the multidimensional SDE has the form i i X n +1 = X n + F i h + ∑ G i , j ∆Wnj + j =1 M j1 , j2 =1 ∑ M Lj1 G i , j2 ∫ tn+1 tn ∫ t tn dWs j1 dWt j2 j for i = 1,…, N , where the operators Lj are defined by L = ∑G i =1 N i, j ∂ . ∂xi The Euler scheme converges with strong order γ = 1 and the stochastic 2 Milstein scheme converges with strong order γ = 1 (see [1]). 5.3 Numerical experiments using C# In this section we present two different approaches to implementation of the Euler and Milstein methods for numerical solution of SDEs in the MS .NET Framework. The first one is based on matrices and the second one on delegates. To make matrix manipulation and visualization simpler we used the component library LinAlg described in [3]. LinAlg is a set of classes that enables vectorial programming and incorporates a wide range of numerical, statistical and graphical methods. Matrix arguments. The following codelines present the implementation in MS Visual C# of the Euler and Milstein methods described in section 5.2 for the Itô SDE of form dXt = FXt dt + GXt dWt , where X t is an r dimensional vector, F and G are r × r matrices and Wt is a one dimensional Wiener process: static public MatrixD Euler(VectorD X0, MatrixD F, MatrixD G, double h, int n, VectorD w) { MatrixD xM = new MatrixD(X0.Length, n); VectorD xMj = new VectorD(X0); xM.ColumnsSet(0, xMj); double dw;
Slide 47: Stochastic numerical simulations using C# for(int j=1; j<n; j++) { dw = w[j] - w[j-1]; xMj += F*xMj*h + G*xMj*dw; xM.ColumnsSet(j, xMj); } return xM; 191 } static public MatrixD Milstein(VectorD X0, MatrixD F, MatrixD G, MatrixD DG, double h, int n, VectorD w) { MatrixD xM = new MatrixD(X0.Length, n); VectorD xMj = new VectorD(X0); xM.ColumnsSet(0, xMj); double dw; for(int j=1; j<n; j++) { dw = w[j] - w[j-1]; xMj += F*xMj*h + G*xMj*dw + 0.5*DG*G*xMj*(dw*dw-h); xM.ColumnsSet(j, xMj); } return xM; } where the approximant xM of Xt is a matrix and its k -th column contains the approximation of Xt in tk . Delegate arguments. The C# methods, Euler(…) and Milstein(…), presented above, use matrices as arguments to solve the Itô SDE dXt = FXt dt + GXt dWt . Fortunately the MS .NET Framework enables, due to the concept of delegate, the implementation of methods with function arguments that solve the more general equation dXt = F (t , Xt ) dt + G (t , Xt ) dWt . Delegates are type-safe function pointers that can be used to program events, multithreads, asynchron operations or remoting (see [4]). Now we describe shortly in four steps the implementation of the Euler scheme with function arguments (the steps for the Milstein scheme are similar). Step 1: declare a public delegate FuncVec with a given signature (double and VectorD arguments) and VectorD return type: public delegate VectorD FuncVec(double t, VectorD X); Step 2: implement a method EulerDelegate with arguments of FuncVec delegate type: static public MatrixD EulerDelegate(VectorD X0, FuncVec F, FuncVec G, double h, int n, VectorD w) { MatrixD xM = new MatrixD(X0.Length, n); VectorD xMj = new VectorD(X0); xM.ColumnsSet(0, xMj);
Slide 48: 192 Edita Kolářová, Csaba Török double dw; for(int j=1; j<n; j++) { dw = w[j] - w[j-1]; xMj += F(0, xMj)*h + G(0, xMj)*dw; // Delegatefunction argument use xM.ColumnsSet(j, xMj); }return xM; } Step 3: declare new VectorD functions F(…), G(…) with the return type and signature of the FuncVec delegate: static VectorD F(double t, VectorD X) { return -0.5*(new VectorD(X[0], X[1])); // F corresponds to the example } static VectorD G(double t, VectorD X) { return new VectorD(X[1], -X[0]); // G corresponds to the example } Step 4: call the method EulerDelegate(…) with the corresponding wrapped functions F and G as arguments: xy = EulerDelegate(x0, new FuncVec(F), new FuncVec(G), h, n, w); Example. We illustrate the use of these methods on the Itô SDE: dxt = −0.5 xt dt + yt dwt , dyt = −0.5 yt dt − xt dwt . This SDE allows to compare the numerical solution with the analytical solution xt = cos wt and yt = sin wt . The Euler approximation of x and y over 0,1 is computed by the codelines: int n = 100, kernel = 1900317; double T = 1, h = T/n; VectorD x0 = new VectorD(0, 1); MatrixD f, g, xy; f = MatrixD.CreateFromVector (2,2, -0.5, 0, 0,-0.5); g = MatrixD.CreateFromVector (2,2, 0, 1,-1, 0); VectorD wd = Wiener.Create (h, n, kernel); xy = Euler(x0, f, g, h, n, wd); The following pictures show the generated approximation w of the Wiener process wt and the approximants x and y of xt and yt .
Slide 49: Stochastic numerical simulations using C# 193 Fig. 5.1. The approximation of sin( wt ) and cos ( wt ) by the Euler method The next pictures show the approximants x and y based on the Milstein schneme. MatrixD dg= MatrixD.CreateFromVector (2,2, 0, 1,-1, 0); xy=Milstein(x0, f, g, dg, h, n, wd); Fig. 5.2. The approximation of sin( wt ) and cos ( wt ) by the Milstein method Acknowledgements. This research has been supported by the Czech Ministry of Education in the frame of MSM 0021630529 Research Intention Inteligent Systems in Automation. References 1. Kloeden P, Platen E, Schulz (1997) Numerical solution of SDE through computer experiments. Springer –Verlag 2. Oksendal B (1995) Stochastic differential equations – An introduction with applications. Springer-Verlag 3. Török Cs (2004) Visualization and data analysis in the MS .NET Framework. Communication of JINR, Dubna, E10-2004-136 4. Török Cs et al. (2002) Professional Windows GUI Programming: Using C#. Wrox Press Inc, Chicago, ISBN 1-861007-66-3 5. Török Cs (1994) Numerical solution of linear stochastic differential equations. Computers & Mathematics with Applications 27(4):1-10
Slide 50: Chapter 6 Visualization and analyses of multi-dimensional data sets using OLAP- A case study of a student administration system Che-Chern Lin, Fun-Chi Hsu, Chun-Hung Wu, Chia-Jui Hsu, Chia-Hsun 5 6 7 Wu, Chung-Ping Lee, Hung-Jen Yang National Kaohsiung Normal University, 116 Heping First Road, Kaohsiung City, Taiwan (R.O.C.) 1 2 cclin@njknucc.nknu.edu.tw , kyohikaru@msn.com , hans_wu@hotmail.3 4 5 com , chiajuimr@hotmail.com , der54367@msn.com ,7 cl87369@yahoo.6 com.tw , hjyang@nknucc.nknu.edu.tw 1 2 3 4 Abstract. In this paper, we introduce the visualization and analyses of multi-dimensional data sets using on-line analytic processing (OLAP). We discuss three fact table schemas for building data cubes for displaying different views and the levels of details of date sets Five operations of OLAP are used for manipulating data cubes including slice, dice, roll-up, drill-own, and rotation operations By the five operations one can perform extraction, aggregation, sub-dividing, changing perspective of information stored in OLAP data cubes. We present a case study to explain the above operations. In the proposed case study, a student administration system was developed. To build data cubes, we established a constellation schema consisting of three fact tables and four dimension tables. We also demonstrate the five operations on the data cubes and discuss how these operations are applied to analyze data. Keywords. OLAP; Data Cube; Data Warehouse; Multi-dimensional Database
Slide 51: Visualization and analyses of multi-dimensional data sets using OLAP 195 6.1 Introduction Recently with the development of information technologies, huge data can be handled by computers. Based on data bases, many data analysis techniques are developed and applied in different areas. Data warehouse is one of the popular techniques where multi-dimensional data structures are established by extracting different perspective from related normalized data tables in an operational database. To build a data warehouse, people use data cubes to represent the multi-dimensional data structure. Fact tables are utilized to describe the data structures of the data cubes. With the capabilities of handling and displaying the multi-dimensional data sets, data warehouse applications are successfully utilized in data analyses and decision support systems and therefore widely applied in many fields such as business, engineering, education, medicine, etc. Data warehouses are normally utilized to analyze off-line data for making decisions. On-line analytic processing (OLAP) is a similar technique but focuses on analyzing real time data. It retrieves data from an on-line database. Data mining is another information technique to cluster data by creating association rules. It is also widely applied in different areas such as business, engineering, education, and medicine. A cubic-wise balance method for privacy preservation has been proposed to furthermore make closely estimation of data without actual data access [1]. MSMiner, an OLAP development software has been generally discussed including design requirements, system architecture, and an application example [2]. Based on unified modeling language (UML), Prat et al. proposed a data warehouse design methodology with three phases: conceptual, logic, and physical phases [3]. A data warehouse application on site determination was implemented by Ahmad et al. where an OLAPbased decision support system was built to select the most appropriate residential area in Miramar, Florida, U.S.A.. Moon et al. discussed the effectiveness on cost estimation of OLAP-based management systems [4]. Efficient view selection methods for data warehouse were proposed to improve the query time and data storage space [5]. In this paper, we apply the data warehouse technique in education and provide a case study on student administration system where OLAP data cubes were generated for manipulating data.
Slide 52: 196 Che-Chern Lin, Fun-Chi Hsu, Chun-Hung Wu, Chia-Jui Hsu, Chia-Hsun Wu, Chung-Ping Lee, Hung-Jen Yang 6.2 Design of OLAP cubes Relational databases uses normalized tables where relationships among these tables are used to aggregate data from different data and hence get integrated information for views and reports. A table in a relational database is two-dimensional, consisting of fields (columns) to define data attributes of the table and records (rows) to describe the field values for a particular data instance. Normalizations are utilized to generate the normalized tables in a relational database from an original unnormalized data set. During normalization procedure, tables are sequentially divided into smaller tables without losing information. After normalizations, tables are said to be in normal forms. Five normalizations are used to generate five normal forms from first normal form (1NF) to fifth normal form (5NF). To implement the relationships among these tables in a database, people use join operations to integrate different data from different tables using “keys”. Structured query language (SQL) is used to practically realize the join operations using a “select” command. Two keys are generally used in tables: primary key (PK) and foreign key (FK). A PK is used to identify a particular record and to get the rest of field values associated with this particular record. A FK is utilized to link the PK of another table to get more information form the linked table. A table in a relational database only shows the information related the table. Using SQL commands gets some partially integrated data. For decision making, people need total information to analyze data and make decisions. Data warehouses are applied to integrate data from a database in support of subject-oriented data analyses for decision making. Figure 6.1 shows a data warehouse process model [6]. In the figure, a data warehouse obtains its data by using an ETL (extract, transform, and load) routine from differ way including external data, operational database and independent marts. To build a data warehouse, people use fact tables to aggregate different data from dimension tables which provide necessary information for establishing the data warehouse. Similar a PK, a dimension key is used to link a fact table to a dimension table associated with the dimension key. Three types of fact table schemas are often used to build data cubes including: star, snowflake, and constellation schemas. The star schema is the simplest structure of fact table where a single fact table is located at the center of the structure, linking each dimension table with a corresponding dimension key. To decrease data redundancy, a snowflake schema is used to further divide some dimension tables. A constellation schema is another structure where more than one fact table is located at the center of the
Slide 53: Visualization and analyses of multi-dimensional data sets using OLAP 197 structure. In a constellation schema, dimension tables can be multiply linked to fact tables. Based on the techniques of building data warehouses, OLAP is a querybased approach to handle real time data sets for data analyses. Five operations are often applied to perform OLAP including: slice, dice, dill-down, roll-up, and rotation operations. A slice is an operation to perform data retrieval on a single dimension of an OLAP cube. A dice operation is similar to slice operation but focuses on selecting data on two or more dimensions. A roll-up operation performs date generalization by aggregating data on one particular dimension on an OLAP cube. A drill-down operation, a reverse process of roll-up, is used to obtain more detailed data for a particular dimension on an OLAP cube. A rotation simply selects another perspective of an OLAP cube by rotating the displayed dimension without aggregation, sub-dividing, and extraction of the data. 6.3 Case study To demonstrate visualization of multi-dimensional data sets, we present an example of student administration system. Figure 6.2 shows the schema of the proposed example where a constellation schema is used to construct OLAP cubes .Three fact tables are used to form the center parts of the constellation schema including course selection table, score table, and absentation table. In addition to the fact tables, four dimension tables are also utilized to form the OLAP cubes including teacher, class, course and student tables. The detailed fields of the fact tables and dimension tables are also displayed in Figure 6.2. 6.4 Conclusion We introduced the visualization and analyses of multi-dimensional data sets using OLAP. We also discussed three fact table schemas for building data cubes Five operations are discussed for manipulating data cubes including slice, dice, roll-up, drill-own, and rotation operations. We presented an example of a student administration system to explain the above operations. To demonstrate the example, we established OLAP cubes using a constellation schema. As about further studies, we suggest extending the system with more tables and building more complex schema to get more information.
Slide 54: 198 Che-Chern Lin, Fun-Chi Hsu, Chun-Hung Wu, Chia-Jui Hsu, Chia-Hsun Wu, Chung-Ping Lee, Hung-Jen Yang References 1. Liu Y, Sung SY, Xiong H (2000) A cube-wise balance approach for privacy preservation in data cubes. Information Sciences 176:1215-1240 2. Shi Z, Huang Y, He Q, Xu L, Liu S, Qin L, Jia Z, Li J, Huang H, Zhao L (2007) MSMiner- a developing platform for OLAP. Decision Support Systems 42:2016-2028 3. Prat N, Akoka J, Comyn-Wattiau I (2006) A UML-based data warehouse design method. Decision Support Systems 42:1449-1473 4. Ahmad I, Azhar S, Lukauskis P (2004) Development of a decision support system using data warehousing to assist builders/developers in site selection. Automation in Construction Vol. 13:525-542 5. Moon SW, Kim JS, Kwon KN (2007) Effectiveness of OLAP-based cost data management in construction cost estimate. Automation in Construction 16:336-344 6. Roiger RJ, Geatz MW (2003) Data mining: A tutorial-based primer. Addsion Welsley, Pearson Education, Inc., Chapter 6 External Data Dependent Data Mart Extract/Summarize Data Operation al Database( s) ETL Routine (Extract/Transfor m/ Load) Data Warehou se Decision Support System Independe nt Data Mart Report Fig. 6.1. A data warehouse process model (taken from [6])
Slide 55: Visualization and analyses of multi-dimensional data sets using OLAP 199 Teacher table Id Name 32 Zhen-Qin Lin 31 Xi-Yu Jing . . . . … … … . . Class table Id Name YM1 ITE class 1 OCE1 OCE class 1 . . .. . … … … . . Course _selection table Course_id Student_id Teacher_id GI101 D1100016 05019 GI101 D1100025 05019 . . . . . . Class_id YM3 YM3 . . Note (null) (null) . . Score table Course_id Student_id GI101 D1100016 GI101 D1100028 . . . . Teacher_id 05019 05019 . . Class_id YM3 YM3 . . Score 20 54 . . Note Fail Fail . .
Slide 56: 200 Che-Chern Lin, Fun-Chi Hsu, Chun-Hung Wu, Chia-Jui Hsu, Chia-Hsun Wu, Chung-Ping Lee, Hung-Jen Yang Course _id GI101 . . Absentation table Teacher_id Student_id 05019 D1100016 . . . . Class_id YM3 . . Time 2007-12-01 12:20 . . Id D01 DS03 . . Course table Title Basic Design Graphics . . … … … … Id C9461101 C9461103 . . Student table Name Mary Wang Peter Chen . . … … … … Fig. 6.2. The constellation schema of the proposed OLAP cubes
Slide 57: Chapter 7 Design of a computer-based triangle chess machine Che-Chern Lin, Chia-Jung Hsu, Ming-Jun Chan, Chih-Hung Chung, 5 6 Chong-Cheng Hong, Hung-Jen Yang National Kaohsiung Normal University, 116 Heping First Road, Kaohsiung, TAIWAN (R.O.C) 1 2 cclin@nknucc.nknu.edu.tw , z3charles@msn.com4 , 3 taiwanka@yahoo.com.tw , bbc160@yahoo.com.tw , t771580@yahoo.5 6 com.tw , hjyang@nknucc.nknu.edu.tw 1 2 3 4 Abstract. Computer-based chess machines have been built based on tree searches and parallel computing. Several papers have discussed the computer implementations of different types of chess games such as chess (western), Chinese chess (Xiangqi), Japanese chess (Shogi), and Hex. This paper focuses on the implementation of triangle chess machine. We first make a brief explanation on the popular chess games and their related studies. We then describe the rules for playing a triangle chess. Basically, the triangle chess machine proposed in this paper considers all possible configurations of chess patterns and then makes moves based on these patterns. We present the software modules of the machine and discuss the computation issues related to this study. Conclusions and the directions for future studies are also given at the end of this paper. Keywords. Triangle Chess, Chess Machine, Pattern Marching, Searching Space, Computer Chess
Slide 58: 202 Che-Chern Lin, Chia-Jung Hsu, Ming-Jun Chan, Chih-Hung Chung, Chong-Cheng Hong, Hung-Jen Yang 7.1 Introduction Recently with the promotion of computational speed and data storage, computers have stronger capability to handle more complicated computing. Computer programs for different types of chess games have been built successfully in the past decades including the developments of chess (western), Chinese chess (Xiangqi), Japanese chess (Shogi), Hex, and Go. Xiangqi, a Chinese chess, is very popular in worldwide Chinese community. It uses an 8x8 grid-like chessboard played by two players, “Black” and “Red” [1]. Each of them owns a territory in a roughly half size of the chessboard and has fifteen pieces. These pieces are categorized into seven different types of roles with differ moving regulations, respectively. The seven roles include King, Assistant, Elephant, Horse, Chariot, Gunner, and Pawn [1]. The player who eliminates all of the opponent’s pieces wins the game. Similar to Xiangqi, Shogi is a Japanese chess played by two players, called “Black” and “White” [2]. It uses a 9x9 grid-like chessboard. Each of players has 20 pieces. Hex is also a two-player game played on a hexagonally grid-like chessboard with regularly an 11x11 rhombus [3]. The two players, named “Red” and “Blue”, have their own sides, respectively. During a Hex game, each player uses his pieces to make a link from his side to the opponent’s side. The first player to make a successful implementation of the link wins the game. Go is another popular chess in East Asia. It also has two players, “Black” and “White”, played on an 18x18 grid-like chessboard [4]. During a Go game, each player uses his pieces to form his own territory by removing the opponent’s pieces tightly surrounded by his pieces [4]. After an endgame, the player who has the maximum area of territory wins the game. Basically a chess machine uses searching and parallel computing techniques. However, it requires computers with faster CPU speed and more memory capacity. Using rule-based machines needs to transfer the chess experts’ strategies into rules by which to determine the next steps. It is sometimes difficult to generate and implement these rule-based chess machines. Originally derived from Deep Thought, Deep Blue, developed at IBM Watson Research Center, is a successful computer-based chess machine which defeated a World Chess Champion in 1997 [5]. It basically used parallel computing techniques and searching trees to deal with massive data processing. The computational algorithms developed for Deep Blue calculate all possible moves and might result in massive data manipulations. After calculating the possible moves, Deep Blue then uses evaluation functions to measure the possible scores for these moves and makes a
Slide 59: Design of a computer-based triangle chess machine 203 decision for next steps. Deep Blue not only used the computer software techniques but also hardware techniques. It is so far the most successful chess machine implemented by computer technologies. Iida et al. compared the similarity and the differences between Chess and Shogi, and described the techniques used to build a computer-based shogi machine, including opening and endgame plays, searching algorithm, tactical strategies, and position evaluation. [2]. Wu and Beal used endgame database construction method to implement a computer-based Chinese chess machine and demonstrated its performance in reducing the size of the database [1]. Anshelevich presented a hierarchical method for building a Hex chess machine where he used deduction rules to recursively compute the Hex positions from the beginning of a game [6]. In this paper, we present a case study of implementation of a computerbased triangle chess machine. We also discuss the rules for playing a triangle chess game and the design methodology of this chess machine. Finally we give conclusions and suggest the directions for future studies. 7.2 Implementation The rules for playing a triangle chess are very simple and straightforward. Figure 7.1 shows a triangle chess machine where fifteen circles are arranged in a triangle chessboard. During a triangle chess game, one should select one or more circles (up to five circles) in each step. The selected circles in each step must form a line. This is called “co-linear” rule. The player who selects the last circle is the loser. We used Visual C++ to implement the triangle chess machine. The machine provides a user interface for users to play a triangle chess game and a replay function to repeat the whole process of the game. To implement the machine, we need some software modules (subroutines) to perform the functionalities. There are mainly four modules for doing this. The first module is to validate if the circles selected by a user (the opponent) fit the co-linear rule. We then call this module “co-linear checking” module. The second module is to determine the pattern of the configuration of the triangle chess after the opponent selects his circles. The second module also makes a responding selection of circles (automatically done by the machine) to react the opponent selection. This module is called pattern determination/circles selection module. The third module is called replay module serving to record all steps in a triangle game and to perform replay functionality if necessary. The fourth module is called “user interface” module providing a graphic interfaces for playing a triangle chess game.
Slide 60: 204 Che-Chern Lin, Chia-Jung Hsu, Ming-Jun Chan, Chih-Hung Chung, Chong-Cheng Hong, Hung-Jen Yang Figure 7.2 shows the four functional modules and their relationships. The four modules are explained in details below. 1. Co-linear checking module: The co-linear checking module uses tree structures to determine if circles selected by the opponent are colinear. Each circle in a triangle chessboard has its own searching tree by which to examine if selected circles satisfy the co-linear rule. Each searching tree describes all possible co-linear paths for its corresponding circle. If the opponent selects his circles, the module examines if the selection of circles is on any of co-linear paths. Figure 7.3 shows a triangle chess configuration and the associated tree structures. For convenience, we number the 15 circles in a triangle chessboard from 1 to 15, as indicated in Figure 7.3(a). By the property of symmetry, the 15 circles are categorized into 4 types based on the geometrical property. They are shown as follows: Type 1: circles 1, 11, and 15. Type 2: circles 2, 3, 7, 10, 12, and 14. Type 3: circles 4, 6 and 13 Type 4: circles 5, 8 and 9. The sampled examples for the four types of trees are also shown in Figure 7.3. It is important to note that the selected circles must be sorted before using a tree since the user (opponent player) may make their selections of circles in any orders. 2. Pattern determination/circles selection module: This module stores all possible configurations of patters for a triangle chess game. There are 15 circles in a triangle chessboard and each of circles has two stages: selected (= 1) and unselected (= 0). We then have 2 15 (=32768) combinations of chess configurations. Of the 32768 combinations, only 7795 patterns satisfy the co-linear rule. We therefore use the 7795 patterns as pattern-matching data source. Each of patterns is associated with a response configuration which determines the next move (done by the machine). Since the values of the 15 circles are binary (0 and 1), we then encode each of patterns in a two-byte short integer. The response patterns are also encoded in two-byte short integers. We use a two-dimensional array to store these short integers 3. Replay module: The replay module records all steps played in a game and replays them if a user (opponent) needs to know the history of the game. 4. User Interface module: The user interface module provides a playing platform for an opponent player.
Slide 61: Design of a computer-based triangle chess machine 205 7.3 Conclusions We made a brief explanation on several popular chess games and their computer implementations. We also presented a case study of implementation of a computer-based triangle chess machine. Basically, the chess machine considers all possible configurations of chess patterns and then makes a selection of circles based on these patterns. We demonstrated the software modules of the machine and discussed the issues related to this study. Using decision rules to implement chess machine might be an interesting issue for future studies since it can significantly reduce searching spaces. References 1. Wu R, Beal DF (2001) Solving Chinese chess endgames by database construction. Information Sciences 135:207-228 2. Iida H, Sakuta M, Rollason J (2002) Computer Shogi. Artificial Intelligence 134:121-144 3. http://en.wikipedia.org/wiki/Hex_(board_game) 4. http://en.wikipedia.org/wiki/Go_(board_game) 5. Champbell M, Hoane Jr AJ, Hsu F (2002) Deep Blue. Artificial Intelligence 134:57-83 6. Anshelevich VV (2002) A hierarchical approach to computer hex. Artificial Intelligence 134:101-120 7. Müller M (2001) Global and local tree search. Information Sciences 135:187206 8. Ewerhart C (2002) Backward induction and the game-theoretic analysis of chess. Game and Economic Behavior 39:206-214 Remark: Selected by machine Selected by opponent Unselected (a) At the beginning of a game Fig. 7.1. The triangle machine (b) At the end of a game
Slide 62: 206 Che-Chern Lin, Chia-Jung Hsu, Ming-Jun Chan, Chih-Hung Chung, Chong-Cheng Hong, Hung-Jen Yang Co-linear checking module Replay module User interface module Pattern determination /circle selection module Fig. 7.2. The functional modules in the chess machine 1 2 4 7 11 12 8 13 5 9 3 6 10 14 15 1 2 4 7 11 3 6 10 15 (a) Chess Configuration 2 4 7 3 5 (b) Tree structure of type 1 4 7 8 5 7 4 8 5 9 11 13 6 11 13 6 11 14 (c) Tree structure of type 2 (d) Tree structure of type 3 (e) Tree structure of type 4 Fig. 7.3. Trees to examine the co-linear rule
Slide 63: Chapter 8 A taxonomy model for analyzing project-based learning using Analytical Hierarchy Process (AHP): A case study of design of a beer company website in an elementary school Chung-Ping Lee, Che-Chern Lin, Rong-Jyue Fang, Howard Lo, Ming5 Chih Wu 1,2,4 1 2 3 4 Department of Industrial Technology Education, National Kaohsiung Normal University, Taiwan (R.O.C.) cl87369@ya1 2 hoo.com.tw, cclin@nknucc.nknu.edu.tw, howardlab@ya4 hoo.com 3 Department of Information Management, Southern Taiwan University of Technology, Taiwan (R.O.C.) rxf26@mail.stut.edu.tw 5 Graduate Institute of Educational Technology, National Pingtung University of Education, Taiwan (R.O.C.) michywu@yahoo.com.tw Abstract. This paper presents a taxonomy model which applies analytical hierarchy process (AHP) to project-based learning. To implement the proposed model, a website has been built for the sixthgraders of an elementary school for their project-based learning. The learning target is the knowledge about beer. The learning materials were provided by a local beer company. Six factors are considered as the inputs of the AHP including company introduction, characteristics of beer of the company, company visiting, beer promotion, beer manufacturing, and learning activity sharing. To investigate the importances among the six factors, we interviewed five
Slide 64: 208 Chung-Ping Lee, Che-Chern Lin, Rong-Jyue Fang, Howard Lo, MingChih Wu experts who have at least seven years of teaching experience in an elementary school in Taiwan. The AHP is utilized to generate the weights (importances) for the input variables for the taxonomy model. Keywords. Project- based learning, PBL, Analytical Hierarchy Process, AHP 8.1 Introduction Analytical hierarchy process (AHP) is developed for decision-making [14]. Basically, an AHP model is hierarchically layered structure. Figure 8.1 shows a three-layer AHP [3]. Nodes are used in each layer to represent factors or dimensions. One utilizes weights to link two nodes in the adjacent layers. Mappings are performed from inputs to outputs sequentially. The mapping function is given by the follow formula [3] y j = ∑ wij xi i =1 n (8.1) where yj = the output for node j in a particular layer, xi = the output of node i in the previous layer of this particular layer, wij = the weight linking node j in the particular layer and the node i in the previous layer, n = the number of node in the previous layer. z (output) The 3rd layer (Final decision) y1 w11 w12 x1 w21 x2 y2 w22 The 2nd layer (Dimensions) w32 w31 The 1st layer (Factors) x3 inputs Fig. 8.1. A simple three-layer AHP (taken from [3]) Project-based learning (PBL) is a model that organizes learning materials from different projects. The projects are complex tasks that involve learners in design, problem-solving, decision making, investigative activit-
Slide 65: A taxonomy model for analyzing project-based learning using AHP 209 ies, etc [5]. Instructors provide learners some activities to analyze information on learning topics, compare other cases with their problems, and develop an optimal method for the task [6]. The task-oriented approach is used to find directions of problem solving by providing different practical problems. Finally, learners must gather and organize relevant information in order to implement their learning projects. In this paper, we propose a taxonomy model which applies a two-layer AHP to PBL. We introduce the AHP procedure and explain how AHP is utilized to PBL on beer. A website whose contents were provided by a local beer company has been built for the sixth-graders of an elementary school for their learning on beer. Six factors were determined using a brainstorming procedure including company introduction, characteristics of beer of the company, company visiting, beer promotion, beer manufacturing, and learning activity sharing. Five experts were selected to answer specially designed questionnaires. Finally we present the evaluation model for the taxonomy. 8.2 The AHP procedure The AHP procedure of the propose model is depicted as follows [1-4, 7]. Step 1: Define the problem and determine the goal The goal of this study is to select the useful messages and knowledge from the forum of the website for PBL on beer. This is done by collection of information through internet, group discussion, and special homework related to this study. Step 2: Select factors for the model We used brainstorming to determine the relative importance for establishing evaluation criteria of the elements in the hierarchy. Nine sixthgraders in an elementary school were selected to carry out the brainstorming and generate the structure of factors using a free software package, Xebece. Xebece produces structures of brainstorming by the combination of catalogues, attachment of documents, and XML documents [8]. After the brainstorming, six factors were considered to build the proposed model including company introduction, characteristics of beer of the company, company visiting, beer promotion, beer manufacturing, and learning activity sharing. Step 3: Design the questionnaire The questionnaire was designed to make all possible pair-wise comparisons among the factors. Table 8.1 shows a typical nine-point scale for an
Slide 66: 210 Chung-Ping Lee, Che-Chern Lin, Rong-Jyue Fang, Howard Lo, MingChih Wu AHP questionnaire [3, 4]. The questionnaire was designed to measure all possible importance ratios among the factors. Table 8.2 shows a simple example of the questionnaire where three factors are selected: factors A, B, and C. In the table, factor A is twice important than factor B, the ratio of factors A to B is 2:1. Row 1 is corresponding to the ratio of factors A to B. In row 1, we then mark “ˇˇ” in the cell associated with a value of 2 (closed to the factor of A). Similarly, the importance ratio of factor A to factor C is 3: 1. The importance ratio of factor B to factor C is 1:5. Both of them are shown in Table 8.2 (rows 2 and 3). Table 8.1. The definition and explanation of AHP 9-point scale (taken from [3, 4]) Intensity of Relative Importance 1 3 5 7 9 2, 4, 6, 8 Definition Equal Importance Moderate important of one over another Essential or strong important Demonstrated importance Absolute importance Intermediate values between the two neighboring scales Table 8.2. A simple example of questionnaire (taken from [3]) Factor 98 7 6 5 4 3 21234 5 6 7 8 9 Factor ˇ A (row 1) B ˇ A (row 2) C ˇ B (row 3) C Step 4: Use the questionnaire to collect the experts’ opinions. After collecting questionnaires from experts, one uses a “matrix of importance ratios” to describe the results of pair-wise comparisons. Eq. 8.2 shows the matrix of importance ratios associated with Table 8.2 [3]. The matrix is a symmetrical and reciprocal matrix due to pair-wise comparisons. A B C A 1 1/ 2   1/ 3 B C 2 3 1 1/ 5  5 1  (8.2) Step 5: Test the consistency The Consistency Index (CI) is utilized to express the degree of consistency. Saaty [4] defined the consistency index (CI) as follows:
Slide 67: A taxonomy model for analyzing project-based learning using AHP 211 CI = λmax − n n −1 (8.3) where λmax is the maximum eigenvalue of the matrix of the importance ratios and n is the number of factors. Accordingly, Saaty [4] defined the Constituency Ratio (CR) as follows: CR = CI RI (8.4) where Random Index (RI) is given by Table 8.3. If the value of the consistency ratio CR is less than or equal to 0.1 the questionnaire is considered to be acceptable. If CR is greater than 0.1, the questionnaire fails. Table 8.3. Random Index [1] n RI 1 2 3 4 0.00 0.00 0.58 0.90 Remark: n is the number of fact 5 1.12 6 1.24 7 1.32 8 1.41 9 1.45 10 1.49 8.3 Experimental setup and results In this study, five experts from an elementary school in Taiwan were selected. All of them have at least seven years of teaching experience. The results of five experts’ questionnaires and consistency tests are shown in Table 8.4. Only two questionnaires (Expert 2 and Expert 4) passed the consistency tests. Table 8.4. Eigenvalue and consistency indices of experiment CI λmax Experts 1 7.15 0.23 Experts 2 6.00 0 Experts 3 7.30 0.26 Experts 4 6.33 0.07 Experts 5 7.18 0.24 Remark: * indicates CR ≤ 0.1 (passing the consistence tests) Experts CR 0.19 0.00* 0.21 0.05* 0.19 We took geometrical averages of the weights from the questionnaires which passed the consistency tests. The evaluation formula for the taxonomy model is obtained by taking the normalized eigenvector associated with the maximum eigenvalue of
Slide 68: 212 Chung-Ping Lee, Che-Chern Lin, Rong-Jyue Fang, Howard Lo, MingChih Wu the matrix of importances ( λmax ). Eq. 8.5 demonstrates the evaluation formula y = 0.071x1 + 0.106 x2 + 0.232 x3 + 0.068 x4 + 0.228 x5 + 0.228 x6 (8.5) where x1 = company introduction, x2 = characteristics of beer of the company, x3 = company visiting, x4 = beer promotion, x5 = beer manufacturing, x6 = learning activity sharing. In Eq. (8.5), the higher value of y means the stronger recommendation for taxonomy. 8.4 Conclusions We proposed a taxonomy model which applied AHP to PBL. The learning target of the PBL is the knowledge of beer. The learners were the sixthgraders of an elementary school. To implement the model, we built a website cooperating with a local beer company. Six factors were determined using a brainstorming procedure including company introduction, characteristics of beer of the company, company visiting, beer promotion, beer manufacturing, and learning activity sharing. Five experts were selected to answer the specially designed questionnaires. Finally we used the AHP procedure to generate the evaluation formula for the taxonomy model. As about the directions of further studies, Delphi technique may be considered to collect more experts’ opinions into the project. Besides, using fuzzy logic to describe the factors might be an interesting topic for future study. Finally, we suggest using more layers in the AHP structure to collect more detailed items for further analyses. References 1. Saaty TL (1990) How to mark a decision: the analytic hierarchy process. European Journal of Operational Research 48(1):9–26 2. Saaty TL (2003) Decision-making with the AHP: Why is the principal eigenvector necessary. European Journal of Operational Research 145:85-91 3. Huang C, Lin Y, Lin C (2007) An evaluation model for determining insurance policy using AHP and fuzzy logic: case studies of life and annuity insurances.
Slide 69: A taxonomy model for analyzing project-based learning using AHP 213 4. 5. 6. 7. 8. In: The 8th WSEAS international conference on fuzzy systems, Vancouver, Canada, pp 126-131 Saaty TL (1980) The Analytic Hierarchy Process. Revised and extended 1988, McGraw-Hill, New York John TW (2000) A review of research on project-based learning. T. A. Foundation, California Brunettti AJ, Petrell RJ, Sawada B (2003) Team project-based learning enhances awareness of sustainability at the University of British Columbia, Canada. International Journal of Sustainability in Higher Education 4(1):210217 Lee SK, Yoon YJ, Kim JW (2007) A study on making a long-term improvement in the national energy efficiency and GHG control plans by the AHP approach. Energy Policy 35:2862–2868 Kennke R (2007) Xebece: Visualize and organize information easily. Retrieved 6.1, from http://xebece.sourceforge.net/
Slide 70: Chapter 9 A framework of mixed model of a neural network and boolean logic for financial crisis prediction 1 2 3 4 Che-Chern Lin, Ghuan-Hsien Mao, Howard Lo, Hung-Jen Yang 1,3,4 National Kaohsiung Normal University, 116 Heping First Road, Kaohsiung City, Taiwan (R.O.C.) 2 Shu-Te University, 59 Hun Shan Road, Yen-Chau, Kaohsiung County, Taiwan (R.O.C.) 1 2 cclin@nknucc.nknu.edu.tw, js.mao@msa.hinet.net, 4 3 howardlab@yahoo.com, hjyang@nknucc.nknu.edu.tw Abstract. This paper proposes a framework for pattern classifications. This framework includes two neural networks and a logic circuit. The first neural network serves to classify regular instances, and the second one handles the overlapped instances caused by the first neural network. The proposed framework integrates the two neural networks by the logic circuit and then makes the final classifications. We provide two methodologies using the proposed framework including financial crisis prediction and principle components analysis. In the financial crisis prediction case, we use the financial ratios of individual companies as the inputs of the first neural network and the macroeconomic indicators as the inputs of the second neural network. In the principle components analysis case, we use the attributes in a major factor group as the inputs of the first neural network and those in a minor factor group as the inputs of the second neural network. Keywords. Neural Networks, Logic Circuit; Financial Crisis Prediction
Slide 71: A framework of mixed model for financial crisis prediction 215 9.1 Introduction Traditionally, people use statistical methods to analyze data, build models, and make decisions (prediction, estimation, and classification). Instead of statistical methods, recently artificial intelligent algorithms are widely utilized in different areas. The most popular artificial intelligence algorithms include data mining algorithms, fuzzy systems, genetic algorithms, and neural networks. Data mining algorithms use computer programs to find relationships among different attributions by establishing association rules. Based on an iterative procedure to find the optimal combinations of items, the apriori algorithm is the most popular one to general association rules for categorical items. Basket analyses are successful applications for business to analyze customers’ behaviors. Fuzzy expert systems mimic the thinking processes of human beings where verbal expresses are used to generate rules and make decisions. Unlike traditional crisp values, fuzzy variables use membership functions to describe the marching degree of how inputs fit a particular fuzzy set. Two types of membership functions are often adopted in fuzzy systems: triangular and trapezoidal functions. In general, a fuzzy expert system consists of three parts: a fuzzy base, an inference engine, and user interfaces. The fuzzy base consists of a set of fuzzy rules usually obtained by domain experts. The inference engine is the mechanism to make conclusions by firing the fuzzy rules. The user interfaces allow users to define membership functions, compose fuzzy rules and display outcomes. Genetic algorithms use an evolutionary procedure to find optimal solutions. Like biological evolutionary process, genetic algorithms use fitness function to evaluate the performance for particular generations and use genes (chromosomes) as input strings. In genetic algorithms, selections are used to get better offspring and mutations are utilized to mimic the random changing of genes. Neural networks use computer programs to simulate the structure of human brains and the cognition processes of human beings. A neural network is usually a layered structure with nodes in each layer. Weights are used to connect two nodes between two adjacent layers and updated by training algorithms. The back-propagation algorithm is one of the most popular updating algorithms where the gradient descent method is utilized to minimize the errors. The training algorithm uses a set of well-known examples, called training set, to backwardly adjust weighs from outputs to inputs. This procedure is called training procedure. After the training procedure, neural networks are ready to classify unknown instances based on the well-trained weights. Neural networks are widely applied to financial applications. A lots of studies related to financial crisis prediction can be found in [1-6].
Slide 72: 216 Che-Chern Lin, Ghuan-Hsien Mao, Howard Lo, Hung-Jen Yang 9.2 The Framework Figure 9.1 shows the diagram for the proposed framework. There are two neural networks and a logic circuit in Figure 9.1. The first neural network functions serve to classify regular instances and the second one handles the overlapped instances caused by the first neural network. For a two-class classification problem (Class I and Class II), the classification results are determined in Table 9.1. Table 9.1. The classification results of a two-class classification problem A 0 0 1 1 B 0 1 0 1 Class assigned Undetermined Class I Class II Overlapped To handle the overlapped instances, we use the second neural network to furthermore classify these overlapped instances. We select these overlapped instances as the training data for the second neural network. The logic circuit is used to integrate the two neural networks and get the final classification results. Table 9.2 is the truth table for the logic circuit of the proposed framework. Table 9.2. The truth table for the logic circuit Input A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Output Y 0 0 1 1 0 0 0 1 Remark: Y=1 represents Class I, and Y= 0 represents Class II. The simplified Boolean expression for Table 9.2 is given by Y = B( A + C ) (1) The logic circuit for Eq. 9.1 is also shown in Figure 9.1. In brief, the procedure of the proposed framework is described as follows:
Slide 73: A framework of mixed model for financial crisis prediction 217 Step 1: Train the first neural network. The overlapping instances are the patterns with A =1 and B = 1. Step 2: Train the second neural network using the overlapping instances obtained in Step 1. Step 3: Implement the classifier using the proposed framework shown in Figure 9.1. 9.3 Methodologies In the proposed framework, the first neural network serves to perform the main classifications and the second one handles the overlapped patterns to improve the classification accuracies. We then call the first neural network “primary neural network” and the second one “secondary neural network”. Below, we present two methodologies applying the proposed framework. Methodology 1: Establish the primary and secondary neural networks using well-defined dimensions of attributes. If the dimensionality of the variables has well-defined, one can use the variables in major dimension as the inputs of the primary neural network, and the minor dimension as the input of the secondary neural network. Financial crisis prediction is one of the applications of using methodology 1 [6]. Previous studies have indicated the financial crisis can be predicted using neural networks based on two groups of variables: financial ratios for individual companies and macroeconomic indicators. The financial ratios affect the financial crisis more strongly than the macroeconomic indicators. We then use the financial ratios as the inputs for the primary neural network and the macroeconomic indicators as the inputs for the secondary neural network. Mao used this framework to predict the financial crises for public electronic companies in Taiwan and got better results than regular neural networks [6]. The financial ratios and macroeconomic indicators used in Mao’s study are shown in Table 9.3 [6]. Methodology 2: The second methodology is to use statistical techniques to separate variables into two groups according their importance: the major affecting and minor affecting groups before using the proposed framework. Consider a set of instances with n attributes. Based on the importance of the affecting degree of the n attributes, one can use statistical methods to divide the n attributes into two groups: the major factor group with higher affecting degrees and minor factor group with lower affecting degrees. Principle components analysis is one of the popular methods to do this. After dividing the input attributes, one can use the attributes in major
Slide 74: 218 Che-Chern Lin, Ghuan-Hsien Mao, Howard Lo, Hung-Jen Yang factor group as the input of the primary neural network and those in minor factors as inputs of the secondary neural network. 9.4 Conclusions We introduced the artificial intelligence algorithms and their applications. We proposed a framework for pattern classifications. This framework includes two neural networks and a logic circuit. The first neural network serves to classify regular instances, and the second one handles the overlapped instances caused by the first neural network. The proposed framework integrates the two neural networks by the logic circuit and then makes the final classifications. We provided two methodologies using the proposed framework including financial crisis prediction and principle components analysis. In the financial crisis prediction case, we used the financial ratios of individual companies as the inputs for the primary neural network and the macroeconomic indicators as the inputs for the secondary neural network. In the principle components analysis case, we used the attributes in major factor group as the input of the primary neural network and those in minor factors as the inputs of secondary neural network. As for the further studies, people might add fuzzy logics into the proposed framework to furthermore classify overlapped patterns. Using more neural networks for the framework might be interesting research topics for further works. References 1. Altman EI (1968) Financial ratios, discriminant analysis and the prediction of Corporate bankruptcy. Journal of Finance, pp 589-609 2. Altman EI, Marco GV, Varetto F (1994) Corporate distress diagnosis: Comparisons using linear discriminant analysis and neural networks (The Italian Experience). Jouranl of Banking and Finance 18:505-529 3. Beaver WH (1966) Financial ratios as predictors of failure. Journal of Accounting Research, pp 71-111 4. Blum M (1974) Failing company discriminant analysis. Journal of Accounting Research 12:1-25 5. Coats PK, Fant LF (1993) Recognizing financial distress patterns using a neural network tool. Financial Management 12:142-155 6. Mao C (2002) A study on financial crisis forecasting using a mixed model of neural network and digital logic manipulation — A case study of public elec-
Slide 75: A framework of mixed model for financial crisis prediction 219 tronic companies. Master Thesis, Shu-Te University, Kaohsiung County, Taiwan Table 9.3. The financial ratios and macroeconomic indicators used for financial crisis prediction [6] Financial ratio Return on total assets Growth rate in sales Growth rate in operating profits Growth rate in total assets Growth rate in equity Growth rate in fixed assets Current ratio Quick ratio Debt ratio Times interest earned ratio Accounts receivable turnover Inventory turnover Total asset turnover Debt- to-Equity Ratio Macroeconomic indicators Gross Domestic Product Export Import Annual increasing rate of wages Employment rate Unemployment rate Economic growth rate Annual increasing rate of loans and investments Rediscount rate Interest rate in money market Exchange rate Financial Ratios The first (primary) neural network A B NOT OR Macroconomic Indicators The second (secondary) neural network C AND Fig. 9.1. The proposed framework
Slide 76: Chapter 10 Chinese document clustering using selforganizing map-based on botanical document warehouse Howard Lo, Che-Chern Lin, Rong-Jyue Fang, Chungping Lee, Yu-Chen 5 Weng 1,2,4,5 1 2 3 4 3 Department of Industrial Technology Education, National Kaohsiung Normal University, TAIWAN Department of Information Management, Southern Taiwan University of Technology, TAIWAN 13F., No.225, Guanghua 3rd Rd., Kaohsiung City 806 Taiwan 1 2 howardlab@gmail.com, cclin@nknucc.nknu.edu.tw, rxf26@mail.s- 5 3 4 tut.edu.tw, cl87369@yahoo.com.tw, jane2080@gmail.com Abstract. The exponential growth of information has made an overflow situation in the sea of information. It had created difficulties in the search for information. An efficient method to organize the query of information and assist users’ navigation is therefore particularly important. In this paper, we applied SOM algorithm to cluster Chinese botanical documents onto a two-dimensional map. Each botanical document has been regarded as bags of words, and transferred into a plain text respectively. We applied term frequency and inverse term frequency to extract key terms from documents as the input of SOM. 892 Chinese botanical documents have been projected onto a 2D map to assist users’ navigation. In our experimental results, the lowest recall was 0.71 for Polygonaceae documents and the highest recall rate was 0.94 for Amaranthaceae docuemnts. The lowest precision rate was 0.81 for Umbelliferae documents, and the
Slide 77: Chinese document clustering using self-organizing map highest precision rate was one hundred percent for Convolvulaceae and Cruciferae documents. Keywords. Self Organizing Map, Information retrieval, Vector Space Model, Clustering, Browsing 221 10.1 Introduction The Self-Organizing Map (SOM) algorithm, which is developed by Kononen[1], is largely use in images and documents clustering. The SOM algorithm works best with browsing tasks, especially in a very large document storage, such as an document warehouse [2]. The aim of this study is to apply SOM algorithm to cluster those botanical data in a document warehouse into a two-dimensional map, in order to fulfill the naïve users’ information needs. We exploited the discrimination values to cull important terms from the document warehouse, and transferred the unstructured documents into vectorized tuples as inputs of the SOM algorithm. The results will be projected onto a two-dimensional SOM map. When considering retrieval performance evaluation, we adopted the recall rate and precision rate as our measurements. The rest of the paper is organized as follows: section 10.2 describes related works and the SOM algorithm. Section 10.3 describes the research steps and model of our research. The evaluation and experiment results would be discuss in section 10.4, and section 10.5 will come to a conclusion and point out the future research. 10.2 Related works According to the survey of Sullivan[3], eighty percent of the necessary information for the decision maker were came from unstructured data, such as documents and only twenty of them were came from structured data, such as a database. There is a need to deal with documents. 10.2.1 Dealing with unstructured documents Since 1950s, there were lots of researchers trying to deal with unstructured documents with computer technologies. In 1961, Doyle used an associ-
Slide 78: 222 Howard Lo, Che-Chern Lin, Rong-Jyue Fang, Chungping Lee, Yu-Chen Weng ation map to describe documents. In 1967, Borko proposed an idea to index and classify documents using computer technologies [4]. In 1980, Porter [5] proposed an algorithm to remove suffixes automatically from words in English and restore the words to its original form. In 1983, Salton recommended a vector space model (VSM) to help user compared the similarities between documents [6-9]. Salton’s VSM has make progress in information retrieval from documents indexing and classifying, to comparison of similarities. Their studies have proved one thing, it’s possible to deal with documents using computer technologies. Artificial neural networks are currently attracting particular interest as methodologies to deal with unstructured data. Chen [10] applied Hopfield network to classify terms in the documents. Nigam proposed the use of maximum entropy techniques for text classification in his paper [11]. Mladenic [12] applied a näive Bayesian classifier to select features from documents. Chen et al [13] exploited a fair feature-subset selection algorithm and an adaptive fuzzy learning network to classify online documents. Since Kohonen introduced the SOM in the early 1980s [14], the SOM algorithm has attracted a great deal of interests among researchers in a wide variety of domains. In 1996, Lagus et al. [15] applied SOM to develop a tool called WEBSOM to cluster documents. Kohonen et al. mapped 6840568 patent abstracts onto a SOM with 1002240-node [16]. In 2002, Vicente et al. [17] exploited vector space model to extract key terms from document as input of SOM. In 2003, Smith et al. developed an LOGSOM system using Kohonen’s self-organizing map to organize web pages onto a two-dimensional map [18]. In 2004, Azcarraga et al. [19] analyzed the relative weight distribution of the SOM weight vectors and took advantage of some characteristics of the random projection method to select keywords in order to extract meaningful labels each cluster on the map. 10.2.2 Self Organizing Map Algorithm The SOM is an artificial neural network model based on unsupervised learning, introduced by Kohonen in the early 1980s. The SOM is a tool for automatically arranging high dimensional statistical data onto a two-dimensional map. Therefore, it is able to transfer sophisticated, non-linear statistical relationships among high dimensional data into simple, low dimensional map. In our study, we adopted Smith’s revised SOM algorithm [18]. The algorithm is summarized as follow.
Slide 79: Chinese document clustering using self-organizing map 223 • Initialize input nodes, out nodes, and connection weights. Initialize a small random value for Wij as seeds. Assign Nk as neighborhood size. Assign a random value between 0 and 1 for parameter function α (t) and σ 2 (t) . In the study, we assigned α (0) = 0.1 and σ 2 (0) = 1 . • Calculate the distance with Euclidean distance. Present an input vector xi to represent document xi and calculate the similarity d (distance) of the input vector to the weights w of each node j using Eq. 10.1. d j = x - wj = ∑ ( xi - wij ) i n 2 (10.1) • Select the node with minimum Euclidean distance as the winner node k . • Update the weight. Applying Eq. 10.2 to adjust the weight related to the input layer and winning node, and its neighboring nodes. wij (t + 1) = wij (t ) + c( xi - wij (t )) (10.2) where c = α (t)exp(- ri - rk /σ 2 (t)) , and ri - rk is the number of nodes, to represent the physical distance between node j and winning node k. • Repeat the step above, until the weights have stabilized. In each epoch, increase t by 1, and decrease the neighborhood size, α (t) and σ 2 (t) by Eq. 10.3. α (t) = α (0)N k (t)/N k (0) (10.3) Nk: size of neighborhood. • The final stage. The iterative step will be terminated after all the vectors of documents have been presented to the training network, and mapped onto a two-dimensional map. 10.2.3 Users’ information need According to the researches of Baeza-Yates [20], there are three seeking techniques for most users to fulfill their information needs. The first technique is browsing. Marchionini defined browsing behavior as “an exploratory, information seeking strategy that depends upon serendipity and especially appropriate for ill-defined problems and for exploring new task domains” [21].
Slide 80: 224 Howard Lo, Che-Chern Lin, Rong-Jyue Fang, Chungping Lee, Yu-Chen Weng The second technique is searching. According to definition of Sim, searching is “an analytical process, is a planned activity with a specific goal, such as to find a particular fact” [22]. The third technique is visualization. Visualization interfaces, such as windows, menu, icon, and dialog boxes, make the computer system more friendly and easily to use. The goal of this study is to apply SOM algorithm to cluster Chinese documents onto a two-dimensional SOM. With this map, it can assist users’ browsing and visualization needs in information retrieval. 10.3 Methodology In our research, we regarded documents as a bag of words. We ignored the order of the words as well as any punctuations or structural information, but retained the frequencies of every word. Our research steps are as follow. • Acquiring documents We attained 892 botanical documents from Herbarium, Research Center for Biodiversity, Academia Sinica, in Taiwan (HAST) [23] and Taiwan Agricultural Chemicals and Toxic Substances Research Institute, Council of Agriculture (TACTRI/COA) [24] as our training data. The documents are all in html format, and needed to be transferred to plain text. • Preprocessing documents All tags in the botanical documents needed to be removed and transferred to plain text as training data. • Segmenting Chinese terms CKIP was a Chinese term segmentation system, developed by Institute Linguistics, Academia Sinica, Taiwan [25]. We applied the CKIP system to extract Chinese terms from sentences. • Extracting Chinese key terms We removed the stopwords from the documents, and revised the errors which segmented by CKIP with our revising system developed by Java language. • Calculating term weight Calculate the weight of every key term. We applied Eq. 10.4 to calculate the term weight. w = (tf × idf) (10.4)
Slide 81: Chinese document clustering using self-organizing map 225 N where idf = log   , W: the term weight, tf: the term frequency, df: the  df  term frequency shows in the document collection, idf: the inverse df. • Vectorizing documents After the term extracting and weight calculating, the 892 botanical documents will transfer into vectorized statistical data shown as Eq. 10.5. Di =( W1, W2, W3,..., Wn) (10.5) where Di represents the 892 documents, and W represents the term weight. • Clustering documents with SOM The Vectorized documents will be used as input data of SOM algorithm. After the training processes, the input data will be mapped to the Kohonen layer. • Projecting documents onto a SOM map The vectorized data D1…. Di will be projected onto a two-dimensional grid map. This map can represent the relationships among documents. The features of adjacent nodes will be similar to the centroid node. 10.4 Results In this study, we applied Vector Space Model, developed by Salton to vectorize the 892 botanical documents into statistical data as the input value of SOM algorithm. We assigned 20x20 nodes in our research. The learning rate would be 01, 0.5, and 0.9; learning epochs would be 100, 200, 400, and 500. Fig. 10.1. Analysis of botanical document map
Slide 82: 226 Howard Lo, Che-Chern Lin, Rong-Jyue Fang, Chungping Lee, Yu-Chen Weng 10.4.1 Discussion Figure 10.1 represents an output map of SOM, Each number on the cell points the amount of botanical documents clustered into this cell. There are two documents in cell (10, 4). Those features of these two documents were “葉對生 (Phyllotaxy: Opposite) 長橢圓形 (Leaf shape: Oblong) 葉尖銳 (Apex: Acuminate) 全緣 (Leaf margin: Entire) 花白色 (flower: White) 球 形 (Inflorescence: sphere) 腋生 (Inflorescence: axillary)”. When we look up the botanical illustration, we found they are the same plant, but using different Chinese name. Both of them are “Alternanthera philoxeroides (Mart.) Griseb” in the scientific name of “長梗滿天星” and the nickname of “空心蓮子草” in Chinese. They have been clustered into the same area correctly. 10.4.2 Evaluation To Evaluate the efficiency of an information retrieval system, Baeza-Yates [23] proposed recall rate and precision rate as the measurements. Eq. 10.6 is the formula for calculating recall rate, and Eq. 10.7 is the formula for calculating precision rate. Recall = number of relevant Docs retrieved number of relevant Docs in collection number of relevant Docs retrieved number of Docs retrieved (10.7) (10.6) Precision = Figure 10.1 depicts the analysis of botanical document map, and Table 10.1 shows the result of our study. In our experimental results, the lowest recall was 0.71 for Polygonaceae documents and the highest recall rate was 0.94 for Amaranthaceae documents. The lowest precision rate was 0.81 for Umbelliferae documents, and the highest precision rate was one hundred percent for Convolvulaceae and Cruciferae documents. Table 10.1. Analysis of recall and precision rate Area Family Related docs Related docs Retrieve Recall been retrieved in collection d docs rate Precision rate
Slide 83: Chinese document clustering using self-organizing map A B C D E F Convolvulaceae Cruciferae Amaranthaceae Fabaceae Polygonaceae Umbelliferae 6 14 32 19 22 22 8 15 34 25 31 30 6 14 36 21 24 27 0.75 0.93 0.94 0.76 0.71 0.73 1 1 0.89 0.90 0.92 0.81 227 10.5 Conclusion In this work we applied SOM algorithm to classify the Chinese botanical documents onto a two-dimensional map. The method performed a completely automatic and unsupervised clustering of the botanical documents. The result shown in Figure 10.1 depicted a lowest recall rate 0.71 for Polygonaceae and lowest precision rate 0.81 for Umbelliferae. The experimental results depicted a good performance in recall and precision rate. This botanical document map can assist users to browse information with visualization SOM map. In the future research, we hope to adopt other artificial neural networks to cluster or classify unstructured data, and improve the efficiency of information retrieval. References 1. Kohonen T, Kaski S, Lagus K, Salojärvi J, Honkela J, Paatero V, Saarela A (2000) Self-organization of a massive document collection. IEEE Trans. Neural Networks 11:574-585 2. Fang R-J, Lo H, Weng Y-C, Tsai HL (2007) Mobile learning system using multi-dimension data warehouse concept-based on botanical data. In: Proceeding of the 6th WSEAS International Conference on Applied Computer Science, Hangzhou, China 3. Sullivan D (2001) Document warehousing and text mining. John Wiley & Sons, Inc. 4. Trybula WJ (1999) Text mining and knowledge discernment: An exploratory investigation. Ph.D., The University of Texas at Austin 5. Porter M (1980) Readings in information retrieval. Morgan Kaufmann, San Francisco 6. Salton G, Wong A, Yang CS (1975) A vector space model for automatic indexing. Communications of the ACM 18:613-620 7. Salton G, McGill M (1983) Introduction to modern information retrieval. McGraw Hill, New York
Slide 84: 228 Howard Lo, Che-Chern Lin, Rong-Jyue Fang, Chungping Lee, Yu-Chen Weng 8. Salton G, Buckley C (1988) Term-weighting approaches in automatic text retrieval. Information Processing and Management 24:513-532 9. Salton G, Singhal A (1995) Automatic text browsing using vector space model. Department of Computer Science, Cornell University 10. Chen H, Ng T (1995) An algorithmic approach to concept exploration in a large knowledge network (Automatic Thesaurus Consultation): Symbolic Branch-and-Bound Search vs. Connectionist Hopield Net Activation. Journal of the American Society for Information Science 45:348-369 11. Nigam K, Lafferty J, McCallum A (1999) Using maximum entropy for text classification. In: IJCAI-99 Workshop on Machine Learning for Information Filtering, Stockholm, Sweden, pp 61-67 12. Mladenic D, Grobelnik Marko (2003) Feature selection on hierarchy of web documents. Decision Support Systems 35:45-87 13. Chen C-M, Lee H-M, Tan C-C (2006) An intelligent web-page classifier with fair feature-subset selection. Engineering Applications of Artificial Intelligence 19:967-978 14. Kohonen T (1995) Self-organizing maps. Springer, Berlin, Heidelberg 15. Lagus K, Honkela T, Kaski S, Kohonen Teuvo (1996) Self-organizing maps of document collections: A new approach to interactive exploration. In: Proceedings of the Second International Conference on Knowledge Discovery & Data Mining 16. Kohonen T, Kaski S, Lagus K, Salojärvi J, Honkela J (2000) Self organization of a massive document collection. IEEE Transactions on Neural Networks 11:574-585 17. Guerrero VP, Moya-Anego´n FL, and Herrero-Solana V (2002) Automatic extraction of relationships between terms by means of Kohonen's algorithm. Library & Information Science Research 24:235-250 18. Smith KA, Ng A (2003) Web page clustering using a self-organizing map of user navigation patterns. Decision Support Systems 35:245-256 19. Azcarraga AP, Y Jr TN, Tan J, Chua TS (2004) Evaluating keyword selection methods for WEBSOM text archives. IEEE Transactions on Knowledge and Data Engineering 16:380-283 20. Baeza-Yates R, Ribeiro-Neto B (1999) Modern information retrieval. 21. Marchionini G, Shneiderman B (1988) Finding facts vs. browsing knowledge in hyptertext systems. IEEE Computer, pp 70-79 22. Sim SE, Clarke CLA, Holt RC, Cox AM (1999) Browsing and searching software architectures. In: Proceedings of the International Conference on Software Maintenance, Oxford, England 23. T. Academia Sinica (2007) Herbarium, research center for biodiversity. Available at http://hast.sinica.edu.tw 24. Hsu LM, Chiang MY (2007) Lawn weeds in Taiwan. Available at http://www.tactri.gov.tw/htdocs/plant/lawnweed/index.asp 25. Institute Linguistis (2007) CKIP Chinese term segmentation system. Academia Sinica
Slide 85: Chapter 11 Linear discriminant analysis in Ottoman alphabet character recognition Zeyneb Kurt, H. Irem Turkmen, M. Elif Karsligil Department of Computer Engineering, Yildiz Technical University, 34349 Besiktas / Istanbul TURKEY zeyneb@ce.yildiz.edu.tr, irem@ce.yildiz.edu.tr, elif@ce.yildiz.edu.tr Abstract. This paper proposes a novel Linear Discriminant Analysis (LDA) based Ottoman Character Recognition system. Linear Discriminant Analysis reduces dimensionality of the data while retaining as much as possible of the variation present in the original dataset. In the proposed system, the training set consisted of 33 classes for each character of Ottoman language alphabet. First the training set images were normalized to reduce the variations in illumination and size. Then characteristic features were extracted by LDA. To apply LDA, the number of samples in train set must be larger than the features of each sample. To achieve this, Principal Component Analysis (PCA) were applied as an intermediate step. The described processes were also applied to the unknown test images. K-nearest neighborhood approach was used for classification. Keywords. Ottoman Character Recognition, PCA, LDA 11.1 Introduction Within the last years, rapidly growing interest in document archiving and retrieval systems increased attention to character recognition systems. Nu-
Slide 86: 230 Zeyneb Kurt, H. Irem Turkmen, M. Elif Karsligil merous approaches have been proposed for optical or handwritten character recognition mostly in Latin-based alphabets. On the contrary, some alphabets as Arabic, Chinese, and Japanese have picture like characters which require more complex recognition algorithms to identify. This paper presents an Ottoman alphabet recognition system. Ottoman characters are the characters of an alphabet that was formed by adding some new letters from Farce and Turkish alphabet to the Arabian alphabet. Besides, Ottoman alphabet has been improved with its original features and has become an art due to its various scriptural formats. There are few implementations of automated Ottoman alphabet recognition. Atici and Yarman-Vural, applied chain coding to characters to propose a Hidden Markov Model based Ottoman alphabet recognition system [1]. Ozturk, A.Gunes proposed a method for recognition of isolated Ottoman characters by neural networks [2]. We propose a new global feature based approach for Ottoman alphabet recognition by using Linear Discriminant Analysis (LDA). LDA projects the data onto a lower dimensional space while preserving as much of the class discriminatory information as possible. Fig. 11.1. Block diagram of proposed system Ottoman script is fundamentally cursive. Since this paper focuses on the character recognition, the segmentation of the connected characters has
Slide 87: Linear discriminant analysis in Ottoman alphabet character recognition 231 been not studied. In Figure 11.1, the block diagram of the proposed system is illustrated. The outline of the paper is as follows: Section 11.2 presents preprocessing steps of the system. Section 11.3 describes extraction of the characteristics features using LDA. In Section 11.4, decision steps of the system are described. Finally in section 11.5, experimental results of our implementation are given. Moreover, the performance of the proposed system is discussed. 11.2 The preprocessing Ottoman characters have many common points with each other in their main shapes, whereas they differ in detail. In the proposed system, each Ottoman character is considered as a class. Our main goal is to discuss the influence of the components that points out the within class similarities and between class differences on success rate. Since our purpose is to measure the performance on recognition of isolated characters, the classification success of separate characters is scrutinized. The objective of LDA is to find out the most efficient combinations to split up multiple classes and to maximize between class differences. Thus, it is widely used in several applications such as face recognition, speech recognition, image summarization and data classification [5]. As a precondition of LDA implementation, the size of each sample must be less than the number of samples in the training set. Since the training set is inconvenient with that precondition, dimension reduction should be applied. For this purpose PCA is applied to training set as an intermediate step. The main purpose of preprocessing is to reduce the variation in size and illumination. The preprocessing steps are applied both to the training and testing images. In this study, 256 gray level images with a light colored background were used. By the contrast enhancement, not only the identification of characters was improved and the characters were slimed down, but also the potential noises in the images were eliminated. Moreover, the images were aligned and resized. Figure 11.2, shows the preprocessing steps applied on images. For each image, the inside of the frame which was drawn by using the tangents to the maximum and minimum points of characters on x and y coordinates, is taken into consideration.
Slide 88: 232 Zeyneb Kurt, H. Irem Turkmen, M. Elif Karsligil After the alignment process, images may be in several sizes. In this study, each character was normalized to 32x32 pixels. Fig. 11.2. Examples of the Preprocessing Steps 11.3 The feature extraction Each Ottoman character has some features that are similar to others and different from others. In this study LDA was used to extract the characteristic features of Ottoman characters. To implement the LDA, the number of samples in train set must be larger than the features of each example. To achieve this, first we applied PCA. The selection of eigenvectors with the highest eigenvalues reduces the dimensionality. Then we applied LDA to this reduced feature set. 11.3.1 Principle components analysis PCA reduces dimensionality of data while expressing most important characteristic features. PCA finds basis vectors for a subspace, which: • maximizes the variance retained in the projected data • or (equivalently) gives uncorrelated projected distributions • or (equivalently) minimizes the least square reconstruction error[3]. Each of the p number of images whose size is n*m is assumed to be [n*m]*1 sized column vectors that correspond to the original data [4]. Ω = X * XT (11.1) The covariance matrix (Ω) is defined by the Equation-1 where X is the mean matrix subtracted vector whose size is [n*m]*p, where there are p
Slide 89: Linear discriminant analysis in Ottoman alphabet character recognition 233 image in the training set. Because of the multidimensionality, (Ω) is calcu lated using (11.2), instead of (11.1). Ω = XT *X (11.2) The eigenvalues and associated eigenvectors are obtained as in (11.3) where Ω is the covariance matrix, λ is the set of eigenvalues and V is the associated eigenvectors. Ω * V =λ * V (11.3) We do not have to use the whole acquired eigenvectors. Therefore the eigenvectors are sorted by descending order and only selected number of highest eigenvalues are used. PCA was applied to both training data and test data. The acquired projections in the eigenspace were given to LDA as input. 11.3.2 Linear discriminant analysis LDA aims to determine the linear combinations of the features which can separate the objects and events into more than one class. These combinations, which were obtained after applying LDA, can be used as a linear classifier or it can be used to decrease the dimension for the classification step. LDA maximizes between-class scatter while minimizing the withinclass scatter [6]. The projections in the eigenspace, which were obtained by PCA and belonged to the alphabet’s each character, were vectorized. The mean vector (M) of the alphabet’s character set was calculated. The mean vectors of each character class (Mi) were calculated and for each class the mean vector of the class was subtracted from each character in a class. Let m be the number of the samples in each class, n be the number of classes and A be the mean-centered eigenspace projections. The scatter matrices for each class were acquired by: S1 = A11 * A11T + … + A1m * A1mT Sn = A n1 * A n1T + … + A nm * A nmT (11.4) (11.5) The within class scatter matrix Sw was obtained by (11.6) where Mi is the mean vector of ith class and M is the mean vector of whole characters in the train set. Sw = S1 + S2 + … + Sn (11.6)
Slide 90: 234 Zeyneb Kurt, H. Irem Turkmen, M. Elif Karsligil The between class scatter matrix SB was built by: SB = 2 * Σ (Mi – M) The eigenvectors (V) and eigenvalues (λ) were calculated as: SB * V = λ * SW * V (11.8) The eigenvectors were sorted by their associated eigenvalues in descending order and the first n-1 eigenvectors were kept. Fisher space projections of each class in the train set were obtained by using these eigenvectors. (11.7) 11.4 Classification Each test image was first projected into eigenspace and then into Fisher space. The k-Nearest Neighborhood was used for classification of unknown test images. The system performance was evaluated by applying 10-fold cross validations [7]. 11.5 Experimental results We conducted experiments using a database of 10 sample images of 33 Ottoman alphabet characters. The samples, gathered from electronic resources were both handwritten and in press printed format. In k-nearest neighborhood, k was selected as 3 by 10-fold cross validation. Figure 11.3(a) illustrates true classification of three test examples. Fig. 11.3. (a). Three samples for the test data which were recognized correctly. (b). The train set samples of these characters respectively.
Slide 91: Linear discriminant analysis in Ottoman alphabet character recognition 235 Figure 11.4 illustrates false classification of three test examples. As it can clearly be seen, the test examples are very similar to the characters of the incorrect classes. Fig. 11.4. (a). Three samples for the test data which were recognized incorrectly. (b). Train set samples for the decision classes of the system for incorrectly recognized letters As given in Table 11.1 success ratio of our Ottoman Character Recognition system is 88%. Table 11.1. The success ratio of the processed system True Classification False Classification Total Number of Characters Recognition Ratio 290 40 330 88% 11.6 Conclusion This study presents a Linear Discriminant Analysis based automatic Ottoman Alphabet Character Recognition System. This approach retains class separability while reducing the dimensionality. As the performance of our proposed system is very promising for the recognition of individual characters, in the future work we will study on a system for the recognition of cursive characters in scripts. This will yield to processing and recognition of a large number of historical documents and we will be able to archive these documents.
Slide 92: 236 Zeyneb Kurt, H. Irem Turkmen, M. Elif Karsligil References 1. Atici AA, Yarman-Vural FT (1997) A heuristic algorithm for optical character recognition of Arabic script. Signal Processing 62(1):87-99 2. Ozturk A, Gunes S, Ozbay Y (2000) Multifont Ottoman character recognition. In: Proceedings of the 7th IEEE Int. Conf. on Electronics Circuits and Systems (ICECS), Jounieh, Lebenon, pp 945-949 3. Turk M, Pentland A (1991) Eigenfaces for recognition. J. Cog. Neurosci. 3(1) 4. Turk M, Pentland A (1991) Face recognition using eigenfaces. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Maui, Hawaii, USA, pp 586-591 5. Belhumeur PN, Hespanha JP, Kriegman DJ (1996) Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. In: Proc. of the 4th European Conference on Computer Vision, ECCV'96, Cambridge, UK, pp 4558 6. Etemad K, Chellappa R (1997) Discriminant analysis for recognition of human face images. Journal of Optical Society of America A, pp 1724-1733 7. Kung SY, Mak MW, Lin SH (2004) Biometric authentication: A machine learning approach. Prentice Hall
Slide 93: Chapter 12 User requirements engineering and management in software development Zeljko Panian Faculty of Economics and Business, University of Zagreb, Croatia Abstract. Requirements engineering is an often underutilized discipline in software development. Yet the economic benefits – lowered development costs, faster development and better products that delight customers – have plainly been demonstrated in study after study. In this paper, the case is made for requirements engineering as an integral part of any product lifecycle. Metrics are provided to show the positive effect of requirements engineering and requirements management (RM), from individual developers to the business to the customer. A software product is examined as an example of how to bring effective requirements management into product development. Keywords. Information technology, software engineering, user requirements, requirements engineering, requirements management 12.1 Introduction Many software problems arise from shortcomings in the ways that people acquire, document, agree on, and modify the product’s requirements. Typical problem areas include informal information gathering, implied functionality, inadequately defined requirements, and a casual change process.
Slide 94: 238 Zeljko Panian Most people wouldn’t ask a construction contractor to build a custom multi-hundred-thousand-dollar house without extensively discussing their needs and desires and refining the details progressively. Homebuyers also understand that making changes carries a price tag. However, people blithely gloss over the corresponding issues when it comes to software development. One of the widely quoted CHAOS reports from The Standish Group relates the consequences of casual approaches to requirements engineering (The Standish Group 2005). Year after year, lack of user input, incomplete and changing requirements are the major reasons why so many information technology projects fail to deliver all of their planned functionality on schedule and within budget. Nor do requirements issues only plague the early stages of a software project. One study at a large defence contractor found that 54 percent of all the errors were discovered after unit testing was complete, and that 45 percent of these were requirements or design errors (Davis 1993). Other studies also indicate that 40 to 60 percent of all defects found in a software project can be traced back to errors made during the requirements stage. Nonetheless, many organizations still practice ineffective methods for this essential project activity. The typical outcome is an expectation gap, a difference between what developers think they are supposed to build and what customers really need. 12.2 Stakeholders’ interests Nowhere more than in the requirements process do the interests of all the stakeholders in a software or system project intersect. These stakeholders include end users, customers acquiring the product, requirements analysts, project managers, developers, testers, regulators and auditors, manufacturing staff, sales and marketing, and field support or help desk staff. Handled well, this intersection can lead to exciting products, delighted customers, and fulfilled developers. Handled poorly, it is the source of misunderstanding, frustration, and friction that undermine the product’s quality and business value. Requirements are the foundation for all the subsequent software development and project management activities. Therefore, all stakeholders must be committed to following an effective requirements process. This process includes activities for: • Requirements development (eliciting, analyzing, specifying, and validating requirements).
Slide 95: User requirements engineering and management in software development 239 • Requirements engineering (dealing with the requirements once you have them in hand). Developing and engineering requirements is hard! There are no simple shortcuts or magic solutions. But a toolkit of techniques, coupled with tools to store and manage requirements, provides a powerful defence against the expectation gap. 12.3 Requirements are interrelated If John Donne had been a business analyst rather than a 17th century poet, he might have said, “No requirement is an island.” Requirements have a natural parent-child relationship because high-level user requirements can be decomposed into lower level functional requirements that, in turn, generate specific test requirements. For example, the requirement ‘Generate e-mail confirmation to customer online order’ would produce a number of distinct functional requirements (‘Verify e-mail address,’ ‘Transmit message,’ ‘Receive returned email message,’ etc.), each of which needs to be implemented in a code module and requires testing. Understanding these relationships is essential to planning and executing adequate test coverage. And when analyzing a proposed change to a requirement – or test procedure – it should be known what other requirements may be affected by the change. Traceability between requirements has to be maintained since this provides a useful tool for the analyst or software designer when trying to asses the software product quality. For example: • Users can define multiple types of requirements and maintain relationships between them. • Requirement types can be customized for each project. • Trace-to and trace-from views can display the parent/child relationship between requirements. • Requirements can be organized into folders for easier navigation. • Stakeholders need to be automatically informed via e-mail or requirements traceability alerts when a requirement changes. • Audit trail can track which values are changed and when. But, traceability between requirements only solves part of the problem. It is also essential to follow individual requirements through the application lifecycle to test, defects and release. That means testers and quality
Slide 96: 240 Zeljko Panian managers should be able see what and how much testing is planned for each requirement. They can than analyze the status of the testing to see how much has been completed and how many defects have been found. And when defects are found, it lets them see which requirements are affected. 12.4 The need for requirements management The major consequence of requirements problems is rework – doing something again that you thought was already done. Rework can consume 30 to 50 percent of total development cost (Boehm and Papaccio 1988) and requirements errors account for 70 to 85 percent of the rework cost (Leffingwell 1997). As illustrated in Figure 12.1 it costs far more to correct a defect that is found late in the project than to fix it shortly after it was created (Grady 1999). 120 100 80 60 116 40 20 3 Requirements 7 Design 9 Code 19 0 Test Operation Fig. 12.1. Relative cost to correct a requirement defect depending on when it is discovered Preventing requirements errors and catching them early, therefore, has a huge leveraging effect on reducing rework. Shortcomings in requirements cause no end of headaches on software projects. For example, creeping requirements contribute to schedule and budget overruns. Now, change is going to happen. Requirements change because initial elicitation activities are imperfect, because business needs
Slide 97: User requirements engineering and management in software development 241 evolve, and because customer expectations change once they see the product beginning to take shape. Project plans and commitments therefore need to anticipate change, rather than expecting that an initial stage of gathering requirements is all that’s needed. Requirements creep, though, is the uncontrolled growth of requirements well beyond the original scope boundary. The way in which requirements changes are incorporated into the product can degrade quality. Changes need to be introduced at the highest level of abstraction they affect and follow the links in the traceability chain to see the impact of each proposed change. Traceability data stored in an appropriate requirements management tool greatly facilitates this impact analysis. Many projects suffer from gold-plating. Developers might add unnecessary features they think the users will like, or users request excessively complex systems. Tracing each functional requirement back to its origin – such as a user task, a business rule, or a business objective - helps solve this problem. The result of all of these kinds of requirements problems is to slow the pace of software development. It doesn’t do you any good to work very efficiently on the wrong requirements. If you don’t get the requirements right, it doesn’t matter how well your team executes the rest of the project. 12.5 Accelerating development A sign in a high-school chemistry lab reads, “If you don’t have time to do it right, when will you have time to do it over?” (Bates 2003). To convince itself of the benefits, a firm should think about how much effort on their projects is misspent because of miscommunications, misunderstandings about requirements, missing information, or misstated requirements. The case for emphasizing solid requirements practices is an economic argument, not a philosophical or technical argument. A solid foundation of agreed-upon business requirements and project objectives establishes a shared vision, goals, and expectations. Frequent and intimate user involvement makes software development a collaborative partnership between IT and the customer community. It also reduces the chance of system rejection upon rollout. It is frustrating for everyone to release a product only to find that essential functionality is missing and other capabilities are included that no one will ever use. Good requirements processes ensure that the functionality built enables users to perform essential business tasks. Well-specified re-
Slide 98: 242 Zeljko Panian quirements also define achievable quality expectations, letting the team implement both the capabilities and the characteristics that will make the users happy. While typical projects spend perhaps 10 percent of their effort on requirements, investing more has a big payoff. A study of 15 projects in the telecommunications and banking industries revealed that the most successful projects spent 28 percent of their resources on requirements engineering (Hofmann and Lehner 2001). The average project devoted 15.7 percent of its effort and 38.6 percent of its schedule to requirements engineering. NASA projects that invested more than 10 percent of their total resources on requirements development had substantially lower cost and schedule overruns than projects that devoted less effort to requirements (Hooks and Farry 2001). In a European study, teams that developed products more quickly devoted more of their schedule and effort to requirements than did slower teams, as shown in Table 12.1. Table 12.1. Investing in Requirements (Blackburn et al. 1996) Faster Projects Slower Projects Effort Devoted to Requirements 14% 7% Schedule Devoted to Requirements 17% 9% Not all of the requirements development effort should be allocated to the beginning of the project. Don’t think of it as a “requirements phase,” but rather a set of requirements-development activities that are threaded throughout the project’s lifecycle. Projects that follow an incremental lifecycle will work on requirements in every iteration through the development process. Agile development projects take an incremental approach, rapidly building small portions of the product so users can refine their needs and developers can keep up with changing business demands. Agile projects will have frequent but small requirements development efforts (Light 2005). Regardless of how large an increment your team tackles, they need to understand the requirements for that increment. 12.6 Requirements development and management The goal of requirements development is to deduce, capture, and agree upon a set of functional requirements and product characteristics that will
Slide 99: User requirements engineering and management in software development 243 achieve the stated business objectives. Requirements management, then, involves everything that happens with the requirements in the product lifecycle once the requirements are developed, as shown in Figure 12.2. The demarcation between requirements development and requirements management is the defining of a requirements baseline. A baseline is a snapshot in time that represents the agreed-upon set of requirements for a specific product release. Launch Concept Test Gather Requirements Build Manage Requirements Design Fig. 12.2. Product Life Cycle 12.7 Strategies and best practices for better user requirements management A variety of strategies and practices can help software development teams bridge communication gaps and do a better job of understanding, documenting and communicating customer needs. Figure 12.3 synthesizes several best practices we evidenced in our research, and yet in the categories of elicitation, analysis, specification, validation, and management. • Requirements Elicitation – Defining the product vision and project scope; identifying stakeholders, customers and users; choosing elicitation techniques; exploring user scenarios. • Requirements Analysis – Creating visual analysis models; building and evaluating prototypes; prioritizing requirements using previously selected attributes.
Slide 100: 244 Zeljko Panian • Requirements Specification – Looking for ambiguities in text-based requirements; storing requirements in a central, usually shared database for better communication; tracing requirements into design, code and tests. • Requirements Validation – Reviewing the requirements; creating test cases from requirements. • Requirements Management – Managing requirements versions; adopting a change control process; performing requirements change impact analysis; storing requirements attributes; tracking the status of each requirement. IT GOVERNANCE Strategic & Operational Demand ANALYSIS Prioritization Verification Risk Assessment & Estimation ELICITATION Technique Stakeholders System Boundaries Glossary SPECIFICATION Detail Requirements Business Model Scenarios Prototype VALIDATION Review Signoff Baseline MANAGEMENT Storage Linking/Trace Measurement/Audit Reporting/Documentation Security Fig. 12.3. Strategies for Requirements Management 12.8 Traditional vs. novel approach to RM The traditional requirements engineering and management approach is to create documents that contain business, user, functional, and non-functional requirements written in natural language, preferably using the organization’s standard templates.
Slide 101: User requirements engineering and management in software development 245 But, it appears that the traditional document-based approach to storing requirements has numerous limitations (Ellis 2006): • It is difficult to keep the documents current and synchronized. • Communicating changes to all affected team members is usually a manual process. • It is not easy to store supplementary information (attributes) about each requirement. • It is hard to define logical links between requirements of various types and other system elements. • Tracking the status of individual requirements is cumbersome. • Concurrently managing sets of requirements that are planned for different releases or for related products is difficult. When a requirement is deferred from one release to another, an analyst needs to move it from one software requirements specification (SRS) to the other. • There is no convenient place to store those requirements that were proposed but rejected, nor those requirements that were deleted from a baseline. Sometimes someone may want to remember that these requirements had been proposed, because they might be back in scope one day. • Reusing a requirement means that the analyst must copy the text from the original SRS into the SRS for each other system or product where the requirement is to be used. • It is difficult for multiple project participants to modify the requirements, particularly if they are geographically separated. A novel approach to requirements management suggests usage of a software tool that can store information in a multi-user database, thus providing a robust solution to these restrictions. Users should be able to create various classes of requirements information and define unique sets of attribute values for each requirement class. Users should import requirements from source documents, filter and display the database contents, and export requirements in various formats. They should also define traceability links between pairs of objects stored in the database, as well as connecting requirements to items stored in other software development tools. Following are some of the tasks such a tool should help users to perform: • Tracking requirements status – Collecting the requirements into a database lets user know how many discrete requirements he has specified for the product. Tracking the status of each requirement during development supports the overall status tracking of the project. A
Slide 102: 246 Zeljko Panian • • • • project manager has good insight into project status if he or she knows that, e.g., 55 percent of the requirements committed to the next release have been verified, 28 percent have been implemented but not verified, and 17 percent are not yet fully implemented. Communicate with stakeholders – The tool should permit team members to discuss requirements issues electronically through threaded and interactive conversations. Additionally, e-mail messages can automatically be triggered to notify affected individuals when a specific requirement is modified or a change is proposed. Making the requirements accessible online can save travel costs and reduce document proliferation. Store requirements attributes – Possible attributes that provide a richer understanding of each requirement include priority, status, verification method, origin, person responsible, planned release, and so on. Everyone working on the project must be able to view the attributes and selected individuals be permitted to update their values (Frankl and King 2005). The tool should generate system-defined attributes such as the date a requirement was created and its current version number, and it lets you define additional attributes of various data types. One can sort, filter, or query the database to display subsets of the requirements that have specific attribute values. For example, a user might ask to see a list of all the requirements planned for release 2.3 that were assigned to Julie and have a current status of Implemented. Manage versions and changes – The project should define a requirements baseline. Software tool should provide flexible baselining functions and maintains a history of the changes made to every requirement. You can record the rationale behind each change decision and revert to a previous version of a requirement if necessary. The tool should also contain a built-in change-proposal system that links change requests directly to the affected requirements. Facilitate impact analysis – The appropriate software tool should enable requirements tracing by letting user define links between different kinds of requirements, between requirements in different subsystems, and between individual requirements and related system components – for example, designs, code, tests, and user documentation. These links then help when analyzing the impact that a proposed change will have on a specific requirement by identifying other system elements the change might affect. It is also a good idea to trace each functional requirement back to its origin or parent so that you know where every requirement came from.
Slide 103: User requirements engineering and management in software development 247 • Control access – An organization can define access permissions for individuals or groups of users. The software tool should enable information sharing with a geographically dispersed team through a Web interface to the database. The database uses requirement-level locking to permit multiple users to update the database contents concurrently. • Reuse requirements – Storing requirements in the tool's database facilitates reusing them in multiple projects or subprojects. Requirements that logically fit into multiple parts of the product description can be stored once and referenced when necessary to avoid duplicating requirements. In short, the software tool should be a powerful complement to a robust requirements engineering process. The tool alone will not guarantee that high-quality requirements are written, that system designer has talked with the right user representatives or that he has set the right priorities. However, the tool can keep a project team aligned on the specified requirements for each release, so they all agree when they are done and there will not be so many surprises when they get there. 12.9 Assessing return on investment Our research has convinced us that estimating the payback that better requirements can bring to the organization requires considering the following questions: • What fraction of organization’s own development effort is expended on rework (due to miscommunication)? • How much does a typical customer-reported defect cost the organization? • How much costs them a defect found in system testing? • What fraction of user-reported defects and what fraction of defects discovered during system testing originate in requirements errors? • How much of the organization’s costs – such as defect correction and unplanned enhancements – can be attributed to missing requirements or other requirements inadequacies? Aside from obvious benefits, improving requirements approaches leads to other valuable – though less tangible – outcomes. Fewer miscommunications on a software project reduce the overall level of disorder. Less dis-
Slide 104: 248 Zeljko Panian order lowers unpaid overtime, increases team morale, boosts employee retention and improves the team’s chances of delivering on time. Best of all, these benefits ultimately lead to higher customer satisfaction. 12.10 Conclusion Software development involves roughly 50 percent computing and 50 percent communication. Unfortunately, most IT professionals and teams are better at computing – user requirements, however, are almost entirely about communication. Because there are many links in the requirements communication chain, a breakdown in any of these links leads to significant problems. For example, if an analyst misunderstands stakeholder input about requirements, if important requirements information does not surface, or if an analyst and developer do not share the same understanding about requirements, the resulting product fails to meet customers’ needs. The inevitable outcome of requirements errors is time-consuming and costly rework. Experts report that rework can consume 30 to 40 percent of the total effort expended on a software project. Our study has indicated that nearly 50 percent of the defects identified on software projects observed can be traced back to errors in the requirements. Our analysis of potential return on investment from requirements suggests that requirements errors can consume between 70 and 85 percent of all project rework costs. It can cost up to 110 times more to correct a requirements defect found in operation that it would if that same defect has been discovered during requirements assessment and definition. To convince itself of the benefits, a firm should think about how much effort on their projects is misspent because of miscommunications, misunderstandings about requirements, missing information, or misstated requirements. Requirement engineering and management is a developing discipline that tries to solve those problems. A novel approach to requirements engineering and management suggests usage of a software toolkit that can store information in a multi-user database, thus providing a robust solution to these restrictions.
Slide 105: User requirements engineering and management in software development 249 References 1. Bates J (2005) Business in real time – Realizing the vision. DM Review, 05/2003 (http://www.dmreview.com/) 2. Blackburn JD, Scudder GD, Van Wassenhove LN (1996) Improving speed and productivity of software development: A global survey of software developers. IEEE Transactions on Software Engineering 22(12):875-885 3. Boehm BW, Papaccio PN (1998) Understanding and controlling software costs. IEEE Transactions on Software Engineering 14(10):1462-1476 4. Davis AM (1993) Software requirements: Objects, functions, and states. Prentice Hall PTR, Upper Saddle River (NJ) 5. Ellis K (2006) The executive briefing on the issues surrounding getting business requirements right. http://www.digital-mosaic.com, May 2 6. Frankl A, King T (2005) How to detect requirements errors – A guide to slashing software costs and shortening development time. http://www. n8systems.com, July 22 7. Grady RB (1999) An economic release decision model: insights into software project management. In: Proceedings of the Applications of Software Measurement Conference, Orange Park (FL), pp 227–239 8. Hofmann HF, Lehner F (2001) Requirements engineering as a success factor in software projects. IEEE Software 18(4):58-66 9. Hooks IF, Farry KA (2001) Customer-centered products: Creating successful products through smart requirements management. In: Proceedings of the AMACOM Conference, Miami (FL), pp 207-215 10. Leffingwell D (1997) Calculating the return on investment from more effective requirements management. American Programmer 10(4):13-16 11. Light M (2005) Agile requirements definition and management will benefit application development. http://www.gartner.com, Apr. 18 12. The Standish Group Staff (2005) The CHAOS report on software design. The Standish Group, Palo Alto (CAL)
Slide 106: Chapter 13 SSAF – A tool for active filter synthesis Elena Doicaru, Lucian Bărbulescu, Claudius Dan 1 1 1 2 Faculty of Automation, Computer Science and Electronics, University of Craiova str. Decebal, Nr.5, 200646 Craiova ROMANIA, dmilena@electronics.ucv.ro, luci@cs.ucv.ro 2 Faculty of Electronics, Telecommunication and Information Technologies, POLITEHNICA University of Bucharest, blvd. Iuliu Maniu, Nr. 1-3, 77209 Bucharest, ROMANIA, claus@mESsnet.pub.ro Abstract. In this paper a software tool used to determine the topological elements of active analog continuous-time filters is presented. The filter is described by an arbitrary transfer functions expressed as t (s) = p(s) / e(s) , where e(s) is the natural mode (pole) polynomial and p(s) is the transmission zero polynomial. The goal is to obtain filters having small sensitivities, low noise and high dynamic ranges. The synthesis method implemented in this program is based on the intermediate transfer functions (IFs) method. Keywords. Synthesis, Active Filters, Low Sensitivities, and Low Noise 13.1 Introduction In the VLSI era, as mixed analog/digital circuits of increasing complexity are implemented into a single IC, the need for low-sensitivity, low-noise, high performance filters steadily increases. A major application for con-
Slide 107: SSAF – A tool for active filter synthesis 251 tinuous-time filters is direct signal processing, especially for medium dynamic range applications, when high speed and/or low power operation are needed. For this reason we developed a software tool for automate synthesis of analog continuous-time filters – SSAF (Automatic Structural Synthesis of Active Analog Continuous-Time High-order Filters). The software tool was developed in C++ using Visual C++ 2005 programming environment and can be used to determine the topological elements of active analog continuous-time filters, described by an arbitrary transfer function in the form t (s) = p(s) / e(s) , where e(s) is the natural mode (pole) polynomial (of order n) and p(s) is the transmission zero polynomial (of order m). The goal is to obtain small sensitivities, very low noise and good dynamic range. The synthesis method selected is the intermediate transfer functions (IF's) method (Snelgrove and Sedra 1986). The method consists in obtaining an n-th transfer function, t(s), by means of a structure of n resistively interconnected integrators using the linearly independent IFs selected from the given t(s) following the general structure presented in Figure 13.1. The IFs have identical denominator polynomials, e(s), and arbitrary numerator polynomials of degree less than n. The program selects the IF's that are able to provide optimum performance structures. The significant advantage of this method consists in the possibility to optimize the filter performance at the abstract level of IFs while using other methods only topological level optimization is possible. 13.2 Program’s structure and algorithm The filter structure presented in Figure 13.1 can be described by a statevariable formulation: s ⋅ x(s) = A ⋅ x(s) + b ⋅ u (s) + ε(s), y (s) = c T ⋅ x(s) + d ⋅ u (s) (13.1) In equation (13.1) vector x(s) represents the circuit state (integrators output voltages), matrix A describes the interconnections between the n integrators, vector b contains the coefficients that multiply the input signal u(s), vector c contains the coefficients required to form the output, scalar d is the coefficient of the feed-through component and ε(s) is the vector containing the noise components at the integrator inputs. The dual sets of IFs, {fi(s)} and {gi(s)}, are given by:
Slide 108: 252 Elena Doicaru, Lucian Bărbulescu, Claudius Dan f i (s) = xi (s)/u (s); f (s) = (s ⋅ I − A ) −1 ⋅ b g i (s) = y (s)/ε i (s); g T (s) = c T ⋅ (s ⋅ I − A ) −1 (13.2) The {fi(s)} set contains the transfer function from the filter input to the integrator outputs and the {gi(s)} set can be physically interpreted as the integrators noise gains. Fig. 13.1. Generic Filter Structure From these sets we can obtain the {A, b, c, d} topological parameters using the following relationships: A = F ⋅ E ⋅ F −1 , b = F ⋅ 1, c T = t T ⋅ F −1 , d = t n +1 , t (s) = t T ⋅ v (s) + t n +1 (13.3) f (s) = F ⋅ v (s), g (s) = G ⋅ v (s), vi (s) = 1 /(s − ei ), i = 1, n, G T = H ⋅ F −1 where t is a vector containing the n residues of t(s) at the poles, t n+1 is the residue at s = ∞, F is a matrix containing the residues of the f functions at the poles, G is a matrix of the residues of the g functions, ei are the roots of e(s), E is the diagonal matrix having the roots ei as its elements and H is a diagonal matrix formed from the residues of t(s). The sensitivities of the A, b, c, d parameters, the integrator gain γi and the operational amplifier gain µi(s) hardly depend by the IFs set (Snelgrove and Sedra 1986). In the terms of {A, b, c, d} elements the gain of the integrator i is proportional to
Slide 109: SSAF – A tool for active filter synthesis 253 the i row sum of system (13.1.a). From classical sensitivities results (Snelgrove and Sedra 1980) can be demonstrated that the minimum sensitivity realization has: f i (s) ⋅ g i (s) = −(1 / n) ⋅ [d t (s) / ds], ∀i = 1, n (13.4) If we assume that the noise signals, modeled by ε(s), have white spectra with equal densities N i2 , the output noise will have a power spectrum and a rms level given by: Pn 0 (ω ) = N i2 ⋅ ∑ g i ( j ⋅ ω ) , Pn 0 (ω ) = N i2 ⋅ ∑ g i ( j ⋅ ω ) i i 2 2 2 (13.5) The mathematical analysis emphasizes the fact that the best realizations are those obtained by orthogonal, orthonormal and derivative IFs sets. The SSAF program generates all these types of IFs sets. The general structure of the program is presented in Figure 13.2. An IFs set is orthogonal if the all functions of the set are linearly independent and their inner product is zero. An IFs set is orthonormal if all fi(s) are orthogonal and f i 2 = 1, ∀i = 1, n . Such sets can be obtained from any set of independent {ui(s)} by using the Gram-Schmidt ortho-normalization procedure (Şabac 1981). The inner products, ui • v j , and the norm of functions, v j 2 = vi • vi , required by the Gram-Schmidt procedure, are determined using the residue theorem. This is possible because of rational form of functions. So the program uses the following relations: ∞ u i • v j = ∫−∞ R (ω ) ⋅ dω =2 ⋅ π ⋅ j ⋅ ij m Im( polm ) >0 ∑ rez( Rij , polm ) (13.6) The function residues are determined in conformity with classical definition. The orthonormal functions are f i = vi / vi 2 . Then the topological elements are determined in conformity with relation (13.3). Their sensitivities and the filter noise are evaluated and the following sensitivity and noise criteria are listed: ( SA = max Real(StAisj ) ), Sb = max Real(Stb(s ) ), Sc = max Real(Stc( s ) ), (13.7) i , j , ω∈Ra i, ω ∈ Ra i i , ω∈Ra i t Sd = max Real(Std( s ) ), Sd = max Real(Std( s ) ), Sγ = max Real(Sγ( s ) ) ω∈Ra ω ∈ Ra i, ω ∈ R a i Pzg = Pn 0 (ω ) 2 N =1 i = ∑ gi ( j ⋅ ω) i 2 2
Slide 110: 254 Elena Doicaru, Lucian Bărbulescu, Claudius Dan Since sensitivities are proportional to {fi(s)} it results that various sensitivities (magnitudes and phases) go to zero in the pass-band. In a ladder only magnitude sensitivity is zero. From eq. (13.4) one can see that if the minimum sensitivity realization exists, then {fi(s)} must divide t'(s). In the SSAF program, {fi} are chosen so that the factors of t'(s) missing from fi(s) (that could be the factors of gi(s) in the case of minimum-sensitivity realizations) can appear in fn- i (Doicaru 1998). Load/Save Module Export to Spice Module Application Core Derivative functions Module Fig. 13.2. Application Structure Orthogonal functions Module Orthonormal functions Module Presentation Module Unlike orthogonal and orthonormal IF's that provide a single set of n functions fi, in the DIF's case we can obtain a lot of n functions sets. The program generates all DIF's sets and selects one or more DIF's sets, following the user options. The first step in the DIF's sets determination is to obtain the derived transfer function t ′(s) and his roots. The DIF's can't be generated in two cases: (1) if the transmission zero polynomial order of t ′(s) is less than n; (2) if in all sets of IF's we have at least a function with the transmission zero polynomial order greater than n. The next step is to separate the real roots from the complex roots. The conjugated complex roots are grouped in binomials. Then, the monomials and binomials are binary coded. This binary code facilitates the simultaneous generation of fi and fn-I DIF's of a set. The number of monomials and binomials possible combinations is reduced by generating only the combinations that yield polynomials with order less than n. These combination variants, representing all possible physical variants, are combined once again in n/2 groups.
Slide 111: SSAF – A tool for active filter synthesis 255 13.3 SSAF program - Implementation and operation As presented previously, the application contains several modules, each with its own role, as follows: • Load/Save Module: this module is used to save or load a filter to of from a file. The files must have the extension “.mil” and their format is proprietary and text-based. • Export to Spice Module: this module is used to export the filter into a spice-recognized file, thus offering the possibility to obtain a simulation. • Presentation Module: this module is used to obtain several information about the filter such as sensitivity, residuum etc. Also a schematic view of the filter can be obtained using this module. • Derivative function module: is used to compute the derivative functions for the filter. • Orthogonal function module: is used to compute the orthogonal functions for the filter. • Orthonormal function module: is used to compute the orthonormal functions for the filter. • Application Core: this module is the bridge between all previous modules. It contains the application GUI and links to the functions implemented by all the previous modules. Each of the previous modules is implemented as a set of C++ classes. All modules exchange data with the application core in both ways. One piece of data that is very important for the entire application is the transfer function represented as two polynomials. Each polynomial is saved within the application as a template class. The template for this class was needed to represent the polynomial coefficients. Usually those are real numbers, but the class allows the usage of complex values too.
Slide 112: 256 Elena Doicaru, Lucian Bărbulescu, Claudius Dan Fig. 13.3. Coefficients’ Specification and Computed Residuum Working with the application is a very easy task. After starting it the user can either choose to create a new filter or to open an existing one. The creation of a filter can be performed in two ways: either by entering the coefficients for the P(s) and E(s) polynomials (see Figure 13.3), or by specifying their degrees and complex zeroes. After the required data is entered, the user may decide which type of functions he/she want to generate. The application will generate the functions and the result will be displayed in a list form. The user can view information about IFs sets or about the transfer function t(s), such as the Residuum (see Figure 13.3), the userfriendly representation of the transfer function and its derivative. The elements of topological set {A, b, c, d} and their computed sensitivity are also given. Another feature is the application’s ability to generate a Spicecompatible file, based on which a simulation of the filter can be performed. In this way the user can further test the filter before deciding to implement in using real hardware. 13.4 Conclusion The paper presented a C++ code program for the synthesis of continuoustime analog filters. The synthesis method is based on the selection of an appropriate set of intermediate transfer functions. This way the filter sensitivity, noise and dynamic range properties are easily determined from these intermediate functions. Therefore, it is possible to optimize the sensitivity, noise and dynamic range by the appropriate choice of intermediate functions. The synthesis program is easy to use and the user can select the optimum realization in rapport with one of the following performances: A, b, c and d sensitivities, noise and dynamic range. The solution helps the user to define better filters without using any expensive hardware components. He/she can generate several implementations for a filter and then, after examining the results using a simulation environment, can choose the best solution for his/she’s needs. The user-friendly interface is very intuitive and the help integration offers further information about the usage of SSAF. Acknowledgement. This work was supported by the CNCSIS Research Project no. 29C/08.05.2007, theme no. 5, CNCSIS code no.602.
Slide 113: SSAF – A tool for active filter synthesis 257 References 1. Doicaru E (1998) The optimum automatic synthesis at active analogue continuous-time high-order filters. In: 6th International Symposium on Automatic Control and Computer Science, Volume II Computer Science, Iasi, Romania, pp 182-189 2. Press WH, Teukolski SA, Vetterling WT, Flannerry BP (1992) Numerical recipes in C: The art of scientific computing. Cambridge University Press, Cambridge 3. Snelgrove WM, Sedra AS (1980) A novel synthesis method for state-space active networks. In: Proc. Mid-west Symp. Circuits and Systems, Toledo 4. Snelgrove WM, Sedra AS (1986) Synthesis and analysis of state-space active filters using intermediate transfer functions. IEEE Transaction on Circuits and Systems CAS-33:287-300 5. Şabac IG (1981) Special Mathematics (in roumanian). Editura Didactica si Pedagogica, Bucuresti