Catálogo de publicaciones - libros

This chapter discusses the well-known knapsack problem. This problem is another classical problem and is quoted as often in the problem-solving literature as the traveling salesman problem of Chapter 6. According to the problem classification of the model theory approach, the knapsack problem is more difficult than the traveling salesman problem because the former is less structured than the latter. Since the target state is not well specified except that it should be an optimal state, the stopping condition of the knapsack problem requires an involved expression to secure optimality.

This chapter discusses a class schedule problem as an I-O-C problem. The problem relates to the design of a class schedule for a college and includes assignment of instructors, subjects, and classrooms to slots of a weekly timetable. In order to simplify the problem, we will consider the class schedule for one grade of a specific department.

This chapter discusses a data mining system as a nontrivial example of the model theory approach. Needless to say, the system has a special significance for the model theory approach due to its role in the intelligent management information system of Fig. 1.2. Because a data mining system is not usually considered as a problem-solving system, this trial may seem strange. This trial has three objectives. First, from a theoretical viewpoint, this trial demonstrates how the model theory approach is applicable to a more realistic system than a simple academic example. It is shown thatalthough a data mining problem is the least structured, the model theory approach is applicable to it in constructing a solver. Second, from a practical viewpoint, because the model theory approach is strong in exploration of the structure of a target system, good insight into a data mining system can be obtained throughout the trial. This is beneficial in practice because a data mining system has become crucial for sofisticated management. Third, this chapter shows how tuning of stage 6 of Fig. 4.6 can be performed using the insights. Because the goal-seeker of the model theory approach is developed on a general level, it is desirable in practice that a generated solver be tuned according to specific properties of the target.

Because the problem classification of Chapter 4 is a general one, any problem can be covered by it. Furthermore, because the methodology of Chapters 4 and 5 is also general, in principle every problem can be attacked by it. It is obvious, however, that there are problems that cannot be solved by it in practical sense. Extension of the basic extSLV of Fig. 4.5 is necessary to address more difficult problems. In the model theory approach there are two ways for extension: introduction of a hierarchical multilevel system [] and extension to a task skeleton model. This chapter introduces the task skeleton model. An intelligent data mining system is developed as a demonstration of the model.

This chapter presents the model theory approach to development of a transaction processing system (TPS), which is the main target of current systems engineering. With this approach, the system developer constructs the specification for the target system based on the relational structure of the TPS (presented in Section 1.2). The specification is described in computer-acceptable set theory (introduced in Chapter 2) and then compiled into an executable TPS in extProlog. The system is executed under the control of a standardized user interface (UI) designed in PHP. The UI has been developed on several levels of sophistication. For the sake of simplicity, this chapter discusses TPS development using the simplest UI.

This chapter presents an example of systems development involving a combination of the methodologies for developing a transaction processing system and a solver system treated separately in previous chapters. The user model includes a solver-type atomic process as well as transaction-type processes. The target system is a temporary staff recruitment system (employment system) that must perform optimum matching between job-seeking applicants and job-offering clients as a typical problem-solving activity. The development leads to a browser-based intelligent management information system (MIS), which is a modification of Fig. 1.2 in Chapter 1.

The target of the model theory approach is development of an intelligent MIS, as illustrated in Fig. 1.2 and in Fig. 15.2. The lower part of the system, a transaction processing system (TPS), constitutes the infrastructure of an MIS. Its main task is management of data. Although a simple file system is used for TPS development in Chapters 14 and 15, the model theory approach requires implementation of database connectivity because the file system is, in fact, supported by a database system. The language extProlog and hence the model theory approach are extended to implement that function.

This chapter presents the theoretical base of extProlog. It is discussed as a logic programming language. It would therefore be convenient to start with the definition of logic programming; however, there is no formal definition of a logic programming language. It is commonly understood that a logic programming language is one that has the ultimate goal of providing clarity and declarativeness for programming. In general, a programming activity consists of two parts: design of the algorithm (heuristic) and its implementation in a language. The algorithm part can be further decomposed into a logic aspect and a control aspect. The logic aspect refers to the facts or data and the rules and requirements specifying what the algorithm does. The control aspect refers to how the algorithm can be implemented by arranging the rules and requirements in a particular order. The latter aspect becomes serious when the algorithm is modified.

An extProlog program is executed by the extProlog interpreter. This chapter discusses how the interpreter is designed for extProlog. Chapter 17 indicated that the main functions of a Prolog interpreter are unification and backtracking. A Prolog program is executed by these functions. Then, it is natural to guess that a generalization of a pushdown automaton (PDA) can be a model for the interpreter, where the push-down stack of a PDA can handle the backtracking while the head can perform unification, provided an appropriate Prolog database for matching is supplied [Takahara and Iijima, 1990]. The Prolog interpreter of this book is constructed as a generalized PDA with a Prolog database.