STEAM For Vietnam

Author: Gia Đào

Trước khi diễn giải khái niệm tính kế thừa (Inheritance) trong lập trình hướng đối tượng, chúng ta cùng đến với một vài ví dụ trong thực tế để nắm bắt sơ qua về khái niệm này. Trong cuộc sống, tính kế thừa xuất hiện ở khắp mọi nơi. Chúng ta kế thừa những đặc điểm của bố mẹ chúng ta, chẳng hạn như màu mắt, màu tóc, thậm chí là tính cách. Ngoài tự nhiên, loài khỉ đột, khỉ đầu chó, đười ươi, hay vượn má trắng… mặc dù chúng có bề ngoài khác nhau, nhưng đều được các nhà sinh vật học xếp vào bộ Linh Trưởng bởi khả năng leo trèo tuyệt vời, não bộ lớn, sử dụng chi trước linh hoạt,… Chúng đều kế thừa những đặc điểm này từ loài vượn cổ xưa, tổ tiên của chúng trong lịch sử. Dù chưa đề cập tới khái niệm tính kế thừa trong lập trình nhưng với những ví dụ trên, chúng ta có thể hình dung qua nội dung cơ bản của nó: khi một tập con sở hữu những đặc điểm sẵn có từ tập cha và phát triển những đặc điểm riêng của mình, gọi là kế thừa. Hổ là sinh vật hoạt động cá nhân, có vằn, sinh trưởng thích hợp trong môi trường rừng rậm, trong khi đó sư tử sinh hoạt theo bầy và chỉ xuất hiện ở vùng đồng cỏ với khí hậu khô. Hổ và sư tử là hai loài vật hoàn toàn khác nhau với những đặc điểm khác nhau đã tiến hóa, tuy vậy, chúng vẫn được xếp chung vào lớp họ Mèo bởi những đặc tính chung được kế thừa như săn mồi bằng cách mai phục, hoạt động mạnh về đêm, là động vật có vú ăn thịt đi bằng bốn chân… 

Trong ảnh là 1 ví dụ về Animal class, lớp Thú nói chung có các loài 4 chân như chó, mèo, và bò. 

Tính kế thừa thú vị ở chỗ một cá thể được phát triển dựa trên những gì sẵn có và tự tạo nên những đặc tính riêng của mình. Trong khoa học, tính kế thừa được áp dụng để tận dụng những phát minh đã có sẵn nhằm tiết kiệm thời gian và công sức. Chẳng hạn, tập đoàn Apple sẽ không phát triển iPhone 13 bằng cách bắt đầu từ con số 0 mà chắc chắn, họ sẽ sử dụng lại những thiết kế, chức năng cơ bản của những đời iPhone trước để phát triển những tính năng mới cho iPhone 13. Ta có thể nói, iPhone 13 ‘kế thừa’ iPhone 11 hay 12 và được thêm những tính năng như chụp ảnh ‘nét’ hơn, giao diện thân thiện hơn hay pin dùng được lâu hơn.  

Tính kế thừa trong lập trình hướng đối tượng được định nghĩa là, khi một lớp con (derived or child class) được thừa hưởng các thuộc tính (property) và phương thức (method) của lớp cha (base or parent class) mà nó kế thừa.  

Trước khi đến với cách hoạt động của tính kế thừa, chúng ta cùng tìm ôn lại hai khái niệm cơ bản trong lập trình hướng đối tượng, đó là: Lớp (Class) và Đối tượng (Object). 

Chúng ta có thể liên kết khái niệm trên thông qua một ví dụ: ‘Ngôi nhà’ được coi là một ‘đối tượng’ và khi chúng ta nhắc tới ‘Ngôi nhà’, chúng ta đều biết ‘ngôi nhà’ phải có những đặc điểm như ‘có cửa sổ’, ‘có cửa ra vào’, ‘mái che’, ‘phòng ngủ’… Những đặc điểm chung cơ bản nêu trên của một ngôi nhà mà tất cả chúng ta đều biết được gọi là ‘thuộc tính’ (Attributes). Tuy vậy, để xây được ngôi nhà, chúng ta cần có bản thiết kế. Lớp (Class), chính là bản thiết kế này, là nơi chúng ta sẽ thiết kế ngôi nhà trông ra sao, có màu gì, có bao nhiêu phòng… 

class House: 

Ở đây chúng ta thấy, sau khi có bản thiết kế ngôi nhà, nói cách khác, khi khởi tạo class House, chúng ta có 2 đặc tính là color, house_number. Sample_house là 1 đối tượng được xây dựng dựa trên bản thiết kế House, và chúng ta có thể cho chúng các đặc điểm cụ thể.  

Biến color và house_number được gọi bằng dấu ‘.’ và chúng ta lưu giá trị ‘blue’ cho color và 10 cho house_number. 

Ở bức ảnh trên, ta thấy 3 lớp, xe buýt (Bus), xe con (Car), và xe tải (Truck) đều có chung các phương thức hoạt động như fuelAmount() (kiểm tra xăng), capacity() (số người có thể chứa), applyBrakes() (có phanh). Ta có thể thấy, đây là một vài đặc điểm cơ bản chung của các loại xe được nêu trên, tuy nhiên, nếu khai báo tất cả các lớp này với các phương thức lặp đi lặp lại như vậy sẽ tốn rất nhiều thời gian và công sức, do đó, ta sẽ sử dụng tính kế thừa, bằng cách tạo 1 lớp chung, gọi là ‘Phương tiện’ (Vehicle) với các phương thức như trên, và xe buýt, xe con, và xe tải sẽ là những lớp con kế thừa từ lớp cha này: 

Trong ảnh là một ví dụ đơn giản để mô phỏng tính kế thừa. Lớp cha đại diện cho các phương tiện giao thông nói chung (Vehicle) mà trong đó, những phương thức của lớp cha bao gồm fuelAmount(), capacity(), applyBrakes(), sẽ được thừa hưởng bởi lớp con. Việc tạo ra lớp cha rồi sử dụng tính kế thừa khi tạo những lớp con giúp ta tiết kiệm rất nhiều thời gian và tránh được việc lặp lại các phương thức khi phải tạo ra nhiều lớp.  

Mô phỏng tính kế thừa bằng Python: 

# define a superclass
class super_class:
# attributes and method definition

# inheritance
class sub_class(super_class):
# attributes and method of super_class
# attributes and method of sub_class 

Super class ở đây là lớp cha và sub_class là lớp con kế thừa từ lớp cha. Ví dụ trên là cách khai báo lớp nói chung và dưới đây là ví dụ cụ thể: 

class Animal:

# attribute and method of the parent class
name = “”

def eat(self):
    print(“I can eat”)

# inherit from Animal
class Dog(Animal):

# new method in subclass
def display(self):
    # access name attribute of superclass using self
    print(“My name is “, self.name)

# create an object of the subclass
labrador = Dog()

# access superclass attribute and method 
labrador.name = “Rohu”
labrador.eat()

# call subclass method 
labrador.display() 

Ở đây ta khởi tạo lớp cha là Animal với 1 biến name và phương thức eat(). Phương thức eat khi được gọi sẽ in ra dòng “I can eat”. Dog là 1 lớp con cụ thể được tạo ra bằng việc kế thừa từ lớp cha. Để khởi tạo lớp con Dog, ta truyền lớp cha Animal vào trong 2 dấu ngoặc tròn. Lưu ý rằng, bởi lớp con Dog được kế thừa từ lớp cha và thông qua những ví dụ ở trên, ta biết rằng lớp con Dog có thể thừa hưởng những biến và phương thức của lớp cha.  

Thật vậy, phương thức display() trong lớp Dog, có thể gọi biến name trong lớp cha thông qua biến self: self.name. Nói 1 cách cụ thể, khi phương thức display() được gọi, kết quả sẽ in ra “My name is “ với biến name sở hữu bất kỳ giá trị nào. 

Cuối cùng, ta khởi tạo labrador = Dog() để có thể sử dụng lớp con Dog. Labrador chính là 1 đối tượng (Object) mà chúng ta đã đề cập tới trong bài học. Một lần nữa, ta thấy 3 dòng: 

Labrador.name = “Rohu” => Lưu trữ giá trị xâu “Rohu” vào trong biến name 

Labrador.eat() => gọi phương thức eat (sử dụng dấu ‘.’) 

Labrador.display() => gọi phương thức display (sử dụng dấu ‘.’) 

Ba dòng code trên đều cho thấy rằng, labrador là 1 đối tượng của lớp con nhưng bởi tính kế thừa, nó hoàn toàn có thể sở hữu những phương thức và biến của lớp cha và truy cập tới chúng. Khi chạy toàn bộ đoạn code trên, chúng ta có kết quả như sau: 

Output:  

I can eat
My name is Rohu 

Tác giả: Quốc Huỳnh

Python cung cấp cho người dùng nhiều công cụ hỗ trợ tính toán và vẽ đồ thị, giúp cho việc trực quan hóa dữ liệu trở nên dễ dàng hơn bao giờ hết. Trong Python, có rất nhiều thư viện và module hỗ trợ vẽ đồ thị.

Trong bài viết này, chúng ta sẽ tìm hiểu về một số công cụ vẽ đồ họa và biểu đồ trong Python.

1. Turtle:

Turtle là một thư viện vẽ hình đơn giản trong Python, được thiết kế để giúp các em học lập trình và vẽ hình ảnh đơn giản một cách dễ dàng.

Khi sử dụng Turtle, bạn có thể tạo ra những hình dạng đơn giản như hình vuông, hình tam giác, hình tròn và các hình khác. Bạn cũng có thể điều khiển con rùa (turtle) để vẽ hình theo ý muốn của mình.

Ví dụ:

Để vẽ lá cờ Việt Nam bằng Turtle, ta có thể dùng lệnh sau đây

Ta vẽ nền đỏ của cờ, bắt đầu bằng cách nâng bút lên (penup), di chuyển đến vị trí (-200, 200) (tọa độ này nằm ở góc trên bên trái của cửa sổ vẽ), đặt bút xuống (pendown), thiết lập màu đỏ và bắt đầu tô màu (begin_fill). Với mỗi vòng lặp i trong khoảng từ 0 đến 1, di chuyển về phía trước 400 đơn vị, quay sang phải 90 độ, di chuyển về phía trước 266 đơn vị và quay sang phải 90 độ nữa để hoàn thành một hình chữ nhật. Khi vẽ xong hình, kết thúc tô màu (end_fill).

Vẽ ngôi sao, bắt đầu bằng cách nâng bút lên (penup), di chuyển đến vị trí (-90, 90) (tọa độ này nằm ở giữa cửa sổ vẽ), đặt bút xuống (pendown), thiết lập màu và bắt đầu tô màu (begin_fill). Với mỗi vòng lặp i trong khoảng từ 0 đến 4, di chuyển về phía trước 180 đơn vị, quay sang phải 144 độ để tạo ra 5 góc của ngôi sao. Khi vẽ xong hình, kết thúc tô màu (end_fill).

Đây là kết quả thu được

2. Matplotlib

Matplotlib là một trong những thư viện vẽ đồ họa và biểu đồ phổ biến nhất trong Python. Thư viện này có thể được sử dụng để vẽ nhiều loại biểu đồ khác nhau, bao gồm biểu đồ đường, biểu đồ thanh, biểu đồ hộp, biểu đồ phân tán và nhiều hơn nữa. Matplotlib cho phép người dùng tùy chỉnh hoàn toàn các phần của biểu đồ, từ tiêu đề cho đến các trục và các chú thích.

Đây là một số kết quả thu được khi dùng Matplotlib để vẽ biểu đồ trong việc phân tích dữ liệu

3. Seaborn

Seaborn là một thư viện vẽ biểu đồ dựa trên Matplotlib, được thiết kế để giúp người dùng vẽ các biểu đồ phức tạp một cách dễ dàng hơn. Seaborn cho phép người dùng vẽ các biểu đồ phân tán với các đường hồi quy và các biểu đồ phân phối với các đường cong phù hợp. Thư viện này cũng có thể được sử dụng để vẽ các biểu đồ hộp và các biểu đồ đường.

Matplotlib và Seaborn là hai thư viện phổ biến trong việc trực quan hóa dữ liệu trong Python.

Dưới đây là một số khác biệt chính giữa hai thư viện này:

1. Cú pháp: Matplotlib cung cấp cú pháp đơn giản để tạo ra các biểu đồ cơ bản, trong khi Seaborn cung cấp các biểu đồ trực quan hơn và có cú pháp đơn giản hơn để tạo ra các biểu đồ phức tạp hơn.
2. Kiểu biểu đồ: Matplotlib cung cấp các biểu đồ cơ bản như biểu đồ đường, cột, hình tròn, v.v., trong khi Seaborn cung cấp các biểu đồ trực quan hơn như biểu đồ phân phối, biểu đồ tương quan, biểu đồ hộp, v.v.
3. Màu sắc: Seaborn cung cấp các màu sắc mặc định cho các biểu đồ, trong khi Matplotlib yêu cầu người dùng tự định nghĩa màu sắc.
4. Tích hợp với Pandas: Seaborn được thiết kế để tích hợp tốt với thư viện Pandas để trực quan hóa dữ liệu, trong khi Matplotlib chỉ hỗ trợ cơ bản tích hợp với Pandas.

Tóm lại, Matplotlib là một thư viện trực quan hóa dữ liệu cơ bản trong Python, trong khi Seaborn cung cấp các biểu đồ phức tạp và trực quan hơn. 

Ngoài những thư viện phổ biến đã kể trên ra thì chúng ta còn có các công cụ vẽ khác có thể được dùng trong Python như Plotly, Bokeh hay Altair, v.v mà các bạn học sinh có thể tìm hiểu thêm.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Jack Vo

1. Stack

Stack (ngăn xếp) là kiểu dữ hoạt động theo nguyên lý Last In First Out hay LIFO (vào sau ra trước). Chúng ta có thể xem ảnh động bên dưới để hình dung rõ hơn về các hoạt động của kiểu dữ liệu này. Khối vuông màu đỏ sẽ lần lượt được đặt trồng lên nhau trong một cái cốc sau đó khối vuông ở trên cùng sẽ là cái ra khỏi chiếc cốc đầu tiên dựa theo nguyên lý vào sau ra trước hay LIFO.

2. Queue

Queue (hàng chờ) là một kiểu dữ liệu có cách hoạt động hơi khác so với Stack là sẽ dựa vào nguyên lý First In First Out hay FIFO (vào trước ra trước). Chúng ta có thể xem ảnh động ở bên dưới để hình dung rõ hơn về cách hoạt động của kiểu dữ liệu này. Số 8 là số đầu tiên vô hàng cũng như sẽ là số đầu tiên ra khỏi hàng dựa trên nguyên lý vào trước ra trước hay FIFO.

3. Ứng dụng thực tế

• Stack có thể ứng dụng vào việc làm trình duyệt tabs như khi chúng ta đã đi qua một loạt các trang webs và muốn quay lại trang đầu tiên thì chúng ta sẽ nhấn nút mũi tên quay lại thì trang trước trang cuối cùng của chúng ta sẽ được hiển thị lại trước và chúng ta sẽ cứ dùng mũi tên quay lại cho đến khi về lại trang đầu tiên.
• Queue có thể ứng dụng vào làm mấy xuất vé tự động khi mà mỗi người khách tới rút vé thì họ sẽ là người đầu tiên vô cũng là người đầu tiên ra về, tờ vé đầu tiên ra khỏi máy xuất vé cũng là tờ vé đầu tiên mà vị khách đó cầm về.

4. Cách để viết kiểu dữ liệu bằng Python

• Stack

Chúng ta sẽ tạo một class tên Stack và sẽ sử dụng list() để xây dựng lên Stack, trong Stack sẽ bao gồm các functions như peek(), pop(), is_empty(), size(), push()

class Stack:

  def __init__(self):

      self.items = list()

  def push(self, item): // thêm vào stack

      self.items.append(item)

   def pop(self): // lấy số đầu tiên ra khỏi Stack

      return self.items.pop()

   def is_empty(self): // kiểm tra xem Stack có đang rỗng

      return self.items == []

  def peek(self): // xem số trên cùng

      return self.items[len(self.items) – 1]

  def size(self): // kiểm tra xem độ lớn của Stack

      return len(self.items)

• Queue

Chúng ta sẽ tạo một class tên Queue và sẽ sử dụng list() để xây dựng lên Queue, trong Queue sẽ bao gồm các functions của như is_empty(), size(), enqueue(), dequeue()

class Queue:

  def __init__(self):

      self.items = list()

  def enqueue(self, item): // thêm vào queue

      self.items.insert(0, item)

   def dequeue(self): // lấy số đầu tiên ra khỏi Queue

      return self.items.pop()

   def is_empty(self): // kiểm tra xem Queue có đang rỗng

      return self.items == []

  def size(self): // kiểm tra xem độ lớn của Queue

      return len(self.items)

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Quang Nguyễn

Trong blog này, chúng ta sẽ cùng tìm hiểu qua hai thuật toán tìm kiếm rất phổ biến trong khoa học máy tính là DFS và BFS để giúp máy tính thực hiện nhiệm vụ tìm đường đi trong mê cung này nhé. Hai thuật toán này có sử dụng hai kiểu cấu trúc dữ liệu đã được học ở trong bài 6 của lớp CS101 đấy!!!

1. Mê cung:

Một mê cung của chúng sẽ được biểu diễn như hình dưới đây, với các tường được biểu diễn dưới ô vuông màu xám, đường đi dưới dạng các ô vuông màu vàng đất, điểm bắt đầu với biển bàn tay chỉ dẫn màu xanh lá cây, và điểm kết thúc là lá cờ màu đỏ:

Các bạn có thấy hình ảnh về mê cung có quen không nào?? Chúng ta đã được biết đến khái niệm mảng hai chiều, và mê cung có thể được biểu diễn bằng mảng hai chiều gồm các hàng và cột. Nhiệm vụ của chúng ta là phải tìm ra đường đi từ điểm bắt đầu cho đến điểm kết thúc:

• 

2. Thuật toán Depth-first search (DFS):

Đầu tiên hãy tưởng tượng rằng bạn đang đi du lịch Bà Nà Hills ở Đà Nẵng, và bạn được trải nghiệm giải mã mê cung ngoài đời thật tại Khu vườn bí ẩn. Và bạn chợt nhận ra là trong thực tế, thay vì nhìn trước được toàn bộ mê cung như các trò chơi được in trên báo, giờ đây bạn chỉ có thể nhìn được một vài vị trí xung quanh bản thân để quyết định xem hướng nào sẽ đi tiếp.

Và máy tính của chúng ta cũng vậy, trong thực tế máy tính chỉ có thể nhìn thấy đường đi xung quanh kế bên mình. 

Vậy ở tại mỗi vị trí chúng ta sẽ quyết định đường đi tiếp theo như thế nào nhỉ? Làm sao để chúng ta tránh đi lòng vòng và quay đi quay lại đường mình đã đi? Chọn bừa một hướng đi và hy vọng nó sẽ dẫn đến lối thoát hay có một chiến thuật thông minh hơn? Ở phần này chúng ta sẽ cùng tìm hiểu cách tiếp cận đầu tiên thông qua thuật toán DFS. 

Thuật toán DFS là viết tắt của Depth-First Search, có nghĩa là tìm kiếm theo chiều sâu. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp (stack) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ tìm theo một nhánh đến khi tìm được đường ra, nếu hết đường thì mới quay lại đến khi thấy nhánh mới.

Để hiểu rõ hơn về thuật toán này chúng ta sẽ giúp bạn Trẩu tìm đường đi từ điểm bắt đầu đến điểm kết thúc qua ví dụ đơn giản dưới đây:

Ở ví dụ này, chúng ta sẽ minh hoạ cấu trúc dữ liệu ngăn xếp bằng một chiếc hộp carton với các phần tử trong stack là các tờ giấy đánh số được bỏ vào hộp. Các bước của thuật toán DFS sẽ như sau:

• Bước 1: Đến điểm xuất phát
• Bước 2: Đánh số vị trí hiện tại (lưu ý rằng các số không được trùng nhau)
• Bước 3: Nhìn xung quanh theo thứ tự Trên – Dưới – Trái – Phải xem có đường nào chưa được đánh dấu không. Nếu có, sang bước 4. Nếu không, sang bước 5.
• Bước 4: Đi sang ô tiếp theo, ghi lại số của ô cũ vào trong tờ giấy rồi bỏ vào hộp. Quay lại bước 2.
• Bước 5: Lấy lại 1 tờ giấy trong hộp, quay lại vị trí trong tờ giấy. Quay lại bước 3.

Đầu tiên theo bước 1 và bước 2 bạn Trẩu sẽ đến điểm xuất phát và đánh số vị trí bạn đang đứng hiện tại là số 1 và hiện tại chiếc hộp vẫn đang rỗng:

Sau đó, bạn Trẩu tiếp tục thực hiện bước 3 nhìn xung quanh xem có đường nào theo thứ tự Trên – Dưới – Trái – Phải chưa được đánh dấu không, ở bước này chúng ta thấy chỉ có một đường duy nhất cho bạn Trẩu là đi sang phải:

Bạn Trẩu thực hiện bước 4 quyết định đi sang ô bên phải, đồng thời ghi lại số của ô cũ vào trong tờ giấy và bỏ vào hộp:

Sau đó, chúng ta quay lại bước 2 bằng cách đánh số vị trí hiện tại là 2. Tiếp theo thực hiện bước 3 bằng các xác định đường đi theo thứ tự Trên – Dưới – Trái – Phải và được kết quả như sau:

Ở đây bạn Trẩu của chúng ta có hai lựa chọn di chuyển sang phải hoặc di chuyển xuống dưới. Tại vì trong số 4 hướng di chuyển Trên – Dưới – Trái – Phải, hướng di chuyển Dưới được ưu tiên trước hướng di chuyển Phải nên ở bước này bạn Trẩu sẽ di chuyển xuống dưới, đồng thời ghi lại số của ô cũ là 2 và bỏ vào hộp:

Tiếp tục thực hiện các bước của thuật toán, chúng ta sẽ đến được trạng thái như sau:

Ở bước này, bạn Trẩu có hai hướng di chuyển là lên trên và sang phải, tuy nhiên vì lựa chọn Trên được ưu tiên trước lựa chọn Phải trong bước 3 của thuật toán nên bạn Trẩu tiếp tục di chuyển lên trên và thực hiện tiếp các bước của thuật toán chúng ta sẽ được:

Theo như bước 3, đến vị trí này thì chúng ta thấy xung quanh bạn Trẩu tất ở các đường đều đã được đánh dấu, vì vậy chúng ta sẽ di chuyển đến bước 5 để hướng dẫn bạn Trẩu tiếp tục di chuyển. Đầu tiên chúng ta sẽ lấy 1 tờ giấy ờ trong hộp ra, tờ giấy này có đánh số 8, vì vậy bạn Trẩu sẽ di chuyển đến vị trí được đánh dấu số 8 trên mê cung và quay lại bước 3:

Ở vị trí này chúng ta thấy tất cả các vị trí xung quanh Trẩu đều đã được đánh dấu nên chúng ta sẽ tiến đến thực hiện bước 5 đưa Trẩu quay lại về vị trí 7:

Sau khi quay lại hai vị trí cuối cùng bạn Trẩu cũng tìm được một hướng đi chưa được đánh dấu là di chuyển sang bên phải vị trí số 7:

Bạn Trẩu đi theo hướng bên phải và tiếp tục thực hiện các bước của thuật toán. Và voila, cuối cùng bạn Trẩu của chúng ta cũng đến được vị trí đích:

Vậy bây giờ làm thế nào để đi lại vị trí ban đầu nhỉ? Rất đơn giản, tất cả các thông tin về đường đi từ vị trí ban đầu đã được lưu lại trong chiếc hộp. Thứ tự các mảnh giấy từ trên xuống dưới trong chiếc hộp, bước nào đi sau cùng sẽ được thực hiện trước (Last in First out – LIFO): 12 – 11 – 10 – 7 – 6 – 5 – 4 – 3 – 2 – 1. (Lưu ý rằng các mảnh giấy ví dụ như số 8 sẽ không nằm trong hộp vì đã được loại bỏ ở các bước trước do không thuộc đường đi). 

3. Thuật toán Breadth-First-Search (BFS):

Thuật toán BFS là viết tắt của Breadth-First Search, có nghĩa là tìm kiếm theo chiều rộng. Khi thực hiện thuật toán này chúng ta sẽ sử dụng cấu trúc dữ liệu hàng đợi (queue) đã được học ở trong bài 6. Ý tưởng là chúng ta sẽ duyệt tất cả các nhánh để xem nhánh nào có lối ra thì dừng lại.

Để hiểu rõ hơn thuật toán này chúng ta sẽ cùng quay lại ví dụ của bạn Trẩu ở phần 2. Ở phần này, chúng ta sẽ minh hoạ cấu trúc dữ liệu hàng đợi là một chiếc thước kẻ với các phần tử bên trong là các mẩu giấy có đánh số được dán lên thước kẻ.

 Các bước của thuật toán BFS sẽ như sau:

• Bước 1: Đến điểm xuất phát và đánh dấu điểm xuất phát.
• Bước 2: Đánh dấu các ô xung quanh có thể đi được. (Lưu ý rằng không dùng các số trùng nhau)
• Bước 3: Ghi số của các ô xung quanh vào mẩu giấy, rồi dán chúng lên thước kẻ theo chiều từ trái qua phải.
• Bước 4: Lấy một mẩu giấy bên trái ngoài cùng ghi trên thước kẻ, đi đến ô ghi trên mẩu giấy. Quay lại bước 2. 

Đầu tiên chúng ta sẽ bắt đầu và đánh số 1 ở vị trí đầu tiên, lúc này thước kẻ vẫn trống chưa có mảnh giấy nào được dán lên:

Sau đó thực hiện bước 2 và bước 3, đánh dấu các ô xung quanh có thể đi được từ vị trí đang đứng và dán các mẩu giấy có ghi số các ô xung quanh lên trên thước kẻ:

Thực hiện bước 4, chúng ta lấy mẩu giấy bên trái ngoài cùng có ghi số 2 trên thước kẻ và bạn Trẩu di chuyển đến vị trí 2 có ghi trên mẩu giấy:

Tiếp tục quay lại thực hiện bước 2 và bước 3, ở vị trí hiện tại bạn Trẩu có hai lựa chọn ở xung quanh có thể đi được, đánh số các ô đó tương ứng với số 3 và 4 và dán các mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 3 và di chuyển bạn Trẩu đến vị trí số 3:

Quay lại thực hiện bước 2 và bước 3, bạn Trẩu có một lựa chọn bên phải có thể đi được, đánh số vị trí này là 5 và dán mẩu giấy lên trên thước kẻ:

Thực hiện bước 4 chúng ta lấy ra mẩu giấy bên trái ngoài cùng của thước kẻ là mẩu giấy có chứa số 4 và di chuyển bạn Trẩu đến vị trí số 4:

Tiếp tục thực hiện các bước của thuật toán và tada, cuối cùng bạn Trẩu sẽ đến được vị trí đích với các số được đánh dấu trên mê cung như sau:

Để đi lại về vị trí ban đầu, bạn Trẩu của chúng ta chỉ cần đi ngược lại theo các ô có số nhỏ hơn là được (nếu có từ 2 ô số nhỏ hơn, chọn ô có số nhỏ nhất): 13 – 12 – 11 – 9 – 7 – 5 – 3 – 2 – 1. Mảnh giấy ở bên trái trên thước kẻ sẽ được thực hiện trước trong queue (First In First Out – FIFO).

4. So sánh DFS và BFS:

Wow, như vậy là chúng ta đã giúp bạn Trẩu tìm đường di chuyển ra khỏi mê cung bằng hai thuật toán DFS và BFS, thật là ảo diệu phải không các bạn? Để kết thúc blog này, chúng ta sẽ cùng điểm qua một vài sự khác biệt giữa hai thuật toán này nhé:

DFS	BFS
Tìm theo một nhánh đến khi gặp đường cụt hoặc đích Dùng hộp giấy (ngăn xếp) Cả con người và máy tính có thể thực hiện Đường đi tìm được có thể không phải là ngắn nhất	Tìm cùng lúc nhiều nhánh Dùng thước kẻ (hàng đợi) Chỉ áp dụng hợp lý với máy tính Đường đi tìm được luôn là đường đi ngắn nhất

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Yang Tuấn Anh

Hard Drive

Ổ cứng giống như một cuốn sách lớn, nơi bạn có thể lưu trữ nhiều hình ảnh, video và trò chơi. Nó có một bộ phận đặc biệt gọi là “platter” quay rất nhanh, giống như đu quay. Đĩa được làm bằng vật liệu cứng và có lớp phủ đặc biệt có thể nhiễm từ hoặc khử từ. Điều này có nghĩa là ổ cứng có thể lưu trữ thông tin bằng cách sử dụng các nam châm cực nhỏ để tạo các mẫu trên đĩa.

Khi bạn muốn tìm thứ gì đó trên ổ cứng, một cánh tay đặc biệt được gọi là đầu đọc-ghi sẽ di chuyển trên đĩa quay để đọc các dạng từ tính. Nó giống như một con robot có thể đọc sách cho bạn. Nhưng ổ cứng rất mỏng manh, và ngay cả một hạt bụi nhỏ cũng có thể làm cho đầu đọc-ghi nảy lên xuống, đâm vào đĩa và làm hỏng lớp phủ từ tính của nó. Đó là lý do tại sao điều quan trọng là phải rất cẩn thận với ổ cứng và giữ cho nó sạch sẽ.

Ngoài ra còn có các ổ cứng mới hơn được gọi là ổ cứng thể rắn hoạt động theo cách khác. Thay vì sử dụng đĩa quay, họ sử dụng mạch điện để lưu trữ thông tin. Điều này có nghĩa là chúng nhanh hơn và bền hơn ổ cứng truyền thống, nhưng chúng cũng đắt hơn.

CPU – RAM

CPU được ví như bộ não của máy tính. Nó giúp máy tính suy nghĩ và làm mọi việc. Nó giống như một nhạc trưởng nói cho các nhạc công chơi gì. CPU có rất nhiều bộ phận nhỏ gọi là bóng bán dẫn giúp nó hoạt động.

Sau khi nó được đặt trong ổ cắm, các bộ phận khác của máy tính có thể kết nối với CPU thông qua một thứ gọi là “bus”. Ví dụ, RAM kết nối với CPU thông qua bus riêng của nó. CPU thực hiện hầu hết việc xử lý lệnh và đôi khi, thậm chí cả đồ họa cũng hoạt động (nếu nó được chế tạo cho việc đó). Tuy nhiên, CPU không phải là cách duy nhất để xử lý các lệnh. Các thành phần khác, chẳng hạn như card đồ họa, có khả năng xử lý trên bo mạch riêng.

RAM giống như bộ nhớ ngắn hạn của máy tính. Nó giúp CPU ghi nhớ những thứ nó cần làm ngay bây giờ. Nó giống như một chiếc bàn nơi bạn để bài tập về nhà trong khi bạn đang làm bài.

RAM là viết tắt của Random Access Memory và nó chỉ lưu trữ dữ liệu tạm thời, ngay khi bạn tắt nguồn, bạn sẽ mất dữ liệu, những ưu điểm là tốc độ của nó nhanh hơn rất nhiều so với bộ nhớ ngoài hoặc ROM.

RAM được tạo thành từ các tụ điện nhỏ và bóng bán dẫn có khả năng giữ điện tích. Bộ nhớ cache giống như một phiên bản RAM nhỏ hơn, nhanh hơn. Chúng giúp CPU ghi nhớ những thứ nó cần làm ngay bây giờ, nhưng chúng thậm chí còn nhanh hơn cả RAM. Nó giống như một cuốn sổ nhỏ bạn để trong túi với những điều quan trọng nhất mà bạn cần ghi nhớ

Bộ nhớ hoạt động thế nào? (Logic gates)

Các cổng logic giống như các công tắc nhỏ giúp máy tính đưa ra quyết định. Chúng là các khối xây dựng của các mạch kỹ thuật số, giống như những con đường mà thông tin di chuyển bên trong máy tính. Một con chip máy tính có nhiều cổng logic hoạt động cùng nhau để giúp máy tính thực hiện mọi việc rất nhanh.

Cổng logic giống như các khối xây dựng của máy tính. Chúng giúp máy tính đưa ra quyết định và thực hiện mọi việc. Có nhiều loại cổng logic khác nhau, như AND, OR và NOT.

Cổng AND nhận hai đầu vào và đánh giá là đúng (tức là đầu ra là ‘1’) khi cả hai đầu vào của nó đều đúng. Nó giống như một người bảo vệ chỉ cho phép bạn tham gia một bữa tiệc nếu bạn có vé và tem.

Cổng OR nhận hai đầu vào và đánh giá là đúng khi ít nhất một trong các đầu vào của nó là đúng. Nó giống như một giáo viên cho phép bạn ra chơi nếu bạn có giấy phép hoặc giấy nhắn của cha mẹ bạn.

Cổng NOT nhận một đầu vào và đánh giá ngược lại với đầu vào của nó. Nó giống như biển báo “cấm chó” khi bạn không được phép mang theo chó của mình.

Cổng logic được tìm thấy trong hầu hết mọi thiết bị kỹ thuật số mà chúng ta sử dụng thường xuyên. Cổng logic được sử dụng trong kiến trúc của điện thoại, máy tính xách tay, máy tính bảng và bộ nhớ của chúng ta. Máy tính thường xâu chuỗi các cổng logic lại với nhau, bằng cách lấy đầu ra từ một cổng và sử dụng nó làm đầu vào cho một cổng khác. Chúng ta gọi đó là một mạch logic. Mạch cho phép máy tính thực hiện các hoạt động phức tạp hơn mức chúng có thể thực hiện chỉ với một cổng duy nhất.

Tổng kết

Bộ nhớ máy tính có thể được lưu trữ trên CPU, RAM, hoặc lưu trữ bên ngoài như các ổ cứng. Bằng các cổng logic, RAM sử dụng các thiết bị tụ điện để “nhớ” các bit. Còn các ổ cứng lưu trữ dữ liệu bằng các mô hình từ tính. Các bạn học sinh có thể chia sẻ trên STEAMese Profile loại bộ nhớ nào các bạn đang có trong máy tính ở nhà và với dung lượng bao nhiêu nhé.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Jack Võ

Ngoài thuật toán tìm kiếm, trong bài học tuần này, chúng ta sẽ làm quen thêm một thuật toán quan trọng khác trong đời sống đó là thuật toán sắp xếp.

1. Định nghĩa

Thuật toán sắp xếp là thuật toán dùng để xếp lại vị trí thứ tự của các giá trị trong một tập hợp hay chuỗi dữ liệu theo thứ tự từ bé đến lớn hay lớn đến bé hay theo yêu cầu của người dùng/khách hàng. Thuật toán sắp xếp không chỉ có thể dùng với số mà còn thể dùng với kí tự.

2. Các thuật toán sắp xếp

Những thuật toán sắp xếp phổ biến:

a. Bubble Sort Algorithm (sắp xếp sủi bọt):

Thuật toán này sẽ sắp xếp các cặp số hay giá trị liền kề nhau bằng cách so sánh và hoán đổi giá trị của 2 số đó, và sẽ lặp lại cho đến khi dãy dữ liệu hoặc tập hợp đã theo thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp sủi bọt bằng hình động dưới đây.

Tên của thuật toán xuất phát từ việc các số nhỏ nhất hoặc lớn nhất “sủi bọt” lên vị trí đầu trong dãy số. Thuật toán sắp xếp sủi bọt dễ sử dụng và lập trình. Tuy nhiên, thuật toán này rất không hiệu quả với dãy có nhiều số. 

b. Insertion Sort Algorithm (sắp xếp chèn):

Thuật toán này hoạt động bằng cách so sánh và xếp số có giá trị nhỏ nhất hoặc lớn nhất về hướng bên trái, và lặp lại đến khi dãy số đã vào thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp chèn bằng hình động dưới đây. 

Thuật toán sắp xếp di chuyển một phần tử của dãy số từ phần chưa được sắp xếp và chèn vào phần đã được sắp xếp. Đó cũng chính là một phần lý do về tên gọi của thuật toán này. Chúng ta chắc đã từng một vài lần sử dụng thuật toán này để sắp xếp các lá bài trên tay khi chơi cùng bạn bè. Thuật toán sắp xếp chèn không tốn nhiều bộ nhớ và dễ sử dụng cho các dãy số có ít phần tử.   

c. Selection Sort Algorithm (sắp xếp chọn lọc):

Thuật toán này sẽ liên tục chọn phần tử hay dữ liệu có giá trị nhỏ và sẽ đưa nó lên đầu, và sẽ tiếp tục lặp lại việc chọn phần tử để sắp xếp dãy số theo thứ tự tăng dần. Tương tự thuật toán có thể được sử dụng để sắp xếp dãy số theo thứ tự giảm dần bằng cách chọn phần tử có giá trị lớn để đưa lên đầu. Chính vì thế thuật toán có tên gọi là sắp xếp chọn lọc. Chúng ta có thể hình dung thuật toán sắp xếp chọn lọc bằng hình động dưới đây. 

Thuật toán sắp xếp chọn lọc nhanh và hữu ích cho dãy số có nhiều phần tử. Tuy nhiên, thuật toán sắp xếp chọn lọc cũng không hiệu quả với dãy số có nhiều phần tử.

d. Merge Sort Algorithm (sắp xếp trộn):

Thuật toán này sẽ chia tập hợp hay mảng dữ liệu ra làm 2 nửa, rồi tiếp tục chia nửa các mảng nhỏ đó, rồi sắp xếp các giá trị trong các mảng nhỏ đó, và sau cùng sẽ gộp các mảng đó lại thành một mảng giá trị đã được sắp xếp. Đó cũng là lý do thuật toán có tên là sắp xếp trộn. Chúng ta có thể hình dung thuật toán bằng hình động dưới đây.

Thuật toán sắp xếp trộn hoạt động tốt với các dãy số có nhiều phần tử. Tuy nhiên thuật toán tốn nhiều dung lượng.

Ngoài ra còn có các thuật toán sắp xếp khác gồm:

• Quick Sort Algorithm
• Heap Sort Algorithm
• Counting Sort Algorithm
• Radix Sort Algorithm
• Bucket Sort Algorithm
• Shell Sort Algorithm

Không có thuận toán nào thật sự hoàn hảo, tùy vào trường hợp và lượng dữ liệu/thông tin mà thuật toán đó có thể phù hợp và sắp xếp nhanh hơn các thuật toán còn lại

3. Ứng dụng thực tế

Các thuật toán sắp xếp được ứng dụng trong nhiều lĩnh vực và công nghiệp như ngân hàng dùng để sắp xếp thống kê sổ sách tiền tệ, phân tích dữ liệu sẽ dùng thuật toán để sắp các dữ kiện theo thứ tự thích hợp để tiện cho việc xử lý và đưa ra các biểu đồ cũng như thông tin cho công ty chủ quản.

4. Cách để viết các thuật toán bằng Python

• Bubble Sort Algorithm

Pseudo Code:

for i in range of sample_list:

    for j in range of sample_list:

          // so sánh 2 số liền kề

                     if sample_list[j] > sample_list[j+1]: 

    // đổi vị trí 2 số đó

          Ví dụ: như sắp xếp cho các bạn trong một hàng theo thứ tự từ thấp đến cao thì mình sẽ so sánh chiều cao của 2 bạn liền kề rồi mình sẽ đổi vị trí 2 bạn, ai lùn hơn thì mình đổi qua trái ai cao thì sẽ đổi qua bên phải và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao.

• Insertion Sort Algorithm

Pseudo Code:

// đặt 2 giá trị

position // giá trị position để mình theo dõi vị trí của số mình sắp xếp

insert_value // giá trị số mình sắp xếp

for i in range of sample_list:

    insert_value = sample_list[i]

    position = i

                // tìm vị trí để sắp xếp số

    while position > 0 and sample_list[position – 1] > insert_value:

            // hoán đổi vị trí các số

sample_list[position] = sample_list[position – 1]

position = position – 1

    // bỏ số đó vào vị trí đúng

    sample_list[position] = insert_value

Ví dụ: như mình sắp xếp các bạn trong một hàng theo thứ tự từ thấp đến cao thì nếu như bạn đầu tiên đã là lùn nhất rồi thì mình sẽ giữ nguyên vị trí bạn đầu tiên, sau đó mình bắt đầu so sánh như các mình làm với bubble sort nhưng thay vì mình so sánh 2 bạn một lần thì mình sẽ so sánh một bạn với tất cả các bạn ở bên tay trái để mình đưa bạn đó vào đúng vị trí, và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao. 

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation

Author: Gia Đào

Google Search, Bing… là những công cụ tìm kiếm đã quá đỗi quen thuộc với chúng ta, và gần đây nhất, ChatGPT, 1 sản phẩm của OpenAI, được ‘hậu thuẫn’ bởi gã khổng lồ công nghệ Microsoft, đã gây ra 1 cơn bão làm náo loạn giới công nghệ, với việc xử lý rất nhanh những truy vấn tìm kiếm về một thông tin bất kỳ nào đó và có thể đưa ra những kết quả gần như chính xác. Tuy vẫn còn tồn tại nhiều sai sót nhưng những gì ChatGPT có thể làm được đã vượt xa trí tưởng tượng phức tạp nhất của con người và đồng thời, thực hiện cuộc cách mạng hóa cải tổ công cụ tìm kiếm nhanh, mạnh hơn nữa. ‘Tìm kiếm’ quả là một điều thú vị và trong bài học số 4 của lớp CS101, chúng ta sẽ cùng nhau tìm hiểu về hai giải thuật tìm kiếm cơ bản và phổ biến nhất, có ứng dụng rất nhiều trong đời sống hiện nay, đó là ‘Tìm kiếm tuần tự’ và ‘Tìm kiếm nhị phân’.

1. Tìm kiếm tuần tự (Linear Search)

Tìm kiếm tuần tự (Linear Search) là một thuật toán cơ bản và gần như chúng ta có thể thực hiện ngay như một bản năng sẵn có. Giả sử như  chúng ta có một dãy các hộp gỗ đóng kín xếp cạnh nhau, mỗi hộp được đánh dấu thứ tự từ 0 đến 88 và trong mỗi hộp có 1 số tự nhiên bất kỳ:

70, 40, 30, 11, 7, 41, 25, 14, 52

Yêu cầu bài toán được đặt ra: Số 41 ở trong chiếc hộp thứ mấy? Bởi ta không biết số 41 nằm ở đâu trong mỗi hộp được đóng kín nên ta phải kiểm tra từng hộp, bằng cách mở chúng lần lượt từ trái sang phải. Nếu mở tới hộp có số thứ tự 5, thấy được số 41 nằm trong đó nên ta kết luận, số 41 nằm ở thứ tự 5. Đó cũng là cách hoạt động của thuật toán Tìm kiếm tuần tự. Bằng cách duyệt qua từng phần tử từ trái qua phải, ta có thể kết luận xem liệu phần tử cần tìm kiếm có tồn tại trong dãy trong dãy hay không, và nếu có, trả kết quả là vị trí của phần tử cần tìm nằm ở đâu trong dãy (thứ tự). Dưới đây là hình vẽ mô phỏng từng bước của thuật toán tìm kiếm tuần tự.

Đó là cách hoạt động của thuật toán Tìm kiếm tuần tự và cách tiếp cận của thuật toán này vô cùng đơn giản. Tuy vậy, giả sử như có 100,000 chiếc hộp và chúng ta được yêu cầu phải tìm hộp có chứa số 41 trong đó, liệu Tìm kiếm tuần tự có phải một giải pháp hiệu quả?

2. Tìm kiếm nhị phân (Binary Search)

Để giải quyết những bài toán tìm kiếm với số lượng lớn như vậy, chúng ta sẽ cùng tìm hiểu 1 thuật toán tìm kiếm kinh điển khác sẽ rút gọn thời gian thực hiện tìm kiếm hơn rất nhiều. Đó là thuật toán ‘Tìm kiếm nhị phân’ (Binary Search).

Chúng ta tiếp tục ví dụ về những chiếc hộp với mỗi chiếc đều được đánh số. Chỉ duy nhất một chiếc hộp có chứa kho báu ở trong và bạn được phép biết số của chiếc hộp đó. Tuy nhiên, những chiếc hộp được xếp ngẫu nhiên và số lượng chiếc hộp lên tới hàng trăm chiếc, liệu bạn có kiểm tra từng hộp, rồi so sánh chúng với số của chiếc hộp có chứa kho báu mà bạn đang cầm? Kiểm tra từng hộp cũng là một phương án, nhưng chúng ta mất quá nhiều thời gian trong việc kiểm tra từng chiếc khi số lượng chiếc hộp quá lớn như vậy, do đó, thuật toán tìm kiếm nhị phân sẽ được áp dụng trong ví dụ như sau.

Giả sử những chiếc hộp được sắp xếp theo thứ tự từ nhỏ tới lớn với các số được đánh dấu trên mỗi chiếc hộp. Tiếp theo, bắt đầu với chiếc hộp ở giữa, và ta so sánh số trên chiếc hộp ở giữa này với số của hộp kho báu mà ta đang có. Lưu ý rằng, khi đã sắp xếp những chiếc hộp theo thứ tự như trên, các hộp với số nhỏ hơn sẽ xếp trước và các hộp với số lớn sẽ xếp sau. Các hộp được sắp xếp theo thứ tự các số trong hộp là điều kiện quan trọng của thuật toán tìm kiếm nhị phân.  

Khi so sánh số của chiếc hộp ở giữa với số của hộp kho báu, ta nhận ra và có thể chắc chắn một điều rằng: nếu như số của chiếc hộp ở giữa lớn hơn số của chiếc hộp kho báu, vậy thì chiếc hộp kho báu chỉ có thể nằm trong khoảng từ vị trí chiếc hộp đầu tiên, cho tới vị trí trước chiếc hộp ở giữa, bởi lẽ, ta đã sắp xếp những chiếc hộp theo thứ tự các số trên hộp từ nhỏ tới lớn.

Ví dụ nếu như chiếc hộp ở giữa mang số 60, mà chiếc hộp có chứa kho báu mà ta cần tìm mang số 35, ta có thể biết được, chiếc hộp 35 phải nằm trước chiếc hộp 60 (bởi ta đã sắp xếp trước khi tìm kiếm)

Ngược lại, nếu như chiếc hộp ở giữa mang số 60, nhưng chiếc hộp có chứa kho báu cần tìm mang số 72, ta chắc chắn chiếc hộp có chứa kho báu sẽ nằm đâu đó sau chiếc hộp số 60, và ta sẽ loại bỏ, không cần tìm những hộp mang số nhỏ hơn 60 nữa. Như vậy việc tìm kiếm sẽ nhanh hơn rất nhiều.

Lặp đi lặp lại quá trình như vậy, với việc so sánh số dán trên chiếc hộp ở giữa với số của hộp kho báu cần tìm, ta có thể thu hẹp được xuống một hộp duy nhất và đó cũng là đáp án.

Dưới đây là mô phỏng thuật toán tìm kiếm nhị phân theo từng bước.

Cho 1 mảng A như trong hình với các phần tử đã được sắp xếp theo thứ tự tăng dần, từ nhỏ tới lớn.

Yêu cầu được đặt ra, chúng ta phải tìm kiếm phần tử có giá trị 55 nằm ở đâu trong dãy, nếu có, trả về vị trí của phần tử cần tìm, ngược lại, trả về “Không tìm thấy”

(Ký hiệu của mảng là A)

Ở lượt tìm kiếm đầu tiên, ta chọn phần tử ở giữa của dãy, tức vị trí số 6. Giá trị của phần tử ở vị trí số 6 là 41 (A[6] = 41). Vì các phần tử trong mảng đã được sắp xếp theo thứ tự tăng dần, do đó, ta có thể suy luận rằng, phần tử chúng ta cần tìm, 55, chắc chắn sẽ nằm trong phạm vi tìm kiếm từ phần tử thứ 7 trở về sau (những phần tử lớn hơn 41). Vì vậy, khoảng không gian tìm kiếm của chúng ta sẽ giảm xuống còn 1 nữa (từ 7 -> 11, lượt 2)

Tiếp tục chọn phần tử ở giữa trong khoảng không gian tìm kiếm, lần này là phần từ ở vị trí thứ 8. Phần từ ở vị trí thứ 8 là 72, vì vậy, ta biết chắc chắn phần từ 55 sẽ nằm phía trước phần tử này, do đó, ta có thể thu hẹp phạm vi tìm kiếm thêm 1 lần nữa (từ vị trí thứ 7 đến vị trí thứ 8). 

Ở lượt tìm cuối cùng, ta cũng xét phần tử ở giữa của không gian tìm kiếm hiện tại ở vị trí 7 (ở đây số lượng phần tử của không gian tìm kiếm là chẵn, do đó có hai phần tử giữa, ta có thể chọn một trong hai đều được, ở ví dụ này ta chọn phần tử giữa đầu tiên), Nhận thấy A[7]=55, bằng số chúng ta cần tìm, ta kết luận 5 chính là vị trí của phần tử cần tìm và dừng thuật toán. 

Một lưu ý vô cùng quan trọng sau các bước cụ thể ở trên, với việc thu hẹp khoảng tìm kiếm dựa trên việc so sánh phần tử ở giữa với phần tử cần tìm, thuật toán tìm kiếm nhị phân chỉ có thể áp dụng khi dãy đã được sắp xếp sẵn, với giá trị của các phần tử có thể theo thứ tự tăng dần hoặc thứ tự giảm dần. 

Chúng ta có thể hình dung thuật toán tìm kiếm nhị phân bằng hình ảnh sinh động sau:

Ngoài ra thuật toán tìm kiếm nhị phân còn có thể được sử dụng để tìm kiếm trong đời sống hàng ngày với nhiều loại dữ liệu khác nhau (số, chữ,…). Một ứng dụng là tìm tên trong danh bạ điện thoại vì các tên đã được sắp xếp theo thứ tự bảng chữ cái. Một ứng dụng khác là khi chúng ta cần tìm một từ trong từ điển. Các bạn học sinh có ví dụ nào về tìm kiếm nhị phân thì có thể chia sẻ trên STEAMese Profile nhé. Ngoài hai thuật toán tìm kiếm tuần tự và nhị phân, chúng ta còn rất nhiều thuật toán tìm kiếm khác. Các bạn học sinh cùng tìm hiểu và chia sẻ trên STEAMese Profile nhé.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official

📍Donation: https://www.steamforvietnam.org/donation