Transcript Introduction to Computer Science

Introduction to Computer
Science
Fall 2004, 劉震昌
Ref: Computer Science: an overview
J. Glenn Brookshear
Outline

Concept of computers




Computer software: algorithm
Computer hardware: algorithmic machine
Turing Machine
5 major components of computers
Computers ?
Software
Package
(Executable)
Software
Hardware
Source
Program
compile
#include <stdio.h>
main(){
…
}
Computers are machines to
execute Algorithm
Hierarchy of computer
Program language
Ex. C, Java,…
Readable by human
Machine language
(instruction set)
Ex. Executable file
Readable by machine
Computer hardware
Computer software:
Algorithm 演算法




Computers are machines to execute
Algorithm
Fundamental concept of CS
Definition of algorithm (1): a set of steps
that defines how a task is performed
Definition of algorithm (2): an ordered set of
unambiguous, executable steps that defines
a terminating activity
Algorithm: example

Sorting(排序): sort the cards from top to
down in alphabetical order
Albert
Baker
Charlie
Algorithm: sort (cont.)
Albert
Charlie
Baker
Albert
Baker
Charlie
After
Step 1
input
Charlie
Albert
Baker
Charlie
Baker
Albert
After
Step 2
After
Step 3
Write an algorithm: sort
Input: 3 cards in arbitrary order
1. Compare the names on the first and second
cards. Exchange them if they are out of order.
2. Compare the names on the second and third
cards. Exchange them if they are out of order.
3. Compare the names on the first and second
cards. Exchange them if they are out of order.
Output: 3 cards in alphabetical order
Properties of algorithms



Goal: find a single set of directions that
describe how any problem could be solved
Algorithm = Programs within computers
The intelligence required to perform the
task is encoded in the algorithm
Mini break


NCNU webmail system
http://webmail.ncnu.edu.tw/


The web-based email system
計算中心 FAQ
http://www.cc.ncnu.edu.tw/net/ccfaq/FAQ.htm

Send an email to me with subject :
Lab2 學號
How to devise an algorithm?





1945 Polya, “How to solve it”
Phase 1: Understand the problem
Phase 2: Devise a plan for solving the
problem
Phase 3: Carry out the plan
Phase 4: Evaluate the solution for accuracy
and for its potential as a tools for solving
other problems
HW#1.1
Write an algorithm to sort 4 cards
2.
Write an algorithm to sort 5 cards
Give an example for each of your algorithm.
1.
Write your homework in a well-formed
document (.txt, .doc), and send it to me
via email.
Computers hardware?



Concept of algorithm appeared first
Computers are designed to implement algorithms
Computers (計算機,電腦) are not smart
themselves…
+
Development of Algorithmic
Machines

Algorithmic machines:
machines that perform
algorithm tasks
Abacus(算盤): ancient
Greek and Roman
Blaise Pascal(16231662), France
Development of Algorithmic
Machines (cont.)
Charles Babbage(17921871), England
Herman Hollerith
打孔機
解多項式
1st generation computer

1940
真空管
ENIAC
2nd generation computer

1959
電晶體
3rd generation computer

1965
IC (積體電路)
4th generation computer

1971
VLSI (超大積體電路)
Turing machines



The abstract model of general-purpose
algorithmic machines
1936 by Alan M. Turing
You will learn more in the class of automata
and formal language 自動機與形式語言
Turing machines (cont.)
Components of a Turing machine
Control
unit
state of the machines
read/write head
…
…
tape
symbols
A specific Turing machine

A Turing machine for incrementing a vlaue
Example:
1
2
state=START
3
state=ADD
4
state=CARRY
5
state=NO CARRY
state=NO CARRY
HW#1.2

Apply the above Turing machine to the
following tape: 1
1
1
0
state=START

Design a Turing machine that decrements
the value on the tape if it is greater than 0
or leaves the value unaltered if it is 0.
Turing machines (cont.)

Prototype of today’s computer





Control unit -> CPU
States -> registers
Tape cells -> memory
Symbols -> 0 and 1
The power of Turing machine

If a problem cannot be solved by a Turing
machine, then it cannot be solved by any
algorithmic system
John von Neumann
machine


In early computing machines, the programs
were built as part of the machine
Store-program concept



Program, just like data, can be coded and
stored in main memory
Control unit extracts the program from memory,
decodes the instructions, and executes them
Some data(bit patterns) were interpreted as
instructions -> machine language
Outline

Concept of computers




Computer software: algorithm
Computer hardware: algorithmic machine
Turing Machine
5 major components of computers
Computer hardware
Peripherals 週邊
Central
processing
unit
memory
Input
devices
Output
devices
Auxiliary
memory
Bus: for data transmission
CPU (central processing unit)

Carry out the instructions in the program
ALU: arithmetic/logic unit
ALU
Control
unit
registers
CPU
CPU – control unit
Instruction fetch
Instruction decoding
Instruction execution
Memory read/write
time
Instruction cycle
Memory

Main memory




RAM(random access memory)
Fast
Volatile 揮發
Auxiliary memory




Secondary storage
Slower
Permanent
Ex. Hard Disk, CD-ROM
I/O devices

Input devices


Keyboard, mouse, …
Output devices

Display, printer, …
Overview of computer systems
software
High-level
language
applications
User
Interface
Operation
system
desktop
dos
MS Windows
Hardware
machines
shell
Unix
Linux
compiler
assembly
language
assembler
machine
language
Purpose of this class
software
High-level
language
applications
User
Interface
Operation
system
desktop
dos
MS Windows
Hardware
machines
shell
Unix
Linux
compiler
assembly
language
assembler
machine
language