Transcript Categories of languages

The Programming Layer
1
Outline
Concepts
– Definition
– How to develop an algorithm
– Essential features
Three Constructs
Algorithm Representation
– Pseudocode
Basic algorithms
2
Outline
• Evolution
• Categories of languages
• Building programs
3
Objectives
• Define algorithms.
• List the 5 essential properties of an algorithm.
• Define and use the three constructs for developing
algorithms: sequence, decision, and repetition.
• Understand and use tools to represent algorithms:
pseudocode
• Understand the concept of modularity and
subalgorithms.
• List and comprehend common algorithms, such as
sorting and searching.
4
Objectives
• Have a vision of computer language evolution.
• Distinguish between machine, assembly, and highlevel languages.
• Distinguish between the different categories of
languages: procedural, object-oriented, functional,
declarative, and special.
• Understand the process of creating and running a
program.
5
part 1
DEFINITION
6
Informal definition
7
Example--Finding the largest integer
among five integers
8
Defining actions
9
Refinement
• 2 problems with the previous method:
– The action in the first step is different from the
ones for the other steps.
– The wording is not the same in steps 2 to 5.
10
Generalization
11
Formal definition
• Algorithm: an ordered set of unambiguous steps
that produces a result and terminates in a finite
time.
• It is a step-by-step problem-solving procedure,
especially an established, recursive computational
procedure for solving a problem in a finite number
of steps.
• It is a precise, systematic method for producing a
specified result.
12
5 essential properties of algorithms
• To write algorithms that are specified well
enough for a computer to follow, make sure
every algorithm has five essential properties:
–
–
–
–
–
Inputs specified
Outputs specified
Definiteness
Effectiveness
Finiteness
13
Input specified
• The inputs are the data that will be transformed
during the computation to produce the output.
• We must specify the type of the data, the amount
of data, and the form that the data will take.
• Suppose the algorithm is a recipe. We must list the
ingredients(type of inputs), their
quantities(amount of input), and their preparation,
if any(form of inputs), as in “1/4 cup onion,
minced.”
14
Outputs specified
• The outputs are the data resulting from the
computation, the intended result.
• Often the description is given in the name of the
algorithm, as in “Algorithm to compute a batting
average.”
• As with inputs, we must specify the type, amount,
and any form of the outputs. “3 dozen 3-inch
chocolate chip cookies.”
• A possible output for some computation is a
statement that there can be no output—that is, no
solution is possible.
15
Definiteness
• Algorithms must specify every step.
• Definiteness means specifying the sequence of
operations for transforming the inputs into the
outputs.
• Every detail of each step must be spelled out,
including how to handle errors.
• Definiteness ensures that if the algorithm is
performed at different times or by different agents
(people or computers) using the same data, the
output will be the same.
16
Effectiveness
• It must be possible for the agent to execute the
algorithm mechanically without any further inputs,
special talent, clairvoyance, creativity, help from
Superman, and so on.
• Whereas definiteness specifies which operations
to do, effectiveness means that they are doable.
• Examples of ineffectiveness: “Enter the amount of
income you would have received this year had you
worked harder”
17
Finiteness
• An algorithm must have finiteness; it must
eventually stop, either with the right output or
with a statement that no solution is possible.
• If no answer comes back, we can’t tell whether the
algorithm is still working on an answer or is just
plain “stuck”.
• Finiteness becomes an issue for computer
algorithms because if the algorithm doesn’t
specify when to stop the repetition, the computer
will continue to repeat the instructions forever. For
example, divide 3 into 10.
• Any process having these five properties will be
18
called an algorithm.
part 2
3 CONSTRUCTS
19
3 Constructs
• Computer scientists have defined three
constructs for a structured program or
algorithm.
• The idea is that a program must be made up
of a combination of only these three
constructs: sequence, decision (selection),
and repetition.
20
Sequence
• An algorithm, and eventually a program, is
a sequence of instructions, which can be a
simple instruction or either of the other two
constructs.
• A program is an algorithm that has been
customized to solve a specific task under a
specific set of circumstances in a specific
language.
21
Decision
• Some problems can not be solved with only
a sequence of instructions.
• Sometimes you need to test a condition.
• If the result of testing is true, you follow a
sequence of instructions; if it is false, you
follow a different sequence of instructions.
• This is called the decision (selection)
construct.
22
Repetition
• In some problems, the same sequence of
instructions must be repeated.
• You handle this with the repetition (loop)
construct.
23
part 3
Algorithm Representation
24
Algorithm Representation
• We can use different tools to represent
algorithms:
– Pseudo-code
25
Pseudocode
• It is an English-like representation of the code
required for an algorithm. It is part English and
part structured code.
– English part provides a relaxed syntax that is easy to
read.
– Code part consists of an extended version of the basic
algorithmic constructs (sequence, decision and
repetition).
• Until now, there is no standard for pseudocode.
26
Pseudocode example
Algorithm: Finding Smallest
Purpose: This algorithm finds the smallest number among a
list of numbers.
Pre: List of numbers
Post: None
Return: The Smallest
1. Set smallest to the first number
2. loop (not end of list)
2.1 if (next number < smallest)
2.1.1 set smallest to next number
2.2 end if
3. end loop
4. Return smallest
End finding Smallest
27
Pseudocode
• An algorithm written in pseudocode can be
decomposed into several elements and constructs.
• Header: name the algorithm.
• Purpose, precondition, postcondition and return:
– The purpose is a short statement about what the
algorithm does;
– The precondition lists any requirements;
– The postcondition identifies any effect created;
– The return shows what is returned from the algorithm.
If there is nothing to be returned, the null should be
specified.
• Statement numbers: list execution order.
• Statement constructs: based on three constructs.
28
Pseudocode
29
Example 1
Write an algorithm in pseudocode that finds
the average of two numbers
Solution
AverageOfTwo
Input: Two numbers
1. Add the two numbers
2. Divide the result by 2
3. Return the result of step 2
End
Example 2
Write an algorithm to change a numeric grade to a
pass/no pass grade.
Solution
Pass/NoPassGrade
Input: One number
1. if (the number is greater than or equal to 60)
then
1.1 Set the grade to “pass”
else
1.2 Set the grade to “nopass”
End if
2. Return the grade
End
Example 3
Write an algorithm to change a numeric grade to a letter grade.
Solution
LetterGrade
Input: One number
1. if (the number is between 90 and 100, inclusive)
then
1.1 Set the grade to “A”
End if
2. if (the number is between 80 and 89, inclusive)
then
2.1 Set the grade to “B”
End if
… See page 148
Example 4
Write an algorithm to find the largest of a set of numbers.
You do not know the number of numbers.
Solution
1.
2.
3.
FindLargest
Input: A list of positive integers
Set Largest to 0
while (more integers)
2.1 if (the integer is greater than Largest)
then
2.1.1 Set largest to the value of the integer
End if
End while
Return Largest
End
Example 5
Write an algorithm to find the largest of 1000 numbers.
Solution
1.
2.
3.
4.
FindLargest
Input: 1000 positive integers
Set Largest to 0
Set Counter to 0
while (Counter less than 1000)
3.1 if (the integer is greater than Largest)
then
3.1.1 Set Largest to the value of the integer
End if
3.2 Increment Counter
End while
Return Largest
End
Subprograms
• The principles of structured programming require
that an algorithm be broken into small units called
subalgorithms (the term subprograms, subroutines,
procedures, functions, methods, and modules are
also used).
• Each subalgorithm is in turn divided into smaller
subalgorithms.
• The process continues until the subalgorithm
become intrinsic (understood easily).
35
Subprograms
• We can divide “Algorithm Find Largest”
into a main algorithm and a subalgorithm.
• In each iteration, the algorithm finds the
larger of two integers.
• We can separate this part of the task and
create a small subtask out of it.
36
Subprograms
• In line 2.1, FindLargest is suspended and
FindLarger begins.
• FindLarger finds the larger number between the
current Largest value and the current integer value.
This is known as a function call.
• Note that in each iteration, FindLarger is called
once.
• The advantages of using subalgorithms:
– It is more understandable.
– A subalgorithm can be called many times in different
parts of the main algorithm without being rewritten.
37
Subprograms
1.
2.
3.
1.
FindLargest
Input: A list of positive integers
Set Largest to 0
while (more integers)
2.1 FindLarger
End while
Return Largest
End
FindLarger
Input: Largest and current integer
if (the integer is greater than Largest)
then
1.1 Set Largest to the value of the integer
End if
End
38
Example
1. Write an algorithm that will calculate and print
the average grade on three tests for an entire class.
(in pseudocode, structure chart and flowchart)
Pseudocode:
1. Get the 3 test scores;
2. Add the scores together;
3. Divide the sum by 3;
4. Print the average;
5. Repeat step1 through 4 for each student.
39
Example
2. Write an algorithm for a simple calculator (in
pseudocode and structure chart).
Pseudocode:
1. Get two numbers and the operation desired.
2. Check the operation:
2.1 If operation is addition, the result is the first + the
second;
2.2 If operation is subtraction, the result is the first the second;
2.3 If operation is multiplication, the result is the first *
the second;
2.4 If operation is division, check the second number:
2.4.1 If zero, send error message.
2.4.2 If not zero, the first / the second.
3. Print out the result or the error message.
40
Example
3. Write an algorithm in pseudocode for a program to
calculate the area of simple shapes (rectangle, right
triangle and circle).
1.
2.
Get the shape desired.
If it is a rectangle:
2.1 get the length and width.
2.2 calculate the area as length * width.
3. If it is a right triangle:
3.1 get the base and height.
3.2 calculate the area as base* height / 2.
4. If it is a circle:
4.1 get the radius.
4.2 calculate the area as radius * radius * 3.14.
5. Print out the area.
41
part 4
Basic Algorithms
42
Summation
43
Product
44
Sorting
• Sorting is the process by which data are
arranged according to their values.
• There are three fundamental sorting
algorithms:
– Selection sort
– Bubble sort
– Insertion sort
45
Selection sort
• In selection sort, the list is divided into 2 sublists—sorted
and unsorted—which are divided by an imaginary wall.
• You find the smallest element from the unsorted sublist
and swap it with the element at the beginning of the
unsorted data.
• After each selection and swapping, the imaginary wall
moves one element ahead, increasing the number of sorted
elements and decreasing the number of unsorted ones.
• Each time you move one element from the unsorted sublist
to the sorted sublist, you have completed a sort pass.
• A list of n elements requires n-1 passes to completely
rearrange the data.
46
47
48
49
Bubble sort
• In bubble sort method, the list is divided into 2 sublists—
sorted and unsorted.
• The smallest element is bubbled from the unsorted sublist
and moved to the sorted sublist.
• After the smallest element has been moved to the sorted
list, the wall moves one element ahead.
• Each time an element moves from the unsorted sublist to
the sorted sublist, one sort pass is completed.
• Given a list of n elements, bubble sort requires up to n-1
passes to sort the data.
50
51
Insertion sort
• In insertion sort method, the list is divided into 2
sublists—sorted and unsorted.
• In each pass, the first element of the unsorted
sublist is picked up, transferred to the sorted list,
and inserted at the appropriate place.
• Note that a list of n elements will take at most n-1
passes to sort the data.
52
53
Searching
• Searching is the process of finding the
location of a target among a list of objects.
• In the case of a list, searching means that
given a value, you want to find the location
(index) of the first element in the list that
contains that value.
54
Sequential search
• Sequential search is used if the list being
searched is not ordered.
• In a sequential search, you start searching
for the target from the beginning of the list.
• You continue until you either find the target
or you are sure that it is not in the list
(because you have reached the end of the
list).
55
56
Binary search
• If the list is sorted, you can use a more
efficient algorithm called binary search.
• A binary search starts by testing the data in
the element at the middle of the list.
• This determines if the target is in the first
half or the second half of the list.
• With every pass, we eliminate half of the
list.
57
part 6
Evolution
58
Evolution
• A computer language is a set of predefined
words that are combined into a program
according to predefined rules (syntax).
• Computer languages have evolved from
machine language to natural languages.
59
Machine languages
• Machine language, the lowest level of language, is
the basic language of the computer, representing
data as 1s and 0s.
• Machine programs vary from computer to
computer; that is, they are machine dependent.
• The only language understood by a computer is
machine language.
• These binary digits correspond to the on and off
electrical states of the computer.
60
Machine languages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
00000000
00000100
0000000000000000
01011110 00001100110000100000000000000010
11101111 000101100000000000000101
11101111 10011110 0000000000001011
11111000 10101101
11011111 0000000000010010
0110001011011111 0000000000010101
11101111 00000010
11111011 0000000000010111
11110100 1010110111011111 0000000000011110
0000001110100010
11011111 0000000000100001
11101111 00000010
11111011 0000000000100100
01111110 11110100 10101101
11111000 10101110 110001010000000000101011
0000011010100010
11111011 0000000000110001
11101111 00000010
11111011 0000000000110100
00000100
0000000000111101
00000100
0000000000111101
• Advantage: it works efficiently for computer.
• Disadvantage: it is not convenient for people to read and use.61
Symbolic languages
• Symbolic language, also called assembly language,
is a low-level language that allows a programmer
to use abbreviations or easily remembered words
instead of numbers.
• Assembly language varies from computer to
computer; it’s machine dependent.
• A programmer can write instructions in assembly
language more quickly than in machine language;
however, it’s still not an easy one to learn, and it’s
so tedious to use that mistakes are frequent.
62
Symbolic languages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
00000000 00000100 0000000000000000
Entry
main, ^m<r2>
01011110 00001100 11000010 0000000000000010
subl2
#12,sp
11101111 00010110 0000000000000101
jsb
C$MAIN_ARGS
11101111 10011110 0000000000001011
movab $CHAR_STRING_CON
11111000 10101101 11011111 0000000000010010
01100010 11011111 0000000000010101
pushal -8(fp)
11101111 00000010 11111011 0000000000010111
pushal (r2)
11110100 10101101 11011111 0000000000011110
calls
#2,read
00000011 10100010 11011111 0000000000100001
pushal -12(fp)
11101111 00000010 11111011 0000000000100100
pushal 3(r2)
01111110 11101000 10101101
calls
#2,read
11111000 10101110 11000101 0000000000101011
mull3
-8(fp),-12(fp),00000110 10100010 11111011 0000000000110001
pushal 6(r2)
11101111 00000010 11111011 0000000000110100
calls
#2,print
00000100
0000000000111101
clrl
r0
00000100
0000000000111101
ret
63
Language translators
• A special program called an assembler is
used to translate symbolic code into
machine language.
• A language translator is a type of system
software that translates a program written in
a second- or higher-generation language
into machine language.
64
Language translators
• Languages translators are of three types:
– Assemblers
– Compilers
– Interpreters
Source
Code
Language Translator
Object
Code
65
High-level languages
• A high level language is an English-like
language that allows users to write in a
familiar notation, rather than numbers or
abbreviations.
• Most high-level languages are not machine
dependent; they can be used on more than
one kind of computers.
• They are portable, allowing the programmer
to concentrate on the application rather than
the intricacies of the computer.
66
High-level languages
• The translator for high-level languages is
depending on the language, either a compiler or an
interpreter.
• Compiler—execute later. It’s software that looks
at an entire high-level program before translating
it into machine language. Examples are C and
COBOL.
• Interpreter—execute immediately. It’s software
that converts high-level language statements into
machine language one at a time, in succession.
Examples are BASIC and LISP.
67
Natural languages
• Natural languages are of two types.
– The first are ordinary human languages (such as
Chinese, English, Spanish and so on).
– The second are programming languages that
use human language to give people a more
natural connection with computer.
• Natural languages are part of the field of
study known as artificial intelligence (AI).
68
part 7
Categories of languages
69
Categories of languages
• We divide computer languages into five
categories:
70
Procedural languages
• A procedural language is a set of instructions that
are executed one by one from beginning to end
unless an instruction forces the control elsewhere.
• When programmers need to solve a problem using
one of the procedural languages, they should know
the procedure to follow.
• Because each instruction of procedural languages
is a command to the computer system to do some
specific task, procedural languages sometimes
called imperative languages.
71
Procedural languages
• FORTRAN (FORmula TRANslation)
• COBOL (Common Business-Oriented
Language
• Pascal
• C
• Ada
72
Object-oriented languages
• Unlike C and Pascal are procedural oriented
languages, forcing the user to follow a
predetermined path from step A to Step B
and so on, object-oriented languages are
event driven—that is, they respond to input
from the user or other programs at
unregulated times and thus are driven by
user choices.
73
Object-oriented languages
• If we think of a data item in a programming
language as an object, a program can be thought of
as a series of operations that you want to perform
on the object.
• In procedural languages, the objects are passive.
They do not have operations defined for them. The
programmers define the operations and apply them
to the objects.
• In object-oriented programming, the objects and
the operations to be applied to them are tied
together. The objects are active.
74
Object-oriented languages
• C++
– Encapsulation
– Inheritance
– Polymorphism
• Java
– Application vs. applet
– Multithreading
75
Part 8
Building a program
76
Building a program
• It is the job of a programmer to write the
program and then turn it into an executable
(machine language) file.
• There are 3 steps in this process:
– Writing and editing the program
– Compiling the program
– Linking the program with the required library
modules
77
Edit
program
Compile
program
*.c
Edit
Link
program
C Library
Compile
System
*.exe
*.obj
Compile
Link
Execute
*.obj
78
79
Objectives
• Define algorithms.
• List the 5 essential properties of an algorithm.
• Define and use the three constructs for developing
algorithms: sequence, decision, and repetition.
• Understand and use tool to represent algorithms:
pseudocode.
• Understand the concept of modularity and
subalgorithms.
• List and comprehend common algorithms, such as
sorting and searching.
80
Objectives
• Have a vision of computer language evolution.
• Distinguish between machine, assembly, and highlevel languages.
• Distinguish between the different categories of
languages: procedural, object-oriented, functional,
declarative, and special.
• Understand the process of creating and running a
program.
81
That’s all for this chapter!
82