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