Tài liệu Skkn tin học ứng dụng bài tập trên uva trong giảng dạy chuyên tin

BM 01-Bia SKKN SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI Trường THPT Chuyên Lương Thế Vinh Mã số: ................................ (Do HĐKH Sở GD&ĐT ghi) SÁNG KIẾN KINH NGHIỆM ỨNG DỤNG BÀI TẬP TRÊN UVA TRONG GIẢNG DẠY CHUYÊN TIN Người thực hiện: NGUYỄN HOÀNG ANH Lĩnh vực nghiên cứu: - Quản lý giáo dục - Phương pháp dạy học bộ môn: Tin học - Lĩnh vực khác: Chuyên đề giảng dạy chuyên tin Có đính kèm: Các sản phẩm không thể hiện trong bản in SKKN  Mô hình  Đĩa CD (DVD)  Phim ảnh  Hiện vật khác (các phim, ảnh, sản phẩm phần mềm) Năm học: 2015 - 2016 2 SƠ LƯỢC LÝ LỊCH KHOA HỌC I. THÔNG TIN CHUNG VỀ CÁ NHÂN 1. Họ và tên: NGUYỄN HOÀNG ANH 2. Ngày tháng năm sinh: 08/09/1987 BM02-LLKHSKKN 3 . N a m , N ữ : Nam 4. Địa chỉ: 10/8-Tổ 1-Kp1-P Bửu Long- Biên Hòa- Đồng Nai 5. Điện thoại: 6. Fax: (CQ)/ (NR); ĐTDĐ: 0945 648 411 E-mail: [email protected] 7. Chức vụ: Giáo viên 8. Nhiệm vụ được giao: - Giáo viên bộ môn Tin học. - Giáo viên chủ nhiệm lớp 11 Chuyên Tin - Phụ trách một số chuyên đề chuyên lớp 10 và 11. - Tham gia bồi dưỡng đội tuyển HSG Quốc gia. 9. Đơn vị công tác: Trường THPT Chuyên Lương Thế Vinh II. TRÌNH ĐỘ ĐÀO TẠO - Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Cử nhân - Năm nhận bằng: 2010 - Chuyên ngành đào tạo: Tin học III. KINH NGHIỆM KHOA HỌC - Lĩnh vực chuyên môn có kinh nghiệm: Giảng dạy Tin học - Số năm có kinh nghiệm: 6 - Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: 03  Hàm Z trong bài toán so khớp chuỗi - 2012-2013  Ứng dụng hàm Z! trong giải các bài toán tin – 2013-2014  Phân loại bài tập theo chuyên đề tin 10 - 2014-2015 BM03-TMSKKN ĐỀ TÀI ỨNG DỤNG BÀI TẬP TRÊN UVA TRONG GIẢNG DẠY CHUYÊN TIN I. Lý do chọn đề tài Trong quá trình giảng dạy chuyên Tin, giáo viên phục trách giảng dạy chuyên phải liên tục cập nhật và phân loại bài tập tương ứng với các chuyên đề mà mình phụ trách để học sinh được luyện tập. Hệ thống bài tập trong sách giáo khoa chuyên Tin còn hạn chế về số lượng và tính đa dạng cũng như là để học sinh có thể chủ động tự chấm bài khi làm bài tập ở nhà. Hiện tại đang có một số hệ thống chấm online như VN.SPOJ, Codeforces, UVA… tuy nhiên việc phân loại, hệ thống bài tập trên các hệ thống này chưa thực sự rõ ràng và phù hợp với khả năng phân loại của học sinh. Vì thế tôi chọn đề tài có mục đích phân loại và hệ thống lại các bài tập trên UVA để làm hệ thống bài tập theo chuyên đề trong giảng dạy chuyên Tin tại cơ sở. ỨNG DỤNG BÀI TẬP TRÊN UVA TRONG GIẢNG DẠY CHUYÊN TIN là một gợi ý có tính tham khảo trong quá trình giảng dạy chuyên Tin. Có thể áp dụng với các đối tượng học sinh lớp 10,11 có đam mê và cũng là để các em có thể tự nâng cao khả năng đọc tài liệu bằng tiếng Anh trong quá trình làm bài. Đồng thời, hệ thống UVA còn cung cấp chức năng giám sát tiến độ làm bài của học sinh trong danh sách mà giáo viên cài đặt. Từ đó giúp giáo viên có thể đánh giá được một phần nào sự tích cực và khả năng hiện của từng học sinh. Phần kiểm tra đánh giá bằng UHunt sẽ được giới thiệu ở một đề tài khác. Đề tài được thiết kế theo dạng danh sách các bài tập hiện có trên hệ thống UVA được sắp xếp áp dụng theo chuyên đề mang tính tham khảo. Tài liệu không nhắc lại các vấn đề về lý thuyết. II. Cơ sở lý luận-thực tiễn - Khung chuyên đề (tham khảo): o Các bài toán làm quen với kỹ thuật lập trình. o Các phương pháp tiếp cận bài toán:  Cấu trúc dữ liệu  Tìm kiếm  Chia để trị  Tham lam  Quy hoạch động o Đồ thị  DFS – Depth First Search  BFS – Breadth First Search  Kruskal  Dijkstra  Bellman Ford  Floyd Warshall  Edmonds Karp  Các dạng đồ thị đặc biệc:  Tree-Cây  Directed Acyclic Graph –  Bipartite graph – Đồ thị hai phía o Toán ứng dụng  Ad-Hoc – Các bài toán hiển nhiên , suy luận  Lý thuyết số  Số nguyên tố  UCLN-Ước chung lớn nhất, BCNN –Bội chung nhỏ nhất.  Hàm Euler  Thuật toán Eulich mở rộng – Giải quyết các bài toán Diophantine tuyến tính  Thuyết đồng dư  Fibonacci  Giai thừa  Các bài toán hỗn hợp  Kết hợp  Tìm chu trình  Tìm các số tận cùng – số dư một dãy phép tính hoặc phép giai thừa…  Xác suất thống kê.  Đại số tuyến tính. o Xử lý xâu  Các bài toán xử lý xâu cơ bản  Xử lý xâu bằng quy hoạch động  Biến đổi xâu – khoảng cách xâu  Xâu con chung dài nhất  Palindrome  Cây hậu tố -Mảng hậu tố  Cây hậu tố  Ứng dụng cây hậu tố  Mảng hậu tố o Hình học tính toán:  Hình học cơ bản  GrahamScan – Quét tìm bao lồi  Bài toán cắt nhau  Chia để trị. - Hệ thống làm bài trực tuyến Uva Online Judge. o Địa chỉ: https://uva.onlinejudge.org o Tập hợp các bài tập từ cuộc thi ACM-ICPC được chọn lọc và bổ sung. o Test chấm được sử dụng là bộ test sử dụng trong các cuộc thi chính thức nên có tính khách quan và chính xác cao. o Có hệ thống chấm online giúp học sinh có thể làm bài mọi lúc, mọi nơi có thể truy cập internet, giúp học sinh chủ động trong việc làm bài để nâng cao trình độ. o Có hệ thống Uhunt giúp giáo viên giám sát quá trình làm bài của học sinh rất tiện lợi. - Học sinh lớp chuyên đã được làm quen với hình thức làm bài và nộp bài online trên các hệ thống chấm bài. - III. Tổ chức thực hiện – giải pháp A. Hình thức triển khai: Mỗi chuyên đề tương ứng, giáo viên tham khảo trong danh sách các bài tập tương ứng và chọn ra các bài phù hợp với lượng kiến thức từng buổi, trình độ của học sinh. Cho học sinh làm bài và sử dụng chức năng Uhunt để giám sát quá trình làm bài và tiến độ làm của học sinh. Giáo viên trong giai đoạn đầu cần theo sát để giúp học sinh hiểu được các đề bài sử dụng từ lạ và để giúp học sinh làm quen với hình thức chấm của UVA, từ đó có chiến lược làm bài phù hợp. B. Các bài toán rèn luyện ban đầu: 1. Các bài toán làm quen kỹ thuật lập trình 01. UVa 100 - The 3n + 1 problem 02. UVa 272 - TEX Quotes 03. UVa 394 - Mapmaker 04. UVa 483 - Word Scramble 05. UVa 573 - The Snail 06. UVa 661 - Blowing Fuses 07. UVa 739 - Soundex Indexing 08. UVa 837 - Light and Transparencies 09. UVa 941 - Permutations 10. UVa 10082 - WERTYU 11. UVa 10141 - Request for Proposal 12. UVa 10281 - Average Speed 13. UVa 10363 - Tic Tac Toe 14. UVa 10420 - List of Conquests 15. UVa 10528 - Major Scales 16. UVa 10683 - The decadary watch 17. UVa 10703 - Free spots 18. UVa 10812 - Beat the Spread 19. UVa 10921 - Find the Telephone 20. UVa 11044 - Searching for Nessy 21. UVa 11150 - Cola 22. UVa 11223 - O: dah, dah, dah! 23. UVa 11340 - Newspaper 24. UVa 11498 - Division of Nlogonia 25. UVa 11547 - Automatic Answer 26. UVa 11616 - Roman Numerals 27. UVa 11727 - Cost Cutting 28. UVa 11800 - Determine the Shape C. Các phương pháp tiếp cận bài toán: 1. Cấu trúc dữ liệu: 01. UVa 482 - Permutation Arrays 02. UVa 594 - One Two Three Little Endian 03. UVa 11340 - Newspaper 04. UVa 146 - ID Codes 05. UVa 10194 - Football 06. UVa 10258 - Contest 07. UVa 299 - Train Swapping 08. UVa 612 - DNA 09. UVa 10810 - Ultra 10. UVa 11462 - Age Sort 11. UVa 11495 - Bubbles and Buckets 12. UVa 127 - “Accordian” 13. UVa 514 - Rails 14. UVa 673 - Parentheses Balance 15. UVa 727 - Equation 16. UVa 336 - A Node Too Far 17. UVa 10901 - Ferry Loading III 18. UVa 11034 - Ferry Loading IV 19. UVa 10226 - Hardwood Species 20. UVa 11239 - Open Source 21. UVa 11308 - Bankrupt Baker 22. UVa 11136 - Hoax or what 23. UVa 908 - Re-connecting Computer Sites 24. UVa 11492 - Babel 2. Thuật toán tìm kiếm: 01. UVa 154 - Recyling 02. UVa 441 - Lotto 03. UVa 639 - Don’t Get Rooked 04. UVa 725 - Division 05. UVa 10360 - Rat Attack 06. UVa 10662 - The Wedding 07. UVa 11242 - Tour de France 08. UVa 11804 - Argentina 09. UVa 10496 - Collecting Beepers 10. UVa 193 - Graph Coloring 12. UVa 222 - Budget Travel 13. UVa 524 - Prime Ring Problem 14. UVa 624 - CD 15. UVa 628 - Passwords 16. UVa 729 - The Hamming Distance Problem 17. UVa 750 - 8 Queens Chess Problem 18. UVa 10285 - Longest Run on a Snowboard 3. Chia để trị 01. UVa 679 - Dropping Balls 02. UVa 714 - Copying Books 03. UVa 957 - Popes 04. UVa 10077 - The Stern-Brocot Number System 05. UVa 10341 - Solve It 06. UVa 10369 - Arctic Networks 07. UVa 10474 - Where is the Marble? 08. UVa 10611 - Playboy Chimp 09. UVa 11262 - Weird Fence 4. Tham lam 01. UVa 410 - Station Balance 02. UVa 10020 - Minimal Coverage 03. UVa 10340 - All in All 04. UVa 10440 - Ferry Loading II 05. UVa 10670 - Work Reduction 06. UVa 10763 - Foreign Exchange 07. UVa 11054 - Wine Trading in Gergovia 08. UVa 11292 - Dragon of Loowater 09. UVa 11369 – Shopaholic 5. Quy hoạch động 01. UVa 103 - Stacking Boxes 02. UVa 111 - History Grading 03. UVa 231 - Testing the Catcher 04. UVa 481 - What Goes Up? 05. UVa 497 - Strategic Defense Initiative 06. UVa 10051 - Tower of Cubes 07. UVa 10534 - Wavio Sequence 08. UVa 11790 - Murcia’s Skyline 09. UVa 11003 - Boxes 10. UVa 11456 - Trainsorting 11. UVa 147 - Dollars 12. UVa 166 - Making Change 13. UVa 357 - Let Me Count The Ways 14. UVa 674 - Coin Change 15. UVa 10306 - e-Coins 16. UVa 10313 - Pay the Price 17. UVa 11137 - Ingenuous Cubrency 18. UVa 11517 - Exact Change 19. UVa 108 - Maximum Sum 20. UVa 836 - Largest Submatrix 21. UVa 10074 - Take the Land 22. UVa 10667 - Largest Block 23. UVa 10827 - Maximum Sum on a Torus 24. UVa 507 - Jill Rides Again 25. UVa 10684 - The Jackpot 26. UVa 562 - Dividing Coins 27. UVa 990 - Diving For Gold 28. UVa 10130 - SuperSale 29. UVa 116 - Unidirectional TSP 30. UVa 473 - Raucuous Rockers 31. UVa 607 - Scheduling Lectures 32. UVa 10003 - Cutting Sticks 33. UVa 10337 - Flight Planner 34. UVa 10891 - Game of Sum 35. UVa 11450 - Wedding Shopping 36. UVa 10364 - Square 37. UVa 10651 - Pebble Solitaire 38. UVa 10908 - Largest Square 39. UVa 10911 - Forming Quiz Teams 40. UVa 590 - Always on the Run 41. UVa 910 - TV Game 42. UVa 10681 - Teobaldo’s Trip 43. UVa 10702 - Traveling Salesman 44. UVa 10243 - Fire! Fire!! Fire!!! 45. UVa 11307 - Alternative Arborescence D. Mô hình Đồ thị 1. Depth First Search – DFS – Tìm kiếm theo chiều sâu 01. UVa 260 - Il Gioco dell’X 02. UVa 352 - Seasonal War 03. UVa 459 - Graph Connectivity 04. UVa 469 - Wetlands of Florida 05. UVa 572 - Oil Deposits 06. UVa 657 - The Die is Cast 07. UVa 782 - Countour Painting 08. UVa 784 - Maze Exploration 09. UVa 785 - Grid Colouring 10. UVa 852 - Deciding victory in Go 11. UVa 10336 - Rank the Languages 12. UVa 10926 - How Many Dependencies? 13. UVa 10946 - You want what filled? 14. UVa 11110 - Equidivisions 15. UVa 11518 - Dominos 2 16. UVa 11749 - Poor Trade Advisor 17. UVa 315 - Network 18. UVa 610 - Street Directions 19. UVa 796 - Critical Links 20. UVa 10199 - Tourist Guide 21. UVa 10731 - Test 22. UVa 11504 - Dominos 23. UVa 11709 - Trust Groups 24. UVa 11770 - Lighting Away 25. UVa 124 - Following Orders 26. UVa 200 - Rare Order 27. UVa 872 - Ordering 28. UVa 10305 - Ordering Tasks 6. Breath First Search – BFS – Tìm kiếm theo chiều rộng 01. UVa 336 - A Node Too Far 02. UVa 383 - Shipping Routes 03. UVa 417 - Word Index 04. UVa 429 - Word Transformation 05. UVa 439 - Knight Moves 06. UVa 532 - Dungeon Master 07. UVa 567 - Risk 08. UVa 627 - The Net 09. UVa 762 - We Ship Cheap 10. UVa 924 - Spreading the News 11. UVa 928 - Eternal Truths 12. UVa 10009 - All Roads Lead Where? 13. UVa 10044 - Erdos numbers 14. UVa 10067 - Playing with Wheels 15. UVa 10102 - The Path in the Colored Field 16. UVa 10150 - Doublets 17. UVa 10422 - Knights in FEN 18. UVa 10610 - Gopher and Hawks 19. UVa 10653 - Bombs! NO they are Mines!! 20. UVa 10959 - The Party, Part I 21. UVa 11049 - Basic Wall Maze 22. UVa 11352 - Crazy King 23. UVa 11513 - 9 Puzzle 24. UVa 11545 - Avoiding Jungle in the Dark 25. UVa 11730 - Number Transformation 26. UVa 11792 - Krochanska is Here! 27. UVa 10004 - Bicoloring 28. UVa 11080 - Place the Guards 29. UVa 11101 - Mall Mania 30. UVa 11624 - Fire! 7. Kruskal’s 01. UVa 908 - Re-connecting Computer Sites 02. UVa 10034 - Freckles 03. UVa 10307 - Killing Aliens in Borg Maze 04. UVa 11228 - Transportation System 05. UVa 11631 - Dark Roads 06. UVa 11710 - Expensive Subway 07. UVa 11733 - Airports 08. UVa 11747 - Heavy Cycle Edges 09. UVa 10147 - Highways 10. UVa 10369 - Arctic Networks 11. UVa 10397 - Connect the Campus 12. UVa 10600 - ACM Contest and Blackout 13. UVa 10842 - Traffic Flow 8. DIJKSTRA’S – Bellman Ford’s 01. UVa 341 - Non-Stop Travel 02. UVa 929 - Number Maze 03. UVa 10278 - Fire Station 04. UVa 10603 - Fill 05. UVa 10801 - Lift Hopping 06. UVa 10986 - Sending email 07. UVa 11377 - Airport Setup 08. UVa 11492 - Babel 09. UVa 11635 - Hotel Booking 10. UVa 558 - Wormholes 11. UVa 10557 - XYZZY 12. UVa 11280 - Flying to Fredericton 9. Floyd Warshall’s 01. UVa 186 - Trip Routing 02. UVa 341 - Non-Stop Travel 03. UVa 423 - MPI Maelstrom 04. UVa 821 - Page Hopping 05. UVa 10075 - Airlines 06. UVa 10171 - Meeting Prof. Miguel 07. UVa 11015 - 05-32 Rendezvous 08. UVa 10246 - Asterix and Obelix 09. UVa 10724 - Road Construction 10. UVa 10793 - The Orc Attack 11. UVa 10803 - Thunder Mountain 12. UVa 11463 - Commandos 14. UVa 334 - Identifying Concurrent Events 15. UVa 534 - Frogger 16. UVa 544 - Heavy Cargo 17. UVa 869 - Airline Comparison 18. UVa 925 - No more prerequisites, please! 19. UVa 10048 - Audiophobia 20. UVa 10099 - Tourist Guide 10. Maximum Flow 01. UVa 820 - Internet Bandwidth 02. UVa 10480 - Sabotage 03. UVa 10779 - Collector’s Problem 04. UVa 11506 - Angry Programmer 05. UVa 563 - Crimewave 06. UVa 10330 - Power Transmission 07. UVa 10511 - Councilling 08. UVa 10594 - Data Flow 09. UVa 10806 - Dijkstra, Dijkstra. 11. Các dạng đồ thị đặc biệt a. Cây-Tree 01. UVa 112 - Tree Summing 02. UVa 115 - Climbing Trees 03. UVa 122 - Trees on the level 04. UVa 536 - Tree Recovery 05. UVa 615 - Is It A Tree? 06. UVa 699 - The Falling Leaves 07. UVa 712 - S-Trees 08. UVa 10308 - Roads in the North 09. UVa 10459 - The Tree Root 10. UVa 10701 - Pre, in and post 11. UVa 10938 - Flea Circus 12. UVa 11695 - Flight Planning b. Directed Acyclic Graph 01. UVa 103 - Stacking Boxes 02. UVa 10000 - Longest Paths 03. UVa 10166 - Travel 04. UVa 10029 - Edit Step Ladders 05. UVa 10350 - Liftless Eme 06. UVa 11324 - The Largest Clique 07. UVa 825 - Walking on the Safe Side 08. UVa 926 - Walking Around Wisely 09. UVa 988 - Many paths, one destination c. Đồ thị 2 phía – Bipartite Graph 01. UVa 670 - The Dog Task 02. UVa 753 - A Plug for Unix 03. UVa 10080 - Gopher II 04. UVa 10092 - The Problem with the Problemsetter 05. UVa 10735 - Euler Circuit 06. UVa 11045 - My T-Shirt Suits Me 07. UVa 11418 - Clever Naming Patterns 08. UVa 11159 - Factors and Multiples 09. UVa 11419 - SAM I AM E. Mô hình Toán 1. Dạng công thức đặc biệt 01. UVa 344 - Roman Numerals 02. UVa 377 - Cowculations 03. UVa 10346 - Peter’s Smoke 04. UVa 10940 - Throwing Cards Away II 05. UVa 11130 - Billiard bounces 06. UVa 11231 - Black and White Painting 07. UVa 11313 - Gourmet Games 08. UVa 11428 - Cubes 09. UVa 11547 - Automatic Answer 10. UVa 11723 - Numbering Road 11. UVa 11805 - Bafana Bafana 12. Lý thuyết số a. Số nguyên tố: 01. UVa 294 - Divisors 02. UVa 406 - Prime Cuts 03. UVa 516 - Prime Land 04. UVa 524 - Prime Ring Problem 05. UVa 543 - Goldbach’s Conjecture 06. UVa 583 - Prime Factors 07. UVa 686 - Goldbach’s Conjecture (II) 08. UVa 897 - Annagramatic Primes 09. UVa 914 - Jumping Champion 10. UVa 993 - Product of digits 11. UVa 10006 - Carmichael Numbers 12. UVa 10042 - Smith numbers 13. UVa 10140 - Prime Distances 14. UVa 10200 - Prime Time 15. UVa 10235 - Simply Emirp 16. UVa 10311 - Goldbach and Euler 17. UVa 10394 - Twin Primes 18. UVa 10533 - Digit Primes 19. UVa 10539 - Almost Prime Numbers 20. UVa 10637 - Coprimes 21. UVa 10650 - Determinate Prime 22. UVa 10699 - Count the Factors 23. UVa 10738 - Riemann vs. Mertens 24. UVa 10789 - Prime Frequency 25. UVa 10852 - Less Prime 26. UVa 10924 - Prime Words 27. UVa 10948 - The Primary Problem 28. UVa 11287 - Pseudoprime Numbers 29. UVa 11408 - Count DePrimes 30. UVa 11466 - Largest Prime Divisor b. Ước chung lớn nhất (GCD) – Bội chung nhỏ nhất (LCM) 01. UVa 332 - Rational Numbers from Repeating Fractions 02. UVa 412 - Pi 03. UVa 530 - Binomial Showdown 04. UVa 10193 - All You Need Is Love 05. UVa 10407 - Simple Division 06. UVa 10680 - LCM 07. UVa 10717 - Mint 08. UVa 10791 - Minimum Sum LCM 09. UVa 10892 - LCM Cardinality 10. UVa 11388 - GCD LCM 11. UVa 11417 – GCD c. Hàm Euler 01. UVa 10179 - Irreducible Basic Fractions 02. UVa 10299 - Relatives 03. UVa 10820 - Send A Table 04. UVa 11064 - Number Theory 05. UVa 11327 - Enumerating Rational Numbers d. Thuật toán Eulid mở rộng giải các bài toán Diophantine 01. UVa 718 - Skycraper Floors e. f. g. h. 02. UVa 10090 - Marbles 03. UVa 10104 - Euclid Problem Thuyết đồng dư 01. UVa 374 - Big Mod 02. UVa 602 - What Day Is It? 03. UVa 10174 - Couple-Bachelor-Spinster Numbers 04. UVa 10176 - Ocean Deep! Make it shallow!! 06. UVa 10489 - Boxes of Chocolates Số Fibonacci 01. UVa 495 - Fibonacci Freeze 02. UVa 763 - Fibinary Numbers 03. UVa 900 - Brick Wall Patterns 04. UVa 948 - Fibonaccimal Base 05. UVa 10183 - How many Fibs? 06. UVa 10229 - Modular Fibonacci 07. UVa 10334 - Ray Through Glasses 08. UVa 10450 - World Cup Noise 09. UVa 10497 - Sweet Child Make Trouble 10. UVa 10579 - Fibonacci Numbers 11. UVa 10862 - Connect the Cable Wires 12. UVa 11000 - Bee 13. UVa 11161 - Help My Brother (II) 14. UVa 11780 - Miles 2 Km Giai thừa 01. UVa 160 - Factors and Factorials 02. UVa 324 - Factorial Frequencies 03. UVa 568 - Just the Facts 04. UVa 623 - 500! 05. UVa 884 - Factorial Factors 06. UVa 10061 - How many zeros & how many digits? 07. UVa 10139 - Factovisors 08. UVa 10858 - Recover Factorial 09. UVa 10220 - I Love Big Numbers! 10. UVa 10323 - Factorial! You Must Be Kidding 11. UVa 10780 - Again Prime? No time. 12. UVa 11347 - Multifactorials 13. UVa 11415 - Count the Factorials Một số vấn đề khác:  Tổ hợp 01. UVa 326 - Extrapolation using a Difference Table 02. UVa 369 - Combinations 03. UVa 991 - Safe Salutations 04. UVa 10007 - Count the Trees 05. UVa 10219 - Find the Ways! 06. UVa 10303 - How Many Trees 07. UVa 10375 - Choose and Divide 08. UVa 10784 - Diagonal 09. UVa 10790 - How Many Points of Intersection? 10. UVa 10918 - Tri Tiling 11. UVa 11069 - A Graph Problem 12. UVa 11115 - Uncle Jack 13. UVa 11204 - Musical Instruments 14. UVa 11310 - Delivery Debacle 15. UVa 11401 - Triangle Counting 16. UVa 11554 - Hapless Hedonism  Tìm chu trình 01. UVa 350 - Pseudo-Random Numbers 02. UVa 408 - Uniform Generator 03. UVa 944 - Happy Numbers 04. UVa 10591 - Happy Number 05. UVa 11036 - Eventually periodic sequence 06. UVa 11053 - Flavius Josephus Reloaded 07. UVa 11549 - Calculator Conundrum  Chữ số tận cùng, phần dư – Dạng số đặc biệt 01. UVa 100 - The 3n + 1 problem 02. UVa 413 - Up and Down Sequences 03. UVa 694 - The Collatz Sequence 04. UVa 10408 - Farey Sequences 05. UVa 10930 - A-Sequence 06. UVa 11063 - B2 Sequences 07. UVa 136 - Ugly Numbers 08. UVa 138 - Street Numbers 09. UVa 443 - Humble Numbers 10. UVa 640 - Self Numbers 11. UVa 962 - Taxicab Numbers 12. UVa 974 - Kaprekar Numbers 13. UVa 10001 - Bangla Numbers 14. UVa 10006 - Carmichael Numbers 15. UVa 10042 - Smith Numbers 16. UVa 10044 - Erdos Numbers 17. UVa 10591 - Happy Number 18. UVa 11461 - Square Numbers 19. UVa 11472 - Beautiful Numbers  Xác Suất: 01. UVa 474 - Heads Tails Probability 02. UVa 542 - France 98 03. UVa 10056 - What is the Probability? 04. UVa 10491 - Cows and Cars 05. UVa 11176 - Winning Streak 06. UVa 11181 - Probability|Given 07. UVa 11500 - Vampires  Tuyến tính 01. UVa 10089 - Repackaging 02. UVa 10109 - Solving Systems of Linear Equations 03. UVa 10309 - Turn the Lights Off F. Xử lý xâu 1. Cơ bản 01. UVa 148 - Anagram Checker 02. UVa 159 - Word Crosses 03. UVa 263 - Number Chains 04. UVa 353 - Pesky Palindromes 05. UVa 401 - Palindromes 06. UVa 409 - Excuses, Excuses! 07. UVa 422 - Word Search Wonder 08. UVa 537 - Artificial Intelligence? 09. UVa 644 - Immediate Decodability 10. UVa 865 - Substitution Cypher 11. UVa 902 - Password Search 12. UVa 10010 - Where’s Waldorf? 13. UVa 10115 - Automatic Editing 14. UVa 10197 - Learning Portuguese 15. UVa 10293 - Word Length and Frequency 16. UVa 10391 - Compound Words 17. UVa 10508 - Word Morphing 18. UVa 10815 - Andy’s First Dictionary 19. UVa 10878 - Decode the Tape 20. UVa 10896 - Known Plaintext Attack 21. UVa 11056 - Formula 1 22. UVa 11062 - Andy’s Second Dictionary 23. UVa 11221 - Magic Square Palindrome 24. UVa 11233 - Deli Deli 25. UVa 11278 - One-Handed Typist 26. UVa 11362 - Phone List 27. UVa 11385 - Da Vinci Code 28. UVa 11048 - Automatic Correction of Misspellings 29. UVa 11713 - Abstract Names 30. UVa 11716 - Digital Fortress 31. UVa 11734 - Big Number of Teams will Solve This 13. Xử lý xâu bằng Quy hoạch động a. Biến đổi xâu-Xâu con chung dài nhất - Palindrome: 01. UVa 164 - String Computer 02. UVa 531 - Compromise 03. UVa 10066 - The Twin Towers 04. UVa 10100 - Longest Match 05. UVa 10192 - Vacation 06. UVa 10405 - Longest Common Subsequence 07. UVa 10739 - String to Palindrome 08. UVa 11151 - Longest Palindrome b. Cây hậu tố-Mảng hậu tố 01. UVa 719 - Glass Beads 02. UVa 10526 - Intellectual Property 03. UVa 11107 - Life Forms 04. UVa 11512 - GATTACA G. Mô hình Hình học tính toán 1. Cơ bản 01. UVa 184 - Laser Lines 02. UVa 270 - Lining Up 03. UVa 833 - Water Falls 04. UVa 10180 - Rope Crisis In Ropeland 05. UVa 10242 - Fourth Point 06. UVa 10263 - Railway 07. UVa 11068 - An Easy Task 08. UVa 11277 - The Silver Bullet 09. UVa 10005 - Packing polygons 10. UVa 10012 - How Big Is It 11. UVa 10136 - Chocolate Chip Cookies 12. UVa 10221 - Satellites 13. UVa 10432 - Polygon Inside A Circle 14. UVa 10451 - Ancient Village Sports 15. UVa 10589 – Area 16. UVa 143 - Orchard Trees 17. UVa 190 - Circle Through Three Points 18. UVa 438 - The Circumference of the Circle 19. UVa 10195 - The Knights Of The Round Table 20. UVa 10286 - The Trouble with a Pentagon 21. UVa 10347 - Medians 22. UVa 10991 - Region 23. UVa 11152 - Colourful Flowers 24. UVa 11437 - Triangle Fun 25. UVa 11479 - Is this the easiest problem? 26. UVa 11524 - In-Circle 27. UVa 11579 - Triangle Trouble 28. UVa 201 - Square 29. UVa 476 - Point in Figures: Rectangles 30. UVa 922 - Rectangles by the Ocean 31. UVa 10502 - Counting Rectangles 32. UVa 10908 - Largest Square 33. UVa 11207 - The Easiest Way 34. UVa 11455 - Behold My Quadrangle 35. UVa 535 - Globetrotter 36. UVa 10075 - Airlines 37. UVa 10316 - Airline Hub 38. UVa 10897 - Travelling Distance 39. UVa 11817 - Tunnelling The Earth 40. UVa 478 - Point in Figures: Rectangles, Circles, and Triangles 41. UVa 634 - Polygon 42. UVa 10078 - Art Gallery 43. UVa 10112 - Myacm Triangles 44. UVa 11447 - Reservoir Logs 45. UVa 11473 - Campus Roads 46. UVa 10088 - Trees on My Island 47. UVa 10297 - Beavergnaw 48. UVa 10387 - Billiard 49. UVa 11232 - Cylinder 50. UVa 11507 - Bender B. Rodriguez Problem 14. Graham Scan – Tìm bao lồi 01. UVa 109 - Scud Busters 02. UVa 218 - Moth Eradication 03. UVa 361 - Cops and Robbers 04. UVa 681 - Convex Hull Finding 05. UVa 811 - The Fortified Forest 06. UVa 10002 - Center of Masses 07. UVa 10065 - Useless Tile Packers 08. UVa 10135 - Herding Frosh 09. UVa 10173 - Smallest Bounding Rectangle 10. UVa 11626 - Convex Hull 15. Các bài toán tìm phần giao 01. UVa 191 - Intersection 02. UVa 378 - Intersecting Lines 03. UVa 866 - Intersecting line segments 04. UVa 920 - Sunny Mountain 05. UVa 972 - Horizon Line 06. UVa 10902 - Pick-up sticks 07. UVa 11343 - Isolated Segments 08. UVa 453 - Intersecting Circles 09. UVa 460 - Overlapping Rectangles 10. UVa 737- Gleaming the Cubes 11. UVa 904 - Overlapping Air Traffic Control 12. UVa 10301 - Rings and Glue 13. UVa 10321 - Polygon Intersection 14. UVa 11122 - Tri Tri 15. UVa 11345 - Rectangles 16. UVa 11515 - Cranes 17. UVa 11601 - Avoiding Overlaps 18. UVa 11639 - Guard the Land IV. Hiệu quả của đề tài Song song với việc hoàn thiện tài liệu, tôi đã áp dụng vào thực tế giảng dạy tại lớp chuyên được phân công phụ trách để vừa rút kinh nghiệm, vừa hoàn thiện và sắp xếp danh sách tài liệu hợp lý. - Việc ứng dụng tài liệu vào giảng dạy tại cơ sở mang lại một số hiệu quả sau: o Hứng thú học tập của học sinh được tăng lên trong quá trình học. o Các học sinh có đam mê được chủ động rèn luyện các kiến thức bằng hệ thống bài đa dạng. o Việc chấm bài của giáo viên sẽ đạt được một số thuận lợi:  Tiết kiệm thời gian  Đánh giá được học sinh một cách khách quan, phân loại được học sinh qua quá trình làm bài và chủ động chấm bài, từ đó đánh giá được khả năng tự học của học sinh. V. Đề xuất-khuyến nghị- khả năng áp dụng - Tiếp theo đề tài, đề nghị được tiếp tục phát triển ở những điểm sau: o Dịch lại sang tiếng Việt với mục đích diễn đạt một cách rõ ràng hơn bằng tiếng mẹ đẻ, nhằm giúp các học sinh bước đầu làm quen với cách đọc đề và diễn đạt đề bằng tiếng Anh. o Xây dựng hệ thống bài giảng tham khảo tương ứng các bài đã nêu ở đây, làm tư liệu để giáo viên có thể giúp học sinh giải đáp các thắc mắc trong quá trình làm bài trên hệ thống. o Xây dựng hệ thống test của giáo viên tương ứng với các bài để giúp giáo viên có thể tạo thành các bài tập và chấm bài tập trung tại lớp. Đề tài có thể được áp dụng triển khai từ đầu lớp 10 ngay sau giai đoạn làm quen với ngôn ngữ lập trình đến khi tập trung đội tuyển quốc gia. VI. Tài liệu tham khảo. - Uva.onlinejudge.org Topcoder.org Tài liệu giáo khoa chuyên Tin (Quyển 1,2,3) Sách bài tập giáo khoa chuyên Tin(Quyển 1,2,3) Tài liệu từ kho bài tập UVA.