BÀi tập và thực hành môn học lý thuyết đồ thị
ĐỀ TÀI 6: BÀI TOÁN TỔ CHỨC THI CÔNG
tải về 257.57 Kb.
|
- Điều hướng trang này:
- ĐỀ TÀI 7: BÀI TOÁN QUẢN LÝ DỰ ÁN
- ĐỀ TÀI 8: BÀI TOÁN “8 QUÂN HẬU”
- Ngôn ngữ lập trình sử dụng : C, C ++ , Visual C ++
- ĐỀ TÀI 10: BÀI TOÁN PHÂN BỐ KÊNH TRUYỀN HÌNH TẠI ĐBSCL
- ĐỀ TÀI 13: XÂY DỰNG HỆ THỐNG KẾT NỐI MẠNG CỦA CÁC TRƯỜNG ĐẠI HỌC TRONG THÀNH PHỐ VỚI CHI PHÍ THẤP NHẤT
- ĐỀ TÀI 14: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI GIAO HÀNG
- ĐỀ TÀI 15: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI ĐƯA THƯ
ĐỀ TÀI 6: BÀI TOÁN TỔ CHỨC THI CÔNGĐẶ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ị, biểu diễn đồ thị sau khi xếp hạng, xác định các thời điểm sớm nhất, trễ nhất của từng công việc, thời gian hoàn thành công trình và vẽ sơ đồ GANT thể hiện kế hoạch hoàn thành công trình. YÊU CẦU CỦA ĐỀ TÀI :
Phải có những chức năng cơ bản sau:
MÔI TRƯỜNG CÀI ĐẶT : Ngôn ngữ lập trình sử dụng: C hay C ++ ĐỀ TÀI 7: BÀI TOÁN QUẢN LÝ DỰ ÁNĐẶ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ị, biểu diễn đồ thị sau khi xếp hạng, xác định các thời điểm sớm nhất, trễ nhất của từng công việc, thời gian hoàn thành công trình và vẽ sơ đồ GANT thể hiện kế hoạch hoàn thành công trình. YÊU CẦU CỦA ĐỀ TÀI :
Phải có những chức năng cơ bản sau:
MÔI TRƯỜNG CÀI ĐẶT : Sử dụng: MS . PROJECT 2003 ĐỀ TÀI 8: BÀI TOÁN “8 QUÂN HẬU”ĐẶC TẢ ĐỀ TÀI : Bài toán : Đặt 8 quân hậu trên bàn cờ vua 8 8 sao cho không có quân hậu nào có thể tấn công được con khác (theo luật chơi cờ vua), nghĩa là phải đặt các quân hậu sao cho không có hàng, cột hoặc đường chéo nào trên bàn cờ có hơn 1 quân hậu. Chẳng hạn, một cách đặt quân hậu đúng như sau :
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 tìm kiếm sâu kết hợp quay lui (Backtracking)
- Cài đặt cấu trúc dữ liệu tổ chức bàn cờ. - Cài đặt thuật toán tìm kiếm sâu kết hợp quay lui theo nguyên tắc : Trước tiên, đặt quân hậu vào ô thứ nhất của cột 1, rõ ràng tất cả các ô của cột đó đã bị khống chế nên không thể đặt quân hậu khác. Đặt tiếp một quân hậu vào cột thứ hai, hai ô đầu của cột đó đã bị cấm bởi quân hậu thứ nhất, do vậy ta đặt quân hậu vào ô thứ ba. Tiếp tục với cột thứ ba, ô đầu tiên có thể đặt quân hậu của cột này là ô thứ năm … Tiếp tục với các cột còn lại trên bàn cờ cho đến khi tìm được một lời giải đúng. - Hiển thị bàn cờ sau mỗi nước đi. - Dịch chương trình sang file thực thi. Ngôn ngữ lập trình sử dụng : C, C ++, Visual C++ĐỀ TÀI 9: BÀI TOÁN “QUÂN Mà ĐI TUẦN”ĐẶC TẢ ĐỀ TÀI : Bài toán : Trên bàn cờ vua 8 8, một quân mã được phép đi theo luật cờ vua. Vị trí đầu tiên của quân mã đặt tại một ô nào đó. Hãy tìm cách di chuyển quân mã qua tất cả các ô của bàn cờ sao cho mỗi ô chỉ được đi qua 1 lần duy nhất. Chẳng hạn 10 vị trí hợp lệ đầu tiên cho quân mã nếu quân mã bắt đầu khởi hành tại ô (1, 1) trên bàn cờ vua như sau :
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. - Thuật toán đệ qui
- Cài đặt cấu trúc dữ liệu tổ chức bàn cờ. - Khởi tạo ngẫu nhiên vị trí đặt quân mã đầu tiên. - Cài đặt chương trình máy tính đệ qui theo kiểu thử sai, vét cạn mọi khả năng để tìm lời giải: tìm kiếm nước đi kế tiếp bằng cách chọn một trong những ô có thể đặt quân mã hợp lệ tiếp theo trên bàn cờ. Cứ tiếp tục cho những nước sau đó đến khi tìm thấy một lời giải. - Hiển thị bàn cờ sau mỗi nước đi. - Dịch chương trình sang file thực thi. Ngôn ngữ lập trình sử dụng : C, C ++, Visual C++ ĐỀ TÀI 10:BÀI TOÁN PHÂN BỐ KÊNH TRUYỀN HÌNH TẠI ĐBSCLDÙNG THUẬT TOÁN TÔ MÀU ĐỒ THỊĐẶC TẢ ĐỀ TÀI : Bài toán (Phân bố kênh truyền hình đồng bằng Sông Cửu long): Các kênh truyền hình từ số 2 đến số 13 được phân chia cho các đài truyền hình các tỉnh trong vùng đồng bằng Sông Cửu long (Cà Mau, Bạc Liêu, Sóc Trăng, Cần thơ, Vĩnh long, An giang, Kiên giang, Đồng tháp, Trà Vinh, Bến Tre, Tiền giang, Long An) sao cho không có hai đài phát nào ở hai tỉnh nằm cạnh nhau trên bản đồ địa lý lại dùng cùng một kênh ? 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 tô màu đồ thị (giáo trình Toán rời rạc, Nguyễn Đức Nghĩa, NXB ĐH Quốc Gia TP. Hồ Chí Minh) Về chương trình : - Dữ liệu nhập vào và xuất ra dưới dạng file chứa các thông tin về đồ thị. - Tổ chức đồ thị: Mỗi đài phát tương ứng 1 đỉnh, mỗi màu biểu thị 1 kênh. Việc phân chia kênh tương ứng với việc tô màu đồ thị (tô màu theo thuật toán Greedy xét lần lượt theo số thứ tự các đỉnh) - Cài đặt quá trình thực hiện giải thuật tô màu (hiển thị Tên tỉnh và Số kênh tương ứng) - Dịch chương trình sang file thực thi.
Ngôn ngữ lập trình sử dụng : C, C ++ , Visual C++ĐỀ TÀI 11:BÀI TOÁN PHÂN BỐ KÊNH TRUYỀN HÌNH TẠI MIỀN ĐÔNG NAM BỘDÙNG THUẬT TOÁN TÔ MÀU ĐỒ THỊĐẶC TẢ ĐỀ TÀI : Bài toán (Phân bố kênh truyền hình miền đông Nam Bộ): Các kênh truyền hình từ số 15 đến số 25 được phân chia cho các đài truyền hình các tỉnh trong vùng miền đông Nam Bộ (TP.Hồ Chí Minh, Đồng Nai, Bà Rịa – Vũng Tàu, Tây Ninh, Bình Dương, Bình Phước) sao cho không có hai đài phát nào ở hai tỉnh nằm cạnh nhau trên bản đồ địa lý lại dùng cùng một kênh ? 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 tô màu đồ thị (giáo trình Toán rời rạc, Nguyễn Đức Nghĩa, NXB ĐH Quốc Gia TP. Hồ Chí Minh) Về chương trình : - Dữ liệu nhập vào và xuất ra dưới dạng file chứa các thông tin về đồ thị. - Tổ chức đồ thị: Mỗi đài phát tương ứng 1 đỉnh, mỗi màu biểu thị 1 kênh. Việc phân chia kênh tương ứng với việc tô màu đồ thị (tô màu theo thuật toán Greedy xét lần lượt theo số thứ tự các đỉnh) - Cài đặt quá trình thực hiện giải thuật tô màu (hiển thị Tên tỉnh và Số kênh tương ứng) - Dịch chương trình sang file thực thi.
Ngôn ngữ lập trình sử dụng : C, C ++ , Visual C++ĐỀ TÀI 12:XÂY DỰNG BẢN ĐỒ TRỰC TUYẾN NHỮNG CON ĐƯỜNG LỚN TRONG NỘI THÀNH TP.HỒ CHÍ MINH VỚI VIỆC TÍNH CHI PHÍ THẤP NHẤT ĐỂ DI CHUYỂN GIỮA TRUNG TÂM CÁC QUẬN.ĐẶ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 xác định con đường đi trên đồ thị, kiểm tra tính liên thông và tìm đường đi ngắn nhất giữa 2 đỉnh , mỗi đỉnh là 1 địa danh cụ thể tại trung tâm Tp.Hồ Chí Minh bằng giải thuật Dijkstra, Ford-Bellman trên đồ thị vô hướng. YÊU CẦU CỦA ĐỀ TÀI :
Phải có những chức năng cơ bản sau:
MÔI TRƯỜNG CÀI ĐẶT : Ngôn ngữ lập trình sử dụng: C hay C ++ ĐỀ TÀI 13:XÂY DỰNG HỆ THỐNG KẾT NỐI MẠNG CỦA CÁC TRƯỜNG ĐẠI HỌC TRONG THÀNH PHỐ VỚI CHI PHÍ THẤP NHẤTĐẶC TẢ ĐỀ TÀI : Vận dụng các lý thuyết cơ bản về đồ thị để thiết kế ra đồ thị thực tế kết nối các trường đại học, xây dựng 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 hoặc Prim. YÊU CẦU CỦA ĐỀ TÀI :
Phải có những chức năng cơ bản sau:
MÔI TRƯỜNG CÀI ĐẶT : Ngôn ngữ lập trình sử dụng: C hay C ++ ĐỀ TÀI 14: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI GIAO HÀNGĐẶC TẢ ĐỀ TÀINội dung bài toán: Xét bài toán rất nổi tiếng có tên là bài toán tìm đường đi của người giao hàng (TSP - Traveling Salesman Problem): Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua 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 (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. YÊU CẦU CỦA ĐỀ TÀI Nắm vững cơ sở lý thuyết về cấu trúc dữ liệu. Các kỹ thuật thiết kế giải thuật. Chương trình cần có các chức năng sau: Cho phép nhập vào bài toán: số thành phố, khoảng cách giữa các thành phố (có thể lấy số liệu từ trong tập tin). Xuất ra phương án tìm được. Nếu thể hiện dưới dạng đồ hoạ càng tốt. Mô phỏng thực tế của các tỉnh ĐBSCL. MÔT TRƯỜNG CÀI ĐẶT Ngôn ngữ lập trình sử dụng: C, C++ , Visual C++ ĐỀ TÀI 15: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI ĐƯA THƯĐẶC TẢ ĐỀ TÀINội dung bài toán: Xét bài toán về người đưa thư, xuất phát từ Bưu điện Tp. Hồ Chí Minh, anh ta đi đến tất các bưu điện chính trong nội ô, mỗi nơi đúng 1 lần. Cuối cùng anh ta quay trở lại nơi xuất phát sao cho quảng đường mà anh ta đi qua là ngắn nhất. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. YÊU CẦU CỦA ĐỀ TÀI Nắm vững cơ sở lý thuyết về cấu trúc dữ liệu. Các kỹ thuật thiết kế giải thuật. Chương trình cần có các chức năng sau: Cho nhập vào bài toán: số bưu điện chính tại các quận, khoảng cách nối giữa các bưu điện (có thể lấy số liệu từ trong bản đồ hoặc khảo sát thực tế). Xuất ra phương án tìm được. Nếu thể hiện dưới dạng đồ hoạ càng tốt.
Ngôn ngữ lập trình sử dụng: C, C++ , Visual C++ 2009 Каталог: wp-content -> uploads -> 2017 2017 -> Th ng b¸o thuèc míi 2017 -> Nguyen hoang cuong 2017 -> Curriculum vitae 2017 -> CỤc quản lý DƯỢc cộng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh Phúc 2017 -> Cung cấp giải pháp phần mềm 2017 -> MỘt số kiến thức cơ BẢn dành cho newbie 2017 -> NguyễN ĐĂng thảo vài Nét Chấm Phá Trong Đời Sống Âm Nhạc 2017 -> ĐỀ CƯƠng chi tiết môN: quản trị nguồn nhân lựC 2017 -> Điều Danh mục thuốc đông y, thuốc từ dược liệu và vị thuốc y học cổ truyền tải về 257.57 Kb. Chia sẻ với bạn bè của bạn:
|