//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10

Chuyên đề 4. BÀI TOÁN LUỒNG CỰC ĐẠI TRONG MẠNG VÀ ỨNG DỤNG

Số tiết: 5

TT Nội dung Mức độ cần đạt Ghi chú
1 Biểu diễn đồ thị, duyệt đồ thị Kiến thức:
Hiểu các khái niệm:
– Ma trận trọng số
– Danh sách kề
– Thuật toán duyệt BFS và DFS
Kĩ năng:
• Lập đúng ma trận kề
• Cài đặt được các thuật toán BFS và DFS Trước khi cài đặt thuật toán có thể yêu cầu HS mô phỏng thuật toán bằng ví dụ đơn giản, cụ thể
2 Bài toán luồng cực đại Kiến thức:
Hiểu các khái niệm:
– Mạng và luồng trong mạng
– Bài toán luồng cực đại trong mạng
Kĩ năng:
Nhận biết được bài toán thực tế có thể đưa về bài toán luồng cực đại trong mạng.
3 Lát cắt. Đường tăng luồng. Định lý Ford – Fulkerson Kiến thức:
Hiểu các nội dung:
– Lát cắt và đường tăng luồng
– Định lý về luồng cực đại và lát cắt hẹp nhất
Kĩ năng:
Vận dụng được định lí trong các bài toán cụ thể
4 Thuật toán Ford – Fulkerson tìm luồng cực đại trong mạng Kiến thức:
Hiểu các nội dung:
– Mô tả thuật toán
– Về hiệu quả của thuật toán
– Thuật toán cải biên của Edmond-Karp
Kĩ năng:
Cài đặt tốt chương trình cho thuật toán
5 Một số bài toán luồng tổng quát Kiến thức:
Hiểu các nội dung:
– Mạng với nhiều điểm phát và điểm thu
– Bài toán với khả năng thông qua của các cung và các đỉnh
– Mạng trong đó khả năng thông qua của mỗi cung bị chặn hai phía.
Kĩ năng:
Nhận biết được các vấn đề thực tế tương ứng với các luồng tổng quát
6 Một số ứng dụng
Kiến thức:
Hiểu một số bài toán:
– Bài toán ghép cặp trên đồ thị hai phía
– Bài toán về hệ thống đại diện chung.
– Bài toán lập lịch
Kĩ năng:
Cài đặt được chương trình cho các thuật toán giải các bài toán

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: