TêN ĐỀ TÀi tạo giao diệN ĐỒ HỌa tiếng việt cho thư viện zlib msđT



tải về 422 Kb.
trang6/7
Chuyển đổi dữ liệu14.11.2017
Kích422 Kb.
#1710
1   2   3   4   5   6   7

ĐỀ TÀI

BÀI Toán NGƯỜI BÁN HÀNG

(TSP : TRAVELING SALEMAN PROBLEM)


MSĐT : NL1TH-042



ĐẶC TẢ ĐỀ TÀI :

Bài toán : Một người bán hàng rong cần đi qua n thành phố. Xuất phát từ một thành phố nào đó, người bán hàng sẽ đi qua tất cả các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Hãy tìm một chu trình cho đường đi qua n thành phố của người bán hàng sao cho tổng khoảng cách là nhỏ nhất ?

YÊU CẦU CỦA ĐỀ TÀI :

Về lý thuyết :

- Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật

- So sánh một số giải thuật áp dụng cho bài toán TSP.

Về chương trình :

- Dữ liệu nhập vào dưới dạng file chứa các dòng dữ liệu: số thành phố, tọa độ đỉnh của trung tâm các thành phố.

- Thể hiện vị trí các thành phố trên màn hình đồ họa (khoảng cách giữa chúng được tính theo tọa độ các đỉnh).

- Hiển thị menu chọn các giải thuật :

. Thuật toán "vét cạn"

. Thuật toán “háu ăn” (Greedy)

- Tính chi phí tối ưu và so sánh thời gian thực hiện của mỗi giải thuật.

- Dịch chương trình sang file thực thi.


Ngôn ngữ lập trình sử dụng : Pascal, C, C ++

TÀI LIỆU THAM KHẢO


1) Nguyễn Văn Linh, Giáo trình Giải thuật – Khoa CNTT – ĐHCT :

http://www.dec.ctu.edu.vn/cit/gtrinh/gthuat/

2) A. Aho, J. Ullman, Data Structures and Algorithms

3) Wirth, Chương trình = Cấu trúc dữ liệu + Giải thuật

4) Nguyễn Trung Trực, Cấu trúc dữ liệu - ĐHBK tp HCM

5) Robert Sedgewick, Cẩm nang thuật toán 1,2

Ghi chú: Liên hệ trực tiếp với giáo viên hướng dẫn để biết thêm chi tiết.

ĐỀ TÀI

TRÒ CHƠI “NIM”


MSĐT : NL1TH-043





ĐẶC TẢ ĐỀ TÀI :

Bài toán “Nim” : 7 viên sỏi và 2 người

tham gia chơi. Đến lượt đi của mình, người

tham gia trò chơi phải chia đống sỏi thành

hai đống nhỏ có số lượng không bằng nhau.

Hai người chơi cứ luân phiên nhau chia nhỏ

đống sỏi như vậy. Người chơi sau cùng đến

lượt đi của mình không thể chia được nữa

thì xem như thua cuộc. Không gian bài toán


triển khai như hình bên (MIN – MAX ký hiệu

cho 2 người tham gia trò chơi)

YÊU CẦU CỦA ĐỀ TÀI :

Về lý thuyết :


- Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật

- Giải thuật cây trò chơi Min-Max kết hợp cắt giảm -(Alpha-Beta pruning)


Về chương trình :


- Cài đặt cấu trúc dữ liệu lưu trữ cây trò chơi

- Viết giao diện chương trình máy tính cho phép thực hiện trò chơi giữa 2 đấu thủ : Người – Người hoặc Người – Máy tính.

- Cài đặt giải thuật chơi cho máy theo thuật toán cây trò chơi Min-Max (có thể kết hợp giải thuật cắt giảm Alpha-Beta) để định trị cho nút gốc, chọn nước đi phù hợp kế tiếp.

- Hiển thị số lượng các đống sỏi được chia sau mỗi nước đi trên màn hình.

- Dịch chương trình sang file thực thi.

Ngôn ngữ lập trình sử dụng : Pascal, C, C ++

TÀI LIỆU THAM KHẢO


1) Nguyễn Văn Linh, Giáo trình Giải thuật – Khoa CNTT – ĐHCT :

http://www.dec.ctu.edu.vn/cit/gtrinh/gthuat/

2) A. Aho, J. Ullman, Data Structures and Algorithms

3) Wirth, Chương trình = Cấu trúc dữ liệu + Giải thuật

4) Robert Sedgewick, Cẩm nang thuật toán 1,2



Ghi chú: Liên hệ trực tiếp với giáo viên hướng dẫn để biết thêm chi tiết.

ĐỀ TÀI

CẮT TỈA CÂY TRÒ CHƠI đơn giẢn


MSĐT : NL1TH-044

ĐẶC TẢ ĐỀ TÀI :

Bài toán : Xét một cây trò chơi đơn giản với giá trị các nút lá là có sẵn. Hãy định giá trị của nút gốc cây trò chơi thông qua việc tìm kiếm và cắt tỉa các nhánh không cần phải xét đến trên cây ?



YÊU CẦU CỦA ĐỀ TÀI :

Về lý thuyết :


- Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật

- Giải thuật duyệt cây theo chiều sâu, giải thuật cắt giảm -(Alpha-Beta pruning)


Về chương trình :


- Cài đặt cấu trúc dữ liệu lưu trữ cây

- Áp dụng giải thuật Alpha-Beta pruning để cắt giảm các nhánh không cần xét trên cây và định trị nút gốc của cây.

+ Input : Nhập dữ liệu input dưới dạng file chứa các dữ liệu :

Dòng đầu tiên : Tên nút gốc (giả sử tầng chứa nút gốc luôn là Max)

Các dòng chứa thông tin về cây dưới dạng danh sách : phần tử đầu tiên là nút cha, các phần tử theo sau là các nút con theo thứ tự từ trái sang phải. Nếu ngay sau tên nút cha là một số thì đó là nút lá. Ví dụ mô tả file input cho một cây trò chơi như sau:


A

A B C

B D E F

C G

D 8

E 14

F 2

G 9

+ Output : Cây đã định trị nút gốc và các nhánh bị cắt giảm.

- Dịch chương trình sang file thực thi.


Ngôn ngữ lập trình sử dụng : Pascal, C, C ++

TÀI LIỆU THAM KHẢO


1) Nguyễn Văn Linh, Giáo trình Giải thuật – Khoa CNTT – ĐHCT :

http://www.dec.ctu.edu.vn/cit/gtrinh/gthuat/

2) A. Aho, J. Ullman, Data Structures and Algorithms

3) Wirth, Chương trình = Cấu trúc dữ liệu + Giải thuật

4) Robert Sedgewick, Cẩm nang thuật toán 1,2



Ghi chú: Liên hệ trực tiếp với giáo viên hướng dẫn để biết thêm chi tiết.


ĐỀ TÀI

CÁC GIẢI THUẬT Tìm kiẾM CHUỖI


MSĐT : NL1TH-045



ĐẶC TẢ ĐỀ TÀI :

Bài toán : Cài đặt và so sánh một số giải thuật tìm kiếm chuỗi mẫu p có chiều dài m trong một chuỗi nguồn a có chiều dài là n hoặc trong một tập tin văn bản cho trước.

YÊU CẦU CỦA ĐỀ TÀI :

Về lý thuyết :

- Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật

- Các giải thuật phổ biến trong việc tìm kiếm trên chuỗi như: giải thuật Brute-Force, giải thuật Knuth-Morris-Pratt, giải thuật Boyer-Moore (trình bày chi tiết trong quyển Cấu trúc dữ liệu - Nguyễn Trung Trực, ĐHBK tp HCM)

Về chương trình:

- Nhập vào một chuỗi mẫu p cần tìm kiếm và chọn lựa nguồn cần tìm dạng : chuỗi (nhập vào chuỗi nguồn) hay tập tin (nhập vào tên tập tin có chứa cả đường dẫn).

- Cài đặt các giải thuật tìm kiếm chuỗi :

+ Giải thuật Brute-Force

+ Giải thuật Knuth-Morris-Pratt

+ Giải thuật Boyer-Moore.

- Hiển thị thời gian tìm kiếm và kết quả tìm kiếm:

+ Vị trí của ký tự đầu tiên của lần tìm thấy đầu tiên

+ Số lần xuất hiện của ký tự trong chuỗi.

+ Thông báo “Không tìm thấy” nếu ngược lại

- Dịch chương trình sang file thực thi.

Ngôn ngữ lập trình sử dụng : Pascal, C, C ++

TÀI LIỆU THAM KHẢO


1) Nguyễn Văn Linh, Giáo trình Giải thuật – Khoa CNTT – ĐHCT :

http://www.dec.ctu.edu.vn/cit/gtrinh/gthuat/

2) A. Aho, J. Ullman, Data Structures and Algorithms

3) Wirth, Chương trình = Cấu trúc dữ liệu + Giải thuật

4) Nguyễn Trung Trực, Cấu trúc dữ liệu - ĐHBK tp HCM

5) Robert Sedgewick, Cẩm nang thuật toán 1,2

Ghi chú: Liên hệ trực tiếp với giáo viên hướng dẫn để biết thêm chi tiết.



tải về 422 Kb.

Chia sẻ với bạn bè của bạn:
1   2   3   4   5   6   7




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©tieuluan.info 2022
được sử dụng cho việc quản lý

    Quê hương