BÀi tập và thực hành môn học lý thuyết đồ thị



tải về 257.57 Kb.
trang4/5
Chuyển đổi dữ liệu09.09.2017
Kích257.57 Kb.
#33017
1   2   3   4   5

Viết tiểu luận

ĐỀ TÀI 1:

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ THỂ HIỆN VIỆC BỐ TRÍ LỊCH THI CHO SINH VIÊN KHOA TOÁN – TIN HỌC.


ĐẶC TẢ ĐỀ TÀI :

Sử dụng phương pháp đồ thị để thể hiện việc bố trí lịch thi cho sinh viên khoa Toán – Tin học 7 môn thi trong 7 ngày.

Yêu cầu phải bố trí lịch thi sao cho hai môn thi của cùng một giáo viên không được rơi vào hai ngày liên tiếp nhau.

Biết rằng không có giáo viên nào có nhiều hơn 5 môn thi.



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

Về lý thuyết : Tìm hiểu và trình bày các khái niện cơ bản về :

- Đồ thị và các khái niệm cơ bản về đồ thị có hướng, đồ thị vô hướng.

- Các thủ tục (hàm) có liên quan đến giao diện của màn hình đồ họa.

- Đường đi và chu trình Hamilton.

- Thiết lập thuật toán của đề tài và minh họa kết quả bằng đồ thị Hamilton.

Về lập trình:

- Viết chương trình dựa vào thuật toán đã thiết lập.

- Giao diện thân thiện với người sử dụng.

- Kết quả cho ra là một đồ thị với màu sắc phân biệt.



MÔI TRƯỜNG CÀI ĐẶT

Ngôn ngữ sử dụng : C, C++, Visual C++, Visual Basic




ĐỀ TÀI 2:

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ GIẢI BÀI TOÁN DÂN GIAN (BÀI TOÁN 1).


ĐẶC TẢ ĐỀ TÀI :

Có một vị khách đến xin nhà vua ban cho một quả cam trong vườn ngự uyển. Nhà vua chấp thuận. Ông ta đến vườn mới hay phải qua 3 cổng lính canh.

Đến cổng thứ nhất, người lính canh bảo vị khách: " Vua ban cho thì anh cứ vào mà hái, nhưng lúc ra phải đưa cho ta một nữa số cam và thêm một trái".

Qua cổng thứ hai và thứ ba, hai lính canh cũng nói với anh như người lính canh thứ nhất. Vị khách phải hái bao nhiêu quả cam để lúc ra khỏi vườn còn được một quả trong tay?



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

Về lý thuyết : Tìm hiểu và trình bày các khái niện cơ bản về :

- Các thủ tục (hàm) có liên quan đến giao diện của màn hình đồ họa.

- Đồ thị và các khái niệm cơ bản về đồ thị có hướng, đồ thị vô hướng.

- Minh họa bài toán bằng đồ thị.

- Thiết lập thuật toán.

- Có thể mở rộng bài toán bằng cách cho người sử dụng thay đổi kết quả số lượng cam mà vị khách có được sau khi ra khỏi vườn.

Về lập trình:

- Viết chương trình dựa vào thuật toán đã thiết lập.

- Giao diện thân thiện với người sử dụng.

- Kết quả cho ra là một đồ thị với màu sắc phân biệt.

MÔI TRƯỜNG CÀI ĐẶT

Ngôn ngữ sử dụng : C, C++, Visual C++, Visual Basic




ĐỀ TÀI 3:

SỬ DỤNG PHƯƠNG PHÁP ĐỒ THỊ ĐỂ GIẢI BÀI TOÁN DÂN GIAN (BÀI TOÁN 2).


ĐẶC TẢ ĐỀ TÀI :

Có hai cha con người nông dân đi mua vé tàu hỏa. Người bán vé tàu hỏi: " Chú bé này bao nhiêu tuổi ?". Ông cha trả lời: "Con trai tôi tuổi gấp 5 lần em gái nó, mẹ nó tuổi gấp 6 lần tuổi nó. Tuổi tôi thì bằng tuổi của vợ và hai con tôi cộng lại. Còn mẹ tôi thì bằng tuổi của tất cả gia đình chúng tôi cộng lại". Người bán vé tàu nói: "Thôi đủ rồi! Con ông được miễn vé".

Dựa vào đâu mà người vé tàu miễn vé cho chú bé? Biết rằng, theo luật đường sắt thì trẻ em dưới 6 tuổi đi cùng người lớn sẽ được miễn vé.

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

Về lý thuyết : Tìm hiểu và trình bày các khái niện cơ bản về :

- Các thủ tục (hàm) có liên quan đến giao diện của màn hình đồ họa.

- Đồ thị và các khái niệm cơ bản về đồ thị có hướng, đồ thị vô hướng.

- Minh họa bài toán bằng đồ thị.

- Thiết lập thuật toán.

Về lập trình:

- Viết chương trình dựa vào thuật toán đã thiết lập.

- Giao diện thân thiện với người sử dụng.

- Kết quả cho ra là một đồ thị với màu sắc phân biệt.



MÔI TRƯỜNG CÀI ĐẶT

Ngôn ngữ sử dụng : C, C++, Visual C++, Visual Basic




ĐỀ TÀI 4:

CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ


ĐẶC TẢ ĐỀ TÀI :

Vận dụng các lý thuyết cơ bản về đồ thị để cài đặt chương trình cho phép biểu diễn đồ thị, kiểm tra tính liên thông và tìm đường đi ngắn nhất giữa 2 đỉnh cho trước bằng giải thuật Dijkstra, Ford-Bellman trên đồ thị vô hướng.



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

  • Lý thuyết:

      • Các thao tác cơ bản về đồ họa.

      • Các khái niệm về đồ thị có hướng và đồ thị vô hướng

      • Các cách biểu diễn đồ thị, các phương pháp tìm kiếm trên đồ thị (tìm theo chiều rộng và chiều sâu) và tính liên thông.

      • Các giải thuật có liên quan như: kiểm tra tính liên thông, tìm đường đi ngắn nhất.

      • Những cấu trúc dữ liệu cần thiết để cài đặt chương trình.

    • Chương trình:

Phải có những chức năng cơ bản sau:

      • Cập nhật dữ liệu về đồ thị.

      • Biểu diễn đồ thị trên màn hình.

      • Kiểm tra tính liên thông.

      • Cho phép tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ.


MÔI TRƯỜNG CÀI ĐẶT :

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

ĐỀ TÀI 5: CÁC GIẢI THUẬT TÌM CÂY PHỦ TỐI TIỂU


ĐẶC TẢ ĐỀ TÀI :

Vận dụng các lý thuyết cơ bản về đồ thị để cài đặt chương trình cho phép biểu diễn đồ thị, kiểm tra tính liên thông và tìm cây có trọng lượng nhỏ nhất bằng giải thuật Kruscal.


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

  • Lý thuyết:

      • Các thao tác cơ bản về đồ họa.

      • Các khái niệm về đồ thị có hướng và đồ thị vô hướng

      • Các cách biểu diễn đồ thị, các phương pháp tìm kiếm trên đồ thị (tìm theo chiều rộng và chiều sâu) và tính liên thông.

      • Các giải thuật có liên quan như: kiểm tra tính liên thông, giải thuật kiểm tra tính liên thông và giải thuật Kruscal tìm cây có trọng lượng nhỏ nhất.

      • Những cấu trúc dữ liệu cần thiết để cài đặt chương trình.

    • Chương trình:

Phải có những chức năng cơ bản sau:

      • Cập nhật dữ liệu về đồ thị.

      • Biểu diễn đồ thị trên màn hình.

      • Kiểm tra tính liên thông.

      • Cho phép tìm cây có trọng lượng nhỏ nhất.


MÔI TRƯỜNG CÀI ĐẶT :

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




tải về 257.57 Kb.

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




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

    Quê hương