Transcript Fundamental Computing - Gadjah Mada University

TEL 104 / MKK
Fundamental Programming:
Lecture 2
Computer Systems Overview
&
Introduction to Algorithm
1
eureka!
Algorithm:
A set of instructions describing
how to do a task (or process)
Program
2
How the program works inside the
computer
3
Transistor
Collector
Base
Emitter
“semi-conductor”
Binary digit or “bit”:
0  off
1  on
4
Transistor (cont)
Collector
Base
Emitter
off : 0
5
Transistor
Collector
Base
Emitter
on : 1
6
Transistor
Collector
Base
Emitter
Modern-day “chips” (about 3 x 3 mm in size) can
contain millions of transistors
7
Gates
• Gate: a group of transistors
• Gates are switches that distinguish between
two electrical voltages:
– Current is low => 0
– Current is high => 1
• Types:
AND Gate
OR Gate
NOT Gate
8
Example: AND Gate
A
A AND B
B
A
A
B
0
0
1
1
0
1
0
1
A AND B
B
A AND B
9
Gates and Boolean Algebra
AND Gate
A
B
0
0
1
1
0
1
0
1
OR Gate
A AND B A OR B
10
Gates and Boolean Algebra (cont)
NOT Gate
A
NOT A
0
1
11
Gates and Boolean Algebra (cont)
A sequence of bits at a time:
A =
B =
1 1 0 0 1 1 0 1
0 1 1 0 0 1 1 0
A AND B =
• Most PCs do 32 bits at a time (“32-bit machines”),
others as many as 128 bits at a time
12
0 or 1
• Gates are the basic building blocks of computers
13
Hardware Components of a
Typical Computer
Peripheral
Devices
Central
Processing
Unit (CPU)
Memory
• "Buses" allow components to pass data to each other
14
Hardware Components of a
Typical Computer -- CPU
Peripheral
Devices
Central
Processing
Unit (CPU)
Memory
Central Processing Unit (CPU)
• performs the basic operations
• consists of two parts:
– Arithmetic / Logic Unit (ALU) - data manipulation
– Control Unit - coordinate machine’s activities
15
Hardware Components of a
Typical Computer -- Memory
Peripheral
Devices
Central
Processing
Unit (CPU)
Memory
Main Memory
• holds programs and data
• stores bits in fixed-sized chunks: “word” (8, 16, 32, or
64 bits)
• each word is stored in a cell, which has a unique address
• the cells can be accessed in any order =>
random-access memory or “RAM”
16
Hardware Components of a Typical
Computer -- Peripherals
Peripheral
Devices
Central
Processing
Unit (CPU)
Memory
Peripheral devices –
• communicate with the outside world
• store data long term
17
Hardware Components of a Typical
Computer – Peripheral Devices that
Communicate with the Outside World
Peripheral
Devices
Central
Processing
Unit (CPU)
Memory
• Input/Output (I/O)
– Input: keyboard, mouse, microphone, scanner,
sensors (camera, infra-red), punch-cards
– Output: video, printer, audio speakers, etc
• Communication
– modem, ethernet card
18
Modes of communication
• Parallel communication:
– all the bits are transferred at the same time
1
– each bit on a separate line
0
• Serial communication:
– one bit at a time
1
1
0
0
0
1
1
0
19
Introduction to Algorithm
20
7 Steps in Program Development
1.
Define the problem
•
•
•
2.
The inputs
The outputs
The processing steps to produce the required outputs
Outline the solution
•
•
•
•
•
•
3.
The major processing steps involved
The subtask (if any)
The user interface (if any)
The major control stuctures (e.g. Repetition loops)
The major variables and record structures
The mainline logic
Develop the outline into an algorithm
21
7 Steps in Program Development
(cont)
4. Test the algorithm for correctness
5. Code the algorithm into a specific
programming language
6. Run the program on the computer
7. Document and maintain the program
22
How do we solve problems?
•
•
•
•
•
We "just do"
Guesswork-and-luck
Trial-and-error
Experience (possibly someone else's)
"Scientifically"
23
The Problem-solving Process
"Doctor, my head hurts"
Patient has elevated
pressure in anterior
parietal lobe
Analysis
Problem
specification
Design
Algorithm
Implementation
Program
Compilation
Executable
(solution)
1. Sterilize cranial saw
2. Anaesthetize patient
3. Remove top of skull
4. Get the big spoon...
5. etc., etc.
sterilize(saw,alcohol);
raise_hammer();
lower hammer(fast);
start(saw);
/* etc. etc. */
0100111010110010101010101
0010101010101001100101010
1010100101101001110101010
1010010010111010011110101
010111110101010001101…24
The Problem-solving Process
"Doctor, my head hurts"
Patient has elevated
pressure in anterior
parietal lobe.
Analysis
Problem
specification
Design
Algorithm
Implementation
Program
Compilation
Executable
(solution)
1. Sterilize cranial saw
2. Anaesthetize patient
3. Remove top of skull
4. Get the big spoon...
5. etc., etc.
sterilize(saw,alcohol);
raise_hammer();
lower hammer(fast);
start(saw);
/* etc. etc. */
01001110101100101010101010010
10101010100110010101010101001
011010011101010101010010010111
010011110101010111110101010001
10100001101...
25
The Problem-solving Process
Analysis
Problem
specification
Design
Algorithm
Implementation
Program
Compilation
Executable
(solution)
26
Algorithm
• A sequence of instructions specifying the
steps required to accomplish some task
• Named after:
Muhammad ibn Musa al-Khwarizmi
of Khowarezm (now Khiva in Uzbekistan)
Circa 780-850 C.E. (Common Era)
27
Algorithm –History
Muhammad ibn Musa Al-Khwarizmi
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Al-Khwarizmi.html
• Book on arithmetic:
– Hindu numeration, decimal numbers, use of zero,
method for finding square root
– Latin translation (c.1120 CE): “Algoritmi de
numero Indorum”
• Book on algebra
– Hisab al-jabr w’al-muqabala
28
Algorithm – Working Definition
• A sequence of instructions describing how
to do a task
[As opposed to actually executing
the instructions]
29
Algorithm -- Examples
•
•
•
•
•
•
•
•
A cooking recipe
Assembly instructions for a model
The rules of how to play a game
VCR instructions
Directions for driving from A to B
A knitting pattern
A car repair manual
Recipe for Almond and honey slice
30
Almond and Honey Slice
1/2 quantity Shortcrust
Pastry
185 g unsalted butter
100 g castor sugar
5 tablespoons honey
50 ml cream
50 ml brandy or any other
liqueur or spirit
300 g flaked almonds
From: Stephanie Alexander, The
Cook’s Companion, Viking/Penguin,
Ringwood, Victoria, 1996, p. 349.
Preheat oven for 200° C
Line a 30 cm  20 cm baking
tray with baking paper, and
then with pastry
Bake blind for 20 minutes, then
remove weights and foil
Turn oven up to 220° C.
Bring remaining ingredients to a
boil, stirring.
Spread evenly over pastry.
Bake until topping is bubbling
and has caramelised evenly,
about 15 minutes.
Cool before cutting into fingers
or squares.
31
Almond and Honey Slice
1/2 quantity Shortcrust
Pastry
185 g unsalted butter
100 gInstructions
castor sugar are given
in the order in which
5 tablespoons honey
they are performed
50 ml(“executed”)
cream
50 ml brandy or any other
liqueur or spirit
300 g flaked almonds
From: Stephanie Alexander, The
Cook’s Companion, Viking/Penguin,
Ringwood, Victoria, 1996, p. 349.
Preheat oven for 200° C
Line a 30 cm  20 cm baking
tray with baking paper, and
then with pastry
Bake blind for 20 minutes, then
remove weights and foil
Turn oven up to 220° C.
Bring remaining ingredients to a
boil, stirring.
Spread evenly over pastry.
Bake until topping is bubbling
and has caramelised evenly,
about 15 minutes.
Cool before cutting into fingers
or squares.
32
Correct Algorithm?
Cut chicken into pieces and
brown the pieces on all
sides in a casserole dish in
hot olive oil.
Remove the chicken and to
the juices in the casserole
add garlic, onions and
green peppers, and sauté
until onion is golden.
Add bay leaf, whole
tomatoes, and chicken
broth.
When the broth boils add
salt, saffron and rice.
Arrange chicken on rice,
cover casserole and bake
in a moderate oven
(350°F) for 20 minutes or
until the rice is tender.
Add beans and artichokes
during last 10 minutes of
cooking.
From: “Arroz Con Pollo” in The
Margaret Fulton Cookbook, Hamlyn,
Sydney, 1968.
33
Correct Algorithm?
Cut chicken into pieces and
brown the pieces on all
sides in a casserole dish in
hot olive oil.
Remove the chicken and to
the juices in the casserole
add garlic, onions and
green peppers, and sauté
until onion is golden.
Add bay leaf, whole
tomatoes, and chicken
broth.
When the broth boils add
salt, saffron and rice.
Arrange chicken on rice,
cover casserole and bake
in a moderate oven
(350°F) for 20 minutes or
until the rice is tender.
Add beans and artichokes
during last 10 minutes of
cooking.
From: “Arroz Con Pollo” in The
Margaret Fulton Cookbook, Hamlyn,
Sydney, 1968.
34
Correct Algorithm?
Cut chicken into pieces and
brown the pieces on all
sides in a casserole dish in
hot olive oil.
Remove the chicken and to
the juices in the casserole
add garlic, onions and
green peppers, and sauté
until onion is golden.
Add bay leaf, whole
tomatoes, and chicken
broth.
When the broth boils add
salt, saffron and rice.
Arrange chicken on rice,
cover casserole and bake
in a moderate oven
(350°F) for 10 minutes.
Add beans and artichokes.
Cover, and bake for another
10 minutes or until rice is
tender.
35
From Algorithms to Programs
Problem
Algorithm: A sequence
of instructions describing
how to do a task (or
process)
C, Java Program
36
Components of an Algorithm
•
•
•
•
•
•
•
Variables and values
Instructions
Sequences
Procedures
Selections
Repetitions
Documentation
37
Values
• Represent quantities, amounts or
measurements
• May be numerical or alphabetical (or other
things)
• Often have a unit related to their purpose
• Example:
– Recipe ingredients
38
Almond and Honey Slice
1/2 quantity Shortcrust
Pastry
185 g unsalted butter
100 g castor sugar
5 tablespoons honey
50 ml cream
50 ml brandy or any other
liqueur or spirit
300 g flaked almonds
From: Stephanie Alexander, The
Cook’s Companion, Viking/Penguin,
Ringwood, Victoria, 1996, p. 349.
Preheat oven for 200° C
Line a 30 cm  20 cm baking
tray with baking paper, and
then with pastry
Bake blind for 20 minutes, then
remove weights and foil
Turn oven up to 220° C.
Bring remaining ingredients to a
boil, stirring.
Spread evenly over pastry.
Bake until topping is bubbling
and has caramelised evenly,
about 15 minutes.
Cool before cutting into fingers
or squares.
39
Almond and Honey Slice
1/2 quantity Shotcrust Pastry
185 g unsalted butter
100 g castor sugar
5 tablespoons honey
50 ml cream
50 ml brandy or any other
liqueur or spirit
300 g flaked almonds
From: Stephanie Alexander, The
Cook’s Companion, Viking/Penguin,
Ringwood, Victoria, 1996, p. 349.
Preheat oven for 200° C
Line a 30 cm  20 cm baking
tray with baking paper, and
then with pastry
Bake blind for 20 minutes, then
remove weights and foil
Turn oven up to 220° C.
Bring remaining ingredients to a
boil, stirring.
Spread evenly over pastry.
Bake until topping is bubbling
and has caramelised evenly,
about 15 minutes.
Cool before cutting into fingers
or squares.
40
Variables
• Are containers for values – places to store
values
• Example:
Variable
Values
This jar
can contain
10 cookies
50 grams of sugar
3 slices of cake
etc.
41
Restrictions on Variables
• Variables may be restricted to contain a
specific type of value
42
Components of an Algorithm
Values and Variables
• Instruction (a.k.a. primitive)
• Sequence (of instructions)
• Procedure (involving instructions)
• Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)
43
Instructions (Primitives)
•
•
•
•
Some action that is simple...
...and unambiguous...
...that the system knows about...
...and should be able to actually do
44
Instructions – Examples
•
•
•
•
•
•
Take off your shoes
Directions to perform
Count to 10
specific actions on values
Cut along dotted line and variables.
Knit 1
Purl 2
Sift 10 grams of arsenic
45
Instructions -- Application
• Some instructions can only be applied to a
specific type of values or variables
• Examples:
46
Instructions (Primitives) -Recommendations
• When writing an algorithm, make each
instruction simple and unambiguous
• Example:
Cut chicken into pieces and Cut chicken into pieces.
brown the pieces on all
Heat olive oil in a casserole
sides in a casserole dish
dish.
in hot olive oil.
Brown the chicken pieces in
the casserole dish.
47
Instruction (Primitives)
• When
an algorithm,
make the
A writing
“sequence”
of
instructions
and unambiguous.
simplesimple
instructions
• Example:
Cut chicken into pieces and
brown the pieces on all
sides in a casserole dish in
hot olive oil.
Cut chicken into pieces.
Heat olive oil in a casserole
dish.
Brown the chicken pieces in
the casserole dish.
48
Conclusion
• An algorithm must:
– Be lucid, precise and unambiguous
– Give the correct solution in all cases
– Eventually end.
49
Developing an algorithm
• To help the initial analysis, the
problem should be divided into 3
separate components:
1. Input: a list of the source data provided to
the problem
2. Output: a list of the outputs required
3. Processing: a list of actions needed to
produce the required outputs.
50
Example 1. Add three numbers

A program is required to read
three numbers, add them
together and print their
total.
51
Solution:
1. Underline the nouns and adjectives used
in the specification  establish the
input, output component and any object
that are required.
A program is required to read three
numbers, add them together and
print their total.
52
• Defining diagram
Input
Number1
Number2
Number3
Processing
Output
total
53
2. Underline the verbs and adverbs used in
the specification  establish the action
required.
A program is required to read
three numbers, add them
together and print their
total.
54
• Defining diagram
Input
Processing
Number1 Read three numbers
Number2 Add numbers together
Number3 Print total number
Output
total
55
3. Writing down the processing steps in an
algorithm,
Read three numbers
Add numbers together
Print total number
56
Example 2. Find average temperature
• A program is required to prompt
the terminal operator for the
maximum and minimum temperature
readings on a particular day,
accept those readings as
integers, and calculate and
display to the screen the average
temperature, calculated by
(maximum temperature + minimum
temperature)/2.
57
Step 1
• A program is required to prompt
the terminal operator for the
maximum and minimum temperature
readings on a particular day,
accept those readings as
integers, and calculate and
display to the screen the average
temperature, calculated by
(maximum temperature + minimum
temperature)/2.
58
• Defining diagram
Input
Max_temp
Min_temp
Processing
Output
Avg_temp
59
Step 2
• A program is required to prompt
the terminal operator for the
maximum and minimum temperature
readings on a particular day,
accept those readings as
integers, and calculate and
display to the screen the average
temperature, calculated by
(maximum temperature + minimum
temperature)/2.
60
• Defining diagram
Input
Max_temp
Min_temp
Processing
Output
Prompt for temperatures
Avg_temp
Get temperatures
Calculate average temperature
Display average temperature
61
Assignment1.
Compute mowing time
• A program is required to read
from the screen the lenght and
widht of a rectangular house
block, and the lenght and width
of the rectangular house that has
been built on the block. The
algorithm should then compute and
display the mowing time required
to cut the grass around the
house, at the rate of two square
metres per minute.
62