Transcript Introduction to Computer Science

Chapter 1
Basic Computer Concept
國立雲林科技大學 資訊工程研究所
張傳育(Chuan-Yu Chang ) 博士
Office: ES 709
TEL: 05-5342601 ext. 4337
E-mail: [email protected]
1
Textbook


G. Michael Schneider & Judith L. Gersting,
“Invitation to Computer Science C++ Version”,
3rd Edition, 2004, ISBN:0-534-39097-8
台灣代理商：滄海書局
Tel：04-27088787
Fax ：04-27087799
2
A few Common Misconceptions about
Computer Science

Misconception 1:

Computer science is the study of computers.


Misconception 2:

Computer science is the study of how to write computer
programs.


Many researchers investigate problems not with actual computers but
rather with formal models of computation, which are easier to study
and analyze mathematically.
Programming is so primarily as a tool by which researchers can study
new ideas and build and test new solutions.
Misconception 3:

Computer science is the study of the uses and applications of
computers and software.

The computer scientist is responsible for specifying, designing,
building, and testing software packages as well as the computer
systems on which they run.
3
The Definition of Computer Science


The central concept in computer science is the
algorithm. [Gibbs and Tucker, 1986]
Computer science is the study of algorithms,
including:




1. Their formal and mathematical properties
2. Their hardware realizations
3. Their linguistic realizations
4. Their applications
4
The Definition of Computer Science (cont.)

Based on the definition, the tasks of the computer
scientist are




Study the behavior of algorithms to determine whether they
are correct and efficient.
Designing and building computer systems that are able to
execute algorithms
Designing programming languages and translating
algorithms into these languages so that they can be
executed by the hardware.
Identifying important problems and designing correct and
efficient software packages to solve these problems.
5
The Definition the word Algorithm

Algorithm:


A procedure for solving a mathematical problem in a finite
number of steps that frequently involves repetition of an
operation; broadly: a step-by-step method for
accomplishing some task.
An algorithm is an ordered sequence of instructions that is
guaranteed to solve a specific problem. It looks like:
Step 1
Step 2
Step 3
Step N
Do something
Do something
Do something
:
:
Stop, you are finished
6
Three categories of operations

The operations used to construct algorithms
can be categorized as

Sequential operations :


Conditional operations :


carries out a single well-defined task, usually expressed
as simple declarative sentences.
“question-asking” instructions of an algorithm
Iterative operations :

“looping” instructions of an algorithm.
7
Example:
Algorithm for Programming the VCR

Step1 :


Step2 :


Place a blank tape into the VCR tape slot.
Step3 :


If the clock calendar are not correctly set, then go to page 9
of the instruction manual and follow the instructions there
before proceeding.
Repeat step 4 through 7 for each program that you wish to
record, up to maximum of 10 shows.
Step4 :

Enter the channel number that you wish to record, and
press the button labeled CHAN.
8
Algorithm for Programming the VCR
(cont.)

Step5 :


Step6 :


Enter the time that you wish recording to stop, and then
press the button labeled TIME-FINISH.
Step7 :


Enter the time that you wish recording to start, and then
press the button labeled TIME-START.
This completes the programming of one show. If you do
not wish to record anything else press the button labeled
END-PROG.
Step8 :

Press the button labeled TIMER. Your VCR is now ready to
record.
9
Example:
Algorithm for Adding Two m-digit Numbers


Given m >=1 and two positive numbers
each containing m digits: am-1am-2 …… a0
and bm-1bm-2……b0
Wanted: cm-1cm-2…c0 where cm-1cm-2…c0 =
(am-1am-2 …… a0 )+ (bm-1bm-2……b0)
10
Example:
Algorithm for Adding Two m-digit Numbers

Step 1:


Step 2:


Set the value of carry to 0
Set the value of i equal to the value 0
Step 3:

Repeat the instructions in steps 4 through 6 until the
value of i is greater than m-1

Step 4:


Step 5:


Add the two digits ai and bi to the current value of carry to get ci
if ci>= 10 , reset ci to (ci -10) and reset the value of carry to 1; otherwise,
set the new value of carry to 0
Step 6:

Add 1 to i , effectively moving one column to the left
11
Algorithm for Adding Two m-digit Numbers
(cont.)

Step 7:


Step 8:


set cm to the value of carry
print out the final answer, cmcm-1cm-2 … … … c0
Step 9:

Stop
12
Analyzing the algorithm



Steps 1,2,4,6,7,8,9: sequential operations
Step 5: conditional operations
Step 3: iterative operations
13
Why formalizing the steps?



Why are formal algorithms so important in computer science ?
 If we can specify an algorithm to solve a problem, then we can
automate its solution.
 The machine, robot, person , or thing carrying out the steps of the
algorithm is called a computing agent.
Computer science can be viewed as “the science of algorithmic problem
solving”.
Computability: is it true that every problem can be solved algorithmically?
 Unsolvable problem
 To specify an algorithm, but it would take a computing agent so long to
execute that the solution is useless.




Ex. Chessboard: brute force algorithm
假設在每一狀態有40個合法的移動，每盤棋約30步，則決定下第一步可有
40x40x40x…x40=4030=1048
假設每秒可評估1012步，則須花3x1025年才能下哪一步。
We do not yet know how to solve algorithmically.

Ex. intelligence
14
The Formal definition of an Algorithm

The formal definition of an algorithm

A well-ordered collection of unambiguous and
effectively computable operations that, when,
executed, produces a result and halts in a finite
amount of time.
15
Examples of algorithms
shampooing instructions




Step
Step
Step
Step
1
2
3
4
Wet hair
Lather
Rinse
Repeat
16
Examples of algorithms
making a cherry pie

Step 1:








1.1
Take one and one-third cups flour
1.2
Sift the flour
1.3
Mix the sifted flour with one-half cup butter and onefourth cup water.
1.4
Roll into two 9-inch pie crusts.
Step 2:

Make the crust
2.1
bowl
2.2
Step 3:
Step 4:
Make the cherry filling
Open a 16-oz can of cherry pie filling and pour into
Add a dash of cinnamom and nutmeg, and stir.
Pour the filling into the crust
Bake at 350F for 45 minutes.
17
Unambiguous




An unambiguous operation is one that can be understood
and carried out directly by the computing agent without
needing to be further simplified or explained.
An operation is unambiguous , we call it a primitive
operation
It is not enough for an operation to be understandable. It
must also be doable by the computing agent.
Doable means there exists a computational process that
allows the computing agent to complete that operation
successfully.

Effectively computable.
18
Examples of algorithms
prime number




Step 1: Generate a list L of all the prime
numbers: L1, L2, L3,…
Step 2: Sort the list L into ascending order.
Step 3: Print out the 100th element in the list
L100.
Not doable
Step 4: Stop
19

Some examples of operations that may not
be effectively computable:




Write out the exact decimal value p.
Set average to sum/number
Set the value of result to (N)1/2
Add 1 to the current value of x
20
…halts in a finite amount of time.


The result must be produced after the execution
of a finite number of operations.
We must guarantee that the algorithm eventually
reaches a statement that says “Stop, you are
done”
21
A correct solution to the Shampooing problem (1)







Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
Step 7:
Wet your hair.
Set the value of WashCount to 0
Repeat step 4 through 6 until the value of
WashCount equals 2.
Lather your hair
Rinse your hair
Add 1 to the value of WashCount
Stop, you have finished shampooing your
hair.
22
A correct solution to the Shampooing problem (2)






Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
Wet your hair
Lather your hair
Rinse your hair
Lather your hair
Rinse your hair
Stop, you have finished shampooing
your hair.
23