Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!
Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.
Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.
Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.
Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.
H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.

Cấu trúc dữ liệu và Giải thuật

Trong khi giải một b&agrave;i to&aacute;n, th&ocirc;ng thường ta chỉ ch&uacute; trọng đến thuật to&aacute;n (hay c&aacute;ch giải của b&agrave;i to&aacute;n) m&agrave; &iacute;t khi quan t&acirc;m đến việc tổ chức dữ liệu. Tuy nhi&ecirc;n, giữa việc tổ chức dữ liệu v&agrave; thuật to&aacute;n c&oacute; mối li&ecirc;n hệ chặt chẽ với nhau. Điều n&agrave;y đ&atilde; được n&oacute;i đến ngay ở b&agrave;i đầu ti&ecirc;n của kh&oacute;a học:
[___NOTE_
CHƯƠNG TR&Igrave;NH = THUẬT TO&Aacute;N + CẤU TR&Uacute;C DỮ LIỆU
Programs = Algorithms + Data structures
_NOTE___]
<h2 style="text-align: justify;">Mối li&ecirc;n hệ giữa cấu tr&uacute;c dữ liệu v&agrave; thuật to&aacute;n</h2>
Một thuật to&aacute;n bao giờ cũng thao t&aacute;c tr&ecirc;n một c&aacute;ch tổ chức dữ liệu (cấu tr&uacute;c dữ liệu) cụ thể v&agrave; c&aacute;c thao t&aacute;c phải được cấu tr&uacute;c dữ liệu đ&oacute; hỗ trợ.
Khi tổ chức dữ liệu cho b&agrave;i to&aacute;n thay đổi th&igrave; thuật to&aacute;n cũng phải thay đổi theo cho ph&ugrave; hợp với c&aacute;ch tổ chức dữ liệu mới. Ngược lại, trong qu&aacute; tr&igrave;nh x&acirc;y dựng, ho&agrave;n thiện thuật to&aacute;n cũng gợi mở cho người lập tr&igrave;nh c&aacute;ch tổ chức dữ liệu ph&ugrave; hợp với thuật to&aacute;n v&agrave; tiết kiệm t&agrave;i nguy&ecirc;n hệ thống. Chẳng hạn, d&ugrave;ng th&ecirc;m c&aacute;c &ocirc; nhớ phụ để lưu c&aacute;c kết quả trung gian v&agrave; giảm thời gian t&iacute;nh to&aacute;n.
Ch&uacute;ng ta c&oacute; thể thấy sự li&ecirc;n hệ n&agrave;y th&ocirc;ng qua một số v&iacute; dụ sau:
<h3 style="text-align: justify;">V&iacute; dụ 1. B&agrave;i to&aacute;n đổi gi&aacute; trị hai biến $x$, $y$.</h3>
Với b&agrave;i to&aacute;n n&agrave;y ta c&oacute; hai phương &aacute;n giải như sau:
Phương &aacute;n 1. D&ugrave;ng &ocirc; nhớ trung gian
<pre class="language-python3"><code>tmp = x
x = y
y = tmp</code></pre>
Phương &aacute;n 2. Kh&ocirc;ng d&ugrave;ng &ocirc; nhớ trung gian
<pre class="language-python3"><code>x = x + y
y = x - y
x = x - y</code></pre>
Qua v&iacute; dụ đơn giản n&agrave;y, ta nhận thấy việc tổ chức dữ liệu kh&aacute;c nhau (d&ugrave;ng hay kh&ocirc;ng d&ugrave;ng biến trung gian) ảnh hưởng rất lớn đến thuật to&aacute;n v&agrave; gần như thay đổi to&agrave;n bộ thuật to&aacute;n. Hơn nữa, n&oacute; c&ograve;n ảnh hưởng đến t&iacute;nh hiệu quả v&agrave; phạm vi ứng dụng của thuật to&aacute;n.
<h3 style="text-align: justify;">V&iacute; dụ 2. T&iacute;nh số tổ hợp chập $k$ của $n$ phần tử</h3>
Tương tự như b&agrave;i trước, ta cũng c&oacute; nhiều c&aacute;ch giải quyết b&agrave;i to&aacute;n n&agrave;y. Ở đ&acirc;y, ch&uacute;ng ta xem x&eacute;t 4 c&aacute;ch như sau:
Phương &aacute;n 1. D&ugrave;ng định nghĩa $C^{k}_{n} = \displaystyle\frac{n!}{k!(n-k)!}$. Giả sử <code>gt(n)</code> l&agrave; h&agrave;m trả về $n!$. Ta c&oacute; h&agrave;m t&iacute;nh hệ số $C^{k}_{n}$ như sau:
<pre class="language-c"><code>ToHop = gt(n)/gt(k)
ToHop = ToHop/gt(n-k)</code></pre>
C&oacute; thể thấy, với thuật to&aacute;n n&agrave;y, chương tr&igrave;nh chỉ t&iacute;nh được gi&aacute; trị của tổ hợp với c&aacute;c số $n$ v&agrave; $k$ kh&aacute; nhỏ v&igrave; phải lưu c&aacute;c kết quả trung gian rất lớn khi t&iacute;nh to&aacute;n l&agrave; $n!$, $k!$, v&agrave; $(n-k)!$.
Phương &aacute;n 2. D&ugrave;ng c&ocirc;ng thức $C^{k}_{n} = C^{k-1}_{n-1}+C^{k}_{n-1}$, với $C^{0}_{n}=1, C^{i}_{i}=1$. H&agrave;m t&iacute;nh $C^{k}_{n}$ được viết dưới dạng đệ quy như sau:
<pre class="language-python3"><code>Function ToHop(n, k)
 if (k = 0) or (k = n) then
 ToHop = 1
 else
 ToHop = ToHop(n-1, k-1) + ToHop(n-1, k)</code></pre>
Với thuật to&aacute;n n&agrave;y, ta đ&atilde; khắc phục được việc phải lưu trữ c&aacute;c gi&aacute; trị trung gian lớn. Tuy vậy, hạn chế của thuật to&aacute;n l&agrave; phải t&iacute;nh lại nhiều lần c&aacute;c gi&aacute; trị đ&atilde; t&iacute;nh ở c&aacute;c bước trước, chẳng hạn để t&iacute;nh $C^{3}_{5}$ thuật to&aacute;n phải lặp lại hai lần t&iacute;nh $C^{2}_{3}$, ba lần t&iacute;nh $C^{1}_{2}$...
Phương &aacute;n 3. D&ugrave;ng một mảng 2 chiều <code>C[n, k]</code> để lưu c&aacute;c kết quả trung gian trong khi t&iacute;nh $C^{k}_{n}$, với $C[i,j]=C^{j}_{i} (0\leq j\leq i, \ i\leq k, \ i\leq n).$ Từ c&ocirc;ng thức $C^{k}_{n}=C^{k-1}_{n-1}+C^{k}_{n-1}$, ta c&oacute; <code>C[i, j] = C[i-1, j-1] + C[i-1, j]</code>. Do đ&oacute;, ta c&oacute; thuật to&aacute;n cụ thể như sau:
<pre class="language-python3"><code>Function ToHop(n, k)
 C[n, k] = 0
 for i = 1 to n do C[i, 0] = 1
 for j = 1 to k do
 C[i, j] = 1
 for i = j+1 to n do
 C[i, j] = C[i-1, j-1] + C[i-1, j]
 ToHop = C[n, k]</code></pre>
Phương &aacute;n n&agrave;y c&ograve;n nhiều &ocirc; nhớ của mảng kh&ocirc;ng được sử dụng, cụ thể l&agrave; c&aacute;c phần ở ph&iacute;a tr&ecirc;n đường ch&eacute;o ch&iacute;nh. V&igrave; mục đ&iacute;ch của b&agrave;i to&aacute;n chỉ l&agrave; t&iacute;nh gi&aacute; trị $C^{k}_{n}$ m&agrave; kh&ocirc;ng cần gi&aacute; trị trung gian n&ecirc;n ta c&oacute; thể tổ chức bộ nhớ tiết kiệm hơn bằng c&aacute;ch sử dụng mảng một chiều như sau:
Phương &aacute;n 4. Sử dụng mảng một chiều <code>A[k]</code> để lưu c&aacute;c gi&aacute; trị của từng d&ograve;ng trong mảng <code>C</code> của phương &aacute;n tr&ecirc;n. Mảng <code>A</code> được t&iacute;nh qua <code>n</code> bước, tại bước thứ <code>i</code>, <code>A</code> l&agrave; d&ograve;ng thứ <code>i</code> của mảng <code>C</code>, cụ thể tại bước thứ <code>i</code>, $A[j]=C^{j}_{i}$, với $j\leq i$
<pre class="language-python3"><code>Function ToHop(n, k)
 var A[k]
 for i = 1 to k do A[i] = 0
 A[0] = 1
 for j = 1 to n do
 for i = k downto 1 do
 A[i] = A[i] + A[i-1]
 HeSo = A[k]</code></pre>
Với phương &aacute;n n&agrave;y vừa tiết kiệm được bộ nhớ vừa tăng khả năng t&iacute;nh to&aacute;n đối với c&aacute;c số $n, k$ lớn hơn so với c&aacute;c phương &aacute;n kh&aacute;c.
Như vậy, c&oacute; thể thấy rằng cấu tr&uacute;c dữ liệu m&agrave; ta chọn sẽ c&oacute; mối tương quan chặt chẽ với thuật to&aacute;n m&agrave; ch&uacute;ng ta sử dụng để giải quyết b&agrave;i to&aacute;n. Việc giải b&agrave;i to&aacute;n l&agrave; việc ch&uacute;ng ta sẽ cố gắng t&igrave;m ra phương &aacute;n tốt nhất cho việc sử dụng c&aacute;c cấu tr&uacute;c dữ liệu v&agrave; thuật to&aacute;n ph&ugrave; hợp nhất để tăng t&iacute;nh hiệu quả cho việc sử dụng c&aacute;c t&agrave;i nguy&ecirc;n m&aacute;y t&iacute;nh. Trong b&agrave;i sau, ch&uacute;ng ta sẽ đi chi tiết h&oacute;a phương ph&aacute;p l&iacute; luận để t&igrave;m ra lời giải tối ưu nhất cho mỗi b&agrave;i to&aacute;n.
[___QUESTION_H&atilde;y thử tự ph&acirc;n t&iacute;ch xem c&aacute;c phương &aacute;n giải quyết cho c&aacute;c b&agrave;i to&aacute;n tr&ecirc;n c&oacute; độ phức tạp kh&ocirc;ng gian v&agrave; thời gian l&agrave; bao nhi&ecirc;u nh&eacute;!!! V&agrave; h&atilde;y để lại c&acirc;u trả lời ở phần thảo luận để mọi người c&ugrave;ng trao đổi._QUESTION___]
Tiếp theo, trước khi sang một nội dung đặc biệt quan trọng trong kh&oacute;a học n&agrave;y, đ&oacute; l&agrave; c&aacute;ch thức để ph&acirc;n t&iacute;ch v&agrave; giải quyết b&agrave;i to&aacute;n th&igrave; ch&uacute;ng ta h&atilde;y thử sức với việc triển khai thuật to&aacute;n t&iacute;nh tổ hợp ở tr&ecirc;n với ng&ocirc;n ngữ lập tr&igrave;nh m&agrave; bạn cảm thấy th&agrave;nh thạo nhất qua b&agrave;i tập sau đ&acirc;y.

Ví dụ về mối liên hệ giữa cấu trúc dữ liệu và thuật toán