CHƯƠNG 1- TỔNG QUAN Do đó, trong việc mô hình hóa bài toán, cần phải phản ánh chính xác dữ liệu thực này và tổ chức, xây dựng một cấu trúc tối ưu để máy tính dễ dàng xử lý. Nhiệm vụ này được gọi là xây dựng cấu trúc dữ liệu cho bài toán trong thực tế. - Xây dựng các thao tác xử lý trên dữ liệu: Bắt đầu từ nhu cầu xử lý thực tế của mình, chúng ta cần tìm giải thuật phù hợp để xác định trình tự các thao tác máy tính cần thực hiện để đạt được kết quả mong muốn. Bước này được gọi là xây dựng giải thuật cho bài toán.
Khi giải quyết các vấn đề thực tế trên máy tính, ta thường tập trung vào việc xây dựng các thuật toán và ít chú trọng đến việc sắp xếp, tổ chức dữ liệu. Việc tổ chức dữ liệu đóng vai trò rất quan trọng trong tiến tình xây dựng chương trình. Các giải thuật phản ánh chính xác các thao tác xử lý trên dữ liệu trong khi đó đối tượng xử lý của giải thuật là dữ liệu. Bản thân dữ liệu chứa thông tin quan trọng để thực thi giải thuật.
Như công thức [5] trong hình 1.2 cho thấy, giải thuật và cấu trúc dữ liệu luôn luôn có mối quan hệ với nhau trong các dự án tin học. Data structures + Algorithms = Programs. 2-Mối quan hệ giữa cấu trúc dữ liệu và giải thuật Khi chọn lựa cấu trúc dữ liệu phù hợp với bài toán sẽ có giải thuật tương ứng với cấu trúc dữ liệu đó. Nếu cấu trúc dữ liệu thay đổi, thông thường thuật toán cũng thay đổi tương ứng.
Ngoài ra, cấu trúc dữ liệu tốt góp phần không nhỏ nhằm giúp giải thuật hoạt động tốt hơn, chính vì vậy ta có thể kết luận cấu trúc dữ liệu sẽ quyết định giải thuật. Các kiểu dữ liệu cơ bản Các kiểu dữ liệu cơ bản thường là các kiểu dữ liệu phi cấu trúc, đơn giản, điển hình là các giá trị như số nguyên, số thực, ký tự, chuỗi. Các kiểu dữ liệu này được tích hợp sẵn trong hầu hết các ngôn ngữ lập trình do tính phổ biến và tính đơn giản của chúng, cho phép người lập trình thao tác với chúng một cách dễ dàng. Như vậy, chúng thường được gọi là các kiểu dữ liệu định sẵn (dữ liệu tiền định).
Một số loại kiểu dữ liệu cơ bản sau: Kiểu dữ liệu số nguyên: Chứa số nguyên có dấu và số nguyên không dấu, với các kích thước:1 byte, 2 bytes hoặc 4 bytes. 4 CHƯƠNG 1- TỔNG QUAN Kiểu dữ liệu số thực: Đây là kiểu dữ liệu được tổ chức trong bộ nhớ và chứa dấu chấm động (số lẻ) thường có kích thước sau: 4 bytes, 6 bytes, 8 bytes hoặc 10 bytes. Kiểu dữ liệu ký tự: Dùng chuỗi 8 bit theo bộ mã ASCII để biểu diễn một ký tự trong máy tính. Kiểu ký tự có kích thước 1 byte và 2 bytes.
Kiểu dữ liệu chuỗi ký tự: Kiểu dữ liệu dạng chuỗi ký tự được tổ chức trong bộ nhớ máy tính bằng bảng mã ASCII của mỗi ký tự trong chuỗi đó. Kích thước của nó tùy vào ngôn ngữ lập trình hỗ trợ. Kiểu luận lý: Đây là kiểu dữ liệu logic có giá trị true hoặc false, thường có kích thước 1 byte. Các kiểu dữ liệu tiền định trong ngôn ngữ lập trình Python [13]: Bảng 1-Các kiểu dữ liệu định sẳn trong Python Kiểu dữ liệu Mô tả Kiểu số nguyên lưu trữ các giá trị số nguyên có dấu và không Kiểu int dấu, giá trị không giới hạn.
Kiểu float Lưu trữ các giá trị số thực. Kiểu complex Lưu trữ số phức bao gồm hai phần: phần thực và phần ảo. Kiểu str Lưu trữ các kí tự tạo thành chuỗi ký tự Lưu trữ tập các phần tử dữ liệu có thể thay đổi, nó thường lưu Kiểu list các phần tử cùng kiểu dữ liệu. Kiểu tuple Lưu trữ tập các phần tử cố định không thể thay đổi.
Range tức là khoảng, nó đại diện cho tập các giá trị số nguyên Kiểu range không thể thay đổi, thường dùng trong vòng lặp for. Là một loại bảng băm, hoạt động giống mảng kết hợp lưu trữ dữ Kiểu dict liệu dạng key-value. Là tập hợp không có thứ tự của các đối tượng duy nhất. Đây là Kiểu set một dạng bảng băm, ta có thể thêm hoặc xóa phần tử khỏi set.
Là kiểu set và không thể thay đổi được, các giá trị trong frozenset không thể thay đổi sau khi nó được tạo. Nó được sử Kiểu frozenset dụng chủ yếu làm khóa trong dictionary hoặc phần tử trong các set khác. Kiểu bool Lưu giá trị True hoặc False. Kiểu bytes Dùng để chứa chuỗi byte đơn không thể thay đổi.
Kiểu bytearray Chứa chuỗi các byte có thể thay đổi. Cho phép truy cập dữ liệu của một đối tượng hỗ trợ giao thức Kiểu memoryview đệm mà không cần sao chép. 5 CHƯƠNG 1- TỔNG QUAN Bảng 2 dưới đây mô tả các kiểu dữ liệu và các ví dụ minh họa đặc điểm của nó [13]: Bảng 2- Kiểu dữ liệu và ví dụ minh họa cho kiểu dữ liệu Kiểu dữ liệu Ví dụ str “Hello Word” int 560 float 3.25 complex 5 + 3j list [1, 2, 3] tuple (1, 2, 3) range range(10) dict {“name” : “Nam”, “age”: 20} set {“Apple”, “Samsung”, “Xiaomi”} frozenset frozenset({“Apple”, “Samsung”, “Xiaomi”}) bytes b“Hello” bytearray bytearray(5) memoryview memmoryview(bytes(5)) bool True Các kiểu dữ liệu có cấu trúc Kiểu dữ liệu có cấu trúc là kiểu dữ liệu được xây dựng trên một kiểu dữ liệu đã có, hoặc có thể xây dựng dựa trên một kiểu dữ liệu có cấu trúc khác. Ví dụ: Để mô tả một đối tượng sinh viên, thông tin và kiểu dữ liệu bao gồm: - Mã sinh viên: kiểu dữ liệu chuỗi ký tự - Tên sinh viên: kiểu dữ liệu chuỗi ký tự - Ngày sinh: kiểu dữ liệu ngày tháng - Nơi sinh: kiểu dữ liệu chuỗi ký tự - Điểm thi: kiểu dữ liệu số thực Đối với thông tin điểm thi: kiểu số thực, mã sinh viên: kiểu chuỗi ký tự; tên sinh viên: kiểu chuỗi ký tự; nơi sinh: kiểu chuỗi ký tự, ngoài ra, các thông tin khác đòi hỏi phải sử dụng các kiểu có cấu trúc như ngày sinh: kiểu ngày tháng.
Để thể hiện thông tin về ngày tháng năm sinh của một sinh viên ta cần phải xây dựng một cấu trúc dữ liệu trong ngôn ngữ lập trình Python như sau: 6 CHƯƠNG 1- TỔNG QUAN Tiếp theo, ta có thể xây dựng kiểu dữ liệu thể hiện thông tin về một sinh viên như sau: Phân tích và thiết kế giải thuật Trong quá trình giải một bài toán trên máy tính, đối với những bài toán khác nhau có thể có nhiều giải thuật khác nhau. Có những giải thuật được thiết kế đơn giản, dễ hiểu, dễ triển khai v.v… tuy nhiên thời gian thực hiện của giải thuật đó lớn và chiếm nhiều tài nguyên của máy tính. Ngược lại, với những giải thuật được thiết kế và lập trình rất phức tạp, nhưng thời gian thực thi chương trình cho kết quả nhanh hơn, ít chiếm dụng tài nguyên trên máy tính. Như vậy ta nên lựa chọn giải thuật nào để mang lại hiệu quả hơn? Đối với những chương trình có tần suất sử dụng thấp thì thời gian thực thi chương trình không phải là yếu tố quan trọng.
Các bài toán dạng này, thời gian để người phát triển chương trình xây dựng giải thuật là tiêu chí quan trọng hơn việc xem xét thời gian thực thi của chương trình cho nên những giải thuật có thiết kế đơn giản nên được lựa chọn. Ngược lại, có những chương trình có tần suất sử dụng cao thì thời gian thực thi của chương trình cần được chú trọng hơn nhiều so với thời gian được người lập trình sử dụng để thiết kế và xây dựng giải thuật. Khi đó, lựa chọn một giải thuật có thời gian thực thi nhanh hơn là một lựa chọn đúng đắn. Quá trình từ một bài toán cần được giải quyết đến chương trình hoàn chỉnh được thể hiện ở sơ đồ (hình 1.3) dưới đây: 7 CHƯƠNG 1- TỔNG QUAN Hình 1.
3- Quá trình từ bài toán thực tế đến chương trình Một vấn đề đặt ra là làm thế nào để đưa ra giải thuật để giải quyết bài toán? Sau đây là các phương pháp thiết kế giải thuật phổ biến: - Chia-để-trị (divide-and-conquer) - Quy hoạch động (dynamic programming) - Quay lui (backtracking): Đây là kỹ thuật vét cạn - Tham lam (greedy method): Được sử dụng trong trí tuệ nhân tạo (AI) Mặc dù hiện nay có nhiều kỹ thuật thiết kế giải thuật, tuy nhiên trong tài liệu tham khảo này, chúng tôi chỉ trình bày chi tiết kỹ thuật chia để trị, còn các phương pháp khác chỉ được nêu khái quát, người học sẽ tự tìm hiểu trong các tài liệu khác. Phương pháp chia để trị (divide- and-conquer) Chia để trị là phương pháp quan trọng được sử dụng rộng rãi để thiết kế giải thuật. Ý tưởng của phương pháp này là chia bài toán lớn thành các bài toán nhỏ, rồi lại chia các bài toán nhỏ này thành các bài toán con nhỏ hơn cho đến khi ta được các bài toán đã biết cách giải. Sau đó ta tổng hợp lại kết quả để được lời giải của bài toán ban đầu [10].
Để thực hiện kỹ thuật này, thông thường có hai cách thiết kế: • Thiết kế từ trên xuống (top-down design) • Thiết kế tinh chỉnh từng bước (stepwise refinement) Kỹ thuật thiết kế Top-Down Đây là phương pháp được mô tả dạng đệ quy dạng ngôn trình Python dưới đây: def DivideConquer (A,x): # tìm nghiệm x của bài toán A. if (A đủ nhỏ): # nếu bài toán A đủ nhỏ Solve (A) # giải quyết bài toán A else: # Chia bài toán A thành các bài toán con A1, A2,…, Am; for i in range (1, m+1): DivideConquer (Ai, xi); Kết hợp các nghiệm xi của các bài toán con Ai (i=1, …, m) để nhận được nghiệm x của bài toán A. 8 CHƯƠNG 1- TỔNG QUAN Ví dụ: Bài toán tìm từ trong từ điển, QuickSort, Tháp Hà Nội là dạng bài toán sử dụng kỹ thuật chia để trị. Phương pháp tinh chỉnh từng bước: for i in range(1,n): - Chọn số bé nhất trong các số - Đổi chỗ cho xi for i in range(1,n): - tg = x[i] - So sánh tg với các số từ xi+1 -> xn .