Tabulation And Memozitation [ Dynamic Programming ] [ Set 1 ]

LÝ THUYẾT CƠ SỞ

Có hai cách thức để lưu các value của một problem mà những value này có thể được tái sử dụng.
Ở đây, chúng ta tập trung vào hai mô hình của việc giải quyết problem thông qua dynamic programming. Đó là:
1. Tabulation: Sự sắp xếp thành bảng, cột. Từ dưới lên gọi là bottom up.
2. Memoization: Sự ghi nhớ hay lưu trữ. Từ trên xuống gọi là top down

Trước khi đi đến những định nghĩa của hai mục trên, ta xem xét 2 phát biểu sau:
Version 1: Tôi sẽ học lý thuyết của Quy hoạch động từ blog buingoctai.blogspot.com và sau đó practice vài problem trên đây, dĩ nhiên tôi sẽ trở thành chuyên gia về lập trình quy hoạch động.
Version 2:  Để trở thành một chuyên gia về lập trình quy hoạch động, tôi cần luyện tập giải quyết nhiều problem về quy hoạch động, do đó đầu tiên, tôi cần học lý thuyết về quy hoạch động từ trang buingoctai.blogspot.com.

Cả hai version trên đều giống nhau về mặt nội  dung, chỉ khác nhau về cách truyền đạt lời nhắn trên và đó chính xác là cách làm việc của bottom up và top down.
Version 1 có thể được xem như bottom up và Version 2 được xem như top down.

TABULATION METHOD- BOTTOM UP DYNAMIC PROGRAMMING

Đúng như cái tên của nó, bắt đầu từ đấy và tích lũy câu trả lời đến top.
cùng thảo luận vào những mục của sự chuyển đổi trạng thái.
Ta xem trạng thái cơ sở được gắn liền với dp[0] và trạng thái đích là dp[n]. vì vậy ta cần tìm value của trạng thái đích dp[n]
Cách tiếp cận theo kiểu bottom up là chúng ta bắt đầu sự chuyển đổi từ trạng thái cơ bản bottom và đi đến trạng thái top mong muốn.

 Vậy tại sao ta gọi đó là tabulation method ?
Để hiểu được nó, ta cần viết 1 vài dòng code tinh thừa số của một số sử dụng cách tiếp cận bottom up. Các thủ tục thông thường để solve một DP problem là đầu tiên ta cần định nghĩa một trạng thái.
trong trường hợp này ta định nghĩa 1 trạng thái như 1 dp[x] mà ở đó dp[x] là để tìm thừa số của x.
Rất dễ hiểu rằng dp[x+1]=dp[x]*(x+1). ví dụ tìm giai thừa của 4 thì rõ ràng ta thấy giai thừa của 4= giai thừa của 3  nhân cho 4
implement trong c:

Ở cách tiếp cận theo phương pháp tabulation trên, ta bắt đầu sự chuyển tiếp từ đáy với trạng thái cơ bản là dp[0] và tới trạng thái đích là dp[9]. ở đây chúng ta nhận thấy rằng bảng dp được thêm vào một cách tuần tự và chúng ta truy cập và tính trực tiếp từ bảng đó . Và do đó ta gọi phương pháp này là tabulation ( lập bảng)

MEMOZATION METHOD- TOP DOWN DYNAMIC PROGRAMMING

Phương pháp memozation rất giống với phương pháp chia để trị, tức là ta chi nhỏ bài toán thành các bài toán con, sau đó đi tìm lời giải các bài toán con, để tổng hợp thành lời giải cho bài toán ban đầu. Nhưng khác phương pháp chia để trị ở chỗ là phương pháp này nó giúp ta ghi nhớ lời giải các bài toán con để có thể tái sử dụng chúng cho các problem khác nên nó cũng được gọi là phương pháp ghi nhớ.

Ta thấy rằng lời giải của các bài toán con được lưu vào mảng dp[]

TÓM LẠI: Ý tưởng của quy hoạch động khá đơn giản " mỗi khi tính toán một problem nào đó, ta lưu kết quả của nó để trong tương lai, nếu sau này có gặp vấn đề đó sau này thì không phải tính lại nữa. Nếu một problem có thể chia nhỏ thành các sub- problem và các sub-problem này chồng chéo lên nhau, tức kết của sub-problem này dùng để giải các sub-problem kia thì đây là lúc cần dùng quy hoạch động "

Tham khảo: https://www.geeksforgeeks.org/

Đọc tiếp »

LINEAR ALGEBRA ( ĐẠI SỐ TUYẾN TÍNH )

1. CHUYỂN VỊ VÀ CHUYỂN VỊ LIÊN HỢP
   Lý thuyết cơ sở

• Chuyển vị

Cho A ∈ R^m*n, ta nói B ∈ R^m*n là chuyển vị của A nếu như bij=aji với mọi 1<= i <=n
và 1<= j <= m. Chuyển vị của một ma trận nhận được từ ma trận cũ thông qua phép phản xạ gương qua đường chéo chính của ma trận ban đầu. Ký hiệu: T
Nếu  A ∈ R^m*n,  A^T=A thì ma trận A được gọi là ma trận đối xứng.

Ví dụ:

• Chuyển vị liên hợp

Định nghĩa giống với chuyển vị thông thường, tuy nhiên các thành phần của vector hay ma trận là số phức. Việc lấy chuyển vị đi kèm với lấy liên hợp phức. Ký hiệu : H

Nếu A ∈ R^m*n,  A^H=A thì ma trận A được gọi là hermitan.

Ví dụ:

Implement by Python code

Problem: Tìm ma trận chuyển vị của ma trận a và vector b.

Solution: Sử dụng các lớp và hàm mà module numpy cung cấp

Cách implement 1: Ta sử dụng class array của module numpy, tạo ra hai đối tượng a và b.

sau đó ta tìm ma trận chuyển vị của hai ma trận trên bằng cách dùng hàm transpose của module numpy hỗ trợ.

Cách implement 2: Khi tìm ma trận chuyển vị, ta dùng hàm toán tử T của class array.

Kết quả giống nhau cho hai cách implement trên !

Các thuật ngữ tiếng anh dùng cho tra cứu:
Toán tử chuyển vị: Transpose operator
Ma trận đối xứng: Symmetric matrix
chuyển vị liên hợp: Conjugate transpose

Tham khảo tài liệu:
-Machine learning cơ bản- Vũ Hữu Tiệp

Edit bye me_BNT.

Mong nhận được đóng góp ý kiến từ độc giả.

Xin chân thành cảm ơn !

Đọc tiếp »

Median in a stream of intergers ( Part 1) [ Statistical Algorithms ]

Problem: Cho một dãy số interger được đọc từ 1 data stream. Tìm median của dãy online data.

Sau khi số đầu tiên của stream là 5 là median là 5

…….số thứ 2…………….. là 15, dãy số 5 , 15 là median là 10

…….số thứ 3 …. Là 1,dãy số 5,15,1 và median là 5

…….số thứ 4….là 3, dãy số là 5,15,1,3 và median là 4



Lưu ý: Cần sắp xếp trước khi tìm median. Output là median của dãy số interger đọc từ stream.
Một thuật toán như thế gọi là online algorithm.
" Any algorithm that can guarantee output of i-elements after processing i-th element, is said to be online algorithm "( Các định nghĩa luôn được giữ nguyên bảng bằng tiếng anh).

Có 3 solutions cho problem trên, chúng ta bắt đầu với giải pháp đầu tiên:

Method 1: Tư tưởng thuật toán insertion sort
Tóm tắt nội dung thuật toán insertion sort: Thuật toán này giả định ta có 1 nhóm phần tử đầu tiên đã được sắp xếp, ta lần lượt chèn các phần tử còn lại vào nhóm phần tử trên.

Ban đầu, nhóm phần tử đó chỉ là phần tử đầu tiên của dãy. Lập lần 1, ta chèn phần tử thứ 2 vào nhóm trên sao cho phù hợp, ta có số lượng của nhóm phần tử đầu tiên là 2, lập lần 3, ta số lượng nhóm phần tử đầu tiên là 3, cứ như thế lập n-1 lần ( với n là số lượng phần tử của dãy số ban đầu)  thì ta có được danh sách đã được sắp.

Quay trở lại problem trên, nếu ta có thể sắp xếp data ngay khi nó xuất hiện, chúng ta có thể dễ dàng xác định được median. Insertion sort là 1 online algorithm mà sắp xếp data ngay khi nó xuất hiện.

Ta thấy rằng sau khi sắp xếp element thứ i, i elements của mảng thì được sắp xếp. Insertion sort không phụ thuộc vào data tương lai. Điều này làm nó được gọi là online algorithm.

Tuy nhiên, insertion sort mất O(n^2) để sắp xếp n elements. Có lẽ chúng ta có thể dùng binary search trên insertion sort để vị trí của element kế tiếp trong time O(nlogn).

Tuy vậy, chúng ta không thể làm vậy để duy chuyển data trong time O(nlogn).
Nó mất polynomial time trong trường hợp insertion sort.


Implement: Full python code

Time complexity: O(n^2)

Mong nhận được đóng góp từ bạn đọc.

Xin chân thành cảm ơn !

Edit bye me_BNT

Đọc tiếp »

Median of two sorted arrays [ Statistical Algorithm ]

Đề bài: Tìm trung vị của 2 mảng cho trước và có kích thước bằng nhau. ( Mỗi mảng đã được sắp xếp_ ở bài này ta giả sử sắp xếp tăng dần).

Ví dụ ar1=[1 , 12  , 15 ,  26  ,  38]    và     ar2 =[2  , 13  ,  17  ,  30  ,  40]
 Sau khi giao hai mảng ta có 1 mảng chung ar=[1 , 2 , 12, 13 , 15 , 17 , 26 , 30 , 38 , 40]
↝↝↝↝↝↝↝↝Median=(15+17)/2

Tư duy giải thuật 1: Ta dựa trên tư tưởng của giải thuật merge sort
Giải thuật merge sort: Giả sử một mảng số nguyên chưa có thứ tự. Ta sẽ xem các phần tử riêng lẻ hay một nhóm phần tử là một đường chạy ( một nhóm phần tử được gọi là 1 đường chạy nếu thỏa mãn an<an+1<...<an+x ).
Mục đích của giải thuật merge sort là làm giảm số đường chạy về một và mảng được xem sắp xếp xong.
Ta chia các đường chạy có trong một mảng làm 2 phần, sau đó so sánh và gộp 2 đường chạy tương ứng của 2 phần thành 1 đường chạy. Qúa trình trên lập lại nhiều lần, đến khi số đường chạy còn lại 1. DONE !.

Trở lại bài toán trên,ta thấy đó là bước lặp cuối cùng của thuật toán merge sort, ta đang có 2 đường chạy. Vậy chỉ cần so sánh các phần tương ứng của 2 mảng trên và ra được một danh sách phần tử giao giữa 2 mảng đã được sắp xếp !.

Tư duy lập trình 1: Bài toán này chỉ yêu cầu ta xác định  median nên  ta chỉ cần số cặp số so sánh bằng với kích thước n của mỗi mảng cộng thêm 1 là được.

Full Python code:

Time complexity: O(n)

Tư duy giải thuật 2: "Chia để trị" trung vị trong một mảng phần tử đã được sắp xếp thì ngoài mang ý nghĩa là vị trí đứng giữa và còn là vị trí giúp ta chia được danh sách thành 2 phần lớn và bé.

Vậy nếu như một mảng muốn chia thành 3 phần thì cần 2 trung vị ( trong trường hợp này thì dùng từ trung vị không đúng nhưng cứ tạm gọi là vậy ).

Ý tưởng của bài toán đã hình thành, quan sát hình sau:

Giả sử ta có 2 mảng sau ( đã được sắp xếp tăng dần):

ar1=[a1  ,  b1  ,  c1  ,  d1  , e1]      và       ar2 = [ a2 , b2  ,  c2 ,  d2  , e3]

Ta có media của mảng 1: m1=c1 và mảng 2: m2=c2

Nếu m2 > m1 thì rõ ràng a1 và b1 chắc chắn bé hơn c2 và cộng với việc cả 2 phần tử này theo đề bài đã nhỏ hơn c1 nên sẽ nằm phía ngoài cùng bên trái của mảng sau khi giao giữa 2 ar1 và ar2. Và hơn thế nữa d2 và e2 chắc chắn lớn hơn c1 và theo đề bài lớn hơn cả c2 nên chúng sẽ nằm ngoài cùng bên phải của mảng sau khi giao giữa hai mảng.

Vậy là rõ ràng median mà ta đang tìm kiếm sẽ phải phụ thuộc vào 2 mảng con sau:[d1,e1] và [a2,b2]

khi kích thước mỗi con là 2 thì ta dừng việc "chia"

median cần tìm dễ dàng tìm thấy được =(min(ar1[0],ar2[0] + max(ar1[1],ar2[1])) /2

Lý luận tương tự cho trường hợp m1>m2

Nội dung giải thuật:

1.       Tính toán m1 và m2

2.       Nếu m1 và m2 bằng nhau à return m1 or m2

3.       Nếu m1 lớn hơn m2, median được tìm thấy dựa vào 2 mảng con sau:

·         Từ phần tử đầu tiên của ar1 đến m1

·         Từ m2 đến phần tử cuối cùng của ar2

4.       Nếu m2 lớn hơn m1, median được tìm thấy dựa vào 2 mảng con sau:

·         Từ m1 đến phần tử cuối cùng của mảng ar1

·         Từ phần tử đầu tiên của ar2 đến m2

5.       Nhắc lại quá trình trên cho đến khi kích thước của 2 mảng thành 2

6.       Nếu kích thước của 2 mảng là 2 thì áp dụng công thức sau để tìm median:

Median=(max(ar1[0],ar2[0]) + min(ar1[1]+ar2[1]))/2

Tư duy lập trình: dùng đệ quy để ứng dụng giải thuật trên !

C code:

Time complexity: O(logn)

Kết luận: Rõ ràng chi phí dành cho giải thuật 2 là ít hơn là giải thuật 1. Tuy nhiên giải thuật 2 implement phức tạp hơn giải thuật 1.

The end !

Mong nhận sự đóng góp của các bạn.

Edit by me _BNT

Tham khảo đề bài: geeksforgeeks

Đọc tiếp »

C/Cplusplus NOTES FOR PROFESSIONALS

-------------------------- Tổng hợp những NOTE về ngôn ngữ lập trình C và C++---------------------

+++++++++++++++ Link download:Nhấp vào đây để tải tài liệu

Đọc tiếp »

ALGORITHMS NOTES FOR PROFESSIONALS

----------Những NOTE quan trọng về thuật toán cần nắm---------


Link:https://drive.google.com/file/d/1Hxnq1LyJ5jZLATd9tyoZT0OCKCZQhdZt/view?ts=5adcaac2

Đọc tiếp »

MAXIMUM DRAWS

PROBLEM: Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

SOLUTION:
- Đầu tiên ta cần quan tâm đến nguyên tắc Pigeonhole. Có thể phát biểu nguyên tắc này qua ví dụ:

Nếu chúng ta đặt N con chim bồ câu vào M thùng container, với N>M ( Khi N=M+1 thì có một một container chứa 2 con chim bồ câu ) thì chắc chắn sẽ có ít nhất một thùng phải chứa hơn một con chim bồ câu.

Quay trở lại vấn đề trên, theo đề bài ta giả sử có N đôi vớ ( mỗi đôi 2 chiếc vớ ) trong ngăn tủ của Jim ( các đôi vớ có màu khác nhau). Áp dụng nguyên tắc trên ta thấy rằng trường hợp xấu nhất tức số lượng chiếc vớ mà Jim phải rút lớn nhất đến khi tìm được 2 chiếc vớ cùng màu là N+1. Mỗi chiếc vớ tương ứng với 1 con chim bồ câu trên và ta có N màu khác nhau tức tương ứng có N container khác nhau.

FULL CODE:

Với t là số trường hợp ta test, n là số lượng đôi vớ.

Edited by Bùi Ngọc Tài

Đọc tiếp »

FIND THE POINTS

PROBLEM: Consider two points,p=(Px,Py)  and q=(Qx,Qy) . We consider the inversion or point reflection,r=(Qx,Qy) , of point p across point q to be a  rotation of point p around q .

SOLUTION:
Trong mặt phẳng tọa độ Oxy. Theo đề bài, Q sẽ là trung điểm của P và P'.
Tính chất: (xP+xP')/2=xQ và  (yP+yP')/2=yQ.

Áp dụng tính chất trên ta dễ dàng tìm được tọa độ điểm P' khi đã biết vị trí 2 điểm còn lại trong không gian Oxy.

FULL CODE:



Time complexity: O(1).

Edited bye me.

Đọc tiếp »

Bitwise Hacks for Competitive Programming

1.Làm sao để set một bit trong số " num":
- Nếu chúng ta muốn set một bit tại một vị trí n trong số num, chúng ta có thể dùng toán tử OR ( | )
- Đầu tiên , chúng ta dịch trái số 1 với số bit dịch là n: 1<<n.
- Sau đó sử dụng toán tử OR tại vị trí n. Sở dĩ toán tử OR được dùng vì nó set một bit mà không quan tâm đến giá trị của từng bit trong dãy nhị phân của số " num ".

num=0100, set bit 1 tại vị trí 1 ( pos=1 ) . Tưởng tượng num giống như mảng, tức set bit 1 tại vị trí num[1], sau khi set sau num=0110 tức bằng 6.

2) Làm sao để unset/clear một bit tại vị trí n trong số " num "

- Gỉa sử rằng chúng ta muốn unset một bit tại vị trí n trong số " num" do đó chúng ta phải nhờ sự giúp  của toán tử AND ( &).

- Đầu tiên chúng ta dịch trái số 1 với n bit dịch hơn nữa cũng dùng toán tử NOT (~) để unset kết quả của shifted "1 ".

- Sau khi clear sau xong kết quả của shifted " 1", ta thực hiện nó với số " num " bằng toán tử AND (&).

num=0111, kết quả của 1<<pos là 1110, sau khi thực hiện toán tử NOT ta được 0001, thực hiện AND với num ta được 01110.Vậy là với pos=1, ta đã thực hiện xong unset.

3) Toggling một bit tại vị trí n:

- Toggling có nghĩa là nếu bit tại trí n đang là có giá trị là 0 thì sẽ turn lên 1 và ngược lại. Sử dụng toán tử XOR. Do đặc điểm của XOR giữa 2 bit luôn cho kết quả 0 nếu 2 bit có cùng giá trị.

num=0100, kết hợp với (1<<pos=0010) bằng toán tử XOR ( ^ ), ta được 0110.ở đây ta xem num như mảng và Toggling tại pos=1 thì xem như tại num[1].

4) kiểm tra xem tại vị trí n đang là set hay unset:

num=0101 và 1<<pos=0001. Kết quả khi thực hiện toán tử AND=0001, dùng kiểu bool nên bit=1. Xem num như mảng, tức kết quả có được cho thấy tại  num[0], giá trị bit đang set.

5) Stripping off the lowest set bit ( Loại bỏ bit thấp nhấp được set lên 1 )

Ở ví dụ trên num=7=0111, ta mong muốn loại bỏ bit được set lên 1 cuối cùng, ta lấy 7-1=6=0110, sau đó AND num, ta được 0110.
xét ví dụ với num=14=1110, một cách diễn đạt khác, phép tính num-1=14-1=1101 có thể được diễn giải theo thao tác trên bit như sau: xét từ bit trái của numsang phải, nếu gặp bit được set lên 1 cuối cùng thì đảo lại thành bit 0 và kể từ đó, đảo tất các bit sau bit cuối cùng được set lên 1, tức ta sẽ được kết quả 1101=13, thực hiện AND với num ta đã hoàn thành việc loại bỏ bit cuối cùng được set lên 1.

6)Getting lowest set bit of a number( lấy bit được set thấp nhất)

Ta thấy num=10=1010, ta mong muốn get bit được set cuối cùng, tức mong muốn đạt được kết quả là 0010. Đầu tiên đảo số num thành số âm bằng 2 cách:
+ Dùng 1's complement( biến num thành số bù 1)+ 2's complement(+1 để thành số bù 2) tức phép toán ~num+1
+ Dùng - num.
Ta thực hiện 1  trong 2 cách trên, sau đó lấy kết quả trên AND với num ta được kết quả mong muốn ban đầu là 0010.


Tham khảo: geeksforgeeks
Edited by me " NÓI THẬT, LÀM THẬT ! "

Đọc tiếp »

INTERESTING FACTS ABOUT BITWISE OPERATOR IN C

Trong ngôn ngữ C, có 6 toán tử xử lý trên bit, Các phép toán xử lý trên bit:

& ( AND ): lấy 2 số như toán hạng thực hiện phép AND trên mỗi bit tương ứng của 2 số.Kết quả từng phép xử lý trên cặp bit bằng 1 nếu cả 2 đều là 1.

| ( OR ):Tương tự trả về 1 nếu một trong 2 bit bằng 1.

^ ( XOR ): Trả về 1 nếu 2 bit khác nhau.

~ ( NOT ): Đảo ngược tất cả các bit.

<< (Dịch trái): Dịch trái số bit n của toán hạng đầu tiên. Toán hạng thứ 2 quy định số n bit dịch.

>>(Dịch phải): Dịch phải số bit n của toán hạng đầu tiên. Toán hạng thứ 2 quy định số n bit dịch.

! NOTE:

• Toán tử dịch trái và dịch phải không dùng cho số âm (negative numbers):

-Kết quả không được xác định nếu có bất cứ toán hạng nào negative numbers.
Vd: -1<<1 hay 1<<-1.

-Tương tự số lượng bit dịch nếu vượt quá size of integer thì không thể xác định được kết quả.
Vd: 1<<33.

• Toán tử XOR thì được sử dụng phổ biến trong các cuộc phỏng vấn kỹ thuật.

-Nó thì được dùng  để giải quyết nhiều vấn đề.
Xét ví dụ sau: cho một danh sách các số mà ở đó tất các số đều có tần xuất xuất hiện chẵn ngoại trừ một số. Hãy tìm giá trị của số có số lần xuất hiện lẻ.

Mình tâm đắc nhất đối với chức năng đặc biệt này của XOR. Great !

• Những toán tử xử lý trên bit không nên được dùng trong cùng vị trí với toán tử logic.

- Kết quả của một logical operator  ( &&, || và !) là 1 hoặc 0. Nhưng kết quả trả về của toán tử bit là một giá trị kiểu integer. Toán tử logic chỉ trả về là 0 (false) hoặc 1 (true). Các toán hạng thực hiện toán tử logic,  nếu là số 0 thì nó xem là false và tất cả các số khác 0 xem là true. Xem ví dụ bên dưới:

• Toán tử dịch trái và dịch phải tương đương với với phép nhân và phép chia.

-Ở chú ý đầu tiên, ta đã nói 2 toán tử trên chỉ làm việc với số dương (positive numbers)

-Dịch trái tương ứng với phép nhân ( 19*2=38 ) và dịch phải tương ứng với phép chia (19/2=9).

• Toán tử & có thể được dùng để kiểm tra nhanh là số chẵn hay lẻ.

Gía trị trả về của phép toán x & 1 là khác 0 nếu như x là số lẻ, nếu chẵn thì là 0.

• Toán tử ~ nên được sử dụng một cách cẩn thận

Kết quả khi thực hiện toán tử t ~ trên số nhỏ có thể cho ra kết quả một số lớn nếu kết quả được lưu với kiểu dữ liệu không dấu.Và có thể thành số âm nếu được lưu với kiểu dữ liệu có dấu.

ÁP DỤNG: bài toán LARGEST PRIME FACTOR ta sẽ thay việc check tính chia hết và thực hiện phép chia cho 2 bằng cách áp dụng toán tử dịch bit sang phải. Gíup chương trình nhanh hơn, do số lần lập của bài này vẫn còn ít nên mình không thể đo được time chạy của thuật toán để thấy được khác biệt.

Tham khảo: geeksforgeeks.

Edited by me.

Đọc tiếp »

LARGEST PRIME FACTOR

PROBLEM: The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

SOLUTION: Bài này thuật toán cũng khá đơn giản ( Có lẽ sẽ có thuật toán tối ưu hơn, mong bạn đọc góp ý), cái khó duy nhất có lẽ làm sao để lưu trữ một số quá khủng như vậy (600851475143). Đầu tiên ta xem qua các kiểu dữ liệu quen thuộc:

Rõ ràng các KDL trên không thể lưu trữ con số trên, ta dùng thư viện inttypes.h hoặc cstdint.

FULL CODE:

! NOte: Cách xuất con số kiểu int64_t hay  uint64_t.

printf("%d" PRId64"\n",t);

printf("%d" PRIu64"\n",t);


với t là tên biến.

Mong bạn đọc góp ý ! Xin cảm ơn.

EDITED BY ME " NÓI THẬT,  LÀM THẬT !"

Đọc tiếp »

EVEN FIBONACCI NUMBERS

PROBLEM: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

SOLUTION: Giải pháp của mình dùng khá nhiều biến. 3 biến pre_1, pre_2 và term để lần lượt lưu 3 giá trị đó là số fibonacci và 2 số phía trước nó. Mỗi vòng lặp là 3 biến này được cập nhật giá trị mới.

FULL CODE:

Mong nhận được sự góp ý từ bạn đọc !

Edited by me.

Đọc tiếp »

MULTILES OF 3 AND 5

PROBLEM: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

SOLUTION:

+Bài toán thì rất đơn giản thôi nhưng chỉ cần chú ý nếu một số đồng thời là bội của 2 số 3 và 5 thì biến result chỉ cộng một lần.

vdL: 15 là bội của 3 và 5, trong quá trình xét duyệt, biến result sẽ cộng 2 lần số  15, ta sẽ trừ bớt đi 15 trong điều kiện if cuối.

! Đoạn code từ dòng 8-17 có thể thay bằng if (!((i%3)||(i%5)) ( góp ý bởi anh Nguyễn Hoàng Phúc ).

By me.

Đọc tiếp »

VÀI ĐIỀU CÓ THỂ BẠN CHƯA BIẾT VỀ ĐẤT NƯỚC QATAR

Qatar, đối thủ của Việt Nam trong trận bán kết U23 châu Á ngày mai là một đất nước có nhiều điều kỳ lạ.

Theo công bố, dân số Qatar khoảng 2,7 triệu người, nhưng dân bản địa có quốc tịch Qatar chỉ khoảng 313.000 người, chiếm 11,5% dân số. Số dân nhập cư nước ngoài làm việc ở Qatar cỡ 2,4 triệu người, riêng số dân Ấn Độ nhập cư đã lên đến 650.000 người, nhiều gấp 2 lần dân Qatar bản địa.
Qatar là một trong số những quốc gia giàu có nhất thế giới. Thế nhưng thu nhập của dân nhập cư rất thấp, công nhân Ấn Độ thu nhập chỉ cỡ 650$ người tháng, trong khi đó thu nhập trung bình của một công chức nhà nước Qatar lên đến 400.000$ người năm.



Chính vì vậy rất khó nói chính xác GDP đầu người của Qatar là bao nhiêu. Với tổng GDP quốc gia cỡ 180 tỷ USD, nếu chia cho số dân 2,7 triệu thì GDP đầu người cỡ 65.000$, nhưng nếu chỉ chia cho 313.000 công dân Qatar thì GDP đầu người lên đến hơn 500.000$. Vì vậy có thể nói Qatar là quốc gia giàu có nhất trên thế giới.

Vì giàu có, Qatar có quĩ đầu tư lên đến trên 500 tỷ USD. Qatar đầu tư ở Mỹ, châu Âu, châu Á Thái Bình Dương và trở thành quốc gia đầu tư lớn nhất ở London.
Người dân Qatar bản địa được chế độ phúc lợi đặc biệt ưu đãi: giáo dục miễn phí, y tế, khám chữa bệnh, chăm sóc sức khỏe miễn phí, tiền điện, tiền nước miễn phí, trợ cấp nhà ở, đảm bảo việc làm, miễn thuế thu nhập và các loại thuế.

Thế nhưng Qatar lại bị mất cân bằng giới tính nghiêm trọng. Trong tổng số 2,7 triệu dân, phụ nữ chỉ có 700.000 người, nghĩa là cứ 3 đàn ông mới có 1 phụ nữ. Lý do là dân nhập cư đa số là đàn ông trẻ.
Dù Qatar có giàu có nhất thế giới, dù Qatar có tỷ lệ đàn ông chiếm đến 74% dân số, dù cầu thủ Qatar có thể hình, thể lực vượt trội, dù Qatar đã từng vô địch châu Á thì nhất định ngày mai U23 Việt Nam sẽ thắng.

Source: Đỗ Cao Bảo.

Đọc tiếp »

XU HƯỚNG CHIẾN LƯỢC CÔNG NGHỆ HÀNG ĐẦU TRONG NĂM 2018

1. Trí tuệ nhân tạo (AI)
Trí tuệ nhân tạo (AI) đang là chìa khóa giải quyết rất nhiều vấn đề của đời sống. Hiện nay trí tuệ nhân tạo đang được nghiên cứu và ứng dụng để giải quyết các bài toán rất cụ thể, xu hướng này được gọi là “Narrow AI“. Ví dụ như nhận dạng biển số xe, nhận dạng mặt người, chuyển đổi từ tiếng nói ra văn bản,…

Narrow AI có thể giúp phân biệt " gay " hoặc " thẳng " chính xác 70 % - 80 %

Trong tương lai từ 2025 công nghệ AI sẽ chuyển sang nghiên cứu “General AI” – Những thiết bị hoàn hảo có tất cả các giác quan của con người (có thể nhiều hơn), có khả năng suy đoán, suy nghĩ như chúng ta. Trong General AI, các bài toán AI về âm thanh, hình ảnh, cảm biến,… sẽ được kết hợp để máy móc có thể hiểu về các ngữ cảnh thực tế và tự đưa ra quyết định. Đặc biệt là khả năng học đa dạng sẽ được mở rộng chứ không trong các phạm vi hẹp như ngày nay.
Hiện nay những gì chúng ta đang thấy rơi vào khái niệm “Narrow AI“. Các công nghệ có khả năng thực hiện các nhiệm vụ cụ thể tương đương, hoặc tốt hơn con người có thể làm. Ví dụ như phân loại hình ảnh trên một dịch vụ như Pinterest và nhận dạng khuôn mặt trên Facebook. Đó là những ví dụ về Narrow AI trong thực tế.

2. Hệ thống ứng dụng thông minh dựa vào phân tích hành vi người dùng
Trong vài năm tới, hầu như mọi ứng dụng và dịch vụ sẽ kết hợp với trí tuệ nhân tạo tùy theo mức độ. Các ứng dụng thông minh tạo ra một lớp trung gian thông minh mới giữa con người và các hệ thống. Các sản phẩm công nghệ mới hiện nay đều ứng dụng phân tích các dữ liệu của người dùng để đưa ra những trải nghiệm khác nhau đối với mỗi người dùng. Ví dụ: đọc một bài báo tuỳ theo sở thích của bạn ứng dụng sẽ gợi ý các bài viết phù hợp mà không phải tìm, quảng cáo google hay facebook đều dựa vào thông tin phân tích của người dùng để quảng cáo cho phù hợp, giáo dục dùng việc phân tích học viên để đưa ra những chương trình phù hợp với mỗi bài giảng.



3. Thiết bị thông minh
Ngày nay các thiết bị gia dụng văn phòng hay nhà máy bắt đầu trở nên thông minh và tự ra quyết định hoặc hỗ trợ con người tốt hơn. Những thiết bị này có các cảm biến, có mạng để thông báo và lưu trữ dự liệu cũng như các thuật toán để ra quyết định. Ví dụ các camera thông minh có khả năng phát hiện lúc nào có người, lúc nào có dấu hiệu bất thường và thông báo tới người dùng ngay lập tức; điều khiển thông minh tự học môi nhiệt độ môi trường và đưa ra lệnh điều khiển phù hợp theo thói quen của người dùng (Google Nest); xe tự hành tự đi trong nhà máy dùng camera và các cảm biến để tự ra quyết định đi trong một môi trường nhất định …
Các sản phẩm về IoT liên tục phát triển trong nhiều lĩnh vực như smart home, smart TV hay những hệ thống chăm sóc cây trồng tự động hoặc thậm chí là những giải pháp khám chữa bệnh tân tiến đòi hỏi độ chính xác cao.


4. Digital Twin
Digital Twin là mô hình phần mềm của một thiết bị vật lý hoặc một hệ thống, dựa trên các dữ liệu cảm biến để hiểu trạng thái của thiết bị hay hệ thống, đồng thời có thể điều chỉnh, cải thiện hoạt động và gia tăng giá trị.
Khi một chiếc máy bay cất cánh, vận tốc, sức gió, mức nhiên liệu, nhiệt độ, độ cao… đều được ghi lại theo thời gian thực. Lúc này có thể nói digital twin của máy bay cũng đang “sống” và đang “bay“. Digital twin còn có thể áp dụng cho con người. Giả sử bạn có một chiếc vòng đeo tay có thể thu thập huyết áp, nhịp tim. Khi bạn làm việc quá nhiều, huyết áp lên cao, bạn sẽ được một hệ thống y tế tự động cảnh báo. Với những dữ liệu này, có thể cảnh báo sớm khi một người có sức khỏe không bình thường, hạn chế tình trạng bệnh đã phát ra mới phát hiện.

Đến năm 2020, ước tính có hơn 21 tỷ cảm biến và thiết bị đầu cuối được kết nối và sẽ có hàng tỷ digital twin cho các thiết bị vật lý. Digital twin có tác dụng tối ưu hóa tài sản và cải thiện trải nghiệm người dùng hầu như ở tất cả ngành công nghiệp như: Sửa chữa thiết bị và lên kế hoạch bảo dưỡng; dự đoán hỏng hóc thiết bị hoặc tăng hiệu quả hoạt động; lên quy trình sản xuất; vận hành các nhà máy… Các thiết bị được mô phỏng, có thể đưa ra chạy thử nghiệm và giả lập hoàn toàn trên máy tính, cloud trước khi ứng dụng thực tế. Trong nhà máy các bài toán AI rất khó triển khai nếu không được thử nghiệm. Các mô hình bản sao trên cloud giúp các kỹ sư có thể thử nghiệm mà không gây ra ảnh hưởng tới hệ thống. Đây chính là công nghệ đang được nghiên cứu cho các bài toán nhà máy thông minh. Hiện nay các công ty lớn đang thu thập dữ liệu và xây dựng các mô hình mô phỏng các thiết bị các nhà máy.

5. Cloud to the Edge
Mạng internet là thứ gây ra khó triển khai thiết bị thông minh. Xu hướng tạo ra những thiết bị tại chỗ thông minh có khả năng xử lý dữ liệu. Các mô hình học máy sẽ được đưa xuống và xử lý các bài toán ở mức cơ bản. Ví dụ: loa thông minh có khả năng nhận dạng những câu hỏi thông thường,  gọi ngay tại thiết bị….

6. Nền tảng hội thoại
Nền tảng hội thoại hay còn gọi là là hệ thống chatbot. Một nền tảng hội thoại đầy đủ bao gồm: Nhận dạng tiếng nói, tổng hợp tiếng (từ văn bản ra tiếng nói) và xử lý ngôn ngữ từ các đoạn hội thoại.
Trong những năm gần đây, các nhà đầu tư mạo hiểm đã dành hàng triệu đô la đầu tư vào lĩnh vực tiềm năng bot. Điều này thể hiện bởi những thương vụ đầu tư liên tiếp trong thời gian gần đây. Có thể kể ra một vài cái tên như:

• X.ai hoạt động như một trợ lý cá nhân có thể sắp xếp cuộc họp qua email.

•  MagicX.có một nền tảng trí tuệ nhân tạo, giúp con người trong một số việc hàng ngày. 

• Angel.ai (trước đây là GoButler) – trợ lý giúp trong hỗ trợ trong tìm chuyến bay.
•  Poncho: chatbot dự báo thời tiết cá nhân hóa.
•  Digit: bot giúp người dùng quản lý chi tiêu. 
• Growbot: bot dùng để đưa ra những nhận xét, động viên đồng nghiệp… 
• Các ứng dụng chăm sóc khách hàng qua facebook, loa thông minh như Alexa, google home,… các nền tảng hỗ trợ phát triển như wit.ai hay fpt.ai cho tiếng Việt…

Với rất nhiều những ứng dụng của chatbot trong đời sống, có thể nói chatbot là một nhân tố quan trọng trong tiến tới một thế giới số, nơi mà máy móc trở nên thông minh và hiểu con người hơn. Cho dù các ứng dụng vẫn còn hạn chế trên một số lĩnh vực nhất định, tuy nhiên chắc chắn vai trò của chatbot sẽ ngày càng tăng cao, với nhiều ứng dụng hơn vào các bài toán trong thực tiễn đời sống.

7. VR, AR và MR
Kết quả hình ảnh cho xu hướng và chiến lược công nghệ nổi bật trong năm 2017.Trong cuộc cách mạng 4.0, thực tế ảo (VR – Virtual reality), thực tế tăng cường (AR – Augmented Reality) và MR (Mixed Reality) không nắm vai trò chủ chốt nhưng hỗ trợ quan trọng cho việc phát triển các ứng dụng, không chỉ đơn giản là những ứng dụng cho người dùng thông thường, mà còn hỗ trợ cho việc sản xuất.

VR

AR

MR

Điểm nổi bật của công nghệ này là tạo ra môi trường ảo một cách rất thật. Qua đó giúp tái hiện được được những thứ đã có, hoặc trình diễn ra những thứ sẽ dự kiến sản xuất. Việc tạo ra một môi trường ảo giúp con người có thể gặp gỡ, làm việc, trao đổi trực tiếp ở mọi nơi trên thế giới. Việc sản xuất sẽ trở nên thuận tiện hơn rất nhiều nếu như nhìn vào máy móc, thiết bị nào cũng có thể thấy được đầy đủ các thông tin chi tiết, trạng thái ra sao, cần phải nâng cấp như thế nào….
Hiện nay VR, AR và MR được ứng dụng nhiều trong giáo dục, nhà máy và đặc biệt là trong lĩnh vực trò chơi giả lập. Các hãng công nghệ liên tục ra các platform AR KIT (iOS), AR Core (android), các sản phẩm AR,VR như HoloLen, Vive HTC, Samsung Gear,…

8. Blockchain
Kết quả hình ảnh cho xu hướng và chiến lược công nghệ nổi bật trong năm 2017.Những ngày này, có lẽ bitcoin chính là một trong những chủ đề “hot” nhất trên thị trường tài chính quốc tế. Nhưng không phải ai cũng biết công nghệ phía sau của đồng tiền ảo đang làm mưa làm gió – Blockchain. Công nghệ này đảm bảo cho chúng ta một phương thức xác thực phân tán, nhiều bên dựa vào các chuỗi số duy nhất được sinh ra. Nó được ứng dụng trong tiền ảo, hợp đồng ảo, phân quyền các thiết bị IoT public…

Blockchain thường được ví như một cuốn sổ cái số công khai mà bất cứ ai cũng có thể truy cập vào và kiểm tra nhưng không ai có thể toàn quyền kiểm soát nó. Các thành viên tham gia hệ thống blockchain đều đặn cập nhật thông tin trên sổ cái, nhưng các biện pháp kỹ thuật đảm bảo họ chỉ có thể sửa đổi thông tin khi đã tuân theo những quy tắc hết sức nghiêm ngặt. Trong công nghệ blockchain của bitcoin, các giao dịch được cập nhật liên tục theo thời gian thực và tránh được việc ghi trùng hai lần.

Công nghệ blockchain đang có tác động đến nhiều ngành. Công ty quản lý tài sản Everledger đã đăng ký thông tin cho hơn một triệu viên kim cương để theo dõi chúng tốt hơn bằng công nghệ blockchain.

Maersk – công ty vận tải biển lớn nhất thế giới – vừa qua đã hoàn tất việc thử nghiệm ứng dụng blockchain vào theo dõi hàng hóa.

Các ngân hàng muốn áp dụng blockchain để giảm thiểu bộ máy quản lý các giao dịch chuyển tiền hay đầu tư hiện đang cồng kềnh và thiếu chính xác. Có thể thấy công nghệ blockchain đang dần hoàn thiện và âm thầm len lỏi vào mọi mặt của đời sống.

9. Event-Driven Model
Mọi doanh nghiệp đều muốn kiểm soát được các “event” của mình. Mỗi sự kiện đều ảnh hưởng tới doanh thu và hoạt động của doanh nghiệp. Sự kiện kinh doanh có thể là bất cứ điều gì được lưu trữ bằng kỹ thuật số, phản ánh việc khám phá các tình huống đáng chú ý hoặc thay đổi trạng thái, ví dụ như hoàn thành đơn đặt hàng hoặc cho máy bay hạ cánh. Với việc sử dụng IoT, điện toán đám mây, blockchain, quản lý dữ liệu trên bộ nhớ và AI, các sự kiện kinh doanh có thể được phát hiện nhanh hơn và phân tích chi tiết hơn. Mỗi trạng thái hợp đồng triển khai hay sản xuất đều được cập nhật liên tục để hỗ trợ các quản lý đưa ra quyết định hoặc để khách hàng theo dõi. Nhưng nếu công nghệ độc lập mà không có sự thay đổi phù hợp về văn hoá và luật phát từng quốc gia, khu vực thì không mang lại giá trị đầy đủ của mô hình.

10. Kiểm soát rủi ro, đảm bảo an toàn an ninh mạng
Kiểm soát được rủi ro đảm bảo an toàn an ninh mạng là một nhiệm vụ rất quan trọng cho các doanh nghiệp số. Vào năm 2009, một phần mềm độc hại thao túng tốc độ của máy ly tâm trong một nhà máy hạt nhân, khiến chúng bị mất kiểm soát. Phần mềm độc hại này, được biết đến như Stuxnet, đã di chuyển vào các mạng độc lập thông qua các ổ đĩa flash, và tự phân tán trên các mạng lưới sản xuất. Sự phức tạp của Stuxnet là một ví dụ mạnh mẽ về tiềm năng tấn công mạng, như một vũ khí trong thế giới của các nhà máy sản xuất vật lý được kết nối.
Ngoài ra trong thời gian gần đây, sự xuất hiện của mã độc Wanna Cry cũng đã nói lên phần nào về những rủi ro đe dọa đến tình hình hoạt động của doanh nghiệp. Sự gia tăng tính kết nối của máy móc thông minh đã góp phần làm gia tăng rủi ro. Công nghiệp 4.0 báo hiệu một thời đại mới về sản xuất thông minh, kết nối, các mạng lưới cung ứng phản hồi nhanh, các sản phẩm và dịch vụ phù hợp.
Khi dây chuyền cung ứng, nhà máy, khách hàng và các hoạt động vận hành được kết nối, rủi ro gây ra bởi các cuộc tấn công mạng trở nên dữ dội hơn và trở nên ngoài tầm kiểm soát. Sự an toàn của các doanh nghiệp sẽ trở thành một phần không thể tách rời của chiến lược, thiết kế, và hoạt động vận hành, được xem xét từ khi bắt đầu bất kỳ sáng kiến mới nào của ngành Công nghiệp 4.0.

SOURCE tham khảo: Gartner Top 10 StrategicTechnology Trends for 2018+ HOÀNG NAM TIẾN ( fpt software )

Đọc tiếp »