Thiết kế và phân tích thuật toán

Cấu trúc dữ liệu và Giải thuật của Đỗ Xuân Lôi:

  • Chương 2. Thiết kế và phân tích giải thuật;
  • Mã giả được sử dụng trong bài học này và các bài học kế tiếp gọi là ngôn ngữ giả mã tựa PASCAL mục 1.3, chương 1.

1. Từ bài toán đến chương trình

Mô-đun hóa và việc giải quyết bài toán

Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán và chương trình để giải quyết chúng cũng ngày càng có quy mô lớn và càng khó khi thiết lập cũng như khi muốn tìm hiểu.

Một giải pháp là chia nhỏ bài toán lớn thành các bài toán nhỏ hơn. Điều đó có nghĩa là nếu xem bài toán cần giải quyết là một mô-đun lớn thì các bài toán nhỏ hơn có thể xem là mô-đun con và cứ tiếp tục phân chia cho đến khi một bài toán hay mô-đun không thể chia nhỏ được nữa. Ví dụ bài toán A có thể phân chia thành các bài toán B, C, D; bài toán B phân chia thành E, F,…

Phương pháp giải quyết bài toán kiểu này được gọi là phương pháp chia để trị (divide and conquer) và được thiết kế từ đỉnh xuống (top-down design). Đó là cách phân tích tổng quát toàn bộ vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra, rồi sau đó mới đi dần vào giải quyết các phần cụ thể một cách chi tiết hơn (vì vậy mà người ta còn gọi là cách thiết kế từ khái quát đến chi tiết).

Ví dụ một chương trình xử lý tệp (hay tập tin)

Phương pháp tinh chỉnh từng bước (Stepwise refinement)

Tinh chỉnh từng bước là phương pháp thiết kế thuật toán gắn liền với lập trình. Nó phản ánh tinh thần của quá trình mô-đun hóa bài toán kiểu và thiết kế kiểu top-down.

Thoạt đầu chương trình thể hiện thuật toán được trình bày bằng ngôn ngữ tự nhiên phản ánh ý chính của công việc cần làm sau đó được thể hiện bằng mã giả (pseudo code) rồi đến ngôn ngữ lập trình. Hay nói cách khác, phương pháp tinh chỉnh từng bước sẽ đi từ mức “làm cái gì” đến mức “làm thế nào”, ngày càng sát với các chức năng ứng với các câu lệnh của ngôn ngữ lập trình đã chọn.

Bài toán ví dụ: Sắp xếp một dãy n số nguyên khác nhau theo thứ tự tăng dần.

* Có thể phác thảo thuật toán như sau:

Từ dãy các số nguyên chưa được sắp xếp, chọn ra số nhỏ nhất, đặt nó vào cuối dãy đã được sắp xếp.

Cứ lặp lại quy trình đó cho tới khi dãy chưa được sắp xếp trở thành rỗng.

Hình dung cụ thể hơn một chút ta thấy, thoạt đầu dãy số chưa được sắp xếp chính là dãy số đã cho. Dãy số đã được sắp xếp còn rỗng, chưa có phần tử nào. Vậy thì nếu chọn được số nhỏ nhất đầu tiên và đặt vào cuối dãy đã được sắp thì cũng chính là đặt vào vị trí đầu tiên của dãy này. Nhưng dãy này đặt ở đâu?

Thế thì phải hiểu dãy số mà ta sẽ sắp xếp được đặt tại chỗ cũ hay đặt chỗ khác? Điều đó đòi hỏi phải chi tiết hơn về cấu trúc dữ liệu và cấu trúc lưu trữ của dãy số đã cho.

Trước hết ta ấn định: dãy số cho ở đây được coi như dãy các phần tử của một vectơ (sau này ta nói: nó có cấu trúc mảng một chiều) và dãy này cần được lưu trữ bởi một vectơ lưu trữ gồm n từ máy kế tiếp ở bộ nhớ trong (a1, a2,…,an) mỗi từ ai lưu trữ một phần tử thứ i (1 <= i <= n) của dãy số.

Ta cũng quy ước: dãy số được sắp xếp rồi vẫn để tại chỗ cũ như đã cho.

Vậy thì việc đặt “số nhỏ nhất” vừa được chọn, ở một lượt nào đó, vào cuối dãy đã được sắp xếp phải thực hiện bằng cách đổi chỗ với số hiện đang ở vị trí đó (nếu như nó khác số này). Ta có bước tinh chỉnh đầu tiên.

Bước tinh chỉnh 1

For i := 1 to n do begin
– Xét từ ai đến an để tìm số nhỏ nhất aj
– Đổi chỗ giữa ai và aj
End

Tới đây ta thấy có hai nhiệm vụ con cần làm rõ thêm:

  • NV1: Tìm số nguyên nhỏ nhất aj trong các số từ ai đến an
  • NV2: Đổi chỗ giữa aj và ai

NV1 có thể thực hiện bằng cách: Thoạt tiên coi ai là số nhỏ nhất tạm thời; lần lượt so sánh ai với ai+1, ai+2, v.v… Khi thấy số nào nhỏ hơn thì lại coi đó là số nhỏ nhất mới. Khi đã so sánh với an rồi thì số nhỏ nhất sẽ được xác định.

Nhưng xác định bằng cách nào? Có thể chỉ ra chỗ của nó, nghĩa là nắm được chỉ số của phần tử ấy. Ta có bước tinh chỉnh tiếp theo.

Bước tinh chỉnh 2.1

j := i

For k := j + 1 to n do

                If ak < aj then j := k;

Với nhiệm vụ thứ hai (NV2) thì có thể giải quyết tương tự như khi ta muốn chuyển hai thứ rượu trong hai ly, từ ly nọ sang ly kia: ta sẽ phải dùng ly thứ ba (không đựng gì) B để làm ly trung chuyển. Ta có bước tinh chỉnh cuối cùng.

Bước tinh chỉnh 2.2

B := ai; ai := aj; aj := B;

Sau các bước tinh chỉnh, thuật toán sắp xếp được viết lại như sau:

Procedure SORT (A, n)

For i := 1 to n do begin
{Chọn số nhỏ nhất}  j := i;
	For k := j + 1 to n do
		If A[k] < A[j] then j := k;
{Đổi chỗ}  B := A[i]; A[i] := A[k]; A[j] := B;
	end
Return

Bạn có vấn đề gì về bài học này không?

Giới thiệu Cấu trúc dữ liệu và thuật toán

Thuật toán (Algorithm) là gì?

Theo thuật ngữ lập trình máy tính, thuật toán là một tập hợp các hướng dẫn hay lệnh (statement) được xác định rõ ràng để giải quyết một vấn đề cụ thể. Hay nói cách khác, thuật toán nhận một tập hợp đầu vào (input) và tạo một đầu ra (output) mong muốn. Ví dụ, một thuật toán để cộng hai số sẽ bao gồm các hướng dẫn:

  • Nhận hai số đầu vào
  • Cộng các số bằng toán tử +
  • Hiển thị kết quả (đầu ra)

Một thuật toán tốt sẽ thỏa mãn các yếu tố sau:

  • Đầu vào và đầu ra phải được xác định chính xác.
  • Mỗi bước trong thuật toán phải rõ ràng và không mơ hồ.
  • Thuật toán nên hiệu quả nhất trong số nhiều cách khác nhau để giải quyết một vấn đề.
  • Một thuật toán không được bao gồm mã máy tính. Thay vào đó, thuật toán nên được viết theo cách mà nó có thể được sử dụng trong các ngôn ngữ lập trình khác nhau.

Các thuật toán ví dụ

Thuật toán 1: Cộng hai số do người dùng nhập

Bước 1: Bắt đầu
Bước 2: Khai báo các biến num1, num2 và sum
Bước 3: Đọc giá trị num1 và num2
Bước 4: Cộng num1 và num2 và gán kết quả đến sum
 sum ← num1 + num2
Bước 5: Hiển thị sum
Bước 6: Dừng lại

Thuật toán 2: Tìm số lớn nhất trong ba số

Bước 1: Bắt đầu
Bước 2: Khai báo các biến a, b, c
Bước 3: Đọc các biến a, b và c
Bước 4: Nếu a> b
   Nếu a> c
      Hiển thị a là số lớn nhất
   Khác 
      Hiển thị c là số lớn nhất
 Khác
   Nếu b> c
      Hiển thị b là số lớn nhất
   Khác
      Hiển thị c là số lớn nhất
Bước 5: Dừng lại

Cấu trúc dữ liệu (Data structure) là gì?

Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở còn gọi là dữ liệu nguyên tử (atoms). Đó có thể là một số nguyên, một số thực, một kí tự,… Trên cơ sở của các dữ liệu nguyên tử, các cách thức khả dĩ theo đó liên kết chúng lại với nhau, sẽ dẫn đến các cấu trúc dữ liệu (data structures) khác nhau.

Cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ gọi là cấu trúc lưu trữ (storage structure). Có thể có nhiều cấu trúc lưu trữ khác nhau cho một cấu trúc dữ liệu, cũng như có thể có những cấu trúc dữ liệu khác nhau mà được thể hiện trong bộ nhớ bởi cùng một kiểu cấu trúc lưu trữ. Khi đề cập đến cấu trúc lưu trữ, chúng ta cũng cần phân biệt cấu trúc lưu trữ tương ứng bộ nhớ trong – lưu trữ trong, hay ứng với bộ nhớ ngoài – lưu trữ ngoài. Chúng có những đặc điểm riêng kéo theo các cách xử lý cũng khác nhau.

Lưu ý: Các câu từ trên được trích từ cuốn sách kinh điển 
Cấu trúc dữ liệu và giải thuật của tác giả Đỗ Xuân Lôi, 
nhà xuất bản Đại học Quốc gia Hà Nội.

Một cấu trúc dữ liệu được sử dụng để lưu trữ và tổ chức dữ liệu trên máy tính để nó có thể được truy cập và cập nhật một cách hiệu quả.

Tùy thuộc vào yêu cầu và dự án của bạn, điều quan trọng là chọn cấu trúc dữ liệu phù hợp cho dự án của bạn. Ví dụ: nếu bạn muốn lưu trữ dữ liệu tuần tự trong bộ nhớ, thì bạn có thể sử dụng cấu trúc dữ liệu Mảng (Array).

Các loại cấu trúc dữ liệu

Về cơ bản, cấu trúc dữ liệu được chia thành hai loại:

  • Cấu trúc dữ liệu tuyến tính (Linear data structure): Trong cấu trúc dữ liệu tuyến tính, các phần tử được sắp xếp tuần tự. Vì các phần tử được sắp xếp theo thứ tự cụ thể nên chúng rất dễ thực hiện. Tuy nhiên, khi độ phức tạp của chương trình tăng lên, cấu trúc dữ liệu tuyến tính có thể không phải là lựa chọn tốt nhất vì sự phức tạp trong hoạt động xử lý. Ví dụ về cấu trúc dữ liệu tuyến tính là Mảng (Array), Ngăn xếp (Stack), Hàng đợi (Queue) và Danh sách liên kết (Linked list). Trong đó cấu trúc Mảng cấu trúc được định nghĩa trước (cấu trúc dữ liệu tiền định – predefined data structure) trong các ngôn ngữ lập trình; các cấu trúc Ngăn xếp, Hàng đợi và Danh sách liên kết sẽ được đề cập chi tiết trong khóa học này.  
  • Cấu trúc dữ liệu phi tuyến tính (Non linear data structure): Không giống như cấu trúc dữ liệu tuyến tính, các phần tử trong cấu trúc dữ liệu phi tuyến tính không nằm trong bất kỳ trình tự nào. Thay vào đó, chúng được sắp xếp theo thứ bậc trong đó một phần tử sẽ được kết nối với một hoặc nhiều phần tử. Các ví dụ về cấu trúc này gồm Đồ thị (Graph) và Cây (Tree) sẽ được bàn chi tiết trong khóa học này.

So sánh Cấu trúc dữ liệu tuyến tính  và Cấu trúc dữ liệu phi tuyến tính

Cấu trúc dữ liệu tuyến tínhCấu trúc dữ liệu phi tuyến tính
Các phần tử dữ liệu được sắp xếp theo thứ tự tuần tự, nối tiếp nhau.Các phần tử dữ liệu được sắp xếp theo thứ tự không tuần tự (theo cách phân cấp).
Tất cả các phần tử dữ liệu chỉ xuất hiện trên cùng một mức hay cấp.Các phần tử dữ liệu hiện diện ở các mức hay cấp khác nhau.
Có thể được duyệt qua trong một lần chạy. Có nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên, chúng ta có thể duyệt qua tất cả các phần tử một cách tuần tự trong một lần.Yêu cầu nhiều lần chạy. Có nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên thì có thể không thể duyệt qua tất cả các phần tử chỉ trong một lần.
Việc sử dụng bộ nhớ không hiệu quả.Các cấu trúc khác nhau sử dụng bộ nhớ theo những cách hiệu quả khác nhau tùy theo nhu cầu.
Độ phức tạp về thời gian tăng theo kích thước dữ liệu.Độ phức tạp về thời gian tương tự cấu trúc tuyến tính.

Tại sao phải học cấu trúc dữ liệu và thuật toán?

Lập trình là tất cả về cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để lưu giữ dữ liệu trong khi các thuật toán được sử dụng để giải quyết vấn đề bằng cách sử dụng dữ liệu đó.

Cấu trúc dữ liệu và thuật toán đi qua các giải pháp cho các vấn đề tiêu chuẩn một cách chi tiết và cung cấp cho bạn cái nhìn sâu sắc về mức độ hiệu quả của việc sử dụng từng vấn đề trong số chúng. Nó cũng dạy bạn khoa học về đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn chọn tốt nhất trong số các lựa chọn khác nhau.

Phát triển phần mềm liên quan đến việc học các công nghệ mới hàng ngày. Bạn có thể tìm hiểu hầu hết các công nghệ này khi sử dụng chúng trong một trong các dự án của mình. Tuy nhiên, nó không phải là trường hợp với các thuật toán.

Nếu bạn không biết rõ về các thuật toán, bạn sẽ không thể xác định được liệu bạn có thể tối ưu hóa mã bạn đang viết ngay bây giờ hay không. Bạn phải biết trước về chúng và áp dụng chúng ở những nơi có thể và quan trọng.

Bạn có vấn đề gì về bài học này không?

Nhập môn CSS

1. Làm quen CSS


Trong bài này chúng ta sẽ tìm hiểu về định nghĩa CSS, cú pháp CSS, các kiểu CSS, bộ chọn (Selector) và làm quen một vài thuộc tính CSS cơ bản.



Bạn có vấn đề gì về bài học này không?

Một nhập môn về ngôn ngữ HTML


Kiến thức trọng tâm

Trong bài học này chúng ta sẽ tìm hiểu về HTTP Request và HTTP Response, Request Header, Response Header, Status Code, công cụ Inspect từ các trình duyệt web, HTML DOM, cấu trúc cơ bản của một tài liệu HTML, trình duyệt Web (Web Browser).
Chúng ta cũng tìm hiểu về môi trường Visual Studio Code và các môi trường trực tuyến. Cuối cùng, chúng ta sẽ làm quen với các thẻ HTML cơ bản.



Bạn có vấn đề gì về bài học này không?

Các khái niệm cơ bản


Kiến thức trọng tâm

Trong bài học này chúng ta sẽ tìm hiểu về WWW (World Wide Web), URL (Uniform Resource Locator), HTTP (HyperText Transfer Protocol) / HTTPS, địa chỉ IP, tên miền (Domain Name), DNS (Domain Name System), trình duyệt Web (Web Browser), máy chủ Web (Web Server), HTML (Hypertext Markup Language) và Github Pages.



Bạn có vấn đề gì về bài học này không?

Mô hình Cơ sở dữ liệu quan hệ (Mức Logic / Vật lý)


Kiến thức trọng tâm

Trong bài này sẽ trình bày mô hình Cơ sở dữ liệu quan hệ mức Logic bao gồm các thành phần cơ bản: Bảng (Table), Cột (Column) – Kiểu dữ liệu (Data Type), Hàng (Row), Ràng buộc khóa chính (Primary Key Constraint), Ràng buộc tham chiếu (Referential Constraint), Ràng buộc nghiệp vụ (Business Rule), Bảng trung gian (Intersection Table), Ràng buộc toàn vẹn (Integrity Constraint): Ràng buộc NULL, Ràng buộc CHECK.




Bạn có vấn đề gì về bài học này không?