TTƯD-Samsung_STP| Bài giảng Thuật toán ứng dụng| Trường Đại học Bách Khoa Hà Nội

TLƯD-Samsung_STP| Bài giảng Thuật toán ứng dụng| Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 371 trang giúp bạn ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.

34 17 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Thuật toán ứng dụng

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

371 trang 2 tháng trước

Tác giả:

Profile Trịnh Thảo Anh
Design, Analysis and
Implementation of Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology.
September 4, 2017
1 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Plan
Basic
I
Chapter 1: Introduction to algorithms and data structures (weeks 1-2)
I
Chapter 2: Recursion, Backtracking, and Branch-and-Bound (weeks
3-5)
I
Chapter 3: Greedy algorithms (weeks 6)
I
Chapter 4: Divide-and-Conquer (week 7)
I
Chapter 5: Dynamic Programming (weeks 8-9)
I
Chapter 6: Graph algorithms and applications (weeks 10-11)
Advances
I
Chapter 7: Advanced data structures and applications (weeks 12-13)
I
Chapter 8: Algorithms on Strings and applications (week 14-15)
3 / 5
4 / 5
References
1
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to
Algorithms. Second Edition, MIT Press, 2001
2
Robert Lafore. Data structures and Algorithms in Java (2nd Edition)
Sams Publishing, 2002
5 / 5
Introduction to Data Structures
and Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology.
January 19, 2018
1 / 1
First example
Find the largest weight subsequence of a given sequence of numbers
Given a sequence s = ha
1
, . . . , a
n
i
a subsequence is s(i , j) = ha
i
, . . . , a
j
i, 1 ≤ i ≤ j ≤ n
weight w(s(i, j)) =
j
X
k=i
a
k
Problem: find the subsequence having largest weight
http://www.spoj.com/problems/MAXSUMSU/
Example
sequence: -2, 11, -4, 13, -5, 2
The largest weight subsequence is 11, -4, 13 having weight 20
2 / 1
How many subsequences?
Number of couple (i, j) where 1 ≤ i ≤ j ≤ n
n
2
+n
This give a direct algorithm
3 / 1
Direct algorithm — O(n
3
)
Scan all possible subsequences
n
2
+n =
n
2
+n
2
Compute and keep the largest weight subsequence
1 public long algo1 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 for ( int i = 0; i < n; i ++){
5 for ( int j = i; j < n; j ++){
6 int s = 0;
7 for ( int k = i; k <= j ; k ++)
8 s = s + a[ k ];
9 max = max < s ? s : max ;
10 }
11 }
12 return max ;
13 }
4 / 1
Direct algorithm
Faster algorithm — O(n
2
)
Observation:
P
j
k=i
a[k] = a[j] +
P
j−1
k=i
a[k]
1 public long algo2 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 for ( int i = 0; i < n; i ++){
5 int s = 0;
6 for ( int j = i; j < n; j ++){
7 s = s + a [j ];
8 max = max < s ? s : max ;
9 }
10 }
11 return max ;
12 }
5 / 1
Divide And Conquer
Divide the sequence into 2 subsequences at the middle s = s
1
:: s
2
The largest subsequence might
I
be in s
1
or
I
be in s
2
or
I
start at some position of s
1
and end at some position of s
2
Java code:
1 pri vate long m axSeq ( int i, int j ){
2 if ( i == j ) return a [i ];
3 int m = (i +j ) /2;
4 long ml = maxSeq (i ,m );
5 long mr = maxSeq (m +1 ,j );
6 long maxL = max Left (i ,m );
7 long maxR = maxRig ht ( m+1 , j);
8 long maxL R = maxL + maxR ;
9 long max = ml > mr ? ml : mr ;
10 max = max > ma xLR ? max : m axLR ;
11 return max ;
12 }
13 public long algo3 ( int [] a ){
14 int n = a. length ;
15 return ma xSeq (0 , n -1);
16 }
6 / 1
Divide and Conquer — O(n log n)
1 pri vate long m axLe ft ( int i , int j ){
2 long maxL = a[j ];
3 int s = 0;
4 for ( int k = j; k >= i ; k - -){
5 s += a[ k ];
6 maxL = maxL > s ? maxL : s ;
7 }
8 return maxL ;
9 }
10 pri vate long m axR ight ( int i, int j ){
11 long maxR = a[i ];
12 int s = 0;
13 for ( int k = i; k <= j ; k ++){
14 s += a[ k ];
15 maxR = maxR > s ? maxR : s ;
16 }
17 return maxR ;
18 }
7 / 1
Dynamic programming
General principle
Division: divide the initial problem into smaller similar problems
(subproblems)
Storing solutions to subproblems: store the solution to subproblems
into memory
Aggregation: establish the solution to the initial problem by
aggregating solutions to subproblems stored in the memory
8 / 1
Dynamic programming
Largest subsequence
Division:
I
Let s
i
be the weight of the largest subsequence of a
1
, . . . , a
i
ending at
a
i
Aggregation:
I
s
1
= a
1
I
s
i
= max{s
i−1
+ a
i
, a
i
}, ∀i = 2, . . . , n
I
Solution to the original problem is max{s
1
, . . . , s
n
}
Number of basic operations is n (best algorithm)
9 / 1
Dynamic programming — O(n)
1 public long algo4 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 int [] s = new int [n ];
5 s [0] = a [0];
6 max = s [0];
7 for ( int i = 1; i < n; i ++){
8 if (s [i -1] > 0) s [i] = s [i -1] + a [i ];
9 else s [i] = a [i ];
10 max = max > s[ i ] ? max : s[i ];
11 }
12 return max ;
13 }
10 / 1
Analyzing algorithms
Resources (memory, bandwithd, CPU, etc.) required by the algorithms
Most concern is the computational time
Input size: number of items in the input
Running time: measured in term of the number of primitive
operations performed
11 / 1
Analyzing algorithms
algo1: T (n) =
n
3
6
+
n
2
2
+
n
3
algo2: T (n) =
n
2
2
+
n
2
algo3:
I
Count the number of addition (”+”) operation T (n)
T (n) =
(
0 if n = 1
T (
n
2
) + T (
n
2
) + cn if n > 1
I
By induction: T (n) = n c logn
algo4: T (n) = c n
12 / 1
Analyzing algorithms
Worst-case running time: the longest running time for any input of
size n
Best-case running time: the shortest running time for any input of
size n
Average-case running time: probabilistic analysis (make assumption of
a distribution of the input) yields expected running time
13 / 1
| 1/371
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Design, Analysis and Implementation of Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology. September 4, 2017 1 / 5 General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output I Objectives of the course
F Skills: Design, analysis and implementation of algorithms Introduction Questions you may have I What are algorithms? I Why do we learn this course? 2 / 5 I Objectives of the course
F Skills: Design, analysis and implementation of algorithms Introduction Questions you may have I What are algorithms? I Why do we learn this course? General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output 2 / 5 Introduction Questions you may have I What are algorithms? I Why do we learn this course? General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output I Objectives of the course
F Skills: Design, analysis and implementation of algorithms 2 / 5 Plan Basic
I Chapter 1: Introduction to algorithms and data structures (weeks 1-2)
I Chapter 2: Recursion, Backtracking, and Branch-and-Bound (weeks 3-5)
I Chapter 3: Greedy algorithms (weeks 6)
I Chapter 4: Divide-and-Conquer (week 7)
I Chapter 5: Dynamic Programming (weeks 8-9)
I Chapter 6: Graph algorithms and applications (weeks 10-11) Advances
I Chapter 7: Advanced data structures and applications (weeks 12-13)
I Chapter 8: Algorithms on Strings and applications (week 14-15) 3 / 5 4 / 5 References 1
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to
Algorithms. Second Edition, MIT Press, 2001 2
Robert Lafore. Data structures and Algorithms in Java (2nd Edition) Sams Publishing, 2002 5 / 5
Introduction to Data Structures and Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology. January 19, 2018 1 / 1 First example
Find the largest weight subsequence of a given sequence of numbers
Given a sequence s = ha1, . . . , ani
a subsequence is s(i , j ) = hai , . . . , aj i, 1 ≤ i ≤ j ≤ n weight w (s(i , j )) = j X ak k=i
Problem: find the subsequence having largest weight
http://www.spoj.com/problems/MAXSUMSU/ Example
sequence: -2, 11, -4, 13, -5, 2
The largest weight subsequence is 11, -4, 13 having weight 20 2 / 1 How many subsequences?
Number of couple (i , j ) where 1 ≤ i ≤ j ≤ n n+n 2 This give a direct algorithm 3 / 1 Direct algorithm — O(n3)
Scan all possible subsequences n +n = n2+n 2 2
Compute and keep the largest weight subsequence 1
p u b l i c l o n g a l g o 1 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4
for ( int i = 0; i < n ; i + + ) { 5
for ( int j = i ; j < n ; j + + ) { 6 int s = 0; 7
for ( int k = i ; k <= j ; k ++) 8 s = s + a [ k ]; 9 max = max < s ? s : max ; 10 } 11 } 12 r e t u r n max ; 13 } 4 / 1 Direct algorithm Faster algorithm — O(n2) Observation: Pj a[k] = a[j ] + Pj−1 a[k] k=i k=i 1
p u b l i c l o n g a l g o 2 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4
for ( int i = 0; i < n ; i + + ) { 5 int s = 0; 6
for ( int j = i ; j < n ; j + + ) { 7 s = s + a [ j ]; 8 max = max < s ? s : max ; 9 } 10 } 11 r e t u r n max ; 12 } 5 / 1 Divide And Conquer
Divide the sequence into 2 subsequences at the middle s = s1 :: s2 The largest subsequence might I be in s1 or I be in s2 or
I start at some position of s1 and end at some position of s2 Java code: 1
p r i v a t e l o n g m a x S e q ( int i , int j ){ 2
if ( i == j ) r e t u r n a [ i ]; 3 int m = ( i + j ) / 2 ; 4
l o n g ml = m a x S e q ( i , m ); 5
l o n g mr = m a x S e q ( m +1 , j ); 6
l o n g m a x L = m a x L e f t ( i , m ); 7
l o n g m a x R = m a x R i g h t ( m +1 , j ); 8
l o n g m a x L R = m a x L + m a x R ; 9
l o n g max = ml > mr ? ml : mr ; 10
max = max > m a x L R ? max : m a x L R ; 11 r e t u r n max ; 12 } 13
p u b l i c l o n g a l g o 3 ( int [] a ){ 14 int n = a . l e n g t h ; 15
r e t u r n m a x S e q (0 , n - 1 ) ; 16 } 6 / 1
Divide and Conquer — O(n log n) 1
p r i v a t e l o n g m a x L e f t ( int i , int j ){ 2 l o n g m a x L = a [ j ]; 3 int s = 0; 4
for ( int k = j ; k >= i ; k - -){ 5 s += a [ k ]; 6
m a x L = m a x L > s ? m a x L : s ; 7 } 8 r e t u r n m a x L ; 9 } 10
p r i v a t e l o n g m a x R i g h t ( int i , int j ){ 11 l o n g m a x R = a [ i ]; 12 int s = 0; 13
for ( int k = i ; k <= j ; k + + ) { 14 s += a [ k ]; 15
m a x R = m a x R > s ? m a x R : s ; 16 } 17 r e t u r n m a x R ; 18 } 7 / 1 Dynamic programming General principle
Division: divide the initial problem into smaller similar problems (subproblems)
Storing solutions to subproblems: store the solution to subproblems into memory
Aggregation: establish the solution to the initial problem by
aggregating solutions to subproblems stored in the memory 8 / 1 Dynamic programming Largest subsequence Division:
I Let si be the weight of the largest subsequence of a1, . . . , ai ending at ai Aggregation: I s1 = a1
I si = max{si−1 + ai , ai }, ∀i = 2, . . . , n
I Solution to the original problem is max{s1, . . . , sn}
Number of basic operations is n (best algorithm) 9 / 1 Dynamic programming — O(n) 1
p u b l i c l o n g a l g o 4 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4 int [] s = new int [ n ]; 5 s [0] = a [ 0 ] ; 6 max = s [ 0 ] ; 7
for ( int i = 1; i < n ; i + + ) { 8
if ( s [ i -1] > 0) s [ i ] = s [ i -1] + a [ i ]; 9 e l s e s [ i ] = a [ i ]; 10
max = max > s [ i ] ? max : s [ i ]; 11 } 12 r e t u r n max ; 13 } 10 / 1 Analyzing algorithms
Resources (memory, bandwithd, CPU, etc.) required by the algorithms
Most concern is the computational time
Input size: number of items in the input
Running time: measured in term of the number of primitive operations performed 11 / 1 Analyzing algorithms algo1: T (n) = n3 + n2 + n 6 2 3 algo2: T (n) = n2 + n 2 2 algo3:
I Count the number of addition (”+”) operation T (n) ( 0 if n = 1 T (n) = T ( n ) + T ( n ) + cn if n > 1 2 2
I By induction: T (n) = n c logn algo4: T (n) = c n 12 / 1 Analyzing algorithms
Worst-case running time: the longest running time for any input of size n
Best-case running time: the shortest running time for any input of size n
Average-case running time: probabilistic analysis (make assumption of
a distribution of the input) yields expected running time 13 / 1