›
›

Bài tập lớn môn Cấu trúc dữ liệu và giải thuật - Đề tài 1: Cài đặt công cụ kiểm tra chính tả spell checker

Download
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 1: CÀI ĐẶT CÔNG CỤ KIỂM TRA CHÍNH TẢ  
SPELL CHECKER  
1. Sơ lược bài toán  
Kiểm tra lỗi chính tả là một qui trình kiểm tra một từ có đúng chính tả hay không  
dựa trên một từ điển có sẵn. Đây là một qui trinh được sử dụng trong nhiều ứng dụng  
như các phần mềm soạn thảo văn bản hay là các từ điển điện tử.  
Việc cài đặt một chương trình kiểm tra lỗi chính tả cơ bản thì chỉ dựa thuần túy trên  
việc kiểm tra trong một từ điển được xây dựng sẵn trên một cấu trúc dữ liệu nào đó.  
Tuy nhiên có những chương trình còn thực hiện một thao tác là nếu như từ đưa vào  
không đúng chính tả thì sẽ đưa ra một số các từ đúng chính tả , gợi ý để người dùng  
có thể nhanh chóng sửa lại lỗi của mình. Việc làm này đòi hỏi thêm một số các thao  
tác kiểm tra.  
2. Yêu cầu  
• Yêu cầu cơ bản của bài tập này là lựa chọn một cấu trúc dữ liệu thích hợp để  
cài đặt một từ điển lưu trữ một số lượng lớn các từ. Khai báo và cài đặt các  
thuật toán cho phép thêm một từ mới vào từ điển, xóa một từ có sẵn trong từ  
điển.  
• Cài đặt một chương trình cho phép sử dụng một từ điển có sẵn được lưu trữ  
trong cấu trúc vừa xây dựng và thực hiện công việc kiểm tra xem một từ bất  
kỳ đưa vào có đúng chính tả hay không.  
• Tìm hiểu các giải thuật để thực hiện việc đưa ra một số từ gợi ý sửa lỗi chính  
tả và cài đặt giải thuật đó.  
3. Chú ý  
• Ngôn ngữ lập trình : Tùy chọn, ưu tiên sử dụng Java hoặc C++  
• Sinh viên cần phải viết các chương trình để kiểm thử kết quả hoạt động  
của các thao tác đã được cài đặt.  
• SInh viên nên cung cấp một giao diện để người dung có thể tự nhập dữ  
liệu đầu vào và kiểm thử các thao tác đã được cài đặt  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 2: CÁC GIẢI THUẬT SẮP XẾP  
1. Yêu cầu:  
Trong chương trình môn học Cấu trúc dữ liệu và giải thuật, chúng ta có xem xét một  
số các giải thuật khác nhau để thực hiện việc sắp xếp một dãy các số theo chiều tăng  
dần hay giảm dần.  
Hãy tìm hiểu phương pháp sắp xếp kiểu phân đoạn , sắp xếp kiểu vun đống , sắp xếp  
kiểu hòa nhập. So sánh các phương pháp sắp xếp trên.  
Cài đặt ít nhất 2 trong số các phương pháp sắp xếp đó, thiết lập giao diện đồ họa để  
minh họa các phương pháp sắp xếp.  
Đưa ra một qui trình kiểm thử để có thể đánh giá được các giải thuật đã được cài đặt  
bằng phương pháp thực nghiệm  
Khi cài đặt các phương pháp, chú ý đến việc cho phép hiển thị rõ từng bước thực hiện  
các giải thuật để thấy được đặc trưng của từng giải thuật.  
2. Chú ý  
• Ngôn ngữ lập trình : Tùy chọn  
• Sinh viên cần phải viết các chương trình để kiểm thử kết quả hoạt động  
của các thao tác đã được cài đặt.  
• SInh viên nên cung cấp một giao diện để người dùng có thể tự nhập dữ  
liệu đầu vào và kiểm thử các thao tác đã được cài đặt  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 3: CẤU TRÚC ĐỒ THỊ VÀ BÀI TOÁN TÌM ĐƯỜNG ĐI  
NGẮN NHẤT  
1. Sơ lược bài toán  
Hãy xem xét một bài toán thực tế về việc chuyển các gói dữ liệu trên một mạng  
máy tính. Một mạng máy tính bao gồm nhiều các router được nối với nhau thông qua  
các dây cáp. Một router có thể là nguồn, là đích hoặc là một trạm trung chuyển các  
gói dữ liệu trên mạng. Một mạng như vậy có thể được hình dung như là một đồ thị  
với các router là các đỉnh trong đồ thị và các đường nối giữa các router đóng vai trò  
như là những cung nối các đỉnh trong đồ thị. Một mạng máy tính tuân thủ theo giao  
thức OPSF tức là sử dụng đường đi ngắn nhất được xác định sử dụng giải thuật  
Dijkstra.  
Trong phạm vi của bài tập lớn này, hãy hình dung mạng là một đồ thị trọng số, vô  
hướng. Các cung của đồ thị sẽ được gắn một trọng số coi như là thời gian để chuyển  
một gói dữ liệu bất kỳ giữa hai router được biểu diễn bằng hai đỉnh đầu của cung.  
2. Yêu cầu : Các yêu cầu của bài tập lớn này như sau  
• Khai báo và cài đặt cấu trúc dữ liệu ĐỒ THỊ cho phép tạo lập và cập nhật một  
đồ thị trọng số vô hướng. Mỗi đỉnh của đồ thị được đặc trưng bởi một cái tên  
là một xâu ký tự chứa các chữ cái hoặc chữ số. Mỗi cung của đồ thị được xác  
lập bằng một cặp đỉnh và một trọng số là số thực.  
• Cài đặt các thao tác cơ bản trên đồ thị như sau  
o Khởi tạo một đồ thị ban đầu rỗng  
o InsertEdge(Vertex s, Vertex d, float weight) : bổ sung một cung có  
trọng số w giữa hai đỉnh s, d  
o InsertVertex(name) : thêm một đỉnh mới vào đồ thị  
o GetWeight(Vertex s, Vertex d): lấy ra trọng số của một cạnh  
o ShortestPath (Vertex s, Vertex d) : Tìm đường đi ngắn nhất từ s đến d  
trong ngữ cảnh hiện tại của đồ thị (cài đặt giải thuật Dijkstra)  
o Print: hiển thị hiện trạng của đồ thị  
Để sử dụng cho ứng dụng tìm đường truyền trong mạng, cài đặt các thao  
tác sau:  
o EdgeDown(Vertex s, Vertex d) : đánh dấu một cạnh nào đó đang được  
sử dụng, không dùng được  
o EdgeUp(Vertex s, Vertex d) Giải phóng việc sử dụng một cạnh  
o VertexDown(name) : Đánh dấu một đỉnh đang được sử dụng  
o VertexUp(name) : Giải phóng việc sử dụng một đỉnh, đỉnh này trở nên  
có thể dùng được  
3. Chú ý  
• Ngôn ngữ lập trình : Tùy chọn, ưu tiên sử dụng Java hoặc C++  
• Sinh viên cần phải viết các chương trình để kiểm thử kết quả hoạt động  
của các thao tác đã được cài đặt.  
• SInh viên nên cung cấp một giao diện để người dung có thể tự nhập dữ  
liệu đầu vào và kiểm thử các thao tác đã được cài đặt  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 4: CẤU TRÚC ĐỒ THỊ VÀ BÀI TOÁN TÌM CÂY KHUNG  
CỰC TIỂU  
1. Sơ lược bài toán  
Bài toán tìm cây khung cực tiểu trên cấu trúc đồ thị là một bài toán được áp dụng  
nhiều trong thực tế.  
Trong ngữ cảnh của cấu trúc đồ thị , một cây T là một đồ thị trong đó bất kỳ hai đỉnh  
trong đồ thị này đều được nối với nhau bằng một đường đi duy nhất.  
Cho một đồ thị G, một cây khung T1 trong G là một phần con của G mà nó là một  
cây và nó chứa tất cả các đỉnh trong đồ thị G. Một đồ thị có thể có nhiều cây khung.  
Nếu đồ thị đã cho ban đầu là một đồ thị trọng số thì chúng ta có thể tính trọng số của  
một cây khung bằng tổng tất cả các trọng số của các cạnh trong cây.  
Một cây khung có trọng số nhỏ nhất được gọi là cây khung cực tiểu của đồ thị  
2. Yêu cầu : Các yêu cầu của bài tập lớn này như sau  
• Khai báo và cài đặt cấu trúc dữ liệu ĐỒ THỊ cho phép tạo lập và cập nhật một  
đồ thị trọng số vô hướng. Mỗi đỉnh của đồ thị được đặc trưng số tự nhiên có  
giá trị duy nhất trong đồ thị. Mỗi cung của đồ thị được xác lập bằng một cặp  
đỉnh và một trọng số là số thực.  
• Cài đặt các thao tác cơ bản trên đồ thị như sau  
o Khởi tạo một đồ thị ban đầu rỗng  
o InsertEdge(Vertex s, Vertex d, float weight) : bổ sung một cung có  
trọng số w giữa hai đỉnh s, d  
o InsertVertex(name) : thêm một đỉnh mới vào đồ thị  
o GetWeight(Vertex s, Vertex d): lấy ra trọng số của một cạnh  
o Print: hiển thị hiện trạng của đồ thị  
• Tìm hiểu về hai thuật toán Kruskal và Prim để tìm một cây khung cực tiểu  
trong một đồ thị trọng số cho trước, so sánh hai giải thuật này về mặt hiệu  
năng  
• Cài đặt hai giải thuật đã tìm hiểu  
• Xây dựng một chương trình nhận đầu vào là một file text chứa thông tin về  
một đồ thị cho trước, tạo lập đồ thị và chỉ rõ từng bước hoạt động của giải  
thuật tìm cây khung cực tiểu đã cài đặt trên đồ thị tạo lập được  
3. Chú ý  
• Ngôn ngữ lập trình : Tùy chọn, ưu tiên sử dụng Java hoặc C++  
• Sinh viên cần phải viết các chương trình để kiểm thử kết quả hoạt động  
của các thao tác đã được cài đặt.  
• SInh viên nên cung cấp một giao diện để người dung có thể tự nhập dữ  
liệu đầu vào và kiểm thử các thao tác đã được cài đặt  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 5: CẤU TRÚC CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG  
1. Sơ lược bài toán  
• Cây nhị phân tìm kiếm là một cấu trúc đặc biệt, được sử dụng trong bài  
toán tìm kiếm. Mô tả về cây nhị phân tìm kiếm có thể tham khảo trong  
sách giáo trình của môn học. Cây AVL là một dạng đặc biệt của cây nhị  
phân tìm kiếm , mô tả về cây AVL cũng có trong sách giáo trình  
2. Yêu cầu  
Hãy khai báo một lớp đối tượng dạng cây nhị phân tìm kiếm có tên BST trong đó  
chấp nhận các nút của cây có thể nhận giá trị là các số nguyên sử dụng kiểu lưu  
trữ móc nối của cây. Cài đặt các thao tác sau trên cây nhị phân tìm kiêm:  
a. Create(): Khởi tạo một cây rỗng, thủ tục này sẽ trả ra một con trỏ trỏ tới  
gốc của cây, con trỏ ban đầu sẽ có giá trị không xác định  
b. Contain(T,x) : Thực hiện việc tìm kiếm , xác định xem trong cây đã có nút  
nào có giá trị x cho trước hay không? Nếu có, hãy chỉ ra chỉ số của nút  
chứa giá trị đó  
c. Insert(T, x) : Bổ sung một nút mới có giá trị là x cho trước vào một cây T.  
Trong quá trình bổ sung có thực hiện tìm kiếm, nếu giá trị x đã có trong  
cây, không cần tiến hành bổ sung  
d. Delete(T,x): Loại bỏ một nút có giá trị x cho trước ra khỏi cây T  
e. Print(T) : Thủ tục này cho phép hiển thị một cây T lên màn hình  
f. IsAVL(T) : Kiểm tra xem một cây T có phải là một cây AVL không?  
Phần mở rộng: Mở rộng thủ tục Insert để có thể đáp ứng được yêu cầu như đối  
với cây AVL (thực hiện các thao tác quay để đảm bảo tính cân bằng của cây)  
3. Chú ý  
• Ngôn ngữ lập trình : Tùy chọn, ưu tiên sử C, Java hoặc C++  
• Sinh viên cần phải viết các chương trình để kiểm thử kết quả hoạt động  
của các thao tác đã được cài đặt.  
• SInh viên nên cung cấp một giao diện để người dung có thể tự nhập dữ  
liệu đầu vào và kiểm thử các thao tác đã được cài đặt  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
BÀI TẬP LỚN MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  
ĐỀ TÀI 6: Các giải thuật cho bài toán đối sánh mẫu  
1. Sơ lược bài toán  
Đối sánh mẫu ( Pattern matching) là một bài toán tìm sự xuất hiện của một xâu ký  
tự mẫu (pattern) trong một văn bản. Bài toán này có thể được áp dụng trong một  
số lĩnh vực như tìm kiếm thông tin, xử lý văn bản , các chương trình soạn thảo  
văn bản.  
2. Yêu cầu  
Tìm hiểu 3 giải thuật cho bài toán đối sánh mẫu  
-
-
-
Giải thuật Naïve  
Giải thuật Knutt-Morris-Pratt (KMP)  
Giải thuật Boyer-Moore (BM)  
So sánh 3 giải thuật  
Cài đặt chương trình demo ít nhất 2 trong số 3 giải thuật trên,  
Chương trình demo cần cho phép người sử dụng nhập dữ liệu đầu vào một cách  
linh hoạt và cho người sử dụng nhìn thấy từng bước xử lý của giải thuật trong quá  
trình xác định vị trí xuất hiện của mẫu trong văn bản đầu vào.  
Cấu trúc dữ liệu và Giải thuật – TTM & KTMT K51 – Khoa CNTT – ĐHBKHN  
pdf 6 trang baolam 26/04/2022 6900
Download
Bạn đang xem tài liệu "Bài tập lớn môn Cấu trúc dữ liệu và giải thuật - Đề tài 1: Cài đặt công cụ kiểm tra chính tả spell checker", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_tap_lon_mon_cau_truc_du_lieu_va_giai_thuat_de_tai_1_cai.pdf