bài tập lớn CTDL-GT

Đề bài tập lớn môn học:
Cấu trúc dữ liệu và thuật toán

I. CÁC ĐỀ TÀI

01. ADT danh sách – Danh sách nối đơn (Singly linked list) và Danh sách nối đôi (Doubly linked list)
02. ADT ngăn xếp (Stacks) và ADT hàng đợi (Queues)
03. ADT đống (heap) và hàng đợi có ưu tiên (Priority heap)
04. ADT cây nhị phân tìm kiếm (Binary Search Tree)
05. ADT cây nhị phân cân bằng (AVL Tree)
06. ADT bảng băm (Hash Table)
07. Các thuật toán sắp xếp sử dụng phép so sánh: Heap sort, Merge Sort, Quick Sort
08. Các thuật toán sắp xếp đặc biệt
09. Các thuật toán tìm kiếm xâu mẫu
10. Tìm kiếm theo chiều sâu trên đồ thị có hướng: Phân loại cạnh và ứng dụng
11. Bài toán cây khung nhỏ nhất: Thuật toán Kruskal và thuật toán Prim
12. Bài toán đường đi ngắn nhất: Thuật toán Dijkstra

Hãy đọc kỹ các yêu cầu sau đây trước khi thực hiện đề tài:

II. YÊU CẦU
1) Nội dung báo cáo:
Đối với các đề tài từ 1-6, Báo cáo bao gồm các nội dung sau:
• Định nghĩa ADT cần tìm hiểu: Đối tượng cất giữ, Các phép toán cơ bản
• Cài đặt: Các cấu trúc dữ liệu để biểu diễn và cài đặt các phép toán. Xây dựng chương trình minh hoạ việc sử dụng các phép toán.
• Ứng dụng: Phát triển thuật toán giải quyết một bài toán trong đó có ứng dụng kiểu dữ liệu xây dựng (có thể chọn các bài toán minh hoạ trong bài giảng):
a. Phát biểu bài toán
b. Mô tả thuật toán giải và đánh giá độ phức tạp của thuật toán
c. Mô tả cài đặt chương trình
d. Ví dụ minh hoạ và hướng dẫn sử dụng.
Đối với các đề tài từ 7-12, Báo cáo bao gồm các nội dung sau:
• Mô tả thuật toán và các cấu trúc dữ liệu được sử dụng
• Cài đặt chương trình thực hiện các thuật toán
• Tiến hành thực nghiệm, để đưa ra nhận xét đánh giá các thuật toán

Báo cáo được soạn thảo trên MS Word có trang tiêu đề như qui định của Viện Công nghệ Thông tin và Truyền thông về trang tiêu đề của báo cáo thực tập (xem mẫu bìa ở phía dưới).
2) Ngôn ngữ lập trình: C, C++. Sử dụng bộ dịch: DEVCPP. Không được sử dụng thư viện của bộ dịch cung cấp sẵn về ADT mà đề tài yêu cầu cài đặt!
3) Đóng gói sản phẩm: File soạn thảo trên MS Word chứa báo cáo và các file chương trình nguồn được ghi vào trong thư mục có tên được đặt theo qui cách sau: DSA2011_xx_name, trong đó xx là chỉ số của nhóm đề tài xx ∈ {01, 02, …, 12}, còn name là tên sinh viên (nhóm sinh viên) thực hiện. Toàn bộ thư mục được nén lại thành 1 file cùng tên DSA2011_xx_name.???, với ??? là đuôi ngầm định của chương trình nén.
4) Giao nộp kết quả: Mỗi lớp tập trung các file nén ghi lại lên CD và giao nộp trực tiếp cho giáo viên.
5) Hạn nộp: Trước ngày thi kết thúc môn học 7 ngày.
6) Đánh giá: Điểm đánh giá sẽ cho từ 0 đến 3. Điểm này sẽ được cộng vào điểm thi kết thúc môn học với điều kiện điểm kết thúc môn học > 5, và điểm thi kết thúc môn học sẽ phải là số <= 10.
7) Cách tạo nhóm cùng thực hiện đề tài: Theo danh sách phân công của giáo viên, mỗi sinh viên sẽ phải thực hiện đúng đề tài được phân công. Những người được phân công làm cùng đề tài có thể tự lập nhóm nhỏ (tối đa là 3 người) để cùng thực hiện và nộp báo cáo chung.
Chú ý:
• Việc sao chép kết quả của người khác là bị cấm. Nếu bị phát hiện, các báo cáo có hiện tượng sao chép sẽ không được chấm điểm.
• Tuyệt đối không được đặt bất cứ tên file nào trong sản phẩm giao nộp bằng tiếng Việt có dấu.
• Các đề tài giao nộp không đúng qui cách sẽ không được chấm.

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Viện Công nghệ Thông tin và Truyền thông






BÀI TẬP LỚN MÔN HỌC
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT




Đề tài:
CÁC THUẬT TOÁN TÌM KIẾM XÂU MẪU




Sinh viên thực hiện:
1. Nguyễn Đức M. SHHV: 7777777
2. Cao Văn T. SHHV: 9999999
Mã lớp: 32658?
Giáo viên hướng dẫn: PGS Nguyễn Đức Nghĩa





HÀ NỘI – 2011