Ebook Tài liệu giáo khoa chuyên tin, quyển 3

Bộ sách Tài Liệu Giáo Khoa Chuyên Tin Trọn Bộ gồm 3 quyển, quyển 1, 2 và 3. Cấu trúc mỗi quyển bao gồm . phần lí thuyết giới thiệu các khái niệm cơ bản, cần thiết, thường dùng nhất, phần áp dụng trình bày các bài toán thường gặp, cách giải và cài đặt chương trình; cuối cùng là các bài tập. Các chuyên đề trong bộ sách được lựa chọn mang tính hệ thống từ cơ bản đến chuyên sâu.

Tải về

Pass giải nén: chuyentin.pro

LỜI NÓI ðẦU Bộ Giáo dục và ðào tạo ñã ban hành chương trình chuyên tin học cho các lớp chuyên 10, 11, 12. Dựa theo các chuyên ñề chuyên sâu trong chương trình nói trên, các tác giả biên soạn bộ sách chuyên tin học, bao gồm các vấn ñề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài ñặt chương trình. Bộ sách gồm ba quyển, quyển 1, 2 và 3. Cấu trúc mỗi quyển bao gồm: phần lí thuyết, giới thiệu các khái niệm cơ bản, cần thiết trực tiếp, thường dùng nhất; phần áp dụng, trình bày các bài toán thường gặp, cách giải và cài ñặt chương trình; cuối cùng là các bài tập. Các chuyên ñề trong bộ sách ñược lựa chọn mang tính hệ thống từ cơ bản ñến chuyên sâu. Với trải nghiệm nhiều năm tham gia giảng dạy, bồi dưỡng học sinh chuyên tin học của các trường chuyên có truyền thống và uy tín, các tác giả ñã lựa chọn, biên soạn các nội dung cơ bản, thiết yếu nhất mà mình ñã sử dụng ñể dạy học với mong muốn bộ sách phục vụ không chỉ cho giáo viên và học sinh chuyên PTTH mà cả cho giáo viên, học sinh chuyên tin học THCS làm tài liệu tham khảo cho việc dạy và học của mình. Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham gia các kì thi học sinh giỏi Quốc gia, Quốc tế Hội thi Tin học trẻ Toàn quốc, Olympiad Sinh viên Tin học Toàn quốc, Kì thi lập trình viên Quốc tế khu vực ðông Nam Á, các tác giả ñã lựa chọn giới thiệu các bài tập, lời giải có ñịnh hướng phục vụ cho không chỉ học sinh mà cả sinh viên làm tài liệu tham khảo khi tham gia các kì thi trên. Lần ñầu tập sách ñược biên soạn, thời gian và trình ñộ có hạn chế nên chắc chắn còn nhiều thiếu sót, các tác giả mong nhận ñược ý kiến ñóng góp của bạn ñọc, các ñồng nghiệp, sinh viên và học sinh ñể bộ sách ñược ngày càng hoàn thiện hơn . Các tác giả

MỤC LỤC CHUYÊN ðỀ 1. THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN ........................................ 5 1. Thuật toán ........................................................................................................ 5 2. Phân tích thuật toán .......................................................................................... 6 Bài tập ................................................................................................................ 11 CHUYÊN ðỀ 2. CÁC KIẾN THỨC CƠ BẢN ........................................................................... 13 1. Hệ ñếm ........................................................................................................... 13 2. Số nguyên tố .................................................................................................. 14 3. Ước số, bội số ................................................................................................ 17 4. Lí thuyết tập hợp ............................................................................................ 18 5. Số Fibonacci .................................................................................................. 21 6. Số Catalan ...................................................................................................... 23 7. Xử lí số nguyên lớn ........................................................................................ 24 Bài tập ................................................................................................................ 33 CHUYÊN ðỀ 3. SẮP XẾP ........................................................................................................... 39 1. Phát biểu bài toán ........................................................................................... 39 2. Các thuật toán sắp xếp thông dụng ................................................................ 40 3. Sắp xếp bằng ñếm phân phối (Distribution Counting) .................................. 43 Bài tập ................................................................................................................ 51 CHUYÊN ðỀ 4. THIẾT KẾ GIẢI THUẬT ............................................................................... 59 1. Quay lui (Backtracking) ................................................................................. 59 2. Nhánh và cận ................................................................................................. 71 3. Tham ăn (Greedy Method)............................................................................. 78 4. Chia ñể trị (Divide and Conquer) .................................................................. 88 5. Quy hoạch ñộng (Dynamic programming) .................................................... 97 Bài tập .............................................................................................................. 107 CHUYÊN ðỀ 5. CÁC THUẬT TOÁN TRÊN ðỒ THỊ ........................................................ 126 1. Các khái niệm cơ bản ................................................................................... 127 2. Biểu diễn ñồ thị ............................................................................................ 132 3. Các thuật toán tìm kiếm trên ñồ thị .............................................................. 143 4. Tính liên thông của ñồ thị ............................................................................ 158 5. Vài ứng dụng của DFS và BFS .................................................................... 182 6. ðồ thị Euler và ñồ thị Hamilton ................................................................... 201 HƯỚNG DẪN GIẢI BÀI TẬP ................................................................................................ thiếu