Đọc truyện lí thuyết cấu trúc dữ liệu và giải thuật - lí thuyết cấu trúc dữ liệu và giải thuật

lí thuyết cấu trúc dữ liệu và giải thuật

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

I. Phần lý thuyết

1) Trình bày mối quan hệ giữa cấu trúc dữ liệu và giải thuật?

Trả lời:

Giải thuật chỉ phản ánh các phép xử lý, còn đối tượng để xử lý trên máy tính chính là dữ liệu, chúng biểu diễn các thong tin cần thiết cho bài toán như dữ liệu vào, dữ liệu ra và các kết quả trung gian. Không thể nói tới giải thuật mà không nghĩ tới nó tác động nên dữ liệu nào. Còn xét tới dữ liệu thì phải hiểu dữ liệu ấy cần được tác động bởi giải thuật nào để đưa tới kết quả mong.

Giữa CTDL và GT có mối quan hệ mật thiết. Có thể coi chúng như hình với bóng. Không thể nói tới cái này mà không nhắc đến cái kia.

Do đó cần nghiên cứu các CTDL đi đôi với việc xác lập các giải thuật xử lý trên các cấu trúc ấy.

2) Trình bày sự khác nhau giữa cấu trúc dữ liệu và cấu trúc lưu trữ.

Trả lời:

Cấu trúc lưu trữ là các biểu diễn dữ liệu trong bộ nhớ. Có thể có nhiều cấu trúc lưu trữ khác nhau cho cùng một cấu trúc dữ liệu, cũng như có thể có những cấu trúc dữ liệu khác nhau mà được thể hiện trọng một bộ nhớ bởi cùng một kiểu cấu trúc lưu trữ.

3) Các cấu trúc dữ liệu tiền định của ngôn ngữ có đủ đáp ứng mọi yêu cầu về tổ chức dữ liệu hay không? Cho ví dụ minh họa.

Trả lời:

Không phải các CTDL tiền định của ngôn ngữ lập trình được sử dụng đều đáp ứng được nhu cầu cần thiết về dữ liệu của người dùng.

VD: Xử lý hồ sơ học sinh, sinh viên mà dùng ngôn ngữ PASCAL, thì ta có thể tổ chức mỗi hồ sơ dưới 1 dạng bản ghi bao gồm nhiều thành phần, mỗi thành phần của bản ghi đó ta gọi là trường sẽ không nhất thiết phải dùng kiểu. (VD: Trường: “Họ và tên” có kiểu kí tự. Trường: “Ngày sinh” có kiểu số nguyên)

Nhưng nếu dùng ngôn ngữ FORTRAN thì lại gặp khó khăn. Ta chỉ có thể mô phỏng các mục của hồ sơ dưới dạng vectơ hay ma trận và do đó việc xử lý sẽ phức tạp hơn.

4) Việc chia bài toán thành những bài toán nhỏ có những thuận lợi gì?

Trả lời:

Các bài toán giải được trên máy tính điện tử ngày càng đa dạng và phức tạp. Các giải thuật và chương trình để giải chúng cũng ngày càng có quy mô lớn và càng khó khi thiết lập cũng như khi muốn tìm hiểu. Nhưng mọi việc sẽ trở lên đơn giản hơn nếu như có thể phân chia bài toán lớn thành các bài toán nhỏ.

Việc chia bài toán thành những bài toán nhỏ thì việc tìm hiểu cũng như sửa chữa chỉnh lý chương trình sẽ dễ dàng hơn.

5) Trình bày nguyên tắc thiết kế từ đỉnh xuống (Top – Down), cho ví dụ minh họa.

Trả lời:

Nguyên tắc: Phân tích tổng quát toàn bộ vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra, để đề cập đến công việc chủ yếu, rồi sau đó mới đi dần vào giải quyết các phần cụ thể một cách chi tiết hơn.

VD: Ta phải quản lý và bào trì các hồ sơ về học bổng của các sinh viên ở diện được tài trợ, đồng thời thường xuyên phải lập báo cáo tổng kết để trình lên hiệu trưởng.

Do đó, chương trình lập ra phải tạo điều kiện cho người sử dụng giải quyết được các vấn đề sau:

- Tìm lại và hiển thị được bất kì bản ghi của bất kì sinh viên nào tại thiết bị cuối của người dùng.

- Cập nhật được bản ghi của 1 sinh viên cho trước bằng các thay đổi điểm trung bình, điểm đạo đức, khoản tiền tài trợ, nếu cần.

- In bản tổng kết chứa những thong tin hiện thời gồm số hiệu, điểm trung bình, điểm đạo đức, khoản tiền tài trợ.

Từ những nhận định trên, giải thuật sẽ phải giải quyết các vấn đề sau:

- Những thông tin về sinh viên được học bổng, lưu trên đĩa phải được đọc vào bộ nhớ trong để có thế xử lý.

- Xử lý các thông tin này để tạo ra kết quả mong muốn.

- Sao chép các thông tin đã được cập nhật vào tệp trên đĩa để lưu trữ cho việc xử lý sau này.

Các nhiệm vụ ở mức đầu này thường phức tạp, cần phải chia thành các nhiệm vụ con. Chẳng hạn nhiệm vụ xử lý thông tin có thể phân thành 3:

- Tìm lại bản ghi của một sinh viên cho trước

- Cập nhật thông tin trong bản ghi sinh viên

- In bảng tổng kết những thông tin về các sinh viên được học bổng

Những nhiệm vụ con này cũng có thể chia thành nhiệm vụ nhỏ hơn…

6) Trình bày phương pháp tinh chỉnh từng bước.

Trả lời:

Tinh chỉnh từng bước là phương pháp thiết kế giải thuật gắn liền với lập trình. Nó phản ánh tinh thần của quá trình mô – dun hóa bài toán và thiết kế kiểu top – down.

Ban đầu chương trình thể hiện giải thuật được trình bày bằng ngôn ngữ tự nhiên phản ánh ý chính của công việc cần làm. Từ các bước sau, những lời, những ý đó sẽ được chi tiết hóa dần dần tương ứng với những công việc nhỏ hơn. Đó là các bước tinh chỉnh. Sự tinh chỉnh sẽ được hướng về phía ngôn ngữ lập trình mà ta chọn.

Quá trình thiết kế giải thuật và phát triển chương trình sẽ được thể hiện dần dần từ dạng ngôn ngữ tự nhiên, qua giả ngôn ngữ rồi đến ngôn ngữ lập trình và đi từ mức “làm cái gì” đến mức “làm thế nào”, ngày càng sát với các chức năng ứng với các câu lệnh của ngôn ngữ lập trình đã chọn. Dữ liệu trong quá trình này cũng được “tinh chế” dần dần từ dạng cấu trúc đến dạng lưu trữ để cài đặt cụ thể.

7) Trình bày phân tích thời gian thực hiện giải thuật.

Trả lời:

Với 1 bài toán, không phải chỉ có 1 giải thuật. Do đó đòi hỏi phải chọn 1 giải thuật đưa tới kết quả nhanh.

Thời gian thực hiện giải thuật phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần được chú ý trước tiên là kích thước của dữ liệu vào thì thời gian thực hiện T của 1 giải thuật cần được biểu diễn như 1 hàm của n: T(n).

Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện; nhưng những yếu tố này không đồng đều với mọi loại máy tính trên đó cài đặt giải thuật, vì vậy không thể dựa vào chúng để xác lập T(n). Nghĩa là T(n) không thể biểu diễn thành đơn vị thời gian bằng giây, bằng phút…được. Tuy nhiên nếu như thời gian thực hiện của một giải thuật là T1(n) = cn2 và thời gian thực hiện một giải thuật khác T2(n) = kn, thì khi n khá lớn, thời gian thực hiện T2 rõ ràng ít hơn với giải thuật T1.

Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan tới máy như vậy sẽ dẫn tới khái niệm về độ phức tạp vê thời gian của giải thuật.

8) Trình bày xác định độ phức tạp tính toán giải thuật (phép toán tích cực, qui tắc tổng, qui tắc nhân, cho ví dụ minh họa)

Trả lời:

- Phép toán tích cực: Là phép toán thuộc giải thuật mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác, hay số lần thực hiện nó không kém gì cách thực hiện nó.

- Qui tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện của 2 đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 kế tiếp nhau sẽ là:

T1(n) + T2(n) = O(max(f(n), g(n)))

VD : 1 chương trình có 3 bước thực hiện mà thời gian thực hiện từng bước : O(n2), O(n3) và O(nlog2n) thì thời gian thực hiện 2 bước đầu là O(max(n2, n3)) = O(n3). Thời gian thực hiện chương trình sẽ là O(max(n3, nlog2n)) = O(n3)

- Qui tắc nhân: Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là : T1(n)T2(n) = O(f(n)g(n))

VD : Câu lệnh gán: x := x + 1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1).

Câu lệnh: for i :=1 to n do x :=x+1 ;

Có thời gian thực hiện O(n.1) = O(n)

Bạn đang đọc truyện trên: Truyen2U.Pro

Trước Sau

#art