2001cs sub考试大纲

主题 2001CSsubject考试大纲    ppmm  2001-09-07 03:22:35

I. SOFTWARE SYSTEMS AND METHODOLOGY — 35%
A. Data organization
1. Data types
2. Data structures and implementation
techniques
3. File organization (e.g., sequential,
indexed, multilevel)
B. Program control
1. Iteration and recursion
2. Functions, procedures, and
exception handlers
3. Communication and synchronization
C. Programming languages and notation
1. Constructs for data organization and
program control
2. Scope, binding, and parameter passing
3. Expression evaluation
D. Systems
1. Compilers and interpreters
2. Operating systems, including resource
management and protection/security
3. Networking and distributed systems
4. System development tools
5. System performance
*************************
II. COMPUTER ORGANIZATION AND ARCHITECTURE — 20%
A. Logic design
1. Implementation of combinational and
sequential circuits
2. Functional properties of digital
integrated circuits
B. Processors and control units
1. Instruction sets
2. Register and ALU organization
3. Number representation
4. Control sequencing
5. Data paths
C. Memories and their hierarchies
1. Speed, capacity, cost, allocation
2. Cache, main, secondary storage
3. Virtual memory, paging, segmentation
D. Communication
1. Bus, switch, and network structures
and protocols
2. I/O
3. Synchronization
E. High-performance architectures
1. Pipelining super-scalar and out-of-order
execution processors
2. Parallel computing
3. Distributed computing
********************************
III. THEORY — 25%
A. Automata and language theory
1. Models of computation (finite automata,
pushdown automata, Turing machines)
2. Formal languages (regular languages,
context-free languages)
3. Decidability
B. Design and analysis of algorithms and
computational complexity
1. Exact or asymptotic analysis of the best,
worst, or average case for the time and
space complexity of specific algorithms
2. Algorithmic design techniques
(divide and conquer, dynamic
programming, greedy)
3 Upper and lower bounds on the
complexity of specific problems
4. NP-completeness
C. Correctness of programs
1. Formal specifications and assertions
2. Verification techniques
*****************************************
IV. MATHEMATICAL BACKGROUND — 15%
A. Discrete structures
1. Mathematical logic
2. Elementary combinatorics, including
graph theory and counting arguments
3. Elementary discrete mathematics,
including number theory, discrete
probability, recurrence relations
B. Numerical mathematics
1. Computer arithmetic, including number
representations, roundoff errors, overflow
and underflow
2. Classical numerical algorithms
3. Linear algebra
**********************************
V. OTHER TOPICS — 5%
Topics including modeling and simulation,
information retrieval, artificial intelligence,
computer graphics, data communications,
databases, VLSI, logic programming.