Những thuật toán hay thi HSG Tin học

[myhanh]

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
2.Cây khung của đồ thị:
Định nghĩa:
Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F), F là tập con của E được gọi là cây khung của đồ thị.
Áp dụng thuật toán tìm kiếm theo chiều rộng, chiều sâu để xây dựng cây khung của đồ thị vô hướng liên thông. Trong cả hai trường hợp mỗi khi ta đến được đỉnh mới u từ đỉnh v thì cạnh (v,u) sẽ được kết nạp vào cây khung

PROCEDURE STREE_DFS(v);
(* Tìm kiếm theo chiều sâu tìm cây khung T của đồ thị vô hướng liên thông G cho bởi danh sách kề, các biến chuaxet,ke,T là toàn cục*)
BEGIN
  chuaxet[v]:=false;
  FOR u in ke(v) DO
      IF chuaxet[u] THEN
          BEGIN
                T:=T U (v,u);
                   STREE_DFS(u);
          END;
END;
BEGIN
  FOR u in V DO chuaxet[u]:=true;
  T:=Ø;
  STREE_DFS(Root);
 END.

Bài tập:
Viết thủ tục STREE_BFS(v).

[myhanh]

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
3.Bài toán cây khung nhỏ nhất:
Cho đồ thị G=(V,E) là đồ thị vô hướng , liên thông với
V={v1,v2,...,vn}, E= m cạnh với ∀e ∈ E, ∃C(e)>0: C(e) gọi là độ dài của nó.
H=(V,T) là cây khung của đồ thị G. Ta gọi độ dài C(H) của cây khung H là tổng độ dài các cạnh của nó
C(H) = ΣC(e), e ∈ H.
Tìm H sao cho C(H) nhỏ nhất.

[quemoi]

Ngoài các thuật toán ra, trong các kỳ thi Olympic các bạn đi thi cần một số chiến thuật và kinh nghiêm. Ví dụ:
1. Ban giám khảo chấm điểm tự đông bằng chương trình, không xem source code, cho nên đầu tiên là chương trình của các bạn cần phải chạy, cho kết quả được đầu vào đầu ra đúng. Trong một số trường hợp thì không tìm được thuật giải hoàn chỉnh với một khoảng thời gian cho phép, lúc đó bạn cứ bình tĩnh, cố gắng tìm ra được một thuật giải càng đúng nhiều test càng tốt.

2. Có một số vấn đề mà trong toán học có thể hơi khác với trong tin học, lúc các bạn làm bài nếu bị một tính "ì" trong toán học thì các bạn có thể dẫn đến KQ sai(không đúng với đầu ra của test). Chẳng hạn như là so sánh 2 số thực, trong toán học 2 số thực bằng nhau là a=b, nhưng trong một số bài toán của tin học thì các bạn phải thay a=b bởi 1 hàm số abs(a-B)<saiso vì số thực của Tin học không "chính xác" như là số thực của toán học. VD so sánh a*a=2*b*b, nếu như b=1, a=1.4142... thì dấu bằng cũng có thể không xảy ra. Các bạn phải chú ý sai số mà bài toán đưa ra.
Tuy những vấn đề này đơn giản nhưng có nhiều bạn làm rất tốt về thuật toán vẫn bị điểm thấp, nhất là các bạn thiếu "kinh nghiêm trận mạc".

Bữa khác tiếp tục nhé............

[myhanh]

Mấy ngày gần đây myhanh quá bận với thi cử nên không có ghé qua diễn đàn. Hôm nay thi xong myhanh xin tiếp tục chủ đề này.
Thứ nhất là ý kiến của quemoi rất hay. Văn ôn thì võ luyện. Cái kinh nghiệm trận mạc của quemoi chỉ là dùng để luyện gà chọi thôi. Ở đây myhanh muốn bàn về khía cạnh kiến thức. Cả hai mặt này bổ sung cho nhau, không thể xem nhẹ mặt nào đâu nha :lol: .

[quemoi]

Originally posted by myhanh@Jan 9 2006, 12:27 PM
Mấy ngày gần đây myhanh quá bận với thi cử nên không có ghé qua diễn đàn. Hôm nay thi xong myhanh xin tiếp tục chủ đề này.
Thứ nhất là ý kiến của quemoi rất hay. Văn ôn thì võ luyện. Cái kinh nghiệm trận mạc của quemoi chỉ là dùng để luyện gà chọi thôi. Ở đây myhanh muốn bàn về khía cạnh kiến thức. Cả hai mặt này bổ sung cho nhau, không thể xem nhẹ mặt nào đâu nha :lol: .

Đúng là không được xem nhẹ mặt nào, trong các kỳ thi thì kiến thức thuật toán vẫn là quan trọng nhất, nhưng bên cạnh đó cần chú ý một số vấn đề mà minh đưa ra. Thực tế là đã có nhiều bạn HSSV ở các trường phổ thông và ĐH đã gặp phải những vấn đề này mặc dù rất giỏi. Mục tiêu của chúng ta là đem lại tiếng tăm cho HSSV Miền Nam chúng ta nói chung và quê hương Long An nói riêng, nên mình cũng tham gia đóng góp một vài ý kiến nho nhỏ cho đàn em của chúng ta.

3. Vấn đề thứ 3 trong các kỳ thi đó là thuật giải sắp xếp:
Có nhiều thuật giải sắp xếp khác nhau, nhưng ở các kỳ thi thì các bạn sẽ thường dùng đến 2 thuật giải là Bubble Sort và Quick Sort.
- Thuật giải Bubble sort cài đặt rất nhanh, dễ, dễ dàng kiểm tra tính đúng đắn, tuy nhiên lại chiếm thời gian lớn khi thực thi (0(n^2)).
- Thuật giải Quick sort thì thực thi nhanh nhưng lại đòi hỏi thời gian cài đặt lâu hơn 1 chút.
Vì vậy tuỳ vào yêu cầu của bài toán(số phần tử cực đại và thời gian cho 1 test) mà các bạn chọn 1 thuật giải thích hợp. Đã từng có bạn đi thi viết đúng thật giải hoàn toàn nhưng đề bài cho số phần tử lớn, và thời gian để thực thi 1 test ít, chương trình của bạn ấy không kịp ghi KQ ra file xuất cho nên đã không đạt điểm tuyệt đối do sai ở một số test, thật đáng tiếc!!!!!

[myhanh]

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
4.Thuật toán Kruskal:
Xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T). Sắp xêp các cạnh của đồ thị G theo thứ tự không giảm của độ dài.
Bắt đầu T = Ø
Ở mỗi bước duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn để tìm ra cạnh mà việc bổ sung vào tập T không tạo thành chu trình trong tập này.
Thuật toán sẽ kết thúc khi ta thu được tập T gồm có n-1 cạnh.

 PROCEDURE KRUSKAL;
  BEGIN
   Sắp xếp các cạnh theo chiều không giảm;
    T = Ø;
  WHILE ( |T| < n-1 ) AND ( E <> Ø) DO
      BEGIN
           Chọn e in E là cạnh có độ dài nhỏ nhất.
             E:= E - {e};
             IF (T + {e}) không chứa chu trình THEN
             T:=T+{e}
            END;
      END;

[nguyenchican]

Nguyên văn bởi myhanh

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
2.Cây khung của đồ thị:
Định nghĩa:
Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F), F là tập con của E được gọi là cây khung của đồ thị.
Áp dụng thuật toán tìm kiếm theo chiều rộng, chiều sâu để xây dựng cây khung của đồ thị vô hướng liên thông. Trong cả hai trường hợp mỗi khi ta đến được đỉnh mới u từ đỉnh v thì cạnh (v,u) sẽ được kết nạp vào cây khung

PROCEDURE STREE_DFS(v);
(* Tìm kiếm theo chiều sâu tìm cây khung T của đồ thị vô hướng liên thông G cho bởi danh sách kề, các biến chuaxet,ke,T là toàn cục*)
BEGIN
  chuaxet[v]:=false;
  FOR u in ke(v) DO
      IF chuaxet[u] THEN
          BEGIN
                T:=T U (v,u);
                   STREE_DFS(u);
          END;
END;
BEGIN
  FOR u in V DO chuaxet[u]:=true;
  T:=Ø;
  STREE_DFS(Root);
 END.

Bài tập:
Viết thủ tục STREE_BFS(v).

Nó giống Pascal thé trời

[myhanh]

Nguyên văn bởi nguyenchican

Nó giống Pascal thé trời

Thế thì có vấn đề gì không bạn.
Thật ra nó là mã giả (pseudo code)