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

[myhanh]

TÌM ĐƯỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG
B.Kiểm tra tính liên thông:
Dựa vào nhận xét đầu tiên mục A ta dễ dàng có thuật toán kiểm tra tính liên thông.

[myhanh]

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
1.Cây và tính chất cơ bản của cây:
Ta gọi cây là đồ thị vô hướng, liên thông và không có chu trình. Một đồ thị không có chu trình gọi là rừng. Như vậy thì rừng là đồ thị mà mỗi thành phần liên thông của nó là cây.

Định lí:
Giả sử G=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đề sau đây là tương đương nhau:
a. G là cây.
b. G không chứa chu trình và có n-1 cạnh.
c.G liên thông và có n-1 cạnh.
d.G liên thông và mỗi cạnh của nó đều là cầu.
e.Hai đỉnh bất kì của đồ thị được nối với nhau duy nhất bởi một đường đi đơn.
f.G không chứa chu trình, nhưng hễ cứ thêm vào nó một cạnh thì thì ta thu được đúng một chu trình

[thihonghanh]

doc nhung gi chi Hanh dua len, em cam thay rat vui, nhung cung buon!!ba giao vien Tin hoc cua truong minh hinh nhu chua co ai la len trang web nay ca!!!That la tiec qua phai khong chi!!!Em se noi voi nhung dua hoc tro thich Tin nhung bai viet cua chi va mong rang tui se thich trang web hon!!

[myhanh]

Originally posted by thihonghanh@Nov 27 2005, 09:49 AM
doc nhung gi chi Hanh dua len, em cam thay rat vui, nhung cung buon!!ba giao vien Tin hoc cua truong minh hinh nhu chua co ai la len trang web nay ca!!!That la tiec qua phai khong chi!!!Em se noi voi nhung dua hoc tro thich Tin nhung bai viet cua chi va mong rang tui se thich trang web hon!!

[snapback]6115[/snapback]

Chào cô Hạnh!
myhanh cũng có một chút giống cô Hạnh đó là cái nick myhanh. Cái nick này myhanh lấy khi làm thơ, viết báo riết rồi quen chứ myhanh là man 100% hì hì.
Đọc mấy dòng của cô Hạnh, myhanh cảm thấy mình có thêm sức mạnh. Thật ra kiến thức tin học rất mênh mông. myhanh cũng không biết các em cần gì nữa. myhanh chỉ nhớ lại những chủ đề mà Thầy Nhàn, Thầy Yên, Thầy Tân dạy myhanh khi myhanh tham gia đội tuyển Toán-Tin ngày trước.
Nhớ năm 1997 tại trường Đại học Bách Khoa Hà nội, khi ấy myhanh tham gia kỳ thi Tin học không chuyên toàn quốc lần thứ 3, đề thi cho hai câu hỏi thật đơn giản một bài dùng thuật giải Dijkstra và một bài nhân chia số lớn nhưng myhanh không làm được. Thật đáng buồn. Cuối cùng chỉ được giải khuyến khích. Một phần lúc đó do myhanh đang bệnh, một phần do mình thực hành quá ít nên khi lâm trận thì thiếu tự tin.
Từ ngày đó đến nay đã 8 năm rồi không biết việc thi cử có gì thay đổi không. Theo kinh nghiệm qua qua các lần thi cử hồi đó (4 lần thi học sinh giỏi, 3 lần thi tin học không chuyên) thì để làm được bài thi thì thí sinh phải nắm một số giải thuật, heuristic sau:
1. Mô hình quay lui, giải thuật vét cạn, nhánh cận.
2. Mô hình vết dầu loang, bài toán sinh.
3. Các giải thuật đồ thị như: Tô màu đồ thị, tìm đường đi ngắn nhất (Dijkstra, Loyd), cây phủ, cây phủ tối thiểu (Prism, Krusal),BFS,DFS, liên thông, chu trình Euler, chu trình Hamilton,...
4. Bài toán hình học: Đa giác lồi, diện tích đa giác lồi, cặp đoạn thẳng cắt nhau, tìm vùng nhìn,...
5. Bài toán cộng, trừ, nhân, chia số lớn.
6. Bài toán phân việc, giải thuật tham lam (greedy algorithm).
7. Giải hệ phương trình tuyến tính (phương pháp Gauss, Jaccobi).

[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;