11
appendix
Calculate science as a discipline definition
Computer Science and Engineering is a systematic study of the system of the algorithm process of describing and transforming information, its theory, analysis, design, efficiency, implementation and application - The basic problem of all computational science is that what can be automatically carried out [2, 3]. The disciplines and algorithms theory, the number of logic, and the invention of storage program electronic computers are formed in the early 1940s.
The origin of the calculation can be extended to mathematics and engineering. Mathematics divides the analysis into this area, while the project is divided into this field. This subject includes its own theory, experimental methods and engineering. This is different from many other natural sciences. Many other natural sciences and engineering disciplines using their results are separate (for example, chemical and chemical engineering principles), computer science and engineering are unsurable, because the science and engineering form of this discipline is fundamentally penetrated.
Calculating the main object of mathematics has been thousands of years. Many models of natural phenomena are used to export equations, and its solution leads to the prediction of natural phenomena. For example, ballistic calculation, weather forecast, and fluid flow, etc. Many methods of solving these equations have been given. For example, the method of solving the method of linear equations, the solution of the differential equation and the integral of the function of the function. Almost at the same time, the calculations required for mechanical system design have become the object of the main concern. For example, algorithms calculating static object pressure, calculating algorithms and measurements of moving object inertia ratios are much larger or much more distances.
A long-term cooperation of engineering and mathematics has always been a mechanical tool for calculation. Some surveyors and nautical instruments dates back to thousands of years ago. Pascal and Leibniz have made an arithmetic calculator in the middle of the 17th century. In the 1930s, Babbage envisioned a "analyzer" that allows for logarithmic, triangular functions, and other arithmetic functions. Although his machine is not completed, he gives the later work to inspire. By the 1920s, BUSH made an electronic simulation computer to understand the general differential equations. At the same time, there is a problem. Reduce, multiply, remove and open the square electric computer. Later, the electronic trigger becomes a bridge from these machines to digital computers without moving parts.
Logic is a branch of mathematics, researching the formal principle of rationality guidelines and reasoning. Since the era of Europe, it has been a tool for strict math and scientific arguments. Since the 19th century, people began to find universal logic systems, which should not see incompleteness in known interpretation systems. In the fully system, it is possible to mechanically determine that any given statement is true or false. GoDel issued his "incompletely-dictator" in 1931, pointing out that this system does not exist. By the late 1930s, Tuling explored the idea of universal computers. This general purpose computer can imitate any other process procedure for one step forward. His discovery is similar to Godel idea, that is, some good definitions cannot be solved with any mechanical process. The logic is important, not only because it deeply sees the limitations of automatic calculation, but also because it is noted that the symbol string is noted, or the number already encoded. It can be interpreted as data and can be interpreted as procedures.
This view is a key idea that distinguishes the storage program computer and computing machinery. The algorithm step is encoded as a machine representation and is stored in the memory, and decoded when used in the memory and executed by the processor. The machine code can be mechanically derived from a high-grade symbolic form (programming language).
This is the historical origin of ancient computing and logical symbol operations, and the modern representation of electronics and information. They have led to the birth of the calculation discipline.
We confirmed several branches of calculating science:
1. Algorithm and data structure
2. programming language
3. Architecture
4. Value and symbol calculation
5. Operating system
6. Software Methodology and Engineering
7. Database and information retrieval
8. Artificial intelligence and robotics
9. Human machine communication
Each branch has a common basis of subjects, the theoretical part of the essence, meaningful abstraction and important design and implementation. Theoretical Research as the development of mathematics in the field of this branch. Includes support theory, pictograph theory, combined theory or form language. Abstract (modeling) handling potential implementation models. These models ignore some technical details, while saving essential features, and provides tools for future behavior. The process of design is a given problem, export requirements, and technical conditions, repeatedly develop and test the prototype, thereby achieving a system. Design includes experimental methods. There are several forms of experimental methods in computational science: measurement procedures and systems, verify the rationality of hypothesis, and make abstraction through the prototype. Although software methodology is essentially a design, it contains the theoretical and abstract substantive components. Therefore, we make it a branch area. on the other hand. Parallel and distributed calculations penetrate into all branches and their hierarchical theories, abstractions and design). They are neither a branch area, nor as a hierarchy in a branch. The following sections provide details of three levels in the fields of branches. Theory and abstraction, the boundaries of abstract design must be blurred, and the appetite of each person may vary.
Our goal is to provide discipline guidelines through the discipline's profile characteristics, but not detailed columns. It should be remember that this discipline guide is a course plan, which is just a framework required to design a course. At the same time, it should be remembered that this discipline guide is a changing organism instant to grab the shot. It requires constant test and regular changes.
An algorithm and data structure
Some specific types of problems and their effective solution are studied in the art. Basic issues include: What is the best algorithm? What is the most storage space and time? What is the compromise for space and time? What is the best way to access data? The best algorithm What is the bad situation? What is the extent of the algorithm? Algorithm is generally to what extent - what type of problem can be treated with a similar method?
Theory
The main principle of the theory of algorithms and data structures is:
(1) Credible theory. It defines what the machine can do, what can't do.
(2) Computational complexity theory. It tells you how to measure the time and space requirements of the Mi-machi function, link the size of the problem and the best or worst case of the problem algorithm, and provide a method of demonstrating any possible solution to the problem.
(3) The time and spatial boundaries of algorithms and algorithms.
(4) Intractability level. For example, deterministic multi-class time can be solved (P-issues); problems in question (NP-issues); and effective parallel can be solved (NC-issues).
(5) Data stream from the algorithm to the parallel computing, lower bound and image of the machine communication path.
(6) The probability algorithm is obtained in the time and space than the deterministic algorithm and obtains TF deterioration at sufficiently high probability. Monte Carlo method.
(7) Cryptography.
(8) Chart, recursive function, progressive relationship, combination theory, calculus, induction, predicate logic and timeline logic (Temport
Logic), semantics, probability, and statistics.
2. abstract
Abstract part of the algorithm and data structure is:
(1) Effective optimal algorithm for important problems and analysis of best, worst, and general performance.
(2) Classification of the impact of control and data structures on various problems of time and space requirements.
(3) Important technical types, Divide-and-Conquer, Gri Land Algorithm, Dynamic, Finite State Machine Interpreter, Stack Machine Interpreter.
(4) Parallel and distributed algorithms, divide the problem to divide the task of the task can be performed on different processors.
3. Design
The main contents of the avoidance and experiments in the field of algorithms and data structures are:
(1) The choice, implementation, and test of the algorithm of the most problem classes. These problems include search, sorting. The random number of leafs and structural patterns match.
(2) Implementation and testing of general methods can be used for many types of issues. Such as Hashing, Figure and Tree.
(3) Realization and testing of distributed algorithms. For example, a network protocol, a distributed data update, a signal (Semaphores), a deadlock detector, and a synchronization method.
(4) Implementation and testing of storage management. For example, the Universal Unit Collection, a Buddy System, a table (LISTS), table (Tables), and pagination.
(5) A large number of experimental tests for combined problem heuristic algorithms. (6) Password protocols that are safe and reliable and secret communication.
Second, programming language
The symbolic expression, algorithm and data symbolic expression, algorithm and data symbolic expression, and efficient translation from advanced languages to machine code. Basic problems include: What is the possible organization of a virtual machine (data type, calculation, control structure, introduction new type and operation) of a virtual machine, how these abstractions are implemented on a computer? What kind of symbol is used? Expression (syntax) can effectively indicate what computer should do?
Theory
The main part of the theory of programming language is:
(1) Form language and automaton, including syntax analysis and language translation.
(2) Figure foreground (foundation of process language).
(3) Form semantics: Define a computer mathematical model and a model, grammar and realization relationship. The main method includes the symbol, algebraic, operational, and axioming semantics.
(4) Support areas: predicate logic, timing logic, near generation and mathematics.
2. abstract
The main part of the abstract area of the programming language area includes:
(1] Classification of languages based on grammar and dynamic semantics: ie static, dynamic, functional, process, object-oriented, logical, illustrative, packet transfer, and data streams.
(2) Language Classification by application: ie commercial data processing, simulation, table processing, and graphics.
(3) Classification of the main grammar and semantic model of the program structure: that is, the process classification, functional synthesis, abstract data type, and parallel process of communication.
(4) The main type of abstract realization model for each language.
(5) Method of optimization of syntax analysis, compilation, interpretation, and bid code.
(6) Method for automatically generated by syntax analyzer, scanner, compiler component, and compiler.
3. Design
The main content of the design and experiment of programming language tendency is:
(1) With a particular abstract machine (semantic) and syntax, it can form a unified implementable overall specific language. For example, pro Process (COBOL, FORTRAN, Algol, Pascal, ADA, C), functional (LISP), data stream (Sisal, Val), object-oriented (Prolog), string processing ( Snobol), and parallelism (CSP, OCCAM, CONCURRENT PASCAL, MODULA2).
(2) Specifiable methods for specific types: Run time model, static and dynamic execution method, print inspection, storage, and register allocation, print detacters, cross-cutters, and interpreters, looking in parallelism in sigma system.
(3) Program design environment.
(4) Syntax analyzer and scanner generator (such as YACC, LEX), compiler generator.
(5) Syntax and semantic error check programs, profiles, error, and tracking.
(6) Programming language method for file processing functions, such as tabulation, diagram, chemical formula, expansion sheet, equation, input, and output, and data switches. Other applications, such as statistical processing.
Third, the architecture
BACKGROUND OF THE INVENTION Hardware (and corresponding software) is organized into effective and reliable systems. Basic problems include: What is the good way to implement processors, storage, and communications in a machine? How do we design and control large computing systems and persuasive indicate that they can complete expectations in the case of errors and faults J. What type of architecture enables many processing units to work effectively, implement a computing parallel? How do we measure computers?
L. Theory
The main part of the architecture field is:
(1) Boolean
(2) Switch theory
(3) Coding theory
(4) Finite state machine theory
(5) Statistics, probability, queuing theory, reliability theory, discrete mathematics, number theory, and different counting of arithmetic and other support areas.
2. abstract
The abstract main part of the architecture field is:
(1) Limited state machine and Boolean model associated with the circuits that functions and behavior.
(2) Other general methods of combining the system by the basic components.
(3) Calculate the circuit and finite state machine of the arithmetic function on a limited domain.
(4) Model of data pathway and control structure.
(5) Optimization of instruction systems in various models and workload conditions. (6) Hardware reliability: redundancy, error detection, recovery and testing.
(7) The compromise between space, time and organization in the design of the VLSI device.
(8) Tissue of various computing models: timing, data stream, table processing, array processing, vector processing, and packet transfer.
(9) Determination of grading design: the system configuration stage, program level, command system level, register level, and gate level.
3. Design
The design and experiment of the architecture field is:
(1) Quickly calculate the hardware unit. For example, an arithmetic function unit, a cache.
(2) The so-called von. Orman Machine (single-instruction sequence storage program computer): Simple instruction system computer (RISC) and complex instruction system counting machine (CISC) implementation.
(3) Effective methods for storing and recording information, detecting and correcting errors.
(4) Special treatment pathways for errors: recovery, diagnosis, reconstruction, and backup processes.
(5) Computer Aided Design (CAD) System and Logic Simulation, Map Generation Program, Trouble Diagnosis, and Silicon Compiler for Visi Circuit Design.
(6) Machine implementation of various calculation models, such as data stream, tree, LISP, Hypercube, vector, and multi-microcessor.
(7) Supercomputers such as CRAY and CYBER.
Fourth, numerical and symbol calculation
The general method of effective and accurately solving the equation exported by the system's mathematical model by the system. Basic problems include: How can we use poor discrete processes to accurately approach continuous or endless process? How do we deal with errors caused by approximation? How can I solve the given type of equation quickly? How to make equation Perform symbol operations, such as points, differential and simple, etc., how to add these questions to valid, reliable, high-quality mathematics software package?
Theory
The main part of the estate and symbol calculation is:
(1) Number
(2) Linear dedication
(3) numerical analysis
(4) Nonlinear mechanics
(5) Fields such as calculus, real analysis, complex analysis and algebra.
2. abstract
The abstract main part of the numerical and symbol calculations is:
(1) The form of physical problems is a continuous (sometimes discrete) mathematical model.
(2) Discrete approximation of continuous problems. Backward error analysis, error propagation and stability of linear and nonlinear system solutions. Special methods in special circumstances, such as fast Fuye leaf transform and Poisson.
(3) Finite element models of large-class problems that can be given by regular mesh and boundary values, corresponding iterative methods and convergence theories: direct, implicit, multi-grid, and convergence rate. Parallel solution. Automatic grill refining when numerical integral.
(4) Symbol points and differentials
3. design
The main contents of the design and experiments of numerical and symbol calculations are:
(1) Senior problem formulation system, such as CHEM and Web.
(2) Linear algebra, normalized equations, statistics, nonlinear equations, and optimized, specially designed libraries, such as Linpackk, Eispack, Ellpack.
(3) Methods of mapping finite element algorithms to specific structures For example, these specific structures may be a plurality of grids on a superconfigure.
(4) Symbol operations, such as MacSyma and Reduce, can make powerful non-obvious operations, especially differential, integral, and expression to minimal termination.
V. Operating system
BACKGROUND OF THE INVENTION Multi-resources allows multiple resources to effectively cooperate in program execution. Basic problems include: What are the visible objects and permissible operations at all levels of computer systems? What is the minimum operating set that allows them to be effective for every type of resource (visible objects on a certain level)? How to organize interface Make the user only deal with the abstract form of the resource, but what is the actual details of the hardware? For job scheduling, memory management, communication, software resource access, communication, reliability, and secure control strategy between the task? You should be able to expand, as long as the construction rule of the application is repeated. Then, what is the principle of this expansion? How to organize distributed calculations, enabling many autonomous machines that are connected by communication networks to participate in the same calculation, and detailed network protocols, host locations, bandwidth and resource names, people Is it not visible?
1. theory
The main part of the theory of operating system is: (1) concurrency theory: synchronous, deterministic and dead lock.
(2) Scheduling theory, especially processor scheduling.
(3) The theory of program behavior and memory management, including the optimal policy of storage allocation.
(4) Performance Modelization and Analysis.
(5) Memory packaging, probability theory, queuing, queuing network, communication and information theory, timelic logic, and cryptography.
2. Abstract
The main part of the abstract operating system is:
(1) Allows the user to consider the abstract principle to operate on the same type of resource (for example, a process rather than the processor, virtual memory instead of the processor, the virtual memory instead of the processor, the virtual memory instead of the processor, and the file rather than the disk).
(2) The user interface can be perceived to the binding of the internal computing structure.
(3) Model of important sub-problems, examples of these sub-issues have process management, memory management, job scheduling, secondary storage management and performance analysis.
(4) Model of distributed placed. For example, customers and servers, cooperation timing processes, messaging, and remote processes calls.
(5) Safety calculation model. For example, access control, authentication, and communication.
(6) Network. Including hierarchical protocols, naming, remote resource usage, help services, and local network protocols, such as markers, and Time bus.
3. design
The main contents of the design and experiments in the operating system are:
(1) Time-time system, automatic storage of allocator, multi-level scheduler, storage manager, grading file system, and other models such as system components such as commercial system based.
(2) Techniques for building operating systems, examples of these operating systems are UNIX, MULTICS, MACH, VMS, and MS-DOS.
(3) Construction of a practical library technology, these utilities include editor, file constructors, compilers, connector, and device drivers.
(4) Files and file systems.
(5) Analog package of queuing network models and actual system performance assessments.
(6) Network structure, such as Ethernet, FDDI, token ring network, SNA and DECNET.
(7) Contains protocol technology, virtual circuit protocol, interactive network (Internet), real-time conference and X.25 in the Ministry of National Defense Agreement Set (TCP / IP).
