matlab代写-M6803|学霸联盟

matlab代写-M6803

时间：2021-10-01

1 Object Modelling and Algorithms M6803 Computational Methods in Engineering A/P Lee Yong Tsui 2 Reference • Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni, Computer Science Press. 3 Modelling of Objects and Events • To solve real world problems, computers need to be able to model real world objects. • Models of real world objects are built using the fundamental data types. • Computer languages have only a few fundamental data types which can be used to represent “things”  Integers  Floating point numbers, single and double precision  Characters and strings  Arrays • The real world is a lot more complicated than that. 4 Modelling of Real World Objects • Modelling of an object involves representations of the characteristics essential to what we wish to manipulate. • Examples  Personal details – name, address, date of birth, occupation, nationality.  Liquid – viscosity, colour, density, boiling point.  Lecture – subject, lecturer, time & date, location. Object Oriented Programming • OOP is a philosophy that forces us to thinking of programming as a means of modelling objects, their properties and operations. • Operations are associated with objects, so that only the right operations can be applied to a given object. • Related objects can be “instantiated” and characteristics inherited, thus emphasising discrete, reusable units of programming logic. • An object can be viewed as an independent 'machine' with a distinct role or responsibility. 5 6 Some Practical Problems • Create a computational model for  The marks of a subject in a class.  The marks of different subjects in a class.  A polynomial.  A shop’s income for every day of a month.  The colour of a surface.  Your personal data.  The shape of an object. 7 • • • • For storing multiple items of the same data type. • Simple to use. • Allows fast direct access to any element so long as we know the array index. • Usually requires pre-declared size. Wasteful if not well utilised. • Adding and deleting elements are clumsy, except at the end of the list. Arrays 1 3 2 5 4 6 n n-1 n-2 8 Example • A polynomial can be modelled using an array which stores its coefficients. • Write a program that will read in the coefficients of a polynomial anxn +an-1xn-1 + … + a1x + a0 Find its value given the value of the variable x. • Given two polynomials, find the sum (in the form of a new polynomial, not the value). 9 Another Everyday Problem • Evaluate an arithmetic expression computationally, such as 3*4^2+8-5*4. • Generally, evaluate any mathematical expression, which may include arithmetic operators, square roots, or other mathematical functions such as sine, cosine, etc. 10 Arithmetic Expressions: Infix and Postfix Forms Two ways of writing an expression: infix, where the operators come between the operands, and postfix where the operators come after the operand. Postfix allows expressions to be written without brackets. Infix Postfix 3*4^2+8-5*4 3|4|2|^|*|8|+|5|4|*|- -3*4^2+8-5*4 -3|4|2|^|*|8|+|5|4|*|- -(3*4)^2+(8-5)*4 3|4|*|2|^|-|8|5|-|4|*|+ Note: Postfix is also called reverse Polish notation. 11 Conversion from infix to postfix • First, put a pair of brackets around every step in the expression in the correct priority order, such as ((3*(4^2))+8)-(5*4)) • Then replace every closing bracket by the operator within that bracket. See the arrows above. • Then remove all the remaining brackets, and we are left with the postfix string. 12 Postfix Evaluation Via a Stack • A stack is an array where a new element can only be pushed to the top (or end) of the stack, and popped (removed) from the top; last in first out. • In an evaluation, we traverse the expression from left to right. When we encounter a number, we push it onto the stack. When we encounter an operator, we pop the top two elements off the stack and apply the operator to them, and then push the result back on to the stack. • There is the complication of a unary operator, in which case, only one element need be popped from the stack before applying the operator. • At the end, there should only be one element left on the stack, and it contains the value of the expression. 13 Traversing left to right: 1: push 3 onto stack. 2: push 4 onto stack. 3: push 2 onto stack. 4: operator ^; pop 2 from stack, pop 4 from stack, evaluate 4^2, push result 16 onto stack. 5: operator *; pop 16 from stack, pop 3 from stack, evaluate 3*16, push result 48 onto stack. 6: push 8 onto stack. 16 Evaluating 3|4|2|^|*|8|+|5|4|*|- 3 4 3 1 2 4 3 3 2 3 4 48 5 8 48 6 14 Evaluating 3|4|2|^|*|8|+|5|4|*|- 7: Operator +; pop 8 from stack, pop 48 from stack, evaluate 48+8, push result 56 onto stack. 8: Push 5 onto stack. 9: Push 4 onto stack. 10: Operator *; pop 4 from stack, pop 5 from stack, evaluate 5*4, push result 20 onto stack. 11: Operator -; push 20 from stack, push 56 from stack, evaluate 56-20, push result 36 onto stack. 12: End of expression. Return the final result 36 from the top of the stack. 56 7 8 5 56 5 56 9 4 20 56 10 36 11 8 48 6 15 The Evaluation Algorithm Initialise the stack to empty For each element in the postfix expression { If the element contains a value v push v onto the stack Else If the element is operator

{ v1 = pop the stack

v2 = pop the stack
push v2 v1 onto the stack
}
}
Final result = pop the stack
Exercise: Modify the algorithm to deal with unary operators.
16
Comments
• In the development of an algorithm: the
“native” representation of an “object” may
not necessarily be the best representation
for developing an efficient algorithm for
operating on the object.
• One may need to convert the representation
to another form.
17
Pseudo code
• Pseudo code is used for expressing algorithms step
by step in a form that looks like computer code, but
replacing some tedious details with simple English.
• Normally we keep the use of control key words like
If, Else, For loop, etc.
• In these notes, we adopt a pseudo C style, using { }
for enclosing compound statements, and = for
assignment, for example.
• Also, we normally skip the declaration of variables,
taking the data types to be understood, unless they
are critical to the operation of the algorithm.
18
Problem: Representing a Polygon
• A polygon consists of a list of vertices joined by
edges.
• The list can be stored in an array.
• Perform these operations using the representation:
 insert a new vertex
 delete an existing vertex
 calculate the area of the polygon
 find the nearest edge to a given point
19
Value Value
Linked Lists
• A set of elements that are linked together
via “pointers”.
• Each element has two parts: a value and a
pointer to the next element.
• The head of the list is stored explicitly. It
enables access to all the elements.
Head Value
20
Linked Lists
• Fast for inserting and deleting elements.
Head Value Value Value
Value
Insert a New Element:
Pnew element = Pi
Pi = New element address
P
P
P P
Head Value Value Value P P P
Delete an Element: Pi = Pi+1
21
More Linked Lists
• Doubly linked list: one where there is a
pointer forward and another pointer backward.
This allows fast reverse traversal.

• Circular linked list: one where the last element
points to the first, forming a closed loop.
Head
Head Value Value Value
Value Value Value
22
The Polygon Problem Revisited
• Study the polygon problem in the light of
linked lists.
• Which type of linked list would you use?
Why?
• How do you perform these operations:
 insert a new vertex
 delete an existing vertex
 calculate the area of the polygon
 find the nearest edge to a given point
23
Area of Triangle
• Unsigned area of triangle = |AB × AC|/2.
• Signed area of triangle = ((AB × AC) · N)/2
where N is the unit normal to the plane of
the triangle.
A
C
B A C
B
Area
positive Area negative
24
Area of a Polygon
TotalArea = 0
For i = 2 to n-1
TotalArea = TotalArea + ∆(1, i, i+1)
1
2
4 5
6
7
8
9
10
3
25
Beyond the Polygon
• Solid shapes are bounded by many faces.
• Each face sits on a mathematical surface
bounded by one or more polygons.
• Create a data structure that will support the
modelling of solid objects with many faces.
26
Data Structure and Algorithms
• Data structure is the mechanism for creating the
model of an object.
• Having a model is useless unless we can do things
with it. For example, in the case of a solid model,
we need to be able to display it, find its volume,
determine its strength, or even produce it.
• This requires algorithms.
• Often, there are many algorithms to do the same
thing.
27
Sorting, a common problem
• Given a class of students, or the patients in
a clinic, find a way to store the people so
that you can quickly establish if a particular
person exists in the list.
• Store the words in a dictionary digitally
such that you can find any word quickly.
• Given a set of points scattered in space, find
the point nearest to a given point.
28
A Simpler Sorting Problem
• Given a list of n numbers in an array, sort the list in
ascending order.
• One simple way:
for i = 1 to n
{ for j = i to n
search for the smallest number;
swap it with the ith element;
}
• Total number of searches
n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n2)
29
A Better Sorting Algorithm
• Insertion Sort: Given a list of j sorted numbers,
v1 … vj, to insert a new number vnew into the list,
we write a function Insert which inserts vnew in
the right position in v.
• Then write another function, ISort which takes a
given unsorted list, v, of n elements, and calls
Insert repeatedly to create a progressively sorted
list, starting from the first two elements of v. It
terminates when the complete list is traversed.

30
Insertion Sort
Function ISort (v, n)
{
For j = 1 to n
{
vnew = vj+1;
Insert (v, j, vnew)
}
}
Function Insert (v, j, vnew)
{
i = j;
while vnew < vi and i > 0
{
vi+1 = vi;
i = i–1;
}
vi+1 = vnew;
}
31
Analysis of Insertion Sort
• There are two loops. The outer loop in ISort visits
every element in v, total n visits.
• The inner loop in Insert goes down the partial list
which is sorted and visit each element, until it comes
to the right place. This partial list grows from 1 to n,
as it progresses.
• Hence total visit is 1 + 2 + … + n = n(n-1)/2 in the
worst case.
• But normally the inner loop does not visit every
element of the partial list. So on average, the
performance is better than O(n2).
32
Other Sorting Methods
• Bubble Sort - worst case O(n2), average case
O(n2).
• Quick Sort - worst case O(n2), average case
O(n log2 n).
• Merge Sort - worst and average: O(n log2 n).
• Heap Sort - worst and average: O(n log2 n).

33
Complexity Analysis
• The performance of an
algorithm can often be
characterised using the
big O, over some
fundamental factor that
affects the algorithm.
• This performance can
be for time or storage.
Time
n
O(n2)
O(n)
O(log2n)
O(2n)
34
Searching
• Locate a given value in a given list. For
example, given the name of a person, find
his/her address from the “store”.
• If the store is unsorted, the search will be of
O(n) where n is the number of people stored.
• The performance can be much better if the
store is sorted.
35
Binary Search
• Given a sorted list, v1, v2 … vn, vi ≤ vj for iSearch for the location where a value u is
stored.
i = n/2
If u < vi, repeat the search for v1 … vi-1.
If u > vi, repeat the search for vi+1 … vn.
If u = vi, location found.
• Complexity of the search: O(log2 n)
36
A Binary Tree
• A binary tree consists
of nodes, each of which
may have at most two
children. The top node
is called the root.
• Each non-top node has
a unique parent.
• The depth of a tree is
the number of levels in
the tree.
Root
1
2
3
4
5
6
Level
37
Binary Tree for Sorting
• A binary tree is identified by its root node.
• Each node has a left child and/or a right
child, or no child, in which case it is a
terminal node.
• The nodes hold values in a specific order: If
u is the value held in a node, then its left
child holds a value less than u, and its right
child holds a value greater than or equal to u.
38
Basics of a Binary Tree
• A binary tree is visible via its root node. All
other nodes can be visited by following the
paths to the children. Functions required:
 Left_child(node) – move to the left child of node.
 Right_child(node) – move to the right child of
node.
 Value(node) – value stored at a node
 When a node does not exist, it is denoted by null.
39
Insert a Value onto a Binary Tree
Function Insert_value (v, node)
{ If node is null
{ create new node;
Value(node) = v;
}
Else
{ If v < Value(node)
Insert_value(v, Left_child(node));
Else Insert_value(v, Right_child(node));
}
}
Root: the root of the tree
v: the value to be inserted
40
A Binary Tree with Sorted
Numbers Root
48
45
56
72
63 87
79
61
99
95
88
25
29
24 35
31
37
41
Searching for a Value on a
Binary Tree
Function Search_value (v, node)
// Find the node that contains the value v
{ If node is null
Return no value found;
Else
{ If v < Value(node)
Search_value(v, Left_child(node));
Else If v > Value(node)
Search_value(v, Right_child(node));
Else // value found
Return node;
}
}
42
Complexity of Insertion and
Searching on a Binary Tree
• The complexity depends on the “shape” of
the binary tree.
• If the tree is skewed to one side, then the
complexity would be more like O(n), where
n is the number of elements.
• If the tree is balanced, then the complexity
is O(log2 n), which is a lot better.
43
Functions for Binary Tree
• A data structure requires a basic set of functions
which operates on the structure.
• In the case of binary tree, we have so far
 Insert_value(v, node)
 Search_value(v, node)
 Left_child(node)
 Right_Child(node)
 Value(node)
• There are others.
44
Binary Tree for Arithmetic
Expressions
• Arithmetic expressions
have unary and binary
operators, and can be
very naturally stored on
a binary tree.
• It has operators at non-
terminal nodes and
values at terminal
nodes.
Root
Example: -3*4^2+8-5*4
8
+
4 2
*
^
5 4
*
3
45
Visiting a Binary Tree in
Postorder
Function Postorder (node)
// This function prints the values of
// the nodes in a binary tree in “postorder”
{ If node ≠ Null
{ Postorder (Left_child(node));
Postorder (Right_child(node));
print Value(node);
}
}
This would print -3*4^2+8-5*4 as 3- 4 2 ^ * 8 + 5 4 * -
8
+
4 2
*
^
5 4
*
3
46
Other Forms of Trees
• A tree may not be binary.
A node may have more
than two children.
• For example, a quadtree is
very popular in its use for
subdivision of a 2D
rectangular space into four
equal parts, for successive
spatial partitioning, as
shown in the example on
the right.
Quad Tree
Successive
spatial
partitioning
47
More Trees
• A machine has many parts. Each part can have
many other parts, and so on. This forms a
hierarchy of parts which is easily represented as a
tree on a computer.
• Similarly, company hierarchies can be represented
as trees.
• Also, the folders on your computer form a tree
structure.
• And then there are family trees, which sometimes
become “graphs”.
48
Graphs
• Sometimes trees are not
adequate for describing
an object or system.
• One extension to trees is
graphs where nodes can
have connections
between them.
• Graphs are used
extensively in the
representation of many
real world objects and
problems.
A block
Cities and roads
A
B C
D E
F G
H
49
More Efficient Sorting and
Searching?
• Most of the sorting algorithms are either
O(n2) or O(nlog2n) in complexity.
• Searchings are either O(n) or O(log2n).
• Is there possibly a better method?
50
Hashing Functions
• A value may be stored in a location whose
address is a function of the value.
• Such a function, which transforms a value
into a possibly non-unique address, is a
hashing function.
• These locations are often called “buckets”.

51
• Given the set of integers 23, 16, 8, 4, 13 and 22,
“sort” them into a set of buckets numbered
consecutively. The buckets, in this case, would
simply be an array of elements.
• Hashing function: divide the values by 11, and
return the remainder. Addresses returned: 1, 5, 8,
4, 2, and 0.
13 23 8
Example of Hashing
2
16
1 3 9 10 4 5 6 7 8 0
4 22
52
Analysis of the Operation
• The final “sorted order” is not in a form suitable
for human. But then who cares if it is to be read
only by a machine?
• Every number is operated on only once.
• Hence the complexity of sorting the whole set of n
numbers is O(n). Linear!
• The same operation can be used for searching.
• But there is the problem of “collision”, especially
when there are, in the example, over 11 members.
53
Collision
• Have enough buckets to avoid collision.
• Ensure that the hashing function produces as few
collisions as possible.
• When collision occurs, the new member is either
pushed into the next available bucket in the
sequence or
• The bucket is made the head of a linked list and
the new member becomes the next member in the
list.
54
Hashing Table with Linked List
• • •
• • •
• • •
• • •
55
Problem: Find the Nearest Point
• Given a set of n points on the plane, find the
nearest point from a given point in the x-direction.
x
y
56
The Hashing Algorithm
• Divide the plane into equal
columns (buckets) of
width w.
• Use a hashing function to
place each point in its
column. Complexity O(n).
• Place the given point in its
column using the same
hashing function.
• Search among the points
within this column and the
two neighbouring
columns.
x
y
1 7 6 2 3 4 5 8 9 10 11 12
57
The Hashing Function
• Assuming x > 0, the hashing function is simply
ceiling(x/w), where ceiling returns the smallest
integer larger than x/w.
• Each of the columns will hold a number of points.
Ideally this number should be small, to improve
the speed of searching later. To do so, reduce w.
But this will increase the number of columns.
• This is an example of the typical problem:
balancing between speed and storage
requirements.
58
Conclusion
• Data structure needs designing
• Different structures can serve the same
purpose, supported by different algorithms
• Efficiency of algorithms can be analysed
through complexity analysis
• The best data structure for an object might
not be the best computationally.
59
Software Engineering Principles
• Software development is labour intensive,
requiring a lot of time and effort. To minimise
software development cost, developers follow a
set of well established guidelines.
 The problem and solution must be well specified.
 Your code must be easily readable, which means
• using meaningful variable and function names
• placing appropriate comments in the code
• organising your code neatly.
 Write and use reusable code. Write modular software.
 Document your software properly and completely.
 The program must be tested thoroughly.

学霸联盟