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!!
|
Trích:
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). |
Trích:
|
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 Code:
PROCEDURE STREE_DFS(v); Bài tập: Viết thủ tục STREE_BFS(v). |
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. |
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é............ |
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: . |
Trích:
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!!!!! |
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. Code:
PROCEDURE KRUSKAL; |
Ðề: Những thuật toán hay thi HSG Tin học
sao MH ko viết topic này nữa nhỉ?Em đang học trong đội Tin,em sẽ ủng hộ 2 tay 2 chân luôn.
|
Múi giờ GMT +7. Hiện tại là 03:49 AM. |
Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này