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

Hệ mật Affine l&agrave; một mật m&atilde; kh&oacute;a đối xứng cổ điển. Mỗi k&yacute; tự của của văn bản gốc được &aacute;nh xạ đến một k&iacute; tự duy nhất. Khi gộp c&aacute;c k&yacute; tự được &aacute;nh xạ ch&uacute;ng ta thu được văn bản m&atilde; h&oacute;a hay c&ograve;n gọi l&agrave; bản m&atilde;.
Mỗi k&yacute; tự trong bảng chữ c&aacute;i sẽ được hiển dưới dạng m&atilde; số tương ứng như l&agrave;:
<img style="width: 100%;" src="https://tek4.vn/public_files/f80e6530-1ed2-4c72-9609-b18e34c5527c" alt="ctdl423" />
<h3>C&ocirc;ng thức m&atilde; h&oacute;a</h3>
C&ocirc;ng thức của hệ mật Affine l&agrave; 1 cặp kh&oacute;a <code>k={a, b}</code> với điều kiện ti&ecirc;n quyết <code>UCLN(a,26)=1</code>.
C&ocirc;ng thức m&atilde; h&oacute;a của hệ mật n&agrave;y l&agrave; : <code>y = (a*x + b) mod 26</code>
Để giải m&atilde; được hệ mật n&agrave;y, trước hết ta cần t&igrave;m gi&aacute; trị <code>a^-1</code> thỏa m&atilde;n điều kiện <code>a*a^-1 mod 26 = 1</code>. Sau đ&oacute; &aacute;p dụng c&ocirc;ng thức giải m&atilde; hệ mật l&agrave;: <code>x = a^-1*(y - b) mod 26</code>
Ta c&oacute; thể hiểu hơn c&aacute;ch thực hoạt động của thuật to&aacute;n th&ocirc;ng qua một v&iacute; dụ nhỏ sau:
V&iacute; dụ 
Ta c&oacute; văn bản gốc l&agrave; :"It is nice today". Mục ti&ecirc;u l&agrave; ta cần m&atilde; h&oacute;a văn bản n&agrave;y bằng hệ mật Affine với kh&oacute;a <code>k =(7 ,3)</code>. Sau đ&acirc;y l&agrave; c&aacute;c bước l&agrave;m:
<h4>M&atilde; h&oacute;a: Ta t&igrave;m bản m&atilde; của văn bản gốc th&ocirc;ng qua c&ocirc;ng thức <code>y = (a*x + b) mod 26</code>.</h4>
Tức l&agrave; <code>y[0] = (a * x[0] + b) mod 26</code>. Trong n&agrave;y <code>a=7</code>, <code>b=3</code> , gi&aacute; trị <code>x[0] = "I"</code> mang gi&aacute; trị m&atilde; l&agrave; <code>8</code>. Vậy n&ecirc;n <code>y[0] = (7 * 8 + 3 ) mod 26 = 7</code>. Gi&aacute; trị 7 ta tra trong bảng tr&ecirc;n mang gi&aacute; trị l&agrave; chữ H. Vậy n&ecirc;n chữ c&aacute;i đầu ti&ecirc;n trong bản m&atilde; l&agrave; chữ H. Ta l&agrave;m tương tự với những chữ c&ograve;n lại thu được bảng như sau:
<img style="width: 1280px;" src="https://tek4.vn/public_files/80cb7c67-1e45-4684-808d-303c33cf1407" alt="ctdl424" height="279" />
Vậy, từ văn bản gốc :"<code>It is a nice today</code>" ta thu được bản m&atilde; l&agrave; :"<code>HG HZ QHRF GXYDP</code>".
<h4>Giải m&atilde;: C&ocirc;ng thức của h&agrave;m giải m&atilde; l&agrave;: <code>x = a^-1*(y - b) mod 26</code></h4>
Khi giải bản m&atilde; về văn bản gốc, ta cần thực hiện ngược lại c&aacute;c bước tr&ecirc;n. Trước hết ta cần chuyển đổi chữ c&aacute;i trong bản m&atilde; th&agrave;nh dạng số nguy&ecirc;n của ch&uacute;ng. Sau đ&oacute; &aacute;p dụng c&ocirc;ng thức giải m&atilde;. Ta c&oacute;&nbsp;<code>x[0] = a^-1*(y[0] - b) mod 26 </code>với <code>y[0] = 7</code>, <code>b = 3</code> v&agrave; <code>a^-1=15</code>(v&igrave; <code>7*15 mod 26 = 1</code>). Thế n&ecirc;n ta t&iacute;nh được gi&aacute; trị <code>x[0] = 8</code> tương ứng với chữ "I".
<img style="width: 1279px;" src="https://tek4.vn/public_files/c997afa2-8bf7-4780-b3cb-eb5f11d8d65d" alt="ctdl425" height="286" />
Sau khi t&iacute;nh to&aacute;n tới chữ c&aacute;i cuối c&ugrave;ng, ta thu được bản r&otilde; l&agrave; :"<code>It is nice today</code>".
Y&ecirc;u cầu
Với đầu v&agrave;o d&ograve;ng đầu l&agrave; cặp kh&oacute;a a,b ; d&ograve;ng thứ 2 l&agrave; một chuỗi k&iacute; tự in thường. H&atilde;y in ra kết quả m&atilde; h&oacute;a v&agrave; giải m&atilde; bằng hệ mật Affine. Nếu kh&ocirc;ng m&atilde; h&oacute;a được in kết quả "Can't Encrypted and Decrypted this Message"
V&iacute; dụ 1
Đầu v&agrave;o:
<pre class="language-c" data-content="7%203%0Ait%20is%20nice%20today" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>7 3
it is nice today</code></pre>
Đầu ra:
<pre class="language-c" data-content="hg%20hz%20qhrf%20gxydp" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>Encrypted Message is : hg hz qhrf gxydp
Decrypted Message is : it is nice today</code></pre>
V&iacute; dụ 2
Đầu v&agrave;o:
<pre class="language-c" data-content="7%203%0Ait%20is%20nice%20today" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>4 7
welcome to tek4</code></pre>
Đầu ra:
<pre class="language-c" data-content="hg%20hz%20qhrf%20gxydp" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>Can't Encrypted and Decrypted this Message</code></pre>
&nbsp;