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.
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.
Ổ 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.
