Introduction
Chapter 0: Introduction
• Computer science is the discipline that seeks to
build a scientific foundation for such topics as
– computer design
– computer programming
– information processing
– …etc.
• Computer science provides the underpinnings for
today’s computer applications as well as the
foundations for tomorrow’s applications.
Algorithms: Definitions
• Algorithm
– a set of steps that defines how a task is performed.
• Program
– a representation of an algorithm.
• Programming
– the process of developing a program.
• Software
– programs + algorithms.
• Hardware
– machinery: whatever isn’t software.
Computer History
What is computer??
An Abacus
Origins of Computing
Machines
• Early computing devices
– Abacus: positions of beads represent
numbers
0 1600s-1800s 機械式(轉輪)
積體電路
• 積體電路可以分為以下幾類：
– 小規模積體電路 ( SSI 英文全名為 Small-Scale
Integration, 幾十個邏輯閘以內)。
– 中規模積體電路 ( MSI 英文全名為 Medium-Scale
Integration, 幾百個邏輯閘）。
– 大規模積體電路 ( LSI 英文全名為 Large-Scale
Integration, 幾萬個邏輯閘）。
– 超大規模積體電路 ( VLSI 英文全名為 Very-large-scale
integration, 幾十萬個邏輯閘以上）。
– 甚大規模積體電路 ( ULSI 英文全名為 Ultra-Large Scale
Integration, 百萬個邏輯閘以上）。
• Early computing devices
– Gear-based machines (1600s-1800s)
• Positions of gears represent numbers
• Blaise Pascal, Wilhelm Leibniz, Charles
Babbage (progression of flexibility)
• Blaise Pascal
– 1623-1662,France
– Pascal Machine
• Addition algorithm
• Charles Babbage’s Machine
(1792-1871)
– Print output values on paper
– Programmable
• His assistant Augusta Ada Byron is often
identified today as the world’s first
programmer.
– Punched Card
• Idea from Jacquard Loom in 1801
The London Science
Museum's replica
Assembled after his death
by Babbage's son, using
parts found in his laboratory.
Punched Cards
• Early data storage: punched cards
– First used in Jacquard Loom (1801) to
store patterns for weaving cloth
– Stored programs in Babbage’s Analytical
Engine
– Popular through the 1970’s
Jacquard Loom
Jacquard Loom
Punched Cards
Early computers
• Based on mechanical relays (繼電器)
– 1940: Model K: Stibitz at Bell Laboratories
– 1944: Mark I: Howard Aiken and IBM at Harvard
• Based on vacuum tubes (真空管)
– 1937-1941: Atanasoff-Berry Computer (ABC) at Iowa
State
• The first “computer”, NO CPU, DRAM
– 1940s: Colossus: secret German code-breaker
• Decode German messages during the latter part of World
War II
– 1940s: ENIAC: Mauchly & Eckert at U. of Penn.
Mark I, ASCC
• Howard Aiken, IBM at Harvard, 1944
– ASCC是由開關、繼電器、轉軸以及離合器所構成。
– 它使用了765,000個元件
– 組裝大小為16公尺長，公尺高，2呎深。
– 重達4500公斤。
– 其基本計算單元使用同步式機械，所以它有一跟
長15公尺的傳動軸，並由一顆4千瓦的馬達所驅動。
– 馬可一號可以儲存72組數據，每組數據有23位十
進位數字。每秒可執行3次加法或是減法。一個乘
法則須6秒，一個除法須秒，計算一個對數或
是一個三角函數需花費超過一分鐘。
– 打卡紙讀取 、執行每一道指令。
The Mark I computer
電腦的演進
• 1642巴斯卡加法器
• 1804法國織布工人查卡得發明能用不同打孔卡片自動
來編織圖案的織布機
• 1822英國劍橋大學的巴貝奇發明差分機，可做簡單的
四則運算
• 1833巴貝奇建造分析機失敗，但分析機構想已具有今
日電腦的基本結構，巴貝奇因而有「電腦之父」的尊
稱。
• 1886美國何樂里設計出以打孔卡片來儲存資料的計算
機器
• 1906美國費樂斯(Forest)發明了真空管
電腦之父—巴貝奇(babbage)
巴貝奇的差分機
范紐曼(Von Neumann)
電腦的演進
• 1939美國愛荷華州立大學製造出第一部電腦ABC
• 1946美國賓州大學和軍方合作製造出ENIAC電腦，
范紐曼提出內儲程式的觀念，被譽為「電子電腦之父
」
• 1947美國貝爾實驗室發明了電晶體
• 1949英國劍橋大學完成第一部大型內儲程式電腦
EDSAC
• 1951美國Sperry Rand公司生產UNIVAC-1，第一部
大量製造的商業電腦
電腦的演進 (cont.)
• 1954美國貝爾實驗室製出第一台以電晶體為主
要元件的電腦(TRADIC)
• 1958美國德州儀器公司發明了積體電路(IC
Integrated Circuit
• 1964美國國際商業機器公司(IBM)用IC為主元
件開發出System360電腦
• 1970開始有電腦使用超大型積体電腦(VLSI)
電腦的演進 (cont.)
• 1971美國Intel公司發表第一個微處理機4004
• 1977美國Apple公司推出APPLE II電腦：採封
閉性硬体系統架構。
• 1981美國IBM公司推出個人電腦，稱為IBM PC
：採開放性硬体系統架構，造成IBM相容型電
腦的大量生產。
• 1993, Pentium
EDSAC –1949 劍橋大學
真空管為元件的電腦
APPLE II
IBM computer
• 1981
Chapter 1
Data Storage
Chapter 1: Data Storage
Bits and Their Storage
Main Memory
Mass Storage
Representing Information as Bit
Patterns
The Binary System
Storing Integers
Chapter 1: Data Storage
(continued)
Storing Fractions
Data Compression
Communications Errors
Bits and their meaning
Bit = Binary Digit = a symbol whose
meaning depends on the application at
hand.
Some possible meanings for a single bit
Numeric value (1 or 0)
Boolean value (true or false)
Voltage (high or low)
Bit patterns
All data stored in a computer are
represented by patterns of bits:
Numbers
Text characters
Images
Sound
Anything else…
Boolean operations
Boolean operation = any operation that
manipulates one or more true/false values
Can be used to operate on bits
Specific operations
AND
OR
XOR
NOT
Figure The Boolean
operations AND, OR, and XOR
(exclusive or)
Gates
Gates = devices that produce the
outputs of Boolean operations when
given the operations’ input values
Often implemented as electronic circuits
Provide the building blocks from which
computers are constructed
Figure A pictorial representation of AND,
OR, XOR, and NOT gates as well as their input
and output values
Flip-flops
Flip-flop = a circuit built from gates
that can store one bit of data.
Has an input line which sets its stored
value to 1
Has an input line which sets its stored
value to 0
While both input lines are 0, the most
recently stored value is preserved
Figure A simple flip-flop
circuit
Figure Setting the
output of a flip-flop to 1
Figure Setting the
output of a flip-flop to 1
(cont’d)
Figure Setting the
output of a flip-flop to 1
(cont’d)
Figure Another way of
constructing a flip-flop
Other storage techniques
Dynamic memory – must be replenished
periodically – Example: capacitors
Volatile memory – holds its value until the
power is turned off – Example: flip-flops
Non-volatile memory – holds its value after
the power is off – Example: magnetic storage
Read-only memory (ROM) – never changes –
Examples: flash memory, compact disks
Hexadecimal notation
Hexadecimal notation = a shorthand
notation for streams of bits.
Stream = a long string of bits.
Long bit streams are difficult to make sense of.
The lengths of most bit streams used in a machine
are multiples of four.
Hexadecimal notation is more compact.
Less error-prone to manually read, copy, or write
Figure The hexadecimal
coding system
Main memory: cells
Cells = manageable units (typically 8 bits)
into which a computer’s main memory is
arranged.
Byte = a string of 8 bits.
High-order end = the left end of the
conceptual row in which the contents of a cell
are laid out.
Low-order end = the right end of the
conceptual row in which the contents of a cell
are laid out.
Least significant bit = the last bit at the low-
order end.
Figure The organization
of a byte-size memory cell
Main memory addresses
Address = a “name” to uniquely identify one
cell in the computer’s main memory
The names for cells in a computer are
consecutive numbers, usually starting at zero
Cells have an order: “previous cell” and “next
cell” have reasonable meanings
Random Access Memory = memory where
any cell can be accessed independently
Figure Memory cells
arranged by address
Measuring memory capacity: Not
quite like the metric system
“Kilo-” normally means 1,000;
Kilobyte = 210 = 1024
“Mega-” normally means 1,000,000;
Megabyte = 220 = 1,048,576
“Giga-” normally means
1,000,000,000;
Megabyte = 230 = 1,073,741,824
Mass Storage Systems
Non-volatile; data remains when computer is off
Usually much bigger than main memory
Usually rotating disks
Hard disk, floppy disk, CD-ROM
Much slower than main memory
Data access must wait for seek time (head positioning)
Data access must wait for rotational latency
Figure A disk storage
system
Figure CD storage
format
Figure A magnetic tape
storage mechanism
Files
File = the unit of data stored on a mass
storage system.
Logical record and Field = natural groups of
data within a file
Physical record = a block of data
conforming to the physical characteristics of
the storage device.
Buffer = main memory area sometimes set
aside for assembling logical records or fields
of a file
Figure Logical records
versus physical records on a
disk
Figure The message
“Hello.” in ASCII
Representing text
Each printable character (letter,
punctuation, etc.) is assigned a unique
bit pattern.
ASCII = 7-bit values for most symbols
used in written English text
Unicode = 16-bit values for most symbols
used in most world languages today
ISO proposed standard = 32-bit values
Representing numeric values
Binary notation – uses bits to represent
a number in base two
Limitations of computer representations
of numeric values
Overflow – happens when a number is too
big to be represented
Truncation – happens when a number is
between two representable numbers
Figure The sound wave
represented by the sequence 0, ,
, , , , , , 0
Figure The base ten
and binary systems
Figure Decoding the
binary representation 100101
Figure An algorithm for
finding the binary representation
of a positive integer
Figure Applying the algorithm
in Figure to obtain the binary
representation of thirteen
Figure The binary
addition facts
Figure Decoding the
binary representation
Representing Integers
Unsigned integers can be represented
in base two
Signed integers = numbers that can be
positive or negative
Two’s complement notation = the most
popular representation
Excess notation = another less popular
representation
Figure Two’s
complement notation systems
Figure Coding the value -6
in two’s complement notation
using four bits
Figure Addition problems
converted to two’s complement
notation
Figure An excess eight
conversion table
Figure An excess notation
system using bit patterns of
length three
Figure Floating-point
notation components
Figure Coding the
value 25⁄8
Figure The ASCII codes
for the letters A and F adjusted
for odd parity
Figure An error-
correcting code
Figure Decoding the
pattern 010100 using the code in
Figure
