1

计算思维与人工智能

Computational Thinking and Artificial Intelligence

 Lecture 1:
2

Computers, Computation, and

Computational Thinking
L.1: Computers, Computation, and Computational Thinking
3

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
L.1: Computers, Computation, and Computational Thinking
4

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
 What is a Computer?
5

Is a computer just like this?

 What is a Computer?
6

A computer is any hardware or software facility that can automatically execute programs.

航天器
 What is a Computer?
7

“Software is eating the world.” – Marc Andreessen （Netscape）

多选题 1分
8

Quiz – What is a Computer?

A A tool to help us calculate

B Invisible software
C A tool to overcome time/space
D A virtual-world creator
E Brain of machines
F Tool to transform nature
G Any hardware/software that executes programs
提交
L.1: Computers, Computation, and Computational Thinking
9

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
 What is Computational Thinking? – An Example
10

Problem – Mouse and Poison

Test your thinking...

There are 1000 bottles of water, one of which is poisoned.

A mouse dies within 24 hours after drinking even a drop of
poisoned water.
Question: What is the minimum number of mice needed to
identify the poisoned bottle within 24 hours?
单选题 1分
11

Quiz – How many mice are needed?

A 1
B 10
C 100
D 500
E 999
F 1000
提交
单选题 1分
12

Quiz – Use 10 fingers to represent a number. What is the

largest number that can be represented?

A 10
B 55
C 99
D 1023
E others

提交
 What is Computational Thinking? – An Example
13

Problem – Mouse and Poison

0 1 2 997 998 999

Posioned

0000000000 0000000001 0000000010 1111100101 1111100110 1111100111

1000 bottles of water are

distributed for 10 white mice
B9B8B7B6B5B4B3B2B1B0
to drink. The distribution Any
principle is as follows: If the B9=1 B7=1 B4=1
Bi bit of a bottle of water is 1, B5=1 B3=1 B1=1 insights?
then Mi mouse takes a sip. B8=1 B6=1 B2=1 B0=1
M9 M8 M7 M6 M5 M4 M3 M2 M1 M0

Which of the mice died? Dead is coded as 1 and alive as 0:

M9M8M7M6M5M4M3M2M1M0= 1111100101
 What is Computational Thinking? – An Example
14

【Thought】What is computational thinking?

01 strings can express different meanings

⚫ Any two diffent states could be expressed as 0 The key

and 1 points
---“dead”or“alive”；
000010
---“drink”or“Don’t drink”；
--- "poisonous" or "non-poisonous" Different meanings can be unified in
⚫ These different meanings are represented by a single 01 string, enabling seamless
0/1 encoded strings conversion of meanings.
---000010--- corresponds to the (decimal) bottle
Difficulty: 【 Combination application of multiple
number (000010) meanings of 0 and 1】
---000010---the i-th bit corresponds to the i-th The actions of the mouse "drinking" and "not
mouse, 1 means drink and 0 means not drink drinking"
The state of the mouse "dead" and "alive"
---000010---the i-th bit corresponds to the i-th The "poisonous" and "non-poisonous" nature of the
mouse, 1 means dead and 0 means alive water
 What is Computational Thinking? – An Example
15

【Computational Thinking】

Procedural and Symbol Transformation Thinking

⚫ Procedural Thinking
--- Decimal number of water bottles (all) → Binary coding → Assign to mice for drinking (the i-th bit
corresponds to the i-th mouse, 1 = drink, 0 = not drink) → Mouse survival status → Form binary code
again (the i-th bit corresponds to the i-th mouse, 1 = dead, 0 = alive) → Decimal number (the
poisoned bottle number).
⚫ Symbol Transformation and Logical Reasoning
--- Infer which bottle is poisonous using computational
methods based on mouse survival status;
--- Symbol transformation: Convert decimal to binary,
then convert binary back to decimal.
 What is Computational Thinking?
16

【Computational Thinking】

⚫【Computational Thinking】is the use of fundamental concepts from computer

science to solve problems, design systems, and understand human behavior.
⚫ Computational thinking is a form of scientific and engineering thinking, and a
thinking ability that can be transformed into innovation in the future.
⚫ Computational thinking focuses on computational methods and computational
systems (including design, construction, and application); it is a "big thinking"
rather than a trivial technique.
⚫ Computational thinking is not limited to programming thinking, algorithmic
thinking, or problem-solving thinking (which can be considered "computation
+ thinking"). Instead, it covers a relatively complete system including
"computation + thinking", "Internet + thinking", "big data thinking", and
"artificial intelligence + thinking".
What is Computational Thinking? – Another Example
17

【Application】Communication Data Checking Problem and its Solution

Error Detection and Correction in Data Transmission

·“Even Parity Rule”

1 1 0 1 1 0 1 1 --Ensure the number of
1s in relevant bits is
Judge whether an always even before and
error occurred during
the transmission of the after transmission
传输
following data？
01011010 0
1 0 0 1 1 0 1 1 01010100 1
What is Computational Thinking? – Another Example
18

【Application】Communication Data Checking Problem and its Solution

7 6 5 4 3 2 1

Binary 111 110 101 100 011 010 001

Parity bits
Data bits D7 D6 D5 D4 D3 D2 D1 P4 P2 P1
Data 1 1 0 1 1 0 1 1 1 1 P4 = D7+D6+D5+D4
P2 = D7+D6+D3+D2
P1 = D7+D5+D3+D1
1 1 0 1 1 0 1 1 1 1
Drink?
传输

1 1 0 1 0 0 1 1 1 1 Alive?

P4’P2’P1’ P4’ = D7+D6+D5+D4+P4

0 1 1 P2’ = D7+D6+D3+D2+P2
P1’ = D7+D5+D3+D1+P1

【Hamming Code】
单选题 1分
19

Quiz: Transmitting the bit string "1001 1010", if

even parity is used, the value of the parity bit P
should be ___.

A 0
B 1

提交
单选题 1分
20

Quiz: Assuming the data is 1010011, using even parity, what

should the three parity bits P4 P2 P1 be?

7 6 5 4 3 2 1
Binary 111 110 101 100 011 010 001
Parity bits P4 = D7+D6+D5+D4
Data bits D7 D6 D5 D4 D3 D2 D1 P4 P2 P1 P2 = D7+D6+D3+D2
Data 1 0 1 0 0 1 1 ？ ？ ？ P1 = D7+D5+D3+D1

A 000 E 100
B 001 F 101
C 010 G 110
D 011 H 111 提交
L.1: Computers, Computation, and Computational Thinking
21

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
 What Will Be Covered in this course?
22

Core Context and Nature of Computational Thinking

1、How are social/natural problems computed?

2、The nature of computation and computers?
social/natu
ral Computing Solutions
problems

Computer Science
Mathematics
Human- Machine- Machine-
Computing Automatic Difficult
Computing Computing

Three Dimensions of Computing

 What Will Be Covered in this course?
23

Computing in Mathematics vs. Computing in Computer Science

Example: Solving the quadratic equation ax²+ bx + c = 0

Human- Machine- Machine-Computing
Computing Computing
1. Generate values of x in the real number space
1. Generate all integer with a step size δ.
values of x from -n to n. 2. Substitute each x into the equation for
2. Substitute each x into the calculation.
equation for calculation. 3. If the equation holds (within error tolerance), x
3. If the equation holds, x is is an approximate root; otherwise, it is not.
Use the formula to
calculate the roots a root; otherwise, it is not.
directly [Note: δ can be 0.1, 0.01, ..., 0.000001, etc. A smaller step
size improves accuracy but increases computation load.]

Is x necessarily an integer root?

Optimization:
Can the step size be adjusted dynamically based on the
calculated values, instead of computing every value?
单选题 1分
24

Quiz: What is the biggest difference between computational

thinking and mathematical thinking?

A Computational thinking is the "enumeration - machine computation - verification" thinking.

B Computational thinking is the thinking of solving problems using "mathematical formulas".

Computational thinking is the thinking of "machine automatic computation" using
C
"mathematical formulas".
Computational thinking is the thinking of writing "programs" to solve problems using
D
"mathematical formulas".
E None of the above is correct.

提交
L.1: Computers, Computation, and Computational Thinking
25

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
 Computing and Automatic Computing
26

Key Problems in Automatic Computing

To realize automatic computing, three core

problems must be solved: Representation
- Storage - Execution Principle:
1. Representation of "Data"
2. Representation of "Computing • The simpler the rules, the easier it is
Rules": Programs to build the machine.
• A single simple rule can be applied
3. Automatic Storage of Data and repeatedly to solve complex problems.
Computing Rules
4. Automatic Execution of Computing
Rules

Example: 5x12+6x23+…+8xn2=200
 Computing and Automatic Computing
27

Example: Computing Polynomials with Finite Difference Method

Use simple rules (addition/subtraction) to solve complex computing problems

(exponentiation, polynomial evaluation).

Case 1: Calculating n² n n2
First-order diff. Second-order diff.
n = n2-(n-1)2 n = n - n-1
0 0
1 1 1
(n+1)2 = n2 + n + n 2 4 3 2
3 9 5 2
4 16 7 2
5 25 9 2
 Computing and Automatic Computing
28

Example: Computing Polynomials with Finite Difference Method

Use simple rules (addition/subtraction) to solve complex computing problems

(exponentiation, polynomial evaluation).

Case 2: n F(n)
First-order diff. Second-order diff.
n = n2-(n-1)2 n = n - n-1

Calculating F(x) = x² + 2x + 3 0 3
1 6 3
2 11 5 2

F(n+1) = F(n) + n + n 3 18 7 2
4 27 9 2
5 38 11 2
 Computing and Automatic Computing
29

Program Expression of Computing Rules

/* C-like Program Key Concepts:

Main()
{ •Array Variables: Store multiple values in sequence (e.g., F[0]
stores F(0), F[1] stores F(1)).
int k, n, F[ ], alpha[ ], beta[ ];
input k; •Variables: Values that can change during program execution.
F[0]=3;
F[1]=6; Questions:
F[2]=11; •Q: What if the stored data increases as k increases?
alpha[1] = 3;
for n=2 to k-1 •T: Different initial values can compute different univariate
quadratic polynomials.
{
alpha[n] = F[n] - F[n-1];
beta[n] = alpha[n] - alpha[n-1];
F[n+1] = F[n] + alpha[n] + beta[n];
}
output F[k];
}
 Computing and Automatic Computing
30

Optimized Program: Reducing Variable Usage

/* C-like Program
Main() Optimization Insight:
{ int k, n, F_nminus1, F_n, F_nplus1,
•Use scalar variables instead of arrays to store only necessary
int alpha_nminus1, alpha_n, beta_n; intermediate values.
input k;
F_nminus1 = 1; F_n = 4; alpha_nminus1 = 1; •The amount of stored data no longer depends on k.
for n=2 to k-1 •Realize "iterative computation" by updating variables cyclically.
{
alpha_n = F_n – F_nminus1;
beta_n = alpha_n – alpha_nminus1;
F_nplus1 = F_n + alpha_n + beta_n; F[0] 保存F(0)的值
F_nminus1 = F_n; F[1] 保存F(1)的值
F_n = F_nplus1; F[2] 保存F(2)的值
alpha_nminus1 = alpha_n; F[3] …… F_n
} F[4]
output F_nplus1; F[5]
} …
 Computing and Automatic Computing
31

迭代式方法的执行过程

/* C-like Program
Main()
{ int k, n, F_nminus1, F_n, F_nplus1, alpha_ nminus1
int alpha_nminus1, alpha_n, beta_n; n F_nplus1 F_n F_nminus1 alpha_n beta_n
input k;

F_nminus1 = 1; F_n = 4; alpha_nminus1 = 1; 2 9 1 4 3 1 2
for n=2 to k-1
 
{ 3 16  9  4 5  3 2
alpha_n = F_n – F_nminus1;
beta_n = alpha_n – alpha_nminus1;
4 25 16 9 7 5 2
F_nplus1 = F_n + alpha_n + beta_n;
5 36 25 16 9 7 2
F_nminus1 = F_n;
F_n = F_nplus1; 36 25 9
alpha_nminus1 = alpha_n;
}
output F_nplus1;
}
多选题 1分
32

Quiz: Thinking from Polynomial Computation with Finite

Difference Method

A To build a computing machine, the single rule should be as simple as possible.

As long as the single rule is simple, the machine can realize complex computing through
B
repeated operations.

C The machine should store as little data as possible, so iteration is a common method.

To build an automatic computing machine, it is only necessary to solve the

D representation and automatic storage of data, and the representation, automatic storage,
and automatic execution of rules.
In computers, both data and rules are represented in 0-1 form; their automatic storage is
E
realized by [memory], and their automatic execution is completed by [CPU].

提交
L.1: Computers, Computation, and Computational Thinking
33

1. What is a computer?
2. What is computational thinking? – An example
3. What will we learn?
4. Computation and automatic computation
5. Computation and society
 Computing and Society
34

Computing devices are becoming embeddable and portable.

Smartphones

World's smallest desktop computer

•Human-implantable chips
 Computing and Society
35

Large-scale, complex computing with supercomputers

IBM-BlueGene: Milestone of an
Intelligent Machine

A massively parallel supercomputer using tens of thousands of

embedded PowerPC processors supporting a large memory space
With standard compilers and message passing environment
 Computing and Society
36

Networking of Computing

The "Internet of Everything" connects the world.

Internet of Services Internet of 3D Worlds
For people

Internet of Things Internet of Networks

and
enterprises
 Computing and Society
37

Intelligence of Computing:understand natural language, adapt to

environments, and complete complex tasks independently.

IBM：Smart Planet
◆Instrumented
◆Interconnect
◆Intelligent
 Computing and Society
38

National/Societal Attention to Computational Thinking

• "Teaching complex thinking is a challenge. Computational thinking is an

advanced complex thinking skill and an important support for cultivating
complex thinking capabilities. Emphasizing computational thinking
education can help learners interpret real-world systems and solve global
complex problems." — 2015 Horizon Report.
• Computational thinking is one of the 11 core thinking capabilities for
talents in the new era (including manufacturing, discovery, interpersonal
skills, creativity, systematic thinking, critical thinking, analytical thinking,
computational thinking, experimental thinking, and humanistic thinking) —
MIT.

怎样创新？
 Computing and Society
39

National/Societal Attention to Computational Thinking

• Nobel Prize Recognition:

• 1998: J.A. Pople won the Nobel Prize in Chemistry for developing
quantum chemistry calculation programs (promoting the application of
computing in chemistry).
• 2013: Martin Karplus, Michael Levitt, and Arieh Warshel won the Nobel
Prize in Chemistry for developing multi-scale complex chemical system
models and calculation tools.
• National Policies: China has launched a series of IT-driven initiatives
(e.g., "Internet + Action Plan", "New Generation Artificial Intelligence
Development Plan"), which require talents with "Internet + thinking", "big
data thinking", and "AI thinking". "How far you can think determines how
far you can go" — thinking is the source of innovation.
怎样创新？