Dynamic Programming Related Questions

In summary, the conversation discusses the difference between a compact valued and single valued correspondence, the concept of continuity on a compact set and its relation to boundedness and maximum value, and the difference between Supremum and Maximum. It is explained that some sets may have a least upper bound but no maximum, and the maximum value may not necessarily be contained in the set. Additionally, it is clarified that there is no smallest real number greater than 0.
  • #1
sampahmel
21
0
Hi all,

(1.) Can someone tell me the difference between a compact valued and single valued correspondence?

(2.) I have been seeing repeating themes of "continuity on a compact set". Does that imply boundedness and thus possible to attain maximum?

(3.) What's the difference between Supremum (I know it is the l.u.b.) and Maximum?

Thank you for taking time out to read and to answer.
 
Mathematics news on Phys.org
  • #2
sampahmel said:
(3.) What's the difference between Supremum (I know it is the l.u.b.) and Maximum?

Thank you for taking time out to read and to answer.

Some sets such as the open interval (0,1) have no maximum, but it has a least upper bound, namely 1. This is not the maximum value since it is not contained in the set.
 
  • #3
Jarle said:
Some sets such as the open interval (0,1) have no maximum, but it has a least upper bound, namely 1. This is not the maximum value since it is not contained in the set.

Does that mean the maximum is (1-G) where G is the smallest real >0
 
  • #4
sampahmel said:
Does that mean the maximum is (1-G) where G is the smallest real >0

No such G exists.
 
  • #5


I am happy to provide a response to your questions about dynamic programming.

(1.) A compact valued correspondence is a function that maps elements from one set to a subset of another set, where the subset is compact. This means that the output of the function is a closed and bounded set. On the other hand, a single valued correspondence is a function that maps elements from one set to a single element in another set. In other words, it has a unique output for every input.

(2.) Continuity on a compact set does not necessarily imply boundedness. A function can be continuous on a compact set but still be unbounded. However, if a function is continuous on a compact set and bounded, then it is possible to attain a maximum value. This is because a continuous function on a compact set must attain both its maximum and minimum values.

(3.) The supremum of a set is the least upper bound, meaning it is the smallest value that is greater than or equal to all the elements in the set. On the other hand, the maximum of a set is the largest element in the set. So while the supremum may or may not be an actual element in the set, the maximum always is.

I hope this helps clarify your questions. Dynamic programming is a powerful tool in optimization and problem-solving, and understanding these concepts will be beneficial in your studies. Best of luck!
 

FAQ: Dynamic Programming Related Questions

What is dynamic programming?

Dynamic programming is a problem-solving approach that involves breaking down a complex problem into smaller subproblems and solving each subproblem separately. The solutions to the subproblems are then combined to find the solution to the original problem. It is commonly used in computer science and mathematics to solve optimization problems.

What are the key characteristics of dynamic programming?

The key characteristics of dynamic programming are overlapping subproblems and optimal substructure. Overlapping subproblems occur when the same subproblem is solved multiple times, and optimal substructure means that the optimal solution to a larger problem can be constructed from optimal solutions to its subproblems.

What is the difference between top-down and bottom-up dynamic programming?

In top-down dynamic programming, also known as memoization, the problem is solved by breaking it down into smaller subproblems and storing the solutions to these subproblems in a table. The table is then used to find the solution to the original problem. In bottom-up dynamic programming, also known as tabulation, the subproblems are solved in a bottom-up manner, starting with the smallest subproblems and using their solutions to solve larger subproblems until the solution to the original problem is found.

What types of problems are typically solved using dynamic programming?

Dynamic programming is commonly used to solve optimization problems, such as the shortest path problem and the knapsack problem. It can also be used to solve problems related to string manipulation, such as the longest common subsequence problem and the edit distance problem.

What are the advantages of using dynamic programming?

Dynamic programming can lead to more efficient and optimized solutions for complex problems. It also allows for the reuse of previously computed solutions, reducing the time and space complexity of the algorithm. Additionally, dynamic programming can provide a more intuitive and structured approach to problem-solving compared to other methods.

Similar threads

Back
Top