Tài liệu Bồi Dưỡng Tin Học

CHUYÊN ĐỀ 1 ĐỊNH HƯỚNG TRANG BỊ KIẾN THỨC CƠ SỞ TIN HỌC Trong trường PTTH môn Tin học được triển khải giảng dạy cho mọi học sinh. Với đặc thù của trường chuyên, nếu xét ta trên các góc độ: Trình độ tiếp thu, Yêu cầu của chuyên ngành đối với Tin học, học sinh có thể được chia thành ba lớp đối tượng khác nhau: Học sinh các lớp không chuyên tin, Học sinh lớp chuyên tin nằm ngoài danh sách dự tuyển hoặc đội tuyển, Học sinh đội dự tuyển hoặc đội tuyển. Mỗi loại đối tượng có yêu cầu riêng về kiến thức cần trang bị và kéo theo là nội dung và phương pháp truyền đạt. Với học sinh chuyên tin (không thuộc diện bồi dưỡng đội tuyển) và học sinh không chuyên tin trong phạm nhà trường phổ thông chỉ cần dừng lại ở việc trang bị kiến thức cơ sở, những kiến thức mà trong một Hình 1 chừng mực nào đó sau khi tốt nghiệp phổ thông học sinh còn nhớ được và có tác dụng hỗ trợ trong việc học tập tiếp theo cũng như trong công việc sau này. Mỗi đối tượng cần có một khối lượng kiến thức cơ sở riêng. 1.1. KHỐI KHÔNG CHUYÊN Không chuyên tin là nhóm học sinh đông đảo nhất. Đối với học sinh không chuyên tin, kỹ năng lập trình không phải là điều quan trọng nhất. Học sinh thuộc nhóm này chỉ cần nắm được: Tin học cung cấp dịch vụ có hiệu quả trong mọi lĩnh vực của cuộc sống hàng ngày, Các dịch vụ đó được cung cấp trên nguyên lý và cơ sở nào? Tại sao các dịch vụ đó mang lại hiệu quả lao động cao cho con người? Môi trường tin học hóa cao tác động đến suy nghĩ và hành động của chúng ta như thế nào? 1 Khi trình bày mỗi vấn đề, không nên đi quá sâu vào chi tiết kỹ thuật, không bắt học sinh phải nhớ các thao tác cụ thể cho từng loại công việc. Điều chủ chốt là nguyên nhân tại sao năng suất lao động lại tăng lên, ta được cung cấp những dịch vụ nào, nếu chưa biết hoặc quên thì tìm kiếm cách tác động lên hệ thống như thế nào để đạt được mục đích cụ thể của mình. Ví dụ, với chương Soạn thảo văn bản, những điều mà học sinh phải nhớ sau khi học là: Các hệ thống soạn thảo văn bản cho phép ta tách riêng 2 phần độc lập: nội dung văn bản và hình thức trình bày văn bản, Có nhiều khả năng tác động vào hình thức trình bày: đặt lề cho trang văn bản, kiểu chữ, khoảng cách dòng, . . . Các hệ thống soạn thảo văn bản khác nhau ở khả năng cung cấp các dịch vụ trình bày, khả năng làm việc với các dạng nội dung (bảng, hình ảnh, biểu đồ, công thức, v.v. . .), Hệ thống càng hiện đại thì các khả năng này càng nhiều và càng dễ sử dụng. Trong số các tính năng trên, tính năng quan trọng nhất và mang lại thay đổi về chất lượng là việc tách riêng nội dung với hình thức. Chính điều này đã làm cho việc soạn thảo văn bản trên máy tính khác hẳn việc viết tay trên giấy hoặc đánh máy chữ. Đi sâu hơn nữa, có thể trình bày về cơ chế hoạt động của hệ soạn thảo. Với mỗi văn bản hệ thống tạo một cơ sở dữ liệu để quản lý. Cơ sở dữ liệu càng phong phú thì khả năng của hệ thống càng lớn. Trăm nghe không bằng một thấy, cần phải nêu rất nhiều ví dụ minh họa để học sinh thấy được các khả năng đó là có thực. Giờ thực hành là lúc học sinh trải nghiệm lại những điều đã nghe, thấy, hiểu và nhớ. Đây cũng là lúc rèn luyện kỹ năng tìm kiếm và kích hoạt các chức năng cụ thể trong trường hợp cụ thể. Việc so sánh các hệ thống soạn thảo văn bản khác nhau sẽ cung cấp cho học sinh kiến thức về lô gic tiến hóa, phát triển của hệ thống. 2 Người dùng chủ động Hệ thống hỗ trợ HỆ SOẠN THẢO HÌNH THỨC NỘI DUNG Các khuôn dạng bổ trợ Văn bản Hình ảnh Hành động Màu Bảng Âm thanh Kích thước Hình 2 Từ đây ta có thể cung cấp cho học sinh khả năng tự đoán nhận và dự báo khả năng phát triển của các loại hệ thống soạn thảo nói chung như soạn thảo hình vẽ (photoshop, Microsoft Visio, . . .), soạn thảo ảnh và videoclip (Movie Maker, PowerPoint, . . .), các hệ soạn thảo chuyên dụng để biên tập tài hiệu chuyên ngành (toán, lý, hóa, . . .). Như vậy, chỉ cần thông qua hệ thống soạn thảo văn bản ta đã cung cấp cho học sinh kiến thức về mọi loại hệ thống soạn thảo cho mọi loại đối tượng! Toàn bộ chương trình lớp 12 là xem xét lại một cách tổng quát hóa phần lớn các kiến thức đã có. Như vậy, kiến thức cơ sở không nhiều. Với đối tượng học sinh phổ thông ta, phải đi từ cụ thể đến tổng quát hóa, phải có các ví dụ cụ thể, nhưng phải hết sức tránh: Chỉ dẫn quá nhiều các thao tác cụ thể, Chỉ dẫn một cách rời rạc, không phân loại và hệ thống hóa, Yêu cầu học sinh nhớ, thuộc quá nhiều các chi tiết cụ thể của hệ thống cụ thể. 3 Tất cả các loại hệ thống đều luôn luôn hoạt động của theo sơ đồ: Nạp dữ liệu CSDL Hệ Quản trị CSDL Kết quả Truy vấn Hình 3 Việc dạy Exel, Access cũng hoàn toàn tương tự như dạy hệ soạn thảo văn bản. Tuy nhiên ở mỗi hệ thống cần nhấn mạnh cho học sinh thấy rõ những mặt mạnh và yếu của hệ thống đang xét, để cho học sinh nhớ được khả năng và phạm vi ứng dụng của loại hệ thống này. Đó là những điều ta cần và chỉ cần đạt được đối với đại bộ phận học sinh phổ thông. Những điều này không lạc hậu trong suốt phần cuộc đời tiếp theo của học sinh. Kỹ năng lập trình không phải là trọng tâm đối với các học sinh của nhóm này. Tuyệt đại bộ phận học sinh thuộc nhóm này sẽ không có nhu cầu tự lập trình để giải quyết các vấn đề của mình trong tương lai. 1.2. KHỐI CHUYÊN TIN Đặc trưng cơ bản của lớp đối tượng này: Nhiều học sinh đã biết và sử dụng khá thường xuyên các dịch vụ tin học, Có kiến thức cơ sở toán tốt, Có khả năng và nhu cầu lập trình. Kiến thức cần trang bị bao gồm 2 phần: các Kiến thức chung về Tin học và Cơ sở lập trình. Kiến thức chung về Tin học vẫn rất cần thiết với loại đối tượng này 4 vì nó sẽ tác động rất lớn tới phần Cơ sở lập trình, làm cho việc lập trình dễ dạy hơn và dạy được sâu hơn. Các điểm mấu chốt trong phần này vẫn là: Các dịch vụ đó được cung cấp trên nguyên lý và cơ sở nào? Tại sao các dịch vụ đó mang lại hiệu quả lao động cao cho con người? Môi trường tin học hóa cao tác động đến suy nghĩ và hành động của chúng ta như thế nào? Với đối tượng này cần giải thích sâu hơn về cơ chế trong hiện thực hóa các nguyên lý và cơ sở đó. Học sinh không cần phải nhớ, phải thuộc những kiến thức này nhưng phải biết tại sao máy tính đáp ứng được yêu cầu của ta và đáp ứng bằng cách nào. Ví dụ, khi ta nháy chuột vào một biểu tượng nào đó trên màn hình nền (Desktop) tại sao hệ thống báo đối tượng đó được chọn hoặc hệ thống kích hoạt công việc tương ứng với biểu tượng? Nên giải thích cho học sinh về cơ chế hoạt động của hệ thống: mỗi biểu tượng được biểu diễn dưới dạng một bức tranh hình vuông. Hệ thống có cơ sở dữ liệu quản lý vị trí các hình vuông này trên màn hình nền và công việc (chương trình) tương ứng với hình này. Khi ta nháy chuột, dựa vào vị trí của chuột hệ thống sẽ xác định được biểu tượng mà ta chọn (hoặc không có biểu tượng nào cả). Phụ thuộc vào cách nháy chuột hệ thống sẽ biết ta muốn chọn hay muốn kích hoạt công việc được chọn và có hành động tương ứng: đổi màu nền của biểu tượng hoặc kích hoạt câu lện gọi chương trình tương ứng. Nếu ta kéo biểu tượng sang vị trí mới, hệ thống sẽ cập nhật lại cơ sở dữ liệu quản lý Desktop. Tất cả mọi giải thích đều hướng suy nghĩ của học sinh tới hai ý: Mỗi công việc đều có cơ sở dữ liệu tương ứng (có thể rất đơn giản hoặc phức tạp), Việc lập trình quyết định tất cả! Nếu học sinh, có thể ngạc nhiên, nhưng không còn thấy bí hiểm hay ngỡ ngàng trước một dịch vụ nào đó của hệ thống thì có nghĩa chúng ta đã thành công trong việc chuẩn bị bước sang phần lập trình. Điều này rất quan trọng vì: Học sinh thấy được lô gic của vấn đề, Thấy được vai trò, vị trí của khâu lập trình, Thấy được vai trò, vị trí của dữ liệu và tổ chức dữ liệu. Việc chuyển sang dạy lập trình sẽ bớt khô khan, nhàm chán và rời rạc. Đối với học sinh trong đội tuyển tương lai điều này là hết sức cần thiết vì học sinh thấy 5 được tầm quan trọng của dữ liệu, đặt ngang hàng việc thiết kế, tổ chức dữ liệu với giải thuật. Thông thường, học sinh chỉ quan tâm đến giải thuật trên quan điểm toán học thuần túy. Điều này là cần thiết, nhưng chỉ là một khâu nhỏ trong quá trình giải bài toán. Chính vì vậy, các ngôn ngữ lập trình phát triển hiện nay cung cấp rất nhiều công cụ hỗ trợ tổ chức dữ liệu và các công cụ thao tác chuẩn với các dữ liệu đó. 1.3. HỌC SINH NĂNG KHIẾU Kết quả hoạt động bồi dưỡng học sinh năng khiếu là một trong số các chỉ tiêu quan trọng đánh giá hiệu quả của một trường chuyên. Nếu xem xét trên quan điểm công nghệ, quá trình tác động lên học sinh năng khiếu có 3 khâu: Phát hiện, Đào tạo, Bồi dưỡng. Phát hiện: Tìm ra các học sinh có tiềm năng trở thành học sinh giỏi Tin học. Đào tạo: Xét riêng về mặt chuyên môn là trang bị các kiến thức cơ sở cần thiết với một học sinh năng khiếu. Bồi dưỡng: Trang bị thêm các kiến thức chuyên sâu, rèn luyện và nâng cao kỹ năng tư duy linh hoạt, sáng tạo. Trong phần này ta chỉ xem xét các vấn đề liên quan tới khâu đào tạo và cũng chỉ xem xét ở góc độ trang bị các kiến thức cơ sở. Đây là công việc khá nhàm chán , buồn tẻ. Khối lượng kiến thức thuộc diện cơ sở khá lớn, ít thay đổi trong một khoảng thời gian đủ dài, sơ đồ và trình tự truyền đạt tương đối ổn định, mặt bằng kiến thức của học sinh chưa đồng đều. Với thực tế hiện nay ta có không quá 4 tháng cho việc trang bị kiến thức cơ sở và phải làm việc này đan xen với việc bồi dưỡng, nâng cao kỹ năng ứng dụng sáng tạo đối với các kiến thức cơ sở đã trang bị trước đó. Như vậy, cần phải xác định rõ, những kiến thức gì thuộc loại cơ sở, tức là những thứ phải trang bị đến tận răng cho mỗi học sinh (trong đội tuyển hoặc dự tuyển). Với mỗi mô hình toán học cho một giải thuật cơ sở cần chuẩn bị nhiều bài toán tương đương với nội dung phát biểu khác nhau để tránh sự nhàm chán xuất hiện trong học sinh, đặc biệt là ở những đối tượng đã qua khâu đào tạo của năm trước. 6 1.3.1. ĐỊNH HƯỚNG Các cuộc thi Olympic Tin học được triển khai rộng rãi ở gần hết các nước trên thế giới hướng tới các mục đích:  Đẩy mạnh phong trào dạy và học Tin học nhằm đáp ứng các yêu cầu của cuộc sống đang được tin học hóa sâu rộng và với tốc độ cao trong mọi lĩnh vực,  Phát hiện các nhân tố nổi bật để đào tạo và khai thác nguồn nhân lực đỉnh cao, có tri thức và có tay nghề theo kịp sự phát triển của lý thuyết và yêu cầu của thực tế. Việc đào tạo, bồi dưỡng học sinh giỏi Tin học chịu tác động rất nhiều của hai yếu tố:  Sự phát triển của lý thuyết,  Sự phát triển của công cụ Tin học. Có thể thấy rõ xu hướng dạy và học Tin học cho đến nay chia thành ba giai đoạn:  Giai đoạn I: những năm cuối của thế kỷ XX,  Giai đoạn II: Thập kỷ đầu tiên của thế kỷ XXI,  Giai đoạn III: Thập kỷ thứ 2 của thế kỷ XXI, tức là những năm hiện tại. Ở giai đoạn I, ngành Tin học mới tách ra và phát triển thành một ngành khoa học độc lập. Người ta tập trung mọi sức lực vào việc xây dựng nền móng cho một ngành khoa học mới, cố gắng tìm cách để giải quyết được các lớp bài toán truyền thống xuất hiện khi tiếp cận bài toán trên quan điểm toán học. Việc nắm vững các kiến thức toán học là điều kiện chủ yếu để giải quyết các bài toán tin học. Ngoài ra còn phải lưu ý tới cấc ràng buộc tự nhiên về bộ nhớ nhỏ và tốc độ tương đối thấp của máy tính lúc bấy giờ. Đó là sự tiếp tục của tư duy những năm 70 – 80 của thế kỷ 20. Ví dụ, một vài trong những bài khó của những năm 90: Bài 6. IOI 1990 Belarus Cho các số nguyên a và n (n < 100). Giả thiết ta có một ngôn ngữ lập trình chỉ có thể thực hiện phép gán và phép nhân. Hãy khởi tạo chương trình tính b = an với số phép nhân cần thực hiện là ít nhất. Ví dụ, với n = 13, chương trình có dạng như sau (trong cặp ngoặc {} là thông tin chú thích): X1 := a; {= a} 7 X2 := X1*X1; X3 := X2*X2; X4 := X3*X1; X5 := X3*X3; X6 := X5*X4; B := X6; {= a2} {= a4} {= a5} {= a8} {= a13} Phân tích: Xét n ở dạng biểu diễn nhị phân, n = 1310 = 11012. Gọi m là số chữ số có nghĩa trong dạng biểu diễn nhị phân của n, k là số lượng bít bằng 1, số phép nhân phải thực hiện là (m-1)+(k-1). Có thể dễ dàng xác định số lượng biến trung gian cần sử dụng và cách tính giá trị các biến trung gian đó. Nhận xét: Kích thước bài toán rất nhỏ, phù hợp bộ xử lý 8 bít phổ biến thời kỳ đó (PC XT). Vào nửa sau của những năm 90 độ khó của bài toán bắt đầu thay đổi: Bài 6. IOI 1996 Hungary HÌNH VUÔNG KỲ DIỆU Tiếp theo sự thành công của khối lập phương nổi tiếng ông Rubik đã đề xuất phương án phẳng của trò chơi này. Đó là một tấm nhựa được ghép từ 8 hình vuông thành 2 hàng, mỗi hình vuông có một màu, đánh số từ 1 đến 8 theo chiều kim đồng hồ, bắt đầu từ hình vuông trên trái (Xem phần bên trái của hình 1). Cấu hình này được gọi là cấu hình ban đầu. Có 3 phép biến đổi cơ sở với tấm nay:  A – Đổi chổ 2 hàng trên và dưới,  B – Chuyển dịch vòng tròn các cột sang phải một vị trí,  C - Chuyển dịch vòng tròn 4 hình vuông ở giữa theo chiều kim đồng hồ. Tất cả các cấu hình khác nhau của tấm nhựa đều có thể nhận được từ cấu hình ban đầu bằng cách áp dụng các phép biến đổi cơ sở. 1 2 3 8 7 6 4 1 5 1 Hình 4 B A 8 7 6 1 2 3 4 1 5 1 2 5 1 4 1 3 8 7 6 1 1 7 2 8 6 3 4 1 5 1 Hãy viết chương trình xác định xác định dãy biến đổi cơ sở để đưa tấm nhựa từ cấu hình ban đầu về cấu hình đích cho trước (Yêu cầu A). Bạn sẽ nhận thêm 2 điểm thưởng nếu số phép biến đổi tìm được không vượt quá 300 (Yêu cầu B). Dữ liệu: Vào từ file văn bản INPUT.TXT gồm một dòng chứa 8 số nguyên xác định cấu hình đích. 8 Kết quả: Đưa ra file văn bản OUTPUT.TXT, dòng đầu tiên chứa số nguyên m – số phép biến đổi của dãy tìm được, mỗi dòng trong m dòng sau chứa một ký tự xác định tên phép biến đổi. Các phép biến đổi đưa ra theo trình tự thực hiện. Ví dụ: INPUT.TXT OUTPUT.TXT 2 6 8 4 5 7 3 1 7 B C A B C C B Phân tích: Gọi R = (r1, r2, r3, r4, r5, r6, r7, r8) là véc tơ mô tả trạng thái của Rubic phẳng. R là một hoán vị của các số tự nhiên từ 1 đến 8. Bằng việc áp dụng các phép biến đổi đã cho ta có thể làm cho R nhận giá trị là hoán vị bất kỳ. Như vậy, số trạng thái khác nhau của Rubic là 8! = 40320. Ngày nay, với các công cụ phần cứng và phần mềm hiện đại, đây là một bài toán loang đơn giản. Nhưng ở thời kỳ cuối những năm 90, các công cụ chỉ cho phép sử dụng bộ nhớ 64KB tĩnh + 64KB động, tốc độ máy tính phổ biến 33MHz đây là một bài toán khó. Cần phải khảo sát, tìm các phép biến đổi macro cơ sở, mô tả lời giải qua các phép macro này, khai triển macro và rút gọn, tuy không nhận được dãy phép biến đổi ngắn nhất, nhưng dãy biến đổi cũng ngắn hơn nhiều so với giới hạn thưởng 300. Chúng ta đã đạt được những kết quả rực rỡ trong thời kỳ này vì đội ngũ giáo viên tin học phần lớn xuất thân từ giáo viên chuyên ngành toán. Học sinh của chúng ta được trang bị kiến thức cơ sở về toán khá tốt. Giai đoạn II từ những năm 2001 đến 2007, sự tiến bộ về công nghệ và sự phổ cập của các hệ thống phần mềm tiên tiến đã đưa đến những sự chuyển dịch trong việc đào tạo chuyên gia trong lĩnh vực tin học. Điều này dẫn đến những thay đổi trong công tác phát hiện, đào tạo và bồi dưỡng học sinh giỏi tin học. Do đó nội dung thi Tin học Quốc tế cũng có nhiều thay đổi. Các kiến thức giải thuật được coi là đỉnh cao trước đây bây giờ đã trở thành “bảng cửu chương” mà ai cũng phải biết và phải thuộc. Những giải thuật phức tạp, ít dùng thì không 9 nhất thiết phải thuộc, nhưng bất cứ ai và lúc nào cũng có thể tra cứu, tìm kiếm chúng trên Internet khi cần thiết. Sự thông minh và tính sáng tạo bây giờ phải thể hiện không phải ở chổ bạn thuộc nhiều hay ít các giải thuật khác nhau, cũng không phải bạn cài đặt chúng nhanh tới mức nào. Thử thách bây giờ là ở chổ bạn có thể tìm ra những giải pháp hữu hiệu giải quyết một cách có hiệu quả các bài toán các vấn đề có mô hình toán học đơn giản nhưng có kích thước lớn hay không? Để đạt được mục đích đó người lập trình phải biết tận dụng tối đa khả năng mà phần cứng và hệ điều hành cung cấp. Các hệ thống lập trình mới như Free Pascal, Dev C++ (những phiên bản đầu tiên) đã tạo điều kiện để người dùng khai thác được tối đa khả năng của phần cứng. Ở giai đoạn này, để giải một bài toán olympic thực chất ta phải xây dựng một cơ sở dữ liệu (CSDL) nhỏ, tổ chức quản lý và truy vấn tới CSDL đó để tìm ra lời giải cần thiết. Khai khoáng dữ liệu Dữ liệu vào CSDL Truy vấn Nạp dữ liệu Kết quả Ghi nhận dữ liệu Hình 5 Đặc điểm cơ bản của sơ đồ trên là quá trình giải bài toán được chia thành 2 giai đoạn phân biệt: Ghi nhận dữ liệu, Khai khoáng dữ liệu (Data Mining). Việc ghi nhận dữ liệu khác với việc nhập thuần túy là thông thường dữ liệu được lưu lại sau khi đã qua một số phép biến đổi đơn giản. Trong rất nhiều 10 trường hợp dữ liệu được đơn vị lưu trữ theo cụm, bao gồm giá trị và các thuộc tính. Cụm dữ liệu phổ biến hơn cả là giá trị và thứ tự xuất hiện. Phần khai khoáng dữ liệu đòi hỏi sự linh hoạt và sáng tạo cao của người làm. Để đảm bảo hiệu quả cao trong khai khoáng và truy vấn nhiều lớp bài toán đòi hỏi phải sử dụng các cấu trúc dữ liệu như các loại cây nhị phân, cây quản lý interval, cây tiền tố, v.v. . ., người lập trình phải biết tổ chức và quản lý stack, heap, hàng đợi, hàng đợi hai đầu, hàng đợi ưu tiên , . . . Tất cả những điều này đã làm thay đổi một cách đáng kể đến nội dung và phương pháp trang bị kiến thức cơ sở cho học sinh. Đáng tiếc là tới tận năm 2007 khi thế giới đã đi hết chặng đường quan trọng này thì chúng ta mới được phép chính thức đặt chân lên mãnh đất đã in đầy dấu chân của những người tiên phong, đi vào con đường vốn bây giờ đã trở thành kỷ niệm đẹp của những người đi trước. Ở giai đoạn III, tức là ở những năm gần đây, trong danh mục yêu cầu đối với người lập trình có thêm các đòi hỏi mới:  Không những bạn phải đứng vững trên nền tảng của phần cứng và hệ thống mà còn phải biết khai thác tối đa khả năng của công cụ lập trình. Cụ thể, bạn phải khai thác được triệt để mặt mạnh của các thư viện của hệ thống lập trình có trong tay,  Có kiến thức cơ sở toán học vững và sâu,  Triển khai ứng dụng “giải thuật kép”: kết hợp nhiều giải thuật cơ sở đơn trong việc tổ chức dữ liệu,  Nâng cao tính hoàn thiện của chương trình: chương trình phải cho kết quả đúng và xử lý có hiệu quả với từng lớp dữ liệu (của bài toán). Để đoán nhận hướng giải và tìm được giải thuật có hiệu quả học sinh cần được trang bị: Cơ sở toán học sâu và rộng hơn, Có kỹ năng triển khai một giải thuật với việc ứng dụng các loại cấu trúc dữ liệu khác nhau và phạm vi hiệu quả của các cách triển khai đó, Kỹ thuật làm việc với một số lớp dữ liệu đặc thù như hoán vị các số từ 1 đến n, tập hữu hạn các số nguyên khác nhau từng đôi một . . . Trong nhiều trường hợp chương trình giải bài toán không đơn thuần là một hệ quản trị CSDL mà là một hệ quản lý cơ sở tri thức. Như vậy đối tượng cần chuẩn bị không đơn thuần là một CSDL mà là một CSDL cộng với một cơ sở tri 11 thức. Như vậy chương trình giải trên thực tế là một hệ chuyên gia nhỏ. Phần lớn các bài toán loại này thuộc lớp bài toán giao tiếp người – máy (interactive task). Trên thế giới, loại bài toán này được đưa vào ngày càng nhiều trong các kỳ thi quốc tế, quốc gia và khu vực. Đã bắt đầu xuất hiện các bài toán không thuộc loại giao tiếp người máy nhưng vẫn đòi hỏi chiến lược tìm kiếm động. Học sinh không những phải biết các giải thuật khác nhau cho từng lớp bài toán mà ngoài việc đánh giá độ phức tạp còn phải hiểu sâu về các thuộc tính liên quan tới giải thuật hoặc các tính chất toán học của những đại lượng sử dụng trong giải thuật. Ví dụ, về số Fibonacci, ngoài cách tính theo định nghĩa Fn = Fn-1 + Fn-2 (n ≥ 2) học sinh cần biết các cách tính khác, biết được tốc độ tăng của các số trong dãy là xấp xỉ 1.618. Quỹ thời gian giảng dạy không nhiều, vì vậy cần cân nhắc kỹ khi lựa chọn nội dung, phương pháp và trình tự truyền đạt kiến thức cơ sở cho học sinh. Đây là khối lượng kiến thức cần trang bị trong quá trình giảng dạy chung và chủ yếu là trong giai đoạn làm việc với đội dự tuyển. Khối lượng kiến thức phần này rất lớn, nhưng ổn định trong khoảng thời gian dài và quyết định chất lượng, hiệu quả của việc bồi dưỡng đội tuyển sau này. Chính vì vậy nó cần phải được chuẩn bị hết sức chu đáo và chi tiết. Đối với đội dự tuyển, mỗi chuyên đề sơ đồ lý tưởng trình bày bao gồm các nội dung: Mô hình toán học: phát biểu bài toán dưới dạng toán học thuần túy, Cơ sở toán học của giải thuật, Các cách hiện thực hóa giải thuật: Hình 6 12 Cấu trúc dữ liệu, Sơ đồ xử lý, Chương trình, Độ phức tạp, Các loại bài toán có cùng mô hình toán học, Một số bài toán ứng dụng. Trình tự truyền đạt không quan trọng, độ sâu chuyên môn trong từng mục phụ thuộc vào thời lượng cho phép, vào khả năng tiếp thu của nhóm học sinh cụ thể. Phần Sơ đồ xử lý là trọng tâm của toàn bộ nội dung trình bày. Nói chung, mỗi sơ đồ xử lý đòi hỏi một cách tổ chức dữ liệu riêng. Nó phụ thuộc nhiều vào công cụ lập trình, phụ thuộc vào công cụ xử lý mà hệ thống lập trình cung cấp đối với loại dữ liệu đã chọn. Ở đây giải thuật được trình bày lại trên ngôn ngữ của dữ liệu. Kỹ năng trình bày giải thuật trên ngôn ngữ của dữ liệu là điểm yếu của phần lớn học sinh. Việc rèn luyện kỹ năng này còn quan trọng hơn lập trình! Nếu học sinh trình bày tốt một giải thuật nào đó trên ngôn ngữ dữ liệu thì thậm chí không nhất thiết phải lập trình. Tạo thói quen và kỹ năng trình bày giải thuật trên ngôn ngữ dữ liệu là một quá trình. Để tạo được thói quen thì phải tuân thủ nguyên tắc “Văn ôn võ luyện”: thường xuyên, liên tục yêu cầu học sinh tập trình bày. Bên cạnh việc trình bày giải thuật với các bài mới cần ôn lại cách trình bày các bài đã làm. Một trong những điểm mấu chốt để có thể trình bày được giải thuật trên ngôn ngữ dữ liệu là nói được một cách rõ ràng, ngắn gọn và tuyệt đối chính xác vai trò, ý nghĩa của các dữ liệu dùng trong giải thuật. Việc trình bày này được thực trên ngôn ngữ tự nhiên và toán học, vì vậy tuyệt đối tránh việc đọc câu lệnh của chương trình! Ví dụ: Chuyên đề về số Catalan. Bài toán: Xét dãy số nguyên A = (a0, a1, a2, . . ., a2n) thỏa mãn các điều kiện:  ai ≥ 0, i = 0 ÷ 2n,  |ai – ai-1| = 1, i =1 ÷ 2n. Yêu cầu: Cho số nguyên n (0 ≤ n ≤ 50). Hãy tính số lượng dãy số A khác nhau thỏa mãn các điều kiện đã nêu. 13 Dữ liệu: Vào từ file văn bản CAT.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n. Kết quả: Đưa ra file văn bản CAT.OUT, mỗi kết quả đưa ra trên một dòng dưới dạng số nguyên. Ví dụ: CAT.INP CAT.OUT 2 6 4 2 132 14 Cơ sở toán học: Với n cho trước, gọi số lượng dãy A tìm được là cn. Dãy số C = (c0, c1, c2, . . .) được gọi là dãy số Catalan (theo tên nhà toán học Bỉ Eugène Charles Catalan). Số ci được gọi là số Catalan. Số Catalan thường gặp trong một loạt các bài toán tổ hợp khác nhau. Những số đầu tiên của dãy số Catalan là: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, . . . Các cách tính số Catalan cn: , trong đó i. là tổ hợp chập k của n, ii. C0 = 1, Cn = iii. 2(2n-1) Cn-1 n+1 nk k k 2 Sơ đồ lặp: n iv. v. Cn   14 p0 = 1, pi=0, i =1, 2, . . ., n i=1÷n j =1 ÷ i pi=pi+pi-1 cn=pn vi. Tính gần đúng: Sơ đồ tính toán: Mỗi cách tính phù hợp với một số loại bài toán khi làm việc với số Catalan. Các cách tính thứ 2 và thứ năm chỉ đòi hỏi dùng các phép cộng và nhân. Điều này thích hợp với n lớn vì Cn tăng rất nhanh theo n (công thức 6). Cách tính thứ 5 có độ phức tạp cao nhất, nhưng lại cung cấp đầy đủ thông tin nhất về dãy số catalan cũng như việc phân bố các cấu hình tạo ra một số của dãy. Một số bài toán tổ hợp có kết quả là Cn: - Số lượng biểu thức ngoặc đúng có thể xây dựng từ n cặp ngoặc tròn “(“ và “)”, ví dụ, với n = 3 ta có 5 biểu thức: ((())) (()()) (())() ()(()) ()()() Hình 7 - Số cây nhị phân đầy đủ không đẳng cấu có n+1 nút lá (cây nhị phân mà mỗi nút nếu không phải là lá thì có đúng 2 nút con): Hình 8 - Số đường đi từ điểm tọa độ (0, 0) tới điểm tọa độ (n, n), qua các điểm nguyên của lưới ô vuông kích thước n×n, chỉ sang phải và lên trên, không vượt qua đường chéo nối 2 điểm (0, 0) và (n, n): 15 Hình 9 - Số cách chia một đa giác lồi n+2 đỉnh thành các tam giác bằng các đường chéo không có điểm chung bên trong đa giác: Hình 10 - Số cách phủ cái bục hình bậc thang độ cao n bằng n hình chữ nhật, các hình chữ nhật không có diện tích chung khác không: Hình 11 - Số lượng các hoán vị từ 1 đến n sắp xếp được bằng stack (có thể chứng minh được rằng một hoán vị A = (a1, a2, . . ., an) các số tự nhiên từ 1 đến n có thể sắp xếp được bằng stack khi và chỉ khi không tồn tại i < j < k sao cho ak < ai < aj). Bài tập ứng dụng: 16 Bài 1. Xét tập các biểu thức ngoặc đúng chứa n cặp ngoặc tròn. Các biểu thức được sắp xếp theo thứ tự từ điển thành một danh sách, trong đó ký tự “)” được quy định có thứ tự từ điển nhỏ hơn “(“. Các biểu thức được đánh số từ 1 trở đi. Ví dụ, với n = 5 ta có: Số thứ tự Biểu thức ()()() 1 ()(()) 2 (())() 3 (()()) 4 ((())) 5 Cho S – biểu thức ngoặc đúng có n cặp ngoặc. Hãy xác định biểu thức thứ k sau biểu thức S trong danh sách. Dữ liệu: Vào từ file văn bản BR_LIST.INP:  Dòng đầu tiên chứa 2 số nguyên n và k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018),  Dòng thứ 2 chứa biểu thức S. Dữ liệu đảm bảo tồn tại lời giải. Kết quả: Đưa ra file văn bản BR_LIST.OUT gồm một dòng chứa biểu thức tìm được. Ví dụ: BR_LIST.INP 3 2 BR_LIST.OUT ((())) (())() Bài 2. Đơn vị tân binh có n người. Toàn đơn vị không ai giống ai, mỗi người có một chiều cao riêng. Viên thượng sỹ phụ trách huấn luyện có một thói quen khá độc đáo: cứ 9 giờ sáng, sau lúc nghỉ giải lao giữ buổi tập, ra lệnh tập hợp đơn vị thành một hàng dọc, ai muốn đứng ở chổ nào trong hàng cũng được! Viên thượng sỹ sẽ đi từ đầu hàng đến cuối hàng, chỉ định 3 người đi giúp nhà bếp nấu ăn. Những người được chỉ định sẽ bước sang phải một bước. Nếu 3 người được chỉ định này làm thành một hàng có chiều cao tăng dần nếu nhìn từ đầu của hàng, thượng sỹ sẽ rất hài lòng. Hôm đó đơn vị sẽ được nghỉ đi ăn trưa đúng giờ. Nếu thượng sỹ không chọn được 3 người vừa ý theo tiêu chuẩn trên thì thôi rồi, khả năng được nghỉ về ăn ăn cơm đúng giờ đúng bằng khă năng bạn bị một con cá mập mắc vi rút cúm gà H5N1 tấn công ở giữa Xa ha ra! Mà dù nếu có được về đúng giờ thì chắc gì còn có sức mà ăn. 17 Tuy vậy, nếu cẩn thận một chút thì khả năng thoát được con thịnh nộ của thượng sỹ là rất lớn. Hãy tính số khả năng xếp hàng để bao giờ cùng tìm được 3 người theo yêu cầu và đưa ra theo mô đun m. Dữ liệu: Vào từ file văn bản LINE_UP.INP gồm một dòng chứa 2 số nguyên n và m (3  n  25 000, 1  m  2109). Kết quả: Đưa ra file văn bản LINE_UP.OUT một số nguyên – số khả năng tìm được theo mô đun m. Ví dụ: LINE_UP.INP 5 1000 Các giải thuật cơ sở LINE_UP.OUT 78 Ngay ở mức đội dự tuyển học sinh vẫn cần phải được trang bị các giải thuật cơ bản như giải thuật Dijsktra tìm đường đi ngắn nhất, giải thuật Kruskal xác định cây khung, giải thuật so khớp KMP, . . . Các giải thuật cần được trang bị ở 2 mức: Cơ sở toán học, Cơ sở lập trình. Mức cơ sở toán học cung cấp cho học sinh các kiến thức về bản chất của sơ đồ xử lý dữ liệu, cách hiện thực hóa trực tiếp các sơ đồ đó, các cấu trúc dữ liệu cần tổ chức. Nói chung, giải thuật ở mức cơ sở toán học dễ hiểu, dễ lập trình, nhưng có độ phức tạp khá cao (thông thường là O(n2) hoặc O(nlogn)). Mặc dù là cơ sở toán học nhưng sau phần này học sinh vẫn phải biết và nhớ các hàm, thủ tục hiện thực hóa giải thuật. Các hàm, thủ tục này nên giới thiệu trực tiếp cho học sinh cùng với các tiểu xảo tổ chức dữ liệu và xử lý (nếu có). Cơ sở lập trình là phần quan trọng nhất. Các vấn đề chính trong trang bị cơ sở lập trình: Các loại cấu trúc dữ liệu mà hệ thống lập trình hỗ trợ, Lô gic nâng cao hiệu quả của các giải thuật, Các giải thuật có hiệu năng cao. Các kiến thức này cần được trang bị cho học sinh dự tuyển và đội tuyển để học sinh có thể: 18 Khai thác hết sức mạnh của công cụ mình có, Nắm bắt được tư duy sáng tạo trong việc tìm kiếm và thiết kế giải thuật, Không mất nhiều thời gian và công sức đối với các kiến thức đã trở thành kinh điển. Việc cung cấp các kiến thức về cấu trúc dữ liệu mà hệ thống lập trình hỗ trợ không đơn thuần để học sinh trức tiếp sử dụng trong bài của mình mà quan trọng hơn là mở rộng thế giới quan của học sinh về cấu trúc dữ liệu, tạo hình mẫu để học sinh có định hướng trong việc thiết kế, tổ chức dữ liệu và xác định bộ công cụ xử lý dữ liệu đó. Trên thực tế, trong phần lớn các trường hợp, khi giải bài toán olympic người lập trình thường tự thiết kế các cấu trúc dữ liệu tương đương để phù hợp tối đa với nhu cầu xử lý của mình. Vì vậy kiến thức phần này mang tính chất định hướng, giúp cho học sinh có tầm nhìn chiến lược trong quá trình đoán nhận và thiết kế giải thuật. Các hệ thống lập trình hiện nay như Free Pascal 2.6, Dev C++ 4.9.9 đều cung cấp những thư viện khổng lồ hỗ trợ người dùng và đều có thể mang lại những hiệu quả tương đương trong lập trình. Các hệ lập trình trên C++ đều cung cấp các công cụ chuẩn hóa khởi tạo và xử lý các cấu trúc dữ liệu thường dùng như stack, heap, vector, deque, dòng xếp hàng ưu tiên v. v. . . Ví dụ, với cấu trúc dữ liệu c kiểu bất kỳ (được đảm bảo bởi hệ thống) phép c.push() luôn luôn là nạp dữ liệu vào cuối cấu trúc, c.pop() – xóa phần tử cuối cùng khỏi cấu trúc, c.front() – lấy giá trị của phần tử đầu cấu trúc ra xử lý, . . . Tùy từng loại cấu trúc, có thể có các phép xử lý chuẩn khác (nạp vào đầu/cuối cấu trúc, xóa phần tử đầu/cuối cấu trúc, đọc phần tử đầu/cuối cấu trúc, truy nhập vào phần tử bên trong, v. v. . . c.push() c.back() c.front() c.pop_front() c.push_back() Cấu trúc c Hình 12 19 c.pop() Ngoài ra hệ thống còn cung cấp một bộ các phép xử lý phong phú tác động lên cấu dữ liệu đã khai báo. Do tính chuẩn hóa cao, việc giới thiệu và nắm bắt các công cụ này không đòi hỏi quá nhiều thời gian và công sức trong giảng dạy cũng như học tập. Vấn đề quan trọng là nắm được vai trò, vị trí các cấu trúc đó để có thể áp dụng đúng lúc, đúng chổ và đúng mức, đảm bảo hiệu quả lập trình cao. Trong CSDL cho các bài toán olympic (và nhiều bài toán thực tế khác) những thuộc tính được dùng nhiều nhất là giá trị và số thứ tự. C++ cung cấp kiểu dữ liệu pair (cặp) – một công cụ hết sức thuận tiện và hiệu quả để lưu trữ và xử lý cặp dữ liệu có liên quan lô gic tới nhau. 1.3.2. CÁC GIẢI THUẬT CƠ SỞ Bản chất và sơ đồ tiếp cận trong giảng dạy cũng như học tập và triển khai ứng dụng không thay đổi, nhưng chất lượng giải thuật thay đổi phụ thuộc vào cấu trúc dữ liệu được lựa chọn và cách giải quyết các bước bắt buộc có tính chất tiền định của giải thuật hoặc lớp giải thuật đó. Thông thường một số bước trở thành những bài toán con thuộc lớp giải thuật khác. Như vậy, yếu tố giải thuật kép xuất hiện ngay cả trong việc xây dựng cơ sở. Nội dung của phần trang bị kiến thức cơ sở: Bản chất của vấn đề, Các cách giải quyết, Giải thuật hiệu quả nhất. Bản chất của vấn đề: Xét các vấn đề đơn giản, thường gặp trong việc giải quyết các bài toán, giới thiệu vai trò, vị trí của bài toán trong lý thuyết giải thuật. Vấn đề có thể được xem xét trực tiếp từ mô hình toán học. Các cách giải quyết: Nêu ngắn gọn các giải thuật đơn giản, hiển nhiên, dễ lập trình nhưng có độ phức tạp cao (O(n3), O(n2)). Phần này hỗ trợ cho học sinh hiểu sâu hơn bản chất của bài toán, thấy được lô gic phát triển, từ đó: Nhanh chóng nắm bắt được tư tưởng của giải thuật hiệu quả nhất sẽ xét, Trang bị cho học sinh phương pháp tư duy sáng tạo, đường lối cải tiến, phát triển giải thuật. Các cách giải quyết hiển nhiên, “tầm thường” này vẫn có tác dụng nhất định trong lập trình, đặc biệt khi các bài toán (hoặc bài toán con) có kích thước nhỏ. 20