alg0526
  • 1:40:53,
  • 439 views,
  • 2022-05-26,
  • 上傳者: 系統管理者,
  •  0
 
 
 
  • 1. index 1
  • 2. Tracing Back in the LCS Algorithm
  • 3. ** after Chapter7.ppt
  • 4. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
  • 5. Tracing Back in the LCS Algorithm
  • 6. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
  • 7. Tracing Back in the LCS Algorithm
  • 8. ** after Chapter7.ppt
  • 9. Tracing Back in the LCS Algorithm
  • 10. ** after Chapter7.ppt
  • 11. Fibonacci Sequence
  • 12. Dynamic Programming
  • 13. The Shortest Path
  • 14. The Shortest Path in Multi-stage Graphs
  • 15. Dynamic Programming Approach
  • 16. d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called
  • 17. Backward Approach (Forward Reasoning)
  • 18. Slide 9
  • 19. Principle of Optimality
  • 20. Dynamic Programming
  • 21. The Resource Allocation Problem
  • 22. The Multi-Stage Graph Solution
  • 23. The Resource Allocation Problem
  • 24. The Multi-Stage Graph Solution
  • 25. Slide 14
  • 26. The Longest Common Subsequence (LCS) problem
  • 27. The LCS Algorithm
  • 28. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
  • 29. Tracing Back in the LCS Algorithm
  • 30. The Two-Sequence Alignment Problem
  • 31. Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.
  • 32. Let Ai,j denote the optimal alignment score between a1 a2  ai and b1 b2  bj and, where 1 i m and 1 j  n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2  ai are all aligned with “-”. A0,j : b1 b2  bj are all aligned with “-”.f(ai ,-): ai is al
  • 33. The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:
  • 34. In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the
  • 35. Edit Distance
  • 36. For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of
  • 37. Slide 26
  • 38. The RNA Maximum Base Pair Matching Problem
  • 39. E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:
  • 40. An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1  i < j  n.(1) j - i > t, where t is a small positive constant. Typically, t =
  • 41. Dynamic Programming
  • 42. To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.
  • 43. Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.
  • 44. Case 3: In the optimal solution, rj is paired with some rk, where i + 1  k  j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.
  • 45. Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then
  • 46. Slide 35
  • 47. Algorithm to Compute M1,n
  • 48. Slide 37
  • 49. 0/1 Knapsack Problem
  • 50. The Multi-Stage Graph Solution
  • 51. 0/1 Knapsack Problem
  • 52. The Multi-Stage Graph Solution
  • 53. The Dynamic Programming Approach
  • 54. The Multi-Stage Graph Solution
  • 55. The Dynamic Programming Approach
  • 56. Optimal Binary Search Trees
  • 57. Optimal Binary Search Trees
  • 58. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 59. Optimal Binary Search Trees
  • 60. Optimal Binary Search Trees
  • 61. Optimal Binary Search Trees
  • 62. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 63. The Dynamic Programming Approach
  • 64. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 65. Optimal Binary Search Trees
  • 66. Optimal Binary Search Trees
  • 67. Optimal Binary Search Trees
  • 68. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 69. The Dynamic Programming Approach
  • 70. General Formula
  • 71. Computation Relationships of Subtrees
  • 72. General Formula
  • 73. The Dynamic Programming Approach
  • 74. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 75. The Dynamic Programming Approach
  • 76. General Formula
  • 77. Computation Relationships of Subtrees
  • 78. General Formula
  • 79. Computation Relationships of Subtrees
  • 80. General Formula
  • 81. Computation Relationships of Subtrees
  • 82. General Formula
  • 83. The Dynamic Programming Approach
  • 84. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 85. Optimal Binary Search Trees
  • 86. Optimal Binary Search Trees
  • 87. Optimal Binary Search Trees
  • 88. Identifiers : 4, 5, 8, 10, 11, 12, 14Internal node: successful search, Pi External node: unsuccessful search, Qi
  • 89. Optimal Binary Search Trees
  • 90. Optimal Binary Search Trees
  • 91. The Dynamic Programming Approach
  • 92. The Multi-Stage Graph Solution
  • 93. 0/1 Knapsack Problem
  • 94. Slide 37
  • 95. Algorithm to Compute M1,n
  • 96. Slide 35
  • 97. Find the k between i+1 and j+ 4 such that Mi,j is the maximum, we have Compute Mi,j by the following recursive formula If j - i ≦ 3, then Mi,j = 0. If j - i > 3, then
  • 98. Case 3: In the optimal solution, rj is paired with some rk, where i + 1  k  j - 4. In this case, find the optimal solutions for riri+1 . . . rk-1 and rk+1rk+1 . . . rj-1 and Mi,j = 1 + Mi,k-i+ Mk+1,j-1.
  • 99. Case 2: In the optimal solution, rj is paired with ri. In this case, find an optimal solution for ri+1ri+2 . . . rj-1 and Mi,j = 1 + Mi+1,j-1.
  • 100. To compute Mi,j, where j- i > 3, we consider the following cases from rj’s point of view. Case 1: In the optimal solution, rj is not paired with any other base. In this case, find an optimal solution for riri+1 . . . rj-1 and Mi,j =Mi,j-1.
  • 101. Dynamic Programming
  • 102. An RNA sequence will be represented as a string of n characters R = r1r2 · · ·rn, where ri {A, C, G, U}. A secondary structure of R is a set S of base pairs (ri, rj), where 1  i < j  n.(1) j - i > t, where t is a small positive constant. Typically, t =
  • 103. E.g.The primary structure of an RNA, R: A–G–G–C–C–U–U–C–C–USix possible secondary structures of RNA, R:
  • 104. The RNA Maximum Base Pair Matching Problem
  • 105. Slide 26
  • 106. For exampleLet A = GTAAHTY and B = TAHHYC(1) Delete the first character G of A. GTAAHTY → TAAHTY(2) Substitute the third character of A by H.TAAHTY → TAHHTY(3) Delete the fifth character of A.TAHHTY → TAHHY(4) Insert C after the last character of
  • 107. Edit Distance
  • 108. In the above table, we have also recorded how each Ai,j is obtained.An arrow from (ai,bj) to (ai-1,bj-1): ai matched with bj. An arrow from (ai,bj) to (ai-1,bj): ai matched with “-”, An arrow from (ai,bj) to (ai,bj-1): bj matched with “-”. Based upon the
  • 109. The Ai,j’s for A = a b d a d and B = b a c d using the above recursive formula are listed below:
  • 110. Let Ai,j denote the optimal alignment score between a1 a2  ai and b1 b2  bj and, where 1 i m and 1 j  n.Then, Ai,j can be expressed as follows: Ai,0 : a1 a2  ai are all aligned with “-”. A0,j : b1 b2  bj are all aligned with “-”.f(ai ,-): ai is al
  • 111. Let f(x, y) denote the score for aligning x with y. If x and y are the same, f(x, y)= 2.If x and y are not the same, f(x, y)= 1.If x or y is “-“, f(x, y)= -1. e.g.A= a b c dB= c b - dThe total score of the alignment is 1+ 2 – 1 + 2 = 4.
  • 112. The Two-Sequence Alignment Problem
  • 113. Tracing Back in the LCS Algorithm
  • 114. The dynamic programming approach for solving the LCS problem:Time complexity: O(mn)
  • 115. The LCS Algorithm
  • 116. The Longest Common Subsequence (LCS) problem
  • 117. Slide 14
  • 118. The Multi-Stage Graph Solution
  • 119. The Resource Allocation Problem
  • 120. Dynamic Programming
  • 121. Principle of Optimality
  • 122. Slide 9
  • 123. Backward Approach (Forward Reasoning)
  • 124. d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18.d(C, T) = min{ 2+d(F, T) } = 2+2 = 4d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. The above way of reasoning is called
  • 125. Dynamic Programming Approach
  • 126. The Shortest Path in Multi-stage Graphs
  • 127. The Shortest Path
  • 128. Dynamic Programming
  • 129. Fibonacci Sequence
  • 130. Chapter 7
  • 131. ** after Chapter7.ppt
  • 132. alg0526
1/132
Volume
  • 速度 :
  • 畫質 :
  • 播放設定
00:00/1:40:53
00:00/15:18
 
 
    訪客如要回應,請先 登入
      解析度 : x
      資料夾 :
      發表時間 :
      2022-05-26 15:26:17
      觀看數 :
      439
      長度 :
      1:40:53
      發表人 :
      系統管理者
      部門 :
      www
      QR Code :