Lập trình động - Dynamic programming (DP)

Lập trình động là một phương pháp giải các bài toán phức tạp bằng cách chia bài toán lớn thành các bài toán nhỏ hơn cùng với việc lưu lại giá trị của các bài toán nhỏ hơn này để tránh việc phải thực hiện lại các thao tác này. Những bài toán có thể áp dụng lập trình động có những thuộc tính sau:

1. Overlapping Subproblems (ví dụ dãy fibonacci khi tính toán fib(5) và fib(6) ta đều phải tính toán fib(4)).
2. Optimal Substructure

1) Overlapping Subproblems

Giống như thuật toán Chia để trị (Divide and Conquer), lập trình động bao gồm các kết quả của subproblems. Trong lập trình động, kết quả của các bài toán con sẽ được lưu vào 1 bảng để ta có thể truy cập trực tiếp thay vì tính toán lại các bài toán con này. Do đó, DP sẽ không hữu dụng khi mà các subproblems không có sự trùng lặp (overlapping) khi tính toán. Vi dụ như Binary Search sẽ không có các subproblems chung; ngược lại đối với bài toán Fibonacci, sẽ có rất nhiều subproblems được tính toán lại nhiều lần.

/* simple recursive program for Fibonacci numbers */
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}

                              
                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Ta thấy rằng fib(3) được gọi 2 lần, do đó, nếu ta lưu giá trị fib(3) thì thay vì phải tính toán lại, ta chỉ cần truy cập trực tiếp kết quả này. Ta có hai phương pháp để lưu các giá trị giống như fib(3) là Memoization(Top down) và Tabulation(Bottom up).

a) Memoization(Top down)

Phương pháp này giống với recursion nhưng trước khi ta tính toán 1 subproblems, ta sẽ tìm trong một bảng. Nếu subproblems này chưa được tính toán, ta sẽ tính toán và lưu vào trong bảng, ngược lại, ta sẽ trả lại trực tiếp giá trị của bảng.

# Python program for Memoized version of nth Fibonacci number

  

# Function to calculate nth Fibonacci number

def fib(n, lookup):

  

    # Base case

    if n == 0 or n == 1 :

        lookup[n] = n

  

    # If the value is not calculated previously then calculate it

    if lookup[n] is None:

        lookup[n] = fib(n-1 , lookup)  + fib(n-2 , lookup) 

  

    # return the value corresponding to that value of n

    return lookup[n]

# end of function

b) Tabulation(Bottom up)

Phương pháp này ta xây dựng một bảng từ subproblems nhỏ nhất đến lớn nhất và cuối cùng trả về giá trị cuối cùng trong bảng. Ví dụ, cùng với bài toán Fibonacci, ta đầu tiên  tính toán fib(0), sau đó fib(1), fib(2), fib(3) v.v... 

# Python program Tabulated (bottom up) version def fib(n):        # array declaration     f = [0]*(n+1)        # base case assignment     f[1] = 1        # calculating the fibonacci and storing the values     for i in xrange(2 , n+1):         f[i] = f[i-1] + f[i-2]     return f[n]

Both Tabulated and Memoized store the solutions of subproblems. In Memoized version, table is filled on demand while in Tabulated version, starting from the first entry, all entries are filled one by one. Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version. For example, Memoized solution of the LCS problem doesn’t necessarily fill all entries.

2) Optimal Substructure
Một bài toán có tính chất optimal substructure nếu optimal solution của bài toán lớn có thể tìm ra thông qua optimal solution của các bài toán con.

Ví dụ trong thuật toán tìm đường đi ngắn nhất Shortest Path, ta nếu ta có node X nằm trên cung ngắn nhất từ một node nguồn u  đến một node đích v thì đường đi ngắn nhất từ u tới v sẽ là combination của đường đi ngắn nhất từ u  tới X và từ X tới v.

Ngược lại bài toán Longest Path không có tính chất này. Ví dụ với đồ thị dưới đây:

Ta sẽ có hai đường dài nhất từ q tới t (không kể các cung có cycle) là: q→r→t và q→s→t . Ở đây, ví dụ longest path q→r→t sẽ không là combination của longest path từ q→r và r→t bởi vì longest path từ q tới r và từ r tới t lần lượt là q→s→t→r và r→q→s→t.

Dense Captioning

Dense captioning task both localizes and describes salient(most outstanding and important) regions in images in natural language. The dense captioning task generalizes object detection when the descriptions consist of a single word, and Image Captioning when one predicted region covers the full image.

Above is an example of dense captioning where each bounding box will correspond to a description (not just a class in classical object detection).

Map, Filter

4.2. Filter

As the name suggests, filter creates a list of elements for which a function returns true. Here is a short and concise example:

number_list = range(-5, 5)
less_than_zero = list(filter(lambda x: x < 0, number_list))
print(less_than_zero)

# Output: [-5, -4, -3, -2, -1]

4.1. Map

Map applies a function to all the items in an input_list. Here is the blueprint:

Blueprint

map(function_to_apply, list_of_inputs)

Most of the times we want to pass all the list elements to a function one-by-one and then collect the output. For instance:

items = [1, 2, 3, 4, 5]
squared = []
for i in items:
    squared.append(i**2)

Map allows us to implement this in a much simpler and nicer way. Here you go:

items = [1, 2, 3, 4, 5]
squared = list(map(lambda x: x**2, items))

Most of the times we use lambdas with map so I did the same. Instead of a list of inputs we can even have a list of functions!

def multiply(x):
    return (x*x)
def add(x):
    return (x+x)

funcs = [multiply, add]
for i in range(5):
    value = list(map(lambda x: x(i), funcs))
    print(value)

# Output:
# [0, 0]
# [1, 2]
# [4, 4]
# [9, 6]
# [16, 8]

lambda function in python

A lambda function is a small anonymous function.

A lambda function can take any number of arguments, but can only have one expression.

lambda arguments : expression

Example

A lambda function that adds 10 to the number passed in as an argument, and print the result:

x = lambda a : a + 10
print(x(5))

Example

A lambda function that sums argument a, b, and c and print the result:

x = lambda a, b, c : a + b + c
print(x(5, 6, 2))

Why Use Lambda Functions?

The power of lambda is better shown when you use them as an anonymous function inside another function.

Say you have a function definition that takes one argument, and that argument will be multiplied with an unknown number:

def myfunc(n):
  return lambda a : a * n

Use that function definition to make a function that always doubles the number you send in:

Example

def myfunc(n):
  return lambda a : a * n

mydoubler = myfunc(2)

print(mydoubler(11))

Or, use the same function definition to make a function that always triples the number you send in:

Example

def myfunc(n):
  return lambda a : a * n

mytripler = myfunc(3)

print(mytripler(11))

Or, use the same function definition to make both functions, in the same program:

Example

def myfunc(n):
  return lambda a : a * n

mydoubler = myfunc(2)
mytripler = myfunc(3)

print(mydoubler(11)) 
print(mytripler(11))

Quote of the day - Continual Learning

1. While some learning occurs only once, such as imprinting in ducklings, a majority occurs continuously throughout an organism’s lifespan.
2. For example, a quite common form of learning is sensitization and habituation, among the most basic forms. These result in the animals increased or reduced response to a given stimulus after repeated exposures. These occur throughout the animal kingdom, from humans to single cells. For example, if you’re walking in a dark room and someone startles you, your reaction is likely to be more exaggerated than if you were startled in a well lit room. This is an example of sensitization, as the dark room exaggerates your response.